This paper considers a generic convex minimization template with affine constraints over a compact domain, which covers key semidefinite programming applications. The existing conditional gradient methods either do not apply to our template or are too slow in practice. To this end, we propose a new conditional gradient method, based on a unified treatment of smoothing and augmented Lagrangian frameworks. The proposed method maintains favorable properties of the classical conditional gradient method, such as cheap linear minimization oracle calls and sparse representation of the decision variable. We prove O(1/\sqrt{k}) convergence rate of our method in the objective residual and the feasibility gap. This rate is essentially the same as the state of the art CG-type methods for our problem template, but the proposed method is arguably superior in practice compared to existing methods in various applications.
Author Information
Alp Yurtsever (EPFL)
Olivier Fercoq (Télécom ParisTech, Université Paris-Saclay)
Volkan Cevher (EPFL)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Poster: A Conditional-Gradient-Based Augmented Lagrangian Framework »
Tue Jun 11th 06:30 -- 09:00 PM Room Pacific Ballroom
More from the Same Authors
-
2019 Poster: Almost surely constrained convex optimization »
Olivier Fercoq · Ahmet Alacaoglu · Ion Necoara · Volkan Cevher -
2019 Poster: Finding Mixed Nash Equilibria of Generative Adversarial Networks »
Ya-Ping Hsieh · Chen Liu · Volkan Cevher -
2019 Poster: Efficient learning of smooth probability functions from Bernoulli tests with guarantees »
Paul Rolland · Ali Kavis · Alexander Niklaus Immer · Adish Singla · Volkan Cevher -
2019 Oral: Finding Mixed Nash Equilibria of Generative Adversarial Networks »
Ya-Ping Hsieh · Chen Liu · Volkan Cevher -
2019 Oral: Efficient learning of smooth probability functions from Bernoulli tests with guarantees »
Paul Rolland · Ali Kavis · Alexander Niklaus Immer · Adish Singla · Volkan Cevher -
2019 Oral: Almost surely constrained convex optimization »
Olivier Fercoq · Ahmet Alacaoglu · Ion Necoara · Volkan Cevher -
2019 Poster: Safe Grid Search with Optimal Complexity »
Eugene Ndiaye · Tam Le · Olivier Fercoq · Joseph Salmon · Ichiro Takeuchi -
2019 Poster: On Certifying Non-Uniform Bounds against Adversarial Attacks »
Chen Liu · Ryota Tomioka · Volkan Cevher -
2019 Poster: Conditional Gradient Methods via Stochastic Path-Integrated Differential Estimator »
Alp Yurtsever · Suvrit Sra · Volkan Cevher -
2019 Oral: Conditional Gradient Methods via Stochastic Path-Integrated Differential Estimator »
Alp Yurtsever · Suvrit Sra · Volkan Cevher -
2019 Oral: Safe Grid Search with Optimal Complexity »
Eugene Ndiaye · Tam Le · Olivier Fercoq · Joseph Salmon · Ichiro Takeuchi -
2019 Oral: On Certifying Non-Uniform Bounds against Adversarial Attacks »
Chen Liu · Ryota Tomioka · Volkan Cevher -
2018 Poster: A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming »
Alp Yurtsever · Olivier Fercoq · Francesco Locatello · Volkan Cevher -
2018 Oral: A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming »
Alp Yurtsever · Olivier Fercoq · Francesco Locatello · Volkan Cevher -
2018 Poster: Let’s be Honest: An Optimal No-Regret Framework for Zero-Sum Games »
Ehsan Asadi Kangarshahi · Ya-Ping Hsieh · Mehmet Fatih Sahin · Volkan Cevher -
2018 Poster: Optimal Distributed Learning with Multi-pass Stochastic Gradient Methods »
Junhong Lin · Volkan Cevher -
2018 Oral: Let’s be Honest: An Optimal No-Regret Framework for Zero-Sum Games »
Ehsan Asadi Kangarshahi · Ya-Ping Hsieh · Mehmet Fatih Sahin · Volkan Cevher -
2018 Oral: Optimal Distributed Learning with Multi-pass Stochastic Gradient Methods »
Junhong Lin · Volkan Cevher -
2018 Poster: Optimal Rates of Sketched-regularized Algorithms for Least-Squares Regression over Hilbert Spaces »
Junhong Lin · Volkan Cevher -
2018 Oral: Optimal Rates of Sketched-regularized Algorithms for Least-Squares Regression over Hilbert Spaces »
Junhong Lin · Volkan Cevher -
2017 Poster: Robust Submodular Maximization: A Non-Uniform Partitioning Approach »
Ilija Bogunovic · Slobodan Mitrovic · Jonathan Scarlett · Volkan Cevher -
2017 Talk: Robust Submodular Maximization: A Non-Uniform Partitioning Approach »
Ilija Bogunovic · Slobodan Mitrovic · Jonathan Scarlett · Volkan Cevher
