← All setups

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 F between an equally weighted Gaussian mixture with m≥1 means in Rd, d≥1, and a Gaussian target with mean x⋆∈Rd. Both share an unknown covariance Σ satisfying λ−I⪯Σ⪯λ+I, where 0<λ−≤λ+. The loss averages the squared Euclidean difference of their log-density gradients under the mixture. Each given initial mean θi0 lies within distance R≥0 of x⋆. The oracle returns ∇F(θ) at θ. For ε>0, the final means must satisfy ∥θ¯i−x⋆∥2≤ε for every component and every realization of algorithm randomness.

Write E=(Rd)m, equipped with the product inner product and norm ∥θ∥E2=∑i=1m∥θi∥2. The model consists of an invertible linear map A:Rd→Rd and the target mean x⋆, with Σ=AA⊤. Define the unnormalized log densities hθ(x)=log⁡(∑i=1mexp⁡(−∥A−1(x−θi)∥22)),h⋆(x)=−∥A−1(x−x⋆)∥22. Their gradients with respect to x equal the corresponding log-density gradients. For Z∼N(0,Id), define F(θ)=1m∑ℓ=1mE[‖∇hθ(θℓ+AZ)−∇h⋆(θℓ+AZ)‖2]. The optimization problem is minθ∈EF(θ). The algorithm receives d,m,λ−,λ+,R,ε, and θ0∈E; A and x⋆ are accessible only through the oracle.

Our assumptions:

Assumption 1 (Covariance bounds). For every v∈Rd, λ−∥v∥2≤∥A⊤v∥2≤λ+∥v∥2.

Assumption 2 (Initial localization). The given initial means satisfy ∥θi0−x⋆∥≤R,i=1,…,m.

Our formulation is algorithm-specific: we analyze gradient descent with positive, potentially adaptive step sizes. Queries may be made at any point of E, and ∇F denotes the gradient under its product inner product. Starting from the given θ0, each oracle call and update have the form gt=∇F(θt),θt+1=θt−ηtgt,ηt>0. The step size is selected from the algorithm’s current information before receiving gt and may depend on its randomness. The expectation defining F is part of the objective; oracle replies are exact gradients of that objective.

After K oracle calls, the output is the last iterate θ¯=θK. The required accuracy is ∥θ¯i−x⋆∥2≤ε,i=1,…,m, for every realization of the algorithm’s randomness.

Proved result

⌈(1+8⋅log⁡(components))⋅(upperlower)2⋅(2⋅log⁡(1+radius2lower)+4⋅components⋅min{components,dimension}⋅upperaccuracy)⌉++1

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.