Convergence rates of Newton's method for strongly self-concordant minimization

Nick Tsipinakis; Panos Parpas

REVIEW 4 major objections 6 minor 13 references

Convergence rates of Newton's method for strongly self-concordant minimization

T0 review · 4 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For strongly self-concordant objectives, Newton's method provably converges faster and from a larger region.

desk verdict A solid, limited refinement of Newton's method theory for strongly self-concordant functions; the main bound is correct, but the proof needs cleaning and the global assumption deserves emphasis. read the letter →

arxiv 2507.23558 v1 pith:2KX2I4V2 submitted 2025-07-31 math.OC

Nick Tsipinakis , Panos Parpas This is my paper · ORCID

classification math.OC MSC 90C5390C2565K0549M15

keywords Newton'smethodstronglyself-concordantfunctionslocalquadraticconvergenceNewtondecrementaffineinvarianceconvexoptimizationrates

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks whether the extra curvature control of strongly self-concordant functions buys anything for Newton's method beyond what general self-concordance already guarantees. It answers yes: for a strongly self-concordant objective with constant $M$, pure Newton satisfies $\lambda(x_{k+1}) \leq \frac{\sqrt{1+M\lambda_k}}{2}\,M\lambda_k^2$, which is tighter than the classical self-concordant bound. Consequently the quadratic phase starts earlier—at $\lambda \le 6/(5M)$ instead of roughly $0.7/M$—and every step inside that region is provably faster. If correct, this means a purely structural Hessian condition, not strong convexity or Lipschitz constants, already improves the worst-case local behavior of Newton's method.

What carries the argument

The central object is the Newton decrement $\lambda(x)=\|\nabla f(x)\|_x^*$ together with a one-step bound (Lemma 3.2): $\lambda(x_{k+1}) \leq c_k\sqrt{1+Mr_k}\,\lambda(x_k)$, where $r_k$ is the step length in the local Hessian norm and $c_k$ is a ratio depending on $M$, $r_k$, and the damping parameter $\alpha_k$. Specializing to $\alpha_k=0$ yields the pure-Newton inequality (3.12). The proof is carried by Lemma 2.1, the Hessian comparison inequalities for strongly self-concordant functions, which control the average Hessian $G_k$ along the step by factors of $1+Mr_k/2$ and allow the proof to replace the Hessian at $x_{k+1}$ with the Hessian at $x_k$.

What would settle it

Run pure Newton's method on the log-sum-exp objective (2.7) with $M=2$ from a point with $\lambda(x_0)=0.55$, which lies inside the claimed region $\lambda \le 6/(5M)=0.6$. If $\lambda(x_1)$ does not satisfy $\lambda(x_1) \le \frac{\sqrt{1+2\lambda_0}}{2}\,2\lambda_0^2$, or if $\lambda(x_1) > \lambda(x_0)$, then the bound (3.12) or the region claim fails.

Watch

Extended reading notes

Core claim

Under the global strong self-concordance condition (Definition 2.1), the local quadratic convergence of pure Newton's method is governed by the inequality $\lambda(x_{k+1}) \leq \frac{\sqrt{1+M\lambda_k}}{2}\,M\lambda_k^2$ (Equation (3.12)). This bound is pointwise no larger than the general self-concordant bound $\frac{M\lambda_k^2}{2(1-M\lambda_k/2)^2}$ whenever the method is in its quadratic regime, and the regime itself extends to $\lambda \le 6/(5M)$, compared with $\lambda \le (3-\sqrt{5})/M \approx 0.764/M$ for general self-concordant functions with the same $M_{sc}=M/2$. The proof tracks the Newton decrement through a single step using Hessian comparison inequalities, showing that strong self-concordance keeps the average Hessian along the step close to the endpoint Hessians.

Load-bearing premise

The objective must satisfy the strong self-concordance inequality for every quadruple $x,y,z,w$ in the whole space with a single global constant $M$; if the condition holds only locally or $M$ varies, the enlarged region and the faster rate have no guarantee.

Editorial extensions

If this is right

