arXiv research

PACE optimizes training for averaged language models, improving performance.

Improving optimization for iterate-averaged language models

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…

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

Many problems in machine learning and game theory can be formulated as saddle-point problems, for which various first-order methods have been developed and proven efficient in practice. Under the general convex-concave assumption, most first-order methods only guarantee an ergodic convergence rate, that is, the uniform…

Paper develops bounds for stochastic approximation with averaging.

Improved SEG method converges to Nash equilibrium in bilinear games.

Two-Tailed Averaging improves generalization by optimizing the number of leading iterates to ignore.

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 …

In this paper we study the smooth convex-concave saddle point problem. Specifically, we analyze the last iterate convergence properties of the Extragradient (EG) algorithm. It is well known that the ergodic (averaged) iterates of EG converge at a rate of $O(1/T)$ (Nemirovski, 2004). In this paper, we show that the last…

New RL algorithms improve average-reward performance.

New averaging technique speeds up Newton method convergence.

Improved stochastic Halpern iteration for fixed-point approximation in normed spaces.

Distributed statistical learning problems arise commonly when dealing with large datasets. In this setup, datasets are partitioned over machines, which compute locally, and communicate short messages. Communication is often the bottleneck. In this paper, we study one-step and iterative weighted parameter averaging in s…

We adapt the optimization's concept of momentum to reinforcement learning. Seeing the state-action value functions as an analog to the gradients in optimization, we interpret momentum as an average of consecutive $q$-functions. We derive Momentum Value Iteration (MoVI), a variation of Value Iteration that incorporates …

Iterative procedures for parameter estimation based on stochastic gradient descent allow the estimation to scale to massive data sets. However, in both theory and practice, they suffer from numerical instability. Moreover, they are statistically inefficient as estimators of the true parameter value. To address these tw…

New method averages SGD iterates to achieve adjustable regularization.

Improved TD learning with tail averaging and regularization achieves optimal convergence rates.

The paper offers precise bounds for averaged LSA iterates in linear systems.

In this note, we present a new averaging technique for the projected stochastic subgradient method. By using a weighted average with a weight of t+1 for each iterate w_t at iteration t, we obtain the convergence rate of O(1/t) with both an easy proof and an easy implementation. The new scheme is compared empirically to…

Unified analysis of finite weight averaging methods in deep learning.

New convergence rates for shuffling gradient methods without strong convexity.

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…

New bounds for SGD show improved performance in various settings.

SGD in linear regression overfits but performs well due to bias-variance trade-off.

Q-learning for average cost MDPs gets a concentration bound.

New algorithm reduces reinforcement learning regret to sqrt(T) without strong dynamics assumptions.

This paper analyzes SGD with increasingly weighted averaging for optimization and generalization.

Paper provides tail bounds for stochastic mirror descent in heavy-tailed noise.

GPA improves LLM training speed by 8.71% for Llama-160M models.

The paper develops time-uniform inference methods for stochastic approximation parameters.

New algorithm achieves optimal regret in average reward MDPs without prior bias information.

In this paper, we propose a novel policy iteration method, called dynamic policy programming (DPP), to estimate the optimal policy in the infinite-horizon Markov decision processes. We prove the finite-iteration and asymptotic l\infty-norm performance-loss bounds for DPP in the presence of approximation/estimation erro…

We consider $d$-dimensional linear stochastic approximation algorithms (LSAs) with a constant step-size and the so called Polyak-Ruppert (PR) averaging of iterates. LSAs are widely applied in machine learning and reinforcement learning (RL), where the aim is to compute an appropriate $θ_{*} \in \mathbb{R}^d$ (that is a…

KL regularization helps RL algorithms by implicitly averaging q-values.

AMP algorithms can be efficiently simulated by SDPs even with corrupted data.

Faster algorithms for solving multichain MDPs under average-reward criterion.

Optimal algorithms for Riemannian optimization with reduced complexity.

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…

Stochastic Gradient Descent (SGD) is one of the simplest and most popular stochastic optimization methods. While it has already been theoretically studied for decades, the classical analysis usually required non-trivial smoothness assumptions, which do not apply to many modern applications of SGD with non-smooth object…

Paper analyzes LSA algorithm bias and error bounds with RR extrapolation.

The variance reduction class of algorithms including the representative ones, SVRG and SARAH, have well documented merits for empirical risk minimization problems. However, they require grid search to tune parameters (step size and the number of iterations per inner loop) for optimal performance. This work introduces `…

Stochastic algo learns from evolving data, achieving optimal performance.

We consider the minimization of a function defined on a Riemannian manifold $\mathcal{M}$ accessible only through unbiased estimates of its gradients. We develop a geometric framework to transform a sequence of slowly converging iterates generated from stochastic gradient descent (SGD) on $\mathcal{M}$ to an averaged i…

New TD method stabilizes average-reward learning.

Partial model averaging improves Federated Learning performance.

We propose SWA-Gaussian (SWAG), a simple, scalable, and general purpose approach for uncertainty representation and calibration in deep learning. Stochastic Weight Averaging (SWA), which computes the first moment of stochastic gradient descent (SGD) iterates with a modified learning rate schedule, has recently been sho…

BEMA reduces bias in EMA, leading to faster convergence and better performance.