← All setups

Gradient Descent for Reverse Fisher Estimation

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

In Rd, d≥1, let pθ=12N(θ,I)+12N(−θ,I) and Fμ(θ)=∫∥∇log⁡pθ(x)−∇log⁡pμ(x)∥2pθ(dx). Exact population gradients are available; 0≤s≤∥μ∥≤B and ε,δ∈(0,1] are supplied. The setup requires positive-step GD and its current iterate as output, allowing state-dependent steps. The target is P{min(∥θK−μ∥2,∥θK+μ∥2)≤ε}≥1−δ.

Reverse Fisher gradient descent for symmetric Gaussian mixtures: SymmetricGaussianReverseFisher.
Result Oracle complexity Novelty Limitations
(1) SymmetricReverseFisherGlobalGD (Ours) (review) O((1+B)(1+s2)max{s2,ε}[1+log⁡d(1+B)δε]) exact-gradient calls.
(2) Derived bound: adaptive GD O(1) exact-gradient calls (at most two); exact recovery almost surely. Uses exact one-dimensional Gaussian integrals and scalar inversion. (1): No established improvement. (1): Larger budget; needs B,s,ε,δ in addition to d; approximate recovery with failure probability δ instead of almost-sure exact recovery.
(3) GD (Tyurin 2026), Thm. 3.2/E.1; two untied students, teachers ±μ O(LR2H2/ε) full-gradient calls. Independent sphere initialization of radius R0≳max{1,B2d/δ,B1+log+⁡B}; d≳1+log⁡(1/δ) and ∥μ∥≳(LR+log⁡(1/ε))H. (1): Scope of constant-step analysis extends to zero separation. For s>0, logarithmic accuracy dependence once ε≤s2; different student parameterizations prevent a rate comparison. (1): Only tied, antipodal components; one fixed terminal iterate, whereas (3) controls every subsequent iterate and permits general component counts.
(4) GD (Tyurin 2026), Thm. 2.1/Cor. 2.5; special case μ=0, two students O(ε−1+1+log+⁡R02ε) full-gradient calls; arbitrary initialization, deterministic squared-distance accuracy. (1): Scope extends from a single Gaussian teacher to every ∥μ∥≤B in the symmetric model. (1): At μ=0, R0=1, extra factor (1+B)[1+log⁡d(1+B)δε]; probabilistic instead of deterministic guarantee; tied students only.

Abbr: s,B: supplied signal bounds; ε: squared-distance tolerance; δ: failure probability; GD: gradient descent; log+⁡t=max{0,log⁡t} for t>0, with log+⁡0=0; R0: sphere radius in (3), maximum initial distance to the teacher mean in (4); LR=1+log⁡R0 in (3); H=1+log⁡(d/δ); ≳: at least a sufficiently large universal multiple. Full gradients in (3), (4) differentiate all student means; (1), (2) differentiate the tied parameter.

Tyurin, Alexander. 2026. Global Convergence of Gradient Descent for Score Matching in Gaussian Mixtures via Reverse Fisher Divergence. https://doi.org/10.48550/arXiv.2606.19876.

Lean setup