Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization
arXiv:2107.06534 · doi:10.1109/TSP.2022.3162958
Abstract
This paper considers stochastic convex optimization problems with two sets of constraints: (a) deterministic constraints on the domain of the optimization variable, which are difficult to project onto; and (b) deterministic or stochastic constraints that admit efficient projection. Problems of this form arise frequently in the context of semidefinite programming as well as when various NP-hard problems are solved approximately via semidefinite relaxation. Since projection onto the first set of constraints is difficult, it becomes necessary to explore projection-free algorithms, such as the stochastic Frank-Wolfe (FW) algorithm. On the other hand, the second set of constraints cannot be handled in the same way, and must be incorporated as an indicator function within the objective function, thereby complicating the application of FW methods. Similar problems have been studied before; however, they suffer from slow convergence rates. This work, equipped with momentum based gradient tracking technique, guarantees fast convergence rates on par with the best-known rates for problems without the second set of constraints. Zeroth-order variants of the proposed algorithms are also developed and again improve upon the state-of-the-art rate results. We further propose the novel trimmed FW variants that enjoy the same convergence rates as their classical counterparts, but are empirically shown to require significantly fewer calls to the linear minimization oracle speeding up the overall algorithm. The efficacy of the proposed algorithms is tested on relevant applications of sparse matrix estimation, clustering via semidefinite relaxation, and uniform sparsest cut problem.
References in corpus (22)
- ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
- Closest Star Seen Orbiting the Supermassive Black Hole at the Centre of the Milky Way
- A direct formulation for sparse PCA using semidefinite programming
- Estimation of Simultaneously Sparse and Low Rank Matrices
- Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization
- Variance-Reduced and Projection-Free Stochastic Optimization
- Stability and Performance Limits of Adaptive Primal-Dual Networks
- Hierarchical Clustering with Structural Constraints
- Random Multi-Constraint Projection: Stochastic Gradient Methods for Convex Optimization with Many Constraints
- Conditional Accelerated Lazy Stochastic Gradient Descent
- Scalable Semidefinite Relaxation for Maximum A Posterior Estimation
- Conservative Stochastic Optimization with Expectation Constraints
- Towards Gradient Free and Projection Free Stochastic Optimization
- Projection-Free Optimization on Uniformly Convex Sets
- A Conditional Gradient-Based Augmented Lagrangian Framework
- Almost surely constrained convex optimization
- Stochastic Frank-Wolfe for Composite Convex Minimization
- One Sample Stochastic Frank-Wolfe
- Accelerated Stochastic Gradient-free and Projection-free Methods
- Complexity Issues and Randomization Strategies in Frank-Wolfe Algorithms for Machine Learning
- Conditional gradient methods for stochastically constrained convex minimization
- Frank-Wolfe with Subsampling Oracle