We investigate the optimality of perturbation based algorithms in the stochastic and adversarial multi-armed bandit problems. For the stochastic case, we provide a unified regret analysis for both sub-Weibull and bounded perturbations when rewards are sub-Gaussian. Our bounds are instance optimal for sub-Weibull pertur…
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 “stochastic perturbations”
In this paper we introduce a family of stochastic gradient estimation techniques based of the perturbative expansion around the mean of the sampling distribution. We characterize the bias and variance of the resulting Taylor-corrected estimators using the Lagrange error formula. Furthermore, we introduce a family of va…
Paper proposes faster method to find local minima in nonconvex optimization.
problem Escaping saddle points and finding local minima in nonconvex optimization.
method LENA (Last stEp shriNkAge) framework for faster perturbed stochastic gradient methods.
result LENA finds -approximate local minima within evaluations.
Paper develops robust estimators and strategies for stochastic MABs with heavy-tailed rewards.
problem Stochastic multi-armed bandits with heavy-tailed rewards.
method Proposes a novel robust estimator and perturbation-based exploration strategy.
result Develops upper and lower regret bounds for various perturbations.
Fair pricing and hedging under small perturbations of the numéraire on a finite probability spaceq-fin.PR
The paper examines fair pricing and hedging stability under small numéraire perturbations.
problem Fair pricing and hedging stability under numéraire perturbations.
method Reformulating the stochastic control problem to show stability and deriving asymptotic formulas.
result Fair price and hedging strategy are stable with small numéraire perturbations.
Differentiable clustering method using perturbed spanning forests.
problem Efficient clustering in trainable pipelines with noisy data.
method Stochastic perturbations of minimum-weight spanning forests.
result Method performs well even in challenging settings.
We introduce and analyze stochastic optimization methods where the input to each gradient update is perturbed by bounded noise. We show that this framework forms the basis of a unified approach to analyze asynchronous implementations of stochastic optimization algorithms.In this framework, asynchronous stochastic optim…
Study on stochastic mean curvature flow on networks using Ito calculus.
problem Understanding the dynamics of network structures under random influences.
method Application of Ito calculus to derive a stochastic differential equation (SDE) for network edges.
result New insights into the stability, long-term behavior, and pattern formation of complex networks under stochastic influences.
Optimizes trading in markets with unpredictable price impacts.
problem Optimizing trading strategies in markets with stochastic price impacts.
method Singular perturbation methods to approximate optimal control problem.
result Proves approximations are accurate to specified order using sub- and super-solutions.
In a noncommutative torus, effect of perturbation by inner derivation on the associated quantum stochastic process and geometric parameters like volume and scalar curvature have been studied. Cohomological calculations show that the above perturbation produces new spectral triples. Also for the Weyl C^*-algebra, the La…
SGD generalization bounds derived from information theory.
problem Understanding generalization of SGD for non-convex functions.
method Combining information-theoretic bounds with perturbation analysis.
result Upper bounds on SGD's generalization error based on gradient variance and function smoothness.
Learnable token perturbations boost extrapolation in LLMs.
problem Limited flexibility of current discrete perturbations in large language models.
method Learnable continuous latent vector transformations in embedding space, unbiased estimating equations, stochastic gradient descent optimization.
result Significant gains in out-of-domain settings over state-of-the-art methods.
The paper shows robustness of Hilbert space-valued stochastic volatility models to perturbations.
problem Robustness of Hilbert space-valued stochastic volatility models to measurement or approximation errors.
method Quantifying the error induced by volatility perturbations and studying robustness of volatility process with finite dimensional approximations.
result Explicit bounds for the induced error in terms of approximation of the underlying parameter.
We consider in this work a system of two stochastic differential equations named the perturbed compositional gradient flow. By introducing a separation of fast and slow scales of the two equations, we show that the limit of the slow motion is given by an averaged ordinary differential equation. We then demonstrate that…
SGD converges with perturbed forward-backward passes, explained by geometric amplification.
problem Analyzing convergence of SGD with perturbed forward-backward passes in composite optimization.
method Characterized propagation and amplification of perturbations, derived convergence guarantees for non-convex and PL objectives.
result Perturbations cascade through the computational graph, affecting convergence order under specific conditions.
A new method speeds up sampling of Boltzmann distribution in high-dimensional systems.
problem High computational cost of obtaining Jacobian of flow-based models in high dimensions.
method Flow perturbation method that incorporates stochastic perturbations and reweighting.
result Achieves unbiased sampling of Boltzmann distribution with orders of magnitude speedup.
New framework maximizes perturbed samples for inverse classification with budget constraints.
problem Maximizing perturbed samples for desired classification outcomes under budget constraints.
method Gradient methods, stochastic processes, Lagrangian relaxations, Gumbel trick.
result Stochastic process-based algorithms outperform in different budget settings.
Variance reduction has been commonly used in stochastic optimization. It relies crucially on the assumption that the data set is finite. However, when the data are imputed with random noise as in data augmentation, the perturbed data set be- comes essentially infinite. Recently, the stochastic MISO (S-MISO) algorithm i…
Paper optimizes FTPL for adversarial and stochastic bandits with specific tail distributions.
problem Optimizing Follow-the-Perturbed-Leader (FTPL) policy for bandit problems.
method Analyzes FTPL with Fréchet-type tail distributions in adversarial and stochastic settings.
result FTPL with certain Fréchet-type tail distributions achieves regrets in adversarial bandits.
Feature attribution methods, or saliency maps, are one of the most popular approaches for explaining the decisions of complex machine learning models such as deep neural networks. In this study, we propose a stochastic optimization approach for the perturbation-based feature attribution method. While the original optim…
We propose a new online algorithm for cumulative regret minimization in a stochastic linear bandit. The algorithm pulls the arm with the highest estimated reward in a linear model trained on its perturbed history. Therefore, we call it perturbed-history exploration in a linear bandit (LinPHE). The perturbed history is …
Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite-Sum Structurestat.ML
Stochastic optimization algorithms with variance reduction have proven successful for minimizing large finite sums of functions. Unfortunately, these techniques are unable to deal with stochastic perturbations of input data, induced for example by data augmentation. In such cases, the objective is no longer a finite su…
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.
The paper derives the QGS equations using stochastic central extensions.
problem Deriving the viscous quasi-geostrophic equations on the torus.
method Central extensions of Lie groups and Lie algebras, stochastic Lagrangian formulation, and Euler-Poincaré reduction.
result Stochastic perturbations to the central extension lead to solutions of the QGS equations.
Study robust control for systems with continuous states using adversarial perturbations.
problem Fragile policies in Markov control models under internal or external perturbations.
method Distributionally robust stochastic control with adaptive adversarial perturbations.
result Optimal robust policies for continuous state systems with uniform learning guarantees.
We introduce a new stochastic smoothing perspective to study adversarial contextual bandit problems. We propose a general algorithm template that represents random perturbation based algorithms and identify several perturbation distributions that lead to strong regret bounds. Using the idea of smoothness, we provide an…
Implicit Regularization Makes Overparameterized Asymmetric Matrix Sensing Robust to Perturbationscs.LG
Paper shows robustness of gradient descent in matrix sensing despite perturbations.
problem Understanding robustness of gradient descent in matrix sensing.
method Developed perturbed gradient flow to capture noise and improve robustness.
result Gradient descent is robust to perturbations in matrix sensing.
Volatility modelling has become a significant area of research within Financial Mathematics. Wiener process driven stochastic volatility models have become popular due their consistency with theoretical arguments and empirical observations. However such models lack the ability to take into account long term and fundame…
Improved GSPGS estimators reduce bias in noisy function measurements.
problem Reduced bias in noisy function measurements.
method Generalized Simultaneous Perturbation-based Gradient Search (GSPGS) with various estimators.
result Estimators requiring more function measurements have lower bias.
We propose an online algorithm for cumulative regret minimization in a stochastic multi-armed bandit. The algorithm adds i.i.d. pseudo-rewards to its history in round and then pulls the arm with the highest average reward in its perturbed history. Therefore, we call it perturbed-history exploration (PHE). Th…
Sparse Stochastic Zeroth-Order Optimization with an Application to Bandit Structured Predictionstat.ML
Stochastic zeroth-order (SZO), or gradient-free, optimization allows to optimize arbitrary functions by relying only on function evaluations under parameter perturbations, however, the iteration complexity of SZO methods suffers a factor proportional to the dimensionality of the perturbed function. We show that in scen…
Quadratic approximation of slow factor of volatility in a Multi-factor Stochastic volatility Modelq-fin.PR
In the present work, we propose a new multifactor stochastic volatility model in which slow factor of volatility is approximated by a parabolic arc. We retain ourselves to the perturbation technique to obtain approximate expression for European option prices. We introduce the notion of modified Black-Scholes price. We …
EVILL uses randomised perturbations to improve exploration in bandit problems.
problem Improving exploration in structured stochastic bandit problems.
method Solves for the minimiser of a linearly perturbed regularised negative log-likelihood function.
result EVILL matches the performance of Thompson-sampling-style methods in theory and practice.
The paper calculates how random changes affect paths on a complex geometric space.
problem Computing the evolution of paths on a manifold of Riemannian metrics.
method Using diffusion processes and stochastic kinetic energy functional.
result Computed the evolution equation for the Lagrangian.
New methods help escape strict saddle points in nonsmooth optimization.
problem Escaping strict saddle points in nonsmooth optimization.
method An inexact stochastically perturbed gradient method applied to the Moreau envelope.
result A variety of algorithms for nonsmooth optimization can efficiently escape strict saddle points of the Moreau envelope.
This work analyzes the stability of graph filters under large perturbations.
problem Stability of graph filters under large edge rewires.
method Proves a bound on stability using frequency response and community structure.
result Graph filter stability depends on perturbation to community structure.
This paper analyzes Stochastic Depth regularization in ResNets.
problem Improving generalization in ResNets through regularization.
method Hybrid analysis combining perturbation and signal propagation.
result Principled guidelines for choosing survival rates in SD.
Geometry-informed irreversible perturbations for accelerated convergence of Langevin dynamicsstat.ME
Novel geometry-informed irreversible perturbation accelerates Langevin dynamics convergence.
problem Accelerating convergence of Langevin dynamics for Bayesian computation.
method Geometry-informed irreversible perturbation of Riemannian manifold Langevin dynamics.
result Improves estimation performance over irreversible perturbations that ignore geometry.
The Davis-Kahan-Wedin theorem describes how the singular subspaces of a matrix change when subjected to a small perturbation. This classic result is sharp in the worst case scenario. In this paper, we prove a stochastic version of the Davis-Kahan-Wedin theorem when the perturbation is a Gaussian rando…
Localized uncertainty attacks target uncertain regions to create imperceptible adversarial examples.
problem Adversarial examples that are imperceptible to humans and strong under deterministic classifiers.
method Localized uncertainty attacks by perturbing uncertain regions, using predictive uncertainty or surrogate models.
result Localized uncertainty attacks produce strong adversarial examples that retain input similarity.
Human motion prediction is a stochastic process: Given an observed sequence of poses, multiple future motions are plausible. Existing approaches to modeling this stochasticity typically combine a random noise vector with information about the previous poses. This combination, however, is done in a deterministic manner,…
Sparse perturbations improve convergence in SZO methods for faster training.
problem Dependency of SZO methods on function dimensionality limits their convergence speed.
method Sparse perturbations reduce the effective dimensionality of the optimization problem.
result Sparse SZO optimization leads to faster convergence in training loss and test accuracy.
Distributed descent-based methods are an essential toolset to solving optimization problems in multi-agent system scenarios. Here the agents seek to optimize a global objective function through mutual cooperation. Oftentimes, cooperation is achieved over a wireless communication network that is prone to delays and erro…
DBPA assesses LLM perturbations using frequentist hypothesis testing.
problem Quantifying input perturbation impacts on LLM outputs.
method DBPA reformulates perturbation analysis as frequentist hypothesis testing, using Monte Carlo sampling for empirical null and alternative distributions.
result DBPA provides interpretable p-values and scalar effect sizes for LLM perturbations.
Classical matrix perturbation results, such as Weyl's theorem for eigenvalues and the Davis-Kahan theorem for eigenvectors, are general purpose. These classical bounds are tight in the worst case, but in many settings sub-optimal in the typical case. In this paper, we present perturbation bounds which consider the natu…
As most natural resources, fisheries are affected by random disturbances. The evolution of such resources may be modelled by a succession of deterministic process and random perturbations on biomass and/or growth rate at random times. We analyze the impact of the characteristics of the perturbations on the management o…
Unified framework for gradient estimation in combinatorial spaces.
problem Scaling relaxed gradient estimators to large combinatorial distributions.
method Introducing stochastic softmax tricks within the perturbation model framework.
result Stochastic softmax tricks improve model performance and discover more latent structure.
Gradient perturbation, widely used for differentially private optimization, injects noise at every iterative update to guarantee differential privacy. Previous work first determines the noise level that can satisfy the privacy requirement and then analyzes the utility of noisy gradient updates as in the non-private cas…