← All setups

Reverse Fisher Gradient Descent

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

An equal-weight mixture pθ=n−1∑i=1nN(θi,Σ) fits a single teacher q=N(μ¯,Σ) in Rd, with n,d≥1, 0<sminI⪯Σ⪯smaxI and maxi∥θi0−μ¯∥≤R. The oracle returns the exact full gradient of L(θ)=∫∥∇xlog⁡pθ−∇xlog⁡q∥2pθ(x)dx. The setup requires positive-step GD from the supplied initialization and its last iterate; the target is maxi∥θiK−μ¯∥2≤ε, deterministically, for ε>0.

Reverse Fisher GD with general shared covariance: GeneralCovarianceReverseFisher.
Result Oracle complexity Novelty Limitations
(1) GeneralCovarianceReverseFisherGD (Ours) (review) O(1+(1+log⁡n)κ2⋅[log⁡(1+R2/smin)+nmin{n,d}smax/ε])
(2) GD (Tyurin 2026), Thm. 2.1, Cor. 2.5; rescaled to Σ=σ2I O(1+(1+log⁡n)⋅[log⁡(1+nR2/ε)+nmin{n,d}σ2/ε]) (1): Scope extends GD analysis to arbitrary SPD covariance, with κ2 overhead. At Σ=σ2I, matches known rate; improves constants and removes the redundant accuracy logarithm from the initialization term.
(3) Derived bound: collapsed means, conjugate gradients (Hestenes and Stiefel 1952), §3 O(d+1) exact-gradient calls, including initialization; exact recovery. Same problem and oracle, without the GD-family restriction. (1): Analyzes GD from arbitrary supplied means; no established problem-class complexity improvement. (1): Polynomial ε−1 cost versus finite exact recovery. Needs spectral bounds and R for its budget; (3) needs neither, nor ε.

Abbr: n: student components; d: dimension; smin,smax: covariance spectral bounds; κ=smax/smin; R: initial radius; ε: squared-distance tolerance; σ2: isotropic covariance scale; GD: gradient descent; SPD: symmetric positive definite. Costs count full population-gradient calls in exact arithmetic.

Hestenes, Magnus R., and Eduard Stiefel. 1952. “Methods of Conjugate Gradients for Solving Linear Systems.” Journal of Research of the National Bureau of Standards 49 (6): 409–36. https://doi.org/10.6028/jres.049.044.
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