acceptodds
Under review as a conference paper at ICLR 2027

Optimal Parameter-Free Second-order Acceleration with Inexact Hessians under Generalized Smoothness

Abstract

We study second-order convex optimization under generalized Hessian smoothness, where the local Hessian Lipschitz constant may grow linearly with the gradient norm. For inexact Hessians, we develop adaptive algorithms, including an accelerated Monteiro-Svaiter-type method whose complexity matches the lower bound for second-order methods with -inexact Hessians in the classical Lipschitz-Hessian setting. Our methods are parameter-free in the sense that they require no problem-specific parameters as input, including the Hessian inexactness level and smoothness constants. Instead, their backtracking adapts a single regularization parameter that jointly captures Hessian inexactness and local Hessian smoothness. The resulting rates split into two regimes. Far from the solution, the gradient-dependent smoothness term yields geometric convergence. Near the solution, the rate is governed by the ordinary Hessian smoothness and the inexactness level , recovering the classical Lipschitz-Hessian guarantees.

Primary area:
optimization
Keywords:
second-order optimization, generalized smoothness, Hessian approximation, optimal 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_UadJOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies parameter-free second-order methods for convex optimization under generalized smoothness and inexact Hessians. It proposes three new algorithms that search for regularized Newton steps satisfying the Monteiro-Svaiter condition. The paper analyzes an adaptive regularized Newton method along with the two accelerated variants.

Critical strengths

The paper provides rigorous convergence bounds on adaptive second-order algorithms with inexact Hessians. Algorithm 3 is parameter-free and achieves the optimal convergence rate for convex second-order optimization with inexact Hessians under classical Lipschitz-Hessian smoothness. The authors develop a new convergence analysis that extends prior results to inexact Hessians and generalized Hessian smoothness.

The paper has an in-depth comparison of their proof techniques against similar work of Carmen et al. (2022) and Chen et al. (2026).

Critical weaknesses

The proposed accelerated parameter-free method is outperformed by the simpler non-accelerated method in the experiments. This raises questions about the practical benefits of the accelerated method, especially given its additional complexity. A comparison in terms of wall-clock time would also be useful to better understand the benefits of the proposed methods. More broadly, while achieving an optimal parameter-free convergence rate is theoretically meaningful, its practical significance is less convincing when the accelerated method does not outperform the simpler baseline.

A minor point: the algorithms still require an initial regularization parameter η0>0\eta_0>0. Moreover, the experiments initialize this parameter using the local Hessian smoothness constant L(x0)L(x_0). While Appendix G.2 studies sensitivity to initialization for Algorithm 2, analogous experiments are missing for the main accelerated method (Algorithm 3).

Questions for authors

Can the authors provide any intuition on why the accelerated method is outperformed by the non-accelerated method in the logistic regression experiments?

Most practical ML algorithms use stochastic gradient information. Can the authors comment on whether the algorithms and analysis can be adapted to the stochastic setting?

4 comments

Dear Reviewer,

We thank you for your time and effort in reviewing our paper. We address your comments below.

Weakness Wall-Clock

A comparison in terms of wall-clock time would also be useful to better understand the benefits of the proposed methods.

Answer:

For the experiments with exact Hessians, we added wall-clock time and oracle calls to Figure 1.

For inexact Hessians, our setup is motivated by distributed optimization, with the server’s local Hessian serving as an approximation. Each full gradient requires one communication round (workers compute local gradients in parallel and send them to the server), and the Hessian is computed by the server once per outer iteration of the method. Wall-clock time of a single-machine simulation would not reflect the cost of this setting. Thus, in Figure 1 we report communication rounds, as communication is typically the main bottleneck in this setting.

Note that the two axes in Figure 1 also measure the two kinds of computation: the number of outer iterations is the number of Hessian computations on the server, and the number of communication rounds is the number of local gradient computations on each worker.

Across all measures – iterations, oracle calls, wall-clock time, and communication rounds – the performance of our methods remains consistent, with the basic non-accelerated method performing best. Their wall-clock efficiency comes from solving only quadratic subproblems.

Weakness and Question 1 about Slow Optimal Acceleration

The proposed accelerated parameter-free method is outperformed by the simpler non-accelerated method in the experiments. This raises questions about the practical benefits of the accelerated method, especially given its additional complexity.

More broadly, while achieving an optimal parameter-free convergence rate is theoretically meaningful, its practical significance is less convincing when the accelerated method does not outperform the simpler baseline.

Can the authors provide any intuition on why the accelerated method is outperformed by the non-accelerated method in the logistic regression experiments?

Answer:

First, we would like to emphasize that the non-accelerated method (Algorithm 2) is also a contribution of this paper, not an existing baseline. While simpler than the accelerated method, it is based on several nontrivial ideas, which we explain in the new Appendix I.

The phenomenon of non-accelerated methods outperforming accelerated ones was also observed by Carmon et al. (2022), as discussed in Section 4 and the Limitations section of their paper. Moreover, our original submission already included experiments where acceleration outperforms non-accelerated methods (Appendix G.2 in original submission, in revised version its the first three columns in Figure 3 Appendix H.2).

