Publications related to UNDERGRAD: A Universal Black-Box Optimization Method with Almost Dimension-Free Convergence Rate Guarantees

Enabling Uncertainty Estimation in Iterative Neural Networks

Pascal Fua, Nikita Durasov, Doruk Oner, Minh Hieu Lê

Turning pass-through network architectures into iterative ones, which use their own output as input, is a well-known approach for boosting performance. In this paper, we argue that such architectures offer an additional benefit: The convergence rate of the ...

2024

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Mehmet Fatih Sahin

Non-convex constrained optimization problems have become a powerful framework for modeling a wide range of machine learning problems, with applications in k-means clustering, large- scale semidefinite programs (SDPs), and various other tasks. As the perfor ...

EPFL2023

Universal and adaptive methods for robust stochastic optimization

Ali Kavis

Within the context of contemporary machine learning problems, efficiency of optimization process depends on the properties of the model and the nature of the data available, which poses a significant problem as the complexity of either increases ad infinit ...

EPFL2023

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 with convexity and linear convergenc ...

SIAM PUBLICATIONS2022

Proximal Point Imitation Learning

Volkan Cevher, Luca Viano, Igor Krawczuk, Angeliki Kamoutsi

This work develops new algorithms with rigorous efficiency guarantees for infinite horizon imitation learning (IL) with linear function approximation without restrictive coherence assumptions. We begin with the minimax formulation of the problem and then o ...

2022

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

A first-order primal-dual method with adaptivity to local smoothness

Volkan Cevher, Maria-Luiza Vladarean

We consider the problem of finding a saddle point for the convex-concave objective

\min_x \max_y f(x) + \langle Ax, y\rangle - g^*(y)

, where

f

is a convex function with locally Lipschitz gradient and

g

is convex and possibly non-smooth. We propose an ...

2021

Last iterate convergence of SGD for Least-Squares in the Interpolation regime

Nicolas Henri Bernard Flammarion, Aditya Vardhan Varre, Loucas Pillaud-Vivien

Motivated by the recent successes of neural networks that have the ability to fit the data perfectly \emph{and} generalize well, we study the noiseless model in the fundamental least-squares setup. We assume that an optimum predictor fits perfectly inputs ...

2021

Decentralized 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 INC2021

On Convergence-Diagnostic based Step Sizes for Stochastic Gradient Descent

Nicolas Henri Bernard Flammarion, Scott William Pesme, Aymeric Daphnis Kévin Dieuleveut

Constant step-size Stochastic Gradient Descent exhibits two phases: a transient phase during which iterates make fast progress towards the optimum, followed by a stationary phase during which iterates oscillate around the optimal point. In this paper, we s ...

2020

UNDERGRAD: A Universal Black-Box Optimization Method with Almost Dimension-Free Convergence Rate Guarantees

Graph Chatbot

Chat with Graph Search

Enabling Uncertainty Estimation in Iterative Neural Networks

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Universal and adaptive methods for robust stochastic optimization

On The Convergence Of Stochastic Primal-Dual Hybrid Gradient

Proximal Point Imitation Learning

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

A first-order primal-dual method with adaptivity to local smoothness

Last iterate convergence of SGD for Least-Squares in the Interpolation regime

Decentralized Proximal Gradient Algorithms With Linear Convergence Rates

On Convergence-Diagnostic based Step Sizes for Stochastic Gradient Descent

Universal and adaptive methods for robust stochastic optimization

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

A first-order primal-dual method with adaptivity to local smoothness

Proximal Point Imitation Learning

On The Convergence Of Stochastic Primal-Dual Hybrid Gradient

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

Enabling Uncertainty Estimation in Iterative Neural Networks

Decentralized Proximal Gradient Algorithms With Linear Convergence Rates

Last iterate convergence of SGD for Least-Squares in the Interpolation regime

On Convergence-Diagnostic based Step Sizes for Stochastic Gradient Descent