SONIA: A Symmetric Blockwise Truncated Optimization Algorithm

Majid Jahani, MohammadReza Nazari, Rachael Tappenden, Albert Berahas, Martin Takac
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:487-495, 2021.

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.

Cite this Paper

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. } }
Endnote
%0 Conference Paper %T SONIA: A Symmetric Blockwise Truncated Optimization Algorithm %A Majid Jahani %A MohammadReza Nazari %A Rachael Tappenden %A Albert Berahas %A Martin Takac %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-jahani21a %I PMLR %P 487--495 %U https://proceedings.mlr.press/v130/jahani21a.html %V 130 %X 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.
APA
Jahani, M., Nazari, M., Tappenden, R., Berahas, A. & Takac, M.. (2021). SONIA: A Symmetric Blockwise Truncated Optimization Algorithm . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:487-495 Available from https://proceedings.mlr.press/v130/jahani21a.html.

Related Material