← All setups

Similar Finite-Sum Quasar Minimization

Descriptions may be stale. Consult the linked Lean sources.

Similar Finite-Sum Quasar Minimization

We consider minimizing F(x)=n−1∑i=1nfi(x) on a real Hilbert space E, where n≥1 and the functions fi:E→R are differentiable. The potentially nonconvex objective has a Lipschitz gradient, satisfies a quadratic lower model, and obeys strong quasar-convexity and quadratic growth relative to a global minimizer x⋆. Component-gradient deviations from the mean are Lipschitz with a restricted similarity constant. A given point x0∈E has bounded objective gap. The oracle returns ∇fi(x) at a queried pair (i,x). For ε>0, the goal is an output x¯∈E with F(x¯)−F(x⋆)≤ε almost surely under the algorithm’s randomness.

The optimization problem is minx∈EF(x). The norm ∥⋅∥ is induced by the inner product ⟨⋅,⋅⟩ on E. The parameters satisfy 0<μ≤L,0<γ≤1,δ≥0,384δ2≤γ3μ2,Δ≥0,ε>0. The algorithm receives E, n, L, μ, γ, δ, Δ, ε, and x0.

Our assumptions:

Assumption 1 (Smoothness and component similarity). Each fi is Fréchet differentiable everywhere on E. For every x,y∈E and i∈{1,…,n}, ∥∇F(x)−∇F(y)∥≤L∥x−y∥,∥(∇fi(x)−∇F(x))−(∇fi(y)−∇F(y))∥≤δ∥x−y∥.

Assumption 2 (Quadratic lower model). For every x,y∈E, F(x)+⟨∇F(x),y−x⟩−γμ2μ/L∥y−x∥2≤F(y).

Assumption 3 (Strong quasar-convexity and quadratic growth). There exists a global minimizer x⋆∈E such that F(x0)−F(x⋆)≤Δ, and, for every x∈E, γF(x)+⟨∇F(x),x⋆−x⟩+γμ2∥x−x⋆∥2≤γF(x⋆),γμ2(2−γ)∥x−x⋆∥2≤F(x)−F(x⋆).

Queries may use any component index i∈{1,…,n} and any point x∈E. After the allotted component-gradient calls, the output must satisfy F(x¯)−F(x⋆)≤εP-a.s., where P is the law of the algorithm’s randomness.

Results

On a real Hilbert space, F=n−1∑i=1nfi, n≥1, with differentiable components and exact component-gradient access. The gradient ∇F is L-Lipschitz and each ∇fi−∇F is δ-Lipschitz. Parameters satisfy 0<μ≤L, 0<γ≤1, δ≥0, 384δ2≤γ3μ2, Δ≥0, ε>0. A minimizer x⋆ satisfies F(x0)−F(x⋆)≤Δ and, for every x, F(x⋆)≥F(x)+γ−1⟨∇F(x),x⋆−x⟩+μ2∥x−x⋆∥2 and F(x)−F(x⋆)≥γμ2(2−γ)∥x−x⋆∥2. For every x,y, F(y)≥F(x)+⟨∇F(x),y−x⟩−γμL2∥y−x∥2. Target: F(x^)−F(x⋆)≤ε almost surely; (1) constructs a deterministic output and satisfies this pathwise.

Comparison for SimilarFiniteSumQuasar.
Result Oracle complexity Novelty Limitations
(1) CachedSimilarQuasar (Ours) (⋆⋆) (review) O(n+nℓlog⁡(γ3μ2/δ2)+κγℓ) component gradients
(2) Nesterov acceleration (Hermant et al. 2026, Theorem 2, v3) O(nγ−1κℓ) component gradients; full gradients on Rd (1): replaces multiplicative nγ−1κ by additive costs under 384δ2≤γ3μ2; savings grow with n and γ−1κ. (1) needs finite-sum similarity and knowledge of δ; (2) requires neither.
(3) Derived bound: gradient sliding (Kovalev et al. 2022, Theorem 3) O((n+κ)[1+log⁡(1+κΔ/ε)]) component gradients. Special case: Rd, γ=1, F μ-strongly convex; q=f0, p=F−f0, Lp=μ. (1): on this overlap, divides the nℓ term by log⁡(μ2/δ2), retaining n; removes κ inside the accuracy logarithm. Scope: nonconvex quasar objectives, including γ<1. (1) needs δ≤μ/384 at γ=1; (3) also permits μ≤δ≤L when q is convex. Classes are incomparable.
(4) Quasar acceleration (Hinder et al. 2020, Theorem 1) O(nκγ[1+log⁡(κ/γ)]ℓ) component value/gradient calls, using full evaluations on Rd (1): on the stated curvature/similarity subclass, replaces the multiplicative n cost by additive terms and removes 1+log⁡(κ/γ); needs no function values. (1) needs the lower-curvature bound and similarity; (4) applies without these restrictions.

Abbr: κ=L/μ, ℓ=1+log⁡(1+Δ/(γε)); the fraction with denominator log⁡(γ3μ2/δ2) is interpreted as 0 at δ=0. Each full gradient costs n component-gradient calls; each full value costs n component-value calls. In (3), squared-distance tolerance is 2ε/L.

Hermant, Julien, Jean-François Aujol, Charles Dossal, and Aude Rondepierre. 2026. Study of the Behaviour of Nesterov Accelerated Gradient in a Non Convex Setting: The Strongly Quasar Convex Case. https://doi.org/10.48550/arXiv.2405.19809.
Hinder, Oliver, Aaron Sidford, and Nimit Sohoni. 2020. “Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond.” Proceedings of Thirty Third Conference on Learning Theory, Proceedings of machine learning research, vol. 125: 1894–938. https://proceedings.mlr.press/v125/hinder20a.html.
Kovalev, Dmitry, Aleksandr Beznosikov, Ekaterina Borodich, Alexander Gasnikov, and Gesualdo Scutari. 2022. Optimal Gradient Sliding and Its Application to Distributed Optimization Under Similarity. https://doi.org/10.48550/arXiv.2205.15136.

Lean setup