## Abstract

In this paper, we consider an unconstrained optimization model where the objective is a sum of a large number of possibly nonconvex functions, though overall the objective is assumed to be smooth and convex. Our bid to solving such model uses the framework of cubic regularization of Newton's method. As well known, the crux in cubic regularization is its utilization of the Hessian information, which may be computationally expensive for large-scale problems. To tackle this, we resort to approximating the Hessian matrix via subsampling. In particular, we propose to compute an approximated Hessian matrix by either uniformly or non-uniformly sub-sampling the components of the objective. Based upon such sampling strategy, we develop accelerated adaptive cubic regularization approaches and provide theoretical guarantees on global iteration complexity of O(ϵ-1/3) with high probability, which matches that of the original accelerated cubic regularization methods Jiang et al. (2020) using the full Hessian information. Interestingly, we also show that in the worst case scenario our algorithm still achieves an O(ϵ-5/6 log(ϵ-1)) iteration complexity bound. The proof techniques are new to our knowledge and can be of independent interets. Experimental results on the regularized logistic regression problems demonstrate a clear effect of acceleration on several real data sets.

Original language | English (US) |
---|---|

Journal | Journal of Machine Learning Research |

Volume | 23 |

State | Published - 2022 |

Externally published | Yes |

### Bibliographical note

Funding Information:Xi Chen and Bo Jiang are co-corresponding authors. We would like to thank the three anonymous referees for their insightful comments. Bo Jiang’s research is supported by the National Natural Science Foundation of China (Grants 72171141, 72150001 and 11831002), and Program for Innovative Research Team of Shanghai University of Finance and Economics.

Publisher Copyright:

© 2022 Xi Chen and Bo Jiang and Tianyi Lin and Shuzhong Zhang.

## Keywords

- Newton's method
- Sum of nonconvex functions
- acceleration
- cubic regularization
- iteration complexity
- parameter-free adaptive algorithm
- random sampling