← All setups

Capped Hessian-Similar Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Capped Hessian-Similar Convex Minimization

We minimize f=m−1∑i=1mfi on a finite-dimensional real inner product space E, where m≥1 is an integer. The components fi:E→R are differentiable and convex, f is μ-strongly convex for μ>0, and the centered gradients ∇fi−∇f are jointly δ-Lipschitz in root mean square, with δ≥0. A given x0∈E has objective gap at most Δ≥0 from a minimizer x⋆. Each oracle call returns exact component gradients or proximal points for at most s∈{1,…,m} selected components. For ε>0, the goal is a measurable output x¯∈E with integrable gap and EP[f(x¯)−f(x⋆)]≤ε, where P is the law of the algorithm’s randomness.

The optimization problem is minx∈Ef(x),f(x)=1m∑i=1mfi(x). The norm ∥⋅∥ is induced by the inner product on E, which is also equipped with a measurable structure. The algorithm receives E, m, s, δ, μ, Δ, ε, and x0.

Our assumptions:

Assumption 1 (Component convexity and strong convexity). Each fi is Fréchet differentiable everywhere. For all x,y∈E, t∈[0,1], and i∈{1,…,m}, fi((1−t)x+ty)≤(1−t)fi(x)+tfi(y),f((1−t)x+ty)≤(1−t)f(x)+tf(y)−μ2t(1−t)∥x−y∥2.

Assumption 2 (Mean-square similarity). Define hi(x)=∇fi(x)−∇f(x). For all x,y∈E, 1m∑i=1m∥hi(x)−hi(y)∥2≤δ2∥x−y∥2.

Assumption 3 (Initial objective gap). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,f(x0)−f(x⋆)≤Δ.

Oracle access is organized into capped calls. A call selects a set S⊆{1,…,m} with |S|≤s. For each i∈S, it independently specifies a query point zi∈E and either a gradient request or a proximal request with coefficient ai>0. The corresponding exact reply is, respectively, ∇fi(zi)orproxi,ai(zi), where the proximal map satisfies, for every i, a>0, and z∈E, proxi,a(z)∈argminu∈E{fi(u)+a2∥u−z∥2}. The reply has one entry per component, with zero entries outside S. Gradient and proximal requests may be combined within a single call; the budget counts these capped calls.

After the allotted calls, the output x¯ must be measurable and its objective gap must be integrable under P. The required accuracy is EP[f(x¯)−f(x⋆)]≤ε.

Results

On a finite-dimensional real inner-product space, F=m−1∑ifi has differentiable convex clients and is μ-strongly convex. For gi=∇fi−∇F, assume m−1∑i∥gi(x)−gi(y)∥2≤δ2∥x−y∥2. A minimizer x⋆ exists with F(x0)−F(x⋆)≤Δ. Here 1≤s≤m, δ,Δ≥0, μ,ε>0. Each round contacts at most s clients, returning one gradient or exact proximal point per client. Target: ∫[F(x^(ω))−F(x⋆)]dP(ω)≤ε, with measurable output and integrable gap.

Capped participation under average similarity: CappedHessianSimilarConvex.
Result Oracle complexity Novelty Limitations
(1) CappedHessianSimilarAccelerated (Ours) (⋆⋆⋆) (review) O([1+ms+(1+m3/4s)κ]HQ) deterministic rounds
(2) AccSVRS (Lin et al. 2023), Thm. 3.6 O((m+m3/4κ)Q) expected rounds; κ≥1. (1): m→m/s; κ coefficient gains min(s,m3/4), overcoming H when this factor dominates H. Deterministic budget. (1) requires convex clients and exact proximal steps; (2) permits nonconvex clients and inexact steps. Extra factor H; worse at s=1.
(3) Derived bound: restarted, batched Acc-S-DANE (Jiang et al. 2024), Thm. 6 O(ms(1+κ)Q) deterministic rounds; δ>0. Restart the convex-client bound using D2≤2Δ/μ; 2⌈m/s⌉ rounds per iteration. (1): κ coefficient gains min(m/s,m1/4) for s≤m/2, before H. At s=m3/4,κ=m: O(m1/2log⁡mQ) versus O(m3/4Q). (1) needs exact proximal steps; expected rather than deterministic accuracy. Extra factor H; worse at s=m.
(4) Catalyst VM-SVRS (Wang 2026), Cor. 15; quadratic, individually μ-strongly convex clients O([ms+(ms+m3/4s)κ]ℓ(ℓ+Q)) expected rounds; 0<ε<Δ. (1): nonquadratic convex clients; no Lmax dependence; deterministic budget. On overlap, κ coefficient gains min(m/s,s/m1/4) for m<s<m, peaking at m1/8. (1) guarantees expected accuracy; (4) guarantees accuracy surely.

Abbr: κ=δ/μ, H=1+log⁡(2+m+κ), Q=1+log⁡(2+Δ/ε); ℓ=1+log⁡(mLmax/μ), Lmax=maxi∥∇2fi∥ for quadratics; D=∥x0−x⋆∥. Costs count capped rounds, including full passes and proximal calls; a round uses at most s primitive client calls. P is the algorithm’s randomization law.

Jiang, Xiaowen, Anton Rodomanov, and Sebastian U. Stich. 2024. Stabilized Proximal-Point Methods for Federated Optimization. https://doi.org/10.48550/arXiv.2407.07084.
Lin, Dachao, Yuze Han, Haishan Ye, and Zhihua Zhang. 2023. Stochastic Distributed Optimization Under Average Second-Order Similarity: Algorithms and Analysis. https://doi.org/10.48550/arXiv.2304.07504.
Wang, Rui. 2026. Hessian-Similar Optimization with Capped Participation: Lower Bounds and Virtual Masters. https://doi.org/10.48550/arXiv.2610.33835.

Lean setup