Second-Order Optimization with Asynchronous Curvature

El Mahdi Chayti; Martin Jaggi

math.OCOct 17, 2025

Second-Order Optimization with Asynchronous Curvature

Authors: El Mahdi Chayti, Martin Jaggi

Organizations: Machine Learning and Optimization Laboratory EPFL

Abstract

Second-order methods make fast progress per iteration, but forming and factorizing the Hessian often dominates their wall-clock time. We study Split-Client, a task-parallel design in which a curvature client factorizes Hessians in the background while a gradient client takes cubic-regularized steps with the most recently published matrix, so that curvature cost appears as a delay rather than as blocking time. For delayed exact Hessians, we prove a first-order stationarity bound that depends on the average age of the curvature rather than its maximum, using an overlap count and a weighted Hardy inequality that allows any bounded-error initial matrix; the analysis extends to subsampled and uniformly inexact curvature. Under a fixed-cost model, the resulting wall-clock bound matches the scaling of optimally tuned Lazy Hessian without choosing a reuse period. In experiments on two LIBSVM datasets, an implementation decreases the objective earlier in wall-clock time than Lazy and Vanilla cubic Newton, with the largest gains at intermediate accuracy.

Figures & tables

Panel of Figure 1 — Figure 1: Wall-clock comparison of cubic regularization strategies. (A) Vanilla: The gradient worker waits for Hessian computation and factorization at every step. (B) Lazy: Reuses each factorization for $m$ steps, amortizing its cost, but still blocks at every refresh. (C) Split-Client (Ours): Runs curvature in a background process. The gradient worker starts immediately with a cheap initial matrix $H_{0}$ and proceeds continuously using the latest published $\widetilde{H}$ , so the curvature cost (Hessian and factorization) appears as a delay rather than as blocking time.

Method	Non-block.	Delay model	Avg-delay	No reuse period
Vanilla CR ( Nesterov and Polyak, 2006 )	–	–	n/a	$\checkmark$
Inexact CR ( Chayti et al., 2024 )	–	–	n/a	$\checkmark$
Lazy Hessian ( Doikov et al., 2023 )	–	–	n/a	–
QN-CR ( Kamzolov et al., 2026 )	–	–	n/a	$\checkmark$
Split-Client (ours)	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$

Table 1: Positioning relative to related cubic-regularized methods. Delay model : curvature latency is modeled as an asynchronous delay. Avg-delay : the bound depends on the average age

\bar{\tau}

rather than

\tau_{\max}

. No reuse period : none must be chosen in advance.

Panel of Figure 2 — Figure 2: The two-timeline model. Curvature jobs (blue blocks) run in serial on the wall-clock axis; gradient iterations are integer ticks above. At iteration $k$ inside job $i=2$ , the in-use curvature is from job $i-1=1$ (started at $a_{1}$ ), giving delay $\tau_{k}=k-a_{1}$ . The Overlap Lemma ( Lemma 4 ) bounds the count of future iterations $k^{\prime}>k$ that still include $k$ in their delay window: such $k^{\prime}$ must lie in jobs $\leq i+1=3$ , so $O_{k}\leq\Delta_{i}+\Delta_{i+1}-1$ .

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 11: Cost profiling: per-call time in seconds of each component versus

d

(mean

\pm

std over seeds), with the Hessian assembled in full at every call. Assembly and factorization dominate the gradient and the cubic solve.

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

Near-Optimal Convex Optimization with Lazy Second-Order Oracles
Oct 2, 2026Xinliang Zhang, Lesi Chen, Chengchang Liu +1Second-Order Optimization
IIIS, Tsinghua University · Department of Artificial Intelligence, Westlake University.
Second-Order, First-Class: A Composable Stack for Curvature-Aware Training
Mar 26, 2026Mikalai Korbit, Mario ZanonCurvature-Aware Optimization Deep Learning Optimization
IMT School for Advanced Studies Lucca Lucca, Italy
Efficient Bilevel Optimization with KFAC-Based Hypergradients
Mar 31, 2026Disen Liao, Felix Dangel, Yaoliang YuKronecker-Factored Approximation Bilevel Optimization
University of Waterloo · Vector Institute

Oct 2, 2026J/K move · Enter open · S save

Near-Optimal Convex Optimization with Lazy Second-Order Oracles

Xinliang Zhang, Lesi Chen, Chengchang Liu, Jingzhao Zhang

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

Second-Order Optimization

Open paper AskPDF arXiv

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

m

iterations. Under this setting, we show a lower bound of

Ω(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

\tilde{\mathcal{O}}(m+ m^{1/7} ε^{-2/7})

, which significantly improves the prior one (Chen, Liu, Luo, and Zhang, COLT 2026) of

\tilde{\mathcal{O}}(m+ m^{13/21} ε^{-2/7})

and is tight up to logarithmic factors.

Abstract

Second-Order Optimization

Explore similar work

Near-Optimal Convex Optimization with Lazy Second-Order Oracles

Second-Order, First-Class: A Composable Stack for Curvature-Aware Training

Efficient Bilevel Optimization with KFAC-Based Hypergradients