Hessian-Similar Optimization with Capped Participation: Lower Bounds and Virtual Masters

Rui Wang

cs.LGOct 24, 2026

Hessian-Similar Optimization with Capped Participation: Lower Bounds and Virtual Masters

Authors: Rui Wang

Organizations: Microsoft, Vancouver, BC, Canada

Abstract

What is the round complexity of Hessian-similar optimization when each round can contact at most $s$ of $m$ clients? Prior rates permit a free master or full participation and do not characterize strict caps. We count every one-vector query and reply. A hidden-client chain gives a lower bound for zero-respecting local algorithms with adaptive cohorts and random stopping: on strongly convex quadratics, the required rounds are $Ω((m/s)\sqrt{\min\{δ_a,\barδ/\sqrt m\}/μ}\,\log(1/ε))$ for $s\leq(m-2)/2$ in the high-accuracy, high-dissimilarity regime. Here $μ$ is strong convexity, while $δ_a$ and $\barδ$ bound anchor and average Hessian variation. To remove dependence on a poor anchor, virtual-master SVRS uses independent estimator and proximal cohorts and averages the proximal replies. With Catalyst, it reaches relative gap $ε$ in $\tilde O(m/s+(\sqrt{m/s}+m^{3/4}/s)\sqrt{\barδ/μ})$ expected rounds on quadratics with strongly convex clients, independent of $δ_a$ . Combining this method with charged analyses of existing algorithms matches the lower bound's polynomial dependence for $s\leq\sqrt m$ and $s=Ω(m)$ ; the worst gap is $O(m^{1/8})$ . A held-out 12-seed synthetic study finds fewer rounds than tuned SVRP in nine of ten dip-family incomplete-cohort cells, versus two of 30 other cells. The lower bounds concern zero-respecting algorithms and do not cover unrestricted messages.

Figures & tables

Figure 1: One atypical anchor can deviate much more from global curvature than the population-average second-order scale. (a) For eight quadratic clients

f_{i}(x)=\frac{1}{2}x^{\top}A_{i}x

, seven have

A_{i}=\operatorname{diag}(1,4)

, one designated anchor has

A_{a}=\operatorname{diag}(7,1)

, and the mean is

A=\operatorname{diag}(1.75,3.625)

. Thus

\delta_{a}=5.25=\sqrt{7}\,\bar{\delta}

. (b) From

x_{t}=(2,1.2)

, with exact global gradient and

\lambda=6

, the anchor step uses

(A_{a}+\lambda I)^{-1}

, while the size-two virtual-master step averages sampled client inverses. Its expected endpoint lies near the full-curvature reference using

(A+\lambda I)^{-1}

; hollow squares mark the two possible cohort endpoints. This single-step illustration is not a convergence or runtime comparison.

Work	Similarity information	Participation	Relevant accounting distinction
SVRP	Average squared differences	Full refreshes	Refresh cost batched under cap
SVRS/AccSVRS	Average second-order similarity	One client and full refreshes	Master uncharged; lower bound for one sampled client
Gradient sliding	Componentwise similarity	Full	Full exchange exceeds cap
S-DANE/Acc-S-DANE	Subset similarity and gradient variance	Partial or full	Multistage transcript spans rounds
SPAM	Per-client Hessian similarity, gradient variance	Cohorts	Nonconvex stationarity; inexact prox
ASEG	Hessian and gradient similarity	Sampled clients	Neighborhood set by gradient dissimilarity

Table 1: Assumptions and accounting for nearby analyses. This compares hypotheses and accounting units, not theorem rates. “Full” means all clients may join a nominal exchange; under our cap a full pass is batched.

Figure 2: Hidden links force both sequential discovery and client search in the ZR lower bound. (a) In a schematic six-coordinate assignment, each edge

(x_{j}-x_{j+1})^{2}

has one client holder; adjacent edges have different holders. At frontier

V_{3}=\operatorname{span}(e_{1},e_{2},e_{3})

, the holder

h_{3}=D

of the next link remains hidden to the algorithm. (b) With

s=2

, a cohort without

D

cannot reveal

e_{4}

; one containing

D

can advance the frontier by at most one coordinate that round. (c) The optimum has

x_{j}^{\star}=q^{j}

; the illustrative choice

q=0.6

shows its nonzero tail outside

V_{3}