We see two main reasons why the non-accelerated method is faster in Figure 1.

  1. Local strong convexity. Logistic regression with a full-column-rank data matrix is strongly convex near the solution. It is well known, for both first- and second-order methods, that non-accelerated methods adapt to strong convexity automatically and switch to fast local convergence. For example, gradient descent with step size 1/L1/L adapts to strong convexity automatically. Without any knowledge of μ\mu, it converges linearly with iteration complexity O(L/μlog⁡(1/ε))O(L/\mu \log(1/\varepsilon)). Accelerated methods do not have this property. If their parameters are chosen for the merely convex case, they guarantee only the sublinear rate (for Accelerated Gradient Method: O(1/k2)O(1/k^2)), so for small target accuracy they become slower than plain gradient descent. To reach the accelerated complexity O(L/μlog⁡(1/ε))O(\sqrt{L/\mu} \log(1/\varepsilon)), an accelerated method needs either an estimate of μ\mu [1] or a restart strategy [2, 3, 4]. Adaptive restart schemes reset the momentum based on observed progress [2, 3]. The same idea is valid for second-order accelerations. This agrees with our theoretical results in Section 3.2.

  2. Worst-case safeguards and memory. Accelerated methods are designed for the worst case. Their parameters, safeguards and accumulated memory (momentum) are chosen so that the convergence guarantee holds for every function in the class. When the function has a better structure than assumed, these safeguards can slow the method down in practice. Section 3 of [5] shows that this happens even for classical acceleration. Adaptive non-accelerated methods have no memory: each step depends only on local information at the current point, so they can immediately use a better local structure.

When acceleration helps. For convex functions without local strong convexity or other favorable structure, the accelerated methods can be faster than the non-accelerated ones. This can be seen in Figure 2c for the norm function and in Appendix H.2 for x4x^4, x6x^6, and cosh⁡x−1−x2/2\cosh x -1 - x^2/2. We have also added experiments on Nesterov’s second-order lower-bound function (Appendix H.3, Figures 4,5). There, the accelerated methods are faster for k<dk<d, which is the sublinear regime of the lower bound.

Practical significance. In practice one usually does not know in advance whether the problem has a favorable local structure. The accelerated method guarantees the optimal rate on hard instances without any parameter tuning, while the non-accelerated method is preferable when local strong convexity is expected.

We therefore see the two methods as complementary.

In summary:

  • Adaptive accelerated methods are faster on the classes of functions for which the theory predicts acceleration.
  • Adaptive non-accelerated methods can be faster when the function has a better local structure than assumed, for example local strong convexity.

Minor point

A minor point: the algorithms still require an initial regularization parameter . Moreover, the experiments initialize this parameter using the local Hessian smoothness constant . While Appendix G.2 studies sensitivity to initialization for Algorithm 2, analogous experiments are missing for the main accelerated method (Algorithm 3).

Answer:

Indeed, our methods require an initial regularization parameter η0>0\eta_0 > 0 but it can be chosen arbitrarily. Our theoretical convergence guarantees hold for any η0>0\eta_0 > 0, without requiring knowledge of the smoothness constants or Hessian inexactness level.

In the experiments, we initialize η0>0\eta_0 > 0 using the local smoothness constant only to ensure a fair comparison, so that the methods start with comparable initial trial steps. This information is not required by our algorithms.

We have also extended the sensitivity experiments to accelerated methods in Appendix H.4 (Figures 6-7).

Question 2

Most practical ML algorithms use stochastic gradient information. Can the authors comment on whether the algorithms and analysis can be adapted to the stochastic setting?

Answer:

Incorporating stochastic gradients is indeed a practical and natural extension of our work.

One way to do this is by subsampling. In the revision (Section 3.1, Appendix D), we show that our basic method allows inexact gradients satisfying ∥∇~f(x)−∇f(x)∥≤ξ\|\widetilde{\nabla} f(x)-\nabla f(x)\|\leq\xi. This doesn't come for free: preserving the convergence rate of Theorem 3.1 requires an upper bound D‾≥D\overline D\geq D on the level-set radius, allowing us to set ξ=O(ε/D‾)\xi = O(\varepsilon/\overline D). Then, the required inexact gradient accuracy can be translated into a batch size via standard concentration inequalities, similarly to ([6], Section 4) or Agafonov et al. (2024a, Section 7).

A more interesting and ambitious goal is to exploit gradient unbiasedness to obtain a decreasing stochastic term O(σ1D/T)O(\sigma_1 D/\sqrt{T}), rather than the fixed error floor O(Dξ)O(D\xi). Such guarantees have been achieved by Extra-Newton (Antonakopoulos et al., 2022) and ACSN (Agafonov et al., 2024b). Extending these results to our setting would require combining four ingredients: generalized Hessian smoothness, inexact Hessians, adaptivity, and stochastic gradients. This is nontrivial, as the MS backtracking decisions depend on noisy gradient estimates, while the generalized smoothness constant itself depends on the gradient norm. We leave this direction for future work.

