My Oral Presentations
|
[SNSF2020]
SNSF Fellows Conference Virtual, July 2020. "Scalable semidefinite programming" Joint work with: Cevher, V., Fercoq, O., Udell, M. and Tropp, J.A. |
| Abstract: Semidefinite programming (SDP) is a powerful framework from convex optimization that has striking potential for data science applications. This paper develops a provably correct algorithm for solving large SDP problems by economizing on both the storage and the arithmetic costs. Numerical evidence shows that the method is effective for a range of applications, including relaxations of MaxCut, abstract phase retrieval, and quadratic assignment. Running on a laptop, the algorithm can handle SDP instances where the matrix variable has over 10^13 entries. |
|
[ICML2019]
36th International Conference on Machine Learning Long Beach, California, USA, June 2019. "Conditional gradient methods via stochastic path-integrated differential estimator" Joint work with: Sra, S. and Cevher, V. |
| Abstract: We propose a class of variance-reduced stochastic conditional gradient methods. By adopting the recent stochastic path-integrated differential estimator technique (SPIDER) of Fang et. al. (2018) for the classical Frank-Wolfe (FW) method, we introduce SPIDER-FW for finite-sum minimization as well as the more general expectation minimization problems. SPIDER-FW enjoys superior complexity guarantees in the non-convex setting, while matching the best known FW variants in the convex case. We also extend our framework a la conditional gradient sliding (CGS) of Lan & Zhou. (2016), and propose SPIDER-CGS. |
|
[ICML2019]
36th International Conference on Machine Learning Long Beach, California, USA, June 2019. "A conditional-gradient-based augmented Lagrangian framework" Joint work with: Fercoq, O. and Cevher, V. |
| Abstract: 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/√k) convergence rate for 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. |
|
[ITA2019]
Information Theory and Applications Workshop: Graduation Day San Diego, CA, USA, January 2019. "Sketchy decisions: Convex optimization with optimal storage (with applications to semidefinite programming)" Joint work with: Cevher, V., Fercoq, O., Locatello, F., Udell, M. and Tropp, J.A. |
| Abstract: Semidefinite programs (SDP) often have low-rank solutions that can be represented with O(n)-storage, yet SDP algorithms require us to store a matrix decision variable with size (n x n). This observation leads to a question central to my research: Suppose that the solution to an optimization problem has a compact representation. Can we develop storage-optimal algorithms that provably approximate a solution of this problem? We give an affirmative answer to this question, and develop the first storage-optimal convex optimization method for solving SDPs. We present empirical evidence of the scalability of our approach by solving convex optimization problems of trillion dimensions. |
|
[ICML2018]
35th International Conference on Machine Learning Stockholm, Sweden, July 2018. "A conditional gradient framework for composite convex minimization with applications to semidefinite programming" Joint work with: Fercoq, O., Locatello, F. and Cevher, V. |
| 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 $O(1/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. |
|
[ISMP2018]
23rd International Symposium onMathematical Programming Bordeaux, France, July 2018. "A conditional gradient framework for composite convex minimization" Joint work with: Fercoq, O., Locatello, F. and Cevher, V. |
| Abstract: We propose a conditional gradient framework for a composite convex minimization template with broad applications. Our approach combines the notions of smoothing and homotopy under the CGM framework, and provably achieves the optimal convergence rate. We demonstrate that the same rate holds if the linear subproblems are solved approximately with additive or multiplicative error. Specific applications of the framework include the non-smooth minimization, semidefinite programming, minimization with linear inclusion constraints over a compact domain. We provide numerical evidence to demonstrate the scalability benefits of the new framework. |
|
[AISTATS2017]
20th International Conference on Artificial Intelligence and Statistics Fort Lauderdale, Florida, USA, April 2017. "Sketchy decisions: Convex optimization with optimal storage." Joint work with: Tropp, J.A., Udell, M. and Cevher, V. |
| Abstract: This paper concerns a fundamental class of convex matrix optimization problems. It presents the first algorithm that uses optimal storage and provably computes a lowrank approximation of a solution. In particular, when all solutions have low rank, the algorithm converges to a solution. This algorithm, SketchyCGM, modifies a standard convex optimization scheme, the conditional gradient method, to store only a small randomized sketch of the matrix variable. After the optimization terminates, the algorithm extracts a low-rank approximation of the solution from the sketch. In contrast to nonconvex heuristics, the guarantees for SketchyCGM do not rely on statistical models for the problem data. Numerical work demonstrates the benefits of SketchyCGM over heuristics. |
|
[OP17]
SIAM Conference on Optimization Vancouver, British Columbia, Canada, May 2017. "Stochastic forward Douglas-Rachford splitting for monotone inclusions" Joint work with: Vu, B.C. and Cevher, V. |
| Abstract: We propose a stochastic Forward-Douglas-Rachford Splitting framework for finding a zero point of the sum of three maximally monotone operators in real separable Hilbert space, where one of the operators is cocoercive. We characterize the rate of convergence in expectation in the case of strongly monotone operators. We provide guidance on step-size sequences that achieve this rate, even if the strong convexity parameter is unknown. |
|
[OR2017]
15th Swiss Operations Research Days Fribourg, Switzerland, June 2017. "Sketchy decisions: Convex optimization with optimal storage" Joint work with: Tropp, J.A., Udell, M. and Cevher, V. |
| Abstract: This paper concerns a fundamental class of convex matrix optimization problems. It presents the first algorithm that uses optimal storage and provably computes a lowrank approximation of a solution. In particular, when all solutions have low rank, the algorithm converges to a solution. This algorithm, SketchyCGM, modifies a standard convex optimization scheme, the conditional gradient method, to store only a small randomized sketch of the matrix variable. After the optimization terminates, the algorithm extracts a low-rank approximation of the solution from the sketch. In contrast to nonconvex heuristics, the guarantees for SketchyCGM do not rely on statistical models for the problem data. Numerical work demonstrates the benefits of SketchyCGM over heuristics |
|
[SPARS2017]
Signal Processing with Adaptive Sparse Structured Representations Fribourg, Switzerland, June 2017. "Scalable convex methods for low-rank matrix problems" Joint work with: Tran-Dinh, Q., Tropp, J.A., Udell, M. and Cevher, V. |
| Abstract: We describe our new scalable primal-dual convex optimization framework to solve low-rank matrix recovery problems. The main characteristics of our framework is the cheap per-iteration complexity and the low-memory footprint. We demonstrate the flexibility and scalability of our framework by solving matrix completion, quantum tomography and phase retrieval problems. |
|
[EcoCloud2016]
Annual Event Lausanne, Switzerland, May 2016. "A universal primal-dual convex optimization framework" Joint work with: Tran-Dinh, Q. and Cevher, V. |
| Abstract: We propose a new primal-dual algorithmic framework for a prototypical constrained convex optimization template. The algorithmic instances of our framework are universal since they can automatically adapt to the unknown Holder continuity degree and constant within the dual formulation. They are also guaranteed to have optimal convergence rates in the objective residual and the feasibility gap for each Holder smoothness degree. In contrast to existing primaldual algorithms, our framework avoids the proximity operator of the objective function. We instead leverage computationally cheaper, Fenchel-type operators, which are the main workhorses of the generalized conditional gradient (GCG)-type methods. In contrast to the GCG-type methods, our framework does not require the objective function to be differentiable, and can also process additional general linear inclusion constraints, while guarantees the convergence rate on the primal problem. |
|
[ICCOPT2016]
5th International Conference on Continuous Optimization Tokyo, Japan, August 2016. "A universal primal-dual convex optimization framework" Joint work with: Tran-Dinh, Q. and Cevher, V. |
| Abstract: We propose a new primal-dual algorithmic framework for a prototypical constrained convex optimization template. The algorithmic instances of our framework are universal since they can automatically adapt to the unknown Holder continuity degree and constant within the dual formulation. They are also guaranteed to have optimal convergence rates in the objective residual and the feasibility gap for each Holder smoothness degree. In contrast to existing primaldual algorithms, our framework avoids the proximity operator of the objective function. We instead leverage computationally cheaper, Fenchel-type operators, which are the main workhorses of the generalized conditional gradient (GCG)-type methods. In contrast to the GCG-type methods, our framework does not require the objective function to be differentiable, and can also process additional general linear inclusion constraints, while guarantees the convergence rate on the primal problem. |
|
[ISMP2015]
22nd International Symposium onMathematical Programming Pittsburgh, USA, July 2015. "Universal primal-dual proximal-gradient methods" Joint work with: Tran-Dinh, Q. and Cevher, V. |
| Abstract: We propose a primal-dual algorithmic framework for a prototypical constrained convex minimization problem. The new framework aims to trade-off the computational difficulty between the primal and the dual subproblems. We achieve this in our setting by replacing the standard proximal mapping computations with linear minimization oracles in the primal space, which has been the hallmark of the scalable Frank-Wolfe type algorithms. Our analysis extends Nesterov’s universal gradient methods to the primal-dual setting in a nontrivial fashion, and provides optimal convergence guarantees for the objective residual as well as the feasibility gap without having to know the smoothness structures of the problem. |