. Theorem 7 randomizes link holders and proves the bound for adaptive cohorts.

Figure 3: Independent cohorts have different jobs in VM-SVRS: one corrects the gradient, and the other averages local proximal points. The schematic quadratic case shows

m=8,s=2

. Four capped snapshot rounds cover all clients. For

t\geq 1

, the estimator

S^{\prime}_{t}=\{2,6\}

supplies Hessian-vector products

h_{i}=A_{i}(x_{t}-w)

, where

A_{i}=\nabla^{2}f_{i}

; the independently drawn master

S_{t}=\{3,6\}

supplies proximal points

u_{i}

, whose mean is

x_{t+1}

. Client 6 appears in both cohorts because independence does not require disjointness. At

t=0

, the estimator row is skipped and

g_{0}=\nabla f(w)

. Each row costs one strict round; filled marks indicate contacts with one vector sent and one received.

$s$	C-Acc	C-SVRS	Src. Acc	Best (rounds)
1	2862	2846	1494	SVRP $\times 2$ (416)
4	496	601	1107	APSVRG $\times\frac{1}{2}$ (130)
16	159	197	1012	APSVRG $\times\frac{1}{2}$ (34)
128	112	130	983	APSVRG $\times\frac{1}{2}$ (27)

Table 3: Median strict rounds to relative gap

10^{-4}

for the cell

m=128,d=256,\delta_{a}=\bar{\delta}=10

; all 16 seeds reach the target in each entry. “Best” is the smallest complete-seed median among non-weighted outputs; APSVRG

\times\frac{1}{2}

is heuristic. C-Acc and C-SVRS are the theorem-parameter cohort arms with

b=s

; Src. Acc is source-parameter AccSVRS.

Appendix figures & tables26 assets

Supplementary material from the paper’s appendix.

Appendix

Method or operation	Strict rounds	Contacts	$d$ -vectors	Local work and condition
Capped full-gradient step	$h$	$m$	$2m$	$m$ local gradients
BAPG, $T$ steps	$T(h+1)$	$T(m+1)$	$2T(m+1)$	$T$ anchor proximal solves
Cached affine, $T\geq 1$	$h+T$	$m+T$	$2(m+T)$	Requires $\delta=0$
One-shot affine	$h+1$	$m+1$	$2(m+1)$	Requires $\delta=0$ , one target-dependent prox
Batched GD, $T$ steps	$Th$	$Tm$	$2Tm$	Certified global smoothness supplied
Strict SAGA initialization	$h$	$m$	$2m$	One gradient per table entry

Appendix

Table 4: End-to-end ledger for completed operations.

h=\lceil m/s\rceil

;

T

counts optimizer updates,

d+1

counts distinct quadratic probe points. Every vector total counts a query and a reply per contact.

Panel of Figure 4 — Figure 4: Fresh-seed 4-seed tuning and 8-seed evaluation split of the VM study. Tuned VM-SVRS uses fewer strict rounds than tuned SVRP in 9 of 10 dip-family settings with incomplete participation and in 2 of 30 other settings. Points are paired geometric-mean ratios on evaluation seeds 4–11; bars are paired bootstrap 95% intervals. Values below one favor VM-SVRS. Full-participation ties are omitted. Multipliers were selected on disjoint tuning seeds from the tested grid.

Family	$s$	Cells	Tuned VM / tuned SVRP	CatVM-thm / CAccSVRS-thm
poor	4	4	1.32 [1.31,1.33]	0.70 [0.65,0.82]
poor	16	4	1.27 [1.23,1.31]	0.40 [0.30,0.54]
poor	64	4	1.11 [1.00,1.25]	0.45 [0.33,0.66]
poor	256	2	1.00 [1.00,1.00]	0.39 [0.37,0.42]
mid	4	4	1.24 [1.12,1.48]	1.73 [1.57,1.95]
mid	16	4	1.25 [1.14,1.34]	1.73 [1.59,1.86]

Appendix

Table 5: Fresh 12-seed VM GPU study at relative gap

10^{-6}

, with four tuning seeds and eight held-out evaluation seeds. Entries are medians across cells of paired geometric-mean round ratios on evaluation seeds 4–11, with 95% two-level bootstrap intervals (2,000 resamples). Multipliers were selected on seeds 0–3. Ratios below one favor VM or CatVM, respectively. For

s\in\{4,16,64\}

