Non-Convex Self-Concordant Functions: Practical Algorithms and Complexity Analysis
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908938208804864 |
|---|---|
| author | Goldfarb, Donald Lai, Lexiao Lin, Tianyi Zhang, Jiayu |
| author_facet | Goldfarb, Donald Lai, Lexiao Lin, Tianyi Zhang, Jiayu |
| contents | We extend the standard notion of self-concordance to non-convex optimization and develop a family of second-order algorithms with global convergence guarantees. In particular, two function classes -- \textit{weakly self-concordant} functions and \textit{$F$-based self-concordant} functions -- generalize the self-concordant framework beyond convexity, without assuming the Lipschitz continuity of the gradient or Hessian. For these function classes, we propose a regularized Newton method and an adaptive regularization method that achieve an $ε$-approximate first-order stationary point in $O(ε^{-2})$ iterations. Equipped with an oracle capable of detecting negative curvature, the adaptive algorithm can further attain convergence to an approximate second-order stationary point. Our experimental results demonstrate that the proposed methods offer superior robustness and computational efficiency compared to cubic regularization and trust-region approaches, underscoring the broad potential of self-concordant regularization for large-scale and neural network optimization problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_15019 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Non-Convex Self-Concordant Functions: Practical Algorithms and Complexity Analysis Goldfarb, Donald Lai, Lexiao Lin, Tianyi Zhang, Jiayu Optimization and Control 90C26, 90C30, 65K05, 49M15 We extend the standard notion of self-concordance to non-convex optimization and develop a family of second-order algorithms with global convergence guarantees. In particular, two function classes -- \textit{weakly self-concordant} functions and \textit{$F$-based self-concordant} functions -- generalize the self-concordant framework beyond convexity, without assuming the Lipschitz continuity of the gradient or Hessian. For these function classes, we propose a regularized Newton method and an adaptive regularization method that achieve an $ε$-approximate first-order stationary point in $O(ε^{-2})$ iterations. Equipped with an oracle capable of detecting negative curvature, the adaptive algorithm can further attain convergence to an approximate second-order stationary point. Our experimental results demonstrate that the proposed methods offer superior robustness and computational efficiency compared to cubic regularization and trust-region approaches, underscoring the broad potential of self-concordant regularization for large-scale and neural network optimization problems. |
| title | Non-Convex Self-Concordant Functions: Practical Algorithms and Complexity Analysis |
| topic | Optimization and Control 90C26, 90C30, 65K05, 49M15 |
| url | https://arxiv.org/abs/2511.15019 |