—

References

[1] Yu. Nesterov. Gradient methods for minimizing composite functions. Mathematical Programming, 140(1):125–161, 2013.

[2] B. O’Donoghue and E. Candès. Adaptive restart for accelerated gradient schemes. Foundations of Computational Mathematics, 15(3):715–732, 2015.

[3] O. Fercoq and Z. Qu. Adaptive restart of accelerated gradient methods under local quadratic growth condition. IMA Journal of Numerical Analysis, 39(4):2069–2095, 2019.

[4] V. Roulet and A. d’Aspremont. Sharpness, restart and acceleration. In Advances in Neural Information Processing Systems 30 (NeurIPS), 2017.

[5] Kamzolov, Dmitry, et al. "Optami: Global superlinear convergence of high-order methods." International Conference on Learning Representations. Vol. 2025.

[6] Lucchi, Aurelien, and Jonas Kohler. "A Sub-sampled Tensor Method for Non-convex Optimization." arXiv preprint arXiv:1911.10367 (2019).

—

We hope that the additional experiments and the clarification on the relative performance of the accelerated and non-accelerated methods address the weaknesses raised and give a clearer picture of when acceleration is advantageous. If so, we would appreciate a reconsideration of the rating. We welcome further discussion if any questions remain.

Reviewer_UadJOpenReview ↗

Response

Dear Authors,

Thank you for the detailed responses. I have read the rebuttal and the updated manuscript.

I appreciate the additional insight into the accelerated vs. non-accelerated variant of your method. The additional experiments help clarify the empirical performance of the proposed methods.

Based on your response and your replies to the other reviewers, I have decided to increase my score accordingly.

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

This paper proposes a series of second-order methods for convex problems under various degrees of Hessian specifications, including generalized and local Lipschitz smoothness, and inexact Hessians. The main methods have a two-loop structure. These main methods share the same inner loop, a backtracking routine that returns a step satisfying a Monteiro-Svaiter condition. The outer loop distinguishes the methods. Accelerated variants build on the extragradient scheme of Monteiro-Svaiter/Carmon, while the non-accelerated variant alternates backtracking calls and initial regularization parameter adjustments for the next call. The main conceptual contribution is to show that a single parameter-free backtracking routine can simultaneously handle generalized smoothness and inexact Hessians, while avoiding cubic subproblems altogether. In addition, a new proof technique is proposed to show that a particular variant achieves the complexity lower bound for inexact Hessians. The methods converge in two regimes: at a linear rate far from the solution, then achieving classical Lipschitz-Hessian rates near the solution, including optimal accelerated rates or, for the non-accelerated method, quadratic convergence under strong convexity and relative accuracy. In particular, the paper proposes the first method that is simultaneously parameter-free, optimal, and robust to inexact Hessians. Empirical performance shows the proposed methods are competitive with or, in the case of the non-accelerated adaptive regularized Newton method, outperform previous work.

Critical strengths
  1. The observation that backtracking a single regularization parameter can simultaneously handle two. It allows addressing generalized smoothness and inexact Hessians parameter-free and without additional algorithmic clutter while keeping similar convergence guarantees.
  2. A method that is simultaneously parameter-free, optimal and robust, closing a gap.
Critical weaknesses
  1. Thin empirical comparison. The experiments are somewhat limited and do not necessarily illustrate some cases where the predicted regimes would be active, for example when inexactness vanishes. Also, no comparison with the method in Chen to give a sense of the price of adaptivity.
  2. Unclear conceptual leap. The paper presents a thorough treatment of the several permutations on Hessian specifications, along with techniques to address them and the mechanics of several cases, but it's not very clear what the conceptual leap is in each one. For example, clarifying why are three regimes are necessary to address inexactness in an adaptive way would help the readers better appreciate the contribution.
Questions for authors
  1. The new counting argument based on \Lambda(A) is introduced because |s_i| isn't lower bounded. Would Carmon's argument go through by simply imposing a lower bound on \tau_i >= \delta' for some parameter \delta'? Would the only consequence not be parameter-free in \delta or would something else fail?
3 comments

Dear Reviewer,

We appreciate the time and effort you put into reviewing our paper. We address the points raised below.

Weakness 1

Thin empirical comparison. The experiments are somewhat limited and do not necessarily illustrate some cases where the predicted regimes would be active, for example when inexactness vanishes. Also, no comparison with the method in Chen to give a sense of the price of adaptivity.

Answer:

