Timezone: »

 
Poster
Optimal and Adaptive Monteiro-Svaiter Acceleration
Yair Carmon · Danielle Hausler · Arun Jambulapati · Yujia Jin · Aaron Sidford

Thu Dec 01 09:00 AM -- 11:00 AM (PST) @ Hall J #815
in Poster Session 5 »
We develop a variant of the Monteiro-Svaiter (MS) acceleration framework that removes the need to solve an expensive implicit equation at every iteration. Consequently, for any $p\ge 2$ we improve the complexity of convex optimization with Lipschitz $p$th derivative by a logarithmic factor, matching a lower bound. We also introduce an MS subproblem solver that requires no knowledge of problem parameters, and implement it as either a second- or first-order method by solving linear systems or applying MinRes, respectively. On logistic regression problems our method outperforms previous accelerated second-order methods, but under-performs Newton's method; simply iterating our first-order adaptive subproblem solver is competitive with L-BFGS.
Keywords: Convex Optimization · momentum · optimal algorithms · Adaptive Methods · Oracle complexity · second-order methods · proximal points · conjugate residuals · Newton's method · parameter-free methods · Monteiro-Svaiter acceleration · optimization theory · cubic regularization

Author Information

Yair Carmon (Tel Aviv University)
Danielle Hausler (Tel Aviv University)
Arun Jambulapati (Stanford University)
Yujia Jin (Stanford University)
Aaron Sidford (Stanford)

More from the Same Authors