acceptodds
Under review as a conference paper at ICLR 2027

Finite-Time Hessian Sketching Below the Effective-Dimension Threshold

26 views

Abstract

Distributed Hessian sketching gives each worker only a small sketched matrix. Averaging the workers' Newton directions reduces random error, but not the bias that all small sketches share. Positive-shift debiasing requires the sketch size to exceed the effective dimension ; we study memory-capped workers with smaller . Below a stricter fold threshold , no stable sketched inverse, with a positive or a negative shift, recovers the mean Newton direction once the gradient has components on two distinct Hessian eigenvalues, and adding workers cannot remove this error. We introduce (FT): each worker runs a negatively shifted gradient flow on its sketched quadratic and stops it at a finite time, which keeps the worker operator positive semidefinite even when the shifted sketched Hessian is indefinite. For proportional Gaussian sketches of a Hessian with a few large eigenvalues over a tail of high effective rank, under weak regularization, let be the ratio of the sketched-tail spread to the smallest large eigenvalue. When the large eigenvalues and the gradient's weights on them stay in fixed proportion, every stable shifted inverse keeps a mean-direction error of at least order , whereas FT with explicit parameters reaches under conditions on the tail spread. Averaging workers of a fixed policy reduces the remaining variance at rate , which gives contraction bounds on quadratics without . Experiments confirm the predicted response matching and worker crossover and show fewer outer iterations on synthetic and real-data problems with small local sketches.

Primary area:
optimization
Keywords:
Hessian sketching, randomized second-order optimization, distributed optimization, early stopping, spectral regularization, effective dimension, random matrix theory, Newton methods

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_ju6xOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper studies distributed Hessian sketching, where each worker uses a small local sketch to approximate a shared Newton direction and the server averages the resulting directions. Below a sketch-size threshold, stable shifted-inverse methods retain a directional bias that cannot be removed by adding workers. The paper instead replacing the local inverse with a negatively shifted gradient flow stopped at finite time. Under specific head–tail spectral and gradient assumptions, it proves an improvement in limiting mean-direction loss from Ω(ζ2)\Omega(\zeta^2) to O(ζ4log⁡2(1/ζ))O(\zeta^4\log^2(1/\zeta)) as ζ→0\zeta \to 0. It also provides finite-worker averaging guarantees. Finally, the paper gives an experimental evaluation that demonstrates the advantage of the proposed algorithms.

Critical strengths
  • The paper identifies a clear limitation of distributed averaging: additional workers reduce variance but cannot remove the systematic bias of small local sketches. The proposed method addresses this limitation without increasing the local sketch size. The main theoretical separation is also interesting.
  • The paper gives a numerical evaluation that supports its theoretical analysis and demonstrates the advantage of the proposed methods.
Critical weaknesses
  • The writing of this paper is not easy to follow, especially in the abstract and introduction. For example, techinical terms such as “fold threshold” and “stable endpoints” are introduced without sufficient explanation. The meaning of the error measure and the regime in which the improved rate is beneficial are also unclear at first reading. I suggest the authors revise these sections to explain the main results and their assumptions more clearly.

  • (Minor) The negative-shifted finite-time filter is adopted from Zhao (2026), so the main novelty lies in its Hessian-sketch analysis and distributed guarantees.

Questions for authors

See the above question.

3 comments
AuthorsOpenReview ↗

Response to Reviewer ju6x

Thank you for the careful reading and for pointing to the terms that need definitions. In the revised PDF (changes highlighted in teal), the introduction now intuitively explains the fold, ζ\zeta, the error measure, the regime the paper studies and the main result, and the abstract defines the fold and ζ\zeta.

Here is a summary of the clarified definitions:

  • Stable endpoint. The standard worker direction inverts the small sketched matrix after adding a shift that keeps it positive definite (stable). FT instead runs gradient flow on the same small problem and stops at a finite time; if run forever, the flow would end at this inverse, hence "endpoint".
  • Fold threshold. The sketch size mm below which no stable endpoint removes the bias, for any shift and worker count (Prop. 3.1). Published corrections require mm above the effective dimension, and a stable negative shift extends this only down to the fold. Below the fold, no stable shifted inverse works; this is the regime existing methods bypass and the one we study.
  • Error measure (Newton-energy ray loss). The fraction of the objective gap remaining after taking the optimal step size along a candidate direction (isolating directional error from scaling): 0 for the Newton direction, 1 for a direction that makes no progress.
  • ζ\zeta (tail-spread-to-head ratio). The ratio of the sketched-tail spread to the smallest large eigenvalue. It measures how well the large eigenvalues stand above the sketched tail (ζ≪1\zeta \ll 1 when the gap is wide).
  • When the improved rate applies (Thm. 3.2). When the gradient has components on two or more distinct large eigenvalues standing well above a high-rank tail, and regularization is weak. Then every stable endpoint keeps an error of at least order ζ2\zeta^2 even with infinitely many workers, while FT with a shift and a stopping time given in closed form has error at most of order ζ4log⁡2(1/ζ)\zeta^4\log^2(1/\zeta). For regularization at most a quarter of its fold value, the stable floor computed exactly is 9.9 to 405 times larger than FT's error over 20 configurations (App. F.3).
  • Gains beyond the head. New Prop. 3.4 (Sec. 3.2): Below the fold, for any gradient on two or more eigenvalues, head or tail, there exists a finite-time pair with a smaller mean-direction loss than every stable endpoint. In an experiment run with zero initial head energy, FT needs 14.8 rounds against 20.1 for the tuned endpoint at q=1024q=1024 (App. H.7).
  • When FT helps. Below the fold, with many workers, when the gradient is spread over eigenvalues that a stable endpoint treats unequally. Above the fold, a stable shift already removes the bias.

