First-order permutation-equivariant linear layers
OpenQAlgorithms.Papers.Independent.Intakenext100.P94.first_order_layerLet , let be the fixed shared pointwise nonlinearity, and let be linear. Permutations act by . Then is equivariant if and only if there are real weights , chosen independently of the input, such that
Consequently the layer output is . This gives the complete linear layer form; at the coefficients are redundant. The paper credits this result to Zaheer et al. (2017).
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P94
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakenext100.P94
open scoped BigOperators
attribute [local instance] Classical.propDecidable
/-- Theorem 1, source PDF p.4 (proof p.13), restating Zaheer et al. (2017).
The weights describe the linear map before a possibly noninjective xi; n=1 is allowed. -/
theorem first_order_layer (n : ℕ) (hn : 1 ≤ n) (xi : ℝ → ℝ)
(L : Tensor n 1 →ₗ[ℝ] Tensor n 1) :
(L ∈ equivariantLinearMaps (permutationTensorAction (n := n) (k := 1)) permutationTensorAction ↔
∃ w0 w1 : ℝ, ∀ F i, L F ![i] = w0 * F ![i] + w1 * ∑ j, F ![j]) ∧
(L ∈ equivariantLinearMaps (permutationTensorAction (n := n) (k := 1)) permutationTensorAction →
∃ w0 w1 : ℝ, ∀ F i,
pointwise xi (L F) ![i] = xi (w0 * F ![i] + w1 * ∑ j, F ![j])) := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P94
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For every natural number , every function , and every real-linear map on the space of real functions on one-entry tuples from , identify such a function with its coordinates . For a permutation of , define . The theorem asserts both that
and that, if satisfies the equivariance condition on the left, then there exist real numbers such that, for every and ,
Here applying pointwise means applying it separately to each real coordinate. No regularity or linearity is required of , and uniqueness of the weights is not asserted. The case is included.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.