arXiv research

HF-opt uses Hamiltonian dynamics to optimize functions, achieving accelerated rates with randomized integration time.

Accelerates sampling from Gibbs distributions using ARWP method.

Improved analysis of accelerated noisy power method for PCA.

Paper accelerates diffusion models, improving sampling speed.

Improved first-order algorithm for entropy regularized OT with faster convergence.

Fractal learning rate schedules accelerate vanilla gradient descent.

Accelerates Riemannian gradient methods with extrapolation.

Momentum accelerates Frank Wolfe algorithms on certain problems.

A new algorithm improves convergence rates for convex optimization problems.

In [19], a general, inexact, efficient proximal quasi-Newton algorithm for composite optimization problems has been proposed and a sublinear global convergence rate has been established. In this paper, we analyze the convergence properties of this method, both in the exact and inexact setting, in the case when the obje…

We formulate and study a general family of (continuous-time) stochastic dynamics for accelerated first-order minimization of smooth convex functions. Building on an averaging formulation of accelerated mirror descent, we propose a stochastic variant in which the gradient is contaminated by noise, and study the resultin…

Nesterov SGD is widely used for training modern neural networks and other machine learning models. Yet, its advantages over SGD have not been theoretically clarified. Indeed, as we show in our paper, both theoretically and empirically, Nesterov SGD with any parameter selection does not in general provide acceleration o…

Conditional gradients constitute a class of projection-free first-order algorithms for smooth convex optimization. As such, they are frequently used in solving smooth convex optimization problems over polytopes, for which the computational cost of orthogonal projections would be prohibitive. However, they do not enjoy …

Regularized nonlinear acceleration (RNA) estimates the minimum of a function by post-processing iterates from an algorithm such as the gradient method. It can be seen as a regularized version of Anderson acceleration, a classical acceleration scheme from numerical analysis. The new scheme provably improves the rate of …

Momentum methods such as Polyak's heavy ball (HB) method, Nesterov's accelerated gradient (AG) as well as accelerated projected gradient (APG) method have been commonly used in machine learning practice, but their performance is quite sensitive to noise in the gradients. We study these methods under a first-order stoch…

We provide improved convergence rates for various \emph{non-smooth} optimization problems via higher-order accelerated methods. In the case of $\ell_\infty$ regression, we achieves an $O(ε^{-4/5})$ iteration complexity, breaking the $O(ε^{-1})$ barrier so far present for previous methods. We arrive at a similar rate fo…

Two new differentially private optimization algorithms derived from accelerated methods.

Polyak's momentum accelerates training of neural networks.

New adaptive methods for constrained convex optimization and variational inequalities.

Unified framework for understanding and optimizing training acceleration.

New method solves convex optimization faster than NAG.

Recently, many variance reduced stochastic alternating direction method of multipliers (ADMM) methods (e.g.\ SAG-ADMM, SDCA-ADMM and SVRG-ADMM) have made exciting progress such as linear convergence rates for strongly convex problems. However, the best known convergence rate for general convex problems is O(1/T) as opp…

GADD accelerates uniform-rate discrete diffusion models by 2 orders of magnitude.

In this work we introduce a conditional accelerated lazy stochastic gradient descent algorithm with optimal number of calls to a stochastic first-order oracle and convergence rate $O\left(\frac{1}{\varepsilon^2}\right)$ improving over the projection-free, Online Frank-Wolfe based stochastic gradient descent of Hazan an…

Unified framework for accelerated Perceptron and related problems.

Seesaw optimizes training by balancing learning rate and batch size, accelerating model pretraining.

Principal component analysis (PCA) is one of the most powerful tools in machine learning. The simplest method for PCA, the power iteration, requires $\mathcal O(1/Δ)$ full-data passes to recover the principal component of a matrix with eigen-gap $Δ$. Lanczos, a significantly more complex method, achieves an accelerated…

New methods optimize functions on hyperbolic and spherical spaces, matching Euclidean rates up to logarithmic factors.

Anderson acceleration (or Anderson mixing) is an efficient acceleration method for fixed point iterations $x_{t+1}=G(x_t)$, e.g., gradient descent can be viewed as iteratively applying the operation $G(x) \triangleq x-α\nabla f(x)$. It is known that Anderson acceleration is quite efficient in practice and can be viewed…

Momentum is a popular technique to accelerate the convergence in practical training, and its impact on convergence guarantee has been well-studied for first-order algorithms. However, such a successful acceleration technique has not yet been proposed for second-order algorithms in nonconvex optimization.In this paper, …

Two accelerated extragradient methods converge at $O(1/k)$ rate for co-hypomonotone inclusions.

Stochastic gradient descent (\textsc{Sgd}) methods are the most powerful optimization tools in training machine learning and deep learning models. Moreover, acceleration (a.k.a. momentum) methods and diagonal scaling (a.k.a. adaptive gradient) methods are the two main techniques to improve the slow convergence of \text…

The paper accelerates ISTA and FISTA algorithms for composite optimization problems.

We consider the problem of accelerating distributed optimization in multi-agent networks by sequentially adding edges. Specifically, we extend the distributed dual averaging (DDA) subgradient algorithm to evolving networks of growing connectivity and analyze the corresponding improvement in convergence rate. It is know…

Improved SGD for non-strongly-convex regression with faster convergence.

GD and NAG accelerate matrix factorization and neural networks.

Develops accelerated fixed-point methods with delayed oracles for scientific computing.

Hamiltonian dynamics-based algorithms achieve deterministic and accelerated convergence for convex optimization.

A new family of momentum coefficients improves the convergence rate of accelerated algorithms.

Study adapts liquidity model to equity auctions, revealing accelerated event rates and reduced price impact.

In this work we consider the stochastic minimization of nonsmooth convex loss functions, a central problem in machine learning. We propose a novel algorithm called Accelerated Nonsmooth Stochastic Gradient Descent (ANSGD), which exploits the structure of common nonsmooth loss functions to achieve optimal convergence ra…

Accelerates BERT pretraining from 3 days to 54 minutes.

Accelerated gradient methods play a central role in optimization, achieving optimal rates in many settings. While many generalizations and extensions of Nesterov's original acceleration method have been proposed, it is not yet clear what is the natural scope of the acceleration concept. In this paper, we study accelera…

New insights into optimizing Local SGD's outer optimizer for faster convergence.

AGNES accelerates gradient descent with noisy gradients.

PF-LaCG removes the need for knowing smoothness and strong convexity parameters for locally accelerated CG.

Accelerated optimization methods improve robustness and privacy in estimation.

Integrating adaptive learning rate and momentum techniques into SGD leads to a large class of efficiently accelerated adaptive stochastic algorithms, such as AdaGrad, RMSProp, Adam, AccAdaGrad, \textit{etc}. In spite of their effectiveness in practice, there is still a large gap in their theories of convergences, espec…