2018/05/20 by Yan Li, Li, Yan, Chao Qu +3
Computer Science · Engineering · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1805.07844
openalex publication_date 2018/05/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Frank-Wolfe algorithm (FW) and its variants have gained a surge of interests in machine learning community due to its projection-free property. Recently people have reduced the gradient evaluation complexity of FW algorithm to log(\frac1ε) for the smooth and strongly convex objective. This complexity result is especially significant in learning problem, as the overwhelming data size makes a single evluation of gradient computational expensive. However, in high-dimensional statistical estimation problems, the objective is typically not strongly convex, and sometimes even non-convex. In this paper, we extend the state-of-the-art FW type algorithms for the large-scale, high-dimensional estimation problem. We show that as long as the objective satisfies \em restricted strong convexity, and we are not optimizing over statistical limit of the model, the log(\frac1ε) gradient evaluation complexity could still be attained.