arXiv research

New method bounds high-dimensional regression without estimating design covariance.

New method proves dimension-free convergence for ULD in KL divergence.

Logistic regression gets a new, simpler uniform bound.

On a closed weighted Riemannian manifold with nonnegative Bakry-Émery Ricci curvature, it is shown that the ratio of the $k$-th to first eigenvalues of the weighted Laplacian is dominated by $641k^2$, using an argument via the Cheeger constant. While improving the previous exponential upper bound, the order of $k$ here…

Unified bounds for iterative algorithms with Gaussian data matrices.

By using an explicit Bellman function, we prove a bilinear embedding theorem for the Laplacian associated with a weighted Riemannian manifold $(M,μ_φ)$ having the Bakry-Emery curvature bounded from below. The embedding, acting on the cartesian product of $L^p(M,μ_φ)$ and $L^q(T^*M,μ_φ)$, $1/p+1/q=1$, involves estimates…

The paper provides generalization bounds for metric learning using neural network embeddings.

New bounds for high-dimensional sparse linear bandits, balancing information and regret.

We improve bounds for stochastic processes, especially those with heavy tails.

The goal of the paper is to sharpen and generalise bounds involving the Cheeger's isoperimetric constant $h$ and the first eigenvalue $λ_{1}$ of the Laplacian. A celebrated lower bound of $λ_{1}$ in terms of $h$, $λ_{1}\geq h^{2}/4$, was proved by Cheeger in 1970 for smooth Riemannian manifolds. An upper bound on $λ_{1…

Unified framework for convergence of discrete diffusion models without state space size dependence.

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

New error bound for diffusion models without dimensionality constraints.

Optimal sampling bounds for various classification losses under different regularization terms.

Graphs with nonnegative Bakry-Émery curvature have volume doubling and Poincaré inequalities.

The goal of predictive sparse coding is to learn a representation of examples as sparse linear combinations of elements from a dictionary, such that a learned hypothesis linear in the new representation performs well on a predictive task. Predictive sparse coding algorithms recently have demonstrated impressive perform…

We study Smoothed Online Convex Optimization, a version of online convex optimization where the learner incurs a penalty for changing her actions between rounds. Given a $Ω(\sqrt{d})$ lower bound on the competitive ratio of any online algorithm, where $d$ is the dimension of the action space, we ask under what conditio…

Paper improves Frank-Wolfe algorithm's efficiency bounds.

We derive exponential tail inequalities for sums of random matrices with no dependence on the explicit matrix dimensions. These are similar to the matrix versions of the Chernoff bound and Bernstein inequality except with the explicit matrix dimensions replaced by a trace quantity that can be small even when the dimens…

Improved diffusion models for generative tasks without dimensionality constraints.

This work analyzes Gibbs samplers for Bayesian hierarchical models without dimensionality constraints.

Study shows high-dimensional sparse RL hardness and Lasso Q-iteration's nearly dimension-free regret.

New algorithms achieve decision calibration without sample complexity dependent on feature dimension.

This paper analyzes neural network classifiers' performance in binary classification.

Algorithm achieves optimal pricing with minimal exploration for dynamic markets.

We study the regret minimization problem in the novel setting of generalized kernelized bandits (GKBs), where we optimize an unknown function $f^*$ belonging to a reproducing kernel Hilbert space (RKHS) having access to samples generated by an exponential family (EF) reward model whose mean is a non-linear function $μ(…

New rates for GLD and SGLD in infinite-dimensional spaces without dimensionality issues.

The paper derives Harnack inequalities for evolving Riemannian manifolds without dimensionality restrictions.

Let $(X,d,μ)$ be a $RCD^\ast(K, N)$ space with $K\in \mathbb{R}$ and $N\in [1,\infty]$. For $N\in [1,\infty)$, we derive the upper and lower bounds of the heat kernel on $(X,d,μ)$ by applying the parabolic Harnack inequality and the comparison principle, and then sharp bounds for its gradient, which are also sharp in t…

We develop time-uniform confidence spheres for estimating means of random vectors.

Paper develops probabilistic bounds for a stochastic gradient algorithm in non-convex problems.

New bounds for neural networks without loss boundedness assumption.

Sharp bounds on uniform generalization errors in binary linear classification.

New bounds for adaptive control in high dimensions without fixed state space.

Novel approach to OT using kernel mean embeddings controls overfitting and achieves dimension-free sample complexity.

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…

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.

New bounds for MCMC on discrete spaces without dimension dependence.

Low-precision streaming PCA estimates the leading eigenvector with limited precision.

Sharp inequality in spaces with non-negative Ricci curvature.

In this paper, we study the conjecture of Gardner and Zvavitch from \cite{GZ}, which suggests that the standard Gaussian measure $γ$ enjoys $\frac{1}{n}$-concavity with respect to the Minkowski addition of \textbf{symmetric} convex sets. We prove this fact up to a factor of 2: that is, we show that for symmetric convex…

New algorithm estimates transport maps with nearly optimal error.

This work develops sampling methods for differential privacy using SHK geometry.

Information concentration of probability measures have important implications in learning theory. Recently, it is discovered that the information content of a log-concave distribution concentrates around their differential entropy, albeit with an unpleasant dependence on the ambient dimension. In this work, we prove th…

In this paper, we consider the challenge of maximizing an unknown function f for which evaluations are noisy and are acquired with high cost. An iterative procedure uses the previous measures to actively select the next estimation of f which is predicted to be the most useful. We focus on the case where the function ca…

The study assesses ML model robustness under worst-case subpopulations.

New algorithm reduces complexity in multi-agent reinforcement learning.

In this paper, we prove the Li-Yau type Harnack inequality and Hamilton type dimension free Harnack inequality for the heat equation $\partial_t u=Lu$ associated with the time dependent Witten Laplacian on complete Riemannian manifolds equipped with a variant of the $(K, m)$-super Perelman Ricci flows and the $K$-super…