← 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 possibly nonconvex objective F has an L-Lipschitz gradient and is strongly quasar-convex with parameters 0<μ≤L and 0<γ≤1 relative to a global minimizer x⋆. Component-gradient deviations from ∇F satisfy a mean-square Lipschitz bound with constant δ≥0. A given point x0∈E satisfies F(x0)−F(x⋆)≤Δ, where Δ≥0. At (i,x), the oracle returns ∇fi(x). For ε>0, the goal is an output x¯∈E with integrable objective gap and EP[F(x¯)−F(x⋆)]≤ε, where P is the law of the algorithm’s randomness.

The optimization problem is minx∈EF(x). Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. The algorithm receives E, n, L, μ, γ, δ, Δ, ε, and x0.

Our assumptions:

Assumption 1 (Differentiability and smoothness). Each fi is Fréchet differentiable everywhere on E. The average gradient satisfies ∥∇F(x)−∇F(y)∥≤L∥x−y∥,x,y∈E.

Assumption 2 (Mean-square gradient similarity). Define di(x)=∇fi(x)−∇F(x). For every x,y∈E, 1n∑i=1n∥di(x)−di(y)∥2≤δ2∥x−y∥2.

Assumption 3 (Strong quasar-convexity and initial gap). There exists x⋆∈E such that F(x⋆)≤F(x)for every x∈E,F(x0)−F(x⋆)≤Δ. For this same minimizer and every x∈E, γF(x)+⟨∇F(x),x⋆−x⟩+γμ2∥x⋆−x∥2≤γF(x⋆).

Queries may use any component i∈{1,…,n} and any point x∈E. After the allotted component-gradient calls, the output must have an integrable objective gap and satisfy EP[|F(x¯)−F(x⋆)|]<∞,EP[F(x¯)−F(x⋆)]≤ε.

Results

On a real Hilbert space, F=n−1∑i=1nfi, n≥1, has L-Lipschitz gradient; each fi has a gradient. A global minimizer x⋆ satisfies F(x0)−F(x⋆)≤Δ and F(x⋆)≥F(x)+γ−1⟨∇F(x),x⋆−x⟩+μ2∥x−x⋆∥2. For all x,y, n−1∑i∥[∇fi−∇F](x)−[∇fi−∇F](y)∥2≤δ2∥x−y∥2. Here 0<μ≤L, 0<γ≤1, δ,Δ≥0, and ε>0. The oracle returns exact component gradients; interpolation is not required. Target: ∫[F(X(ω))−F(x⋆)]dP(ω)≤ε, with integrable gap and P the execution law. Our constructions have fixed budgets and expected final-iterate accuracy; the setup imposes no algorithm restriction.

Similar strongly quasar-convex finite sums: ContinuizedSimilarQuasar.
Result Oracle complexity Novelty Limitations
(1) MovementSimilarQuasar (Ours) (⋆⋆⋆) (review) O(n+[n+κγ+(nδ/μ)2/3γ4/3]ℓγ) component gradients.
(2) ContinuizedSimilarQuasar (Ours) (⋆⋆⋆) (review) O([n+κγ+δ2γ3μ2](1+ℓγ)) component gradients.
(3) PAGE (Li et al. 2021), Thm. 5, Cor. 6. Derived bound on Rd via PL constant γ2μ. O(n+[n+nL2+δ2γ2μ]ℓ1) expected component gradients. (1): no worse polynomial dependence; extra accuracy logarithm. For γ=1, n=κ, ε≤Δ: δ=L gives O(κ4/3ℓ1) instead of O(κ3/2ℓ1); δ=0 gives O(κℓ1) for (1), (2). Fixed budgets instead of expected counts. (1), (2) require quasar structure; (3) only PL. Extra log⁡(1/γ). At γ=1, n=κ, δ=L, ε≤Δ, (2) costs O(κ2ℓ1).
(4) Full-batch acceleration (Hinder et al. 2020), Thm. 1; Rd. O(nκγ[1+log⁡(κ/γ)](1+ℓγ)) component values and gradients; deterministic accuracy. (1), (2): gradients only. At δ=0, save a factor ≍min(n,κ/γ)[1+log⁡(κ/γ)] for ε≤Δ. (2) retains this gain if δ2≲γ3μ2(n+κ/γ). (1), (2) give expected accuracy. (1) loses for δ≫nγμ1/4L3/4[1+log⁡(κ/γ)]3/2; (2) can also lose at large δ.
(5) QASVRG (Fu et al. 2023), Cor. 3.6, Option I. Special case: Rd, interpolation, Lmax-smooth components. O([n+min{κmaxγ2,nκmaxγ}⋅[1+log⁡(1/γ)]⋅[1+log⁡(κmax/γ)]](1+ℓγ)) component values and gradients. (1), (2): scope extends to non-interpolating sums; gradients only on the overlap. For (2), a rate gain requires controlling δ2/(γ3μ2) relative to n+min{κmax/γ2,nκmax/γ}. Small similarity is needed for a rate gain. On the overlap, (2) has quadratic κmax dependence at δ=Lmax; (5) has at most linear dependence, apart from logarithms.
(6) AccSVRS (Lin et al. 2023), §3.3, App. E. Special case: Rd, γ=1, strongly convex F, L-smooth f1, μ≤δ≤L. O([n+n3/4(δ/μ+L/δ)
+nκ][1+log⁡nδ+Lμ](1+ℓ1)) expected component gradients, including inner solves.
(1): at δ=μ, n≤κ, ε≤Δ, O(κℓ1) instead of O(n3/4κ[1+log⁡κ]ℓ1). Scope: (1), (2) allow nonconvex F, δ∉[μ,L], and no L-smoothness requirement on f1. (1) has worse polynomial cost at δ=L, κ>n: factor (κ2/n)1/12, excluding logarithms. Similarity dependence is not optimal on this convex overlap.

Abbr: κ=L/μ; κmax=Lmax/μ; Lmax is a common component smoothness bound. ℓa=log⁡(1+Δ/(aε)) for a∈{1,γ}. PL means ∥∇F(x)∥2≥2γ2μ[F(x)−F(x⋆)]. Costs count every component query, including full-gradient refreshes, batches, searches, and inner solves. ≲ suppresses universal constants.

Fu, Qiang, Dongchu Xu, and Ashia Camage Wilson. 2023. “Accelerated Stochastic Optimization Methods Under Quasar-Convexity.” Proceedings of the 40th International Conference on Machine Learning, Proceedings of machine learning research, vol. 202: 10431–60. https://proceedings.mlr.press/v202/fu23e.html.
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.
Li, Zhize, Hongyan Bao, Xiangliang Zhang, and Peter Richtarik. 2021. “PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization.” Proceedings of the 38th International Conference on Machine Learning, Proceedings of machine learning research, vol. 139: 6286–95. https://proceedings.mlr.press/v139/li21a.html.
Lin, Dachao, Yuze Han, Haishan Ye, and Zhihua Zhang. 2023. Stochastic Distributed Optimization Under Average Second-Order Similarity: Algorithms and Analysis. https://arxiv.org/abs/2304.07504v2.

Lean setup