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

Leveraging Continuous Time to Understand Momentum When Training Diagonal Linear Networks

Nicolas Henri Bernard Flammarion, Hristo Georgiev Papazov, Scott William Pesme

In this work, we investigate the effect of momentum on the optimisation trajectory of gradient descent. We leverage a continuous-time approach in the analysis of momentum gradient descent with step size

\gamma

and momentum parameter

\beta

that allows u ...

2024

Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity

Rachid Guerraoui, Nirupam Gupta, Youssef Allouah, Geovani Rizk, Rafaël Benjamin Pinot

The theory underlying robust distributed learning algorithms, designed to resist adversarial machines, matches empirical observations when data is homogeneous. Under data heterogeneity however, which is the norm in practical scenarios, established lower bo ...

2023

The statistical complexity of early-stopped mirror descent

Tomas Vaskevicius, Varun Kanade

Recently there has been a surge of interest in understanding implicit regularization properties of iterative gradient-based optimization algorithms. In this paper, we study the statistical guarantees on the excess risk achieved by early-stopped unconstrain ...

Oxford2023

Iterative pre-conditioning for expediting the distributed gradient-descent method: The case of linear least-squares problem

Nirupam Gupta

This paper considers the multi-agent linear least-squares problem in a server-agent network architecture. The system comprises multiple agents, each with a set of local data points. The agents are connected to a server, and there is no inter-agent communic ...

PERGAMON-ELSEVIER SCIENCE LTD2022

A Least-Squares Method for the Solution of the Non-smooth Prescribed Jacobian Equation

Alexandre Caboussat, Dimitrios Gourzoulidis

We consider a least-squares/relaxation finite element method for the numerical solution of the prescribed Jacobian equation. We look for its solution via a least-squares approach. We introduce a relaxation algorithm that decouples this least-squares proble ...

SPRINGER/PLENUM PUBLISHERS2022

Accelerated SGD for Non-Strongly-Convex Least Squares

Nicolas Henri Bernard Flammarion, Aditya Vardhan Varre

We consider stochastic approximation for the least squares regression problem in the non-strongly convex setting. We present the first practical algorithm that achieves the optimal prediction error rates in terms of dependence on the noise of the problem, ...

2022

Predicting in Uncertain Environments: Methods for Robust Machine Learning

Paul Thierry Yves Rolland

One of the main goal of Artificial Intelligence is to develop models capable of providing valuable predictions in real-world environments. In particular, Machine Learning (ML) seeks to design such models by learning from examples coming from this same envi ...

EPFL2022

Rapid Scalable Distributed Power Flow with Open-Source Implementation

Yuning Jiang, Xinliang Dai

This paper introduces a new method for solving the distributed AC power flow (PF) problem by further exploiting the problem formulation. We propose a new variant of the ALADIN algorithm devised specifically for this type of problem. This new variant is cha ...

ELSEVIER2022

ADAGRAD Avoids Saddle Points

Kimon Antonakopoulos, Xiao Wang

Adaptive first-order methods in optimization are prominent in machine learning and data science owing to their ability to automatically adapt to the landscape of the function being optimized. However, their convergence guarantees are typically stated in te ...

JMLR-JOURNAL MACHINE LEARNING RESEARCH2022

Momentum-Based Policy Gradient with Second-Order Information

Patrick Thiran, Negar Kiyavash, Mohammadsadegh Khorasani, Saber Salehkaleybar

Variance-reduced gradient estimators for policy gradient methods have been one of the main focus of research in the reinforcement learning in recent years as they allow acceleration of the estimation process. We propose a variance-reduced policy-gradient m ...

2022

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

Graph Chatbot

Chat with Graph Search

Leveraging Continuous Time to Understand Momentum When Training Diagonal Linear Networks

Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity

The statistical complexity of early-stopped mirror descent

Iterative pre-conditioning for expediting the distributed gradient-descent method: The case of linear least-squares problem

A Least-Squares Method for the Solution of the Non-smooth Prescribed Jacobian Equation

Accelerated SGD for Non-Strongly-Convex Least Squares

Predicting in Uncertain Environments: Methods for Robust Machine Learning

Rapid Scalable Distributed Power Flow with Open-Source Implementation

ADAGRAD Avoids Saddle Points

Momentum-Based Policy Gradient with Second-Order Information

Leveraging Continuous Time to Understand Momentum When Training Diagonal Linear Networks

Predicting in Uncertain Environments: Methods for Robust Machine Learning

A Least-Squares Method for the Solution of the Non-smooth Prescribed Jacobian Equation

Accelerated SGD for Non-Strongly-Convex Least Squares

Momentum-Based Policy Gradient with Second-Order Information

The statistical complexity of early-stopped mirror descent

Iterative pre-conditioning for expediting the distributed gradient-descent method: The case of linear least-squares problem

Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity

Rapid Scalable Distributed Power Flow with Open-Source Implementation

ADAGRAD Avoids Saddle Points