New rates for GLD and SGLD in infinite-dimensional spaces without dimensionality issues.
problem Gradient Langevin dynamics and SGLD convergence rates in high-dimensional spaces.
method Analysis of GLD and SGLD in infinite-dimensional Hilbert spaces, using stochastic differential equations and Markov chains.
result Derivation of dimension-free convergence rates for GLD and SGLD.
This work analyzes Gibbs samplers for Bayesian hierarchical models without dimensionality constraints.
problem Analyzing convergence properties of Gibbs samplers for Bayesian hierarchical models.
method Using Bayesian asymptotics and total variation mixing times, the study provides dimension-free convergence results.
result Dimension-free convergence results for Gibbs samplers targeting hierarchical models under random data-generating assumptions.
New method proves dimension-free convergence for ULD in KL divergence.
problem Polynomial scaling of existing convergence guarantees in high dimensions.
method Refined KL local error framework, focusing on tr(H) instead of d.
result First dimension-free KL divergence bounds for discretized ULD.
Unified framework for convergence of discrete diffusion models without state space size dependence.
problem Fundamental limitations in existing convergence theory for discrete diffusion models, especially under singular priors and large vocabularies.
method Unified adjoint-equation-based framework that establishes dimension-free convergence guarantees in any integral probability metric (IPM).
result First dimension-free convergence bounds applicable to both masked and uniform priors, free of state space size S S S . The study assesses ML model robustness under worst-case subpopulations.
problem ML model performance degradation under non-training population.
method Two-stage estimation procedure for evaluating worst-case robustness over subpopulations.
result The method certifies model robustness and prevents unreliable deployments.
This paper analyzes neural network classifiers' performance in binary classification.
problem Performance of neural network classifiers in binary classification problems.
method Plug-in classifiers based on neural networks, considering a more general function class and surrogate loss.
result Dimension-free, uniform rate of convergence for the excess risk of neural networks, showing minimax optimality.
New algorithm reduces complexity in multi-agent reinforcement learning.
problem High computational complexity in exact computations for multi-agent reinforcement learning.
method Design of a scalable algorithm based on Natural Policy Gradient, using local information and limited communication.
result Converges to globally optimal policy with dimension-free complexity and localization error.
In this paper, we propose a new adaptive stochastic gradient Langevin dynamics (ASGLD) algorithmic framework and its two specialized versions, namely adaptive stochastic gradient (ASG) and adaptive gradient Langevin dynamics(AGLD), for non-convex optimization problems. All proposed algorithms can escape from saddle poi…
We consider minimizing a nonconvex, smooth function f f f on a Riemannian manifold M \mathcal{M} M . We show that a perturbed version of Riemannian gradient descent algorithm converges to a second-order stationary point (and hence is able to escape saddle points on the manifold). The rate of convergence depends as 1 / ε 2 1/ε^2 1/ ε 2 o…
New method bounds high-dimensional regression without estimating design covariance.
problem High-dimensional linear regression with random design.
method Error-in-operator approach that incorporates design covariance into empirical risk minimization.
result Dimension-free bounds on excess prediction risk derived.
New sampling and diffusion models methods introduced without density function assumptions.
problem Sampling and diffusion models without regularity assumptions.
method Inspired by reverse diffusion process, novel sampling and diffusion algorithms.
result Explicit convergence rate and dimension-free particle approximation convergence result.
This paper shows that a perturbed form of gradient descent converges to a second-order stationary point in a number iterations which depends only poly-logarithmically on dimension (i.e., it is almost "dimension-free"). The convergence rate of this procedure matches the well-known convergence rate of gradient descent to…
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.
We break dimension dependence in sparse distribution estimation with communication constraints.
problem Estimating sparse distributions with limited communication.
method Novel localization schemes and tree-based estimation.
result Achieve dimension-free convergence rate independent of dimension d d d . 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.
MT-HAL learns features and task associations for multiple tasks with a shared sparse structure.
problem Learning features and task associations for multiple tasks with shared structure.
method Fully nonparametric approach that learns features, samples, and task associations with a shared sparse structure.
result MT-HAL achieves a powerful convergence rate and outperforms other methods across various simulation settings.
Study on Metropolis-within-Gibbs schemes for high-dimensional Bayesian models.
problem Improving the scalability of MCMC methods for complex Bayesian models.
method Relating convergence properties to conditional conductance for non-conjugate hierarchical models.
result Established dimension-free convergence results for Metropolis-within-Gibbs schemes.
On a closed weighted Riemannian manifold with nonnegative Bakry-Émery Ricci curvature, it is shown that the ratio of the k k k -th to first eigenvalues of the weighted Laplacian is dominated by 641 k 2 641k^2 641 k 2 , using an argument via the Cheeger constant. While improving the previous exponential upper bound, the order of k k k here…
By using an explicit Bellman function, we prove a bilinear embedding theorem for the Laplacian associated with a weighted Riemannian manifold ( M , μ φ ) (M,μ_φ) ( M , μ φ ) having the Bakry-Emery curvature bounded from below. The embedding, acting on the cartesian product of L p ( M , μ φ ) L^p(M,μ_φ) L p ( M , μ φ ) and L q ( T ∗ M , μ φ ) L^q(T^*M,μ_φ) L q ( T ∗ M , μ φ ) , 1 / p + 1 / q = 1 1/p+1/q=1 1/ p + 1/ q = 1 , involves estimates…
HAR regression improves performance on small datasets.
problem Small datasets with complex functions.
method Data-adaptive kernel ridge regression using tensor-product spline basis.
result Achieves n − 1 / 3 n^{-1/3} n − 1/3 convergence rate for right-continuous functions. We investigate 1) the rate at which refined properties of the empirical risk---in particular, gradients---converge to their population counterparts in standard non-convex learning tasks, and 2) the consequences of this convergence for optimization. Our analysis follows the tradition of norm-based capacity control. We p…
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 paper improves the probability flow ODE sampler for faster sampling of natural images.
problem Improving the convergence rate of the probability flow ODE sampler.
method Adapting the probability flow ODE sampler to exploit intrinsic low-dimensional structures in natural image data.
result Achieves a dimension-free convergence rate of O ( k / T ) O(k/T) O ( k / T ) in total variation distance, improving upon existing results. Novel approach to OT using kernel mean embeddings controls overfitting and achieves dimension-free sample complexity.
problem Consistently estimate optimal transport plan from samples.
method Pose OT as learning kernel mean embedding, employ MMD regularization.
result ε-optimal recovery of transport plan and map with dimension-free sample complexity.
Belief propagation is a fundamental message-passing algorithm for probabilistic reasoning and inference in graphical models. While it is known to be exact on trees, in most applications belief propagation is run on graphs with cycles. Understanding the behavior of "loopy" belief propagation has been a major challenge f…
Performing exact Bayesian inference for complex models is computationally intractable. Markov chain Monte Carlo (MCMC) algorithms can provide reliable approximations of the posterior distribution but are expensive for large datasets and high-dimensional models. A standard approach to mitigate this complexity consists i…
GPMD solves regularized RL with linear convergence, promoting structural policies.
problem Regularized reinforcement learning to encourage exploration and structural policies.
method Policy mirror descent with generalized convex regularizers and Bregman divergence.
result GPMD converges linearly to the global solution over a wide range of learning rates.
A new method for faster optimization in high dimensions.
problem Slow convergence in high-dimensional optimization problems.
method Subspace cubic regularized Newton method within Krylov subspace.
result Achieves a dimension-independent convergence rate of O(1/mk + 1/k^2).
This work studies the implicit bias of mini-batch SGD in classification.
problem Understanding the implicit bias of mini-batch SGD in multi-class classification.
method Characterizes how batch size, momentum, and variance reduction affect convergence and max-margin behavior under different norms.
result Momentum enables small-batch convergence to an approximate max-margin solution, while variance reduction recovers the exact full-batch bias.
This work improves scalability of Wasserstein distances in high dimensions.
problem Scalability issues in computing Wasserstein distances in high dimensions.
method Empirical convergence rates, robustness to data contamination, and computational methods.
result Established fast rates and robust estimation risks for sliced Wasserstein distances.
New metrics avoid high-dimensional analysis challenges, proving convergence without 'curse of dimensionality'.
problem High-dimensional analysis challenges in empirical measure convergence.
method Proposed a new class of probability metrics free of the curse of dimensionality.
result Convergence of empirical measures is free of the curse of dimensionality.
In this paper, the author discusses the elliptic type gradient estimate for the solution of the time-dependent Schrödinger equations on noncompact manifolds. As its application, the dimension-free Harnack inequality and the Liouville type theorem for the Schrödinger equation are proved.
Sharp inequality in spaces with non-negative Ricci curvature.
problem Proving a sharp isoperimetric inequality in metric measure spaces.
method Using volume entropy in non-compact metric measure spaces with non-negative synthetic Ricci curvature.
result Proved a sharp dimension-free isoperimetric inequality.
Graphs with nonnegative Bakry-Émery curvature have volume doubling and Poincaré inequalities.
problem Proving properties of graphs with specific curvature conditions.
method Graph-theoretic modified nonlinear heat-flow method, including point-mass consequences and diffusive exit-time control.
result Volume doubling and Poincaré inequalities for graphs with nonnegative Bakry-Émery curvature.
Algorithm achieves optimal pricing with minimal exploration for dynamic markets.
problem Optimal pricing in dynamic markets with contextual information.
method Localized exploration-then-commit (LetC) algorithm with pure exploration, refinement, and exploitation stages.
result Achieves minimax optimal, dimension-free regret bound.
New method avoids spurious critical points for low-rank matrix recovery.
problem Low-rank matrix recovery problems on Riemannian manifold.
method Riemannian gradient descent with random initialization.
result Riemannian gradient descent avoids spurious critical points and converges nearly linearly.
Unified bounds for iterative algorithms with Gaussian data matrices.
problem Establishing non-asymptotic bounds for iterative algorithms with Gaussian data.
method Explicit coupling between iterates and Gaussian process with deterministic covariance.
result Tight, dimension-free bounds for generalized first-order methods.
New bounds for high-dimensional sparse linear bandits, balancing information and regret.
problem Stochastic linear bandits with high-dimensional sparse features.
method Derivation of minimax regret lower and upper bounds for explore-then-commit algorithm.
result Optimal rate of Θ ( n 2 / 3 ) Θ(n^{2/3}) Θ ( n 2/3 ) for data-poor regime, complemented by O ( n ) O(\sqrt{n}) O ( n ) under signal magnitude assumption. Paper proposes fast, robust methods for low-rank matrix recovery.
problem Estimating low-rank matrices from incomplete or corrupted data.
method Scaled subgradient methods for nonsmooth, nonconvex formulations.
result Methods converge almost dimension-free and condition-number independent.
The paper derives Harnack inequalities for evolving Riemannian manifolds without dimensionality restrictions.
problem Deriving Harnack inequalities for geometric flows with evolving metrics.
method Probabilistic representation of conjugate semigroups and supercontractivity.
result Established dimension-free Harnack inequalities for geometric flows.
New algorithms achieve decision calibration without sample complexity dependent on feature dimension.
problem Achieving decision calibration for nonlinear loss functions with polynomial sample complexity.
method Developed smooth relaxation of decision calibration, enabling dimension-free algorithms.
result Efficient algorithms post-process predictors to satisfy decision calibration without worsening accuracy.
New error bound for diffusion models without dimensionality constraints.
problem Error estimation in diffusion generative models without dimensionality constraints.
method Derive dimension-free error bound using a smooth test functional.
result Explicit, dimension-free bound on generated vs true data distributions.
The paper provides generalization bounds for metric learning using neural network embeddings.
problem Generalization guarantees for metric learning with neural network embeddings.
method Uniform generalization bounds for two regimes: sparse and bounded amplification.
result Dimension-free generalization bounds can be achieved even without sparsity in solutions.
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. 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.
In this paper, we prove the Li-Yau type Harnack inequality and Hamilton type dimension free Harnack inequality for the heat equation ∂ t u = L u \partial_t u=Lu ∂ t u = Lu associated with the time dependent Witten Laplacian on complete Riemannian manifolds equipped with a variant of the ( K , m ) (K, m) ( K , m ) -super Perelman Ricci flows and the K K K -super…
The goal of the paper is to sharpen and generalise bounds involving the Cheeger's isoperimetric constant h h h and the first eigenvalue λ 1 λ_{1} λ 1 of the Laplacian. A celebrated lower bound of λ 1 λ_{1} λ 1 in terms of h h h , λ 1 ≥ h 2 / 4 λ_{1}\geq h^{2}/4 λ 1 ≥ h 2 /4 , was proved by Cheeger in 1970 for smooth Riemannian manifolds. An upper bound on $λ_{1…
A new kernel-based nonconformity score improves multivariate prediction regions.
problem Tackling the challenge of compressing multivariate residual vectors into scalars while preserving geometric structure.
method Introducing a Multivariate Kernel Score (MKS) that decomposes into an anisotropic MMD, providing finite-sample coverage guarantees and convergence rates.
result The MKS produces prediction regions that explicitly adapt to geometric structure, reducing volume compared to ellipsoidal baselines.