each family has four cells; for

s=256

it has two. Intervals describe the selected synthetic grid and are not adjusted for comparisons across cells.

Cohort size	Median ratio	Cohort faster
$s=1$	0.845	4/28
$s=4$	2.818	25/28
$s=16$	6.440	27/28
$s=m$	10.959	28/28

Appendix

Table 6: Cell-level ratio of median first-hit rounds for source-parameter AccSVRS divided by theorem-parameter cohort AccSVRS. The table reports the median of this ratio across 28 feasible cells, and the number of cells in which the cohort arm uses fewer median rounds.

s=m

means

s=32

128

as appropriate. All displayed arms hit in all 16 seeds of every cell.

$m$	$d$	$\delta_{a}$	$\bar{\delta}$	$s=1$	$s=4$	$s=16$	$s=32$	$s=128$	spread
32	64	1	1	307	71	33	36	–	2.46
32	64	1	10	1150	175	44.5	22	–	1.61
32	64	1	100	2759	685	163.5	16	–	1.89
32	64	10	10	1240.5	216	150	122	–	2.22
32	64	10	100	2792.5	685	172.5	76	–	1.14
32	64	100	100	3092	685	398	348	–	1.78

Appendix

Table 7: Median strict rounds to relative gap

10^{-4}

for theorem-parameter cohort AccSVRS over the full feasible grid. “–” denotes a cohort size absent for that

m

; all listed medians use 16 of 16 seeds. The final column is the observed-to-shape spread defined in the text; all entries come from the saved summary.

Method	Quadratic	Logistic
BAPG	36/45	10/15
Batched GD	0/45	15/15
Strict SAGA	0/45	10/15
Quadratic identification	30/45	n/a
S-DANE, exact two-round	15/45	n/a
S-DANE, literal three-round	15/45	5/15

Appendix

Table 8: Last iterates reaching relative error

10^{-4}

within 48 strict rounds (5 seeds; 45 quadratic and 15 logistic cases).

Anchor $\delta$	$M$	$s$	Exact variance	Monte Carlo mean (SE)
0	3	1	6.0000	5.9814 (0.0948)
0	3	11	0.04959	0.04909 (0.00078)
1	3	1	4.6667	4.6468 (0.07365)
1	3	11	0.03857	0.03800 (0.00060)

Appendix

Table 9: Exact and Monte Carlo sampled-difference variance at selected cohort sizes (20,000 draws per estimate).

Figure 5: Finite-population gradient-difference variance at zero anchor dissimilarity. Lines are exact values; points show 20,000-cohort means with unadjusted 1.96-standard-error Monte Carlo intervals. The exact positive-dissimilarity check is reported in the table.

Figure 6: Across 30 paired quadratic seeds at $s=1$ , fraction whose current iterate at each round budget has relative gap at most $10^{-4}$ . The latest saved iterate is carried forward between method steps. Exact quadratic identification solves at round 96; curves do not imply a general-function lower bound.

$M$	$s$	Exact	MC (SE)	$\delta$	$M$	$s$	Exact	MC (SE)
1	1	0.66667	0.66460 (0.0105)	0	3	1	6.00000	5.98140 (0.0948)
1	2	0.30303	0.29950 (0.00324)	0	3	2	2.72727	2.69550 (0.0292)
1	4	0.12121	0.12093 (0.000883)	0	3	4	1.09091	1.08833 (0.00795)
1	8	0.03030	0.03018 (0.000221)	0	3	8	0.27273	0.27160 (0.00199)
1	11	0.00551	0.00545 (0.0000868)	0	3	11	0.04959	0.04909 (0.000781)
9	1	54.00000	53.83260 (0.853)	1	3	1	4.66667	4.64680 (0.0736)

Appendix

Table 11: All saved finite-population cells. The exact column is both formula (8) and enumeration to floating-point precision. MC entries are the 20,000-draw mean with its standard error. The three

\delta=0

scales restart the same seed and therefore share paired cohort draws.

