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…
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 “iterated random function systems”
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.
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…
New study shows faster convergence of SGD and Kaczmarz methods.
problem Improving convergence rates of iterative linear system solvers.
method Last-iterate convergence analysis of SGD with greedy step size over smooth quadratics.
result The -th iterate attains an convergence rate.
Recurrent iterated function systems (RIFSs) are improvements of iterated function systems (IFSs) using elements of the theory of Marcovian stochastic processes which can produce more natural looking images. We construct new RIFSs consisting substantially of a vertical contraction factor function and nonlinear transform…
The paper studies random dynamical systems of polynomial automorphisms on C^2 and finds mean stability.
problem Random dynamical systems of polynomial automorphisms on C^2.
method Generic random dynamical systems of polynomial automorphisms are shown to have mean stability.
result A generic random dynamical system of polynomial automorphisms on C^2 has mean stability.
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…
We present RandomizedCCA, a randomized algorithm for computing canonical analysis, suitable for large datasets stored either out of core or on a distributed file system. Accurate results can be obtained in as few as two data passes, which is relevant for distributed processing frameworks in which iteration is expensive…
We investigate random complex dynamics of rational or polynomial maps on the Riemann sphere. We show that regarding random complex dynamics of polynomials, generically, the chaos of the averaged system disappears at any point in the Riemann sphere due to the automatic coopeartion of many kinds of maps in the system, ev…
Deep networks analyzed using IFS theory for stability and generalization.
problem Stability and generalization of deep neural networks.
method Viewing deep architectures as place-dependent IFS and applying results from random dynamical systems.
result Derivation of a Wasserstein generalization bound and a new training objective.
Exponential distribution is ubiquitous in the framework of multi-agent systems. Usually, it appears as an equilibrium state in the asymptotic time evolution of statistical systems. It has been explained from very different perspectives. In statistical physics, it is obtained from the principle of maximum entropy. In th…
The paper proposes a new auto-regressive model for multivariate distributional time series.
problem Statistical analysis of multivariate time series of probability measures.
method Wasserstein space, auto-regressive model, iterated random function systems.
result Consistent estimator for auto-regressive coefficients with sparse structure.
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.
Random sampling improves DeepONet training efficiency without sacrificing accuracy.
problem Training DeepONet models with high computational and memory costs.
method Random sampling of inputs in the trunk network of DeepONet.
result Significant reduction in training time with comparable accuracy.
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.
Study on self-similar sets on Riemannian manifolds with new separation conditions.
problem Analyzing self-similar sets on Riemannian manifolds with new separation conditions.
method Formulated weak separation and finite type conditions for conformal iterated function systems on Riemannian manifolds.
result Obtained formulas for Hausdorff dimensions of self-similar and graph self-similar sets.
Critical volatility triggers log-normal to power-law transitions in interconnected systems.
problem Understanding the transition from log-normal to power-law distributions in interconnected systems.
method Analyzing an infinite option-on-option chain model, deriving a critical volatility threshold.
result A critical volatility threshold of approximately 250.66% for unconditional cases, dropping to 125.3% with selective survival.
We investigate i.i.d. random complex dynamical systems generated by probability measures on finite unions of the loci of holomorphic families of rational maps on the Riemann sphere. We show that under certain conditions on the families, for a generic system, (especially, for a generic random polynomial dynamical system…
Unified framework for solving linear systems with improved convergence rates.
problem Efficiently solving linear systems with randomized batch-sampling methods.
method Developed a unified randomized batch-sampling Kaczmarz framework with concentration inequalities for analysis.
result Derived new expected linear convergence rate bounds that are tighter and more reflective of empirical behavior.
Stochastic Maps, Wealth Distribution in Random Asset Exchange Models and the Marginal Utility of Relative Wealthcond-mat.stat-mech
We look at how asset exchange models can be mapped to random iterated function systems (IFS) giving new insights into the dynamics of wealth accumulation in such models. In particular, we focus on the "yard-sale" (winner gets a random fraction of the poorer players wealth) and the "theft-and-fraud" (winner gets a rando…
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.
The two main theorems of this paper provide a characterization of hyperbolic affine iterated function systems defined on Rm. Atsushi Kameyama (Distances on Topological Self-Similar Sets, Proceedings of Symposia in Pure Mathematics, Volume 72.1, 2004) asked the following fundamental question: given a topological self-si…
Two-stage nonconvex algorithm and convex relaxation both achieve optimal accuracy in noisy blind deconvolution.
problem Solving bilinear systems of equations with random noise under different designs.
method Two-stage nonconvex algorithm and convex relaxation.
result Both methods achieve minimax-optimal accuracy in the presence of random noise.
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.
The paper sharpens the analysis of sketch-and-project methods using randomized singular value decomposition.
problem Improving convergence rates of sketch-and-project methods for solving linear systems and non-linear optimization problems.
method Developing a theoretical framework and new spectral bounds for the expected sketched projection matrix.
result The convergence rate improves linearly with sketch size and even faster with certain spectral decays.
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 consider the exploration-exploitation dilemma in finite-horizon reinforcement learning (RL). When the state space is large or continuous, traditional tabular approaches are unfeasible and some form of function approximation is mandatory. In this paper, we introduce an optimistically-initialized variant of the popula…
We extend a result regarding the Random Backward Iteration algorithm for drawing Julia sets (known to work for certain rational semigroups containing a non-Möbius element) to a class of Möbius semigroups which includes certain settings not yet been dealt with in the literature, namely, when the Julia set is not a thick…
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.
Kaczmarz++ accelerates convergence for ill-conditioned systems.
problem Solving ill-conditioned linear systems efficiently.
method Adaptive momentum acceleration, Tikhonov-regularized projections, and memoization.
result Kaczmarz++ converges faster than Krylov methods on ill-conditioned systems.
This paper presents a new algorithm, termed \emph{truncated amplitude flow} (TAF), to recover an unknown vector from a system of quadratic equations of the form , where 's are given random measurement vectors. This problem is known to be \emph{NP-hard} in genera…
Proposes a method to generate multivariate prediction intervals for random forests.
problem Uncertainty estimates for iterative design of experiments with multiple correlated model outputs.
method Recalibrated bootstrap method for bagged models.
result Significantly decreases the number of iterations required for satisfactory candidate in sequential learning problems.
Adaptive optimal control of nonlinear dynamic systems with deterministic and known dynamics under a known undiscounted infinite-horizon cost function is investigated. Policy iteration scheme initiated using a stabilizing initial control is analyzed in solving the problem. The convergence of the iterations and the optim…
Software estimates inequality in random systems with changing communities.
problem Measuring inequality in systems with dynamic interactions and random attributes.
method Piecewise homogeneous Markov chain for changing points, copula function for multivariate distribution, Monte Carlo algorithm for entropy estimation.
result Estimates Random Theil's Entropy to measure inequality in random systems.
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.
New method calculates geodesic distances in Gaussian random field manifolds.
problem Quantifying similarity between random fields in different regimes.
method Numerical method using geodesic distances in Gaussian random field manifolds.
result Estimation of geodesic distances for various initial conditions.
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…
Recent developments in system identification have brought attention to regularized kernel-based methods. This type of approach has been proven to compare favorably with classic parametric methods. However, current formulations are not robust with respect to outliers. In this paper, we introduce a novel method to robust…
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.
Proposes an INLA-based method for state and parameter estimation in nonlinear systems.
problem Difficulty in learning parameters accurately in nonlinear dynamical systems.
method Iterated INLA for state and parameter estimation in nonlinear dynamical systems.
result Outperforms existing methods on data assimilation tasks.