Publications associées à Convex Optimization using Sparsified Stochastic Gradient Descent with Memory

Decentralized Semi-supervised Learning over Multitask Graphs

In network semi-supervised learning problems, only a subset of the network nodes is able to access the data labeling. This paper formulates a decentralized optimization problem where agents have individual decision rules to estimate, subject to the conditi ...

IEEE2022

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

Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates

Martin Jaggi, Sebastian Urban Stich, Amirkeivan Mohtashami

It has been experimentally observed that the efficiency of distributed training with stochastic gradient (SGD) depends decisively on the batch size and—in asynchronous implementations—on the gradient staleness. Especially, it has been observed that the spe ...

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

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

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

Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity

Nicolas Henri Bernard Flammarion, Scott William Pesme, Loucas Pillaud-Vivien

Understanding the implicit bias of training algorithms is of crucial importance in order to explain the success of overparametrised neural networks. In this paper, we study the dynamics of stochastic gradient descent over diagonal linear networks through i ...

2021

Regret Minimization in Stochastic Non-Convex Learning via a Proximal-Gradient Approach

Volkan Cevher, Shaul Nadav Hallak

This paper develops a methodology for regret minimization with stochastic first-order oracle feedback in online, constrained, non-smooth, non-convex problems. In this setting, the minimization of external regret is beyond reach for first-order methods, and ...

JMLR-JOURNAL MACHINE LEARNING RESEARCH2021

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

PACOH: Bayes-Optimal Meta-Learning with PAC-Guarantees

Andreas Krause, Martin Josifoski

Meta-learning can successfully acquire useful inductive biases from data. Yet, its generalization properties to unseen learning tasks are poorly understood. Particularly if the number of meta-training tasks is small, this raises concerns about overfitting. ...

JMLR-JOURNAL MACHINE LEARNING RESEARCH2021

Convex Optimization using Sparsified Stochastic Gradient Descent with Memory

Graph Chatbot

Chattez avec Graph Search

Decentralized Semi-supervised Learning over Multitask Graphs

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

Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates

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

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

STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization

Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity

Regret Minimization in Stochastic Non-Convex Learning via a Proximal-Gradient Approach

Convergence of adaptive algorithms for constrained weakly convex optimization

PACOH: Bayes-Optimal Meta-Learning with PAC-Guarantees

STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization

Regret Minimization in Stochastic Non-Convex Learning via a Proximal-Gradient Approach

PACOH: Bayes-Optimal Meta-Learning with PAC-Guarantees

Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates

Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity

Decentralized Semi-supervised Learning over Multitask Graphs

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

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

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

Convergence of adaptive algorithms for constrained weakly convex optimization