W2 (novelty relative to Zhao, 2026). Yes: the worker filter is the one Zhao (2026) introduced for linear regression, and the revised introduction now says so. However, discovering and overcoming the fold barrier in distributed second-order optimization requires fundamentally new analysis. Our problem setting, impossibility barrier, loss geometry, and theoretical guarantees are distinct:

  • Problem. Zhao (2026) studies estimation in single-machine overparameterized linear regression. We study distributed second-order optimization: many workers each sketch the Hessian, and the server averages their Newton directions.
  • Bias and barrier. Here the bias comes from sketching, and more workers cannot remove it. We prove that below the fold no stable sketched inverse recovers the Newton direction, which covers the published positive and negative corrections. The shift that cancels the bias lies past the stability edge, where no stable shifted inverse can operate but a finite-time filter can.
  • Loss. Directions are judged by the scale-invariant Newton-energy ray loss, whereas Zhao (2026) uses prediction risk in linear regression.
  • Rates and workers. FT improves the error from order ζ2\zeta^2 to order ζ4log⁡2(1/ζ)\zeta^4\log^2(1/\zeta) in the sketched spectrum, and the finite-worker bound turns a better mean direction into fewer iterations.
  • Algorithm and evidence. The closed loop selects the shift and stopping time on the workers with a calibrated model, with a guarantee when a reference pair is kept (Prop. C.8). The experiments count outer iterations on synthetic and real problems, and round trips and communication on the synthetic ones.

We would be glad to clarify any remaining questions. Thank you again for your constructive feedback.

Thanks to the authors for the detailed response. I think my previous questions have been addressed, and I have raised my score to 3. One remaining concern, as also acknowledged in the rebuttal to Reviewer Em8f, is the lack of theoretical guarantees when the sketch size mm remains fixed as the dimension grows.

However, I still believe the presentation could be further improved, and I encourage the authors to polish the writing in the next revision.

Thank you for reading our responses, including those to the other reviewers. We are very grateful for your interest in our work, and we promise to polish the writing in the next revision to make the presentation clearer.

Reviewer_Em8fOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies distributed Hessian sketching with small local sketches. Below the effective dimension threshold, stable shifted-inverse methods can suffer from a nonzero mean-direction error that cannot be eliminated by averaging more workers. To address this issue, the authors propose the Finite-Time Hessian Sketching (FT) algorithm, which applies negatively shifted gradient flow with early stopping to improve the approximation of Newton directions. Under specific spectral assumptions, the method achieves a sharper mean-direction error bound than stable shifted inverses, and further establishes finite-worker averaging and convergence guarantees for quadratic objectives.

Critical strengths

This paper provides theoretical guarantees of Hessian sketching below the effective-dimension threshold.

It establishes a nonzero mean-direction error floor for stable shifted-inverse methods and derives an improved error bound for finite-time filtering under specific spectral conditions.

These results provide theoretical support for the proposed method in the small-sketch regime.

Critical weaknesses
  1. The main rate separation in Theorem 3.2 relies on a specific head-tail spectral structure, weak regularization, and gradients supported on a small number of head eigenspaces. The result is established under proportional asymptotics and does not cover fixed sketch sizes as the dimension grows. These conditions limit the scope of the main rate-separation guarantee in general memory-constrained settings.

  2. The experiments mainly report outer iterations, while full parameter tuning may evaluate up to 300 candidates per iteration. Although Appendix E.6 provides per-round communication costs, the main results do not directly compare cumulative communication costs required to reach the target accuracy, making the overall communication efficiency difficult to assess.