For any strongly self-concordant function with parameter $M$, pure Newton's method is guaranteed to enter its quadratic phase once $\lambda(x_k) \le 6/(5M)$, a region roughly 57% larger than the general self-concordant threshold of about $0.7/M$.
Inside the quadratic phase, each iterate satisfies the tighter contraction $\lambda_{k+1} \le \frac{\sqrt{1+M\lambda_k}}{2}\,M\lambda_k^2$, so the same accuracy is reached in fewer Newton steps than the general self-concordant bound predicts.
The damped Newton method with $\alpha_k=M\lambda_k$ also has an explicit quadratic bound, and the paper gives a worst-case bound on the number of damped steps before the quadratic phase begins.
Because strong self-concordance is affine-invariant, the improved rates hold under arbitrary invertible linear changes of variable, matching the invariance of the classical self-concordant theory.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper's constant $M$ is global; in practice one often knows only a local modulus. A natural next step is to check whether the region $6/(5M)$ degrades gracefully when $M$ is replaced by a locally valid value near the optimum.
For functions that are strongly convex with Lipschitz Hessian, the induced $M=L/\mu^{3/2}$ can be large, so the enlarged region may be small in absolute coordinates; the affine-invariant statement is the real content.
The bound (3.12) may not be tight: as $M \to 0$ the constant $\sqrt{1+M\lambda}/2$ approaches $1/2$, and quadratic functions (which satisfy the definition in the limit) converge in one step, so a sharper norm argument could yield a better constant.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

This paper fills a real, if small, gap: a local convergence analysis of Newton's method for strongly self-concordant functions, with explicit constants. The main bound (3.12) is correct; I re-derived it and it follows cleanly from Rodomanov and Nesterov's Lemma 2.1, with no circularity. The comparison with the self-concordant rate is also valid as a pointwise upper-bound comparison, which is the standard meaning of 'faster' in this literature. Credit where due: the paper is transparent, the constants are explicit, and it gives concrete examples and notes the affine-invariance property.

Now the soft spots, in order of severity. First, Lemma 3.2 contains an algebraic slip in the last display: it equates (d_k^T grad^2 f_k d_k)^{1/2} with lambda_k, but the correct value is lambda_k/(1+alpha_k). Since the latter is smaller, the stated inequality remains true, so the damage is limited to the proof's precision; but the line as written is false and should be fixed. Second, the quadratic-region threshold is stated inconsistently: the text after Theorem 3.1 says the region is lambda <= 131/(100M), while the comparison section says lambda <= 6/(5M). These differ (1.31 vs 1.2); one is a typo, but the paper currently contradicts itself. Third, Definition 2.1 is very strong, quantifying Hessian closeness over all x,y,z,w, not just near the optimum or along the Newton path. The paper does not hide this, but it severely limits practical scope; a local version would be much more useful. Fourth, the bound comparison is made using (3.17), which is more conservative than (3.12); the paper should state clearly that the comparison is between worst-case upper bounds, not per-instance behavior.

None of this undermines the central mathematical claim. The proof is understandable, the constants are explicit, and the citation pattern is appropriate. The issues are calibration and exposition, not a load-bearing flaw. This deserves a serious referee; I would send it to review and ask for a careful revision of Lemma 3.2, the threshold inconsistency, and a fuller discussion of the global assumption.

Referee Report

4 major / 6 minor

Summary. The paper studies the local convergence of Newton's method for strongly self-concordant minimization, a subclass of self-concordant functions. After recalling standard self-concordance results and defining strong self-concordance (Definition 2.1), it proves a one-step bound on the Newton decrement (Lemma 3.2) and derives local quadratic rates for pure and damped Newton (Theorem 3.1). The pure Newton bound (3.12) and a conservative variant (3.17) are compared with the general self-concordant bound (3.16), and the paper claims that strong self-concordance yields a faster worst-case quadratic rate and an enlarged region of local quadratic convergence (λ ≤ 6/(5M) versus λ ≤ (3−√5)/M). The paper also gives a global convergence corollary and a bound on the number of damped steps.

Significance. If the results hold, they provide the first local analysis of Newton's method specific to strongly self-concordant functions, confirming that the stronger curvature assumption improves the worst-case local convergence estimates. The proofs are largely self-contained and do not fit parameters or assume the target result. The claimed improvement is in the worst-case upper bound, which is the standard meaning of 'provably faster' in this literature. The main limitations are the very strong global character of Definition 2.1 and the need for several proof clarifications, but the central inequality (3.12) and its derivation are sound.

major comments (4)

