arXiv research

The study identifies conditions for algorithms to have tight generalization bounds.

Jiang et al. (2020) found no uniformly tight generalization bounds for neural networks in the overparameterized setting.

New bound matches exact generalization error for quadratic Gaussian problem.

Classifies tight contact structures on specific Seifert fibered manifolds.

There has been renewed recent interest in developing effective lower bounds for Dynamic Time Warping (DTW) distance between time series. These have many applications in time series indexing, clustering, forecasting, regression and classification. One of the key time series classification algorithms, the nearest neighbo…

Tight geodesics were introduced by Masur-Minsky in [17]. They and their hierarchies have been a powerful tool in the study of the curve complex, mapping class groups, Teichmüller spaces, and hyperbolic 3-manifolds. In the same paper, they showed that there are at least one and at most finitely many tight geodesics betw…

We introduce the notion of tight homomorphism into a locally compact group with nonvanishing bounded cohomology and study these homomorphisms in detail when the target is a Lie group of Hermitian type. Tight homomorphisms between Lie groups of Hermitian type give rise to tight totally geodesic maps of Hermitian symmetr…

Classifies real tight contact structures on lens spaces and solid tori.

We give the proof of a tight lower bound on the probability that a binomial random variable exceeds its expected value. The inequality plays an important role in a variety of contexts, including the analysis of relative deviation bounds in learning theory and generalization bounds for unbounded loss functions.

In this article we give a sharp upper bound on the possible values of the Euler characteristic for a minimal symplectic filling of a tight contact structure on a lens space. This estimate is obtained by looking at the topology of the spaces involved, extending this way what we already knew from the universally tight ca…

