Near-Optimal Convex Optimization with Lazy Second-Order Oracles

1 Introduction

• The cost model counts gradient queries plus m times the Hessian queries because Hessians are usually more costly and algorithms may mix oracle types.Its cost is #O1(x) + m · #O2(x).Source: §1 · p. 2
• The m-lazy oracle returns Hessian information once every m iterations and gradient information on the other iterations.The prior upper bound had optimal dependence on ϵ, but its optimal dependence on m was unknown.Source: §1 · p. 2
• Ω(m + m^1/7ϵ^-2/7) lower and ˜O(m + m^1/7ϵ^-2/7) upper bounds match up to logarithmic factors.The upper bound improves on Chen et al.'s ˜O(m + m^13/21ϵ^-2/7) bound.Source: §1 · p. 2
• A block zero-chain yields the lower bound by distinguishing gradient from Hessian information, unlike prior standard zero-chains that give only the trivial ϵ-dependence.The authors also report that AI models contributed to developing the lower-bound construction and upper-bound improvements.Source: §1 · p. 2

2 Preliminaries

• The analysis assumes a convex objective with an L-Lipschitz continuous Hessian and at least one minimizer.The Hessian is assumed to exist, and the minimizer is denoted x∗.Source: §2 · pp. 2–3
• An ϵ-solution has objective gap f(ˆx) − f∗ ≤ ϵ, and complexity is the minimum iterations needed to find one.The paper's notation hides logarithmic factors in ˜O and ˜Θ.Source: §2 · pp. 2–3

3 Lower Complexity Bound

• For the lower-bound setup, balancing gradient and Hessian query counts is sufficient because under the cost model, unbalanced counts are dominated by filling in missing queries.The proof first treats lazy algorithms and then extends the bound to general second-order algorithms by simulation.Source: §3 · p. 3

3.1 Lower Bound for Lazy Second-Order Algorithms

• The block zero-chain separates oracle access: each gradient call discovers one coordinate, while each Hessian call can discover all m coordinates in a block.The construction addresses the standard zero-chain's inability to reveal the m-dependence.Source: §3.1 · p. 4
• The construction gives an Ω(m + m^1/7ϵ^-2/7) lower bound for m-lazy second-order algorithms.The theorem's instance has an L-Lipschitz Hessian and a minimizer within distance D of the origin.Source: §3.1 · p. 4
• A quadratic instance supplies a separate Ω(m) lower bound, which combines with the block-chain result to give the final bound.Source: §3.1 · p. 4

3.2 Lower Bound for General Second-Order Algorithms

• A general algorithm using n1 gradients and n2 Hessians can be simulated by an m-lazy algorithm in n1 + mn2 iterations, yielding the same lower bound up to constant factors.The simulation waits for the next Hessian snapshot when a Hessian is needed and discards extra oracle information.Source: §3.2 · p. 5

4 Upper Complexity Bound

• Algorithm 1, an m-lazy second-order method, has complexity that nearly matches the preceding lower bound and, under Assumptions 2.1, 2.2, and 2.3, returns an ϵ-solution.Source: §4 · p. 5

4.1 Reduction to a Cubic Proximal Oracle

• The method reduces convex optimization to finding an approximate stationary point of a cubic proximal function, using the search-free acceleration of Carmon et al. [5] and an efficient oracle.The oracle must satisfy the Monteiro–Svaiter condition; the reduction lemma then guarantees an epsilon solution.Source: §4.1 · pp. 5–6

4.2 Reduction From Making Gradient Small to Reducing the Gap

• Additional cubic regularized Newton steps convert suboptimality-gap reduction into the required gradient condition, with CRN steps in the first and last epochs and O(log kappa) total epochs.The remaining epochs use PAGD-Seg; Algorithm 2 then returns a point satisfying the Monteiro–Svaiter condition.Source: §4.2 · p. 7

4.3 Curvature Control by an Extrapolated Objective

• A novel extrapolated objective stabilizes curvature on the relevant sublevel set, avoiding the potentially unbounded Hessians that can destabilize direct preconditioned AGD on the original proximal function.The extrapolation controls curvature on the visited sublevel set.Source: §4 · p. 5, §4.3 · p. 8

4.4 Preconditioned Accelerated Gradient Descent with Segment Search

• PAGD-Seg combines preconditioned accelerated gradient steps with segment search and, using Algorithm 4, achieves O(κ^(1/3) log^(8/3) κ) gradient evaluations of f_{x,γ} with one Hessian evaluation.The search keeps gradient steps within the sublevel set where Lemma 4.6 applies.Source: §4.4 · pp. 10–11

4.5 Implementing the Segment Search Oracle