Questions for authors
  1. Corollary D.6 establishes a rate separation when the tail Newton-energy fraction is small relative to ζ2\zeta^2, while Appendix H.7 reports improvements with 10%–30% tail energy. To what extent can the theoretical analysis explain FT's advantage when the gradient contains a substantial tail component?

  2. Appendix E.2 shows that each FT iteration involves multiple communication stages. Does FT still require fewer worker-server communication rounds than the tuned stable endpoint to reach the same target accuracy?

4 comments
AuthorsOpenReview ↗

Response to Reviewer Em8f

Thank you for the careful review. Based on your valuable comments, we have developed a new proposition, new experiments and a cumulative-cost table, now in the revised PDF (new text in teal). Here are the detailed responses:

W1 (scope). The separation is strongest under the conditions you list. Without the head–tail structure, new Proposition 3.4 shows that finite time still goes below the stable floor for any gradient on two or more eigenvalues, and the barrier and the finite-worker bound do not use that structure either. Weak regularization (λ<μ0\lambda<\mu_0) is the regime we target: the sketch size is then below the fold—an open regime in the literature, as published positive-shift corrections (Dereziński et al., 2020; Romanov et al., 2025) and a stable negative shift (LeJeune et al., 2024) need larger sketches. In detail (Appendix B.3):

  1. Endpoint barrier (Proposition 3.1): below the fold, any gradient on two or more eigenvalues, in the proportional limit (via the deterministic equivalent of LeJeune et al., 2024); no head–tail structure.
  2. Finite time below the floor (new Proposition 3.4, Section 3.2; Q1 below): any such gradient; mean direction with many workers; no rate.
  3. Rate (Theorem 3.2): needs the head–tail structure and a gradient on the head, as you say.
  4. Finite-worker bound (Theorem 3.3): any dd, mm, qq; non-asymptotic, for a fixed policy.
  5. Evaluated empirically: nonlinear objectives, the size of the gain when the tail carries much of the gradient, and fixed mm as dd grows.

Fixed mm as dd grows. A theorem for fixed mm remains open, as you noted, and we agree it is an important next step. A new sweep (Appendix F.5) keeps m=16m=16 and puts the gradient on the head of the power-law spectra of Appendix H.7 as dd grows from 10310^3 to 10510^5. The mean-direction loss of the best of 131 tested stable shifts stays on the same scale. Theorem 3.2's explicit shift and stopping time, computed from the spectrum without tuning, stays 2.05 to 9.5 times below it, and the best grid pair at least 26 times. For tail exponents 0.75 and 0.9, the explicit pair's gain ratio shows no trend in dd; for exponent 0.6 it drifts from 3.6×3.6\times down to 2.05×2.05\times as ζ\zeta grows from 0.25 to 0.31.

Q1 (substantial tail component). For a tail-energy share such as 10–30%, new Proposition 3.4 shows that some finite-time pair still goes below the endpoint floor. On the tail-only gradients of Appendix H.7, the best pair on an analog of our grid has a mean-direction loss 2.4 to 3.8 times below the floor (Appendix D.10). The proof of Proposition 3.4 (Appendix D.10) uses the submission's Lemma D.3 and Proposition 3.1: near the bottom edge of the sketched spectrum, FT's mean response is that of the boundary endpoint plus a first-order term that acts like an effective regularization below the fold, and the endpoint loss increases strictly with that regularization. Conceptually, a stable endpoint keeps κ\kappa above the fold, so its response (h+λ)/(h+κ)(h+\lambda)/(h+\kappa) rises across the tail and part of the tail error survives every step. FT's response is flatter (it varies 1.4 to 2.5 times across the tail against 4.8 to 6.6; Appendix D.10), so FT's steps remove more of the tail error, which adds up to fewer rounds.

Simulation results:

  • Power-law sweep with zero initial head energy (new; Appendix H.7): FT reached 10−410^{-4} in 14.8 rounds against 20.1 for the tuned endpoint at q=1024q=1024, with fewer rounds in all 12 paired runs; at q=256q=256 the ratio of mean rounds is 1.10.
  • Power-law sweep with 10% or 30% tail energy (in the submission): 1.3 to 1.4 times fewer rounds than the endpoint at q=1024q=1024, for every tail exponent.
  • Fixed-mm sweep with 10% or 30% tail energy (new; Appendix F.5): the best grid pair's mean-direction loss is at least 1.9 times below the endpoint's in all 30 cells.
  • Broad-source control (Appendix H.6; less than 0.21% of the energy above the fold): after 100 rounds at q=1024q=1024 the endpoint's gap is 7.2 to 26.7 times that of FT with quality-aware reuse (3.6 to 22.6 at q=256q=256).

W2/Q2 (cumulative cost and rounds). Yes: to reach the same accuracy, FT needs 3.3 to 4.1 times fewer round trips than the tuned stable endpoint on the sampled models and 1.3 to 1.4 times fewer on the power-law sweep. The same ranges hold for rounds and HVPs (ratios of pooled means; 1.8 to 4.3 per model; 3.5 and 1.4 with full retuning on both sides).

