← All setups

Capped Hessian Similar Accelerated — Capped Hessian-Similar Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Capped Hessian-Similar Convex Minimization · Lean proof

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⋆)]≤ε.

Proved result

⌈240⋅(1+ms+(1+m⋅ms)⋅δμ)⋅(1+log⁡(2+m+δμ))⋅(1+log⁡(2+Δε))⌉+

OracleTemplate.Convergence LongTails.Setups.CappedHessianSimilarConvex.spec
  LongTails.Theorems.CappedHessianSimilarAccelerated.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.