[Section 2, Definition 2.1] The definition quantifies over all x,y,z,w ∈ R^n, which makes it much stronger than the standard formulation of strong self-concordance in [13]; please clarify whether this is exactly the definition used in [13]. If it is a stronger condition, the abstract and title overstate the scope, since the results would apply to a proper subclass of strongly self-concordant functions. Please either prove equivalence or adjust the claims and the attribution to [13].
[Section 3, Lemma 3.2] In the proof, the equality (d_k^T ∇²f_k d_k)^{1/2} = λ_k is incorrect: from the definition of d_k in (3.5) the left-hand side equals λ_k/(1+α_k). Since 1+α_k ≥ 1, the inequality λ_{k+1} ≤ c_k sqrt(1+M r_k) λ_k still holds as a relaxation, but the proof must replace the equality by ≤ and state the relaxation explicitly.
[Section 3, after Eq. (3.17)] The claim that for strongly self-concordant functions the local quadratic rate is activated when λ(x_k) ≤ 6/(5M) is stated without derivation. This is one of the two main claims in the abstract, so please supply the argument. For instance, (3.17) implies λ_{k+1} ≤ (1+Mλ/2)(Mλ/2) λ_k, which gives contraction when (1+Mλ/2)(Mλ/2) ≤ 1, i.e., Mλ ≤ √5−1 ≈ 1.236; hence Mλ ≤ 6/5 is sufficient.
[Section 3, Corollary 3.1] The proof says the descent bound follows immediately from (2.4), but (2.4) is stated for the step size 1/(1+M_sc λ) with M_sc = M/2, whereas (3.1) with α_k = Mλ uses the step size 1/(1+Mλ). These differ, so either a more general descent theorem is needed or the proof must be completed. This affects the bound on K in the global-phase analysis that follows Theorem 3.1.

minor comments (6)

[Section 3, Eq. (3.10)] Equation (3.10) contains undefined symbols and garbled terms (e.g., '1 + ak'); please rewrite the display.
[Section 3, after Theorem 3.1] The condition λ(x_k) ≤ 131/(100M) is described as the quadratic phase; it is actually a sufficient condition for λ(x_{k+1}) < λ(x_k) under (3.12), not a characterization of quadratic convergence; please clarify the wording.
[Section 3, final paragraph] The comparison sentence says 'for strongly self-concordant function' (singular); use 'functions'.
[References, [3]] Reference [3] lists 'SIAM, ???' for the publisher location; please complete it.
[Section 3, comparison paragraph] The statement that the rate (3.17) is 'faster' than (3.16) is a comparison of worst-case upper bounds; suggest adding 'worst-case' for precision.
[Theorem 3.1, part 2] The final constant 3√2/2 ≈ 2.12 is correct, but the derivation uses √2 · 3/2; consider displaying this factorization for readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the core bound and comparison follow from external definition and lemmas, not from the conclusions.

full rationale

The paper's derivation is not circular. The central lemma (Lemma 3.2) uses only the definition of strong self-concordance (Definition 2.1), an external bound from Rodomanov and Nesterov [13, Lemma 4.1] reproduced as Lemma 2.1, and a standard eigenvalue argument (Lemma 3.1). The subsequent Theorem 3.1 substitutes r_k = lambda_k/(1+alpha_k) and c_k algebraically; no fitted constants or data are involved. The comparison between rates, Eq. (3.17) vs. Eq. (3.16), is an algebraic comparison of upper bounds using (1+s)(1-s)^2 <= 1, and the enlarged-region claim follows from solving the contraction inequalities lambda_{k+1} < lambda_k for each bound. The self-citations [7,8] appear only in the introduction describing prior multilevel Newton work; they are not used to justify the local analysis, so they are not load-bearing. The only caveats concern correctness calibration, such as the possibly over-strong 'for all z,w' quantification in Definition 2.1 and approximate constants in the region statements, which are not circularity. No equation is equivalent to its conclusion by construction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the definition of strong self-concordance and on imported lemmas from the literature; no free parameters are fit and no new entities are postulated.

assumptions (4)