We have extended the empirical comparison as follows. We added:

  • additional x-axes to Figure 1: wall-clock time and oracle calls for experiments with exact Hessians, and communication rounds for inexact Hessians;
  • illustrative strongly convex experiments comparing five types of Hessian inexactness (Figure 8, Appendix H.5). The results are consistent with the theory: only the method with fixed Hessian error converges linearly, while the methods with exact Hessians and gradient-relative Hessian error converge locally quadratically;
  • a comparison with Chen et al. in Figure 9, Appendix H.6. Both Algorithms 2 and 3 generally outperform AINE on logistic and Poisson regression problems;
  • sensitivity experiments for Algorithm 3 in Appendix H.4;
  • experiments on 22-nd and 33-rd order Nesterov’s lower-bound function (Appendix H.3, Figures 4,5) and a specially designed lower-bound style function function to illustrate the M0M_0- and M1M_1-dependent convergence regimes (Figure 2a, 2b), which we discuss below.

Figure 1 already illustrates some of our theoretical results:

  • Logistic regression on ijcnn1 and german_numer is locally strongly convex, as their data matrices have full column rank. Consistent with the theory in Section 3.2, we observe much faster local convergence (superlinear/quadratic).

  • Comparing exact and inexact Hessians, we observe a change from superlinear to linear convergence of our basic method on ijcnn1 and german_numer, consistent with the behavior predicted by Theorem 3.3. The curves initially exhibit similar convergence rates when the steps are large and M0∣∣s∣∣M_0 ||s|| dominates δ\delta, and then separate as the steps become smaller.

We have added Figure 2 to illustrate the switch between the far and near regimes. f(y)=φ(R−y1)+13∑i∣yi−yi+1∣3f(y)=\varphi(R-y_1)+\frac13\sum_i|y_i-y_{i+1}|^3 with φ(t)=cosh⁡t−1−t22\varphi(t)=\cosh t-1-\frac{t^2}{2}, R=20R=20, d=300d=300 and x0=0x_0 = 0. The first term grows exponentially, and the second is based on Nesterov's second-order lower-bound function, which is flat near the minimum. Far from the solution, φ\varphi dominates and the method converges linearly. Once the gap becomes small, the cubic part takes over and the rate becomes sublinear. This function has no global Lipschitz constant for the Hessian, so the standard theory gives no guarantee for it. The (M0,M1)(M_0,M_1) setting covers it and correctly predicts both the fast linear phase far from the solution and the sublinear phase near it.

We have also added experiments on Nesterov’s lower-bound functions in Appendix H.3.

For p=2p=2, the Nesterov’s lower-bound function fpf_p (Appendix H.3, (229)) has a Lipschitz-continuous Hessian, so it belongs to the (M0,M1)(M_0,M_1) class with M1=0M_1=0. One could assume the possibility that, in this wider class, the complexity may be governed by M1M_1 alone, so that a linear rate holds for every (M0,M1)(M_0,M_1)-smooth function. Our experiments show that this is not the case: on fpf_p there is no linear convergence. This agrees with the fact that the classical sublinear lower bound remains valid for the (M0,M1)(M_0,M_1)-class, and the sublinear M0M_0-part of our convergence results is necessary.

Weakness 2 and Question 1

Unclear conceptual leap. The paper presents a thorough treatment of the several permutations on Hessian specifications, along with techniques to address them and the mechanics of several cases, but it's not very clear what the conceptual leap is in each one.

Answer:

First, let us consider the non-accelerated method.

Our goal is to build a parameter-free method, since generalized smoothness and inexact Hessians introduce several additional problem parameters. As a base we take the cubic regularized Newton for Lipschitz Hessians. Backtracking cubic regularization parameter is a standard approach for this setup.

However, we take a different route. We use MSBacktrack (Algorithm 1) which solves quadratic problem rather than cubic and adapts τ∼M∣∣s∣∣\tau \sim M ||s|| instead of MM itself.

The main obstacle is that acceptance of MS test (2) does not guarantee that τ=O(M∣∣s∣∣)\tau = O(M ||s||) since the initial guess ηk\eta_k may be too large and the first trial would be accepted which leads to unnecessarily small step. These are exactly two cases of counting in Theorem 3.1: controlled iterations (where τk≤48M0gk+1\tau_k \leq \sqrt{48 M_0 g_{k+1}}) and uncontrolled (which satisfy τk=ηk\tau_k = \eta_k). So the conceptual leap here is follows: if we want to backtrack quadratic subproblems, we should account for iterations where we do not have an appropriate regularization scale.

Next, Hessian inexactness comes into play. Our main finding here: one can adapt δ+L∣∣s∣∣\delta + L||s|| as a single parameter τ\tau. Then, the analysis of exact case goes through with replacement M0∣∣s∣∣M_0 ||s|| by M0∣∣s∣∣+δM_0 ||s|| + \delta. Iterations with τ≲δ\tau \lesssim \delta are gradient-like steps and lead to O(δD2/ε)O(\delta D^2/\varepsilon) term.

Finally, we extend the analysis to generalized smoothness in two steps.

