← All setups

Zeroth-Order Matrix-Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Zeroth-Order Matrix-Smooth Convex Minimization

We consider minimizing a twice differentiable convex function f:Rd→R, where d≥1. The function f is matrix (L0,L1)-smooth, with L0>0 and L1≥0, relative to an unknown positive definite matrix H bounded above by the identity and satisfying tr(H)≤r, where r>0. A given point x0 satisfies ∥x0−x⋆∥≤R and f(x0)−f(x⋆)≤Δ for a global minimizer x⋆, with R,Δ>0. The oracle returns the scalar f(x) at x. For ε>0 and δ∈(0,1), the goal is a measurable output x¯ satisfying f(x¯)−f(x⋆)≤ε with probability at least 1−δ over the algorithm’s randomness.

The optimization problem is minx∈Rdf(x). We use the Euclidean inner product ⟨⋅,⋅⟩ and its induced norm ∥⋅∥. The algorithm receives d,L0,L1,r,R,Δ,ε,δ, and x0; the matrix H and the minimizer are not supplied.

Our assumptions:

Assumption 1 (Convexity and differentiability). The function f is differentiable everywhere, its gradient is differentiable everywhere, and f((1−t)x+ty)≤(1−t)f(x)+tf(y),x,y∈Rd,t∈[0,1].

Assumption 2 (Matrix generalized smoothness). There exists a symmetric matrix H∈Rd×d and a constant μ>0 such that μ∥v∥2≤⟨Hv,v⟩≤∥v∥2for every v∈Rd,tr(H)≤r. Write ∥v∥H=⟨Hv,v⟩ and ∥g∥H−1=⟨H−1g,g⟩. The Hessian, viewed as a linear operator on Rd, satisfies ⟨∇2f(x)v,w⟩≤(L0+L1∥∇f(x)∥H−1)∥v∥H∥w∥H,x,v,w∈Rd.

Assumption 3 (Initial distance and objective gap). There exists a global minimizer x⋆∈Rd such that f(x⋆)≤f(x)for every x∈Rd,∥x0−x⋆∥≤R,f(x0)−f(x⋆)≤Δ.

Function-value queries may be made at any point of Rd. After the allotted calls, the output x¯∈Rd must be measurable and satisfy P(f(x¯)−f(x⋆)>ε)≤δ, where P is the law of the algorithm’s randomness.

Results

Convex f:Rd→R has a differentiable gradient and a minimizer x⋆, with ∥x0−x⋆∥≤R and f(x0)−f(x⋆)≤Δ. An unknown symmetric matrix 0≺H⪯I satisfies trH≤r and ∇2f(x)⪯(L0+L1∥∇f(x)∥H−1)H. Here d≥1, L0,r,R,Δ,ε>0, L1≥0, and 0<δ<1. Access is to exact function values; the target is Pr{f(x^)−f(x⋆)>ε}≤δ.

Exact-value optimization under ZerothOrderMatrixGeneralizedSmooth.
Result Oracle complexity Novelty Limitations
(1) ZerothOrderMatrixGeneralizedAccelerated (Ours) (⋆⋆⋆) (review) O(D[d(r+1)L0R2ε
+(r+1+L1Rd(r+1))ℓ]) function values, including independent runs and output selection.
(2) RS-NAG (Omiya et al. 2026), Thm. 3.3, Prop. 5.2. Derived bound: independent runs, best-value selection. O(D[1+d(r+1)L0R2ε]) directional-derivative and selection-value calls. Special case L1=0, d≥2; same probability target. (1): Scope extends to L1>0. Values replace directional derivatives; at L1=0, matches the leading rate. (1): Adds O(D(r+1)ℓ) at L1=0.
(3) AGD (Tyurin 2026), Thm. 4.3; Euclidean reduction. O(1+L0R2ε
+LERlog+⁡min{LE2ΔL0,Δε}
+log+⁡ΔL0R2) exact-gradient calls. Here R=∥x0−x⋆∥, ε<Δ; deterministic accuracy.
(1): Values suffice; no μH−1/2 dependence from LE. No established function-value cost comparison with (3). (1): Probabilistic instead of deterministic accuracy; needs r additionally.
(4) Uniform coordinate acceleration (Lobanov 2026), Thm. 6. O(dR~H0ε+(1+dR~H1)ℓF) partial-derivative, value, and exact segment-solve calls. Expected gap ≤ε; gap local model (Assump. 2), known f⋆,R~<∞, ε≤F0. (1): Values replace derivatives and exact segment solves; R,Δ replace f⋆,R~. Function-value rates are not comparable: segment-solve cost is unbounded here.
(5) Importance-sampled coordinate acceleration (Lobanov 2026), Thm. 8. O(R~∑iH0,iε
+(1+R~∑iH1,i)ℓF) partial-derivative, value, and exact segment-solve calls. Expected gap ≤ε; coordinate local model (Assump. 7), known f⋆,R~<∞, ε≤F0.
(1): No coordinate-curvature inputs; H remains unknown. Values replace derivatives and exact segment solves. Function-value rates are not comparable without segment-solve costs.

Abbr: D=1+log⁡(1/δ); ℓ=log⁡(e+Δ/ε); log+⁡t=max{0,log⁡t}, with log+⁡0=0; μH=λmin(H); LE=L1/μH (or LE=L1 when H=I); ∥g∥H−1=g⊤H−1g; f⋆=f(x⋆); F0=f(x0)−f⋆; ℓF=1+log⁡(F0/ε); R~=supf(x)≤f(x0)∥x−x⋆∥. H0,H1 and H0,i,H1,i are the scalar and coordinate gap-local-model coefficients in (4) and (5); they are not the matrix H.

Lobanov, Aleksandr. 2026. A Few Accelerated Algorithms for Convex Optimization Under (H0,H1)-Smoothness. https://doi.org/10.48550/arXiv.2608.04884.
Omiya, Gaku, Pierre-Louis Poirion, and Akiko Takeda. 2026. Randomized Subspace Nesterov Accelerated Gradient. https://doi.org/10.48550/arXiv.2605.00740.
Tyurin, Alexander. 2026. Near-Optimal Convergence of Accelerated Gradient Methods Under Generalized and (L0,L1)-Smoothness. https://doi.org/10.48550/arXiv.2508.06884.

Lean setup