- Rating
- 3
- Confidence
- 4
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper considers the question of optimal acceleration of convex second-order methods under -inexact Hessians. The contribution is threefold:
- Accelerated Inexact Newton Extragradient method, which achieves rate.
- Its superfast version, which achieves rate for functions under higher smoothness.
- Lower bounds of and
Critical strengths
The main strength of this paper is its theoretical analysis. The authors close the question of optimal acceleration of second-order methods with inexact Hessians. Moreover, they consider a higher-smoothness setting and propose a near-optimal method in this scenario. I find these theoretical results important for modern optimization.
Critical weaknesses
- Related works.
- To the best of my knowledge, none of the works (Gasnikov et al., 2019; Bubeck et al., 2019; Jiang et al., 2021) consider the implementation of a near-optimal third-order method using only second-order derivatives (superfast) and achieve the rate with such an implementation (lines 41–42, 150–151). As far as I know, the first method achieving this rate is [1].
- Similarly, for optimal tensor methods, a superfast second-order implementation was considered by Carmon et al. (2022). It is important to note that they achieved Hessian complexity, while gradient complexity.
- I am not sure that footnote (c) in Table 1 is correct as written. Agafonov et al. (2024a) have Section 6 dedicated to solving the tensor subproblem for . The paper indeed lacks an explicit inner iteration complexity bound, but establishes relative strong convexity and smoothness of the subproblem and provides a way to solve it using BDGM. The iteration complexity follows directly from these results and Nesterov (2021a). At the same time, Section 4 of Ghadimi et al. (2017) only restates eigendecomposition, without explicit per iteration cost, yet the INCR and AINCR rows have no such footnote.
- From my perspective, it is inaccurate to state (lines 453–454) that Proposition 5.1 extends the lower bounds of Agafonov et al. (2024b) , as they consider stochastic gradients. Indeed, in the exact-gradient setting, the authors remove the linear span assumption, but the wording should be clear and precise.
- Practicality.
- The authors do not compare their method with inexact non-accelerated methods. Following the experimental results of Carmon et al. (2022), it would be interesting to see whether optimal acceleration can outperform basic inexact methods and non-optimal accelerated ones in the inexact Hessian setting.
- At the same time, AINE requires three problem parameters: the smoothness constant, the inexactness level, and the distance to the solution, which may make it impractical. From the experimental section in the appendix, it is not clear how these parameters were chosen for different methods.
- I think that the writing in several places oversimplifies the arguments and may mislead readers:
- lines 127-129. I do not see how assumption 2.3 unifies FO and SO methods by setting .
- lines 214-215: the potential bound (Lemma 3.2) requires not only MS condition, but updates in lines 27, 15-16, 20-21 of Algorithm 2.
- lines 390, 399-401. From monotone version of algorithm it follows only that belongs to the level-set. To bound it seems that the authors also use Lemma 3.2.
- line 374. I am not sure that is needed only for stability. It seems to be a crucial part of the argument needed to bound all the inner iterates.
- The text has minor issues, e.g.
- line 136: “has known suboptimal”
- line 150: “generalization”
- line 167: missing braces
- line 205: is defined as argmin over
- line 22 of Algorithm 1: , while algorithm requires
- lines 329: is undefined. Is it compact?
- line 357: is undefined
- the paper uses the ICLR 2026 template instead of 2027.
[1] Kamzolov, Dmitry, and Alexander Gasnikov. "Near-optimal hyperfast second-order method for convex optimization and its sliding." arXiv preprint arXiv:2002.09050 (2020).
Questions for authors
- What is the main obstacle to remove additional logarithm in setting?
- Why do you compare AINE with the Optimal MS Acceleration method of Carmon et al. (2022), rather than with your own algorithm with exact Hessians and ?
- Is it possible to show any local convergence guarantees for your methods?