← All setups

Untied Reverse Fisher Global GD — Gradient Descent for Gaussian Recovery

Descriptions may be stale. Consult the linked Lean sources.

Gradient Descent for Gaussian Recovery · Lean proof

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.

Proved result

⌈1016max{lower2,accuracy}⋅log⁡(1020⋅dimension⋅(1+centre)failure⋅accuracy)⌉+

OracleTemplate.Convergence LongTails.Setups.UntiedGaussianReverseFisher.spec
  LongTails.Theorems.UntiedReverseFisherGlobalGD.budget

Relevant previous results

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