arXiv research

We introduce a simple algorithm, True Asymptotic Natural Gradient Optimization (TANGO), that converges to a true natural gradient descent in the limit of small learning rates, without explicit Fisher matrix estimation. For quadratic models the algorithm is also an instance of averaged stochastic gradient, where the par…

We propose and analyze a variant of the classic Polyak-Ruppert averaging scheme, broadly used in stochastic gradient methods. Rather than a uniform average of the iterates, we consider a weighted average, with weights decaying in a geometric fashion. In the context of linear least squares regression, we show that this …

Paper explores weighted averaging schemes for SGD, achieving asymptotic normality and optimality.

Gradient descent biases neural networks to use an average of features, leading to non-robustness.

DSPI connects natural policy gradient to policy iteration, proving global convergence.

A2SGD reduces distributed SGD communication to O(1) per worker.

COMP-AMS optimizes distributed training with compressed gradients, achieving similar accuracy with less communication.

Averaged SGD achieves optimal convergence rate for neural networks in the NTK regime.

Paper proposes a mean-field gradient descent for zero-sum games, proving convergence to Nash equilibrium.

Many machine learning, statistical inference, and portfolio optimization problems require minimization of a composition of expected value functions (CEVF). Of particular interest is the finite-sum versions of such compositional optimization problems (FS-CEVF). Compositional stochastic variance reduced gradient (C-SVRG)…

SGD (Stochastic Gradient Descent) is a popular algorithm for large scale optimization problems due to its low iterative cost. However, SGD can not achieve linear convergence rate as FGD (Full Gradient Descent) because of the inherent gradient variance. To attack the problem, mini-batch SGD was proposed to get a trade-o…

This paper analyzes the convergence of Federated Average under relaxed assumptions.

New method for unbiased regression reduces excess risk.

New methods optimize functions faster with less gradient accuracy needed.

STORM-PG uses momentum for faster policy gradient updates.

Study shows gradient variance increases during deep learning training, contrary to common belief.

We apply stochastic average gradient (SAG) algorithms for training conditional random fields (CRFs). We describe a practical implementation that uses structure in the CRF gradient to reduce the memory requirement of this linearly-convergent stochastic gradient method, propose a non-uniform sampling scheme that substant…

Convolutional neural networks converge quickly with gradient descent.

We describe the neural-network training framework used in the Kaldi speech recognition toolkit, which is geared towards training DNNs with large amounts of training data using multiple GPU-equipped or multi-core machines. In order to be as hardware-agnostic as possible, we needed a way to use multiple machines without …

Sharp gradient estimate for scalar curvature on 3-manifolds.

In many high-dimensional estimation problems the main task consists in minimizing a cost function, which is often strongly non-convex when scanned in the space of parameters to be estimated. A standard solution to flatten the corresponding rough landscape consists in summing the losses associated to different data poin…

We show that accelerated gradient descent, averaged gradient descent and the heavy-ball method for non-strongly-convex problems may be reformulated as constant parameter second-order difference equation algorithms, where stability of the system is equivalent to convergence at rate O(1/n 2), where n is the number of ite…

We consider in this work a system of two stochastic differential equations named the perturbed compositional gradient flow. By introducing a separation of fast and slow scales of the two equations, we show that the limit of the slow motion is given by an averaged ordinary differential equation. We then demonstrate that…

Unified analysis of finite weight averaging methods in deep learning.

Averaged SGD optimizes a smoothed objective, leading to better generalization.

Improved averaging method for noisy observations converges strongly.

Stochastic gradient methods enable learning probabilistic models from large amounts of data. While large step-sizes (learning rates) have shown to be best for least-squares (e.g., Gaussian noise) once combined with parameter averaging, these are not leading to convergent algorithms in general. In this paper, we conside…

This work characterizes the benefits of averaging schemes widely used in conjunction with stochastic gradient descent (SGD). In particular, this work provides a sharp analysis of: (1) mini-batching, a method of averaging many samples of a stochastic gradient to both reduce the variance of the stochastic gradient estima…

We analyse and explain the increased generalisation performance of iterate averaging using a Gaussian process perturbation model between the true and batch risk surface on the high dimensional quadratic. We derive three phenomena \latestEdits{from our theoretical results:} (1) The importance of combining iterate averag…

U-Clip clips gradients to reduce bias without discarding them.

Paper approximates risk measures using SGD with Langevin dynamics.

We show Vector Autoregressive Moving Average models with scalar Moving Average components could be estimated by generalized least square (GLS) for each fixed moving average polynomial. The conditional variance of the GLS model is the concentrated covariant matrix of the moving average process. Under GLS the likelihood …

The paper analyzes time-dependent streaming data with biased gradient estimates and proposes improved stochastic optimization methods.

We consider stochastic gradient descent algorithms for minimizing a non-smooth, strongly-convex function. Several forms of this algorithm, including suffix averaging, are known to achieve the optimal $O(1/T)$ convergence rate in expectation. We consider a simple, non-uniform averaging strategy of Lacoste-Julien et al. …

Stochastic variational inference (SVI) lets us scale up Bayesian computation to massive data. It uses stochastic optimization to fit a variational distribution, following easy-to-compute noisy natural gradients. As with most traditional stochastic optimization methods, SVI takes precautions to use unbiased stochastic g…

This work tackles semi-supervised federated learning by reducing model gradient diversity.

DoWG optimizer automatically adapts to convex and nonsmooth problems without tuning.

We consider a composite convex minimization problem associated with regularized empirical risk minimization, which often arises in machine learning. We propose two new stochastic gradient methods that are based on stochastic dual averaging method with variance reduction. Our methods generate a sparser solution than the…

New streaming methods improve convergence rates for optimization problems.

The paper analyzes rates for a modified gradient descent method using Stein variational gradients.

SGDM accelerates faster than SGD with large batch sizes and permits broader learning rates.

The study examines how averaging data improves model performance.

Consider a number of workers running SGD independently on the same pool of data and averaging the models every once in a while -- a common but not well understood practice. We study model averaging as a variance-reducing mechanism and describe two ways in which the frequency of averaging affects convergence. For convex…

New bound relaxes uniform gradient norm assumptions for PAC-Bayesian bounds.

Distributed data-parallel algorithms aim to accelerate the training of deep neural networks by parallelizing the computation of large mini-batch gradient updates across multiple nodes. Approaches that synchronize nodes using exact distributed averaging (e.g., via AllReduce) are sensitive to stragglers and communication…

We propose the stochastic average gradient (SAG) method for optimizing the sum of a finite number of smooth convex functions. Like stochastic gradient (SG) methods, the SAG method's iteration cost is independent of the number of terms in the sum. However, by incorporating a memory of previous gradient values the SAG me…

Improves deep learning models by blending gradients from training loss and auxiliary objective.

Actor-Critic method achieves optimal regret for unichain MDPs.