2017/05/25 by Nan Ye, Peter L. Bartlett, Ye, Nan +1
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1705.09396
openalex publication_date 2017/05/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider two greedy algorithms for minimizing a convex function in a bounded convex set: an algorithm by Jones [1992] and the Frank-Wolfe (FW) algorithm. We first consider approximate versions of these algorithms. For smooth convex functions, we give sufficient conditions for convergence, a unified analysis for the well-known convergence rate of O(1/k) together with a result showing that this rate is the best obtainable from the proof technique, and an equivalence result for the two algorithms. We also consider approximate stochastic greedy algorithms for minimizing expectations. We show that replacing the full gradient by a single stochastic gradient can fail even on smooth convex functions. We give a convergent approximate stochastic Jones algorithm and a convergent approximate stochastic FW algorithm for smooth convex functions. In addition, we give a convergent approximate stochastic FW algorithm for nonsmooth convex functions. Convergence rates for these algorithms are given and proved.