math.OCOct 2, 2026

Near-Optimal Convex Optimization with Lazy Second-Order Oracles

Authors: Xinliang Zhang, Lesi Chen, Chengchang Liu, Jingzhao Zhang

Organizations: IIIS, Tsinghua University · Department of Artificial Intelligence, Westlake University.

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

This paper studies the complexity of convex optimization using lazy second-order oracles (Doikov, Chayti, and Jaggi, ICML 2023), where an algorithm queries gradients every iteration and Hessians once per mm iterations. Under this setting, we show a lower bound of Ω(m+m1/7ε−2/7)Ω(m+ m^{1/7} ε^{-2/7}) on the number of total iterations to find an εε-solution using a novel block zero-chain construction. Then we propose a novel method that achieves a new upper bound of O~(m+m1/7ε−2/7)\tilde{\mathcal{O}}(m+ m^{1/7} ε^{-2/7}), which significantly improves the prior one (Chen, Liu, Luo, and Zhang, COLT 2026) of O~(m+m13/21ε−2/7)\tilde{\mathcal{O}}(m+ m^{13/21} ε^{-2/7}) and is tight up to logarithmic factors.

Figures & tables

∇2f(x0)\bm{\nabla^{2}f({\bm{x}}_{0})}⟶reuse Hessian\overset{\textbf{reuse Hessian}}{\bm{\longrightarrow}} ⁣∇2f(xm) ⁣\!\bm{\nabla^{2}f({\bm{x}}_{m})}\!
∇f(x0)\bm{\nabla f({\bm{x}}_{0})}∇f(x1)\bm{\nabla f({\bm{x}}_{1})}…\bm{\ldots}∇f(xm−1)\bm{\nabla f({\bm{x}}_{m-1})}∇f(xm)\bm{\nabla f({\bm{x}}_{m})}
Figure 1: mm -lazy second-order algorithms from Doikov et al. [11] : compute a new Hessian once per mm iterations.
More in this topic

Second-Order Optimization

Second-order optimization uses curvature information, such as Hessians or their approximations, to choose efficient steps toward better solutions.

See all 90 papers

Explore similar work

CardsList

  1. Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization

    Jun 3, 2026Dongruo ZhouOptimization Convergence AnalysisNonconvex Optimization

    Department of Computer Science, Indiana University Bloomington, IN 47408, USA

  2. Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory

    Jul 21, 2026Michael Menart, Aleksandar Nikolov, Ohad ShamirQuery ComplexityOracle Complexity

    Department of Computer Science, University of Toronto, Vector Institute · Department of Computer Science, University of Toronto · Weizmann Institute of Science and University of Toronto +1

  3. On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization

    Oct 14, 2026Yuxuan Xia, Xiao-Tong YuanZeroth-Order OptimizationNonconvex Stochastic Optimization