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,742 papers · 148 categories
Trend · papers per month
48 results for “recursive stochastic algorithms”
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.
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.
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…
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…
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 .
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 …
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.
Unified framework for analyzing convergence of RSAs using Wasserstein divergence.
problem Analyzing convergence of constant stepsize recursive stochastic algorithms (RSAs).
method Lifting RSA into a higher-dimensional space as a Markov chain and studying the distribution's contraction property with respect to Wasserstein divergence.
result RSAs' iterates' distribution converges to an invariant distribution under certain contraction properties.
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.
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.
Stochastic Recursive Variance Reduction for Efficient Smooth Non-Convex Compositional Optimizationstat.ML
New algorithm reduces complexity for optimizing complex machine learning tasks.
problem Optimizing complex machine learning objectives like reinforcement learning and portfolio management.
method Developed SARAH-Compositional algorithm using Stochastic Recursive Gradient Descent.
result Achieved optimal IFO complexity bounds for stochastic compositional optimization.
Approximating Posterior Predictive Distributions by Averaging Output From Many Particle Filtersstat.ME
Paper uses averaging from many particle filters to approximate posterior predictive distributions.
problem Approximating posterior predictive distributions efficiently and accurately.
method Particle swarm filter algorithm that averages many particle filter approximations.
result Law of large numbers and central limit theorem support the method's effectiveness.
Recursive stochastic algorithms have gained significant attention in the recent past due to data driven applications. Examples include stochastic gradient descent for solving large-scale optimization problems and empirical dynamic programming algorithms for solving Markov decision problems. These recursive stochastic a…
A high-order recombination algorithm for weak approximation of stochastic differential equationsmath.PR
Paper develops a high-order recombination algorithm for financial modeling.
problem Creating accurate approximations of stochastic differential equations in finance.
method High-order recombination method applied to practical financial problems.
result Algorithm effectively avoids explosive growth in support cardinality for high-order approximations.
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.
Online (also called "recursive" or "adaptive") estimation of fixed model parameters in hidden Markov models is a topic of much interest in times series modelling. In this work, we propose an online parameter estimation algorithm that combines two key ideas. The first one, which is deeply rooted in the Expectation-Maxim…
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…
A new method for robust product Markovian quantization overcomes numerical instabilities.
problem Numerical instabilities in the PMQ algorithm limit its adoption, especially for stochastic volatility models.
method Reformulated PMQ as standard vector quantization, applying accelerated Lloyd's algorithm for robustness.
result The method overcomes numerical instabilities and extends applicability to stochastic volatility models.
Paper develops efficient methods for estimating Hessian inverses in stochastic optimization.
problem Estimating the inverse Hessian for convex function minimization.
method Robbins-Monro procedure for recursive estimation of the inverse Hessian.
result Develops universal stochastic Newton methods with improved efficiency.
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…
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…
CEFOL uses deep learning for dynamic programming with recursive utility.
problem Challenges in solving dynamic programming problems with recursive utility.
method Introduces a separate neural network for certainty equivalent, uses first-order optimality conditions to learn value and policy functions.
result CEFOL achieves high accuracy in learning value and policy functions, matching VFI benchmarks.
Paper introduces XBART for nonlinear regression, outperforming XGBoost.
problem Nonlinear regression problems, especially in speed and accuracy.
method Combines Bayesian modeling and recursive partitioning for efficient, accurate predictions.
result XBART provides faster and more accurate predictions than XGBoost.
Stochastic recursive inclusion in two timescales with an application to the Lagrangian dual problemeess.SY
In this paper we present a framework to analyze the asymptotic behavior of two timescale stochastic approximation algorithms including those with set-valued mean fields. This paper builds on the works of Borkar and Perkins & Leslie. The framework presented herein is more general as compared to the synchronous two times…
ROOT-SGD solves convex optimization problems with optimal nonasymptotic and near-optimal asymptotic performance.
problem Solving strongly convex and smooth unconstrained optimization problems using stochastic first-order algorithms.
method ROOT-SGD: Recursive One-Over-T SGD, averaging past stochastic gradients.
result Achieves state-of-the-art performance in both nonasymptotic and asymptotic senses.
Study on private algorithms for saddle point and variational inequalities, improving efficiency and applicability.
problem Private algorithms for solving saddle point and variational inequalities under differential privacy constraints.
method Developed a recursive regularization algorithm for both Euclidean and non-Euclidean setups, providing bounds on strong SP-gap and VI-gap.
result Achieved nearly optimal rates for strong SP-gap and VI-gap under -differential privacy, applicable to various setups.
A new ML algorithm solves complex economic control problems.
problem Solving high-dimensional, finite-horizon stochastic control problems in economics.
method Deep neural network representation of optimal policy functions with three key features.
result Efficiently solves various economic control problems including recursive utility and growth models.
Developed moment estimators for affine stochastic volatility models.
problem Estimating parameters of affine stochastic volatility models.
method Introduced recursive equations for moments and proposed moment estimators.
result Established a central limit theorem and derived asymptotic covariance matrix.
SREDA optimizes complex machine learning problems with fewer evaluations.
problem Finding an optimal point in nonconvex-strongly-concave minimax problems.
method Stochastic Recursive Gradient Descent Ascent (SREDA) with variance reduction.
result Achieves optimal stochastic gradient complexity of O(κ^3ε^-3).
This paper concerns the recursive utility maximization problem under partial information. We first transform our problem under partial information into the one under full information. When the generator of the recursive utility is concave, we adopt the variational formulation of the recursive utility which leads to a s…
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…
New approach solves utility maximization problems using Delta family.
problem Utility maximization in stochastic control problems.
method Directly solving DP equation with Delta function representation.
result Explicit series representation of value function.
Quantization goes Polynomialq-fin.PR
Quantization algorithms have been successfully adopted to option pricing in finance thanks to the high convergence rate of the numerical approximation. In particular, very recently, recursive marginal quantization has been proven to be a flexible and versatile tool when applied to stochastic volatility processes. In th…
Learning a Class of Mixed Linear Regressions: Global Convergence under General Data Conditionsstat.ML
Paper addresses global convergence of MLR estimation under weak data conditions.
problem Learning mixed linear regression models with general data conditions.
method Two-step recursive identification algorithm using least squares and EM principles.
result Global convergence and optimal clustering performance established under general data conditions.
Paper proves large deviation principle for stochastic approximations.
problem Asymptotic estimates of learning algorithm deviations.
method Weak convergence approach to large deviations.
result Identifies appropriate scaling sequence and new representation for rate function.
We consider the minimization of composite objective functions composed of the expectation of quadratic functions and an arbitrary convex function. We study the stochastic dual averaging algorithm with a constant step-size, showing that it leads to a convergence rate of O(1/n) without strong convexity assumptions. This …
Optimal privacy-preserving algorithm for solving saddle point problems.
problem Solving convex-concave stochastic saddle point problems under differential privacy constraints.
method Recursive regularization technique repurposed for saddle point problems, achieving strong gap rate of O(1/√n + √d/nε).
result Achieves nearly optimal strong gap rate of O(1/√n + √d/nε) with gradient complexity O(min{n^2ε^(1.5)/√d, n^(3/2)}).
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…
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.
Solves optimal stopping problem with Poisson constraints using jumps.
problem Optimal stopping with Poisson constraints and jumps.
method Penalized backward stochastic differential equation (PBSDE) with jumps, decomposition method based on Jacod-Pham, comparison theorem of BSDEs with jumps.
result Solves American option pricing in nonlinear markets with Poisson constraints.
Efficient optimization method reduces Full AdaGrad complexity.
problem Computational challenges in Full AdaGrad for large-scale applications.
method Recursive method and streaming variant for parameter updates.
result Significant reduction in complexity and resource demands.
This paper studies recursive ensembles driven by Fibonacci updates, improving learning dynamics.
problem Improving learning dynamics in recursive ensemble learning.
method Develops second-order recursive architectures with Fibonacci-type update flows.
result Establishes global convergence conditions and generalization bounds for recursive ensembles.
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 …
ERM uses energy-based selection to improve recursive reasoning.
problem Lack of principled inference mechanism in recursive models.
method Energy-guided Recursive Model (ERM) introduces Hopfield energies for trajectory selection.
result ERM achieves optimal solutions on various puzzles.
Quantization techniques have been applied in many challenging finance applications, including pricing claims with path dependence and early exercise features, stochastic optimal control, filtering problems and efficient calibration of large derivative books. Recursive Marginal Quantization of the Euler scheme has recen…
We propose a robust, scalable, integrated methodology for community detection and community comparison in graphs. In our procedure, we first embed a graph into an appropriate Euclidean space to obtain a low-dimensional representation, and then cluster the vertices into communities. We next employ nonparametric graph in…
The paper provides mean-square error bounds for stochastic approximation algorithms.
problem Error bounds for recursive equations with Markovian disturbances.
method Analysis of mean-square error for stochastic approximation algorithms.
result Mean-square error achieves the optimal rate of under certain conditions.