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

À propos
Confidentialité
Mentions légales

Graph Chatbot

Publications associées (31)

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

Aditya Vardhan Varre, Nicolas Henri Bernard Flammarion, 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 ...

Advances in Neural Information Processing Systems 20212021

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

A Newton Frank-Wolfe method for constrained self-concordant minimization

Volkan Cevher, Quoc Tran Dinh

We develop a new Newton Frank-Wolfe algorithm to solve a class of constrained self-concordant minimization problems using linear minimization oracles (LMO). Unlike L-smooth convex functions, where the Lipschitz continuity of the objective gradient holds gl ...

SPRINGER2022

Learning Lipschitz-Controlled Activation Functions in Neural Networks for Plug-and-Play Image Reconstruction Methods

Michaël Unser, Dimitris Perdios, Sébastien Alexandre Emery, Pakshal Narendra Bohra, Alexis Marie Frederic Goujon

Ill-posed linear inverse problems are frequently encountered in image reconstruction tasks. Image reconstruction methods that combine the Plug-and-Play (PnP) priors framework with convolutional neural network (CNN) based denoisers have shown impressive per ...

2021

Context-Aware Learning for Generative Models

Ricardo Andres Chavarriaga Lozano, José del Rocio Millán Ruiz, Serafeim Perdikis, Robert Leeb

This work studies the class of algorithms for learning with side-information that emerges by extending generative models with embedded context-related variables. Using finite mixture models (FMMs) as the prototypical Bayesian network, we show that maximum- ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2021

STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization

Volkan Cevher, Ali Kavis

In this work we investigate stochastic non-convex optimization problems wherethe objective is an expectation over smooth loss functions, and the goal is to find an approximate stationary point. The most popular approach to handling such problems is varianc ...

2021

LENA: Communication-Efficient Distributed Learning with Self-Triggered Gradient Uploads

Martin Jaggi, Sebastian Urban Stich, Hossein Shokri Ghadikolaei

In distributed optimization, parameter updates from the gradient computing node devices have to be aggregated in every iteration on the orchestrating server. When these updates are sent over an arbitrary commodity network, bandwidth and latency can be limi ...

MICROTOME PUBLISHING2021

On Convergence-Diagnostic based Step Sizes for Stochastic Gradient Descent

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

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

On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems

Volkan Cevher, Ali Kavis, Shaul Nadav Hallak

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 sequence of iterates generated by SGD remains bounded and converges with prob ...

2020

Page 2 sur 2