domain assumption Strong self-concordance (Definition 2.1): grad^2 f(y) - grad^2 f(x) <= M ||x-y||_z grad^2 f(w) for all x,y,z,w in R^n.
This is the defining property of the function class studied; the entire analysis rests on it. It is a global, uniform bound on Hessian variation.
domain assumption Lemma 2.1 (Rodomanov-Nesterov, 2021, Lemma 4.1) bounding Hessians and the integral G along a segment.
The paper imports this result without proof; it converts the strong self-concordance condition into the explicit matrix inequalities used in Lemma 3.2.
standard math Standard self-concordant analysis: Theorem 2.1 and Theorem 2.2 from Nesterov (2018) are used for the global phase and for the comparison rate (3.16).
Well-known results in the SC literature; used as benchmarks and for the damped phase.
domain assumption The objective f is twice differentiable, strictly convex, bounded below, and attains a minimizer x*.
Standard assumptions for Newton's method and for the Newton decrement to be well-defined; stated in the Preliminaries.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Convergence rates of Newton's method for strongly self-concordant minimization." pith.science (2026). https://pith.science/paper/2KX2I4V2

@misc{pith2026250723558,
  author       = {Pith},
  title        = {Pith review of: Convergence rates of Newton's method for strongly self-concordant minimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2KX2I4V2}},
  note         = {Machine review of arXiv:2507.23558}
}

read the original abstract

Newton's method has been thoroughly studied for the class of self-concordant functions. However, a local analysis specific to strongly self-concordant functions (a subclass of the former) is missing from the literature. The local quadratic rate of strongly self-concordant functions follows, of course, from the known results for self-concordant functions. However, it is not known whether strongly self-concordant functions enjoy better theoretical properties. In this paper, we study the local convergence of Newton's method for this subclass. We show that its quadratic convergence rate differs from that of general self-concordant functions. In particular, it is provably faster for a wide range of objective functions and benefits from a larger region of local convergence. Thus, the results of this paper close the gap in the theoretical understanding of Newton's method applied to strongly self-concordant functions.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 10 canonical work pages

[13]

SIAM Journal on Optimization 31(1), 785–811 (2021) https: //doi.org/10.1137/20M1320651 11

Rodomanov, A., Nesterov, Y.: Greedy quasi-newton methods with explicit super- linear convergence. SIAM Journal on Optimization 31(1), 785–811 (2021) https: //doi.org/10.1137/20M1320651 11

work page doi:10.1137/20m1320651 2021
[1]

Springer Optimization and Its Applications, vol

Nesterov, Y.: Lectures on Convex Optimization, 2nd edn. Springer Optimization and Its Applications, vol. 137, p. 589. Springer, Cham, Switzerland (2018)

work page 2018
[2]

Cambridge University Press, Cambridge, United Kingdom (2004)

Boyd, S.P., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge, United Kingdom (2004)

work page 2004
[3]

SIAM, ??? (1994)

Nesterov, Y., Nemirovskii, A.: Interior-Point Polynomial Algorithms in Convex Programming. SIAM, ??? (1994). https://doi.org/10.1137/1.9781611970791

doi:10.1137/1.9781611970791 1994
[4]

Journal of Machine Learning Research 16(1), 371–416 (2015) 10

Tran-Dinh, Q., Kyrillidis, A., Cevher, V.: Composite self-concordant minimiza- tion. Journal of Machine Learning Research 16(1), 371–416 (2015) 10

work page 2015
[5]

Mathematical Methods of Operations Research 85, 19– 41 (2017) https://doi.org/10.1007/s00186-016-0551-3

Li, J., Andersen, M.S., Vandenberghe, L.: Inexact proximal newton methods for self-concordant functions. Mathematical Methods of Operations Research 85, 19– 41 (2017) https://doi.org/10.1007/s00186-016-0551-3

work page doi:10.1007/s00186-016-0551-3 2017
[6]

SIAM Journal on Optimization 27(1), 205–245 (2017) https://doi.org/10.1137/15M101025X

Pilanci, M., Wainwright, M.J.: Newton sketch: A near linear-time optimization algorithm with linear-quadratic convergence. SIAM Journal on Optimization 27(1), 205–245 (2017) https://doi.org/10.1137/15M101025X

work page doi:10.1137/15m101025x 2017
[7]

arXiv preprint arXiv:2305.08742 (2023)

Tsipinakis, N., Tigkas, P., Parpas, P.: A multilevel low-rank newton method with super-linear convergence rate and its application to non-convex problems. arXiv preprint arXiv:2305.08742 (2023)

work page arXiv 2023

Show all 13 references

[8]

Journal of Optimization Theory and Applications 203(3), 2509–2559 (2024) https://doi.org/10.1007/s10957-024-02378-7

Tsipinakis, N., Parpas, P.: A multilevel method for self-concordant minimiza- tion. Journal of Optimization Theory and Applications 203(3), 2509–2559 (2024) https://doi.org/10.1007/s10957-024-02378-7

2024 doi
[9]

Optimization Methods and Software 34(1), 194–217 (2019) https://doi.org/10.1080/10556788.2018.1493086

Gao, W., Goldfarb, D.: Quasi-newton methods: Superlinear convergence without line searches for self-concordant functions. Optimization Methods and Software 34(1), 194–217 (2019) https://doi.org/10.1080/10556788.2018.1493086

2019
[10]

arXiv preprint arXiv:2308.14742 (2023)

Doikov, N.: Minimizing quasi-self-concordant functions by gradient regularization of newton method. arXiv preprint arXiv:2308.14742 (2023)

2023 arXiv
[11]

Tran-Dinh, Q., Li, Y.-H., Cevher, V.: Composite convex minimization involving self-concordant-like cost functions. In: Modelling, Computation and Optimiza- tion in Information Systems and Management Sciences: Proceedings of the 3rd International Conference on Modelling, Comput...

2015
[12]

Mathematical Programming 178(1), 145–213 (2019) https: //doi.org/10.1007/s10107-018-1327-3

Sun, T., Tran-Dinh, Q.: Generalized self-concordant functions: A recipe for newton-type methods. Mathematical Programming 178(1), 145–213 (2019) https: //doi.org/10.1007/s10107-018-1327-3

2019 doi

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [13]

SIAM Journal on Optimization 31(1), 785–811 (2021) https: //doi.org/10.1137/20M1320651 11

Rodomanov, A., Nesterov, Y.: Greedy quasi-newton methods with explicit super- linear convergence. SIAM Journal on Optimization 31(1), 785–811 (2021) https: //doi.org/10.1137/20M1320651 11

work page doi:10.1137/20m1320651 2021

[2] [1]

Springer Optimization and Its Applications, vol

Nesterov, Y.: Lectures on Convex Optimization, 2nd edn. Springer Optimization and Its Applications, vol. 137, p. 589. Springer, Cham, Switzerland (2018)

work page 2018

[3] [2]

Cambridge University Press, Cambridge, United Kingdom (2004)

Boyd, S.P., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge, United Kingdom (2004)

work page 2004

[4] [3]

SIAM, ??? (1994)

Nesterov, Y., Nemirovskii, A.: Interior-Point Polynomial Algorithms in Convex Programming. SIAM, ??? (1994). https://doi.org/10.1137/1.9781611970791

doi:10.1137/1.9781611970791 1994

[5] [4]

Journal of Machine Learning Research 16(1), 371–416 (2015) 10

Tran-Dinh, Q., Kyrillidis, A., Cevher, V.: Composite self-concordant minimiza- tion. Journal of Machine Learning Research 16(1), 371–416 (2015) 10

work page 2015

[6] [5]

Mathematical Methods of Operations Research 85, 19– 41 (2017) https://doi.org/10.1007/s00186-016-0551-3

Li, J., Andersen, M.S., Vandenberghe, L.: Inexact proximal newton methods for self-concordant functions. Mathematical Methods of Operations Research 85, 19– 41 (2017) https://doi.org/10.1007/s00186-016-0551-3

work page doi:10.1007/s00186-016-0551-3 2017

[7] [6]

SIAM Journal on Optimization 27(1), 205–245 (2017) https://doi.org/10.1137/15M101025X

Pilanci, M., Wainwright, M.J.: Newton sketch: A near linear-time optimization algorithm with linear-quadratic convergence. SIAM Journal on Optimization 27(1), 205–245 (2017) https://doi.org/10.1137/15M101025X

work page doi:10.1137/15m101025x 2017

[8] [7]

arXiv preprint arXiv:2305.08742 (2023)

Tsipinakis, N., Tigkas, P., Parpas, P.: A multilevel low-rank newton method with super-linear convergence rate and its application to non-convex problems. arXiv preprint arXiv:2305.08742 (2023)

work page arXiv 2023