Efficient Projection-Free Online Convex Optimization with Membership Oracle

In constrained convex optimization, existing methods based on the ellipsoid cutting plane method do not scale well with the dimension of the ambient. Alternative approaches such as Projected Gradient Descent only provide a benefit for simple convex sets such as Euclidean balls, where projections can be performed efficiently. For other sets, the cost of projections can be too high. To circumvent these issues, alternative based on the famous Frank-Wolfe algorithm have been studied and used. methods use a Linear Optimization Oracle at each iteration instead of projections; the former can often be performed efficiently. Such have also been extended to the online and stochastic optimization. However, the Frank-Wolfe algorithm and its variants do not achieve optimal performance, in terms of regret or rate, for general convex sets. is more, the Linear Optimization Oracle they use can still be expensive in some cases. In this paper, we move away from-Wolfe style algorithms and present a new reduction that turns any A defined on a Euclidean ball (where projections are cheap) to an on a constrained set C contained within the ball, without sacrificing performance of the original algorithm A by much. Our reduction requires O(T T) calls to a Membership Oracle on C after T rounds, and no linear on C is needed. Using our reduction, we recover optimal regret [resp. rates], in terms of the number of iterations, in online [resp.] convex optimization. Our guarantees are also useful in the offline optimization setting when the dimension of the ambient space is large.