We propose a general formalism of iterated random functions with semigroup property, under which exact and approximate Bayesian posterior updates can be viewed as specific instances. A convergence theory for iterated random functions is presented. As an application of the general theory we analyze convergence behaviors…
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 “iterated random functions”
This work's purpose is to understand the dynamics of some social systems whose properties can be captured by certain iterated function systems. To achieve this intension, we start from the theory of iterated function systems, and then we study two specific economic models on random utility function and optimal stochast…
Paper improves worst-case regret bounds for RLSVI in reinforcement learning.
problem Minimizing regret in reinforcement learning with randomized value functions.
method Introduces a clipping variant of Thompson Sampling for RLSVI.
result Achieves a worst-case regret bound.
We study the problem of finding the maximum of a function defined on the nodes of a connected graph. The goal is to identify a node where the function obtains its maximum. We focus on local iterative algorithms, which traverse the nodes of the graph along a path, and the next iterate is chosen from the neighbors of the…
Standard ChIP-seq peak calling pipelines seek to differentiate biochemically reproducible signals of individual genomic elements from background noise. However, reproducibility alone does not imply functional regulation (e.g., enhancer activation, alternative splicing). Here we present a general-purpose, interpretable …
We propose randomized least-squares value iteration (RLSVI) -- a new reinforcement learning algorithm designed to explore and generalize efficiently via linearly parameterized value functions. We explain why versions of least-squares value iteration that use Boltzmann or epsilon-greedy exploration can be highly ineffic…
New method explains GNNs using power iteration clustering.
problem Mysterious mechanism of message passing in GNNs.
method Subspace power iteration clustering (SPIC) models.
result Message passing in GNNs can be understood through power iteration.
Improved RL algorithm reduces regret in large state spaces.
problem Exploration in large or continuous state spaces.
method Optimistically-initialized randomized least-squares value iteration (RLSVI) with function approximation.
result Frequentist regret bound of for low-rank transition dynamics.
Strong stability of ergodic iterations proven without ergodic driving sequence.
problem Ensuring strong stability of ergodic iterations under non-ergodic driving sequences.
method Revisiting processes driven by stationary ergodic sequences, proving strong stability under mild conditions on recursive maps.
result Strong stability of iterations proven without ergodic driving sequence.
New method reduces variance in random coordinate descent for Langevin Monte Carlo.
problem Efficient sampling from log-concave distributions in high dimensions.
method Introduces RCAD, a variance reduction technique for RCD-LMC.
result RCAD-O-LMC and RCAD-U-LMC converge within the same number of iterations as classical LMC methods, saving computational cost.
Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimizationmath.OC
Improved shuffling gradient methods converge faster for nonsmooth convex optimization.
problem Improving convergence rates for nonsmooth convex optimization problems.
method Analysis of shuffling gradient methods, focusing on Random Reshuffle and Single Shuffle strategies.
result Shuffling gradient methods, particularly Random Reshuffle and Single Shuffle, converge faster than Proximal Gradient Descent for nonsmooth convex optimization.
RANDPOL uses randomized networks for efficient reinforcement learning in continuous state and action MDPs.
problem Efficient reinforcement learning in environments with continuous state and action spaces.
method RANDPOL uses randomized function approximation to represent policy and value functions, providing finite time guarantees and improved numerical performance.
result RANDPOL achieves better numerical performance and provides finite time guarantees compared to deep neural network based algorithms.
Paper refutes conjecture on tensor power iteration convergence in overcomplete models.
problem Understanding convergence of tensor power iteration in overcomplete random tensors.
method Analysis of tensor power iteration dynamics from random initialization.
result Polynomially many steps are necessary for convergence, refutes logarithmic conjecture.
We investigate the random dynamics of rational maps on the Riemann sphere and the dynamics of semigroups of rational maps on the Riemann sphere. We show that regarding random complex dynamics of polynomials, in most cases, the chaos of the averaged system disappears, due to the cooperation of the generators. We investi…
This paper improves privacy bounds for DP algorithms using -DP.
problem Difficulty in analyzing randomness in DP algorithms due to mixture distributions.
method Derives a closed-form expression for trade-off functions and analyzes -DP.
result Enhances privacy of DP-GD with random initialization and shuffling models.
The paper analyzes learning rates for non-irreducible Markov chains.
problem Real-world data often violates i.i.d. assumptions.
method Examines iterated random functions and contractive functions.
result Derives data-distribution dependent learning rates.
Inexact acquisition solutions in BO lead to sublinear cumulative regret.
problem Inexact maximization of acquisition functions in Bayesian optimization.
method Define inaccuracy measure, establish cumulative regret bounds for GP-UCB and GP-TS.
result Inexact BO algorithms can achieve sublinear cumulative regret under appropriate inaccuracy conditions.
New RL algorithm explains why deep learning works in stochastic environments.
problem Why deep RL algorithms perform well in practice despite using random exploration.
method Introducing SQIRL, an iterative RL algorithm that separates exploration and learning.
result Effective horizon explains why deep RL works in stochastic environments.
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…
Enhances LMC for log-concave sampling, reducing computational cost.
problem High computational cost of LMC for high-dimensional problems.
method Random coordinate descent (RCD) combined with variance reduction techniques (SAGA, SVRG).
result Achieves computational cost reduction compared to classical LMC, same number of iterations as LMC.
New convergence rates for shuffling gradient methods without strong convexity.
problem Theoretical gap between shuffling gradient methods' empirical success and established convergence rates.
method Proved last-iterate convergence rates for shuffling gradient methods using function value gap.
result First last-iterate convergence rates for shuffling gradient methods without strong convexity.
New method solves constrained optimization problems efficiently.
problem Equality-constrained nonlinear, nonconvex optimization problems.
method Adaptive inexact Newton method with randomized iterative sketching.
result Global almost sure convergence and local linear/superlinear convergence.
Improved SVRG for quadratic functions achieves better performance and running times.
problem Minimizing quadratic functions with a specific type of Hessian matrix.
method Variant of SVRG algorithm for quadratic functions with improved analysis.
result Improved performance and running times for quadratic functions compared to state-of-the-art methods.
The Douglas Rachford algorithm is an algorithm that converges to a minimizer of a sum of two convex functions. The algorithm consists in fixed point iterations involving computations of the proximity operators of the two functions separately. The paper investigates a stochastic version of the algorithm where both funct…
A new method for LDA using randomized Kaczmarz improves accuracy for large datasets.
problem Efficiently performing LDA on large datasets.
method Randomized Kaczmarz method applied to linear discriminant analysis.
result The method achieves comparable accuracy to full data LDA.
In this paper we propose the notion of continuous-time dynamic spectral risk-measure (DSR). Adopting a Poisson random measure setting, we define this class of dynamic coherent risk-measures in terms of certain backward stochastic differential equations. By establishing a functional limit theorem, we show that DSRs may …
In this paper we present a convergence rate analysis of inexact variants of several randomized iterative methods. Among the methods studied are: stochastic gradient descent, stochastic Newton, stochastic proximal point and stochastic subspace ascent. A common feature of these methods is that in their update rule a cert…
Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problemsmath.OC
New algorithms solve complex minimax problems without needing derivatives.
problem Solving nonconvex-concave minimax problems efficiently.
method Zeroth-order alternating and proximal gradient algorithms.
result Iteration complexity and function value estimation bounds established.
New algorithm trains deep neural networks without global optimization.
problem Training deep neural networks efficiently and without global optimization.
method Uses random complex exponential activation functions and Markov Chain Monte Carlo sampling.
result Consistently attains theoretical approximation rate for residual networks.
We study the performance of a family of randomized parallel coordinate descent methods for minimizing the sum of a nonsmooth and separable convex functions. The problem class includes as a special case L1-regularized L1 regression and the minimization of the exponential loss ("AdaBoost problem"). We assume the input da…
In this paper we develop a randomized block-coordinate descent method for minimizing the sum of a smooth and a simple nonsmooth block-separable convex function and prove that it obtains an -accurate solution with probability at least in at most iterations, where is the numbe…
Sparser Random Feature Models via IMP (ShRIMP) efficiently learns sparse models for high-dimensional data.
problem Learning sparse models for high-dimensional data with sparse variable dependencies.
method Iterative Magnitude Pruning applied to Random Feature Models.
result ShRIMP achieves better or competitive test accuracy compared to state-of-the-art methods.
Efficient methods for sparse random projections improve classification accuracy in very high-dimensional data.
problem Handling very high-dimensional sparse data efficiently.
method Non-iterative and iterative classification methods using sparse random projections and Jaccard kernel.
result Non-iterative methods yield larger, more accurate models than iterative methods.
The paper approximates financial derivatives using neural networks and iterated integrals.
problem Approximating -integrable financial derivatives.
method Using iterated Stratonovich integrals and neural networks.
result Approximate solutions to the -hedging problem.
SnapBoost uses random base hypothesis classes to improve gradient boosting performance.
problem Improving gradient boosting performance.
method Heterogeneous Newton Boosting Machine (HNBM) with variable base hypothesis classes.
result SnapBoost achieves better generalization loss than competing frameworks.
We address the problem of automatic generation of features for value function approximation. Bellman Error Basis Functions (BEBFs) have been shown to improve the error of policy evaluation with function approximation, with a convergence rate similar to that of value iteration. We propose a simple, fast and robust algor…
ParPIC clusters directed graphs using random walks and diffusion operators.
problem Challenges in vertex-level clustering for directed graphs due to edge directionality.
method Parametrized Power-Iteration Clustering (ParPIC) based on reversible random walks and diffusion operators.
result ParPIC achieves competitive clustering accuracy with improved scalability compared to spectral and teleportation-based methods.
This paper analyzes DONE, an online optimization algorithm that iteratively minimizes an unknown function based on costly and noisy measurements. The algorithm maintains a surrogate of the unknown function in the form of a random Fourier expansion (RFE). The surrogate is updated whenever a new measurement is available,…
We consider the dynamics of rational semigroups (semigroups of rational maps) on the Riemann sphere. We provide proof that a random backward iteration algorithm to draw the pictures of the Julia sets, previously proven to work in the context of iteration of a rational map of degree two or more, extends to finitely gene…
Distributed learning with random features and gradient descent improves performance and reduces memory usage.
problem Improving generalization in decentralized learning with limited memory.
method Distributed Gradient Descent with Random Features and Implicit Regularization.
result High probability bounds on predictive performance with optimal statistical rates.
WITCHcraft improves PGD attacks with random step size, enhancing efficiency.
problem Efficiently crafting adversarial attacks on neural networks.
method Variant of PGD using random step size.
result Superior performance to classical PGD without additional computational cost.
Iteratively reweighted algorithm is a popular algorithm for solving a large class of optimization problems whose objective is the sum of a Lipschitz differentiable loss function and a possibly nonconvex sparsity inducing regularizer. In this paper, motivated by the success of extrapolation techniques in accele…
A new method solves optimization problems on the generalized Stiefel manifold using random estimates of B.
problem Optimization over the generalized Stiefel manifold in applications like CCA, ICA, and GEVP.
method Cheap stochastic iterative method that converges to critical points on the manifold.
result The method achieves the same convergence rates as Riemannian optimization but with lower per-iteration cost.
Optimizes convergence rate of stochastic proximal algorithms for composite convex problems.
problem Solving composite convex optimization problems with composite regularizers.
method Analyzed proximal stochastic gradient method and randomized incremental proximal method under relaxed variance assumptions.
result Proves convergence rate for last iterate of both algorithms under componentwise convexity and smoothness.
We study the trade-offs between convergence rate and robustness to gradient errors in designing a first-order algorithm. We focus on gradient descent (GD) and accelerated gradient (AG) methods for minimizing strongly convex functions when the gradient has random errors in the form of additive white noise. With gradient…
A machine learning method to discover physical theories from data.
problem Discovering explicit analytic equations from physical data.
method Iterative machine learning approach using random combinations of highly correlated expressions.
result Extracting explicit analytic equations from physical data.
Gradient descent with small random init mimics spectral methods for low-rank matrix recovery.
problem Reconstructing a low-rank matrix from few measurements.
method Gradient descent with small random initialization followed by a few iterations.
result Gradient descent from small random init converges to a well-generalizing solution.
Study reveals three limiting regimes for neural network functionals.
problem Understanding the behavior of functionals of random neural networks.
method Central and non-central limit theorems, Hermite expansions, Diagram Formula, Stein-Malliavin techniques.
result Three distinct limiting regimes based on fixed points of covariance function.