Matching Theorems and Empirical Discrepancy Computations using Majorizing Measures

DOI10.2307/2152764zbMath0810.60036OpenAlexW4255131115MaRDI QIDQ4292711

Michel Talagrand

Publication date: 4 April 1995

Full work available at URL: https://doi.org/10.2307/2152764

zbMATH Keywords

majorizing measuresmatching theoremsexistence of a matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Sample path properties (60G17) Random measures (60G57) Convergence of probability measures (60B10) Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55)

Related Items

Constructions of majorizing measures, Bernoulli processes and cotype, Asymptotics for transportation cost in high dimensions, Random complex zeroes. II. Perturbed lattice, Ollivier curvature of random geometric graphs converges to Ricci curvature of their Riemannian manifolds, Dilation bootstrap, Asymptotic analysis of the optimal cost in some transportation problems with random locations, Gravitational allocation for uniform points on the sphere, On the Wasserstein distance between classical sequences and the Lebesgue measure, Gravitational allocation to Poisson points, Bayesian incentive compatibility via matchings, On optimal matching of Gaussian samples, A simple Fourier analytic proof of the AKT optimal matching theorem, Transport inequalities on Euclidean spaces for non-Euclidean metrics, Matchings and the variance of Lipschitz functions, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Regularity of Gaussian processes
• Some limit theorems for empirical processes (with discussion)
• Minimax grid matching and empirical measures
• Sample boundedness of stochastic processes under increment conditions
• On optimal matchings
• Entropy numbers of diagonal operators between symmetric Banach spaces
• Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
• The sizes of compact subsets of Hilbert space and continuity of Gaussian processes
• An Isoperimetric Theorem on the Cube and the Kintchine-Kahane Inequalities
• Exact Bounds for the Stochastic Upward Matching Problem
• The isoperimetric inequality
• Probability Inequalities for Sums of Bounded Random Variables
• Some Continuity Properties of Brownian Motion with the Time Parameter in Hilbert Space
• Harmonic Analysis of Local Times and Sample Functions of Gaussian Processes
• A Simple Proof of the $O( \sqrt{n} \log^{3 / 4} n )$ Upright Matching Bound