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…
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 algorithms”
Hamiltonian dynamics-based algorithms achieve deterministic and accelerated convergence for convex optimization.
problem Accelerating convex optimization
method Hamiltonian dynamics
result Hamiltonian dynamics-based algorithms achieve deterministic and accelerated convergence for convex optimization.
A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossipmath.OC
Continuized Nesterov acceleration accelerates stochastic gradient descent and gossip algorithms.
problem Improving the convergence rate of stochastic gradient descent and gossip algorithms.
method Introducing a continuized variant of Nesterov acceleration, which mixes variables continuously and takes gradient steps at random times.
result The continuized Nesterov acceleration achieves convergence rates similar to Nesterov's original acceleration but with random parameters.
Two new differentially private optimization algorithms derived from accelerated methods.
problem Improving privacy in optimization algorithms while maintaining convergence rates.
method Polyak's heavy ball method and Nesterov's accelerated gradient method with differential privacy.
result The proposed algorithms outperform existing differentially private optimization methods.
We present an accelerated algorithm for hierarchical density based clustering. Our new algorithm improves upon HDBSCAN*, which itself provided a significant qualitative improvement over the popular DBSCAN algorithm. The accelerated HDBSCAN* algorithm provides comparable performance to DBSCAN, while supporting variable …
We consider gradient descent with `momentum', a widely used method for loss function minimization in machine learning. This method is often used with `Nesterov acceleration', meaning that the gradient is evaluated not at the current position in parameter space, but at the estimated position after one step. In this work…
Octagon map accelerates diagonal changes algorithm.
problem Improving the efficiency of diagonal changes algorithm.
method Octagon Farey map as an acceleration.
result Octagon map accelerates diagonal changes algorithm.
PF-LaCG removes the need for knowing smoothness and strong convexity parameters for locally accelerated CG.
problem Locally accelerated CG requires knowledge of smoothness and strong convexity parameters.
method Parameter-Free Locally Accelerated CG (PF-LaCG) algorithm.
result PF-LaCG achieves local acceleration without requiring knowledge of smoothness and strong convexity parameters.
Improved Analysis of the Accelerated Noisy Power Method with Applications to Decentralized PCAstat.ML
Improved analysis of accelerated noisy power method for PCA.
problem Inexact matrix-vector products in PCA settings.
method Improved analysis of Accelerated Noisy Power Method under milder perturbation conditions.
result Worst-case optimal convergence rate with relaxed noise conditions.
Acceleration via silver step-size on Riemannian manifolds with applications to Wasserstein spacemath.OC
New algorithm accelerates optimization on Riemannian manifolds, including Wasserstein space.
problem Accelerating optimization methods in Riemannian geometry.
method Dynamic stepsize algorithms on Riemannian manifolds with specific vector transport.
result First provable accelerated gradient method in Wasserstein space.
Accelerated gradient method's stability deteriorates exponentially with steps.
problem Algorithmic stability of Nesterov's accelerated gradient method.
method Analysis of two notions of algorithmic stability for Nesterov's accelerated gradient method.
result Stability of Nesterov's accelerated method deteriorates exponentially with the number of gradient steps.
Accelerates sampling from Gibbs distributions using ARWP method.
problem Sampling from Gibbs distributions efficiently.
method ARWP method, combining Nesterov acceleration and regularized Wasserstein proximal.
result ARWP exhibits higher contraction rate and faster tail exploration.
Accelerated Randomized Coordinate Descent Algorithms for Stochastic Optimization and Online Learningcs.LG
We propose accelerated randomized coordinate descent algorithms for stochastic optimization and online learning. Our algorithms have significantly less per-iteration complexity than the known accelerated gradient algorithms. The proposed algorithms for online learning have better regret performance than the known rando…
Paper discovers structural dynamics equations from only acceleration data.
problem Discovering equations from only acceleration measurements in structural dynamics.
method Library-based approach with Approximate Bayesian Computation (ABC) prioritizing parsimonious models.
result Efficacy demonstrated in four structural dynamics examples, including linear and nonlinear systems.
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 accelerate MAP inference in Markov fields with faster convergence.
problem Finding the most likely configuration in discrete-valued Markov random fields.
method Entropy-regularized linear programming with accelerated gradient methods.
result Accelerated algorithms find optimal solutions faster, especially when the LP is tight.
We propose a novel method to accelerate Lloyd's algorithm for K-Means clustering. Unlike previous acceleration approaches that reduce computational cost per iterations or improve initialization, our approach is focused on reducing the number of iterations required for convergence. This is achieved by treating the assig…
Accelerates policy optimization in RL with optimistic and adaptive updates.
problem Improving policy optimization methods in reinforcement learning.
method Integrates foresight into policy improvement step via optimistic and adaptive updates.
result Designs an optimistic policy gradient algorithm, adaptive via meta-gradient learning.
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 …
Hamiltonian Descent Algorithms for Optimization: Accelerated Rates via Randomized Integration Timemath.OC
HF-opt uses Hamiltonian dynamics to optimize functions, achieving accelerated rates with randomized integration time.
problem Optimizing functions efficiently and accelerating convergence rates.
method Randomized Hamiltonian flow (RHF) with accelerated convergence rates.
result RHGD achieves accelerated convergence rates similar to Nesterov's AGD.
Anderson acceleration (or Anderson mixing) is an efficient acceleration method for fixed point iterations , e.g., gradient descent can be viewed as iteratively applying the operation . It is known that Anderson acceleration is quite efficient in practice and can be viewed…
Accelerates TD learning for long-horizon reinforcement learning problems.
problem Slow convergence of conventional TD learning in long-horizon tasks.
method Introduces PID Accelerated Temporal Difference (PID TD) learning algorithms.
result Accelerates convergence of TD learning compared to conventional methods.
Improved first-order algorithm for entropy regularized OT with faster convergence.
problem Solving entropy regularized optimal transport efficiently.
method Accelerated primal-dual stochastic mirror descent algorithm with variance reduction.
result Improved rate from to .
Accelerates MMLE using SVGD with Nesterov acceleration.
problem Maximum Marginal Likelihood Estimation optimization.
method Stein variational gradient descent with Nesterov acceleration.
result Consistently accelerates convergence across various tasks.
Accelerated RPCholesky speeds up kernel matrix approximations.
problem Efficiently approximating large kernel matrices.
method Accelerated randomly pivoted Cholesky (RPCholesky) with block matrix computations and rejection sampling.
result Approximates kernel matrices up to 40 times faster.
AGNES accelerates gradient descent with noisy gradients.
problem Minimizing smooth convex and strongly convex functions with noisy gradients.
method Generalization of Nesterov's accelerated gradient descent algorithm for noisy conditions.
result AGNES achieves acceleration for noisy gradients with a constant of proportionality up to 1.
Accelerates optimization in asynchronous systems with sparse updates.
problem Optimizing finite-sum objectives in asynchronous lock-free environments.
method New accelerated SVRG variant with sparse updates.
result Achieves optimal incremental gradient complexity.
New methods accelerate gradient descent for convex and strongly convex functions.
problem Improving convergence rates of gradient-based optimization methods.
method Formulated two classes of first-order algorithms with Lyapunov analyses and Hamiltonian assisted gradient method.
result Achieved accelerated convergence rates matching Nesterov's methods in strongly and general convex settings.
Memory bandwidth bottleneck is a major challenges in processing machine learning (ML) algorithms. In-memory acceleration has potential to address this problem; however, it needs to address two challenges. First, in-memory accelerator should be general enough to support a large set of different ML algorithms. Second, it…
We formulate gradient-based Markov chain Monte Carlo (MCMC) sampling as optimization on the space of probability measures, with Kullback-Leibler (KL) divergence as the objective functional. We show that an underdamped form of the Langevin algorithm performs accelerated gradient descent in this metric. To characterize t…
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 …
Accelerating Non-Negative and Bounded-Variable Linear Regression Algorithms with Safe Screeningcs.LG
The paper accelerates regression algorithms by identifying saturated coordinates.
problem Non-negative and bounded-variable linear regression problems.
method Safe screening technique to identify saturated coordinates.
result The approach provides theoretical guarantees for identifying saturated coordinates.
Matrix completion is a widely used technique for image inpainting and personalized recommender system, etc. In this work, we focus on accelerating the matrix completion using faster randomized singular value decomposition (rSVD). Firstly, two fast randomized algorithms (rSVD-PI and rSVD- BKI) are proposed for handling …
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…
Hardware-accelerated RBM solves large combinatorial problems and integer factorization.
problem Solving large combinatorial optimization and integer factorization problems.
method Logically synthesized RBM architecture, hardware acceleration, and efficient training methods.
result Hardware-accelerated RBM factorizes 16-bit numbers with 10000x speed and 32x power improvements.
New algorithms accelerate solving nonlinear matrix decomposition with ReLU.
problem Nonlinear matrix decomposition with ReLU function.
method Two new algorithms: A-NMD and 3B-NMD, with adaptive extrapolation and block parametrization.
result Effective algorithms accelerate solving ReLU-NMD problems.
ASVGD accelerates SVGD for efficient sampling.
problem Slow SVGD in high-dimensional sampling.
method Accelerated gradient flow in a metric space of probability densities, using Nesterov's method and momentum-based updates.
result ASVGD outperforms SVGD and other methods in sampling efficiency.
We accelerate PMD algorithms for reinforcement learning using functional methods.
problem Improving reinforcement learning algorithms for large-scale optimization.
method Proposed a momentum-based update for PMD algorithms leveraging duality.
result The proposed method accelerates reinforcement learning algorithms.
SVRN accelerates Newton methods by reducing variance and improving performance.
problem Improving the efficiency of Newton methods for large-scale optimization problems.
method Stochastic Variance-Reduced Newton (SVRN) algorithm that accelerates Subsampled Newton and Iterative Hessian Sketch algorithms.
result SVRN accelerates Newton methods by reducing the number of passes over the data, achieving a significant improvement in performance.
Paper solves robust multi-dimensional scaling with accelerated projections.
problem Localize point locations from noisy pairwise distances.
method Alternating projections with tangent space acceleration.
result Linear convergence of reconstructed points to original points.
Momentum accelerates Frank Wolfe algorithms on certain problems.
problem Improving convergence rate of Frank Wolfe algorithms.
method Introducing momentum into Frank Wolfe algorithms and proving faster convergence rate.
result Accelerated Frank Wolfe (AFW) converges with a faster rate of .
A Python package for GPU-accelerated signature kernel computation.
problem Efficient computation of signature kernels for sequential data.
method GPU-accelerated algorithms and tensor sketches.
result New algorithm outperforms existing methods.
Recent studies incorporate Nesterov's accelerated gradient method for the acceleration of gradient based training. The Nesterov's Accelerated Quasi-Newton (NAQ) method has shown to drastically improve the convergence speed compared to the conventional quasi-Newton method. This paper implements NAQ for non-convex optimi…
Improved SGD for non-strongly-convex regression with faster convergence.
problem Non-strongly-convex least squares regression problems.
method Modified accelerated gradient descent.
result Achieves optimal prediction error rates of and forgets initial conditions faster to .
New algorithms accelerate SVGD convergence using deep unfolding.
problem Improving the speed of SVGD convergence.
method Integrating deep unfolding into SVGD for parameter learning.
result Proposed algorithms achieve faster convergence in various tasks.
Gradient Boosting Machine (GBM) is an extremely powerful supervised learning algorithm that is widely used in practice. GBM routinely features as a leading algorithm in machine learning competitions such as Kaggle and the KDDCup. In this work, we propose Accelerated Gradient Boosting Machine (AGBM) by incorporating Nes…
New study on No-U-Turn Sampler for accelerated mixing in Hamiltonian Monte Carlo.
problem Achieving accelerated convergence in Hamiltonian Monte Carlo.
method Combining concentration of measure and coupling analysis for mixing.
result Rigorous mixing guarantees for the No-U-Turn Sampler in certain Gaussian distributions.
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…