Efficient Projection-Free Online Methods with Stochastic Recursive Gradient
This work addresses computational bottlenecks for researchers and practitioners in online optimization, though it appears incremental as it builds on existing projection-free methods.
The paper tackled the problem of inefficient projection-free methods in Online Convex Optimization by proposing ORGFW and MORGFW, which achieve optimal regret bounds with low computational costs.
This paper focuses on projection-free methods for solving smooth Online Convex Optimization (OCO) problems. Existing projection-free methods either achieve suboptimal regret bounds or have high per-iteration computational costs. To fill this gap, two efficient projection-free online methods called ORGFW and MORGFW are proposed for solving stochastic and adversarial OCO problems, respectively. By employing a recursive gradient estimator, our methods achieve optimal regret bounds (up to a logarithmic factor) while possessing low per-iteration computational costs. Experimental results demonstrate the efficiency of the proposed methods compared to state-of-the-arts.