We derive various inequalities involving the intersection number of the curves contained in geodesics and tight geodesics in the curve graph. While there already exist such inequalities on tight geodesics, our method applies in the setting of geodesics. Furthermore, the method gives inequalities with a uniform constant…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “uniform tightness”
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…
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.
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…
Growth Tight Actionsmath.GR
We introduce and systematically study the concept of a growth tight action. This generalizes growth tightness for word metrics as initiated by Grigorchuk and de la Harpe. Given a finitely generated, non-elementary group acting on a --space , we prove that if contains a strongly contracting eleme…
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.
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…
New bounds for learning polynomial surrogates with guarantees.
problem Learning polynomial surrogates for bounded binary functions with error guarantees.
method Characterized minimax sample complexity for two classes of polynomials under subgaussian noise.
result Sample complexity rates differ from noiseless case, scaling as for degree polynomials and for sparse polynomials.
Jiang et al. (2020) found no uniformly tight generalization bounds for neural networks in the overparameterized setting.
problem Finding uniformly tight generalization bounds for neural networks in the overparameterized setting.
method Examined more than a dozen generalization bounds, proving that no bounds can be uniformly tight in the overparameterized setting.
result No generalization bounds can be uniformly tight in the overparameterized setting.
We study distribution testing with communication and memory constraints in the following computational models: (1) The {\em one-pass streaming model} where the goal is to minimize the sample complexity of the protocol subject to a memory constraint, and (2) A {\em distributed model} where the data samples reside at mul…
Paper establishes tight lower bounds for minimizing certain smooth and convex functions.
problem Minimizing high-order Hölder smooth and uniformly convex functions.
method Analyzes two asymmetric cases of and using worst-case oracle complexities.
result Establishes worst-case oracle complexities for reaching an ε-approximate solution.
New algorithms achieve uniform-PAC guarantees for RL with bounded eluder dimension.
problem Achieving strong performance guarantees in reinforcement learning.
method Proposes algorithms for nonlinear bandits and model-based episodic RL with a bounded eluder dimension.
result Achieves uniform-PAC sample complexity that matches state-of-the-art regret bounds or sample complexity guarantees.
The paper improves the empirical bootstrap method for non-normal estimators.
problem Theoretical properties of empirical bootstrap for non-asymptotically normal estimators.
method Establishing limiting distribution, deriving consistency conditions, proposing alternative methods.
result The empirical bootstrap method can be asymptotically consistent under stability conditions.
We design and mathematically analyze sampling-based algorithms for regularized loss minimization problems that are implementable in popular computational models for large data, in which the access to the data is restricted in some way. Our main result is that if the regularizer's effect does not become negligible as th…
Study flute surfaces and Loch Ness monster, proving their parabolicity and uniformization.
problem Characterizing parabolicity and uniformization of flute surfaces and the Loch Ness monster.
method Associate sequences to Fuchsian groups and analyze their properties.
result Zero-twist flute surfaces are parabolic if and only if the series diverges.
We introduce the -stellated spheres and consider the class of triangulated -manifolds all whose vertex links are -stellated, and its subclass consisting of the -neighbourly members of . We introduce the mu-vector of any simplicial complex and show th…
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, …
New algorithm reduces unfairness in bandit problems by balancing exploration and exploitation.
problem Fairness in bandit problems where early participants can be unfairly disadvantaged.
method Introduces extsf{UCB-HARE} algorithm that balances exploration and exploitation using inverse-weighted harmonic rank schedule.
result Algorithm extsf{UCB-HARE} achieves regret matching the lower bound for .
Interpolating label noise makes models vulnerable to adversarial attacks.
problem Adversarial vulnerability of models trained on noisy labels.
method Theoretical analysis of label noise and adversarial risk relationship.
result Uniform label noise induces adversarial risk similar to worst-case poisoning.
A new loss function HUG decouples and generalizes neural collapse.
problem Neural collapse limits in deep learning models.
method Hyperspherical uniformity gap (HUG) as a unified framework.
result HUG decouples and generalizes neural collapse, improving model flexibility and robustness.
On stellated spheres, shellable balls, lower bounds and a combinatorial criterion for tightnessmath.GT
We introduce the -stellated spheres and compare and contrast them with -stacked spheres. It is shown that for , any -stellated sphere of dimension bounds a unique and canonically defined -stacked ball. In parallel, any -stacked polytopal sphere of dimension bounds a unique and c…
The paper relaxes the stability condition to boost confidence in generalization for randomized learning algorithms.
problem The tension between uniform stability and -stability in generalization bounds.
method Establishes in-expectation first moment generalization error bounds for -stable randomized learning algorithms and uses subbagging to achieve near-tight exponential bounds.
result Improves generalization bounds for convex and non-convex optimization problems with SGD.
Algorithm recovers function samples from noisy modulo samples with high probability.
problem Recovering function samples from noisy modulo samples.
method Two-stage algorithm involving k-NN regression and SDP relaxation.
result Uniform error rate of for function samples.
Improved single-pass streaming MAB regret bound to O(K^1/3T^2/3).
problem Minimize regret in single-pass streaming multi-armed bandits with sublinear memory.
method Improved regret lower bound to Ω(K^1/3T^2/3) and upper bound to O(K^1/3T^2/3).
result Achieved tight regret bound of O(K^1/3T^2/3) for algorithms with o(K) memory.
New bounds for agnostic learning with average smoothness.
problem Distribution-free nonparametric regression with average smoothness.
method Distribution-free uniform convergence bounds and agnostic learning algorithm.
result Distribution-free uniform convergence bounds for average-smoothness classes in the agnostic setting.
We establish a tight characterization of the worst-case rates for the excess risk of agnostic learning with sample compression schemes and for uniform convergence for agnostic sample compression schemes. In particular, we find that the optimal rates of convergence for size- agnostic sample compression schemes are of…
We consider variants of trust-region and cubic regularization methods for non-convex optimization, in which the Hessian matrix is approximated. Under mild conditions on the inexact Hessian, and using approximate solution of the corresponding sub-problems, we provide iteration complexity to achieve -approximate seco…
New bounds for kernel regression under non-Gaussian noise.
problem Uncertainty quantification for function estimates from noisy observations.
method Novel non-asymptotic probabilistic uniform error bounds for kernel-based regression.
result Proposed bounds apply to a broad class of non-Gaussian noise distributions.
We present a method for proving upper bounds on the eigenvalues of the graph Laplacian. A main step involves choosing an appropriate "Riemannian" metric to uniformize the geometry of the graph. In many interesting cases, the existence of such a metric is shown by examining the combinatorics of special types of flows. T…
Study on neural networks' sample complexity with one hidden layer.
problem Understanding how sample complexity is affected by network architecture and norm constraints.
method Norm-based uniform convergence bounds for scalar-valued one-hidden-layer networks, focusing on spectral and Frobenius norms.
result Spectral norm control is insufficient for uniform convergence guarantees, but Frobenius norm control is sufficient, with conditions.
New insights into variational inference using Monte Carlo estimates.
problem Improving variational bounds in latent variable models.
method Analyzing properties of Monte Carlo estimates and their impact on variational gaps.
result Negative correlation reduces variational gaps, contrary to intuition.
Leveraging algorithmic stability to derive sharp generalization bounds is a classic and powerful approach in learning theory. Since Vapnik and Chervonenkis [1974] first formalized the idea for analyzing SVMs, it has been utilized to study many fundamental learning algorithms (e.g., -nearest neighbors [Rogers and Wag…
We show that \emph{No unbounded profit with bounded risk} (NUPBR) implies \emph{predictable uniform tightness} (P-UT), a boundedness property in the Emery topology which has been introduced by C. Stricker \cite{S:85}. Combining this insight with well known results from J. Mémin and L. Słominski \cite{MS:91} leads to a …
Uniform stability of a learning algorithm is a classical notion of algorithmic stability introduced to derive high-probability bounds on the generalization error (Bousquet and Elisseeff, 2002). Specifically, for a loss function with range bounded in , the generalization error of a -uniformly stable learning a…
Tight triangulated manifolds are generalisations of neighborly triangulations of closed surfaces and are interesting objects in Combinatorial Topology. Tight triangulated manifolds are conjectured to be minimal. Except few, all the known tight triangulated manifolds are stacked. It is known that locally stacked tight t…
We propose to study the generalization error of a learned predictor in terms of that of a surrogate (potentially randomized) predictor that is coupled to and designed to trade empirical risk for control of generalization error. In the case where interpolates the data, it is interesting to con…
Sampling without replacement speeds up optimization in minimax problems.
problem Optimizing minimax problems with faster convergence rates.
method Analysis of gradient descent ascent and proximal point method with two sampling strategies.
result Sampling without replacement leads to faster convergence rates in minimax optimization.
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…
Study laws of large numbers in online classification, determining optimal regret bounds.
problem Understanding how sequential sampling affects online learning and classification.
method Characterized online learnable classes and determined optimal regret bounds using Littlestone's dimension.
result Optimal regret bounds in online learning are determined, resolving open questions.
The study identifies conditions for algorithms to have tight generalization bounds.
problem Understanding which algorithms have tight generalization bounds.
method Analyzing conditions that preclude tight generalization bounds and identifying stable algorithms.
result Stable algorithms have tight generalization bounds, while unstable ones do not.
Surgery on knots always admits a tight contact structure.
problem Understanding tight contact structures on knots after surgery.
method Smooth (-r)-surgery on knots, using Heegaard Floer contact invariant.
result Tight contact structures detected for all knots after surgery.
Tight maps was introduced along tight homomorphisms by Burger, Iozzi and Wienhard with aims towards maximal representations. In this paper we classify tight maps into classical Hermitian symmetric spaces and give a partial result for the exceptional spaces.
Improved deep learning model deployment on tiny MCUs with mixed-precision quantization.
problem Memory limitations prevent accurate deployment of DNN models on tiny MCUs.
method Automated mixed-precision quantization using Reinforcement Learning for MCU constraints.
result Mixed-precision models achieve high accuracy with uniform quantization policies.
Golod and tight 3-manifoldsmath.CO
3-manifold triangulations are Golod and tight, proven through a topological characterization.
problem Understanding Golodness and tightness in 3-manifold triangulations.
method Topological characterization of a polyhedral product for a tight-neighborly manifold triangulation.
result Golodness and tightness are equivalent for 3-manifold triangulations.
Simply connected spaces of tight frames identified.
problem Understanding the connectivity of spaces of tight frames.
method Viewing tight frames as elements of Stiefel manifolds and identifying simply connected spaces.
result Spaces of tight frames, including finite unit-norm tight frames, are simply connected.
The study finds many tight contact structures on hyperbolic 3-spheres.
problem Finding tight contact structures on hyperbolic 3-spheres.
method Constructing hyperbolic homology 3-spheres and analyzing their tight contact structures.
result Produces hyperbolic homology 3-spheres with multiple distinct tight contact structures.
Study tight contact structures on specific 3-manifolds.
problem Counting and constructing tight contact structures on plumbed 3-manifolds.
method Algorithm to construct stein diagrams for tight structures without Giroux torsion.
result Explicit algorithm to construct tight contact structures.
Classifies tight contact structures on surgeries of the Whitehead link.
problem Classifying tight contact structures on surgeries of the Whitehead link.
method Analyzes various surgeries on the Whitehead link to classify tight contact structures.
result Determines tight contact structures, Stein fillability, and virtually overtwisted properties.