A Study on Trust Region Update Rules in Newton Methods for Large-scale Linear Classification

Chih-Yang Hsia, Ya Zhu, Chih-Jen Lin
Proceedings of the Ninth Asian Conference on Machine Learning, PMLR 77:33-48, 2017.

Abstract

The main task in training a linear classifier is to solve an unconstrained minimization problem. To apply an optimization method typically we iteratively find a good direction and then decide a suitable step size. Past developments of extending optimization methods for large-scale linear classification focus on finding the direction, but little attention has been paid on adjusting the step size. In this work, we explain that inappropriate step-size adjustment may lead to serious slow convergence. Among the two major methods for step-size selection, line search and trust region, we focus on investigating the trust region methods. After presenting some detailed analysis, we develop novel and effective techniques to adjust the trust-region size. Experiments indicate that our new settings significantly outperform existing implementations for large-scale linear classification.

Cite this Paper

BibTeX
@InProceedings{pmlr-v77-hsia17a, title = {A Study on Trust Region Update Rules in Newton Methods for Large-scale Linear Classification}, author = {Hsia, Chih-Yang and Zhu, Ya and Lin, Chih-Jen}, booktitle = {Proceedings of the Ninth Asian Conference on Machine Learning}, pages = {33--48}, year = {2017}, editor = {Zhang, Min-Ling and Noh, Yung-Kyun}, volume = {77}, series = {Proceedings of Machine Learning Research}, address = {Yonsei University, Seoul, Republic of Korea}, month = {15--17 Nov}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v77/hsia17a/hsia17a.pdf}, url = {https://proceedings.mlr.press/v77/hsia17a.html}, abstract = {The main task in training a linear classifier is to solve an unconstrained minimization problem. To apply an optimization method typically we iteratively find a good direction and then decide a suitable step size. Past developments of extending optimization methods for large-scale linear classification focus on finding the direction, but little attention has been paid on adjusting the step size. In this work, we explain that inappropriate step-size adjustment may lead to serious slow convergence. Among the two major methods for step-size selection, line search and trust region, we focus on investigating the trust region methods. After presenting some detailed analysis, we develop novel and effective techniques to adjust the trust-region size. Experiments indicate that our new settings significantly outperform existing implementations for large-scale linear classification.} }
Endnote
%0 Conference Paper %T A Study on Trust Region Update Rules in Newton Methods for Large-scale Linear Classification %A Chih-Yang Hsia %A Ya Zhu %A Chih-Jen Lin %B Proceedings of the Ninth Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Min-Ling Zhang %E Yung-Kyun Noh %F pmlr-v77-hsia17a %I PMLR %P 33--48 %U https://proceedings.mlr.press/v77/hsia17a.html %V 77 %X The main task in training a linear classifier is to solve an unconstrained minimization problem. To apply an optimization method typically we iteratively find a good direction and then decide a suitable step size. Past developments of extending optimization methods for large-scale linear classification focus on finding the direction, but little attention has been paid on adjusting the step size. In this work, we explain that inappropriate step-size adjustment may lead to serious slow convergence. Among the two major methods for step-size selection, line search and trust region, we focus on investigating the trust region methods. After presenting some detailed analysis, we develop novel and effective techniques to adjust the trust-region size. Experiments indicate that our new settings significantly outperform existing implementations for large-scale linear classification.
APA
Hsia, C., Zhu, Y. & Lin, C.. (2017). A Study on Trust Region Update Rules in Newton Methods for Large-scale Linear Classification. Proceedings of the Ninth Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 77:33-48 Available from https://proceedings.mlr.press/v77/hsia17a.html.

Related Material