Publications de Ahmet Alacaoglu

On The Convergence Of Stochastic Primal-Dual Hybrid Gradient

In this paper, we analyze the recently proposed stochastic primal-dual hybrid gradient (SPDHG) algorithm and provide new theoretical results. In particular, we prove almost sure convergence of the iterates to a solution with convexity and linear convergenc ...

SIAM PUBLICATIONS2022

Convergence of adaptive algorithms for constrained weakly convex optimization

Volkan Cevher, Ahmet Alacaoglu, Yurii Malitskyi

We analyze the adaptive first order algorithm AMSGrad, for solving a constrained stochastic optimization problem with a weakly convex objective. We prove the

\tilde O(t^{-1/2})

rate of convergence for the squared norm of the gradient of Moreau envelope, ...

2021

Adaptation in Stochastic Algorithms: From Nonsmooth Optimization to Min-Max Problems and Beyond

Ahmet Alacaoglu

Stochastic gradient descent (SGD) and randomized coordinate descent (RCD) are two of the workhorses for training modern automated decision systems. Intriguingly, convergence properties of these methods are not well-established as we move away from the spec ...

EPFL2021

Forward-reflected-backward method with variance reduction

Volkan Cevher, Ahmet Alacaoglu

We propose a variance reduced algorithm for solving monotone variational inequalities. Without assuming strong monotonicity, cocoercivity, or boundedness of the domain, we prove almost sure convergence of the iterates generated by the algorithm to a soluti ...

2021

A new regret analysis for Adam-type algorithms

Volkan Cevher, Ahmet Alacaoglu

In this paper, we focus on a theory-practice gap for Adam and its variants (AMSgrad, AdamNC, etc.). In practice, these algorithms are used with a constant first-order moment parameter 1 (typically between 0:9 and 0:99). In theory, regret guarantees for onl ...

JMLR-JOURNAL MACHINE LEARNING RESEARCH2020

Random extrapolation for primal-dual coordinate descent

Volkan Cevher, Ahmet Alacaoglu

We introduce a randomly extrapolated primal-dual coordinate descent method that adapts to sparsity of the data matrix and the favorable structures of the objective function. Our method updates only a subset of primal and dual variables with sparse data, an ...

JMLR-JOURNAL MACHINE LEARNING RESEARCH2020

Conditional gradient methods for stochastically constrained convex minimization

Volkan Cevher, Maria-Luiza Vladarean, Ya-Ping Hsieh, Ahmet Alacaoglu

We propose two novel conditional gradient-based methods for solving structured stochastic convex optimization problems with a large number of linear constraints. Instances of this template naturally arise from SDP-relaxations of combinatorial problems, whi ...

2020

An adaptive primal-dual framework for nonsmooth convex minimization

Volkan Cevher, Quoc Tran Dinh, Ahmet Alacaoglu

We propose a new self-adaptive and double-loop smoothing algorithm to solve composite, nonsmooth, and constrained convex optimization problems. Our algorithm is based on Nesterov’s smoothing technique via general Bregman distance functions. It self-adaptiv ...

2020

An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints

Armin Eftekhari, Volkan Cevher, Ahmet Alacaoglu, Mehmet Fatih Sahin, Fabian Ricardo Latorre Gomez

We propose a practical inexact augmented Lagrangian method (iALM) for nonconvex problems with nonlinear constraints. We characterize the total computational complexity of our method subject to a verifiable geometric condition, which is closely related to t ...

2019

On the convergence of stochastic primal-dual hybrid gradient

Volkan Cevher, Ahmet Alacaoglu

In this paper, we analyze the recently proposed stochastic primal-dual hybrid gradient (SPDHG) algorithm and provide new theoretical results. In particular, we prove almost sure convergence of the iterates to a solution and linear convergence with standard ...

2019

Almost surely constrained convex optimization

Volkan Cevher, Ahmet Alacaoglu

We propose a stochastic gradient framework for solving stochastic composite convex optimization problems with (possibly) infinite number of linear inclusion constraints that need to be satisfied almost surely. We use smoothing and homotopy techniques to ha ...

2019

Smooth Primal-Dual Coordinate Descent Algorithms for Nonsmooth Convex Optimization

Volkan Cevher, Quoc Tran Dinh, Ahmet Alacaoglu

We propose a new randomized coordinate descent method for a convex optimization template with broad applications. Our analysis relies on a novel combination of four ideas applied to the primal-dual gap function: smoothing, acceleration, homotopy, and coord ...

2017