• The finite segment-search oracle uses bisection on the nondecreasing directional derivative to find a point satisfying the segment-search condition.It checks the endpoints first, then bisects until the derivative lies between -zeta and 0.Source: §4.5 · p. 12
• Each segment-search call uses O(log κ) gradient evaluations, while Algorithm 3 uses O(κ^(1/3) log^(8/3) κ) gradient evaluations when called.Source: §4.5 · p. 13
• Theorem 4.1 achieves a near-optimal upper bound of Õ(m + m^(1/7) epsilon^(-2/7)) by balancing gradient and Hessian evaluations.Source: §4.5 · p. 13
• With γ = L/m^3 and κ = m^3 + 2, each of S = O(log κ) phases uses one Hessian evaluation and O(κ^(1/3) log^(8/3) κ) gradient evaluations.Source: §4.5 · p. 13
• Each proximal call costs O(m log^(11/3) m) iterations under the fixed snapshot schedule.Source: §4.5 · p. 14

• The lower bound is Ω(m + m^1/7ϵ^-2/7), and the nearly matching upper bound is Õ(m + m^1/7ϵ^-2/7).Source: §5 · p. 14
• Nonconvex optimization, minimax problems, and nonlinear equations remain directions for future research.For nonconvex ϵ-stationarity, the stated upper and lower bounds are O(m + m^1/3ϵ^-3/2) and Ω(ϵ^-3/2), respectively.Source: §5 · p. 14
• The authors hope the work can serve as a principled starting point for efficient inexact second-order optimizers, given lazy-Hessian techniques in modern deep-learning optimizers.Examples named include KFAC, Sophia, Shampoo, SOAP, ASGO, and Newton-Muon.Source: §5 · p. 14

• The adversary simulates each algorithm query using a truncated function that depends only on the directions revealed so far.The truncated function is independent of the later coordinates.Source: §A.1 · p. 16
• At each iteration, the adversary chooses a new unit direction orthogonal to previous directions and queries, subject to the dimension condition.The construction also completes the basis after the algorithm's output when d ≥ 3T.Source: §A.1 · p. 16
• The truncated and full functions give consistent gradient responses at the algorithm's query points.The proof uses zero coordinates beyond the revealed chain and preservation of derivatives in the revealed coordinates.Source: §A.1 · p. 16
• At periodic Hessian queries, the displayed blocks match the full function, while remaining blocks contribute zero gradients and Hessians.The proof concludes that full Hessian responses are consistent at every Hessian query point.Source: §A.1 · p. 17

• The proof first reduces evaluation of the full function at the algorithm output to the truncated function f_T.It then begins a lower bound for f_T over all y in R^2T.Source: §A.2 · p. 17
• Jensen's inequality is applied to a sum with n = ⌊T/m⌋ + 1 terms.Source: §A.2 · p. 17
• The proof next invokes the triangle inequality on the resulting expression.Source: §A.2 · p. 17

A.3 Proof of Theorem 3.1

• The function is a sum of blocks, and each coordinate appears in at most two adjacent blocks, so the proof bounds each block's Hessian Lipschitz constant.Source: §A.3 · p. 17
• Using the 6-Lipschitz Hessian constant of ∥·∥^3 and ∥A∥ ≤ 2, the proof bounds each block's Hessian Lipschitz constant by 48λ and the full function's by 96λ.It sets λ = L/96 to ensure the full function's Hessian Lipschitz constant is at most L.Source: §A.3 · p. 18
• T = Ω(m^1/7(LD^3/ϵ)^2/7) iterations are required to find an ϵ-solution.Source: §A.3 · p. 18

B.1 Proof of Lemma 4.4

• The proof invokes Lemma 4.2(2) as part of its argument.Source: §B.1 · p. 18
• The proof sets z0 = CH(x) and y0 = CH(z0), then applies Lemma 4.3 to the first two steps.It uses Lemma 4.3(2) for the first step and Lemma 4.3(1) for the second.Source: §B.1 · p. 18
• The output ˆy is at least 3r*/4 from x, so it satisfies Condition 4.1.The proof derives this separation from ∥ˆy − x∥ ≤ r*/4.Source: §B.1 · p. 18

B.2 Proof of Lemma 4.9

• With R = (6∆/γ)^1/3, the proof bounds ∇²f_x,γ(y) and Hρ∥v_k − x_k∥² by O(κ∆).It also bounds ∥v_k − x_k∥ by O(R).Source: §B.2 · pp. 18–19
• The proof bounds A_k by k² and hence by N² = O(Ξ).Source: §B.2 · p. 18
• The proof bounds ∥v_k − y*_x,γ∥ by O(R) and uses Hessian Lipschitzness for points on [y*_x,γ, x_k].The stated distances place those points within 3R of y.Source: §B.2 · p. 19
• The definition of B gives B ⪰ 2(J + 1)∇²f_x,γ(y), which is used with the potential bound to control the Hessian term.The resulting bound is O((J + 1)^1/3κ^2/3∆).Source: §B.2 · p. 19
• M = O(κ∆) and ζ = ∆/100 give at most O(log κ) gradients of g per binary search.Each gradient of g costs J + 1 gradients of f_x,γ.Source: §B.2 · p. 19
• O(κ^1/3 log^8/3 κ) gradient evaluations of f_x,γ suffice for the N descent-gradient queries and searches.Each binary search uses O(log κ) gradients of g, each costing J + 1 gradients of f_x,γ; N = O((J + 1)^2/3κ^1/3) and J + 1 = O(log κ).Source: §B.2 · p. 19