SONIA: A Symmetric Blockwise Truncated Optimization Algorithm

Majid Jahani · MohammadReza Nazari · Rachael Tappenden · Albert Berahas · Martin Takac

Keywords: [ Algorithms, Optimization and Computation Methods ] [ Convex optimization ]

[ Abstract ]
Tue 13 Apr 2 p.m. PDT — 4 p.m. PDT


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.

Chat is not available.