Deep neural networks help recover two signals from noisy mixtures.
problem Recovering two signals from noisy subgaussian mixtures with prior structural information.
method Used deep generative neural networks (GNNs) to solve the demixing problem for Lipschitz signals.
result Proved a sample complexity bound for nearly optimal recovery error, extending previous results.
Proves subgaussian distributions are SoS-certifiably subgaussian, enabling efficient algorithms for various statistical tasks.
problem Efficiently learning from subgaussian distributions in high dimensions.
method Universal constant C C C and polynomial sum of squares (SoS) approach. result Proves subgaussian distributions are SoS-certifiably subgaussian.
We introduce a model-free relax-and-round algorithm for k-means clustering based on a semidefinite relaxation due to Peng and Wei. The algorithm interprets the SDP output as a denoised version of the original data and then rounds this output to a hard clustering. We provide a generic method for proving performance guar…
Study finds the minimum number of finite Gaussian mixtures for best approximation.
problem Finding the minimum number of finite Gaussian mixtures for best approximation.
method Local moment matching for upper bound and spectral analysis for lower bound.
result Corrects a previous lower bound in the case of Gaussian mixing distributions.
In this note, we derive concentration inequalities for random vectors with subGaussian norm (a generalization of both subGaussian random vectors and norm bounded random vectors), which are tight up to logarithmic factors.
Note on subgaussian bounds for sign-quantized linear maps.
problem Understanding subgaussian behavior of sign-quantized linear maps.
method Developed a dimension-independent subgaussian concentration bound for Gaussian vectors under nonlinear mappings.
result Answered a question about sign-quantized linear maps using a new subgaussian bound.
NPMLE estimator automatically chooses the right model complexity for Gaussian mixtures.
problem Learning mixture models and empirical Bayes estimation with non-convex likelihoods.
method Nonparametric maximum likelihood estimator (NPMLE) using complex-analytic techniques.
result NPMLE solution has O ( log n ) O(\log n) O ( log n ) atoms with high probability, improving model complexity. Concentration of infinitely exchangeable sequences with bounded-difference constants
problem Quantifying uncertainty in AI benchmarks
method Using a mixture-free Hoeffding-type bound
result Tight, mixture-free Hoeffding-type bound for zero-sum linear contrasts
Study reduces human labeling in LLM-based classification systems.
problem Minimizing human intervention in training LLM-based classification systems.
method Active learning framework with Conservative Hull-based Classifier (CHC), Center-based Classifier (CC), and Generalized Hull-based Classifier (GHC).
result CHC achieves O ( log d T ) \mathcal{O}(\log^d T) O ( log d T ) regret and is minimax optimal for d = 1 d=1 d = 1 . GHC bridges the gap between different regimes. New robust estimators achieve subgaussian bounds using VC-dimension.
problem Robust estimation of sparse and corrupted data.
method Use of VC-dimension to measure statistical complexity.
result First robust estimators for sparse estimation with subgaussian rate.
New algorithms robustly estimate mean with near-optimal error rates.
problem Outlier robust mean estimation in high-dimensional data.
method Stability condition and iterative filtering algorithms.
result Optimal error rates with subgaussian rates for robust mean estimation.
Paper estimates EOT maps for non-compactly supported measures with subGaussian target.
problem Estimating EOT maps between non-compactly supported measures.
method Uses bias-variance decomposition, T1-transport inequalities, and concentration of measure results.
result Shows error decay rates for different cases of subGaussian measures.
New algorithm for computing Gaussian mixtures with guaranteed accuracy and efficiency.
problem Computing the nonparametric maximum likelihood estimator for Gaussian mixtures efficiently and accurately.
method Developed an algorithm that computes an ε-approximation of the estimator in Wasserstein distance with time complexity K + C n k 2 log log ( 1 / ε ) K+Cnk^2\log\log(1/\varepsilon) K + C n k 2 log log ( 1/ ε ) , and certifiably computes the exact number of components. result The algorithm provides guaranteed accuracy and efficiency for computing the nonparametric maximum likelihood estimator for Gaussian mixtures.
Thompson Sampling shows polynomial regret for combinatorial semi-bandits with subgaussian rewards.
problem Finding optimal solutions in combinatorial semi-bandits with suboptimal sampling.
method Proposes Thompson Sampling with polynomial regret for linear combinatorial semi-bandits.
result Demonstrates 'mismatched sampling paradox' where knowing distributions can lead to worse performance.
Many theoretical results on estimation of high dimensional time series require specifying an underlying data generating model (DGM). Instead, along the footsteps of~\cite{wong2017lasso}, this paper relies only on (strict) stationarity and β β β -mixing condition to establish consistency of lasso when data comes from a $β…
Ridge regression performs optimally in noisy environments with heavy-tailed distributions.
problem Performance of ridge regression in noisy environments with heavy-tailed noise.
method Established excess risk bounds using integral operator framework and Fuk-Nagaev inequality.
result Ridge regression achieves optimal convergence rates under heavy-tailed noise, demonstrating robustness.
We present a theory for Euclidean dimensionality reduction with subgaussian matrices which unifies several restricted isometry property and Johnson-Lindenstrauss type results obtained earlier for specific data sets. In particular, we recover and, in several cases, improve results for sets of sparse and structured spars…
New algorithms exploit mean bounds to improve bandit problem performance.
problem Improving bandit problem performance with side information on arm means.
method Developed novel algorithms R-OFUL and GLUE exploiting mean bounds for tighter estimates and reduced exploration.
result Regret bounds for R-OFUL and GLUE are never worse than standard algorithms, demonstrating improved performance.
Robustly estimates linear regression coefficients with adversarial and noisy data.
problem Estimating robust linear regression coefficients with adversarial and noisy data.
method Adversarial robust weighted Huber regression with polynomial computational complexity.
result Derives an estimation error bound that depends on the stable rank and condition number of the covariance matrix.
RONM method reduces regret in stochastic convex bandits with decreasing noise.
problem Stochastic convex bandit problem with decreasing noise.
method Regularized Online Newton Method (RONM) based on Online Newton Method (ONM).
result RONM achieves polylogarithmic regret in time horizon n.
New algorithm for robust regression with subgaussian error bound.
problem Linear regression in the presence of outliers and finite moments.
method Adaptation of spectral method to linear regression problem.
result Optimal sub-gaussian error bound for robust regression.
New algorithms allocate sampling budget to estimate group means without exploration.
problem Allocate sampling budget to estimate means of multiple groups.
method Design exploration-free non-adaptive and adaptive algorithms.
result Prove tighter regret bounds for multi-group mean estimation.
Improved mean estimation for symmetric distributions with finite-sample guarantees.
problem Estimating the mean of a symmetric distribution from samples.
method Using Fisher information rate for finite-sample guarantees.
result Finite-sample convergence close to subgaussian with variance 1/(n * I_r), where I_r is r-smoothed Fisher information.
Selecting hyperparameters for unsupervised learning problems is challenging in general due to the lack of ground truth for validation. Despite the prevalence of this issue in statistics and machine learning, especially in clustering problems, there are not many methods for tuning these hyperparameters with theoretical …
The paper provides entrywise bounds for Sparse PCA, improving upon previous results.
problem Sparse Principal Component Analysis (PCA) recovery error characterization in spectral or Frobenius norms.
method Entrywise ℓ 2 , ∞ \ell_{2,\infty} ℓ 2 , ∞ bounds for Sparse PCA under general high-dimensional subgaussian design, using sparsistent algorithms. result Improved entrywise bounds for Sparse PCA, finer characterization of estimation error.
New bounds derived for machine learning algorithms using convex functions.
problem Bounding generalization error in machine learning.
method Using strongly convex functions and subgaussian loss tails, derived new generalization bounds.
result Generalization bounds can be derived using any strongly convex function of the joint input-output distribution.
New algorithm optimizes convex functions with noisy evaluations in one dimension.
problem Optimizing convex functions with noisy zero-order evaluations in one dimension.
method Proposed a computationally efficient algorithm achieving O ( 1 / T ) O(1/\sqrt{T}) O ( 1/ T ) convergence rate. result Achieved the optimal O ( 1 / T ) O(1/\sqrt{T}) O ( 1/ T ) convergence rate, closing the gap in one dimension. Estimates change point in high dimensional time series models.
problem Change point estimation in high dimensional time series.
method Plug-in least squares estimator with sufficient conditions for adaptivity.
result Optimal rate of convergence O p ( ξ − 2 ) O_p(ξ^{-2}) O p ( ξ − 2 ) in integer scale. New IDS algorithm refines parameter norm bounds for better bandit performance.
problem Frequentist IDS requires tight norm bounds, which are often unavailable in practice.
method Iteratively refines a high-probability upper bound on true parameter norm using data.
result Regret bounds independent of assumed parameter norm, outperforming state-of-the-art algorithms.
This note gives a simple analysis of a randomized approximation scheme for matrix multiplication proposed by Sarlos (2006) based on a random rotation followed by uniform column sampling. The result follows from a matrix version of Bernstein's inequality and a tail inequality for quadratic forms in subgaussian random ve…
We solve robust regression and matrix completion problems with sparse and low-rank models.
problem Adversarial contamination and noisy matrix completion in high-dimensional settings.
method Subgaussian statistical learning framework, trace-regression with matrix decomposition, novel Huber-type loss.
result Near-optimal estimation rates for robust regression and matrix completion.
Bandit algorithms struggle with consistent performance and robustness.
problem Achieving consistent and robust performance in stochastic multi-armed bandit settings.
method Analyzing regret minimization trade-offs and proposing distribution-oblivious algorithms.
result Logarithmic regret is inconsistent and super-logarithmic regret is necessary for consistent learning.
We study tilting subweibull distributions and their tail behavior.
problem Understanding tail behavior of subweibull distributions.
method Alternative characterizations and conditions for tail behavior preservation.
result Conditions for tail behavior preservation after exponential tilting.
This paper tackles open problem of tight bounds for KBs with Bernoulli rewards.
problem Open problem of tight bounds for Kernelized Bandits with Bernoulli rewards.
method Focus on Bernoulli model, not subgaussian noise, and optimize function in RKHS.
result Open problem remains unsolved in this context.
Analysis of non-asymptotic estimation error and structured statistical recovery based on norm regularized regression, such as Lasso, needs to consider four aspects: the norm, the loss function, the design matrix, and the noise model. This paper presents generalizations of such estimation error analysis on all four aspe…
We show that if F F F is a convex class of functions that is L L L -subgaussian, the error rate of learning problems generated by independent noise is equivalent to a fixed point determined by `local' covering estimates of the class, rather than by the gaussian averages. To that end, we establish new sharp upper and lower e…
Estimates score function from data with optimal rate in high dimensions.
problem Estimating the score function of an unknown probability distribution from data.
method Empirical Bayes smoothing with a Gaussian kernel.
result Optimal rate of estimation i l d e Θ ( n − 2 d + 4 ) ilde \Theta(n^{-\frac{2}{d+4}}) i l d e Θ ( n − d + 4 2 ) for d d d dimensions. I introduce and analyse an anytime version of the Optimally Confident UCB (OCUCB) algorithm designed for minimising the cumulative regret in finite-armed stochastic bandits with subgaussian noise. The new algorithm is simple, intuitive (in hindsight) and comes with the strongest finite-time regret guarantees for a hori…
We solve ReLU regression with efficient approximations for various distributions.
problem Finding the best fitting ReLU function with square loss from unknown distributions.
method Introduced efficient constant-factor approximation algorithm and polynomial-time approximation scheme.
result First constant-factor approximation algorithm for ReLU regression with weak concentration conditions.
The new field of adaptive data analysis seeks to provide algorithms and provable guarantees for models of machine learning that allow researchers to reuse their data, which normally falls outside of the usual statistical paradigm of static data analysis. In 2014, Dwork, Feldman, Hardt, Pitassi, Reingold and Roth introd…
New TS algorithms improve performance in non-stationary multi-armed bandit problems.
problem Sequential decision-making with evolving action rewards.
method Sliding-window Thompson sampling approaches with different priors.
result Unified regret upper bound for arbitrary non-stationary MABs.
The study analyzes the performance of a nonparametric estimator for dynamical systems.
problem Analyzing the performance of a nonparametric estimator for dynamical systems.
method Nonparametric least squares estimator (LSE) and information-theoretic methods.
result Rate-optimal error bounds for nonparametric hypotheses classes.
This paper analyzes the sample complexity of SPS method for scalar linear regression.
problem Analyzing the sample complexity of the Sign-Perturbed Sums (SPS) identification method.
method The paper provides high probability upper bounds for the sizes of SPS confidence intervals under different sets of assumptions.
result The sizes of SPS confidence intervals shrink at a geometric rate around the true parameter, if observation noises are subgaussian.
This work establishes near-minimax optimal guarantees for ODE-based samplers under mild assumptions.
problem Develop rigorous statistical guarantees for ODE-based samplers in generative modeling.
method Proposes a smooth regularized score estimator and refined convergence analysis.
result Achieves minimax rate in total variation distance for ODE-based samplers under mild assumptions.
Diffusion models learn multi-modal distributions with optimal efficiency.
problem Learning high-dimensional distributions with low-dimensional multi-modal structures.
method Score-based diffusion models, focusing on subgaussian distributions within subspaces.
result Diffusion models require O ~ ( ε − k ∨ 2 ) \widetilde{O}(\varepsilon^{-k \vee 2}) O ( ε − k ∨ 2 ) samples for 1-Wasserstein ε \varepsilon ε error, improving over prior guarantees. Estimates mean from heavy-tailed data without variance.
problem Estimating mean from distributions with non-existent variance.
method Developed a computationally efficient estimator for weak-moment distributions.
result Achieved optimal confidence interval for general α.
New bounds for learning polynomial surrogates with L ∞ L_\infty L ∞ guarantees.
problem Learning polynomial surrogates for bounded binary functions with L ∞ L_\infty L ∞ error guarantees. method Characterized minimax sample complexity for two classes of polynomials under subgaussian noise.
result Sample complexity rates differ from noiseless case, scaling as n d + 1 n^{d+1} n d + 1 for degree d d d polynomials and n s 2 ns^2 n s 2 for sparse polynomials. Suppose that we observe y ∈ R f y \in \mathbb{R}^f y ∈ R f and X ∈ R f × m X \in \mathbb{R}^{f \times m} X ∈ R f × m in the following errors-in-variables model: \begin{eqnarray*} y & = & X_0 β^* + ε\\ X & = & X_0 + W \end{eqnarray*} where X 0 X_0 X 0 is a f × m f \times m f × m design matrix with independent subgaussian row vectors, ε ∈ R f ε\in \mathbb{R}^f ε ∈ R f is a noise vector…