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.
Characterizes uncertainty in low-rank matrix completion with noisy data.
problem Uncertainty quantification in low-rank matrix completion with heterogeneous sub-exponential noise.
method Characterizes the distribution of estimated matrix entries under low-rank estimators with heterogeneous sub-exponential noise.
result Explicit formulas for the distribution of estimated matrix entries under Poisson and Binary noise.
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…
The study provides error bounds for the generalized Lasso with sub-exponential data.
problem Analyzing the generalized Lasso under sub-exponential data distributions.
method Non-asymptotic analysis using generic chaining-based proof strategy.
result Error bounds for the generalized Lasso can be controlled by two complexity parameters.
Paper establishes universal lower bounds and optimal rates for clustering sub-exponential mixture models.
problem Achieving optimal error rates in clustering sub-exponential mixture models.
method Establishes universal lower bounds and demonstrates iterative algorithms' optimality in sub-exponential mixture models.
result Iterative algorithms achieve the universal lower bound in sub-exponential mixture models.
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.
Quantifies polynomial approximation rates for smooth functions under various distributions.
problem Approximating smooth functions with polynomials under different distributional constraints.
method Develops a quantitative analogue of Carleman's theorem using complex analysis.
result Establishes superexponential rates of approximation for certain function classes over general distributions.
The Langevin Algorithm's stationary distribution is shown to be sub-exponential or sub-Gaussian under certain conditions.
problem Understanding the properties of the Langevin Algorithm's stationary distribution.
method Analysis using a rotation-invariant moment generating function (Bessel function) to study the stationary dynamics of the Langevin Algorithm.
result Concentration results for the Langevin Algorithm's stationary distribution πη are established, showing it is sub-exponential or sub-Gaussian under convex or strongly convex potential conditions. Kernel thinning compresses distributions more effectively than i.i.d. sampling or standard thinning.
problem Efficiently compressing distributions for better sampling and integration accuracy.
method Introduces kernel thinning, a procedure that compresses an n-point approximation of a distribution into a sqrt(n)-point approximation with comparable integration error.
result Kernel thinning achieves a maximum discrepancy in integration error of O_d(n^(-1/2) sqrt(log n)) in probability for compactly supported distributions and O_d(n^(-1/2) (log n)^(d+1/2) sqrt(log log n)) for sub-exponential distributions.
The paper explores how benign overfitting occurs in heavy-tailed input distributions.
problem Understanding overfitting in heavy-tailed input distributions.
method Analysis of maximum margin classifiers on unregularized logistic loss with gradient descent.
result Linear classifiers trained under certain conditions can asymptotically achieve the noise level as misclassification error.
Generative Adversarial Networks improve robust statistics for various distributions.
problem Estimating unknown parameters in adversarially corrupted samples.
method Designing GANs with specific loss functions for robust estimation.
result Extends robust estimation to broader families of distributions.
The paper introduces a new method for tail bounds of random vectors and matrices.
problem Estimating norms of random vectors and matrices under moment assumptions.
method Variational tail bounds for norms of random vectors and matrices.
result Dimension-free concentration inequalities for various norms of random vectors and matrices.
A novel algorithm minimizes regret in a multi-agent bandit problem with time-varying random graphs and heterogeneous rewards.
problem Minimizing regret in a multi-agent multi-armed bandit problem with time-varying random graphs and heterogeneous rewards.
method Introduces a novel algorithmic framework combining averaging-based consensus with a weighting technique and upper confidence bound.
result Derives optimal instance-dependent regret upper bounds of order logT in both sub-gaussian and sub-exponential environments. 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…
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.
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…
We show that there is no bi-Lipschitz homeomorphism of R2 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.
The paper reviews and improves concentration inequalities for statistical inference.
problem Analyzing statistical inference in various settings with high-dimensional data.
method Review and improvement of concentration inequalities for different types of random variables and statistical measures.
result Fresh new results and improved bounds with sharper constants.
New algorithms achieve high-probability parameter-free regret in online convex optimization with heavy-tailed data.
problem Achieving high-probability parameter-free regret in online convex optimization with heavy-tailed data.
method Developed new regularization techniques to handle exponentially large iterates and heavy-tailed subgradients.
result Achieved regret bound of O(∥u∥T1/plog(1/δ)) with high probability for subgradients with bounded pth moments. Paper develops a robust PP distributed quasi-Newton estimation for Byzantine machines.
problem Byzantine machines in distributed computing under Privacy Protection constraints.
method Robust PP distributed quasi-Newton estimation method that transmits only five vectors.
result Reduces privacy budgeting and transmission cost compared to gradient descent and Newton iteration.
Sharp concentration inequalities for sub-Orlicz random variables with phase transition at α=2.
problem Developing concentration inequalities for sub-Orlicz random variables with phase transition.
method New theoretical analysis framework involving variance and min/max functions of Orlicz tails.
result Sharp concentration inequalities with phase transition at α=2 for sub-Orlicz random variables.
Study robust linear regression without distributional assumptions for heavy-tailed responses.
problem Linear regression with heavy-tailed responses and no distributional assumptions.
method Combining truncated least squares, median-of-means, and aggregation theory to construct a non-linear estimator.
result Achieves excess risk of order d/n with optimal sub-exponential tail. New algorithm reduces semi-bandit regret using covariance estimates.
problem Complexity of semi-bandits due to joint distribution of outcomes.
method Develops a new sub-exponential distribution family and an algorithm using covariance estimates.
result Proves a new lower bound on expected regret and constructs an algorithm with asymptotic analysis.
Analytic networks with bounded coefficients can't outperform polynomial approximations.
problem Approximation limits of neural networks with analytic activation functions under coefficient constraints.
method Deterministic analysis using comparison argument and Bernstein-type estimates.
result Networks with analytic activation functions and controlled coefficients cannot outperform classical polynomial approximation rates on non-analytic targets.
The study investigates how branch points affect the shape and mechanics of hyperbolic surfaces.
problem Understanding the role of branch points in the shape and mechanics of hyperbolic surfaces.
method Developed a discrete differential geometric (DDG) approach to study deformations of hyperbolic objects with distributed branch points.
result Branch points influence the overall morphology of hyperbolic surfaces without concentrating energy, leading to sub-exponential growth in maximum curvature.
We consider the problem of learning a mixture of linear regressions (MLRs). An MLR is specified by k nonnegative mixing weights p1,…,pk summing to 1, and k unknown regressors w1,...,wk∈Rd. A sample from the MLR is drawn by sampling i with probability pi, then outputting (x,y) wh…
Annealed Entropic Allocation improves ranking and selection by mitigating hard switching and improving finite-budget discrimination.
problem Sequential budget allocation in ranking and selection
method Annealed weighted soft-min framework
result Surrogate converges uniformly to the hard minimum, soft-min weights concentrate on active challengers, and target allocation map is continuous.
Novel bounds for SGLD show generalization error decreases with more samples.
problem Understanding the generalization error of SGLD in non-convex optimization.
method Information-theoretic approach focusing on Kullback-Leibler divergence and sub-exponential loss function.
result Time-independent generalization bounds for SGLD, independent of step size and number of iterations.
Using a family of modified Weibull distributions, encompassing both sub-exponentials and super-exponentials, to parameterize the marginal distributions of asset returns and their natural multivariate generalizations, we give exact formulas for the tails and for the moments and cumulants of the distribution of returns o…
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 …
Langevin Dynamics fails to sample from mixture distributions efficiently.
problem Analyzing Langevin Dynamics for sampling from mixture distributions.
method Theoretical analysis of Langevin Dynamics and proposing Chained-Langevin Dynamics.
result Langevin Dynamics fails to sample from mixture distributions efficiently.
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.
We study the problem of finding the best linear model that can minimize least-squares loss given a data-set. While this problem is trivial in the low dimensional regime, it becomes more interesting in high dimensions where the population minimizer is assumed to lie on a manifold such as sparse vectors. We propose proje…
We develop time-uniform confidence spheres for estimating means of random vectors.
problem Sequential mean estimation in high-dimensional spaces.
method Derive time-uniform confidence sphere sequences (CSSs) for various types of random vectors.
result Optimal CSSs for log-concave, sub-Gaussian, and sub-ψ random vectors. Combining diffusion models with Langevin dynamics improves posterior sampling efficiency.
problem Sampling from noisy posterior distributions efficiently.
method Annealed Langevin dynamics combined with diffusion models.
result Achieves posterior sampling in polynomial time with a weaker score error bound.
We introduce a new set of consistent measures of risks, in terms of the semi-invariants of pdf's, such that the centered moments and the cumulants of the portfolio distribution of returns that put more emphasis on the tail the distributions. We derive generalized efficient frontiers, based on these novel measures of ri…
Paper optimizes change-point detection using learned distributions from training sequences.
problem Optimal change-point detection with unknown pre- and post-change distributions.
method Designs a change-point estimator using training sequences and test sequences.
result Optimal confidence width characterized as a function of undetected error.
Decision trees are consistent for regression and classification tasks even with many predictors.
problem Consistency of decision trees with many predictors.
method CART and C4.5 methodology, oracle inequality, sparsity constraints.
result Decision trees and random forests are consistent for various types of data.
The paper develops a minimax optimal method for high-dimensional regression using auxiliary data.
problem High-dimensional additive regression with heavy-tailed errors and transfer learning.
method Smooth backfitting estimator with local linear smoothing, followed by a two-stage estimation method.
result The method achieves the minimax optimal rate under certain conditions.
High-dimensional diffusion models suffer from distorted samples due to CFG.
problem Distortions in high-dimensional guided diffusion models.
method Analytical tools from statistical physics, dynamic mean-field theory.
result Distortions arise in high-dimensional settings due to class separability issues.
Paper studies early-stopped mirror descent for noisy sparse phase retrieval.
problem Recovering a sparse signal from noisy quadratic measurements.
method Early-stopped mirror descent with hyperbolic entropy mirror map.
result Achieves nearly minimax-optimal rate of convergence for k-sparse signals. 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…
Optimizes regret distribution in stochastic bandits for risk balance.
problem Balancing regret expectation and tail risk in stochastic bandits.
method Characterizes optimal regret tail probability for any threshold, proposes new policies.
result Discovers an intrinsic gap in optimal tail rate based on time horizon uncertainty.
Paper introduces a novel method for dynamic covariance estimation with random forests.
problem Estimating high-dimensional dynamic covariance matrices with multiple covariates.
method Nonparametric approach using random forests.
result Uniform consistency theory and error rates established for high-dimensional scenarios.
Algorithm learns mixtures of Gaussians efficiently using diffusion models.
problem Learning mixtures of Gaussians with identity covariance.
method Analytic approach using diffusion models to learn score functions.
result Quasi-polynomial time and sample complexity for learning mixtures.
Efficiently estimates covariance matrix for elliptical distributions under strong contamination.
problem Robust estimation of covariance matrix in the presence of adversarial corruptions.
method Proposes an algorithm that uses spatial sign of elliptical distributions and spectral covariance filtering.
result Achieves nearly optimal error guarantee for various elliptical distributions.
This paper presents a unified approach based on Wasserstein distance to derive concentration bounds for empirical estimates for two broad classes of risk measures defined in the paper. The classes of risk measures introduced include as special cases well known risk measures from the finance literature such as condition…
We improve bounds for stochastic processes, especially those with heavy tails.
problem Bounding the concentration of sub-ψ processes with heavy tails. method Variational approach to concentration, focusing on sub-Gaussian and other tail conditions.
result First dimension-free self-normalized empirical Bernstein inequality.