Assume (GH), where L(x)=M0+M1∣∣∇f(x)∣∣L(x) = M_0 + M_1 ||\nabla f(x)||. Naively, following the approach above we would get τ=O(δ+L(x+s)∣∣s∣∣)\tau = O(\delta + L(x+s)||s||). But MS test allows us to express the gradient at x+sx+s through τ∣∣s∣∣\tau ||s|| (13, Lemma C.1). This allows a faster far regime, while preserving the classical near rate. Indeed, we have two cases: either ∣∣s∣∣≲1/M1||s||\lesssim 1/\sqrt{M_1}, in which case the additional term can be absorbed and we recover the previous bound τ=O(δ+M0∣∣s∣∣)\tau=O(\delta+M_0||s||), or ∣∣s∣∣≳1/M1||s||\gtrsim 1/\sqrt{M_1}, which gives a constant lower bound on the step length and guarantees geometric progress.

Under (LH), generalized smoothness inequality holds only within radius ρ\rho. The main idea is to ensure that the Taylor bound applies inside this ball.Two cases: if ∣∣s∣∣≤ρ/2||s||\leq\rho/2, we can apply the local smoothness condition, otherwise we get constant lower bound on step length ∣∣s∣∣>ρ/2||s||>\rho/2. Thus, we have four problem constants (M0,M1,ρ,δM_0, M_1, \rho, \delta) that affect the analysis in different ways. Yet, the non accelerated method handles all of them through the same adaptive parameter τ\tau.

For example, clarifying why are three regimes are necessary to address inexactness in an adaptive way would help the readers better appreciate the contribution.

By considering each extension, we naturally arrive at the three regimes you mention. Hessian inexactness introduces the regime τ≲δ\tau\lesssim\delta, generalized smoothness adds the regime with a constant lower bound ∣∣s∣∣≳r0||s||\gtrsim r_0, and between them we recover the classical regime ∣∣s∣∣≳τ/M0||s||\gtrsim\tau/M_0.

For the optimal accelerated method, the main challenge is to combine these three regimes while preserving the optimal complexity. This is closely related to your Question 1.

[Question 1] The new counting argument based on \Lambda(A) is introduced because |s_i| isn't lower bounded. Would Carmon's argument go through by simply imposing a lower bound on \tau_i >= \delta' for some parameter \delta'? Would the only consequence not be parameter-free in \delta or would something else fail?

Answer:

Under standard Lipschitz Hessian assumption, this could be a valid alternative. Imposing τi≥δ’≥16δ\tau_i \geq \delta’ \geq 16 \delta will give ∣∣si∣∣≥τi/(48M0)||s_i|| \geq \tau_i/ (48M_0) by (20) in Lemma C.3 for iterations with rejected trials. Then, it seems that Carmon’s proof can be adapted, with a separate counting of iterations with τi=ηi=δ′\tau_i = \eta_i = \delta'. The expected rate would be O(δ’R2/T2+L2R3/T7/2)O(\delta’ R^2/T^2 + L_2 R^3/T^{7/2}). The corresponding optimal rate is achieved by Chen et al. (2026), who explicitly set τ=2δ+L∣∣s∣∣\tau=2\delta+L||s|| and use a regularization schedule depending on δ\delta.

So it seems that under (H) the necessity of knowing δ\delta is the main limitation.

However, under generalized smoothness, imposing a lower bound on τi\tau_i addresses only the Hessian inexactness regime. As in the non-accelerated analysis, we also need to account for iterations with ∣∣si∣∣≳r0||s_i||\gtrsim r_0. Our Λ(A)\Lambda(A)-based counting combines these regimes (classical and generalized smoothness), recovering geometric convergence in the far regime and the optimal classical rate in the near regime, without requiring knowledge of δ\delta.

We have also added a discussion of these points to Appendix I of the revised paper.

—

We hope that the extended experiments and the discussion above, together with Appendix I, address your concerns. If so, we would appreciate it if you could reconsider your rating. We welcome further discussion if any questions remain.

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

The paper studies convex second-order optimization when Hessian variation is locally controlled by a quantity that grows with the gradient norm and when only a uniformly inexact Hessian is available. Its main idea is to adapt one regularization parameter through a Monteiro–Svaiter residual test, allowing the same parameter to compensate for both local Hessian variation and approximation error. The paper develops a basic adaptive Newton method and several accelerated variants. The principal accelerated algorithm converges linearly far from the optimum and then attain the classical optimal complexity O((M0 R^3/epsilon)^(2/7) + sqrt(delta R^2/epsilon)). Additional results establish global linear and superlinear convergence under strong convexity and local quadratic convergence under relative Hessian accuracy. The proofs provide detailed backtracking and oracle-complexity analyses. Experiments on regression problems and one-dimensional examples illustrate the methods

Critical strengths

The paper makes a strong theoretical contribution to adaptive second-order optimization. The central result, Theorem 4.1, shows that a single adaptive regularization parameter can simultaneously account for Hessian inexactness and local smoothness. The method achieves the known optimal dependence under Lipschitz-Hessian smoothness without requiring either the smoothness constant or the Hessian-error level as input. The analysis also distinguishes a far regime with linear convergence, governed by M₁ and ρ, from a near regime governed by M₀ and δ, providing more insight than a single worst-case polynomial bound. Finally, the local-convergence results show that Hessian errors do not simply accumulate and that the method recovers superlinear or quadratic convergence under appropriate vanishing-error conditions.

