arXiv research

Ridge regression performs optimally in noisy environments with heavy-tailed distributions.

RONM method reduces regret in stochastic convex bandits with decreasing noise.

Robustly estimates linear regression coefficients with adversarial and noisy data.

New algorithm optimizes convex functions with noisy evaluations in one dimension.

Proves subgaussian distributions are SoS-certifiably subgaussian, enabling efficient algorithms for various statistical tasks.

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.

This paper tackles open problem of tight bounds for KBs with Bernoulli rewards.

Note on subgaussian bounds for sign-quantized linear maps.

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$ is a convex class of functions that is $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…

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 robust regression and matrix completion problems with sparse and low-rank models.

This paper analyzes the sample complexity of SPS method for scalar linear regression.

New robust estimators achieve subgaussian bounds using VC-dimension.

New bounds for learning polynomial surrogates with $L_\infty$ guarantees.

New algorithms robustly estimate mean with near-optimal error rates.

Deep neural networks help recover two signals from noisy mixtures.

Paper estimates EOT maps for non-compactly supported measures with subGaussian target.

Study generalizes matrix completion with side info in low noise settings.

Suppose that we observe $y \in \mathbb{R}^f$ and $X \in \mathbb{R}^{f \times m}$ in the following errors-in-variables model: \begin{eqnarray*} y & = & X_0 β^* + ε\\ X & = & X_0 + W \end{eqnarray*} where $X_0$ is a $f \times m$ design matrix with independent subgaussian row vectors, $ε\in \mathbb{R}^f$ is a noise vector…

This work studies applications and generalizations of a simple estimation technique that provides exponential concentration under heavy-tailed distributions, assuming only bounded low-order moments. We show that the technique can be used for approximate minimization of smooth and strongly convex losses, and specificall…

Thompson Sampling shows polynomial regret for combinatorial semi-bandits with subgaussian rewards.

New algorithm reduces bandit regret to log^3(T).

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 $β…

Polynomial-time private algorithm for robust estimation of mean and covariance in the presence of outliers.

Existing strategies for finite-armed stochastic bandits mostly depend on a parameter of scale that must be known in advance. Sometimes this is in the form of a bound on the payoffs, or the knowledge of a variance or subgaussian parameter. The notable exceptions are the analysis of Gaussian bandits with unknown mean and…

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…

We prove several fundamental statistical bounds for entropic OT with the squared Euclidean cost between subgaussian probability measures in arbitrary dimension. First, through a new sample complexity result we establish the rate of convergence of entropic OT for empirical measures. Our analysis improves exponentially o…

Suppose that we observe $y \in \mathbb{R}^n$ and $X \in \mathbb{R}^{n \times m}$ in the following errors-in-variables model: \begin{eqnarray*} y & = & X_0 β^* +ε\\ X & = & X_0 + W, \end{eqnarray*} where $X_0$ is an $n \times m$ design matrix with independent subgaussian row vectors, $ε\in \mathbb{R}^n$ is a noise vecto…

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…

We study an extention of total variation denoising over images to over Cartesian power graphs and its applications to estimating non-parametric network models. The power graph fused lasso (PGFL) segments a matrix by exploiting a known graphical structure, $G$, over the rows and columns. Our main results shows that for …

New algorithm for robust regression with subgaussian error bound.

New algorithms allocate sampling budget to estimate group means without exploration.

Improved mean estimation for symmetric distributions with finite-sample guarantees.

The paper provides entrywise bounds for Sparse PCA, improving upon previous results.

New bounds derived for machine learning algorithms using convex functions.

This work establishes safe reinforcement learning for LQR with nonlinear baselines.

Paper proposes a new tensor model for mixed memberships and provides error bounds.

Estimates change point in high dimensional time series models.

We study a variant of the bandit problem where side information in the form of bounds on the mean of each arm is provided. We prove that these translate to tighter estimates of subgaussian factors and develop novel algorithms that exploit these estimates. In the linear setting, we present the Restricted-set OFUL (R-OFU…

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…

Bandit algorithms struggle with consistent performance and robustness.

We study tilting subweibull distributions and their tail behavior.

FGTSVA improves Thompson Sampling for contextual bandits with optimal variance-aware regret.

Estimates score function from data with optimal rate in high dimensions.

We solve ReLU regression with efficient approximations for various distributions.

New IDS algorithm refines parameter norm bounds for better bandit performance.

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…