SONIA: A Symmetric Blockwise Truncated Optimization Algorithm
This work addresses optimization challenges in machine learning by providing a scalable algorithm that improves upon existing methods, though it appears incremental as it builds on known techniques.
The paper tackles empirical risk minimization by introducing SONIA, a symmetric blockwise truncated optimization algorithm that bridges first- and second-order methods, incorporating partial curvature to handle ill-conditioning and scaling to large dimensions. Numerical results confirm its effectiveness on standard machine learning problems, with theoretical convergence guarantees for both strongly convex and nonconvex cases.
This work presents a new 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.