Efficient projection-free online convex optimization using stochastic gradients
摘要
We consider Online Convex Optimization (OCO) problems subject to a compact convex set. An important class of projection-free online methods known as Frank–Wolfe-type (FW-type) methods have attracted considerable attention in the machine learning community, as they eschew the expensive projection operation and only require a simple linear minimization oracle in each round. Recently, the stochastic gradient technique has been integrated in FW-type online methods to circumvent the expensive full gradient computation and further reduce the per-round computational cost. However, these methods generally have high regret bounds due to high variance in gradient estimation. Although adopting a large minibatch in stochastic gradients can reduce the variance, it would in turn increase the per-round computational cost. In this paper, we develop efficient FW-type methods that only need stochastic gradients with small minibatch and achieve nearly optimal regret bounds with low per-round costs. We first explore the similarity between gradients of decision variables in consecutive rounds, and construct a lightweight variance-reduced estimator by utilizing historical gradient information. Based on this estimator, we propose a method named OFWRG for smooth problems in the stochastic setting. We prove that OFWRG achieves a nearly optimal regret bound with the lowest