We give an algorithm to compute the stable lengths of pseudo-Anosovs on the curve graph, answering a question of Bowditch. We also give a procedure to compute all invariant tight geodesic axes of pseudo-Anosovs. Along the way we show that there are constants $1<a_1<a_2$ such that the minimal upper bound on `slices' of …

A new contrastive MI estimator improves efficiency and tightness.

Quantifies tightness in 3D contact manifolds using sub-Riemannian metrics.

We consider a problem of risk estimation for large-margin multi-class classifiers. We propose a novel risk bound for the multi-class classification problem. The bound involves the marginal distribution of the classifier and the Rademacher complexity of the hypothesis class. We prove that our bound is tight in the numbe…

In \cite{confol} Y. Eliashberg and W. Thurston gave a definition of tight confoliations. We give an example of a tight confoliation $ξ$ on $T^3$ violating the Thurston-Bennequin inequalities. This answers a question from \cite{confol} negatively. Although the tightness of a confoliation does not imply the Thurston-Benn…

In this short note we consider a dynamic assortment planning problem under the capacitated multinomial logit (MNL) bandit model. We prove a tight lower bound on the accumulated regret that matches existing regret upper bounds for all parameters (time horizon $T$, number of items $N$ and maximum assortment capacity $K$)…

Upper bounds for Legendrian links in tight contact 3-manifolds.

We introduce the $k$-stellated spheres and compare and contrast them with $k$-stacked spheres. It is shown that for $d \geq 2k$, any $k$-stellated sphere of dimension $d$ bounds a unique and canonically defined $k$-stacked ball. In parallel, any $k$-stacked polytopal sphere of dimension $d\geq 2k$ bounds a unique and c…

The paper provides tight bounds for improving multi-armed bandits problem.

We give a general lower bound for the normal Gromov norm of genuine laminations in terms of the topology of the complementary regions. In the special case of 3-manifolds, this yields a generalization of Agol's inequality from incompressible surfaces to tight laminations. In particular, the inequality excludes the exist…

Investigates tight PAC-Bayes bounds for small datasets.

The study tightens bounds on binomial probabilities and minimums using KL-divergence.

We give explicit bounds on the intersection number between any curve on a tight multigeodesic and the two ending curves. We use this to construct all tight multigeodesics and so conclude that distances in the curve graph are computable. The algorithm applies to all surfaces. We recover the finiteness result of Masur-Mi…

Study on maximizing submodular functions with limited updates, achieving tight bounds and poly-time algorithms.

Paper improves stability analysis of SGD for various loss functions and data distributions.

Unified complexity bound for sampling logconcave distributions

This paper tackles open problem of tight bounds for KBs with Bernoulli rewards.

Improved bounds on combining hypothesis classes for binary functions.

New regularizers tighten convex relaxation bounds for neural networks.

A stochastic combinatorial semi-bandit is an online learning problem where at each step a learning agent chooses a subset of ground items subject to constraints, and then observes stochastic weights of these items and receives their sum as a payoff. In this paper, we close the problem of computationally and sample effi…

Optimizes quadratic bandits with tight Hessian-dependent sample complexity bounds.

For $d\geq 2$, Walkup's class $\Kd$ consists of the $d$-dimensional simplicial complexes whose vertex-links are stacked $(d-1)$-spheres. Recently Lutz, Sulanke and Swartz have shown that all $\mathbb{F}$-orientable triangulated $d$-manifolds satisfy the inequality $\binom{f_0-d-1}{2} \geq \binom{d+2}{2}β_1$ for $d\geq …

Let $M$ be a compact orientable Seifered fibered 3-manifold without a boundary, and $α$ an $S^1$-invariant contact form on $M$. In a suitable adapted Riemannian metric to $α$, we provide a bound for the volume $\text{Vol}(M)$ and the curvature, which implies the universal tightness of the contact structure $ξ=\kerα$.

Noiseless IO bounds inferred from demonstrations, matching adversarial settings.

New study on regret lower bounds for multi-agent multi-armed bandit problems.

The paper improves privacy accounting for discrete-valued mechanisms and the subsampled Gaussian mechanism.

We consider here 6-regular plane graphs whose faces have size 1, 2 or 3. In Section 2 a practical enumeration method is given that allowed us to enumerate them up to 53 vertices. Subsequently, in Section 3 we enumerate all possible symmetry groups of the spheres that showed up. In Section 4 we introduce a new Goldberg-…

In this article, we prove a generalization of a theorem of Lisca-Matic to Stein cobordisms and develop a method for distinguishing certain Stein cobordisms using rotation numbers. Using these results along with standard techniques from convex surface theory and classifications of tight contact structures on certain 3-m…

Paper improves privacy bounds for shuffle model using novel numerical techniques.

"No free lunch" results state the impossibility of obtaining meaningful bounds on the error of a learning algorithm without prior assumptions and modelling. Some models are expensive (strong assumptions, such as as subgaussian tails), others are cheap (simply finite variance). As it is well known, the more you pay, the…

Researchers estimate optimal PAC-Bayes bounds using Hamiltonian Monte Carlo.

We introduce the $k$-stellated spheres and consider the class ${\cal W}_k(d)$ of triangulated $d$-manifolds all whose vertex links are $k$-stellated, and its subclass ${\cal W}^{\ast}_k(d)$ consisting of the $(k+1)$-neighbourly members of ${\cal W}_k(d)$. We introduce the mu-vector of any simplicial complex and show th…

Analyzes the complexity of linear hypothesis sets using Rademacher complexity.

We obtain a tight distribution-specific characterization of the sample complexity of large-margin classification with L_2 regularization: We introduce the γ-adapted-dimension, which is a simple function of the spectrum of a distribution's covariance matrix, and show distribution-specific upper and lower bounds on the s…

Paper tightens lower bounds on decentralized training complexity.

The curve graphs are not locally finite. In this paper, we show that the curve graphs satisfy a property which is equivalent to graphs being uniformly locally finite via Masur--Minsky's subsurface projections. As a direct application of this study, we show that there exist computable bounds for Bowditch's slices on tig…

Paper develops bounds for stochastic approximation with averaging.

Linear contextual bandit is an important class of sequential decision making problems with a wide range of applications to recommender systems, online advertising, healthcare, and many other machine learning related tasks. While there is a lot of prior research, tight regret bounds of linear contextual bandit with infi…