Paper improves SLCB regret bound for bounded noise.
problem Stochastic linear contextual bandits with bounded noise.
method Set-membership estimation (SME) and optimism in the face of uncertainty (OFU).
result Improved regret bound of .
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 “bounded noise”
Enhanced consistency bounds derived for classification under a new noise condition.
problem Enhanced consistency bounds for classification under a new noise condition.
method Model Margin Noise (MM noise) assumption, derived enhanced H-consistency bounds.
result Enhanced H-consistency bounds under MM noise condition, interpolates between linear and square-root regimes.
New bounds for kernel regression under non-Gaussian noise.
problem Uncertainty quantification for function estimates from noisy observations.
method Novel non-asymptotic probabilistic uniform error bounds for kernel-based regression.
result Proposed bounds apply to a broad class of non-Gaussian noise distributions.
Optimizes SGLD noise structure for better generalization bounds.
problem Improving generalization bounds for large models trained with SGLD.
method Manipulates the noise structure in SGLD to optimize information-theoretical bounds.
result Optimal noise covariance is the square root of the expected gradient covariance under certain constraints.
Study noise-free kernel bandits, finding upper bounds on regret.
problem Optimizing unknown functions without noise.
method Upper bounds on regret for noise-free kernel-based bandits.
result No order optimal regret bounds are established, conjecture on optimal bound.
Study on online regression with noise, achieving near-optimal regret bounds.
problem Online generalized linear regression with stochastic noise.
method Sharp analysis of FTRL algorithm for stochastic label noise.
result Achieved near-optimal regret bounds for .
New method bounds stochastic subgradient methods with heavy-tailed noise.
problem Bounding stochastic subgradient methods under heavy-tailed noise.
method Clipped version of projected stochastic subgradient method.
result Near optimal any-time and finite horizon bounds for averaging schemes.
Paper provides tail bounds for stochastic mirror descent in heavy-tailed noise.
problem Optimizing convex and Lipschitz functions with heavy-tailed noise.
method Develops tail bounds for optimization error of Stochastic Mirror Descent.
result Tail bounds extend to heavier-tailed noise regimes without diameter constraints.
We study Principal Component Analysis (PCA) in a setting where a part of the corrupting noise is data-dependent and, as a result, the noise and the true data are correlated. Under a bounded-ness assumption on the true data and the noise, and a simple assumption on data-noise correlation, we obtain a nearly optimal samp…
SGD handles label noise with bounds improving over SGLD.
problem Label noise in non-convex optimization.
method Stochastic gradient descent with uniform dissipativity and smoothness conditions, using Wasserstein distance and algorithmic stability.
result Generalization error bounds with a rate of , better than SGLD's .
Maximal concentration bounds for stochastic approximation with heavy-tailed noise.
problem Analyzing the convergence of stochastic approximation algorithms under heavy-tailed Markovian noise.
method Novel Lyapunov function and black-box truncation argument.
result Tail behavior of the error can be sub-Gaussian, sub-Weibull, or lighter than any Pareto but heavier than any Weibull.
The paper provides tighter error bounds for GPR under bounded support noise.
problem Rigorous error quantification for safety-critical applications with bounded noise.
method Using concentration inequalities and low complexity assumptions in RKHS, the paper derives probabilistic and deterministic error bounds for GPR.
result The derived error bounds are substantially tighter than existing state-of-the-art bounds and are particularly well-suited for GPR with neural network kernels.
New research shows that binary classification can be done with noisy data, but only if there are clean samples available.
problem Learning binary classification with instance and label dependent label noise.
method Theoretical analysis and empirical risk minimization.
result Empirical risk minimization achieves the optimal excess risk bound without additional assumptions.
We present a simple noise-robust margin-based active learning algorithm to find homogeneous (passing the origin) linear separators and analyze its error convergence when labels are corrupted by noise. We show that when the imposed noise satisfies the Tsybakov low noise condition (Mammen, Tsybakov, and others 1999; Tsyb…
Paper tackles online control of linear systems with unbounded noise.
problem Online control of linear systems under unbounded noise with unknown convex cost functions.
method Developed an algorithm achieving high-probability regret under unbounded noise, and established regret bound for strongly convex costs and sub-Gaussian noise.
result Achieved high-probability regret under unbounded noise, and regret bound for specific noise and cost conditions.
Several recent works have shown that state-of-the-art classifiers are vulnerable to worst-case (i.e., adversarial) perturbations of the datapoints. On the other hand, it has been empirically observed that these same classifiers are relatively robust to random noise. In this paper, we propose to study a \textit{semi-ran…
Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysiscs.LG
Study on SA with heavy-tailed and LRD noise, establishing finite-time bounds.
problem Analyzing stochastic approximation under heavy-tailed and LRD noise.
method Noise-averaging argument to regularize impact of non-classical noise.
result Established first finite-time moment bounds for SA under heavy-tailed and LRD noise.
Improved BO algorithms reduce prediction error under Gaussian noise.
problem Reducing prediction error in Bayesian optimization with Gaussian noise.
method Established new prediction error bounds for Gaussian process under frequentist setting.
result Proved improved convergence rates of cumulative regret for GP-UCB and GP-TS.
Framework for private, noise-tolerant, and efficient learning algorithms.
problem Private and efficient learning of large-margin halfspaces in noisy environments.
method Simple framework using differential privacy and noise tolerance conditions.
result Noise-tolerant and private PAC learners for large-margin halfspaces with sample complexity independent of dimension.
RS-NSGD improves SGD convergence for heavy-tailed noise.
problem Nonconvex optimization with heavy-tailed noise.
method Integrates direction normalization into subspace updates.
result Achieves better oracle complexity than full-dimensional normalized SGD.
Researchers establish bounds for SGMs' KL and Wasserstein divergences under various noise schedules.
problem Estimating the error between target and estimated distributions in SGMs.
method Established upper bounds for KL divergence and Wasserstein distance, incorporating target distribution properties and SGM hyperparameters.
result Optimal noise schedules identified for SGMs, improving generative quality.
Improved SGD bounds for machine learning models with Markovian noise.
problem Uniform high-probability bounds for SGD under PL condition with Markovian noise.
method Combining Poisson equation for Markovian noise and probabilistic induction for almost-sure bounds.
result Matching decay rate for expected suboptimality.
Study generalizes matrix completion with side info in low noise settings.
problem Matrix completion with side information in low noise conditions.
method Inductive matrix completion with i.i.d. subgaussian noise, uniform sampling, and side information.
result Generalization bounds with noise scaling, convergence to zero, and logarithmic dependence on matrix size.
Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noisemath.OC
New methods solve optimization problems with heavy-tailed noise, improving upon existing complexity bounds.
problem Optimization problems with heavy-tailed noise and weakly average smoothness.
method Normalized stochastic first-order methods with Polyak, multi-extrapolated, and recursive momentum.
result First-order oracle complexity results for finding approximate stochastic stationary points under heavy-tailed noise.
Noise added to neural network features limits input reconstruction.
problem Protecting privacy during inference with deep neural networks.
method Hammersley-Chapman-Robbins bounds applied to noise added to neural network features.
result HCR bounds limit confidentiality but not accuracy.
Work on SGDm under heavy-tailed noise, revealing its generalization properties.
problem Understanding generalization of SGDm under heavy-tailed noise.
method Analysis of continuous-time limit (SDE) and discrete-time SGDm, establishing generalization bounds.
result SGDm can have worse generalization in the presence of heavy-tailed noise for quadratic loss functions.
Unified approach for first-order methods with Markovian noise in stochastic optimization and variational inequalities.
problem Stochastic optimization problems with Markovian noise.
method Unified theoretical analysis of first-order gradient methods using randomized batching and multilevel Monte Carlo.
result Optimal (linear) dependence on the mixing time of the noise sequence, eliminating previous limiting assumptions.
Paper develops a TR-SSQP method for noisy optimization with heavy-tailed noise.
problem Optimization problems with stochastic objectives and heavy-tailed noise.
method Trust-Region Stochastic Sequential Quadratic Programming (TR-SSQP) method.
result Achieves high-probability first-order and second-order stationarity bounds for heavy-tailed noise.
In the stochastic bandit problem, the goal is to maximize an unknown function via a sequence of noisy evaluations. Typically, the observation noise is assumed to be independent of the evaluation point and to satisfy a tail bound uniformly on the domain; a restrictive assumption for many applications. In this work, we c…
Paper provides a new lower bound on MMSE using Poincaré inequality.
problem Estimating X from noisy Y in exponential family noise.
method Alternative MMSE representation + Poincaré inequality.
result New lower bound on MMSE holds for all distributions.
A new pricing strategy learns customer valuations without noise distribution knowledge.
problem Setting optimal prices for products based on customer valuations with unknown noise.
method Developed a novel perturbed linear bandit framework to learn both contextual functions and market noise.
result Proved sub-linear regret bound and demonstrated superior performance on simulations and real data.
New bandit algorithm for non-i.i.d. noise, improving standard rates.
problem Linear stochastic bandit with non-i.i.d. observation noise.
method Developed new confidence sequences and an algorithm based on optimism in uncertainty.
result Regret bounds for the new algorithm, showing recovery of standard rates up to a factor of the mixing time.
Paper establishes convergence rates and concentration bounds for stochastic approximation and reinforcement learning with Markovian noise.
problem Analyzing convergence rates and concentration bounds for stochastic approximation and reinforcement learning with Markovian noise.
method Novel discretization of the mean ODE of stochastic approximation algorithms using intervals with diminishing length.
result First almost sure convergence rate and maximal concentration bound with exponential tails for contractive stochastic approximation algorithms with Markovian noise.
New bounds for KANs trained with DP-SGD, addressing correlated noise.
problem Risk bounds for Kolmogorov-Arnold Networks trained by DP-SGD with correlated noise.
method Established new optimization and population risk analysis for KANs trained with DP-SGD, addressing correlated noise.
result First optimization and population risk analysis of correlated-noise mechanisms for DP training in non-convex settings, including neural networks.
New method bounds hardware noise without assumptions.
problem Estimating hardware noise without assumptions.
method Machine Learning and Conformal Prediction.
result Theoretical upper bounds of fidelity.
We provide recovery guarantees for compressible signals that have been corrupted with noise and extend the framework introduced in \cite{bafna2018thwarting} to defend neural networks against -norm, -norm, and -norm attacks. Our results are general as they can be applied to most unitary tr…
We consider the mixed regression problem with two components, under adversarial and stochastic noise. We give a convex optimization formulation that provably recovers the true solution, and provide upper bounds on the recovery errors for both arbitrary noise and stochastic noise settings. We also give matching minimax …
Improved GP bandit algorithms for noiseless, varying noise, and RKHS norms.
problem Minimizing regret in Gaussian process bandits with unknown reward functions.
method New upper bound on maximum posterior variance, refined MVR and PE algorithms.
result Optimal regret bounds for noiseless, varying noise, and RKHS norms.
Uniform TD(0) bound derived for function approximation with Markov noise.
problem Uniform concentration bound for TD(0) with function approximation.
method Contractive stochastic approximation, martingale and Markov noises, Poisson equation, relaxed concentration inequalities.
result Uniform all-time concentration bound for TD(0) with linear function approximation.
This paper analyzes M-estimators under infinite-variance noise in high dimensions.
problem High-dimensional M-estimation with infinite-variance noise.
method Study of the Fenchel conjugate domain and its impact on risk.
result Exact risk of M-estimators under infinite-variance noise is derived.
Study near-optimal bounds for learning Gaussian halfspaces with random noise.
problem Learning general halfspaces with Gaussian distribution and random classification noise.
method Established nearly-matching algorithmic and SQ lower bounds, developed a computationally efficient learning algorithm.
result Sample complexity of learning algorithm is , SQ lower bound is .
Study shows multi-distribution learning has slower rates than single-task learning.
problem Understanding the statistical complexity of learning from heterogeneous sources.
method Structured hypothesis-testing framework to capture the statistical cost of certifying near-optimality under bounded noise.
result Learning across multiple distributions incurs slow rates scaling with , even under constant noise levels.
Improved sample complexity for learning halfspaces with malicious noise.
problem Efficiently learning halfspaces in the presence of malicious noise.
method New analysis of Awasthi et al. algorithm with matrix Chernoff inequality and localization schemes.
result Achieved near-optimal sample complexity of for isotropic log-concave distributions.
The paper establishes risk bounds for PU learning with label noise.
problem Finding a classifier in PU learning with label noise.
method Establishes risk bounds under the assumption of label selection randomness.
result Proves that the upper bound on minimax risk is almost optimal.
Study large deviations rates for SGD with strongly convex functions.
problem High probability metrics with SGD.
method Large deviations theory, generic gradient noise, strongly convex functions.
result Upper large deviations bound for SGD with strongly convex functions.
Bounds on Portfolio Qualityq-fin.PM
The signal-noise ratio of a portfolio of p assets, its expected return divided by its risk, is couched as an estimation problem on the sphere. When the portfolio is built using noisy data, the expected value of the signal-noise ratio is bounded from above via a Cramer-Rao bound, for the case of Gaussian returns. The bo…
Study analyzes perturbations in singular subspaces under random noise.
problem Understanding singular vector and subspace changes in signal-plus-noise models.
method Generalized Davis-Kahan-Wedin theorem for any unitarily invariant norm, considering and bounds.
result Fine-grained insights into singular vector and subspace perturbations, including and bounds.
New error bounds for noisy phase retrieval problems using empirical risk minimization.
problem Estimating signals in noisy phase retrieval problems.
method Empirical risk minimization (ERM) with new error bounds for different noise patterns.
result Established new error bounds for NPR and NGPR, showing improved performance under various noise conditions.