← All setups

Gradient Descent for Gaussian Recovery

Descriptions may be stale. Consult the linked Lean sources.

Gradient Descent for Gaussian Recovery

We study recovery of two unknown means μ0,μ1∈Rd, where d≥1, from exact gradients of a reverse Fisher loss for equal-weight Gaussian mixtures with identity covariance. Their separation lies in [a,1], where a∈[0,1], and their midpoint has norm at most C≥0. The loss Fμ averages the squared difference between candidate and target scores under the candidate mixture. The oracle returns ∇Fμ(θ) at θ∈(Rd)2. Constant-step gradient descent must return two means whose summed squared distances to the target means, minimized over the two matchings, are at most ε∈(0,1] with probability at least 1−δ, where δ∈(0,1].

Write E=Rd with its Euclidean norm and equip E2 with the product norm ∥θ∥2=∥θ0∥2+∥θ1∥2. For a candidate pair θ=(θ0,θ1)∈E2, define its mixture density and score by qθ(x)=12(2π)d/2∑i=01exp(−∥x−θi∥22),wi(θ,x)=exp⁡(−∥x−θi∥2/2)∑j=01exp⁡(−∥x−θj∥2/2),sθ(x)=∇xlog⁡qθ(x)=∑i=01wi(θ,x)θi−x. The reverse Fisher loss and the associated optimization problem are Fμ(θ)=12∑i=01EZ∼N(0,Id)[∥sθ(θi+Z)−sμ(θi+Z)∥2],minθ∈E2Fμ(θ). Here Id is the identity matrix. Both candidate means are free optimization variables. The algorithm receives d,C,a,ε,δ; the target pair μ is unknown.

Our assumptions:

Assumption 1 (Target geometry). The target means satisfy a≤∥μ0−μ1∥≤1,‖μ0+μ12‖≤C.

Queries may be made at any θ∈E2. The oracle returns ∇Fμ(θ) at θ, with the gradient taken in the product Euclidean space.

Our result is algorithm-specific: we analyze constant-step gradient descent. The algorithm chooses an initialization θ0∈E2, which may be random, and a fixed step size γ>0. Each query is at the current iterate, and the update is θk+1=θk−γ∇Fμ(θk). After K∈N0 oracle calls, the output is the last iterate θ¯=θK. The initialization and step size are chosen using the available inputs.

Define the squared matching error by Mμ(θ)=min{∥θ0−μ0∥2+∥θ1−μ1∥2,∥θ0−μ1∥2+∥θ1−μ0∥2}. The output must be measurable and satisfy P(Mμ(θ¯)≤ε)≥1−δ, where P is the law of the algorithm’s randomness.

Results

Teacher and student are equal-weight, two-component Gaussian mixtures in Rd, d≥1, with identity covariances and untied means. The teacher satisfies 0≤s≤Δ≤1 and ∥u¯∥≤B, with B≥0 and ε,δ∈(0,1]. The oracle returns the exact gradient of the population reverse Fisher loss. The setup requires positive constant-step GD returning its current iterate. Target: Pr{minπ∈S2∑i=01∥θiK−μ¯π(i)∥2≤ε}≥1−δ.

Constant-step reverse-Fisher GD for UntiedGaussianReverseFisher.
Result Oracle complexity Novelty Limitations
(1) UntiedReverseFisherGlobalGD (Ours) (⋆⋆) (review)

O(1+logd(1+B)δεmax{s2,ε}).

Step 1/32; start (w,−w), with w a normalized uniform-cube point.

(2) GD (Tyurin 2026), Cor. 2.5; single teacher (Δ=0), n=2 O(ε−1+log1+Bε) for the same initial-radius bound. (1): Scope: extends constant-step GD recovery from Δ=0 to 0<Δ≤1 with unknown centre; no rate improvement at Δ=0. (1): Logarithmically worse accuracy term; mirrored random start and one stopping time, versus arbitrary starts and deterministic accuracy for every k≥K; only two components.
(3) GD (Tyurin 2026), Thm. E.1 (explicit Thm. 3.2), n=m=2

O((1+log⁡R0)2(1+log⁡(d/δ))2ε).

Large-sphere initialization: R0≥C[1+dΔ2/δ +(B+Δ)1+log⁡(1+B+Δ)]; d≥C(1+log⁡(1/δ)), Δ≥C(1+log⁡(R0/ε))(1+log⁡(d/δ)).

Each student reaches squared distance ε from its initially closest teacher, with probability 1−δ.

(1): Scope: covers 0≤Δ≤1, d≥1, a complementary GD regime. Permutation recovery instead of closest-teacher accuracy. Disjoint separation classes: rates not comparable. (1): Only two student and teacher components; no coverage of Δ>1, including the intermediate-separation gap.

Abbr: Δ=∥μ¯0−μ¯1∥; u¯=(μ¯0+μ¯1)/2; s is the supplied separation lower bound; B is the centre bound; S2 is the permutation group; K counts full population-gradient calls. w is the random initial direction; R0 is the sphere radius in (3); C denotes sufficiently large universal constants; n,m count student and teacher components.

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