1.3k citations · 3.8k across the 222 of their papers we have counts for
51 papers · 1 filter
Constrained Stochastic Spectral Preconditioning Converges for Nonconvex Objectives
Konstantinos Oikonomidis, Jan Quan, Kimon Antonakopoulos +3
In this work, we develop proximal preconditioned gradient methods with a focus on spectral gradient methods providing a proximal extension to the Muon and Scion optimizers. We intr…
Learning to Remove Cuts in Integer Linear Programming
Pol Puigdemont, Stratis Skoulakis, Grigorios Chrysos +1
Cutting plane methods are a fundamental approach for solving integer linear programs (ILPs). In each iteration of such methods, additional linear constraints (cuts) are introduced…
Efficient Continual Finite-Sum Minimization
Ioannis Mavrothalassitis, Stratis Skoulakis, Leello Tadesse Dadi +1
Given a sequence of functions with , finite-sum minimization seeks a point minimizing $\sum_{j=1}^n…
Randomized algorithms and PAC bounds for inverse reinforcement learning in continuous spaces
Angeliki Kamoutsi, Peter Schmitt-Förster, Tobias Sutter +2
This work studies discrete-time discounted Markov decision processes with continuous state and action spaces and addresses the inverse problem of inferring a cost function from obs…
Universal Gradient Methods for Stochastic Convex Optimization
Anton Rodomanov, Ali Kavis, Yongtao Wu +2
We develop universal gradient methods for Stochastic Convex Optimization (SCO). Our algorithms automatically adapt not only to the oracle's noise but also to the Hölder smoothness…
Krylov Cubic Regularized Newton: A Subspace Second-Order Method with Dimension-Free Convergence Rate
Ruichen Jiang, Parameswaran Raman, Shoham Sabach +3
Second-order optimization methods, such as cubic regularized Newton methods, are known for their rapid convergence rates; nevertheless, they become impractical in high-dimensional…
Advancing the lower bounds: An accelerated, stochastic, second-order method with optimal adaptation to inexactness
Artem Agafonov, Dmitry Kamzolov, Alexander Gasnikov +4
We present a new accelerated stochastic second-order method that is robust to both gradient and Hessian inexactness, which occurs typically in machine learning. We establish theore…
Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems
Thomas Pethick, Puya Latafat, Panagiotis Patrinos +2
This paper introduces a new extragradient-type algorithm for a class of nonconvex-nonconcave minimax problems. It is well-known that finding a local solution for general minimax pr…
Solving stochastic weak Minty variational inequalities without increasing batch size
Thomas Pethick, Olivier Fercoq, Puya Latafat +2
This paper introduces a family of stochastic extragradient-type algorithms for a class of nonconvex-nonconcave problems characterized by the weak Minty variational inequality (MVI)…
Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods
Kimon Antonakopoulos, Ali Kavis, Volkan Cevher
This work proposes a universal and adaptive second-order method for minimizing second-order smooth, convex functions. Our algorithm achieves convergence when the o…
Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization
Ali Kavis, Stratis Skoulakis, Kimon Antonakopoulos +2
We propose an adaptive variance-reduction method, called AdaSpider, for minimization of -smooth, non-convex functions with a finite-sum structure. In essence, AdaSpider combines…
High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize
Ali Kavis, Kfir Yehuda Levy, Volkan Cevher
In this paper, we propose a new, simplified high probability analysis of AdaGrad for smooth, non-convex problems. More specifically, we focus on a particular accelerated gradient (…
On the Complexity of a Practical Primal-Dual Coordinate Method
Ahmet Alacaoglu, Volkan Cevher, Stephen J. Wright
We prove complexity bounds for the primal-dual algorithm with random extrapolation and coordinate descent (PURE-CD), which has been shown to obtain good practical performance for s…
STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization
Kfir Y. Levy, Ali Kavis, Volkan Cevher
In this work we investigate stochastic non-convex optimization problems where the objective is an expectation over smooth loss functions, and the goal is to find an approximate sta…
A first-order primal-dual method with adaptivity to local smoothness
Maria-Luiza Vladarean, Yura Malitsky, Volkan Cevher
We consider the problem of finding a saddle point for the convex-concave objective , where is a convex function with locally…
Random extrapolation for primal-dual coordinate descent
Ahmet Alacaoglu, Olivier Fercoq, Volkan Cevher
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 me…
On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems
Panayotis Mertikopoulos, Nadav Hallak, Ali Kavis +1
This paper analyzes the trajectories of stochastic gradient descent (SGD) to help understand the algorithm's convergence properties in non-convex problems. We first show that the s…
The limits of min-max optimization algorithms: convergence to spurious non-critical sets
Ya-Ping Hsieh, Panayotis Mertikopoulos, Volkan Cevher
Compared to ordinary function minimization problems, min-max optimization algorithms encounter far greater challenges because of the existence of periodic cycles and similar phenom…
A Newton Frank-Wolfe Method for Constrained Self-Concordant Minimization
Deyi Liu, Volkan Cevher, Quoc Tran-Dinh
We demonstrate how to scalably solve a class of constrained self-concordant minimization problems using linear minimization oracles (LMO) over the constraint set. We prove that the…
Scalable Semidefinite Programming
Alp Yurtsever, Joel A. Tropp, Olivier Fercoq +2
Semidefinite programming (SDP) is a powerful framework from convex optimization that has striking potential for data science applications. This paper develops a provably correct ra…
On the convergence of stochastic primal-dual hybrid gradient
Ahmet Alacaoglu, Olivier Fercoq, Volkan Cevher
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 co…
UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization
Ali Kavis, Kfir Y. Levy, Francis Bach +1
We propose a novel adaptive, accelerated algorithm for the stochastic constrained convex optimization setting. Our method, which is inspired by the Mirror-Prox method, \emph{simult…
A reflected forward-backward splitting method for monotone inclusions involving Lipschitzian operators
Volkan Cevher, Bang Cong Vu
The proximal extrapolated gradient method \cite{Malitsky18a} is an extension of the projected reflected gradient method \cite{Malitsky15}. Both methods were proposed for solving th…
An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints
Mehmet Fatih Sahin, Armin Eftekhari, Ahmet Alacaoglu +2
We propose a practical inexact augmented Lagrangian method (iALM) for nonconvex problems with nonlinear constraints. We characterize the total computational complexity of our metho…