← All setups

Hidden Diagonal Curvature Minimization

Descriptions may be stale. Consult the linked Lean sources.

Hidden Diagonal Curvature Minimization

We consider minimizing a differentiable function f:Rd→R, where d≥1, with a given starting point x0∈Rd. For hidden weights w1,…,wd>0, its first-order remainder lies between μ∥y−x∥w2/2 and ∥y−x∥w2/2, where ∥v∥w2=∑i=1dwivi2 and 0<μ≤1. A global minimizer x⋆ satisfies f(x0)−f(x⋆)≤Δ, with Δ≥0. The oracle returns (f(x),∇f(x)) at x. For ε>0, the goal is f(x¯)−f(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is minx∈Rdf(x). The inner product and gradient are Euclidean. The algorithm receives only d and x0; the weights w1,…,wd, relative curvature parameter μ, initial gap bound Δ, and tolerance ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Diagonal curvature bounds). The function f is differentiable everywhere. For every x,y∈Rd, f(y)≤f(x)+⟨∇f(x),y−x⟩+12∥y−x∥w2,f(y)≥f(x)+⟨∇f(x),y−x⟩+μ2∥y−x∥w2.

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

Queries may be made at any point of Rd, with each call returning the exact function value and Euclidean gradient together. After the allotted oracle calls, the output x¯∈Rd must satisfy f(x¯)−f(x⋆)≤εP-a.s.

Results

On Rd, d≥1, differentiable f satisfies μ2∥y−x∥w2≤f(y)−f(x)−⟨∇f(x),y−x⟩≤12∥y−x∥w2, with hidden wi>0, 0<μ≤1. A minimizer x⋆ exists with f(x0)−f(x⋆)≤Δ, Δ≥0. Exact joint value–gradient calls target f(x^)−f(x⋆)≤ε, ε>0, deterministically. Only d,x0 are public; the setup imposes no algorithm restriction.

Comparison for DiagonalSmoothStronglyConvexBlackBox.
Result Oracle complexity Novelty Limitations
(1) BlackBoxDiagonalAcceleration (Ours) (⋆⋆⋆) (review) O(d+κlog⁡(1+Δκ2/ε)+dκh4)
(2) Multidimensional backtracking, derived bound (Kunstner et al. 2023), Prop. 3.2, Thm. 5.3 O(1+dκℓ+dlog+⁡(L/α0)); twice differentiable; initial set contains an optimal preconditioner. (1): leading accuracy term saves dκ when ℓ≳d/κh4. Needs neither initial set nor twice differentiability. (1): warm-up dκh4 replaces dlog+⁡(L/α0); extra κ2 inside accuracy logarithm.
(3) OSGM-R (Gao et al. 2025), Thm. 6.2 O(1+κL2∥P1−P^∥F2+κℓ) on diagonal candidate matrices; known L,f⋆. (1): leading accuracy term saves κ when ℓ≳dh4/κ; no L,f⋆ knowledge or uncontrolled regret initialization. (1): dimension-dependent warm-up; extra κ2 inside logarithm. Covers diagonal metrics, whereas (3) also permits full matrices.
(4) Centre of gravity, derived bound (Bubeck 2015), Sec. 2.1 O(d+dlog⁡(1+Δκ4/ε)) including secant probes; known μ; exact centroid computation. (1): no μ knowledge. For d=ℓ=κ→∞, total O(κ3/2h4) versus O(κ2); gain requires d≫κ, ℓ≫κh4. (1): worse oracle cost when d≲κ or warm-up dominates.

Abbr: ∥z∥w2=∑iwizi2, κ=1/μ, h=1+log⁡κ, ℓ=1+log+⁡(Δ/ε); log+⁡t=log⁡max{1,t}. L is Euclidean smoothness, α0 the initial search scale, P1 the initial scaling, and P^ the comparator scaling. Secant metric J satisfies J⪯diag(w)⪯J/μ. All costs count joint value–gradient calls. Updates in (1) use no w,μ,Δ,ε,f⋆; its budget depends on them and is not a stopping certificate.

Bubeck, Sébastien. 2015. Convex Optimization: Algorithms and Complexity. https://doi.org/10.48550/arXiv.1405.4980.
Gao, Wenzhi, Ya-Chi Chu, Yinyu Ye, and Madeleine Udell. 2025. Gradient Methods with Online Scaling Part I. Theoretical Foundations. https://doi.org/10.48550/arXiv.2505.23081.
Kunstner, Frederik, Victor S. Portella, Mark Schmidt, and Nick Harvey. 2023. Searching for Optimal Per-Coordinate Step-Sizes with Multidimensional Backtracking. https://doi.org/10.48550/arXiv.2306.02527.

Lean setup