Publications de Alp Yurtsever | EPFL Graph Search

Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization

Volkan Cevher, Alp Yurtsever, Maria-Luiza Vladarean

We propose a stochastic conditional gradient method (CGM) for minimizing convex finitesum objectives formed as a sum of smooth and non-smooth terms. Existing CGM variants for this template either suffer from slow convergence rates, or require carefully inc ...

2022

An Optimal-Storage Approach to Semidefinite Programming Using Approximate Complementarity

Volkan Cevher, Alp Yurtsever

This paper develops a new storage-optimal algorithm that provably solves almost all semidefinite programs (SDPs). This method is particularly effective for weakly constrained SDPs under appropriate regularity conditions. The key idea is to formulate an app ...

2021

Scalable Semidefinite Programming

Volkan Cevher, Alp Yurtsever

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 an ...

2021

Scalable Convex Optimization Methods for Semidefinite Programming

Alp Yurtsever

With the ever-growing data sizes along with the increasing complexity of the modern problem formulations, contemporary applications in science and engineering impose heavy computational and storage burdens on the optimization algorithms. As a result, there ...

EPFL2019

Streaming Low-Rank Matrix Approximation With An Application To Scientific Simulation

Volkan Cevher, Alp Yurtsever

This paper argues that randomized linear sketching is a natural tool for on-the-fly compression of data matrices that arise from large-scale scientific simulations and data collection. The technical contribution consists in a new algorithm for constructing ...

2019

A Conditional Gradient-Based Augmented Lagrangian Framework

Volkan Cevher, Alp Yurtsever

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 ...

2019

Stochastic Frank-Wolfe for Composite Convex Minimization

Volkan Cevher, Alp Yurtsever

A broad class of convex optimization problems can be formulated as a semidefinite program (SDP), minimization of a convex function over the positive-semidefinite cone subject to some affine constraints. The majority of classical SDP solvers are designed fo ...

2019

Conditional Gradient Methods via Stochastic Path-Integrated Differential Estimator

Volkan Cevher, Alp Yurtsever

We propose a class of novel 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 ...

2019

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

Volkan Cevher, Alp Yurtsever

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 O(1/sqrt(k)) convergenc ...

ICML2018

Online Adaptive Methods, Universality and Acceleration

Volkan Cevher, Alp Yurtsever

We present a novel method for convex unconstrained optimization that, without any modifications, ensures: (i) accelerated convergence rate for smooth objectives, (ii) standard convergence rate in the general (non-smooth) setting, and (iii) standard converg ...

2018

Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data

Volkan Cevher, Alp Yurtsever

Several important applications, such as streaming PCA and semidefinite programming, involve a large-scale positive-semidefinite (psd) matrix that is presented as a sequence of linear updates. Because of storage limitations, it may only be possible to retai ...

2017

Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage

Volkan Cevher, Alp Yurtsever

This paper considers a fundamental class of convex matrix optimization problems with low-rank solutions. We show it is possible to solve these problem using far less memory than the natural size of the decision variable when the problem data has a concise ...

2017

Practical Sketching Algorithms For Low-Rank Matrix Approximation

Volkan Cevher, Alp Yurtsever

This paper describes a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image, or sketch, of the matrix. These methods can preserve structural properties of the input matrix, such as positive-semidefinite ...

Society for Industrial and Applied Mathematics2017

Stochastic Three-Composite Convex Minimization

Volkan Cevher, Alp Yurtsever, Cong Bang Vu

We propose a stochastic optimization method for the minimization of the sum of three convex functions, one of which has Lipschitz continuous gradient as well as restricted strong convexity. Our approach is most suitable in the setting where it is computati ...

2016

Frank-Wolfe Works for Non-Lipschitz Continuous Gradient Objectives: Scalable Poisson Phase Retrieval

Volkan Cevher, Marwa El Halabi, Yen-Huan Li, Quoc Tran Dinh, Alp Yurtsever, Ya-Ping Hsieh, Gergely Odor

We study a phase retrieval problem in the Poisson noise model. Motivated by the PhaseLift approach, we approximate the maximum-likelihood estimator by solving a convex program with a nuclear norm constraint. While the Frank-Wolfe algorithm, together with t ...

Ieee2016

Scalable Convex Methods for Phase Retrieval

Volkan Cevher, Alp Yurtsever, Ya-Ping Hsieh

This paper describes scalable convex optimization methods for phase retrieval. The main characteristics of these methods are the cheap per-iteration complexity and the low-memory footprint. With a variant of the original PhaseLift formulation, we first ill ...

2015

A Universal Primal-Dual Convex Optimization Framework

Volkan Cevher, Quoc Tran Dinh, Alp Yurtsever

We propose a new primal-dual algorithmic framework for a prototypical con- strained convex optimization template. The algorithmic instances of our frame- work are universal since they can automatically adapt to the unknown Ho ̈lder con- tinuity properties ...

2015