Publications related to Almost surely constrained convex optimization

On the Generalization of Stochastic Gradient Descent with Momentum

While momentum-based accelerated variants of stochastic gradient descent (SGD) are widely used when training machine learning models, there is little theoretical understanding on the generalization error of such methods. In this work, we first show that th ...

Brookline2024

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

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

Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function

Patrick Thiran, Negar Kiyavash, Saber Salehkaleybar

We study the performance of Stochastic Cubic Regularized Newton (SCRN) on a class of functions satisfying gradient dominance property with

1\le\alpha\le2

which holds in a wide range of applications in machine learning and signal processing. This conditio ...

NeurIPS2022

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

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

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

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

Second-Order Guarantees In Federated Learning

Ali H. Sayed, Stefan Vlaski, Elsa Rizk

Federated learning is a useful framework for centralized learning from distributed data under practical considerations of heterogeneity, asynchrony, and privacy. Federated architectures are frequently deployed in deep learning settings, which generally giv ...

IEEE2020

Extrapolation for Large-batch Training in Deep Learning

Martin Jaggi, Sebastian Urban Stich, Tao Lin, Lingjing Kong

Deep learning networks are typically trained by Stochastic Gradient Descent (SGD) methods that iteratively improve the model parameters by estimating a gradient on a very small fraction of the training data. A major roadblock faced when increasing the batc ...

2020

Almost surely constrained convex optimization

Graph Chatbot

Chat with Graph Search

On the Generalization of Stochastic Gradient Descent with Momentum

Universal and adaptive methods for robust stochastic optimization

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function

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

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

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

Second-Order Guarantees In Federated Learning

Extrapolation for Large-batch Training in Deep Learning

Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function

On the Generalization of Stochastic Gradient Descent with Momentum

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Universal and adaptive methods for robust stochastic optimization

Extrapolation for Large-batch Training in Deep Learning

Second-Order Guarantees In Federated Learning

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

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

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

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