Scenario	$s$	Checkpoints	BAPG gap	GD gap	SAGA gap
Quadratic, scale 0	1	163	$5.53\cdot 10^{-8}$	$2.16\cdot 10^{-6}$	$5.06\cdot 10^{-4}$
Quadratic, scale 0	4	221	0	0	$8.05\cdot 10^{-11}$
Quadratic, scale 0	8	254	0	0	$8.88\cdot 10^{-16}$
Quadratic, scale 0.4	1	92	$4.09\cdot 10^{-10}$	$2.16\cdot 10^{-6}$	$4.99\cdot 10^{-4}$
Quadratic, scale 0.4	4	142	0	0	$9.58\cdot 10^{-11}$
Quadratic, scale 0.4	8	183	0	0	0

Appendix

Table 12: Full-sweep inventory and last saved objective gaps. The 13 scenario counts sum to 1,926 checkpoint rows, including initial rows. The table shows three common methods; the saved JSON also includes quadratic identification, affine controls where

\delta=0

, and the previous BAPG parameter where

0<\delta<\mu

. Values shown as zero were clipped to zero by the diagnostic evaluator at numerical precision.

Family or scale	$s$	BAPG	Batched GD	Strict SAGA	Quadratic identification
Quadratic 0	1	50 / 50	72 / 72	35 / 35	96 / 96
Quadratic 0	4	14 / 50	18 / 72	16 / 64	24 / 96
Quadratic 0	8	8 / 50	9 / 72	14 / 112	12 / 96
Quadratic 0.4	1	50 / 50	72 / 72	74 / 74	96 / 96
Quadratic 0.4	4	14 / 50	18 / 72	16 / 64	24 / 96
Quadratic 0.4	8	8 / 50	9 / 72	20 / 160	12 / 96

Appendix

Table 13: Seed-11 first saved relative-target crossing as strict rounds / contacts. A dash means no saved crossing by the 96-round cap. Later iterates may exceed the target, particularly for SAGA; Table 12 gives final gaps. Identification is class-specific and absent on logistic data.

Figure 7: Seed-11 charged sweep, reproduced from saved checkpoints. The left panel uses strict rounds and the right panel client contacts; both axes are needed because one BAPG update contains a full pass plus an anchor prox. The diagnostic objective evaluator supplies plotted gaps only. These curves are finite-dimensional synthetic comparisons, not a minimax rate plot.

Figure 8: Two independent saved-data checks. Left: the five positive- $\delta$ variance cells compare exact enumeration with the 20,000-draw mean and unadjusted Monte Carlo intervals. Right: for each of 30 paired quadratic seeds, the proved BAPG factor at the public $\mu=0.5$ is connected to the same factor recalculated with that instance’s minimum client eigenvalue. Recalibration changes no iterate. These panels check a finite-population identity and an input sensitivity; neither is an optimization lower bound.

Scale	$s$	BAPG IQR	GD IQR	SAGA IQR
0.4	1	$[1.12\cdot 10^{-10},1.57\cdot 10^{-9}]$	$[5.99\cdot 10^{-9},2.42\cdot 10^{-7}]$	$[1.64\cdot 10^{-3},1.12\cdot 10^{-2}]$
0.4	4	$[0,1.67\cdot 10^{-16}]$	$[0,1.27\cdot 10^{-16}]$	$[4.10\cdot 10^{-12},1.58\cdot 10^{-10}]$
6	1	$[1.99\cdot 10^{-4},1.57\cdot 10^{-3}]$	$[5.99\cdot 10^{-9},2.42\cdot 10^{-7}]$	$[1.55\cdot 10^{-3},8.81\cdot 10^{-3}]$
6	4	$[2.76\cdot 10^{-15},2.94\cdot 10^{-12}]$	$[0,1.67\cdot 10^{-16}]$	$[2.93\cdot 10^{-12},4.84\cdot 10^{-11}]$

Appendix

Table 16: Hazen interquartile ranges of final relative gaps across the 30 paired quadratic seeds. These describe generated instances and the specified round cap, not uncertainty in a minimax law.

Scale	Method	48	72	96
0.4	BAPG	2	30	30
0.4	GD	15	30	30
0.4	SAGA	1	0	1
0.4	Identification	0	0	30
6	BAPG	0	1	5
6	GD	15	30	30

Appendix

Table 17: Successes out of 30 at strict round budgets for

s=1

. The latest available current iterate is used.

Scale	$s$	Comparison	B only	Other only
0.4	1	BAPG vs GD	0	0
0.4	1	BAPG vs SAGA	29	0
6	1	BAPG vs GD	0	25
6	1	BAPG vs SAGA	5	0

Appendix