Like Dereziński et al. (2020) and Romanov et al. (2025), the paper counts outer iterations, each of which synchronizes all qq workers; Romanov et al. note that iterations correspond to communication rounds. We agree that cumulative communication totals also belong in the paper (now added to Section 5.2 and Appendix H.8).

The table (Appendix H.8, listed below) gives cumulative costs to relative gap 10−410^{-4} at q=1024q=1024, with every run kept (a miss is charged the round cap). The tuned endpoint, the best of 130 stable shifts, uses the same sketch size, model score and calibration as FT, so it isolates the benefit of finite stopping and is the like-for-like comparison for these costs; with 300 candidates in each family, FT needed fewer rounds in all three ablation cases (Appendix H.9). RZP, the fixed-size rule of Romanov et al. (2025, Algorithm 2) run as published, shows what that rule does at this smaller sketch budget; in these m=16m=16 runs every RZP worker used its fallback shift 5λ/125\lambda/12 (Appendix E.5).

As you note, each submitted round has two communication stages: spectral summaries that set the candidate grid, then the candidate directions. The table counts both for FT and the tuned endpoint, plus one when a quality check triggers a full search; RZP uses one. Bytes are modeled payloads in GiB, with two vectors per candidate and worker.

SettingMethodReachedRoundsRound tripsHVPs (k)CandidatesGiB
SampledFT, retuned18/186.613.11071,9673.88
SampledFT, quality reuse18/186.713.71105251.04
SampledFT without cQc_Q, retuned18/187.314.71202,2004.34
SampledFT, 64-worker selection (new)18/1816.449.22694,9330.653
SampledTuned endpoint, retuned18/1822.945.93762,9835.87
SampledTuned endpoint, reuse18/1827.154.24444070.828
SampledRZP, limited mm15/1843.743.7715440.0853
Power lawFT, retuned24/2413.226.52173,975608
Power lawFT, quality reuse24/2413.627.822362896.9
Power lawFT without cQc_Q, retuned24/2413.627.22234,075623
Power lawFT, 64-worker selection (new)24/2413.640.82234,08942.0
Power lawTuned endpoint, retuned24/2418.336.63002,378364
Power lawTuned endpoint, reuse24/2419.038.131226141.3
Power lawRZP, limited mm0/24100.0100.01,63810015.3

While optimizing this communication, we realized that the first stage is unnecessary: with the grid built in round 1 and kept, FT needs the same rounds in all 42 runs with full retuning and as many or fewer with quality-aware reuse, and each round needs one exchange instead of two, nearly halving FT's round trips (13.1 to 7.56 on the sampled models and 26.5 to 14.25 on the power-law sweep; Appendix E.6).

In bytes the picture is mixed: as implemented, FT's 300-candidate search sends more than the endpoint's on the power-law sweep (608 against 364 GiB) and less on the sampled models (3.88 against 5.87); with reuse it sends more in both. Two changes that we ran cut FT's traffic: quality-aware reuse (608 to 96.9 GiB on the power-law sweep, with 3.7 to 6.3 times fewer candidates and about the same number of rounds) and selecting (α,t)(\alpha,t) on 64 of the 1,024 workers, which adds an exchange per round (42.0 GiB at 13.6 rounds against 13.2, close to the endpoint's 41.3 GiB with reuse at 19.0 rounds; on the sampled models this costs rounds, 16.4 against 6.6).

When FT pays off. Each round costs every worker mm HVPs, and the parameter search adds none. When synchronization, latency or HVPs dominate a round, as with many workers or expensive Hessian–vector products, FT's fewer round trips and HVPs translate directly into time. When bandwidth dominates at large dd, the search payload sets the cost; the two changes above reduce it, and Appendix E.6 gives the crossover condition. We have added this discussion to Section 5.2 and Appendix E.6, and will also highlight it in the Conclusion.

We would be glad to answer further questions. Thank you again for your valuable feedback, which helped us improve the paper.

Thank you for your detailed response. The new theoretical result (Proposition 3.4) partially addresses Weakness 1, and the additional experiments address weakness 2 and both questions. Although the main rate separation still relies on specific assumptions, I will increase my rating from 2 to 3.

Thank you for reading our response and for your helpful comments, which went straight to the key issues and greatly improved the paper.

