Publication
On The Convergence Of Stochastic Primal-Dual Hybrid Gradient
Publications associées (44)
Integrating advanced discrete choice models in mixed integer linear optimization
Michel Bierlaire, Bernard Gendron
In many transportation systems, a mismatch between the associated design and planning decisions and the demand is typically encountered. A tailored system is not only appealing to operators, which could have a better knowledge of their operational costs, b ...
PERGAMON-ELSEVIER SCIENCE LTD2021Fast Projection Onto Convex Smooth Constraints
Maryam Kamgarpour, Andreas Krause, Ilnura Usmanova
The Euclidean projection onto a convex set is an important problem that arises in numerous constrained optimization tasks. Unfortunately, in many cases, computing projections is computationally demanding. In this work, we focus on projection problems where ...
PMLR2021Decentralized Proximal Gradient Algorithms With Linear Convergence Rates
Ali H. Sayed, Kun Yuan, Sulaiman A S A E Alghunaim
This article studies a class of nonsmooth decentralized multiagent optimization problems where the agents aim at minimizing a sum of local strongly-convex smooth components plus a common nonsmooth term. We propose a general primal-dual algorithmic framewor ...
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2021Forward-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 ...
2021Random 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 ...
2020A Multi-Agent Primal-Dual Strategy for Composite Optimization over Distributed Features
Ali H. Sayed, Sulaiman A S A E Alghunaim, Ming Yan
This work studies multi-agent sharing optimization problems with the objective function being the sum of smooth local functions plus a convex (possibly non-smooth) function coupling all agents. This scenario arises in many machine learning and engineering ...
IEEE2020Convergence without Convexity: Sampling, Optimization, and Games
Many important problems in contemporary machine learning involve solving highly non- convex problems in sampling, optimization, or games. The absence of convexity poses significant challenges to convergence analysis of most training algorithms, and in some ...
EPFL2020Finding Second-Order Stationary Points in Constrained Minimization: A Feasible Direction Approach
This paper introduces a method for computing points satisfying the second-order necessary optimality conditions for nonconvex minimization problems subject to a closed and convex constraint set. The method comprises two independent steps corresponding to t ...
SPRINGER/PLENUM PUBLISHERS2020Adaptive Gradient Descent without Descent
We present a strikingly simple proof that two rules are sufficient to automate gradient descent: 1) don’t increase the stepsize too fast and 2) don’t overstep the local curvature. No need for functional values, no line search, no information about the func ...
2020On 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