General Covariance Reverse Fisher GD — Reverse Fisher Gradient Descent
Descriptions may be stale. Consult the linked Lean sources.
Reverse Fisher Gradient Descent · Lean proof
Reverse
Fisher Gradient Descent
We study gradient descent on the reverse Fisher loss between an equally weighted Gaussian
mixture with means in , , and a Gaussian target with mean
. Both share
an unknown covariance
satisfying ,
where .
The loss averages the squared Euclidean difference of their log-density
gradients under the mixture. Each given initial mean lies within distance of . The oracle returns at . For , the final means must
satisfy
for every component and every realization of algorithm randomness.
Write ,
equipped with the product inner product and norm
The model consists of an invertible linear map and the
target mean , with . Define the unnormalized
log densities Their gradients with respect to equal the corresponding log-density
gradients. For , define The optimization problem is The
algorithm receives ,
and ; and are accessible only through the
oracle.
Our assumptions:
Assumption 1 (Covariance bounds). For every ,
Assumption 2 (Initial localization). The given
initial means satisfy
Our formulation is algorithm-specific: we analyze gradient descent
with positive, potentially adaptive step sizes. Queries may be made at
any point of , and denotes the gradient under its
product inner product. Starting from the given , each oracle call and update
have the form The step size is selected from the algorithm’s
current information before receiving and may depend on its randomness. The
expectation defining is part of
the objective; oracle replies are exact gradients of that objective.
After oracle calls, the output
is the last iterate . The required
accuracy is for every realization of the algorithm’s
randomness.
Proved result
OracleTemplate.Convergence LongTails.Setups.GeneralCovarianceReverseFisher.spec
LongTails.Theorems.GeneralCovarianceReverseFisherGD.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.