Reviewer_JurMOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies parallel Hessian sketching under local memory constraints. In the proportional asymptotic regime, the authors show that when the sketch size falls below the fold threshold d2(λ)d_2(\lambda), stable fixed-shift inverses retain a directional bias that worker averaging cannot eliminate, provided the gradient assigns positive Newton-energy weight to at least two distinct eigenvalues. To overcome this limitation, the method uses early-stopped, negatively shifted gradient flow, expanding the attainable mean responses while preserving positive semidefiniteness of the worker operators. Under specified head–tail spectral and source conditions, FT improves the ray loss of the mean direction from the endpoint floor of Ω(ζ2)\Omega(\zeta^2) to O(ζ4log⁡2(1/ζ))O(\zeta^4\log^2(1/\zeta)). The paper also establishes finite-worker guarantees for fixed policies and demonstrates reductions in outer iterations on synthetic and real-data regression problems.

Critical strengths
  1. The paper distinguishes variance, which worker averaging reduces, from bias in the mean response, which averaging leaves unchanged. The fold threshold provides a precise characterization of the limitations of stable shift corrections. Allowing optimal common rescaling also rules out differences attributable solely to step-size selection.

  2. The finite-time filter produces positive-semidefinite worker operators even when the shifted local Hessian is indefinite, allowing shifts unavailable to stable inverses. The analysis of head displacement correction and tail amplification control further explains the improvement in the error order.

Critical weaknesses
  1. Theorem 3.3 and its contraction corollary require the policy to be independent of the current sketches. Algorithm 2 instead constructs its grid from spectral summaries of the current workers and selects parameters using the same worker directions. Quality-aware reuse also includes checks and refreshes driven by the current sketches. Appendix B.2 acknowledges this limitation, but the main text should distinguish more explicitly between guarantees for fixed policies and empirical results for the complete adaptive procedure.

  2. Theorem 3.2 relies on outlying head eigenvalues, a source supported on the head, and additional tail conditions. Its explicit constants are also conservative: for the sources considered in the appendix, the stated bounds typically certify an advantage over endpoints only when ζ\zeta is on the order of 10−310^{-3}. Moreover, the head energy can decrease sharply after the first update, leaving the connection between the single-step separation and subsequent multi-step gains insufficiently explained.

  3. Each FT round includes spectral summaries, candidate broadcasts, and direction aggregation, with additional computation and communication when the search is refreshed. The authors explicitly refrain from claiming serial speedups. Nevertheless, outer iteration counts alone do not establish practical gains in the intended synchronization-dominated setting. Reporting total HVPs, communication volume, and sequential communication stages to reach the same accuracy would clarify the tradeoffs, particularly for parameter reuse.

  4. The current controls usefully separate filtering from outer calibration, but they do not include finite-time filters restricted to nonnegative shifts or to a zero shift. FT and the endpoint baseline also use different numbers of candidates. Restricted comparisons using the existing candidate scores would help establish how much of the improvement comes specifically from negative-shift response correction, beyond finite-time truncation or a larger search budget.

Questions for authors
  1. Can the fact that exact quadratic-model selection performs no worse than a fixed reference candidate be used to establish a guarantee for Algorithm 2? Do the current random grid and exposure screening ensure that such a candidate remains available?

  2. Can the authors report how ζ\zeta, the outlier-condition statistics, and the Newton energy on the head evolve across representative optimization trajectories? What explains the gains after the head energy has substantially decreased?

  3. Using the existing resource logs, can the authors compare full retuning, quality-aware reuse, and the tuned endpoint in terms of total HVPs, candidate evaluations, communication volume, and sequential communication stages required to reach the same accuracy?

  4. Can the authors include finite-time controls restricted to α≥0\alpha\geq0 and to α=0\alpha=0, and assess the sensitivity of the main findings to the number of candidates and grid density?

3 comments
AuthorsOpenReview ↗

Response to Reviewer JurM

Thank you for the careful reading. Based on your valuable comments, we have developed new propositions, new experiments and a cumulative-cost table, now in the revised PDF (new text in teal). Here are the detailed responses:

W1/Q1 (guarantee for the adaptive procedure). Yes for quadratic objectives, by the argument you suggest (new Proposition C.8, summarized in Section 3.3). Fix a reference pair before round kk's sketches are drawn, for example the previous round's pair. If its averaged direction is among the candidates scored by exact calibrated selection, the selected step is never worse than the reference on the same draw, so Theorem 3.3 carries over:

E[Γk+1∣Fk]≤BkΓk,Bk=R∞,k+ωk/q1+ωk/q,\mathbb E[\Gamma_{k+1}\mid\mathcal F_k]\le B_k \Gamma_k,\qquad B_k=\frac{R_{\infty,k}+\omega_k/q}{1+\omega_k/q},

where Γk\Gamma_k is the objective gap, Fk\mathcal F_k is the history, and BkB_k is the reference pair's Theorem 3.3 bound on the current source, with R∞,kR_{\infty,k} its mean-direction loss and ωk\omega_k its relative worker variance. The grid may depend in any way on the current workers, and no factor for the number of candidates appears.

