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

Nicolas Henri Bernard Flammarion, Loucas Pillaud-Vivien, Aditya Vardhan Varre
2021
Report or working paper

Abstract

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 and outputs $\langle \theta_* , \phi(X) \rangle = Y$ , where $\phi(X)$ stands for a possibly infinite dimensional non-linear feature map. To solve this problem, we consider the estimator given by the last iterate of stochastic gradient descent (SGD) with constant step-size. In this context, our contribution is two fold: (i) \emph{from a (stochastic) optimization perspective}, we exhibit an archetypal problem where we can show explicitly the convergence of SGD final iterate for a non-strongly convex problem with constant step-size whereas usual results use some form of average and (ii) \emph{from a statistical perspective}, we give explicit non-asymptotic convergence rates in the over-parameterized setting and leverage a \emph{fine-grained} parameterization of the problem to exhibit polynomial rates that can be faster than $O(1/T)$ . The link with reproducing kernel Hilbert spaces is established.

Official source

https://infoscience.epfl.ch/record/283259?ln=en

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Related publications

Nicolas Henri Bernard Flammarion, Loucas Pillaud-Vivien, Aditya Vardhan Varre
2021
Report or working paper

Abstract

Official source

https://infoscience.epfl.ch/record/283259?ln=en

About this result

Related concepts (20)

Related concepts

Related publications (94)

Related publications

From Classical to Unsupervised-Deep-Learning Methods for Solving Inverse Problems in Imaging.

Harshit Gupta

In this thesis, we propose new algorithms to solve inverse problems in the context of biomedical images. Due to ill-posedness, solving these problems require some prior knowledge of the statistics of the underlying images. The traditional algorithms, in the field, assume prior knowledge related to smoothness or sparsity of these images. Recently, they have been outperformed by the second generation algorithms which harness the power of neural networks to learn required statistics from training data. Even more recently, last generation deep-learning-based methods have emerged which require neither training nor training data. This thesis devises algorithms which progress through these generations. It extends these generations to novel formulations and applications while bringing more robustness. In parallel, it also progresses in terms of complexity, from proposing algorithms for problems with 1D data and an exact known forward model to the ones with 4D data and an unknown parametric forward model. We introduce five main contributions. The last three of them propose deep-learning-based latest-generation algorithms that require no prior training. 1) We develop algorithms to solve the continuous-domain formulation of inverse problems with both classical Tikhonov and total-variation regularizations. We formalize the problems, characterize the solution set, and devise numerical approaches to find the solutions. 2) We propose an algorithm that improves upon end-to-end neural-network-based second generation algorithms. In our method, a neural network is first trained as a projector on a training set, and is then plugged in as a projector inside the projected gradient descent (PGD). Since the problem is nonconvex, we relax the PGD to ensure convergence to a local minimum under some constraints. This method outperforms all the previous generation algorithms for Computed Tomography (CT). 3) We develop a novel time-dependent deep-image-prior algorithm for modalities that involve a temporal sequence of images. We parameterize them as the output of an untrained neural network fed with a sequence of latent variables. To impose temporal directionality, the latent variables are assumed to lie on a 1D manifold. The network is then tuned to minimize the data fidelity. We obtain state-of-the-art results in dynamic magnetic resonance imaging (MRI) and even recover intra-frame images. 4) We propose a novel reconstruction paradigm for cryo-electron-microscopy (CryoEM) called CryoGAN. Motivated by generative adversarial networks (GANs), we reconstruct a biomolecule's 3D structure such that its CryoEM measurements resemble the acquired data in a distributional sense. The algorithm is pose-or-likelihood-estimation-free, needs no ab initio, and is proven to have a theoretical guarantee of recovery of the true structure. 5) We extend CryoGAN to reconstruct continuously varying conformations of a structure from heterogeneous data. We parameterize the conformations as the output of a neural network fed with latent variables on a low-dimensional manifold. The method is shown to recover continuous protein conformations and their energy landscape.

EPFL2020

