Scalable Projection-Free Optimization

Abstract

As a projection-free algorithm, Frank-Wolfe (FW) method, also known as conditional gradient, has recently received considerable attention in the machine learning community. In this dissertation, we study several topics on the FW variants for scalable projection-free optimization. We first propose 1-SFW, the first projection-free method that requires only one sample per iteration to update the optimization variable and yet achieves the best known complexity bounds for convex, non-convex, and monotone DR-submodular settings. Then we move forward to the distributed setting, and develop Quantized Frank-Wolfe (QFW), a general communication-efficient distributed FW framework for both convex and non-convex objective functions. We study the performance of QFW in two widely recognized settings: 1) stochastic optimization and 2) finite-sum optimization. Finally, we propose Black-Box Continuous Greedy, a derivative-free and projection-free algorithm, that maximizes a monotone continuous DR-submodular function over a bounded convex body in Euclidean space.

arXiv commentdissertation

References in corpus (36)

• Practical Bayesian Optimization of Machine Learning Algorithms
• Cooperative Game Theory Approaches for Network Partitioning
• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Sparsified SGD with Memory
• An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
• Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms
• Influence Maximization in Continuous Time Diffusion Networks
• Convergence Rate of Frank-Wolfe for Non-Convex Objectives
• Near-Optimally Teaching the Crowd to Classify
• Variance-Reduced and Projection-Free Stochastic Optimization
• Projection-free Online Learning
• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• Stochastic Variance Reduction Methods for Policy Evaluation
• Structured sparsity-inducing norms through submodular functions
• Stochastic Zeroth-order Optimization in High Dimensions
• Online Continuous Submodular Maximization
• How to be Fair and Diverse?
• Parallel and Distributed Block-Coordinate Frank-Wolfe Algorithms
• Gradient Methods for Submodular Maximization
• Escaping Saddle Points in Constrained Optimization
• Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignments
• Deep Frank-Wolfe For Neural Network Optimization
• Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback
• Causal Markov condition for submodular information measures
• Projection-Free Bandit Convex Optimization
• A Distributed Frank-Wolfe Framework for Learning Low-Rank Matrices with the Trace Norm
• Towards Gradient Free and Projection Free Stochastic Optimization
• Constrained Deep Learning using Conditional Gradient and Applications in Computer Vision
• Optimal DR-Submodular Maximization and Applications to Provable Mean Field Inference
• Categorical Feature Compression via Submodular Optimization
• Submodular Variational Inference for Network Reconstruction
• Neural Conditional Gradients