If a screen can remove the reference with conditional probability δk\delta_k, the bound becomes min⁡(1,Bk+δk)\min(1,B_k+\delta_k). In the submitted rule, the exposure screen under quality-aware reuse keeps the stored pair in all but 7 of 103 later rounds on the sampled models and all but 5 of 302 on the power-law sweep (q=1024q=1024; Appendix H.10). Under full retuning, always keeping the previous pair as a candidate gives δk=0\delta_k=0 at the cost of one candidate and no HVPs; a new run with this rule needed the same rounds as the submitted rule in all 42 paired runs (18 on the sampled models, 24 on the power-law sweep; Appendix H.10).

A fixed grid makes this simpler: if the candidate grid is built in round 1 and kept, every grid pair is such a reference from round 2 on, so the step keeps the smallest BkB_k over the grid with no extra candidate. Full retuning on this fixed grid, without the exposure screen, needed the same rounds as the submitted rule in all 42 paired runs (Appendix E.6). Appendix B.3 now separates the proved guarantees (fixed policies and retained references) from the empirical results for the adaptive procedure, and Section 4 notes the retained-reference case.

W2 (assumptions and constants). The separation is strongest under the conditions you list. Without the head–tail structure, new Proposition 3.4 shows that finite time still goes below the stable floor for any gradient on two or more eigenvalues, and the barrier (Proposition 3.1, which rests on the deterministic equivalent of LeJeune et al., 2024) and the finite-worker bound (Theorem 3.3) do not use that structure either; Appendix B.3 lists which result needs which assumption.

We agree that the closed-form constants of Theorem 3.2(iii) are conservative due to non-optimal constants in the proof steps. Numerically, the exact asymptotic limits, which now stand next to the theorem in Section 3.2, separate even at moderate ζ\zeta: the endpoint floor is at least 11 times the loss of Theorem 3.2's explicit pair (shift and stopping time) in all 90 grid cells with ζ≤0.15\zeta\le0.15 and λ≤0.3μ0\lambda\le0.3\mu_0, and 9.9 to 405 times over the 20 configurations with λ≤μ0/4\lambda\le\mu_0/4. In a new sweep with m=16m=16 fixed, dd from 10310^3 to 10510^5 and a source on the head (Appendix F.5), the explicit pair, computed from the spectrum without tuning, has a mean-direction loss 2.05 to 9.5 times below that of the best of 131 tested stable shifts. Q2 below explains the gains after the head energy has decreased.

Q2 (trajectories and later gains). Theorem 3.2 explains the steps in which the error sits on the head. For the later, tail-driven steps, new Proposition 3.4 proves that finite time still beats every stable endpoint in mean direction, and a new run with zero initial head energy measures the size of the gain. On a quadratic, ζ\zeta and the outlier statistic mθm_\theta depend only on HH, mm and λ\lambda, so they stay constant along the trajectory and only the source changes (on the power-law sweep of Appendix H.7, ζ=0.49,0.29,0.15,0.086\zeta=0.49,0.29,0.15,0.086 and the largest mθ=0.60,0.42,0.32,0.29m_\theta=0.60,0.42,0.32,0.29 for tail exponents 0.5 to 0.9).

Sampled models (larger gains: 1.8- to 4.3-fold fewer rounds). The error stays above the fold for several rounds: after round 1, FT leaves 14% to 50% of the remaining Newton energy above the fold, and the tuned endpoint 73% to 93%. On the two sampled models we replayed from the same state and workers, one FT step leaves 3.9 and 4.8 times less of the gap at the start. Theorem 3.2 describes this head-dominated error.

Power-law sweep (smaller gains: 1.3 to 1.4). Example from the runs of Appendix H.7: power-law tail hi=i−0.6h_i=i^{-0.6}, 10% initial tail energy, q=1024q=1024 (head share: median share of the remaining Newton energy on the head). FT reaches 10−410^{-4} in 12 rounds and the endpoint in 17, in every seed.

After round12510
Gap, FT retuned0.110.0580.00792.8e-4
Gap, tuned endpoint (searched each round)0.120.0710.0171.6e-3
Head share, FT2.2%3.5%2.6%2.7%
Head share, endpoint8.8%6.0%6.6%6.6%

