Towards Gradient Free and Projection Free Stochastic Optimization

2018/10/08 by Anit Kumar Sahu, Manzil Zaheer, Sahu, Anit Kumar +3 · 3 citations
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #cs.LG #math.OC

paper · pdf · doi:10.48550/arxiv.1810.03233

To appear in Proceedings of AISTATS 2019

arxiv created 2019/02/18 · arxiv updated 2019/02/20

Abstract

This paper focuses on the problem of constrained stochastic optimization. A zeroth order Frank-Wolfe algorithm is proposed, which in addition to the projection-free nature of the vanilla Frank-Wolfe algorithm makes it gradient free. Under convexity and smoothness assumption, we show that the proposed algorithm converges to the optimal objective function at a rate O(1/T^1/3), where T denotes the iteration count. In particular, the primal sub-optimality gap is shown to have a dimension dependence of O(d^1/3), which is the best known dimension dependence among all zeroth order optimization algorithms with one directional derivative per iteration. For non-convex functions, we obtain the Frank-Wolfe gap to be O(d^1/3T^-1/4). Experiments on black-box optimization setups demonstrate the efficacy of the proposed algorithm.

Cited by

• On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization
• Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations
• Leveraging Coordinate Momentum in SignSGD and Muon: Memory-Optimized Zero-Order

Related

• Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Points
• Zero-Order Stochastic Conditional Gradient Sliding Method for Non-smooth Convex Optimization
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization
• Scalable Projection-Free Optimization
• A Dimension-Insensitive Algorithm for Stochastic Zeroth-Order Optimization