Critical weaknesses

The main weakness lies in the experimental evaluation. The setting remains computationally expensive because all methods use exact full-data gradients, including during backtracking, even when the Hessian is approximated using only 10% of the samples. A single outer iteration may therefore involve multiple costly gradient evaluations and subproblem solves. Since performance is reported only by outer iterations, these costs are hidden. Reporting the total gradient and Hessian evaluations numbers would enable a more meaningful comparison of practical efficiency.

Questions for authors

The following questions may help clarify the paper’s potential practical impact:

  1. Since exact full-data gradients may dominate the practical cost when the dataset is large, could the method incorporate adaptive gradient subsampling or distributed gradient compression?

  2. How might the analysis change when the Hessian error varies over time, as with adaptive subsampling, quasi-Newton approximations, or lazy Hessian updates?

  3. Do the far/near regime insights suggest practical rules for choosing when to refresh the Hessian, increase sample size, or switch optimization methods?

4 comments

Dear Reviewer,

We thank you for the time and effort you devoted to reviewing our work. We provide our responses to your comments below.

Weakness 1

The main weakness lies in the experimental evaluation. The setting remains computationally expensive because all methods use exact full-data gradients, including during backtracking, even when the Hessian is approximated using only 10% of the samples. A single outer iteration may therefore involve multiple costly gradient evaluations and subproblem solves. Since performance is reported only by outer iterations, these costs are hidden. Reporting the total gradient and Hessian evaluations numbers would enable a more meaningful comparison of practical efficiency.

Answer:

To better reflect the computational costs of the methods, in the revised version we provide additional x-axis for experiments in Figure 1.

For exact Hessians, we add comparisons in terms of wall-clock time and oracle calls (gradient evaluations and Hessian-vector products). Note that all methods use one Hessian per outer iteration, which is reused during backtracking, but may require several gradient evaluations and subproblem solves.

For the experiments with inexact Hessians, we additionally report communication rounds. All methods use the server’s local Hessian and full gradient obtained by aggregating local gradients of each device. Since devices compute local gradients in parallel and the server is assumed to be a powerful machine, the main bottleneck is communication.

Across all measures—iterations, oracle calls, wall-clock time, and communication rounds—the performance of our methods remains consistent, with the basic non-accelerated method performing best. Their wall-clock efficiency comes from solving only quadratic subproblems.

Question 1

Since exact full-data gradients may dominate the practical cost when the dataset is large, could the method incorporate adaptive gradient subsampling or distributed gradient compression?

Answer:

In the revision, we added an extension of our basic non-accelerated method to inexact gradients (Section 3.1 and Appendix D). Assuming bounded gradient errors $ ||\tilde{\nabla} f(x)-\nabla f(x)||\leq\xi$, a small modification of the MS acceptance test preserves the convergence rate of Theorem 3.1, up to constants, provided that ξ≤ε/(288D‾)\xi \leq \varepsilon/(288\overline D) for a known upper bound D‾≥D\overline D\geq D. Equivalently, a fixed error level ξ\xi introduces an additional term O(Dξ)O(D\xi) in convergence rate, similarly to the non-accelerated Inexact Tensor Method (Agafonov et al., 2024a, Theorem 2).

Thus, gradient subsampling or distributed compression can be incorporated when their approximation errors satisfy the required bound. Sufficient mini-batch sizes can be derived using concentration inequalities, see, e.g., ([1], Section 4) or (Agafonov et al., 2024a, Section 7).

A more interesting direction is to exploit gradient unbiasedness to obtain a decreasing stochastic term O(σ1D/T)O(\sigma_1D/\sqrt{T}), rather than the fixed O(Dξ)O(D\xi) error floor. Such variance-dependent guarantees have been obtained by stochastic second-order methods, including Extra-Newton (Antonakopoulos et al., 2022) and ACSN (Agafonov et al., 2024b). Extending these techniques to simultaneously handle generalized Hessian smoothness, inexact Hessians, adaptivity, and stochastic gradients is nontrivial, particularly because the MS backtracking decisions depend on the gradient estimates and the smoothness constant depends on the gradient norm. We leave this extension for future work.

[1] Lucchi, Aurelien, and Jonas Kohler. "A Sub-sampled Tensor Method for Non-convex Optimization." arXiv preprint arXiv:1911.10367 (2019).

Question 2

How might the analysis change when the Hessian error varies over time, as with adaptive subsampling, quasi-Newton approximations, or lazy Hessian updates?

Answer:

Let us begin with a strongly convex case. In Section 3.2, we establish three convergence guarantees for our basic method (Algorithm 2), allowing the Hessian approximation error δk\delta_k to vary across iterations:

  1. global linear convergence for uniformly bounded δk≤δ\delta_k\leq\delta (Theorem 3.3)
  2. global superlinear convergence for δk→0\delta_k \to 0 (Theorem 3.3)
  3. local quadratic convergence under δk≤ν∣∣∇f(xk)∣∣∣\delta_k \leq \nu ||\nabla f(x_k)||| (Theorem 3.4)

