A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming

Abstract

We propose a conditional gradient framework for a composite convex minimization template with broad applications. Our approach combines smoothing and homotopy techniques under the CGM framework, and provably achieves the optimal $\mathcal{O}(1/\sqrt{k})$ convergence rate. We demonstrate that the same rate holds if the linear subproblems are solved approximately with additive or multiplicative error. In contrast with the relevant work, we are able to characterize the convergence when the non-smooth term is an indicator function. Specific applications of our framework include the non-smooth minimization, semidefinite programming, and minimization with linear inclusion constraints over a compact domain. Numerical evidence demonstrates the benefits of our framework.

arXiv commentAppears in Proceedings of the 35th International Conference on Machine Learning (ICML 2018)

Cited by in corpus (10)

• An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints
• Generalized Conditional Gradient with Augmented Lagrangian for Composite Minimization
• An Optimal-Storage Approach to Semidefinite Programming using Approximate Complementarity
• A Conditional Gradient-Based Augmented Lagrangian Framework
• Model Function Based Conditional Gradient Method with Armijo-like Line Search
• Three Operator Splitting with Subgradients, Stochastic Gradients, and Adaptive Learning Rates
• Three Operator Splitting with a Nonconvex Loss Function
• RC Circuits based Distributed Conditional Gradient Method
• One-sided Frank-Wolfe algorithms for saddle problems
• Efficient Low-Rank Semidefinite Programming with Robust Loss Functions