Dynamic optimization problems affected by uncertainty are ubiquitous in many application domains. Decision makers typically model the uncertainty through random variables governed by a probability distribution. If the distribution is precisely known, then the emerging optimization problems constitute stochastic programs or chance constrained programs. On the other hand, if the distribution is at least partially unknown, then the emanating optimization problems represent robust or distributionally robust optimization problems. In this thesis, we leverage techniques from stochastic and distributionally robust optimization to address complex problems in finance, energy systems management and, more abstractly, applied probability. In particular, we seek to solve uncertain optimization problems where the prior distributional information includes only the first and the second moments (and, sometimes, the support). The main objective of the thesis is to solve large instances of practical optimization problems. For this purpose, we develop complexity reduction and decomposition schemes, which exploit structural symmetries or multiscale properties of the problems at hand in order to break them down into smaller and more tractable components. In the first part of the thesis we study the growth-optimal portfolio, which maximizes the expected log-utility over a single investment period. In a classical stochastic setting, this portfolio is known to outperform any other portfolio with probability 1 in the long run. In the short run, however, it is notoriously volatile. Moreover, its performance suffers in the presence of distributional ambiguity. We design fixed-mix strategies that offer similar performance guarantees as the classical growth-optimal portfolio but for a finite investment horizon. Moreover, the proposed performance guarantee remains valid for any asset return distribution with the same mean and covariance matrix. These results rely on a Taylor approximation of the terminal logarithmic wealth that becomes more accurate as the rebalancing frequency is increased. In the second part of the thesis, we demonstrate that such a Taylor approximation is in fact not necessary. Specifically, we derive sharp probability bounds on the tails of a product of non-negative random variables. These generalized Chebyshev bounds can be computed numerically using semidefinite programming--in some cases even analytically. Similar techniques can also be used to derive multivariate Chebyshev bounds for sums, maxima, and minima of random variables. In the final part of the thesis, we consider a multi-market reservoir management problem. The eroding peak/off-peak spreads on European electricity spot markets imply reduced profitability for the hydropower producers and force them to participate in the balancing markets. This motivates us to propose a two-layer stochastic programming model for the optimal operation of a cascade of hydropower plants selling energy on both spot and balancing markets. The planning problem optimizes the reservoir management over a yearly horizon with weekly granularity, and the trading subproblems optimize the market transactions over a weekly horizon with hourly granularity. We solve both the planning and trading problems in linear decision rules, and we exploit the inherent parallelizability of the trading subproblems to achieve computational tractability.

EPFL2016

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 specific case of smooth minimization. In this dissertation, we focus on related problems of nonsmooth optimization and min-max optimization to improve the theoretical understanding of stochastic algorithms.First, we study SGD-based adaptive algorithms and propose a regret analysis framework overcoming the limitations of the existing ones in the convex case. In the nonconvex case, we prove convergence of an adaptive gradient algoritm for solving constrained weakly convex optimization, generalizing the previously known results on unconstrained smooth optimization. We also propose an algorithm combining Nesterov's smoothing with SGD to solve convex problems with infinitely many linear constraints, with optimal rates.Then, we move on to convex-concave min-max problems with bilinear coupling and analyze primal-dual coordinate descent (PDCD) algorithms. We obtain the first PDCD methods with the optimal

\mathcal{O}(1/k)

rate on the the standard optimality measure expected primal-dual gap, which was an open question since 2014. Our analysis also aims to explain the practical behavior of these algorithms by showing that the last iterate enjoys adaptive linear convergence without altering the parameters, depending on a certain error bound condition. Furthermore, we propose an algorithm combining the favorable properties of two branches of PDCD methods: the new method uses large step sizes with dense data and its per-iteration cost depends on the number of nonzeros of the data matrix. Thanks to these unique properties, this method enjoys compelling practical performance complementing its rigorous theoretical guarantees.Next, we consider monotone variational inequalities that generalize convex-concave min-max problems with nonbilinear coupling. We introduce variance reduced algorithms that converge under the same set of assumptions as their deterministic counterparts and improve the best-known complexities for solving convex-concave min-max problems with finite-sum structure. Optimality of our algorithms for this problem class is established in a recent work via matching lower bounds. Finally, we show our preliminary results on policy optimization methods for solving two player zero-sum Markov games for competitive reinforcement learning (RL). Even though this is a nonconvex-nonconcave min-max problem in general, thanks to the special structure, it is tractable to find an approximate Nash equilibrium. We introduce an algorithm that improves the best-known sample complexity of policy gradient methods. This development combines tools from RL and stochastic primal-dual optimization, showing the importance of techniques from convex-concave optimization.

EPFL2021