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.
This work achieves exponential concentration in heavy-tailed data over CAT(κ) spaces using the Fréchet median.
problem Achieving robust estimation in heavy-tailed data distributions.
method Developing a concentration bound for the Fréchet median in CAT(κ) spaces.
result Exponential concentration of the Fréchet median in CAT(κ) spaces over heavy-tailed data.
New approach to concentration inequalities for unbounded state space dynamical systems.
problem Concentration inequalities for unbounded state space dynamical systems.
method Functional analytic framework, transport-entropy inequality.
result Exponential concentration inequalities for sampling from stationary distribution.
We study concentration phenomena of eigenfunctions of the Laplacian on closed Riemannian manifolds. We prove that the volume measure of a closed manifold concentrates around nodal sets of eigenfunctions exponentially. Applying the method of Colding and Minicozzi we also prove restricted exponential concentration inequa…
Quantum kernel methods can lead to trivial models due to exponential concentration of kernel values.
problem Exponential concentration of quantum kernel values can lead to trivial models in QML.
method Analyzing the resources needed to accurately estimate quantum kernel values and identifying four sources of concentration.
result Quantum kernel values can be exponentially concentrated, leading to trivial models.
We consider a priori generalization bounds developed in terms of cross-validation estimates and the stability of learners. In particular, we first derive an exponential Efron-Stein type tail inequality for the concentration of a general function of n independent random variables. Next, under some reasonable notion of s…
Paper addresses concentration of distances for fractional quasi p-norms, identifying conditions for concentration and anti-concentration.
problem Understanding concentration of distances for fractional quasi p-norms in high dimensions.
method Analyzes conditions for concentration and anti-concentration of distances for fractional quasi p-norms.
result Identifies conditions for concentration and anti-concentration of fractional quasi p-norms, ruling out some approaches and specifying conditions for control.
Improved concentration inequalities for sub-Weibull variables enhance statistical and machine learning applications.
problem Improving concentration inequalities for sub-Weibull random variables.
method Developed new concentration inequalities for sums of independent sub-Weibull random variables, including a new sub-Weibull parameter.
result New concentration inequalities with sharper constants and a mixture of sub-Gaussian and sub-Weibull tails.
Stochastic approximation algorithms show exponential progress bounds.
problem Analyzing the convergence of stochastic approximation algorithms.
method Developed geometric ergodicity proofs to establish exponential concentration bounds.
result Proved faster convergence rates for specific algorithms.
A new model CDTM improves text classification by concentrating document topics.
problem Unsupervised text classification with diverse topic distributions.
method Imposes an exponential entropy penalty on document topic distribution to encourage concentration.
result More coherent topics and concentrated, sparse document-topic distributions.
We consider the problem of estimating a spectral risk measure (SRM) from i.i.d. samples, and propose a novel method that is based on numerical integration. We show that our SRM estimate concentrates exponentially, when the underlying distribution has bounded support. Further, we also consider the case when the underlyi…
Barren plateaus are not an average-case phenomenon, but a highly non-unique problem.
problem Avoiding barren plateaus in neural network training
method First-moment framework for initialization strategies
result Many families of inequivalent initialization strategies can avoid concentration
We analyze a plug-in estimator for a large class of integral functionals of one or more continuous probability densities. This class includes important families of entropy, divergence, mutual information, and their conditional versions. For densities on the d-dimensional unit cube [0,1]d that lie in a β-Hölder s…
The paper studies Dirac operators and their solutions concentrating near singular sets.
problem Understanding concentration properties of solutions to Dirac equations.
method Analyzes Dirac operators of the form Dε=D+ε−1A and their solutions. result Solutions concentrate exponentially near the locus where the rank of ker(A) jumps. 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.
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.
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. This work uses statistical mechanics to explain AI learning.
problem Understanding the statistical principles behind AI learning.
method Starting from sample concentration behaviors, the study applies statistical mechanics principles to AI and machine learning.
result Exponential families and statistical quantities are key in AI and machine learning.
Paper establishes convergence rates and concentration bounds for stochastic approximation and reinforcement learning with Markovian noise.
problem Analyzing convergence rates and concentration bounds for stochastic approximation and reinforcement learning with Markovian noise.
method Novel discretization of the mean ODE of stochastic approximation algorithms using intervals with diminishing length.
result First almost sure convergence rate and maximal concentration bound with exponential tails for contractive stochastic approximation algorithms with Markovian noise.
Quantum systems with scrambling improve temporal information processing, but scaling requires exponential overhead.
problem Scalability and memory retention of quantum reservoirs in temporal information processing.
method Examined a quantum reservoir processing framework with scrambling reservoirs modeled by high-order unitary designs, analyzed in noiseless and noisy settings.
result Memory retention improves exponentially with reservoir size but worsens with reservoir iterations, requiring exponential shot overhead for scaling.
Greedy algorithm achieves sublinear regret for various distributions.
problem Efficient performance of greedy algorithms in linear contextual bandit problems.
method Introduced Local Anti-Concentration (LAC) condition to ensure sublinear regret.
result Greedy algorithm achieves O(polylogT) cumulative expected regret. Improved sample complexity for identifying best policies in risk-sensitive reinforcement learning.
problem Identifying approximately optimal policies in risk-sensitive reinforcement learning with exponential horizon dependence.
method Forward-model based algorithm with KL-based exploration bonuses adapted for entropic criterion, leveraging smoothness properties of exponential utility and a new stopping rule.
result Achieved sample complexity matching the lower bound, closing the gap between upper and lower bounds.
We prove near-tight concentration of measure for polynomial functions of the Ising model under high temperature. For any degree d, we show that a degree-d polynomial of a n-spin Ising model exhibits exponential tails that scale as exp(−r2/d) at radius r=Ω~d(nd/2). Our concentration radius is opti…
Conditional Value-at-Risk (CVaR) is a widely used risk metric in applications such as finance. We derive concentration bounds for CVaR estimates, considering separately the cases of light-tailed and heavy-tailed distributions. In the light-tailed case, we use a classical CVaR estimator based on the empirical distributi…
Thompson Sampling has been demonstrated in many complex bandit models, however the theoretical guarantees available for the parametric multi-armed bandit are still limited to the Bernoulli case. Here we extend them by proving asymptotic optimality of the algorithm using the Jeffreys prior for 1-dimensional exponential …
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.
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 study proves inequalities and curvature properties for Markov chains.
problem Isoperimetric and concentration inequalities for Markov chains.
method Laplacian separation principle for eikonal equation; modified log-Sobolev constant; Ollivier curvature.
result Affirmative answers to open questions and new inequalities.
This paper gives new concentration inequalities for the spectral norm of a wide class of matrix martingales in continuous time. These results extend previously established Freedman and Bernstein inequalities for series of random matrices to the class of continuous time processes. Our analysis relies on a new supermarti…
Sharp Gaussian isoperimetry proven along Ricci flow.
problem Proving sharp Gaussian isoperimetric inequality for Ricci flow.
method Using monotonicity formula to prove inequality.
result Exact Gaussian enlargement theorem and concentration estimates.
A robust conformal method for set estimation using non-conformity scores.
problem Lack of robustness in standard conformal prediction methods for outliers or heavy tails.
method Robust conformal method based on non-conformity score defined as half-mass radius.
result Empirical conformal regions converge to robust population central set.
The paper proves concentration inequalities for diffusion processes.
problem Proving concentration inequalities for diffusion processes.
method Analysis via the Poisson equation for a broad class of subexponentially ergodic processes.
result Demonstrates power of concentration inequalities in validating conditions for Lasso estimation and sampling algorithms.
Estimating divergences in a consistent way is of great importance in many machine learning tasks. Although this is a fundamental problem in nonparametric statistics, to the best of our knowledge there has been no finite sample exponential inequality convergence bound derived for any divergence estimators. The main cont…
We analyze the generalized Mallows model, a popular exponential model over rankings. Estimating the central (or consensus) ranking from data is NP-hard. We obtain the following new results: (1) We show that search methods can estimate both the central ranking pi0 and the model parameters theta exactly. The search is n!…
There is accumulating evidence in the literature that stability of learning algorithms is a key characteristic that permits a learning algorithm to generalize. Despite various insightful results in this direction, there seems to be an overlooked dichotomy in the type of stability-based generalization bounds we have in …
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.
Estimates stationary mass and frequency from non-i.i.d. data.
problem Estimating stationary mass and frequency from non-i.i.d. data.
method Combines plug-in estimator with WingIt modification for exponentially α-mixing processes. result Universal consistency in n for total variation distance estimation. Frame flows on certain symmetric spaces mix exponentially.
problem Exponential mixing of frame flows in convex cocompact locally symmetric spaces.
method Generalized local non-integrability and non-concentration properties to apply Dolgopyat's method.
result Exponential mixing of frame flows proved for convex cocompact locally symmetric spaces.
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 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. Robustly learns Ising models with corrupted data.
problem Learning Ising models corrupted by a constant fraction of adversarial samples.
method Develops a computationally efficient algorithm for robust learning.
result First near-optimal error guarantees for robust learning of Ising models.
We provide upper bounds of the expected Wasserstein distance between a probability measure and its empirical version, generalizing recent results for finite dimensional Euclidean spaces and bounded functional spaces. Such a generalization can cover Euclidean spaces with large dimensionality, with the optimal dependence…
A new MMD-based test combines kernels for two-sample testing without splitting data.
problem Efficiently testing if two datasets come from the same distribution without splitting data.
method Proposes a novel statistic based on Maximum Mean Discrepancy (MMD) that combines kernels, proving concentration bounds and showing data-dependent kernel selection.
result Exponential concentration bounds and improved test power compared to existing methods.
We study the concentration of random kernel matrices around their mean. We derive nonasymptotic exponential concentration inequalities for Lipschitz kernels assuming that the data points are independent draws from a class of multivariate distributions on Rd, including the strongly log-concave distributions u…
In this paper, we present a simple analysis of {\bf fast rates} with {\it high probability} of {\bf empirical minimization} for {\it stochastic composite optimization} over a finite-dimensional bounded convex set with exponential concave loss functions and an arbitrary convex regularization. To the best of our knowledg…
We study the problem of cooperative inference where a group of agents interact over a network and seek to estimate a joint parameter that best explains a set of observations. Agents do not know the network topology or the observations of other agents. We explore a variational interpretation of the Bayesian posterior de…
New method learns shared structures in non-linear tasks.
problem Learning shared linear representations in non-linear tasks.
method Convex optimization with structural assumptions.
result Rank and clustered estimators recover shared structures under certain conditions.
This paper proves exponential mixing for frame flows on hyperbolic manifolds with cusps.
problem Establishing exponential mixing for frame flows on geometrically finite hyperbolic manifolds with cusps.
method Symbolic coding of geodesic flow, Dolgopyat's method, large deviation property, combinatorics of cusp excursions, renewal theorem.
result Frame flows for geometrically finite hyperbolic manifolds of arbitrary dimensions are exponentially mixing.