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 , where , from exact gradients of a reverse
Fisher loss for equal-weight Gaussian mixtures with identity covariance.
Their separation lies in ,
where , and their midpoint
has norm at most . The loss
averages the squared
difference between candidate and target scores under the candidate
mixture. The oracle returns at . Constant-step
gradient descent must return two means whose summed squared distances to
the target means, minimized over the two matchings, are at most with probability at
least , where .
Write with its
Euclidean norm and equip with
the product norm
For a candidate pair , define
its mixture density and score by The reverse Fisher loss and the associated
optimization problem are Here is the identity matrix. Both
candidate means are free optimization variables. The algorithm receives
; the
target pair is unknown.
Our assumptions:
Assumption 1 (Target geometry). The target means
satisfy
Queries may be made at any . The oracle returns 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 , which may be random, and
a fixed step size . Each
query is at the current iterate, and the update is After oracle calls, the output
is the last iterate . The initialization
and step size are chosen using the available inputs.
Define the squared matching error by The output must be measurable and satisfy
where is the law of the
algorithm’s randomness.
Proved result
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.