arXiv research

New insights into natural exponential families improve regret bounds for bandit problems.

Improved risk-sensitive RL with exponential Bellman equation and better regret bounds.

New bounds for score matching in polynomial exponential families.

We prove that the number of combinatorially distinct causal 3-dimensional triangulations homeomorphic to the 3-dimensional sphere is bounded by an exponential function of the number of tetrahedra. It is also proven that the number of combinatorially distinct causal 4-dimensional triangulations homeomorphic to the 4-sph…

The paper proves exponential mixing for hyperbolic manifolds, with applications to geodesic holonomy.

Researchers prove constant solutions for a specific Finslerian equation.

Study on U-statistics with heavy-tailed samples, providing tail bounds and LDP.

We give bounds on the number of non-simple closed curves on a negatively curved surface, given upper bounds on both length and self-intersection number. In particular, it was previously known that the number of all closed curves of length at most $L$ grows exponentially in $L$. We get exponentially tighter bounds given…

Improved sample complexity for identifying best policies in risk-sensitive reinforcement learning.

Paper establishes universal lower bounds and optimal rates for clustering sub-exponential mixture models.

Optimization rates improved for manifolds with bounded geometry.

New hyperbolic manifolds show exponential homology torsion growth.

Study shows exponential error reduction in multiclass classification without bias-variance trade-off.

Minimal graphs over simply connected domains grow at most exponentially.

We prove a general connection between the communication complexity of two-player games and the sample complexity of their multi-player locally private analogues. We use this connection to prove sample complexity lower bounds for locally differentially private protocols as straightforward corollaries of results from com…

New aggregation strategy handles unbounded losses with regret bounds.

Unified diffusive bounds for non-linear parabolic equations.

SMRL uses score matching for efficient RL with exponential family models.

Paper analyzes sparse aggregation in GLMs with Kullback-Leibler risk bounds.

Calabi flow works well with bounded curvature on compact manifolds.

In three-dimensional computational topology, the theory of normal surfaces is a tool of great theoretical and practical significance. Although this theory typically leads to exponential time algorithms, very little is known about how these algorithms perform in "typical" scenarios, or how far the best known theoretical…

Study shows exponential gap in sample complexity between noisy and non-noisy recurrent neural networks.

The paper studies scaling limits of hedging prices in financial models.

Motivated by the pricing of lookback options in exponential Lévy models, we study the difference between the continuous and discrete supremum of Lévy processes. In particular, we extend the results of Broadie et al. (1999) to jump-diffusion models. We also derive bounds for general exponential Lévy models.

Unified framework for understanding TVO and improving model learning.

Paper improves generalization bounds for noisy stochastic algorithms.

New Thompson sampling algorithm reduces regret for exponential family bandits.

Stochastic approximation algorithms show exponential progress bounds.

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…

Unified complexity bound for sampling logconcave distributions

TensorPlan shows an exponential lower bound for planning in MDPs with linearly realizable value functions.

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 …

Let Mod(S) denote the mapping class group of a compact, orientable surface S. We prove that finitely generated subgroups of Mod(S) which are not virtually abelian have uniform exponential growth with minimal growth rate bounded below by a constant depending only, and necessarily, on S. For the proof, we find in any suc…

A new machine learning model uses matrix exponentials for universal approximation.

We consider on-line density estimation with a parameterized density from the exponential family. The on-line algorithm receives one example at a time and maintains a parameter that is essentially an average of the past examples. After receiving an example the algorithm incurs a loss which is the negative log-likelihood…

We provide a lower bound for the uniform exponential growth rate of closed nonflat nonpositively curved 3-manifold groups. A detailed study of the uniform exponential growth rate of closed 3-manifold groups is also presented.

The study provides error bounds for the generalized Lasso with sub-exponential data.

New study shows exponential lower bound for RL even with constant suboptimality gap.

New bounds on learning algorithm generalization error derived using information density.

Extends online learning to metric spaces using exponential weights.

First order methods can take extremely long to find global minima of non-convex functions.

We prove existence and uniqueness of optimal maps on $RCD^*(K,N)$ spaces under the assumption that the starting measure is absolutely continuous. We also discuss how this result naturally leads to the notion of exponentiation.

New clustering method for exponential family data.

New algorithms achieve high-probability parameter-free regret in online convex optimization with heavy-tailed data.

New stability bounds for Sinkhorn's algorithm in entropic optimal transport.

For n > 2, the Dehn functions of Aut(F_n) and Out(F_n) are exponential. Hatcher and Vogtmann proved that they are at most exponential, and the complementary lower bound in the case n=3 was established by Bridson and Vogtmann. Handel and Mosher completed the proof by reducing the lower bound for n>4 to the case n=3. In …

We prove a new lower bound for the dilatation of an arbitrary pseudo-Anosov map on a surface of genus g with n punctures. Our bound improves the former super-exponential dependence on the genus by a polynomial dependence.

Optimal learning for parametric prophet inequalities with exponential-type distributions