Concentration of measure and isoperimetric inequalities in product spaces

From MaRDI portal

Publication:1908323

Jump to:navigation, search

DOI10.1007/BF02699376zbMath0864.60013arXivmath/9406212WikidataQ92174908 ScholiaQ92174908MaRDI QIDQ1908323

Michel Talagrand

Publication date: 3 June 1997

Published in: Publications Mathématiques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/9406212

zbMATH Keywords

concentration function Sherrington-Kirkpatrick model martingale methods concentration of measure phenomenon sums of Banach space-valued independent random variables

Mathematics Subject Classification ID

Gaussian processes (60G15) Inequalities; stochastic orderings (60E15) Geometric probability and stochastic geometry (60D05) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Stochastic processes (60G99) Probabilistic measure theory (60A10) Measures and integrals in product spaces (28A35)

Related Items

About the constants in Talagrand's concentration inequalities for empirical processes., Greedy lattice animals: Negative values and unconstrained maxima, Isoperimetry for Gibbs measures, Fluctuations of the free energy in the REM and the \(p\)-spin SK models, Concentration inequalities, large and moderate deviations for self-normalized empirical processes, On the speed of convergence for two-dimensional first passage Ising percolation., Concentration of measure inequalities for Markov chains and \(\Phi\)-mixing processes., Absence of mutual unbounded growth for almost all parameter values in the two-type Richardson model., On Hoeffding's inequalities., Concentration of norms and eigenvalues of random matrices, Stein's method for concentration inequalities, Nonlinear large deviations, A note on transportation cost inequalities for diffusions with reflections, A note on concentration for polynomials in the Ising model, Fluctuations of transverse increments in two-dimensional first passage percolation, Rigorous verification, validation, uncertainty quantification and certification through concentration-of-measure inequalities, A version of Hörmander's theorem for the fractional Brownian motion, Upper tails via high moments and entropic stability, The Legendre transform of two replicas of the Sherrington-Kirkpatrick spin glass model, A measure concentration inequality for contracting Markov chains, Transportation cost for Gaussian and other product measures, Kantorovich duality for general transport costs and applications, Large deviations of the range of the planar random walk on the scale of the mean, On amenability and groups of measurable maps, Localization in random geometric graphs with too many edges, Weak monotone rearrangement on the line, Concentration for multidimensional diffusions and their boundary local times, The structure of low-complexity Gibbs measures on product spaces, Circular law theorem for random Markov matrices, Correction of AI systems by linear discriminants: probabilistic foundations, Shadows of ordered graphs, Empirical risk minimization is optimal for the convex aggregation problem, Polynomial-time targeted attacks on coin tossing for any number of corruptions, Second order accurate distributed eigenvector computation for extremely large matrices, Properties of the parabolic Anderson model and the Anderson polymer model, Poincaré inequalities and dimension free concentration of measure, Fisher information and logarithmic Sobolev inequality for matrix-valued functions, On the uniform convergence of empirical norms and inner products, with application to causal inference, Concentration inequalities via zero bias couplings, Phase transitions in normalized cut of social networks, Transport inequalities for random point measures, The radial spanning tree of a Poisson point process, Modified log-Sobolev inequality for a compact pure jump Markov process with degenerate jumps, Local tail bounds for functions of independent random variables, Maxima and near-maxima of a Gaussian random assignment field, Quantitative estimates for the flux of TASEP with dilute site disorder, The sub-Gaussian constant and concentration inequalities, Bounded size biased couplings, log concave distributions and concentration of measure for occupancy models, Self-organized segregation on the grid, On Bernstein type inequalities for stochastic integrals of multivariate point processes, Random-weighted Sobolev inequalities on \(\mathbb{R}^d\) and application to Hermite functions, Modular statistics for subgraph counts in sparse random graphs, The matching, birthday and the strong birthday problem: a contemporary review, Linear growth for greedy lattice animals., Limiting shape for directed percolation models, From dimension free concentration to the Poincaré inequality, Moment inequalities for functions of independent random variables, Selector processes on classes of sets, A Bernstein type inequality for sums of selections from three dimensional arrays, On the geometry of metric measure spaces. I, A concentration bound for the longest increasing subsequence of a randomly chosen involution, Modified log-Sobolev inequalities for convex functions on the real line. Sufficient conditions, Second order concentration via logarithmic Sobolev inequalities, Talagrand concentration inequalities for stochastic heat-type equations under uniform distance, Quadratic transportation cost inequality for scalar stochastic conservation laws, PDE/statistical mechanics duality: relation between Guerra's interpolated \(p\)-spin ferromagnets and the Burgers hierarchy, Concentration of the empirical spectral distribution of random matrices with dependent entries, Concentration inequalities for dependent random variables via the martingale method, Random Copolymers, Circular law for random matrices with exchangeable entries, Variations on twins in permutations, On the tightness of Gaussian concentration for convex functions, Kloosterman paths and the shape of exponential sums, Talagrand concentration inequalities for stochastic partial differential equations, The central limit theorem for weighted minimal spanning trees on random points, An introduction to large deviations for random graphs, Phase transition in spectral clustering based on resistance matrix, Applications of weak transport theory, Isoperimetric inequality on a metric measure space and Lipschitz order with an additive error, The planted matching problem: phase transitions and exact results, Modified log-Sobolev inequalities, Beckner inequalities and moment estimates, Delocalization of polymers in lower tail large deviation, Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance, Bounding \(\bar d\)-distance by informational divergence: A method to prove measure concentration, Ergodic theorems for some classical problems in combinatorial optimization, A general method for lower bounds on fluctuations of random variables, Competition interfaces and second class particles, Rumor spreading on random regular graphs and expanders, Existence, duality, and cyclical monotonicity for weak transport costs, On the concentration of eigenvalues of random symmetric matrices, Functional linear regression with Huber loss, Entropic curvature on graphs along Schrödinger bridges at zero temperature, Concentration inequalities on the multislice and for sampling without replacement, Modified logarithmic Sobolev inequalities and transportation inequalities, Detecting positive correlations in a multivariate sample, A Hsu-Robbins-Erdős strong law in first-passage percolation, Estimate of observable diameter of \(l_p\)-product spaces, Stability of martingale optimal transport and weak optimal transport, Limit theory for the Gilbert graph, Functional inequalities for two-level concentration, Concentration Properties of Restricted Measures with Applications to Non-Lipschitz Functions, On mappings on the hypercube with small average stretch, Concentration of non‐Lipschitz functions and applications, The infamous upper tail, On independent sets in random graphs, The missing log in large deviations for triangle counts, Generalization error rates in kernel regression: the crossover from the noiseless to noisy regime*, Random Latin square graphs, Statistical Physics and Network Optimization Problems, Colourful categories, Modified log-Sobolev inequalities and two-level concentration, Anticoncentration and the Exact Gap-Hamming Problem, Submodular Functions: Learnability, Structure, and Optimization, Central limit theorem for fluctuations in the high temperature region of the Sherrington–Kirkpatrick spin glass model, Giant descendant trees, matchings, and independent sets in age-biased attachment graphs, $k$-Variance: A Clustered Notion of Variance, Adaptable and conflict colouring multigraphs with no cycles of length three or four, Outliers in spectrum of sparse Wigner matrices, The list linear arboricity of graphs, Talagrand's transportation inequality for SPDEs with locally monotone drifts, Isoperimetric stability in lattices, Colorings, transversals, and local sparsity, Asymptotically good edge correspondence colourings, Bernoulli random matrices, Concentration inequalities using approximate zero bias couplings with applications to Hoeffding’s statistic under the Ewens distribution, Tyler's and Maronna's M-estimators: non-asymptotic concentration results, Connecting eigenvalue rigidity with polymer geometry: diffusive transversal fluctuations under large deviation, Second-order concentration on the sphere, Concentration inequalities for Poisson point processes with application to adaptive intensity estimation, Spectral analysis of the quantum random energy model, Stochastic evolutionary \(p\)-Laplace equation: large deviation principles and transportation cost inequality, Limit theorems for random sums of random summands, A Mass-Shifting Phenomenon of Truncated Multivariate Normal Priors, Maximal inequalities and some applications, Phase transitions, logarithmic Sobolev inequalities, and uniform-in-time propagation of chaos for weakly interacting diffusions, On dimension-dependent concentration for convex Lipschitz functions in product spaces, A Stronger Bound for the Strong Chromatic Index, Dismantling Sparse Random Graphs, Geodesics, bigeodesics, and coalescence in first passage percolation in general dimension, Uniform fluctuation and wandering bounds in first passage percolation, Edge-colouring graphs with local list sizes, Locally uniform random permutations with large increasing subsequences, On Active and Passive Testing, Minimum Cost Matching in a Random Graph with Random Costs, Unnamed Item, Higher order concentration of measure, Connect the dots: how many random points can a regular curve pass through?, Concentration for noncommutative polynomials in random matrices, CONCENTRATION INEQUALITIES FOR GIBBS MEASURES, Semi-Infinite Paths of the Two-Dimensional Radial Spanning Tree, Unnamed Item, A survey of high dimension low sample size asymptotics, Error estimates and convergence rates for the stochastic homogenization of Hamilton-Jacobi equations, Blessing of dimensionality: mathematical foundations of the statistical physics of data, Confounder Detection in High-Dimensional Linear Models Using First Moments of Spectral Measures, A sharp concentration inequality with applications, Uncertainty quantification via codimension-one partitioning, An asymptotically tight bound on the adaptable chromatic number, Asymptotic Theory of Information-Theoretic Experimental Design, Concentration property on probability spaces., New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help, Some applications of concentration inequalities to statistics, Noise sensitivity of Boolean functions and applications to percolation, Unnamed Item, Self averaging and the space of interactions in neural networks, Merging percolation onZdand classical random graphs: Phase transition, A local epsilon version of Reed's conjecture, Rigorous results for mean field models for spin glasses, The cut metric, random graphs, and branching processes, Theory of Classification: a Survey of Some Recent Advances, Deviation inequality for monotonic Boolean functions with application to the number ofk-cycles in a random graph, PHASE SPACE MEASURE CONCENTRATION FOR AN IDEAL GAS, The Communication Complexity of Distributed epsilon-Approximations, A concentration inequality for interval maps with an indifferent fixed point, Concentration and Moment Inequalities for Polynomials of Independent Random Variables, One-dimensional empirical measures, order statistics, and Kantorovich transport distances, Unnamed Item, Concentration inequalities for functions of independent variables, Free energies of Boltzmann machines: self-averaging, annealed and replica symmetric approximations in the thermodynamic limit, On Talagrand's deviation inequalities for product measures, Positive Temperature Versions of Two Theorems on First-Passage Percolation, Random non-Abelian G-circulant matrices. Spectrum of random convolution operators on large finite groups, Entropy and Concentration, Levels of concentration between exponential and Gaussian, The symmetry in the martingale inequality, Asymptotics for Voronoi tessellations on random samples, Concentration for Poisson \(U\)-statistics: subgraph counts in random geometric graphs, Picker-chooser fixed graph games, Concentration of measure, classification of submeasures, and dynamics of \(L_0\), Boolean functions: influence, threshold and noise, Characterization of a class of weak transport-entropy inequalities on the line, Signal propagation in small-world biological networks with weak noise, On the geometry of similarity search: dimensionality curse and concentration of measure, A direct verification argument for the Hamilton-Jacobi equation continuum limit of nondominated sorting, Isoperimetry in supercritical bond percolation in dimensions three and higher, A stochastic mechanism for signal propagation in the brain: force of rapid random fluctuations in membrane potentials of individual neurons, Rate of convergence in first-passage percolation under low moments, A bound on the strong chromatic index of a graph, A stronger bound for the strong chromatic index (extended abstract), Information inequalities and concentration of measure, Limit theorems for maximum flows on a lattice, Speed of convergence in first passage percolation and geodesicity of the average distance, Threshold for monotone symmetric properties through a logarithmic Sobolev inequality, Measure concentration in optimization, Symmetric Langevin spin glass dynamics, Concentration inequalities and limit theorems for randomized sums, Confidence bounds for a parameter, Central limit theorem for first-passage percolation time across thin cylinders, Constructive bounds for a Ramsey-type problem, Interpolated inequalities between exponential and Gaussian, Orlicz hypercontractivity and isoperimetry, Applications of Stein's method for concentration inequalities, Simulation-based optimization of Markov decision processes: an empirical process theory approach, Upper tails for arithmetic progressions in random subsets, Concentration of Haar measures, with an application to random matrices, Optimal random matchings, tours, and spanning trees in hierarchically separated trees, An approximate vertex-isoperimetric inequality for \(r\)-sets, Random walks on quasirandom graphs, Information gathering in ad-hoc radio networks with tree topology, The mean field traveling salesman and related problems, On concentration for (regularized) empirical risk minimization, The Bennett-Orlicz norm, A concentration inequality for product spaces, A Bernstein-type inequality for suprema of random processes with applications to model selection in non-Gaussian regression, Thermodynamics and concentration, On the complexity of asynchronous agreement against powerful adversaries, Mixing and concentration by Ricci curvature, Connected spatial networks over random points and a route-length statistic, Around the circular law, Rate of convergence of power-weighted Euclidean minimal spanning trees, The adjacent vertex distinguishing total chromatic number, Coalescence of Euclidean geodesics on the Poisson-Delaunay triangulation, Spectrum of non-Hermitian heavy tailed random matrices, On the convex Poincaré inequality and weak transportation inequalities, Concentration of measure and cluster analysis., Randomly colouring graphs (a combinatorial view), Oded Schramm's contributions to noise sensitivity, Measure concentration and the weak Pinsker property, Colouring graphs when the number of colours is almost the maximum degree, Noise sensitivity in continuum percolation, Talagrand's inductive method and isoperimetric inequalities involving random sets, Quenched central limit theorem in a corner growth setting, Concentration inequalities using the entropy method, Concentration of measures supported on the cube, First passage percolation has sublinear distance variance., Symmetrization approach to concentration inequalities for empirical processes., A sharp threshold for a modified bootstrap percolation with recovery, Singular perturbations to semilinear stochastic heat equations, A subgaussian embedding theorem, Modified logarithmic Sobolev inequalities on \(\mathbb{R}\), A central limit theorem for the overlap in the Hopfield model, Complexity measures of sign matrices, Colorings of spaces, and random graphs, Sublinearity of the number of semi-infinite branches for geometric random trees, Random assignment problems, Untangling planar graphs from a specified vertex position-Hard cases, Asymptotically optimal frugal colouring, Two-dimensional random projection, Backbone colorings of graphs with bounded degree, Quantitative noise sensitivity and exceptional times for percolation, A Fourier view on the \(R\)-transform and related asymptotics of spherical integrals, On the concentration and the convergence rate with a moment condition in first passage percolation, On measure concentration for separately Lipschitz functions in product spaces, Random weighting, asymptotic counting, and inverse isoperimetry, Variational bounds for the generalized random energy model, Modified logarithmic Sobolev inequalities in null curvature, Exponential concentration for first passage percolation through modified Poincaré inequalities, From the Prékopa-Leindler inequality to modified logarithmic Sobolev inequality, Perfect matchings and \(K_4^3\)-tilings in hypergraphs of large codegree, Sublinear variance in first-passage percolation for general distributions, Martingales, Poincaré type inequalities, and deviation inequalities, On modified logarithmic Sobolev inequalities for Bernoulli and Poisson measures, Central and \(L^p\)-concentration of 1-Lipschitz maps into \(R\)-trees, Typical configurations for one-dimensional random field Kac model, On the existence and nonexistence of finitary codings for a class of random fields, On random graph homomorphisms into \({\mathbb{Z}}\), Exponential integrability and transportation cost related to logarithmic Sobolev inequalities, Instability, complexity, and evolution, Characterization of Gaussian measures by the isoperimetric property of half-spaces, Coalescing and annihilating random walk with `action at a distance', Singular value decomposition of large random matrices (for two-way classification of microarrays), Concentration of measure and spectra of random matrices: applications to correlation matrices, elliptical distributions and beyond, Ramsey-Milman phenomenon, Urysohn metric spaces, and extremely amenable groups, Laws of large numbers and tail inequalities for random tries and PATRICIA trees

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1908323&oldid=14324065"