Table 18: Paired endpoint success discordance at

s=1

across the 30 quadratic seeds. “B only” and “other only” count seeds where one method reaches the

10^{-4}

target and the other does not.

Scale	$s$	Prior global $L$	Active local $L$
0.4	1	1/30	1/30
0.4	4	30/30	30/30
6	1	2/30	0/30
6	4	30/30	30/30

Appendix

Table 20: SAGA success counts before and after correcting the supplied smoothness bound, at the same 30 quadratic seeds and final target. The prior rows are an audit trail, not the active comparator.

Original ingredient	Conditional fact retained	Missing step under the current oracle
Hessian integral and finite-population lemma	Under a bound for every client, centered gradient differences are controlled and $\xi(s)$ is exact.	One-anchor $\delta$ does not control the other clients; Theorem 3 supplies a counterfamily.
Implicit sampled proximal method	Its original nominal-iteration transcript is part of the historical method record.	Charge complete anchor refreshes, the prox reply, and any multi-vector exchange; reprove its rate with matching assumptions.
Catalyst and Chebyshev arguments	Generic acceleration mechanisms can apply to specified inner maps or linear operators.	A valid strict-oracle inner rate and a costed implementable map are not established by the old proof.
Zero-chain lower-bound construction	The original span restriction identifies a limited algorithm class.	Local-prox replies and fixed-dimensional exact identification lie outside the claimed universal inference.
Sampled-anchor variance and floor	The finite-population anchor-gradient variance identity is exact.	A method-specific noise term is not a universal optimization floor over all strict-oracle algorithms.

Appendix

Table 21: Theory transfer audit for the original P11 manuscript and appendix. “Reusable” means the stated conditional mathematical step can be used after its assumptions are restated; it does not validate the original end-to-end rate under the active strict oracle.

Run ( $m,d$ , cap)	Quad. a.	Quad. u.	Floor	Chain	Log. a.	Log. u.
Quick CPU (12,40,300)	0.456	0.970	1.095	0.422	0.377	—
Full CPU (20,60,600)	0.474	0.922	1.007	0.452	0.451	0.829
Large GPU (40,120,1600)	0.459	0.938	1.005	0.451	0.526	0.787

Appendix

Table 22: Saved historical fits across run sizes. “Accel.” and “unaccel.” are fitted exponents in the original nominal iteration metric; “floor” is an empirical fit against

\xi(s)

and “zero-chain” is best-of-named-methods. These values are reported for provenance, not as validation of the active theorem.

Figure family	Saved observation	Strict-oracle disposition
Rounds versus dissimilarity	Large GPU fitted slopes: accelerated 0.459; unaccelerated 0.938.	Each nominal sliding iteration has an exact full gradient and uncharged anchor prox; the dissimilarity assumption is all-client, not anchor-only.
Convergence curves	Named methods have distinct gap-versus-nominal-iteration traces at fixed similarity.	Descriptive trajectories of those implementations; horizontal axis is not charged strict rounds.
Rounds versus participation	Full CPU control-variate count 35.0 and large GPU count 42.36 across $s$ .	Code sets reference $w=y$ , so sampled difference is zero and the estimator is the exact full gradient; this does not test sampled participation.
Sampled floor versus participation	Large GPU fitted exponent 1.005 against $\xi(s)$ for an uncorrected sampled method.	Generator-specific observed floor; it is not a universal strict-oracle floor or a bound from anchor-only $\delta$ .
Quadratic zero-chain	Large GPU best-of-named-methods fitted slope 0.451.	Pointwise minimum over a few named methods on fixed-dimensional quadratics, not a lower bound over arbitrary adaptive algorithms with local-prox replies.
Logistic rounds versus dissimilarity	Large GPU accelerated and unaccelerated fitted slopes 0.526 and 0.787.	Nonlinear historical control, still using exact full gradients and uncharged prox under a different round unit.

Appendix

Table 23: Complete audit of the six historical figure families. Numeric summaries are descriptive values saved in the original JSONs. All are excluded from strict-oracle theorem validation.

$s$	$\xi(s)$	CV nominal	Sampled floor	Direct strict $R$ /step
1	1.00000	42.359	172.836	41
2	0.48718	42.359	82.106	21
4	0.23077	42.359	38.288	11
8	0.10256	42.359	17.248	6
16	0.03846	42.359	6.506	4
24	0.01709	42.359	2.884	3

