SONIA: A Symmetric Blockwise Truncated Optimization Algorithm
Majid Jahani, MohammadReza Nazari, Rachael Tappenden, Albert Berahas, Martin Takac
Abstract
This work presents a new optimization algorithm for empirical risk minimization. The algorithm bridges the gap between first- and second-order methods by computing a search direction that uses a second-order-type update in one subspace, coupled with a scaled steepest descent step in the orthogonal complement. To this end, partial curvature information is incorporated to help with ill-conditioning, while simultaneously allowing the algorithm to scale to the large problem dimensions often encountered in machine learning applications. Theoretical results are presented to confirm that the algorithm converges to a stationary point in both the strongly convex and nonconvex cases. A stochastic variant of the algorithm is also presented, along with corresponding theoretical guarantees. Numerical results confirm the strengths of the new approach on standard machine learning problems.
BibTeX
@InProceedings{pmlr-v130-jahani21a,
title = { SONIA: A Symmetric Blockwise Truncated Optimization Algorithm },
author = {Jahani, Majid and Nazari, MohammadReza and Tappenden, Rachael and Berahas, Albert and Takac, Martin},
booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics},
pages = {487--495},
year = {2021},
editor = {Banerjee, Arindam and Fukumizu, Kenji},
volume = {130},
series = {Proceedings of Machine Learning Research},
month = {13--15 Apr},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v130/jahani21a/jahani21a.pdf},
url = {https://proceedings.mlr.press/v130/jahani21a.html},
abstract = { This work presents a new optimization algorithm for empirical risk minimization. The algorithm bridges the gap between first- and second-order methods by computing a search direction that uses a second-order-type update in one subspace, coupled with a scaled steepest descent step in the orthogonal complement. To this end, partial curvature information is incorporated to help with ill-conditioning, while simultaneously allowing the algorithm to scale to the large problem dimensions often encountered in machine learning applications. Theoretical results are presented to confirm that the algorithm converges to a stationary point in both the strongly convex and nonconvex cases. A stochastic variant of the algorithm is also presented, along with corresponding theoretical guarantees. Numerical results confirm the strengths of the new approach on standard machine learning problems. }
}