The second result directly covers lazy Hessians, as reusing the exact Hessian for a fixed number of iterations ensures δk→0\delta_k\to0.

Inexactness condition in 3) is suitable for adaptive Hessian subsampling. One can increase the batch size to ensure δk≤ν∣∣∇f(xk)∣∣\delta_k\leq\nu ||\nabla f(x_k)|| with high probability by concentration inequalities. This recovers global superlinear and local quadratic convergence without modifying the optimization algorithm.

Our theory applies to several Quasi-Newton approximations under L1L_1-Lipschitz gradient assumption. In particular, (Kamzolov et al, 2025b, Lemmas C.2, C.3) establish δ≤L1\delta \leq L_1 for L-BFGS with history and the sampled convex Broyden class. Thus, our guarantees apply with δ=L1\delta=L_1 in both strongly convex and convex cases.

Stronger guarantees are possible when QN approximations converge to the true Hessian, as established for SR1 under additional assumptions [1, Theorem 2] [2, Theorem 8.2]. Such convergence would imply δk→0\delta_k \to 0 and superlinear convergence by Theorem 3.3, provided the corresponding conditions hold for our iterates. As far as we understand, establishing such properties requires a dedicated QN analysis, potentially with modified approximation schemes or additional structural assumptions (e.g., self-concordance), which we leave for future work.

Now, let us consider varying Hessian inexactness in the general convex case. When the Hessian accuracy can be controlled, e.g., through subsampling, it is possible to recover the convergence rates of the exact methods.

The rate O(M0D3/k2+δD2/k)O(M_0D^3/k^2+\delta D^2/k) in Corollary C.8 suggests that decreasing δk\delta_k at a rate of O(1/k)O(1/k) may recover the exact-Hessian rate. However, this does not follow directly from our analysis with a uniform error bound. Instead, for Algorithm 2, consider the condition δk≤ηk/16\delta_k\le\eta_k/16, where ηk\eta_k is the initial regularization parameter at iteration kk. Whenever backtracking rejects at least one trial, τk≥2ηk\tau_k\ge 2\eta_k, and Lemma 3.2 yields in the secod case (small-step regime) $ \tau_k\le8\delta_k+24M_0||s_k|| \le\frac{\tau_k}{4}+24M_0||s_k||, $ hence τk≤32M0∣∣sk∣∣\tau_k\le32M_0||s_k||. This removes the error-dependent term from the iteration-counting argument and recovers the O(1/k2)O(1/k^2) rate under generalized smoothness. A similar extension seems to be possible for the accelerated Algorithm 3 to recover O(1/k7/2)O(1/k^{7/2}). If you find these extensions interesting and important to include in the paper, we will add them to the revision, together with full proofs in the Appendix.

We hope that these observations clarify how our results can include varying inexactness.

[1] Conn, Andrew R., Nicholas IM Gould, and Ph L. Toint. "Convergence of quasi-Newton matrices generated by the symmetric rank one update." Mathematical programming 50.1 (1991): 177-195.

[2] Nocedal, Jorge, and Stephen J. Wright. Numerical optimization. New York, NY: Springer New York, 1999.

Question 3

Do the far/near regime insights suggest practical rules for choosing when to refresh the Hessian, increase sample size, or switch optimization methods?

Answer:

In short, the far/near analysis gives qualitative rules and, if the problem constants are known, quantitative predictions. However, it does not allow us to detect the current regime from local information alone.

What the theory gives. Theorems 3.1 and 4.1 give the threshold εtr\varepsilon_{tr} at which the method switches from the far regime to the near regime, and from the proofs it is possible to derive the required decrease of the inexactness δt\delta_t that keeps the second-order rate (see condition (5) for Theorem 3.4 as example). If M0M_0, M1M_1 and the other constants in τ\tau are known, this gives a theoretical prediction of the moment of the switching iteration and a schedule for the Hessian accuracy. This leads to a simple practical rule. In the far regime, a low-accuracy Hessian is enough: it can be refreshed rarely or estimated from a small sample. Its accuracy should then increase towards the end of the run, through more frequent refreshes or a larger sample size.

Why local information is not enough. In practice these constants are unknown, and τ\tau depends on several of them. Moreover, the observed local rate can be misleading. We show two examples.

  1. Nesterov’s lower-bound function (Appendix H.3). During the first 100100 iterations the curves look linear or even superlinear, which could suggest the fast far regime driven by M1M_1. In fact, the method is still far from the solution: the gap is only 3-7 times smaller than at the start, and the convergence is sublinear.

  2. german_numer (Figure 1). The function is strongly convex. The exact methods converge linearly at first and then switch to superlinear convergence. The inexact methods have the same linear phase, but then they stay linear, at the level set by δ\delta. Locally, it is not possible to tell whether the method is still in the first linear phase or is already limited by δ\delta and needs a more accurate Hessian.