Round 1 is nearly a tie: both methods remove a large part of the head error and both leave most of the tail error. The later gains come from tail error:

  • Experiment. In a new run with zero initial head energy (same Hessians and seeds; Appendix H.7), FT reached relative gap 10−410^{-4} in 14.8 rounds against 20.1 for the tuned endpoint at q=1024q=1024, with fewer rounds in all 12 paired runs (the ratio of mean rounds is 1.10 at q=256q=256); from round 2, FT's steps left a median 55% of the tail energy, against 65% for the endpoint.
  • Why a gain without head energy. The loss of a direction measures how unequally it responds across the eigenvalues that carry the gradient. A stable endpoint acts like (H+κI)−1(H+\kappa I)^{-1} with κ\kappa above the fold, so its response (h+λ)/(h+κ)(h+\lambda)/(h+\kappa) rises across the tail. No stable shift can lower κ\kappa further, so part of the tail error survives every step. FT's shift lies past the stability edge, so its filter keeps growing as the eigenvalue decreases and puts more weight on the lower modes; to first order this acts like an effective regularization below the fold and flattens the response. Across the tail it varies 1.4 to 2.5 times, against 4.8 to 6.6 times for the endpoint (8,192 workers; Appendix D.10). FT's steps therefore left a smaller share of the tail energy (the medians 55% against 65% above). The parameter ζ\zeta governs head error; on the tail the gain comes from each step and adds up to fewer rounds.
  • Theory for tail error. New Proposition 3.4 (Section 3.2): for any gradient on two or more eigenvalues, some finite-time pair has a smaller mean-direction loss than every stable endpoint; on the tail-only gradients above, the best pair on an analog of our grid has a mean-direction loss 2.4 to 3.8 times below the floor (Appendix D.10). New Proposition D.7 gives a gain by a fixed factor for sources in a low band of the tail (proofs in Appendix D.10). These results concern the mean direction with many workers; the zero-head run above gives the size of the gain with finitely many workers and the implemented exposure cap of 12.

W4/Q4 (restricted shifts and search budget). The negative shifts carry the gain: at equal search budgets FT keeps its advantage and the restricted families lose it. We ran the controls you suggested on three cases fixed before the runs, with the original seeds and sketches (m=16m=16; q=1024q=1024, or 256 for corn; Appendix H.9): FT restricted to α≥0\alpha\ge0 or α=0\alpha=0 needs more rounds than the endpoint or misses the target even with 300 candidates, signed FT with 81 candidates stays within one round of the full grid, and 300 candidates change the endpoint's rounds by less than one. Entries are mean rounds to 10−410^{-4}; the α≥0\alpha\ge0 arms chose α=0\alpha=0 in all 1,478 of their rounds, so their rows match.

Family (candidates)Two-headNoisy spread-headCorn protein
Signed FT (300, as submitted)3.018.338.3
Signed FT, coarse (81)3.019.339.0
FT with α≥0\alpha\ge0 (125 or 300)7.31 of 3 reach0 of 3 reach
FT with α=0\alpha=0 (25 or 300)7.31 of 3 reach0 of 3 reach
Tuned endpoint (130 / 300 shifts)5.3 / 5.378.7 / 78.393.7 / 93.3

W3/Q3 (total cost to the same accuracy). Yes: to reach the same accuracy, FT needs 3.3 to 4.1 times fewer round trips than the tuned stable endpoint on the sampled models and 1.3 to 1.4 times fewer on the power-law sweep. The same ranges hold for rounds and HVPs (ratios of pooled means; 1.8 to 4.3 per model; 3.5 and 1.4 with full retuning on both sides).

Like Dereziński et al. (2020) and Romanov et al. (2025), the paper counts outer iterations, each of which synchronizes all qq workers; Romanov et al. note that iterations correspond to communication rounds. We agree that cumulative communication totals also belong in the paper (now added to Section 5.2 and Appendix H.8).

The table (Appendix H.8, shown below) gives cumulative costs from the saved logs to relative gap 10−410^{-4} at q=1024q=1024. The tuned endpoint, the best of 130 stable shifts, uses the same sketch size, model score and calibration as FT, so it isolates the benefit of finite stopping and is the like-for-like comparison for these costs; with 300 candidates in each family, FT needed fewer rounds in all three ablation cases (W4/Q4 above). RZP, the fixed-size rule of Romanov et al. (2025, Algorithm 2) run as published, shows what that rule does at this smaller sketch budget; in these m=16m=16 runs every RZP worker used its fallback shift 5λ/125\lambda/12 (Appendix E.5).

As you note, each submitted round has two communication stages: spectral summaries that set the candidate grid, then the candidate directions. The table counts both for FT and the tuned endpoint, plus one when a quality check triggers a full search; RZP uses one. Bytes are modeled payloads in GiB, with two vectors per candidate and worker.

