Sharp bounds on uniform generalization errors in binary linear classification.
problem Understanding the uniform generalization errors in binary linear classification.
method Isoperimetric arguments, Poincaré and log-Sobolev inequalities for joint distributions.
result Sharp concentration bounds on uniform generalization errors, almost sure convergence in broad settings.
Logistic regression gets a new, simpler uniform bound.
problem Finding a uniform bound for logistic regression's empirical risk.
method PAC-Bayes approach with second-order expansion and Rademacher-complexity bounds.
result Provides a dimension-free uniform concentration bound.
NUTS mixing time scales as d^(1/4) for Gaussian distributions.
problem Improving the efficiency of the No-U-Turn Sampler (NUTS) for Gaussian distributions.
method Coupling argument leveraging geometric structure of Gaussian concentration, uniformity analysis of NUTS transitions.
result The mixing time of NUTS scales as d^(1/4) for Gaussian distributions, up to logarithmic factors.
We give concentration bounds for martingales that are uniform over finite times and extend classical Hoeffding and Bernstein inequalities. We also demonstrate our concentration bounds to be optimal with a matching anti-concentration inequality, proved using the same method. Together these constitute a finite-time versi…
Paper shows how online betting algorithms' regret can be used to create tight confidence sequences.
problem Estimating the expectation of random variables from samples and creating time-uniform confidence sequences.
method Converts the regret guarantee of universal portfolio algorithms into time-uniform concentration inequalities and confidence sequences.
result Numerically obtained confidence sequences are never vacuous and satisfy the law of iterated logarithm.
One fundamental goal in any learning algorithm is to mitigate its risk for overfitting. Mathematically, this requires that the learning algorithm enjoys a small generalization risk, which is defined either in expectation or in probability. Both types of generalization are commonly used in the literature. For instance, …
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.
Uniform TD(0) bound derived for function approximation with Markov noise.
problem Uniform concentration bound for TD(0) with function approximation.
method Contractive stochastic approximation, martingale and Markov noises, Poisson equation, relaxed concentration inequalities.
result Uniform all-time concentration bound for TD(0) with linear function approximation.
The method to derive uniform bounds with Gaussian and Rademacher complexities is extended to the case where the sample average is replaced by a nonlinear statistic. Tight bounds are obtained for U-statistics, smoothened L-statistics and error functionals of l2-regularized algorithms.
Proposes a new latent variable model for hyperspherical latent spaces.
problem Efficiently modeling heavy-tailed distributions in hyperspherical latent spaces.
method Introduces spherical Cauchy (spCauchy) latent variables and applies Möbius transformations.
result Shows spCauchy recovers vMF geometry in high-concentration limits and avoids complex evaluations.
New sampling bounds improve uniform coverage verification in machine learning.
problem Conservative bounds in classical coverage analyses at small failure probabilities.
method Variance-based analysis of uniform random sampling on a d-dimensional unit hypercube. result Sample complexity bound with logarithmic dependence on failure probability.
Study uniform convergence of random walk Laplacians to diffusion Laplacian on smooth manifolds.
problem Uniform convergence of random walk Laplacians to diffusion Laplacian on smooth manifolds.
method Analysis of random walks on geometric and directed kNN graphs, using concentration tools and differential geometry.
result Uniform convergence of kNN Laplacians to diffusion Laplacian, without continuity of transition kernel. New concentration inequality for U-statistics of Markov chains.
problem Proving a concentration inequality for U-statistics of order two in uniformly ergodic Markov chains.
method Inductive analysis using martingale techniques, uniform ergodicity, Nummelin splitting, and Bernstein's inequality.
result Recovery of convergence rate for U-statistics of independent random variables and canonical kernels, with improved results for dependent kernels.
Proves convergence of gradient Ricci shrinkers with uniform bounds.
problem Compactness and energy concentration in gradient Ricci shrinkers.
method Bubble-tree convergence and local energy analysis.
result No energy concentrates in neck regions, leading to a local diffeomorphism finiteness theorem.
Unified framework for robust clustering under various dissimilarity measures.
problem Improving center-based clustering methods to handle outliers and non-Euclidean data.
method Median-of-Means (MoM) estimation framework with uniform concentration bounds.
result Strong consistency and error rate of O(n−1/2) under mild conditions. New assumptions and algorithm solve offline two-player zero-sum Markov games.
problem Solving offline two-player zero-sum Markov games under insufficient assumptions.
method Proposed unilateral concentration assumption and pessimism-type algorithm.
result Algorithm efficiently learns Nash equilibrium under unilateral concentration.
We give tight concentration bounds for mixtures of martingales that are simultaneously uniform over (a) mixture distributions, in a PAC-Bayes sense; and (b) all finite times. These bounds are proved in terms of the martingale variance, extending classical Bernstein inequalities, and sharpening and simplifying prior wor…
Theoretical study of random forests for nonlinear time series.
problem Theoretical justification for using random forests in time series modeling.
method Uniform concentration inequality for regression trees and random forests consistency proof.
result Consistency of random forests for nonlinear autoregressive processes.
Proves existence of solutions with concentrated energy in 2+1 spacetime.
problem Existence of solutions with concentrated energy in 2+1 spacetime.
method Direct treatment of 2+1 Einstein equations, novel scaling, Klainerman-Sobolev inequality.
result Uniform finite-time existence of solutions with positive incoming H1 energy. Expanding on techniques of concentration of measure, we develop a quantitative framework for modeling liquidity risk using convex risk measures. The fundamental objects of study are curves of the form (ρ(λX))λ≥0, where ρ is a convex risk measure and X a random variable, and we call such a curve a \emph{liqu…
Paper introduces risk assessment for contextual bandits without experiments.
problem Evaluate policies using logged data in context bandits.
method Lipschitz risk functionals and Off-Policy Risk Assessment (OPRA) framework.
result OPRA provides finite sample guarantees for various risk estimates.
The paper analyzes SMOTE for imbalanced classification, providing theoretical bounds and guidelines.
problem The challenge of imbalanced classification problems, especially with minority classes.
method Theoretical analysis of SMOTE and related oversampling techniques for minority classes.
result Derives concentration and excess risk bounds for SMOTE and kernel-based classifiers.
New method certifies anti-concentration for various non-Gaussian distributions.
problem Efficiently certifying anti-concentration for non-Gaussian distributions.
method Sum-of-Squares relaxation of integer program for anti-concentration.
result Quasi-polynomial time certificates for non-Gaussian distributions.
UCRL3 improves UCRL2's efficiency in reinforcement learning by reducing exploration.
problem Long burn-in phases in numerical experiments of UCRL2.
method UCRL3 uses state-of-the-art time-uniform concentration inequalities and adaptive support computation to tighten exploration.
result UCRL3 achieves a better numerical improvement over UCRL2 in standard environments.
The paper derives uniform stability-based coverage bounds for conformal prediction methods.
problem Establishing theoretical guarantees for conformal prediction methods.
method Uniform stability perspective applied to full-conformal, jackknife+, and CV+ prediction regions.
result Coverage bounds for finite-dimensional models derived using a concentration argument.
New methods tackle robust reinforcement learning in sparse, corrupted data.
problem Tackles robust reinforcement learning in sparse, corrupted data.
method Proposes actor-critic methods with sparse robust estimator oracles.
result First non-vacuous guarantees in high-dimensional sparse MDPs with single-policy concentrability coverage.
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. Valid p-value for bounded random variables without distributional assumptions.
problem Calibration of predictive algorithms in a distribution-free setting.
method Built a super-uniform p-value based on a concentration inequality.
result Super-uniform p-value is tighter than existing alternatives.
The paper proves Zimmer's conjecture for non-uniform lattices by controlling mass escape and Lyapunov exponents.
problem Proving Zimmer's conjecture for non-uniform lattices in higher-rank semisimple Lie groups.
method Establishes finiteness of low-dimensional actions, introduces novel techniques to control mass escape and Lyapunov exponents.
result Proves Zimmer's conjecture for many non-uniform lattices, improving previous results.
Sharp threshold for exact recovery in non-uniform hypergraph stochastic block model.
problem Community detection in random hypergraphs with non-uniform hyperedge probabilities.
method Sharp threshold established; two efficient algorithms for exact recovery.
result Sharp threshold for exact recovery; information-theoretic lower bound on misclassification.
We compute the expected value of the Kullback-Leibler divergence to various fundamental statistical models with respect to canonical priors on the probability simplex. We obtain closed formulas for the expected model approximation errors, depending on the dimension of the models and the cardinalities of their sample sp…
Paper improves learning efficiency by focusing on effective dimensionality.
problem Dimensionality bottleneck in modern learning tasks.
method Developed tools to reduce dimensional costs using effective dimensionality.
result Uniform concentration bounds involving effective dimensionality, improving over existing results.
Max-sliced Wasserstein metric reduces high-dimensional data to 1D for better estimation.
problem Curse of dimensionality in optimal transport.
method Introduces max-sliced Wasserstein metric to reduce high-dimensional problems to 1D.
result Uniform ratio bounds of empirical measures on RKHS concentrate uniformly fast at parametric rates.
UCPO improves diversity in reinforcement learning models, maintaining high accuracy.
problem RLVR objectives often lead to diversity collapse, reducing coverage of correct solutions.
method UCPO adds a conditional uniformity penalty to GRPO, redistributing probability mass.
result UCPO improves Pass@K and diversity while maintaining competitive Pass@1 accuracy.
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 …
Paper shows no finite time singularities for smooth conformal heat flow of harmonic maps.
problem Smoothness of conformal heat flow of harmonic maps.
method Combines harmonic map flow with metric evolution in conformal direction.
result No finite time singularity occurs for the flow, and under certain conditions, maps converge to a point.
We consider unreliable distributed learning systems wherein the training data is kept confidential by external workers, and the learner has to interact closely with those workers to train a model. In particular, we assume that there exists a system adversary that can adaptively compromise some workers; the compromised …
Hypergraph partitioning lies at the heart of a number of problems in machine learning and network sciences. Many algorithms for hypergraph partitioning have been proposed that extend standard approaches for graph partitioning to the case of hypergraphs. However, theoretical aspects of such methods have seldom received …
Uniform scaling limits in AdamW-trained transformers converge to ODEs.
problem Understanding the dynamics of large-depth transformers trained with AdamW.
method Modeling transformer dynamics as an interacting particle system coupled through attention, proving convergence to ODEs.
result The joint dynamics of hidden states and backpropagated variables converge uniformly to an ODE system.
Adaptive PCR improves panel data analysis with uniform guarantees.
problem Adaptive data collection in panel data settings.
method Adapting PCR to online settings using martingale concentration.
result Time-uniform guarantees for adaptive PCR in panel data.
Unified framework for uniform signal recovery in nonlinear GCS with 1-bit/quantized measurements.
problem Uniform recovery guarantees for nonlinear generative compressed sensing.
method Unified framework using generalized Lasso and Lipschitz approximation.
result Uniform recovery of all signals in the ball up to an error of ε using approximately O(k/ε^2) samples.
Study improves fractional posterior for 1-bit matrix completion.
problem Estimating a binary matrix from observed entries.
method Fractional posterior approach with low-rank factorization and spectral scaled Student priors.
result Concentration results for fractional posterior, demonstrating effectiveness in matrix recovery.
Paper tackles unknown variances in best-arm identification.
problem Identifying the best arm with unknown variances in Gaussian distributions.
method Two approaches: empirical variance plugging or adapting transportation costs.
result The impact of unknown variances is small on sample complexity.
For stationary harmonic maps between Riemannian manifolds, we provide a necessary and sufficient condition for the uniform interior and boundary gradient estimates in terms of the total energy of maps. We also show that if analytic target manifolds do not carry any harmonic S^2, then the singular sets of stationary map…
New method estimates Schrödinger bridge potentials via empirical risk minimization.
problem Estimating Schrödinger bridge potentials from samples.
method Rewriting Schrödinger system as a fixed-point equation and estimating the potential via empirical risk minimization.
result Uniform concentration of empirical risk around population counterpart under sub-Gaussian assumptions.
New inequalities for unbounded functions improve denoising score matching.
problem Statistical error bounds for denoising score matching with unbounded objective functions.
method Derive new concentration inequalities using McDiarmid's inequality and Rademacher complexity bounds.
result Improved statistical error bounds for denoising score matching.
The paper develops bounds for predictive values in binary classification.
problem Lack of confidence intervals for positive and negative predictive values.
method Bi-criterion framework and distribution-free large deviation and uniform convergence bounds.
result New bounds for predictive values without relying on concentration inequalities.
Paper quantizes heavy-tailed data for near optimal estimation rates.
problem Estimating parameters from heavy-tailed data with quantization.
method Truncate and dither data, then uniformly quantize; achieves near minimax rates.
result Near optimal estimation rates achievable with quantized data.