arXiv research

Characterizes uncertainty in low-rank matrix completion with noisy data.

We consider the problem of unconstrained online convex optimization (OCO) with sub-exponential noise, a strictly more general problem than the standard OCO. In this setting, the learner receives a subgradient of the loss functions corrupted by sub-exponential noise and strives to achieve optimal regret guarantee, witho…

Paper establishes universal lower bounds and optimal rates for clustering sub-exponential mixture models.

SGD converges to an invariant distribution with sub-Gaussian or sub-exponential properties.

Proves new concentration inequalities for sub-gaussian and sub-exponential variables.

New bounds for kernel regression under non-Gaussian noise.

The study provides error bounds for the generalized Lasso with sub-exponential data.

Paper studies early-stopped mirror descent for noisy sparse phase retrieval.

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…

The paper explores how benign overfitting occurs in heavy-tailed input distributions.

Wavelet-based online learning adapts to noisy Besov spaces with high probability.

The matrix completion problem consists in reconstructing a matrix from a sample of entries, possibly observed with noise. A popular class of estimator, known as nuclear norm penalized estimators, are based on minimizing the sum of a data fitting term and a nuclear norm penalization. Here, we investigate the case where …

Using a family of modified Weibull distributions, encompassing both sub-exponentials and super-exponentials, to parameterize the marginal distributions of asset returns and their multivariate generalizations with Gaussian copulas, we offer exact formulas for the tails of the distribution $P(S)$ of returns $S$ of a port…

We consider the problem of learning a mixture of linear regressions (MLRs). An MLR is specified by $k$ nonnegative mixing weights $p_1, \ldots, p_k$ summing to $1$, and $k$ unknown regressors $w_1,...,w_k\in\mathbb{R}^d$. A sample from the MLR is drawn by sampling $i$ with probability $p_i$, then outputting $(x, y)$ wh…

Paper improves confidence intervals and variance estimation for deep learning models.

Paper develops a TR-SSQP method for noisy optimization with heavy-tailed noise.

Efficient method for tensor linear form inference with noisy incomplete data.

This paper considers the noisy sparse phase retrieval problem: recovering a sparse signal $x \in \mathbb{R}^p$ from noisy quadratic measurements $y_j = (a_j' x )^2 + ε_j$, $j=1, \ldots, m$, with independent sub-exponential noise $ε_j$. The goals are to understand the effect of the sparsity of $x$ on the estimation prec…

We show that the regulator, which is the difference between the homology torsion and the combinatorial Ray-Singer torsion, of fnite abelian coverings of a fixed complex has sub-exponential growth rate.

Quantifies polynomial approximation rates for smooth functions under various distributions.

We show that there is no bi-Lipschitz homeomorphism of $\mathbb{R}^2$ that maps a spiral with a sub-exponential decay of winding radii to an unwinded arc. This result is sharp as shows an example of a logarithmic spiral.

While considerable advances have been made in estimating high-dimensional structured models from independent data using Lasso-type models, limited progress has been made for settings when the samples are dependent. We consider estimating structured VAR (vector auto-regressive models), where the structure can be capture…

New algorithms achieve high-probability parameter-free regret in online convex optimization with heavy-tailed data.

Kernel thinning compresses distributions more effectively than i.i.d. sampling or standard thinning.

The Langevin Algorithm's stationary distribution is shown to be sub-exponential or sub-Gaussian under certain conditions.

New error bounds for noisy phase retrieval problems using empirical risk minimization.

New analysis improves SGD for robust and quantile regression with sub-quadratic convergence.

Analytic networks with bounded coefficients can't outperform polynomial approximations.

Paper tackles sparse phase retrieval with a novel Bayesian approach.

Annealed Entropic Allocation improves ranking and selection by mitigating hard switching and improving finite-budget discrimination.

Novel bounds for SGLD show generalization error decreases with more samples.

The paper develops a minimax optimal method for high-dimensional regression using auxiliary data.

Algorithm learns mixtures of Gaussians efficiently using diffusion models.

New algorithms recover sparse tensor principal components efficiently.

Generative Adversarial Networks improve robust statistics for various distributions.

The paper introduces a new method for tail bounds of random vectors and matrices.

Many polynomial invariants of knots and links, including the Jones and HOMFLY-PT polynomials, are widely used in practice but #P-hard to compute. It was shown by Makowsky in 2001 that computing the Jones polynomial is fixed-parameter tractable in the treewidth of the link diagram, but the parameterised complexity of th…

New framework controls generalization for heavy-tailed data in RLHF and SGLD.

A novel algorithm minimizes regret in a multi-agent bandit problem with time-varying random graphs and heterogeneous rewards.

New analysis of SGD with MCMC gradient estimator shows convergence rate and saddle point escape.

New method reduces inventory inaccuracies by 10x, saving retailers 4% annually.

The study classifies translating and self-expanding solitons in 3D space.

We investigate deep Bayesian neural networks with Gaussian weight priors and a class of ReLU-like nonlinearities. Bayesian neural networks with Gaussian priors are well known to induce an L2, "weight decay", regularization. Our results characterize a more intricate regularization effect at the level of the unit activat…

Minimizing a convex risk function is the main step in many basic learning algorithms. We study protocols for convex optimization which provably leak very little about the individual data points that constitute the loss function. Specifically, we consider differentially private algorithms that operate in the local model…

In several real-world applications involving decision making under uncertainty, the traditional expected value objective may not be suitable, as it may be necessary to control losses in the case of a rare but extreme event. Conditional Value-at-Risk (CVaR) is a popular risk measure for modeling the aforementioned objec…

The paper reviews and improves concentration inequalities for statistical inference.

New algorithm speeds up knot polynomial calculations.

Sharp concentration inequalities for sub-Orlicz random variables with phase transition at α=2.