In this paper, we study and analyze the mini-batch version of StochAstic Recursive grAdient algoritHm (SARAH), a method employing the stochastic recursive gradient, for solving empirical loss minimization for the case of nonconvex losses. We provide a sublinear convergence rate (to stationary points) for general noncon…
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,695 papers · 148 categories
Trend · papers per month
48 results for “recursive gradients”
STORM-PG uses momentum for faster policy gradient updates.
problem Improving policy gradient methods for reinforcement learning.
method Introduces STORM-PG, a SARAH-based algorithm with exponential moving average.
result Achieves sample complexity, matching best-known rate.
A new algorithm SRG-DQN reduces variance in deep Q-learning.
problem Inaccurate estimation of anchor points in SVRG for deep Q-learning.
method Introduces recursive gradient variance reduction for stochastic gradient updates.
result Demonstrates improved efficiency and effectiveness of SRG-DQN on reinforcement learning tasks.
Tab-TRM uses recursive model for insurance pricing on tabular data.
problem Insurance pricing on tabular data.
method Adapts recursive latent reasoning to insurance modeling using a compact, parameter-efficient network.
result Improves insurance pricing accuracy using iterative refinement of latent tokens.
New method finds near-optimal solutions for non-convex optimization problems.
problem Finding near-optimal solutions for non-convex optimization problems.
method Riemannian stochastic recursive momentum method
result Achieves a near-optimal complexity of .
A new method optimizes diffusion models with recursive likelihood ratios.
problem Efficiently aligning pre-trained diffusion models for specific applications.
method Recursive Likelihood Ratio (RLR) optimizer for Half-Order (HO) fine-tuning.
result The RLR method achieves unbiased and lower-variance gradients, improving model performance.
In this paper, we propose a StochAstic Recursive grAdient algoritHm (SARAH), as well as its practical variant SARAH+, as a novel approach to the finite-sum minimization problems. Different from the vanilla SGD and other modern stochastic methods such as SVRG, S2GD, SAG and SAGA, SARAH admits a simple recursive framewor…
New ODE solvers improve training efficiency and accuracy.
problem Training Neural ODEs requires efficient and accurate gradient calculation.
method Presented algebraically reversible ODE solvers that are time and memory efficient, calculate exact gradients, and are numerically stable.
result Reversible solvers strictly improve upon previous architectures in efficiency and accuracy.
Estimates and optimizes UBSR risk in recursive settings.
problem Estimating and optimizing UBSR risk in a recursive setting with one-at-a-time samples.
method Casts UBSR as a root finding problem, uses stochastic approximation and gradient descent.
result Derives non-asymptotic bounds on estimation and optimization errors.
This text investigates relations between two well-known family of algorithms, matrix factorisations and recursive linear filters, by describing a probabilistic model in which approximate inference corresponds to a matrix factorisation algorithm. Using the probabilistic model, we derive a matrix factorisation algorithm …
Stochastic Variance-Reduced Cubic regularization (SVRC) algorithms have received increasing attention due to its improved gradient/Hessian complexities (i.e., number of queries to stochastic gradient/Hessian oracles) to find local minima for nonconvex finite-sum optimization. However, it is unclear whether existing SVR…
This paper focuses on projection-free methods for solving smooth Online Convex Optimization (OCO) problems. Existing projection-free methods either achieve suboptimal regret bounds or have high per-iteration computational costs. To fill this gap, two efficient projection-free online methods called ORGFW and MORGFW are …
Paper develops probabilistic bounds for a stochastic gradient algorithm in non-convex problems.
problem Stochastic optimization in non-convex finite sum problems.
method Develops a new dimension-free Azuma-Hoeffding type bound for a martingale difference sequence.
result Empirical results show superior probabilistic performance of Prob-SARAH compared to other algorithms.
A new recursive mixture estimation algorithm improves VAE inference efficiency and accuracy.
problem Inaccurate posterior approximation in traditional VAEs.
method Recursive mixture estimation algorithm using functional gradient approach for iterative component selection.
result Significantly higher test data likelihood compared to state-of-the-art methods on benchmark datasets.
Paper presents novel online MTL methods using WRLS and OSLSSVR.
problem Online Multi-Task Learning (MTL) Regression Problems
method Develops recursive versions of WRLS and OSLSSVR for MTL.
result Achieves exact and approximate recursions with quadratic cost.
New algorithms reduce bilevel optimization complexity to ε^(-1.5).
problem Efficiently solving bilevel optimization problems in machine learning.
method Proposed two new algorithms: one using momentum-based recursive iterations, the other using recursive gradient estimations.
result Achieved computational complexity of ε^(-1.5), significantly faster than previous methods.
New method tracks time-varying parameters in data.
problem Tracking unknown time-varying parameters in data.
method Stochastic gradient descent-based recursive scheme with log-likelihood as gain function.
result Convergence in mean-square error in a suitable neighborhood of the unknown parameter.
DESTRESS optimizes decentralized nonconvex optimization with optimal IFO complexity and efficient communication.
problem Decentralized nonconvex finite-sum optimization in multi-agent systems.
method DESTRESS uses stochastic recursive gradient updates, gradient tracking, and careful hyper-parameter choices to achieve optimal IFO complexity with efficient communication.
result DESTRESS matches the optimal IFO complexity of centralized algorithms while maintaining communication efficiency.
ORFit trains models on streaming data with one pass, minimizing memory and computational costs.
problem Training large models on a stream of data without retraining on previous data.
method Orthogonal Recursive Fitting (ORFit) using orthogonal gradient descent and recursive least-squares.
result ORFit updates parameters orthogonally to past gradients, leading to efficient memory and computational usage.
We introduce Recurrent Predictive State Policy (RPSP) networks, a recurrent architecture that brings insights from predictive state representations to reinforcement learning in partially observable environments. Predictive state policy networks consist of a recursive filter, which keeps track of a belief about the stat…
Novel method recursively partitions sample space for density estimation.
problem Estimating complex density functions efficiently and accurately.
method Recursive partitioning of the sample space, asymptotically exact.
result Asymptotically exact approximation of any density function.
We consider nonconvex-concave minimax optimization problems of the form , where is strongly-concave in but possibly nonconvex in and is a convex and compact set. We focus on the stochastic setting, where we can only access an…
GT-SARAH optimizes decentralized non-convex problems with recursive variance reduction.
problem Decentralized non-convex optimization of functions over a network.
method Stochastic first-order gradient method with SARAH variance reduction and gradient tracking.
result Achieves -accurate first-order stationary point with improved gradient complexity.
Continuous optimization is an important problem in many areas of AI, including vision, robotics, probabilistic inference, and machine learning. Unfortunately, most real-world optimization problems are nonconvex, causing standard convex techniques to find only local optima, even with extensions like random restarts and …
Researchers study heavy-tail properties of SGD using stochastic recurrence equations.
problem Analyzing heavy-tail properties of Stochastic Gradient Descent (SGD).
method Modeling SGD iterations as multivariate affine stochastic recursions and applying the theory of irreducible-proximal (i-p) matrices.
result Extended results of Gürbüzbalaban et al. (2020) by using the theory of i-p matrices.
Greedy training of recursive partitioning estimators faces a computational barrier when the true function doesn't satisfy a specific property.
problem Computational inefficiency of greedy training for recursive partitioning estimators.
method Analysis of greedy training for sparse regression functions over binary features.
result Greedy training requires exponential samples when the true function doesn't satisfy a specific property (MSP), but only logarithmic samples when it does.
We analyze stochastic gradient algorithms for optimizing nonconvex problems. In particular, our goal is to find local minima (second-order stationary points) instead of just finding first-order stationary points which may be some bad unstable saddle points. We show that a simple perturbed version of stochastic recursiv…
Emergence in non-neural models: grokking modular arithmetic via average gradient outer productstat.ML
Recursive Feature Machines show grokking in modular arithmetic without neural networks.
problem Grokking in modular arithmetic tasks.
method Recursive Feature Machines (RFM) with Average Gradient Outer Product (AGOP).
result RFM and neural networks learn block-circulant features to solve modular arithmetic.
Clustering with fast algorithms large samples of high dimensional data is an important challenge in computational statistics. Borrowing ideas from MacQueen (1967) who introduced a sequential version of the -means algorithm, a new class of recursive stochastic gradient algorithms designed for the -medians loss cri…
Asymptotic Properties of Recursive Maximum Likelihood Estimation in Non-Linear State-Space Modelsmath.ST
Using stochastic gradient search and the optimal filter derivative, it is possible to perform recursive (i.e., online) maximum likelihood estimation in a non-linear state-space model. As the optimal filter and its derivative are analytically intractable for such a model, they need to be approximated numerically. In [Po…
Introduces a new theoretical framework for exponential smoothing.
problem Theoretical foundation and robustness of simple exponential smoothing.
method Stochastic gradient ascent to optimize Gaussian log-likelihood functions.
result Simple exponential smoothing converges to the trend of a trend-stationary process.
Recursive Maximum Likelihood Estimation for Interacting Particle Systems using Virtual Particlesstat.ME
Estimates log-likelihood of interacting particle systems using virtual particles.
problem Inconsistent estimation of finite-particle log-likelihood in large particle systems.
method Stochastic gradient estimate using continuous trajectory and virtual particle systems.
result Convergence to stationary points of limiting mean-field system's log-likelihood.
A new algorithm for learning shallow neural networks with infinite width.
problem Learning shallow over-parameterized neural networks.
method Sinkhorn proximal algorithm approximating mean field learning dynamics.
result The algorithm performs gradient descent of the free energy associated with the risk functional.
The asymptotic behavior of the stochastic gradient algorithm with a biased gradient estimator is analyzed. Relying on arguments based on the dynamic system theory (chain-recurrence) and the differential geometry (Yomdin theorem and Lojasiewicz inequality), tight bounds on the asymptotic bias of the iterates generated b…
StochAstic Recursive grAdient algoritHm (SARAH), originally proposed for convex optimization and also proven to be effective for general nonconvex optimization, has received great attention due to its simple recursive framework for updating stochastic gradient estimates. The performance of SARAH significantly depends o…
Training deep neural networks on large-scale datasets requires significant hardware resources whose costs (even on cloud platforms) put them out of reach of smaller organizations, groups, and individuals. Backpropagation, the workhorse for training these networks, is an inherently sequential process that is difficult t…
Explains gradient descent methods and their convergence, focusing on simple analysis.
problem Understanding and analyzing gradient descent methods and their variants.
method Elementary mathematical analysis focusing on structures and assumptions of objective functions.
result Unified convergence analysis of various gradient descent methods and variants.
Recursive neural networks have widely been used by researchers to handle applications with recursively or hierarchically structured data. However, embedded control flow deep learning frameworks such as TensorFlow, Theano, Caffe2, and MXNet fail to efficiently represent and execute such neural networks, due to lack of s…
Transformers solve parity problems efficiently with step-by-step reasoning.
problem Training transformers to solve complex, recursive problems like parity.
method Training a one-layer transformer to solve -parity, incorporating intermediate parities into the loss function, and using teacher forcing or augmented data.
result Transformers can learn parity in one gradient update with intermediate supervision or self-consistency checks.
Gradient descent with chaotic perturbations improves generalization.
problem Improving generalization of gradient descent.
method Introducing chaotic perturbations to gradient descent to achieve improved generalization.
result Gradient descent with chaotic perturbations converges to a heavy-tailed SDE, leading to improved generalization.
The study examines neural networks with random weights and biases, finding that depth-to-width ratio controls fluctuations and correlations.
problem Exploring the exploding and vanishing gradient problem in neural networks with random weights and biases.
method Sharp estimates of joint cumulants and solving cumulant recursions in powers of 1/n.
result The depth-to-width ratio plays a crucial role in controlling fluctuations and correlations, leading to the occurrence of exploding and vanishing gradients.
Humans are capable of attributing latent mental contents such as beliefs or intentions to others. The social skill is critical in daily life for reasoning about the potential consequences of others' behaviors so as to plan ahead. It is known that humans use such reasoning ability recursively by considering what others …
Recent years have seen increased interest in performance guarantees of gradient descent algorithms for non-convex optimization. A number of works have uncovered that gradient noise plays a critical role in the ability of gradient descent recursions to efficiently escape saddle-points and reach second-order stationary p…
Farey Recursive Functionsmath.GT
Paper defines Farey Recursive Functions and explores their properties.
problem Understanding recursive functions on rationals.
method Defined and studied Farey Recursive Functions using Farey graph.
result Farey Recursive Functions naturally connect to 2-bridge knots and links.
Paper addresses private online convex optimization with optimal algorithms in various geometries and high-dimensional bandits.
problem Private online convex optimization with streaming and continual release data.
method Proposes a private variant of online Frank-Wolfe algorithm with recursive gradients for variance reduction.
result Achieves optimal excess risk in linear time for and state-of-the-art excess risk for .
Some Generalizations of Mirzakhani's Recursion and Masur-Veech Volumes via Topological Recursionsmath-ph
The paper explores generalizations of Mirzakhani's recursion and computes volumes for physical gravity models.
problem Computing volumes for physical gravity models.
method Topological recursion and physical two-dimensional gravity models.
result Derivation of Virasoro constraints and cut-and-join equations for generalized Mirzakhani's recursions.
We introduce a dynamic optimization framework to analyze optimal portfolio allocations within an information driven contagious distress model. The investor allocates his wealth across several stocks whose growth rates and distress intensities are driven by a hidden Markov chain, and also influenced by the distress stat…
The paper analyzes SGD with dropout regularization in linear models, proving asymptotic properties and providing inference tools.
problem Analyzing the behavior of SGD with dropout regularization in linear models.
method Establishing geometric-moment contraction (GMC) and proving quenched central limit theorems (CLT).
result The existence of a unique stationary distribution and asymptotic normality results for SGD with dropout.