Appendix

Table 24: Selected large-GPU historical participation cells from the saved original JSON. “CV nominal” is the original control-variate iteration count; the floor is for a different, uncorrected sampled method. The last column charges only the direct full-gradient-plus-prox transcription in the current strict interface and must not be identified with the original x-axis.

Panel of Figure 9 — Figure 9: Historical large-GPU figure families 1 and 2, reproduced read-only. The nominal x-axis charges neither the exact full gradient as $\lceil m/s\rceil$ strict rounds nor the subsequent anchor prox contact. The fitted slopes and gap traces describe that original simulation only; they do not validate the present BAPG bound or a sampled positive- $\delta$ rate.

Panel of Figure 10 — Figure 10: Historical large-GPU figure families 3 and 4. In the control-variate participation simulation, $w=y$ makes the sampled difference identically zero, so its constant count across $s$ comes from an exact full gradient. The uncorrected sampled method’s floor is an observation of that generator; it is not a universal strict-oracle floor theorem.

Figure 11: Historical large-GPU figure family 5. The plotted “lower bound” is the best observed performance among named methods on a finite-dimensional quadratic zero chain. It does not quantify over all strict-oracle algorithms. Proposition 5 supplies a charged exact-identification method for fixed-dimensional quadratics, so the plot cannot certify an accuracy-dependent minimax lower bound here.

Figure 12: Historical large-GPU figure family 6. The logistic fitted slopes are descriptive of the old full-gradient and uncharged-prox iteration convention and are distinct from the current 30-seed charged logistic sensitivity panel. The horizontal quantity must not be read as a strict-round cost under the anchor-only condition.

Federated Learning

Federated learning trains shared models across data holders without requiring them to pool their raw data.

See all 961 papers

Oct 26, 2026

SCAFFOLD under Hessian Similarity: Sharp Convergence Rates

One of the main challenges of federated learning is heterogeneous data split among the clients, leading to biased local updates called client drift. The SCAFFOLD algorithm (Karimireddy et al., 2020) corrects client drift with control variates, but its relation to the similarity of client data is not yet fully understood: the original similarity-based guarantees cover only quadratics with a stronger second-order similarity assumption, and a follow-up weakly convex analysis (Luo et al., 2025) obtains a

\sqrt{Lδ}

dependence for

L

-smooth losses with averaged Hessian similarity

δ

. We analyze SCAFFOLD with minibatch-based control variates and establish linear dependence on Hessian similarity beyond quadratics, for both convex and nonconvex objectives. In particular, for convex objectives with exact gradients,

R

SCAFFOLD rounds with

K

local steps lead to an objective gap of order

(L/K+δ)D_0^2/R

, where

D_0

is the initial distance to a minimizer. When

K=Θ(L/δ)

, it improves the minibatch SGD rate by a factor

Θ(L/δ)

. For nonconvex objectives, we prove an analogous stationarity guarantee under uniform Hessian similarity for a client-selection variant. In both settings, we extend these guarantees to stochastic gradients and prove matching lower bounds for the analyzed methods with constant local stepsizes. We also show that, under partial participation, even identical clients need not obtain the full communication benefit of additional local steps.

Zhirayr Tovmasyan, Slavomír Hanzely, Egor Shulgin +2

King Abdullah University of Science and Technology (KAUST) · CISPA Helmholtz Center for Information Security · Mohamed bin Zayed University of Artificial Intelligence (MBZUAI)

Federated Learning Heterogeneous Federated Learning Federated Learning Aggregation

Ask PDF

Oct 17, 2025

Second-Order Optimization with Asynchronous Curvature

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.

El Mahdi Chayti, Martin Jaggi

Machine Learning and Optimization Laboratory EPFL

Second-Order Optimization Curvature-Aware Optimization Optimization Convergence Analysis

Ask PDF

Oct 2, 2026

Near-Optimal Convex Optimization with Lazy Second-Order Oracles

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.

Xinliang Zhang, Lesi Chen, Chengchang Liu +1

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

Second-Order Optimization

Ask PDF

Abstract

Federated Learning

Explore similar work

SCAFFOLD under Hessian Similarity: Sharp Convergence Rates

Second-Order Optimization with Asynchronous Curvature

Near-Optimal Convex Optimization with Lazy Second-Order Oracles