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,695 papers · 148 categories
Trend · papers per month
48 results for “Sub-Gaussian noise”
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.
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.
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.
Paper solves robust convex problems with heavy-tailed noise.
problem Solving convex compositional problems with heavy-tailed noise.
method Sub-Gaussian confidence bounds under weak heavy-tailed noise assumptions, using boosting strategy.
result Achieves nearly optimal high probability convergence result.
We propose robust sparse reduced rank regression for analyzing large and complex high-dimensional data with heavy-tailed random noise. The proposed method is based on a convex relaxation of a rank- and sparsity-constrained non-convex optimization problem, which is then solved using the alternating direction method of m…
This paper extends the standard chaining technique to prove excess risk upper bounds for empirical risk minimization with random design settings even if the magnitude of the noise and the estimates is unbounded. The bound applies to many loss functions besides the squared loss, and scales only with the sub-Gaussian or …
Sparse Max-Affine Regressionstat.ML
Paper proposes Sp-GD for sparse max-affine regression with theoretical guarantees.
problem Sparse max-affine regression model selection and estimation.
method Sparse Gradient Descent (Sp-GD) initialization using sparse PCA and covering search.
result Sp-GD provides ε-accurate estimates with optimal number of observations.
The paper tackles resource allocation for arms with unknown and random rewards, achieving optimal regret bounds.
problem Allocating resources on arms with unknown and random rewards.
method Developed two algorithms with optimal regret bounds for , demonstrating a phase transition at .
result Achieved optimal gap-dependent and gap-independent regret bounds for .
Paper tackles robust matrix completion with heavy-tailed noise.
problem Estimating a low-rank matrix from noisy incomplete data.
method Adaptive Huber loss for robustness, nonconvex algorithm with spectral initialization.
result Achieves minimax-optimal statistical estimation error under bounded second moment condition.
One-bit clustering method for two-component sub-Gaussian mixture models
problem Clustering in sub-Gaussian mixture models
method One-bit clustering using dithered quantization
result Decaying misclassification rate with exponential signal-to-noise ratio
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.
SGD converges to an invariant distribution with sub-Gaussian or sub-exponential properties.
problem Optimizing smooth and strongly convex objectives using SGD.
method Analysis through Markov chains, focusing on convergence and concentration properties.
result SGD iterates and their invariant limit distribution inherit sub-Gaussian or sub-exponential concentration properties.
On the Estimation Performance of Generalized Power Method for Heteroscedastic Probabilistic PCAmath.OC
Paper proposes GPM for heteroscedastic PCA estimation.
problem Estimating ground truth from heterogeneous data.
method Generalized power method (GPM) for HQPOC.
result GPM achieves geometrically decreasing distances to ground truth.
Max-affine regression method converges linearly using GD and SGD.
problem Regression of max-affine models in signal processing and statistics.
method Gradient descent and mini-batch stochastic gradient descent analysis.
result GD and SGD converge linearly to a neighborhood of the ground truth under sub-Gaussian assumptions.
Algorithm estimates top k eigenvectors of shared covariance matrices while preserving privacy.
problem Differentially private PCA with adaptive noise for arbitrary k.
method Iterative algorithm with adaptive noise reduction.
result First algorithm for estimating top k eigenvectors with near-optimal statistical error.
Recent years have seen increased interest in performance guarantees of gradient descent algorithms for non-convex optimization. A number of works have uncovered that gradient noise plays a critical role in the ability of gradient descent recursions to efficiently escape saddle-points and reach second-order stationary p…
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.
New method tightens sub-Gaussian concentration inequalities.
problem Estimating variance-type parameters of sub-Gaussian distributions.
method Using sub-Gaussian intrinsic moment norm to maximize normalized moments.
result Provides tighter sub-Gaussian concentration inequalities.
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.
Novel confidence sets improve linear bandit performance by adapting to unknown noise levels.
problem Adapting to unknown noise levels in sequential decision-making.
method Proposed semi-adaptive and variance-adaptive confidence sets.
result Improved regret bounds and better performance in Bayesian optimization tasks.
New method improves privacy in linear regression with optimal error bounds.
problem Differentially private linear regression with suboptimal error bounds.
method One-pass mini-batch stochastic gradient descent (DP-AMBSSGD) with adaptive clipping.
result Nearly optimal error bounds in terms of key parameters like dimensionality, number of points, and noise standard deviation.
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 .
Variance Reduction and Low Sample Complexity in Stochastic Optimization via Proximal Point Methodmath.OC
New method reduces variance in stochastic optimization with high confidence.
problem Achieving high-probability guarantees in stochastic optimization with weaker noise assumptions.
method Stochastic proximal point method combining proximal subproblem solver and probability booster.
result Demonstrates convergence with low sample complexity under bounded variance assumptions.
The paper explores how linear neural networks can overfit without bias when data is well-behaved.
problem Understanding why linear neural networks can generalize well despite fitting noisy data.
method Analyzing two-layer linear neural networks trained with gradient flow, deriving bounds on excess risk.
result The excess risk depends on initialization quality and data covariance matrix properties.
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.
This paper improves parameter estimation for autonomous systems with unmodeled dynamics.
problem Accurate parameter estimation for risk-aware autonomous systems with unmodeled dynamics.
method Spectral lines-based approach for estimating parameters of dynamic models, allowing deterministic unmodeled dynamics.
result The proposed method leads to non-asymptotic bounds on parameter estimation error, robust to unmodeled dynamics, and matches existing literature in ideal conditions.
Sharp rates found for learning with dependent data, avoiding sample size deflation.
problem Learning with dependent data and square loss.
method Combining weak sub-Gaussian class and mixed tail generic chaining.
result Achieves a rate that only depends on class complexity and second order statistics.
The paper develops a robust signal estimation method for noisy measurements from generative models.
problem Signal estimation from noisy non-linear measurements with adversarial corruptions.
method Generalized Lasso approach with sub-Gaussian measurements and adversarial noise consideration.
result The method requires $O\left(\frac{k}{ε^2}\log L
ight)$ samples for -error recovery, robust to adversarial noise.
Develops an ℓ_p theory for PCA and spectral clustering.
problem Lack of precise characterizations of PCA scores for low-dimensional embedding.
method An ℓ_p perturbation theory for PCA in Hilbert spaces, analyzing eigenvectors and Gram matrix.
result Optimal recovery results for Gaussian mixture and stochastic block models.
Study non-parametric frequency-domain system identification from finite samples.
problem Frequency-domain system identification from limited data.
method Empirical Transfer Function Estimate (ETFE) under sub-Gaussian colored noise and stability assumptions.
result ETFE estimates are concentrated around true values with a finite-sample rate of for all frequencies in the norm.
We tackle the problem of estimating a location parameter with differential privacy guarantees and sub-Gaussian deviations. Recent work in statistics has focused on the study of estimators that achieve sub-Gaussian type deviations even for heavy tailed data. We revisit some of these estimators through the lens of differ…
Heavy-tailed distributions are widely used in robust mixture modelling due to possessing thick tails. As a computationally tractable subclass of the stable distributions, sub-Gaussian -stable distribution received much interest in the literature. Here, we introduce a type of expectation maximization algorithm that e…
Study revisits AdaGrad convergence with relaxed noise assumptions.
problem Non-convex smooth optimization problems with general noise.
method General noise model with function value gap and gradient magnitude control.
result Probabilistic convergence rate of ( ilde{\mathcal{O}}(1/\sqrt{T})) under general noise.
Thompson Sampling is a well established approach to bandit and reinforcement learning problems. However its use in continuum armed bandit problems has received relatively little attention. We provide the first bounds on the regret of Thompson Sampling for continuum armed bandits under weak conditions on the function cl…
Sharp sub-Gaussian upper bounds for subsolutions of Trudinger's equation on Riemannian manifoldsmath.AP
Sharp sub-Gaussian bounds for subsolutions of Trudinger's equation on Riemannian manifolds.
problem Bounding weak subsolutions of Trudinger's equation on Riemannian manifolds.
method Proving sub-Gaussian upper bounds for weak subsolutions.
result The upper bounds are sharp for specific classes of manifolds, including \(\mathbb{R}^{n}\).
Random linear mappings are widely used in modern signal processing, compressed sensing and machine learning. These mappings may be used to embed the data into a significantly lower dimension while at the same time preserving useful information. This is done by approximately preserving the distances between data points,…
UCB algorithm adapted for large-scale, non-sub-Gaussian problems.
problem Selecting the best alternative from a large set of options with non-sub-Gaussian performance distributions.
method Adapted UCB algorithm for non-sub-Gaussian settings, focusing on sample size and meta-UCB selection.
result UCB algorithms can achieve sample optimality in large-scale, non-sub-Gaussian problems.
Proves new concentration inequalities for sub-gaussian and sub-exponential variables.
problem Understanding functions of independent random variables better.
method Sub-gaussian and sub-exponential conditions, Rademacher complexities, Lipschitz function classes.
result Extension of Rademacher complexities to unbounded sub-exponential distributions.
Study improves self-normalized bounds for vector-valued processes beyond sub-Gaussianity.
problem Limited understanding of self-normalized concentration for vector-valued processes outside sub-Gaussian frameworks.
method Developed concentration inequalities for self-normalized processes with light tails (e.g., Bennett, Bernstein bounds) for vector-valued data.
result Provided new insights and bounds for self-normalized processes with non-sub-Gaussian distributions.
Paper proposes a 1-bit quantization scheme for high-dimensional statistical estimation.
problem High-dimensional statistical estimation with limited data.
method Uniformly dithered 1-bit quantization for sparse covariance matrix estimation, sparse linear regression, and matrix completion.
result Near minimax rates in sub-Gaussian regime and improved rates in heavy-tailed regime.
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.
Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designscs.LG
New algorithm converts data into sub-gaussian designs efficiently.
problem Efficiently converting large datasets into sub-gaussian random designs for robust performance.
method Algorithmic Gaussianization through sketching and averaging, using LESS embeddings.
result Efficient data sketches nearly indistinguishable from sub-gaussian designs.
A new framework for PPLS combines noise estimation, optimization, and calibration.
problem Probabilistic PLS models need interpretable latent factors and calibrated uncertainty.
method End-to-end pipeline combining noise estimation, constrained optimization, and prediction calibration.
result Achieves near-nominal coverage and native calibrated uncertainty across benchmarks.
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.
Paper studies Adam's convergence under relaxed assumptions, proving a rate of O(poly(log T)/sqrt(T)).
problem Understanding Adam's convergence in non-convex, stochastic optimization with unbounded gradients and noise.
method Introduced a comprehensive noise model and used it to prove Adam's convergence rate.
result Adam finds a stationary point with a rate of O(poly(log T)/sqrt(T)) in high probability.
Quantum algorithm estimates mean with sub-Gaussian error.
problem Estimating mean of quantum-computed random variables.
method Quantum mean estimation algorithm with sub-Gaussian error rate.
result Achieves nearly-optimal quadratic speedup over classical methods.
We propose a general framework for solving the group synchronization problem, where we focus on the setting of adversarial or uniform corruption and sufficiently small noise. Specifically, we apply a novel message passing procedure that uses cycle consistency information in order to estimate the corruption levels of gr…