Exploiting Negative Curvature in Conjunction with Adaptive Sampling: Theoretical Results and a Practical Algorithm
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910699890933760 |
|---|---|
| author | Berahas, Albert S. Bollapragada, Raghu Dong, Wanping |
| author_facet | Berahas, Albert S. Bollapragada, Raghu Dong, Wanping |
| contents | In this paper, we propose algorithms that exploit negative curvature for solving noisy nonlinear nonconvex unconstrained optimization problems. We consider both deterministic and stochastic inexact settings, and develop two-step algorithms that combine directions of negative curvature and descent directions to update the iterates. Under reasonable assumptions, we prove second-order convergence results and derive complexity guarantees for both settings. To tackle large-scale problems, we develop a practical variant that utilizes the conjugate gradient method with negative curvature detection and early stopping to compute a step, a simple adaptive step size scheme, and a strategy for selecting the sample sizes of the gradient and Hessian approximations as the optimization progresses. Numerical results on two machine learning problems showcase the efficacy and efficiency of the practical method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_10378 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Exploiting Negative Curvature in Conjunction with Adaptive Sampling: Theoretical Results and a Practical Algorithm Berahas, Albert S. Bollapragada, Raghu Dong, Wanping Optimization and Control In this paper, we propose algorithms that exploit negative curvature for solving noisy nonlinear nonconvex unconstrained optimization problems. We consider both deterministic and stochastic inexact settings, and develop two-step algorithms that combine directions of negative curvature and descent directions to update the iterates. Under reasonable assumptions, we prove second-order convergence results and derive complexity guarantees for both settings. To tackle large-scale problems, we develop a practical variant that utilizes the conjugate gradient method with negative curvature detection and early stopping to compute a step, a simple adaptive step size scheme, and a strategy for selecting the sample sizes of the gradient and Hessian approximations as the optimization progresses. Numerical results on two machine learning problems showcase the efficacy and efficiency of the practical method. |
| title | Exploiting Negative Curvature in Conjunction with Adaptive Sampling: Theoretical Results and a Practical Algorithm |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2411.10378 |