← All setups

Finite-Sum Convex Third-Order Smoothness

Descriptions may be stale. Consult the linked Lean sources.

Finite-Sum Convex Third-Order Smoothness

We consider minimizing f(x)=n−1∑i=1nfi(x) on a finite-dimensional real inner-product space E, where n≥1 is an integer. Each component fi:E→R is convex and three times continuously differentiable, with L-Lipschitz third derivative, where L≥0. A given point x0∈E lies within distance R>0 of a minimizer x⋆; its objective gradient and Hessian have norms bounded by G,H≥0, respectively. A query (i,x) returns (∇fi(x),∇2fi(x)). For ε>0, the goal is a measurable output x¯∈E satisfying P{f(x¯)−f(x⋆)≤ε}≥2/3, where P is the law of the algorithm’s randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. Derivative norms ∥⋅∥op are the induced operator norms: the Hessian acts from E to E, and the third derivative is a trilinear form on E. The algorithm receives E,n,L,R,ε,G,H, and x0.

Our assumptions:

Assumption 1 (Component convexity and regularity). For every i∈{1,…,n}, the function fi belongs to C3(E;R), and for all x,y∈E and t∈[0,1], fi((1−t)x+ty)≤(1−t)fi(x)+tfi(y). Its third derivative satisfies ∥∇3fi(x)−∇3fi(y)∥op≤L∥x−y∥,x,y∈E.

Assumption 2 (Minimizer and initial bounds). The instance specifies a point x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R,∥∇f(x0)∥≤G,∥∇2f(x0)∥op≤H.

The oracle accepts any component index i∈{1,…,n} and any point x∈E, returning the exact component gradient and Hessian together in one call. After the allotted calls, the output x¯ must be measurable with respect to the Borel sets of E and satisfy P{f(x¯)−f(x⋆)≤ε}≥23.

Results

f=n−1∑i=1nfi on a finite-dimensional real inner-product space with its Borel measurable structure; n≥1. Each fi is convex, C3, with L-Lipschitz third derivative. A minimizer x⋆ satisfies ∥x0−x⋆∥≤R, ∥∇f(x0)∥≤G, ∥∇2f(x0)∥≤H; L,G,H≥0, R,ε>0. Exact component queries return (∇fi,∇2fi). Target: Pr{f(x^)−f(x⋆)≤ε}≥2/3.

Finite-sum optimization with Lipschitz third derivatives: FiniteSumThirdSmoothConvex.
Result Oracle complexity Novelty Limitations
(1) HessianOnlyFiniteSumThirdSmooth (Ours) (⋆⋆⋆) (review) O((n+n4/5U1/5)ℓ2) component calls; fixed budget.
(2) Full-mean hyperfast (Kamzolov and Gasnikov 2020), Thm. 2 O(n(1+U1/5)Λℓit) component calls; deterministic accuracy. Λ denotes unspecified logarithmic overhead. (1): Polynomial-factor gain n1/5 for U≥n, U1/5 for 1≤U≤n, modulo logarithms. Scope: G,H needed only at x0, not along iterates. (1) requires convex components; (2) needs only convex mean. Success 2/3 instead of deterministic accuracy; additive nℓ2 cost.
(3) A-TLN (Zhang et al. 2026), Thm. 5.1; overlap: L2-Lipschitz component Hessians O((n+n5/7V2/7)(1+log⁡n)2) expected component calls; almost-sure accuracy. Constant-factor truncation gives the shared target. (1): Smaller polynomial iterative term if n3U7<V10. For L=L2=R=1, ε=n−2, G,H=nO(1): O(n6/5log2⁡n) versus O(n9/7log2⁡n). Scope: includes quartics without globally Lipschitz Hessians. (1) needs C3 and Lipschitz third derivatives, plus G,H; classes incomparable. On overlap, larger polynomial term when n3U7>V10; only 2/3 success.

Abbr: U=LR4/ε, V=L2R3/ε, ℓ=1+log⁡(2+n+GR/ε+HR2/ε+LR4/ε). L2: global component Hessian Lipschitz constant. ℓit=1+log+⁡((Git+Hit)/ε); Git,Hit bound mean gradients and Hessians along the iterates of (2). log+⁡t=max{0,log⁡t}. Λ: logarithmic factors suppressed in (2)’s stated bound. One full-mean call costs n component calls.

Kamzolov, Dmitry, and Alexander Gasnikov. 2020. Near-Optimal Hyperfast Second-Order Method for Convex Optimization and Its Sliding. https://doi.org/10.48550/arXiv.2002.09050.
Zhang, Xinliang, Lesi Chen, Zonghan Li, and Jingzhao Zhang. 2026. Near-Optimal Second-Order Convex Finite-Sum Optimization Under Individual Smoothness. https://doi.org/10.48550/arXiv.2610.42040.

Lean setup