So, to sum up, to the best of our knowledge, the switch cannot be predicted reliably without knowing the problem constants. The theory nevertheless supports next heuristics: use an increasing-accuracy schedule, with a cheap Hessian approximation early and a more accurate one near the solution.

—

We believe that we have addressed the weaknesses you raised. We welcome further discussion if any questions remain.If our responses resolve your concerns, we would appreciate it if you could reconsider your rating.

Reviewer_B6LrOpenReview ↗

Response

Dear Authors, Thank you for the detailed responses. I appreciate the effort of adding wall clock time and the explanation on the Hessian approximation analysis, I find the gradient norm constraint is the most practical one. Yet, I still think a stochastic version would be more useful, as access to the full dataset is often unrealistic in large-scale ML problems. Nevertheless, I think the theoretical analysis is strong and the paper is worth publishing. I therefore maintain my original score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Revisions

We thank the reviewers for the time and effort they put into reviewing our work. Your questions and suggestions led us to explore extensions of the theory and broaden experimental evaluation.

We have prepared a revised version of the paper addressing the weaknesses raised in the reviews. All changes are highlighted in blue. Below, we briefly summarize how we addressed them.

  1. Practical performance of optimal acceleration (Reviewer UadJ, Weakness 1)

The proposed accelerated parameter-free method is outperformed by the simpler non-accelerated method in the experiments.

its practical significance is less convincing when the accelerated method does not outperform the simpler baseline.

In our view, this can be explained by two factors: the local strong convexity of logistic regression and the ability of non-accelerated Newton methods to automatically exploit it, while accelerated methods typically need to be specifically designed for the strongly convex case. We discuss this in detail in our comment to Reviewer UadJ.

The original submission already included one-dimensional experiments showing that acceleration outperforms non-accelerated methods (Appendix G.2 in the original submission; now the first three columns of Figure 3 in Appendix H.2). We have extended these experiments in the revised version, including experiments on Nesterov's second-order lower-bound function (Appendix H.3, Figures 4, 5) and ∣∣x∣∣6||x||^6 on Figure 2c.

We also note that the same phenomenon of non-accelerated methods outperforming accelerated ones on logistic regression was observed by Carmon et al. (2022) and similar behavior can occur for first-order methods as well.

  1. Wall-clock time (Reviewer UadJ, Weakness 1) and computational cost (Reviewer B6Lr, Weakness 1)

A comparison in terms of wall-clock time would also be useful to better understand the benefits of the proposed methods.

Reporting the total gradient and Hessian evaluations numbers would enable a more meaningful comparison of practical efficiency.

We extended Figure 1 with additional performance metrics: wall clock time, oracle calls and communications. The relative performance of our methods remains consistent across these metrics.

  1. Experiments illustrating theory (Reviewer 8i5x, Weakness 1)

Thin empirical comparison. The experiments are somewhat limited and do not necessarily illustrate some cases where the predicted regimes would be active, for example when inexactness vanishes.

We substantially extended the experimental evaluation to illustrate the theoretical convergence regimes. In particular, we added strongly convex experiments comparing five types of Hessian inexactness, including fixed and vanishing errors (Appendix H.5, Figure 8). The results illustrate linear convergence under fixed inexactness and faster convergence as the error vanishes.

We also added experiments illustrating the far and near convergence regimes governed by M1M_1 and M0M_0 on Figures 2a,2b.

A more detailed response is provided in our reply to Reviewer 8i5x.

  1. Comparison with Chen et al. (2026) (Reviewer 8i5x, Weakness 1)

Also, no comparison with the method in Chen to give a sense of the price of adaptivity.

We added a comparison with tuned AINE (Chen et al., 2026) in Appendix H.6 (Figure 9). Both Algorithms 2 and 3 generally outperform AINE on logistic and Poisson regression problems.

  1. Unclear conceptual leap (Reviewer 8i5x, Weakness 2)

it's not very clear what the conceptual leap is in each one.

For example, clarifying why are three regimes are necessary to address inexactness in an adaptive way would help the readers better appreciate the contribution.

We provide a detailed answer in our response to Reviewer 8i5x. We also added a new Appendix I, Key Ideas Behind Our Methods, explaining main conceptual steps:

  • Replacing cubic subproblems with adaptive quadratic ones.
  • Accounting for overregularized iterations in the analysis of adaptive quadratic subproblems.
  • Handling Hessian inexactness and generalized smoothness through a single regularization parameter.
  • Combining the resulting three regimes (classical M0M_0, Hessian inexactness δ\delta, and generalized smoothness M1,ρM_1, \rho) in optimal acceleration.

–

We also included an extension of Algorithm 2 to inexact gradients (Section 3.1, Appendix D) and extended sensitivity experiments to our accelerated methods (H.4).

– Please find our detailed responses to the weaknesses, individual questions, and the minor point in our replies to each reviewer. We believe we have addressed all the weaknesses raised. If the reviewers agree, we would appreciate it if they could reconsider their ratings. If any concerns remain, we welcome further discussion.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.