We study first-order optimization methods obtained by discretizing ordinary differential equations (ODEs) corresponding to Nesterov's accelerated gradient methods (NAGs) and Polyak's heavy-ball method. We consider three discretization schemes: an explicit Euler scheme, an implicit Euler scheme, and a symplectic scheme.…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “accelerated schemes”
Accelerates Riemannian gradient methods with extrapolation.
problem Optimizing functions on manifolds efficiently.
method Extrapolating iterates in Riemannian gradient descent.
result Achieves optimal convergence rate and computational advantage.
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 …
In this paper we explore acceleration techniques for large scale nonconvex optimization problems with special focuses on deep neural networks. The extrapolation scheme is a classical approach for accelerating stochastic gradient descent for convex optimization, but it does not work well for nonconvex optimization typic…
Motivated by weak convergence results in the paper of Takahashi and Yoshida (2005), we show strong convergence for an accelerated Euler-Maruyama scheme applied to perturbed stochastic differential equations. The Milstein scheme with the same acceleration is also discussed as an extended result. The theoretical results …
In this paper, we propose an acceleration scheme for online memory-limited PCA methods. Our scheme converges to the first eigenvectors in a single data pass. We provide empirical convergence results of our scheme based on the spiked covariance model. Our scheme does not require any predefined parameters such as t…
A new algorithm improves convergence rates for convex optimization problems.
problem Convex optimization problems with finite-sum structure.
method Nesterov Accelerated Shuffling Gradient (NASG) integrating Nesterov's acceleration with different shuffling schemes.
result Improved convergence rate of O(1/T) for unified shuffling schemes.
A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insightsstat.ML
We derive a second-order ordinary differential equation (ODE) which is the limit of Nesterov's accelerated gradient method. This ODE exhibits approximate equivalence to Nesterov's scheme and thus can serve as a tool for analysis. We show that the continuous time ODE allows for a better understanding of Nesterov's schem…
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, …
This paper studies accelerations in Q-learning algorithms. We propose an accelerated target update scheme by incorporating the historical iterates of Q functions. The idea is conceptually inspired by the momentum-based accelerated methods in the optimization theory. Conditions under which the proposed accelerated algor…
We present a design and implementation of the Thomas algorithm optimized for hardware acceleration on an FPGA, the Thomas Core. The hardware-based algorithm combined with the custom data flow and low level parallelism available in an FPGA reduces the overall complexity from 8N down to 5N serial arithmetic operations, a…
We present a dynamical system framework for understanding Nesterov's accelerated gradient method. In contrast to earlier work, our derivation does not rely on a vanishing step size argument. We show that Nesterov acceleration arises from discretizing an ordinary differential equation with a semi-implicit Euler integrat…
Extragradient-Type Methods with Last-Iterate Convergence Rates for Co-Hypomonotone Inclusionsmath.OC
Two accelerated extragradient methods converge at rate for co-hypomonotone inclusions.
problem Solving co-hypomonotone inclusions with sum of Lipschitz and multivalued operators.
method Developed two Nesterov's accelerated extragradient methods for co-hypomonotone inclusions.
result Achieve last-iterate convergence rates on the residual norm.
In this paper, we propose a general framework to accelerate significantly the algorithms for nonnegative matrix factorization (NMF). This framework is inspired from the extrapolation scheme used to accelerate gradient methods in convex optimization and from the method of parallel tangents. However, the use of extrapola…
New algorithms solve monotone inclusions and convex-concave minimax problems.
problem Solving maximally monotone equations and inclusions.
method Developed new accelerated algorithms based on Halpern-type fixed-point iteration and Popov's past extra-gradient method.
result Achieved convergence rates for various problems.
In this work, we present an extension of Gaussian process (GP) models with sophisticated parallelization and GPU acceleration. The parallelization scheme arises naturally from the modular computational structure w.r.t. datapoints in the sparse Gaussian process formulation. Additionally, the computational bottleneck is …
Develops an accelerated algorithm for solving nonmonotone generalized equations.
problem Solving nonmonotone generalized equations with possibly non-accelerated schemes.
method Combines Nesterov's acceleration and variance-reduction techniques for a class of generalized equations.
result Achieves convergence rates, improving upon non-accelerated counterparts.
The Regularized Nonlinear Acceleration (RNA) algorithm is an acceleration method capable of improving the rate of convergence of many optimization schemes such as gradient descend, SAGA or SVRG. Until now, its analysis is limited to convex problems, but empirical observations shows that RNA may be extended to wider set…
New method accelerates energetic variational inference using particle dynamics.
problem Efficiently solving variational inference problems with reduced computational cost.
method Particle-based variational inference with implicit scheme, inspired by energy quadratization and operator splitting.
result Significantly reduces computational cost compared to existing methods.
This paper advances extragradient methods for solving inclusions under co-hypomonotonicity.
problem Solving inclusions with non-Lipschitz mappings.
method Unified and generalized extragradient methods under co-hypomonotonicity.
result Achieved convergence rates for residual norms.
Modern distributed training of machine learning models suffers from high communication overhead for synchronizing stochastic gradients and model parameters. In this paper, to reduce the communication complexity, we propose \emph{double quantization}, a general scheme for quantizing both model parameters and gradients. …
Unified framework for understanding and optimizing training acceleration.
problem Challenges in optimizing training with regularization and acceleration techniques.
method Explains how AdaGrad, RMSProp, and Adam accelerate training, and derives a generalization for -regularization.
result Derives a unified mathematical framework for understanding and optimizing training acceleration.
New algorithms accelerate model-based optimization for stochastic problems.
problem Optimizing model-based stochastic optimization problems efficiently.
method Proposed new model-based algorithms with acceleration and minibatch techniques.
result Non-asymptotic convergence guarantees with linear speedup in minibatch size.
State-of-the-art algorithms for sparse subspace clustering perform spectral clustering on a similarity matrix typically obtained by representing each data point as a sparse combination of other points using either basis pursuit (BP) or orthogonal matching pursuit (OMP). BP-based methods are often prohibitive in practic…
New methods boost first-order optimization with faster rates.
problem Designing efficient first-order methods for convex problems.
method Shifted objective function with interpolation condition.
result New schemes achieve faster convergence rates.
We introduce a generic scheme for accelerating gradient-based optimization methods in the sense of Nesterov. The approach, called Catalyst, builds upon the inexact accelerated proximal point algorithm for minimizing a convex objective function, and consists of approximately solving a sequence of well-chosen auxiliary p…
Information that is stored in an encrypted format is, by definition, usually not amenable to statistical analysis or machine learning methods. In this paper we present detailed analysis of coordinate and accelerated gradient descent algorithms which are capable of fitting least squares and penalised ridge regression mo…
We study the conditions under which one is able to efficiently apply variance-reduction and acceleration schemes on finite sum optimization problems. First, we show that, perhaps surprisingly, the finite sum structure by itself, is not sufficient for obtaining a complexity bound of $\tilde{\cO}((n+L/μ)\ln(1/ε))$ for $L…
New algorithms find near-stationary points in convex optimization.
problem Finding near-stationary points in convex optimization.
method Memory-saving variant of OGM-G, accelerated SVRG, adaptively regularized accelerated SVRG.
result Schemes achieve fast rates for minimizing gradient norm and function value.
New method speeds up diffusion models without requiring complex assumptions.
problem Slow sampling in diffusion models due to high computational cost.
method Training-free acceleration scheme under minimal assumptions.
result Provable acceleration within iterations.
Paper explores weighted averaging schemes for SGD, achieving asymptotic normality and optimality.
problem Improving convergence of SGD in various settings.
method Develops a general weighted averaging scheme for SGD and establishes asymptotic normality.
result Establishes asymptotic normality and optimality of weighted averaged SGD solutions.
Accelerating Speculative Diffusions via Block Verification
problem Adapting speculative decoding for continuous diffusion models
method Introducing a novel speculative sampling mechanism for diffusion models
result Improves acceptance rate and speeds up inference
Repulsive Surfacescs.GR
New method avoids surface self-collision in geometric optimization.
problem Avoiding self-collision in surface optimization.
method Developed a numerical framework using tangent-point energy and fractional Sobolev inner product.
result Successfully accelerated collision avoidance scheme for triangle meshes.
GPU speeds up Monte Carlo simulations for large time steps.
problem Slow convergence and inaccurate solutions with large time steps in Monte Carlo simulations.
method Generalizes the Seven League scheme for GPU acceleration.
result Significantly improved computational speed.
New PDMP samplers improve BNN inference with accelerated computation.
problem Inference on Bayesian Neural Networks violates independence and posterior assumptions.
method Piecewise Deterministic Markov Process (PDMP) with adaptive thinning for inhomogenous Poisson Process (IPPs) sampling.
result PDMP samplers accelerate inference in BNNs, improving accuracy and mixing performance.
Memory Organization for Energy-Efficient Learning and Inference in Digital Neuromorphic Acceleratorscs.NE
Improves energy efficiency of neuromorphic hardware by optimizing memory organization and encoding schemes.
problem Energy inefficiency in neuromorphic hardware, especially in digital accelerators.
method Synthesized controller and memory for different encoding schemes, introduced functional encoding for structured connectivity.
result Functional encoding offers a 58% reduction in energy for weight updates in convolutional layers.
This paper introduces an acceleration structure for hyperbolic embeddings.
problem Efficiently embedding and visualizing high-dimensional data in hyperbolic spaces.
method Building upon a polar quadtree, the paper introduces a new acceleration structure for hyperbolic embeddings.
result The new method computes embeddings in significantly less time compared to existing methods.
This research analyzes and accelerates score-based diffusion models using discretization and Hessian information.
problem Theoretical foundations and convergence analysis of score-based diffusion models.
method Investigation of various discretization schemes, including Euler, exponential integrators, and midpoint randomization. Proposal of an accelerated sampler based on local linearization method.
result Hessian-based approach achieves faster convergence rates of order $\widetilde{\mathcal{O}}\left(\frac{1}{\varepsilon}
ight)$, significantly improving upon vanilla diffusion models.
We introduce a generic scheme to solve nonconvex optimization problems using gradient-based algorithms originally designed for minimizing convex functions. Even though these methods may originally require convexity to operate, the proposed approach allows one to use them on weakly convex objectives, which covers a larg…
MER algorithm speeds up VI solving with Markovian data.
problem Solving stochastic variational inequalities with Markovian data.
method MER algorithm using multi-scale sampling from a Markovian buffer.
result Achieves faster convergence without knowing Markov chain mixing time.
We propose a generic algorithmic building block to accelerate training of machine learning models on heterogeneous compute systems. Our scheme allows to efficiently employ compute accelerators such as GPUs and FPGAs for the training of large-scale machine learning models, when the training data exceeds their memory cap…
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…
Accelerated Block Coordinate Proximal Gradients with Applications in High Dimensional Statisticsmath.OC
Nonconvex optimization problems arise in different research fields and arouse lots of attention in signal processing, statistics and machine learning. In this work, we explore the accelerated proximal gradient method and some of its variants which have been shown to converge under nonconvex context recently. We show th…
Accelerated Randomized Mirror Descent Algorithms For Composite Non-strongly Convex Optimizationmath.OC
We consider the problem of minimizing the sum of an average function of a large number of smooth convex components and a general, possibly non-differentiable, convex function. Although many methods have been proposed to solve this problem with the assumption that the sum is strongly convex, few methods support the non-…
Unified method for MMD variance estimation improves accuracy and computational efficiency.
problem Variance estimation for MMD in nonparametric testing.
method Unified finite-sample characterization of MMD variance through U-statistic and Hoeffding decomposition; exact acceleration method for univariate case.
result Unified estimators improve accuracy and computational efficiency for MMD variance.
New algorithm PRACTISE accelerates networks with tiny sets, reducing latency by 22%.
problem Accelerating networks with tiny training sets to improve performance and privacy.
method Proposes a new algorithm PRACTISE based on finetune convexity hypothesis and feature mimicking.
result PRACTISE outperforms previous methods by reducing latency by 22% on ImageNet-1k.
In this work, we propose an iterative reconstruction scheme (ALONE - Adaptive Learning Of NEtworks) for 2D radial cine MRI based on ground truth-free unsupervised learning of shallow convolutional neural networks. The network is trained to approximate patches of the current estimate of the solution during the reconstru…
New method accelerates Bayesian imaging using Langevin sampling.
problem Bayesian inference in imaging inverse problems with convex geometry.
method Stochastic relaxed proximal-point iteration targeting posterior distribution.
result Accelerated convergence for -strongly log-concave targets.