SettingMethodReachedRoundsRound tripsHVPs (k)CandidatesGiB
SampledFT, retuned18/186.613.11071,9673.88
SampledFT, quality reuse18/186.713.71105251.04
SampledFT without cQc_Q, retuned18/187.314.71202,2004.34
SampledFT, 64-worker selection (new)18/1816.449.22694,9330.653
SampledTuned endpoint, retuned18/1822.945.93762,9835.87
SampledTuned endpoint, reuse18/1827.154.24444070.828
SampledRZP, limited mm15/1843.743.7715440.0853
Power lawFT, retuned24/2413.226.52173,975608
Power lawFT, quality reuse24/2413.627.822362896.9
Power lawFT without cQc_Q, retuned24/2413.627.22234,075623
Power lawFT, 64-worker selection (new)24/2413.640.82234,08942.0
Power lawTuned endpoint, retuned24/2418.336.63002,378364
Power lawTuned endpoint, reuse24/2419.038.131226141.3
Power lawRZP, limited mm0/24100.0100.01,63810015.3

While optimizing this communication, we realized that the first stage is unnecessary: with the grid built in round 1 and kept, FT needs the same rounds in all 42 runs with full retuning and as many or fewer with quality-aware reuse, and each round needs one exchange instead of two, nearly halving FT's round trips (13.1 to 7.56 on the sampled models and 26.5 to 14.25 on the power-law sweep; Appendix E.6).

In bytes the picture is mixed: as implemented, FT's 300-candidate search sends more than the endpoint's on the power-law sweep (608 against 364 GiB) and less on the sampled models (3.88 against 5.87); with reuse it sends more in both. Two changes that we ran cut FT's traffic: quality-aware reuse (608 to 96.9 GiB on the power-law sweep, with 3.7 to 6.3 times fewer candidates and about the same number of rounds) and selecting (α,t)(\alpha,t) on 64 of the 1,024 workers, which adds an exchange per round (42.0 GiB at 13.6 rounds against 13.2, close to the endpoint's 41.3 GiB with reuse at 19.0 rounds; on the sampled models this costs rounds, 16.4 against 6.6).

When FT pays off. Each round costs every worker mm HVPs, and the parameter search adds none. When synchronization, latency or HVPs dominate a round, as with many workers or expensive Hessian–vector products, FT's fewer round trips and HVPs translate directly into time. When bandwidth dominates at large dd, the search payload sets the cost; the two changes above reduce it, and Appendix E.6 gives the crossover condition. We have added this discussion to Section 5.2 and Appendix E.6, and will also highlight it in the Conclusion.

We would be glad to answer further questions. Thank you again for your valuable feedback, which helped us improve the paper.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Final summary by the Authors

We thank the reviewers for their careful and constructive reviews. The paper studies distributed Newton methods in which memory limits each worker to a Gaussian Hessian sketch of small size mm. Each worker computes a Newton direction from its sketched Hessian, and the server averages these directions.

All three reviewers recognized the problem the paper aims to address: when mm is below a threshold that we call the fold, more workers reduce variance but cannot remove the bias of stable shifted inverses. Published corrections (Dereziński et al., 2020; Romanov et al., 2025; LeJeune et al., 2024) need mm above the fold, so the regime below the fold is open in the literature. All three also acknowledged the theory, which proves this bias floor and the improved error of finite-time Hessian sketching (FT), proposed in this paper. After the discussion, Reviewer ju6x confirmed that their previous questions have been addressed. Reviewer Em8f found that the new results address their second weakness and both questions, and partially address the first weakness.

The revised PDF (new and rewritten text in teal) addresses the main concerns:

  • Beyond the head–tail structure (JurM, Em8f). The separation is strongest under the conditions of Theorem 3.2. Without that structure, new Proposition 3.4 shows that FT still beats every stable shifted inverse in mean direction for any gradient on two or more eigenvalues, tail included: FT's filter puts more weight on the lower modes and, to first order, acts like an effective regularization below the fold.
  • Cost (JurM, Em8f). To reach the same accuracy, FT needs fewer rounds, round trips and Hessian–vector products (HVPs) than the tuned stable endpoint. In bytes the picture is mixed, so FT pays off when synchronization, latency or HVPs dominate a round (Section 5.2).
  • Adaptive selection (JurM). On quadratic objectives, new Proposition C.8 extends Theorem 3.3's finite-worker guarantee to FT with the shift and stopping time chosen adaptively by the calibrated model score, provided the candidates include a reference pair fixed before the current sketches are drawn.
  • Source of the gain (JurM). Restricted to nonnegative or zero shifts, FT loses its advantage at equal search budgets, so the negative shifts carry the gain.
  • Fixed sketch size (Em8f, ju6x). The main theory is in the proportional asymptotic regime, where dd and mm grow together with d/md/m fixed, so the case of fixed mm and growing dd is a meaningful open question. In a new sweep with mm fixed, FT stays below the best tested stable shift as dd grows (Appendix F.5).
  • Readability (ju6x, Em8f). The abstract and introduction now explain the key terms, and we will polish the writing further in the next revision.

We thank all reviewers again for their effort and helpful suggestions, which greatly helped us improve the paper.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.