Timezone: »

 
Poster
Acceleration with a Ball Optimization Oracle
Yair Carmon · Arun Jambulapati · Qijia Jiang · Yujia Jin · Yin Tat Lee · Aaron Sidford · Kevin Tian

Wed Dec 09 09:00 AM -- 11:00 AM (PST) @ Poster Session 3 #1057
in Poster Session 4 »

Consider an oracle which takes a point x and returns the minimizer of a convex function f in an l2 ball of radius r around x. It is straightforward to show that roughly r^{-1}\log(1/epsilon) calls to the oracle suffice to find an \epsilon-approximate minimizer of f in an l2 unit ball. Perhaps surprisingly, this is not optimal: we design an accelerated algorithm which attains an epsilon-approximate minimizer with roughly r^{-2/3} \log(1/epsilon) oracle queries, and give a matching lower bound. Further, we implement ball optimization oracles for functions with a locally stable Hessian using a variant of Newton's method and, in certain cases, stochastic first-order methods. The resulting algorithms apply to a number of problems of practical and theoretical import, improving upon previous results for logistic and linfinity regression and achieving guarantees comparable to the
state-of-the-art for lp regression.

[ Paper ]

Author Information

Yair Carmon (Tel Aviv University)
Arun Jambulapati (Stanford University)
Qijia Jiang (Stanford University)
Yujia Jin (Stanford University)
Yin Tat Lee (UW)
Aaron Sidford (Stanford)
Kevin Tian (Stanford University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors