Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method
- Kiran Thekumparampil ,
- Prateek Jain ,
- Praneeth Netrapalli ,
- Sewoong Oh
Organized by ACM
We consider the classical setting of optimizing a nonsmooth Lipschitz continuous convex function over a convex constraint set, when having access to a (stochastic) first-order oracle (FO) for the function and a projection oracle (PO) for the constraint set. It is well known that to achieve \(\epsilon\)-suboptimality in high-dimensions, \(\Theta ({\epsilon }_{-2}^)\)