Publication

Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem

Publications associées (31)

On the relation between landscape beauty and land cover: A case study in the U.K. at Sentinel-2 resolution with interpretable AI

The environment where we live and recreate can have a significant effect on our well-being. More beautiful landscapes have considerable benefits to both health and quality of life. When we chose where to live or our next holiday destination, we do so accor ...

2021

Disparity Between Batches as a Signal for Early Stopping

Patrick Thiran, Mahsa Forouzesh

We propose a metric for evaluating the generalization ability of deep neural networks trained with mini-batch gradient descent. Our metric, called gradient disparity, is the l2 norm distance between the gradient vectors of two mini-batches drawn from the t ...

Springer2021

Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classification

Francesca Mignacco, Florent Gérard Krzakala, Lenka Zdeborová

We analyze in a closed form the learning dynamics of stochastic gradient descent (SGD) for a single layer neural network classifying a high-dimensional Gaussian mixture where each cluster is assigned one of two labels. This problem provides a prototype of ...

Curran Associates, Inc.2020

The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Updates

Sai Praneeth Reddy Karimireddy, Sebastian Urban Stich

We analyze (stochastic) gradient descent (SGD) with delayed updates on smooth quasi-convex and non-convex functions and derive concise, non-asymptotic, convergence rates. We show that the rate of convergence in all cases consists of two terms: (i) a stocha ...

Microtome Publishing2020

On the choice of metric in gradient-based theories of brain function

Wulfram Gerstner, Jean-Pascal Théodor Pfister, Johanni Michael Brea

The idea that the brain functions so as to minimize certain costs pervades theoretical neuroscience. Because a cost function by itself does not predict how the brain finds its minima, additional assumptions about the optimization method need to be made to ...

2020

3D nanometrology of transparent objects by phase calibration of a basic bright-field microscope for multiple illumination apertures

Martinus Gijs, Daniel Migliozzi, Bingying Zhao

Optical retrieval of the structure of transparent objects at the nanoscale requires adapted techniques capable of probing their interaction with light. Here, we considered a method based on calibration of the defocusing with partially coherent illumination ...

2020

Optimal Convergence for Distributed Learning with Stochastic Gradient Methods and Spectral Algorithms

Volkan Cevher, Junhong Lin

We study generalization properties of distributed algorithms in the setting of nonparametric regression over a reproducing kernel Hilbert space (RKHS). We first investigate distributed stochastic gradient methods (SGM), with mini-batches and multi-passes o ...

2020

Second-order guarantees in centralized, federated and decentralized nonconvex optimization

Ali H. Sayed, Stefan Vlaski

Rapid advances in data collection and processing capabilities have allowed for the use of increasingly complex models that give rise to nonconvex optimization problems. These formulations, however, can be arbitrarily difficult to solve in general, in the s ...

INT PRESS BOSTON, INC2020

Adaptive Gradient Descent without Descent

Konstantin Mishchenko

We present a strikingly simple proof that two rules are sufficient to automate gradient descent: 1) don’t increase the stepsize too fast and 2) don’t overstep the local curvature. No need for functional values, no line search, no information about the func ...

2020

Stochastic Gradient Descent for Spectral Embedding with Implicit Orthogonality Constraint

Pascal Frossard, Giovanni Chierchia, Mireille El Gheche

In this paper, we propose a scalable algorithm for spectral embedding. The latter is a standard tool for graph clustering. However, its computational bottleneck is the eigendecomposition of the graph Laplacian matrix, which prevents its application to larg ...

IEEE2019

Learning Non-Parametric Models with Guarantees: A Smooth Lipschitz Interpolation Approach

Colin Neil Jones, Emilio Maddalena

We propose a non-parametric regression method that does not rely on the structure of the ground-truth, but only on its regularity properties. The methodology can be readily used for learning surrogate models of nonlinear dynamical systems from data, while ...

2019