← All setups

Symmetric Reverse Fisher Global GD — Gradient Descent for Reverse Fisher Estimation

Descriptions may be stale. Consult the linked Lean sources.

Gradient Descent for Reverse Fisher Estimation · Lean proof

Gradient Descent for Reverse Fisher Estimation

We consider estimating a hidden vector μ∈Rd, where d≥1, from exact gradients of the reverse Fisher objective Fμ: the mean squared difference between candidate and target mixture scores, averaged under the candidate symmetric Gaussian mixture with identity covariance. The signal satisfies a≤∥μ∥≤b, where 0≤a≤b. The oracle returns ∇Fμ(θ) at θ. We analyze gradient descent with positive steps and algorithm-chosen initialization. For ε,δ∈(0,1], the goal is a measurable output θ¯ satisfying min{∥θ¯−μ∥2,∥θ¯+μ∥2}≤ε with probability at least 1−δ over the algorithm’s randomness.

Equip Rd with its Euclidean inner product and norm. For a candidate parameter θ∈Rd, define the symmetric mixture and its score by qθ=12N(θ,Id)+12N(−θ,Id),sθ(x)=tanh⁡(⟨θ,x⟩)θ−x,x∈Rd, where Id is the identity matrix. The objective is Fμ(θ)=EX∼qθ[∥sθ(X)−sμ(X)∥2]=12EZ∼N(0,Id)[∥sθ(θ+Z)−sμ(θ+Z)∥2]+12EZ∼N(0,Id)[∥sθ(−θ+Z)−sμ(−θ+Z)∥2]. The associated optimization problem is minθ∈RdFμ(θ). The algorithm receives d,a,b,ε,δ; the target μ is hidden.

Our assumptions:

Assumption 1 (Signal bounds). The fixed target belongs to the prescribed Euclidean annulus: a≤∥μ∥≤b.

Our result is algorithm-specific: we analyze gradient descent. The algorithm chooses its initialization θ0∈Rd, possibly at random. At each iteration it queries its current point and updates according to gk=∇Fμ(θk),θk+1=θk−ηkgk,ηk>0. The step ηk may depend on the algorithm’s randomness and information available before the current oracle reply. Queries may be made anywhere in Rd. After K≥0 oracle calls, the output is the current iterate θ¯=θK.

The required accuracy concerns recovery up to sign. The output must be measurable and satisfy P(min{∥θ¯−μ∥2,∥θ¯+μ∥2}≤ε)≥1−δ, where P is the law of the algorithm’s randomness.

Proved result

⌈1000000000000000⋅(1+upper)⋅(1+lower2)max{lower2,accuracy}⋅log⁡(1000000000000000⋅dimension⋅(1+upper)failure⋅accuracy)⌉+

OracleTemplate.Convergence LongTails.Setups.SymmetricGaussianReverseFisher.spec
  LongTails.Theorems.SymmetricReverseFisherGlobalGD.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.