Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.22357 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912531851771904 |
|---|---|
| author | Liu, Yu Peng, Weibin Wang, Tianyu Yu, Jiajia |
| author_facet | Liu, Yu Peng, Weibin Wang, Tianyu Yu, Jiajia |
| contents | This paper studies stochastic minimization of a finite-sum loss $ F (\mathbf{x}) = \frac{1}{N} \sum_{ξ=1}^N f(\mathbf{x};ξ) $. In many real-world scenarios, the Hessian matrix of such objectives exhibits a low-rank structure on a batch of data. At the same time, zeroth-order optimization has gained prominence in important applications such as fine-tuning large language models. Drawing on these observations, we propose a novel stochastic zeroth-order cubic Newton method that leverages the low-rank Hessian structure via a matrix recovery-based estimation technique. Our method circumvents restrictive incoherence assumptions, enabling accurate Hessian approximation through finite-difference queries. Theoretically, we establish that for most real-world problems in $\mathbb{R}^n$, $\mathcal{O}\left(\frac{n}{η^{\frac{7}{2}}}\right)+\widetilde{\mathcal{O}}\left(\frac{n^2 }{η^{\frac{5}{2}}}\right)$ function evaluations suffice to attain a second-order $η$-stationary point with high probability. This represents a significant improvement in dimensional dependence over existing methods. This improvement is mostly due to a new Hessian estimator that achieves superior sample complexity; This new Hessian estimation method might be of separate interest. Numerical experiments on matrix recovery and machine learning tasks validate the efficacy and scalability of our approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_22357 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Zeroth-order Stochastic Cubic Newton Method Revisited Liu, Yu Peng, Weibin Wang, Tianyu Yu, Jiajia Optimization and Control This paper studies stochastic minimization of a finite-sum loss $ F (\mathbf{x}) = \frac{1}{N} \sum_{ξ=1}^N f(\mathbf{x};ξ) $. In many real-world scenarios, the Hessian matrix of such objectives exhibits a low-rank structure on a batch of data. At the same time, zeroth-order optimization has gained prominence in important applications such as fine-tuning large language models. Drawing on these observations, we propose a novel stochastic zeroth-order cubic Newton method that leverages the low-rank Hessian structure via a matrix recovery-based estimation technique. Our method circumvents restrictive incoherence assumptions, enabling accurate Hessian approximation through finite-difference queries. Theoretically, we establish that for most real-world problems in $\mathbb{R}^n$, $\mathcal{O}\left(\frac{n}{η^{\frac{7}{2}}}\right)+\widetilde{\mathcal{O}}\left(\frac{n^2 }{η^{\frac{5}{2}}}\right)$ function evaluations suffice to attain a second-order $η$-stationary point with high probability. This represents a significant improvement in dimensional dependence over existing methods. This improvement is mostly due to a new Hessian estimator that achieves superior sample complexity; This new Hessian estimation method might be of separate interest. Numerical experiments on matrix recovery and machine learning tasks validate the efficacy and scalability of our approach. |
| title | Zeroth-order Stochastic Cubic Newton Method Revisited |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2410.22357 |