Concentration of solutions to random equations with concentration of measure hypotheses

• URL: http://arxiv.org/abs/2010.09877v1
• Date: Mon, 19 Oct 2020 21:26:30 GMT
• Title: Concentration of solutions to random equations with concentration of measure hypotheses
• Authors: Cosme Louart and Romain Couillet
• Abstract summary: We study the concentration of random objects that are implicitly formulated as fixed points to equations $Y = f(X)$ where $f$ is a random mapping.
• Score: 45.24358490877106
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose here to study the concentration of random objects that are implicitly formulated as fixed points to equations $Y = f(X)$ where $f$ is a random mapping. Starting from an hypothesis taken from the concentration of the measure theory, we are able to express precisely the concentration of such solutions, under some contractivity hypothesis on $f$. This statement has important implication to random matrix theory, and is at the basis of the study of some optimization procedures like the logistic regression for instance. In those last cases, we give precise estimations to the first statistics of the solution $Y$ which allows us predict the performances of the algorithm.

Related papers

• Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor [7.069470347531414]
  Estimating the density of a distribution from its samples is a fundamental problem in statistics.<n> Hypothesis selection addresses the setting where, in addition to a sample set, we are given $n$ candidate distributions.<n>We propose a differentially private algorithm in the central model that runs in nearly-linear time with respect to the number of hypotheses.
  arXiv  Detail & Related papers  (2025-06-01T20:46:46Z)
• When fractional quasi p-norms concentrate [44.83880683386964]
  Concentration of distances in high dimension is an important factor for the development and design of stable and reliable data analysis algorithms.<n>We identify conditions when fractional quasi $p$-norms concentrate and when they don't.
  arXiv  Detail & Related papers  (2025-05-26T07:53:51Z)
• Parallel simulation for sampling under isoperimetry and score-based diffusion models [56.39904484784127]
  As data size grows, reducing the iteration cost becomes an important goal. Inspired by the success of the parallel simulation of the initial value problem in scientific computation, we propose parallel Picard methods for sampling tasks. Our work highlights the potential advantages of simulation methods in scientific computation for dynamics-based sampling and diffusion models.
  arXiv  Detail & Related papers  (2024-12-10T11:50:46Z)
• Transformer-based Parameter Estimation in Statistics [0.0]
  We propose a transformer-based approach to parameter estimation. It does not even require knowing the probability density function, which is needed by numerical methods. It is shown that our approach achieves similar or better accuracy as measured by mean-square-errors.
  arXiv  Detail & Related papers  (2024-02-28T04:30:41Z)
• MESSY Estimation: Maximum-Entropy based Stochastic and Symbolic densitY Estimation [4.014524824655106]
  MESSY estimation is a Maximum-Entropy based Gradient and Symbolic densitY estimation method. We construct a gradient-based drift-diffusion process that connects samples of the unknown distribution function to a guess symbolic expression. We find that the addition of a symbolic search for basis functions improves the accuracy of the estimation at a reasonable additional computational cost.
  arXiv  Detail & Related papers  (2023-06-07T03:28:47Z)
• Only Tails Matter: Average-Case Universality and Robustness in the Convex Regime [34.34747805050984]
  We show that the concentration of eigenvalues near the edges of the expected spectral distribution determines a problem's average complexity. We show that in the average-case context, Nesterov's method is universally nearly optimalally.
  arXiv  Detail & Related papers  (2022-06-20T17:16:52Z)
• Probability flow solution of the Fokker-Planck equation [10.484851004093919]
  We introduce an alternative scheme based on integrating an ordinary differential equation that describes the flow of probability. Unlike the dynamics, this equation deterministically pushes samples from the initial density onto samples from the solution at any later time. Our approach is based on recent advances in score-based diffusion for generative modeling.
  arXiv  Detail & Related papers  (2022-06-09T17:37:09Z)
• Variance Minimization in the Wasserstein Space for Invariant Causal Prediction [72.13445677280792]
  In this work, we show that the approach taken in ICP may be reformulated as a series of nonparametric tests that scales linearly in the number of predictors. Each of these tests relies on the minimization of a novel loss function that is derived from tools in optimal transport theory. We prove under mild assumptions that our method is able to recover the set of identifiable direct causes, and we demonstrate in our experiments that it is competitive with other benchmark causal discovery algorithms.
  arXiv  Detail & Related papers  (2021-10-13T22:30:47Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  This work provides a general framework for the non-asymotic analysis of sampling error in 2-Wasserstein distance. Our theoretical analysis is further validated by numerical experiments.
  arXiv  Detail & Related papers  (2021-09-08T18:00:05Z)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  We consider the task of heavy-tailed statistical estimation given streaming $p$ samples. We design a clipped gradient descent and provide an improved analysis under a more nuanced condition on the noise of gradients.
  arXiv  Detail & Related papers  (2021-08-25T21:30:27Z)
• Concentration of measure and generalized product of random vectors with an application to Hanson-Wright-like inequalities [45.24358490877106]
  This article provides an expression of the concentration of functionals $phi(Z_1,ldots, Z_m)$ where the variations of $phi$ on each variable depend on the product of the norms (or semi-norms) of the other variables. We illustrate the importance of this result through various generalizations of the Hanson-Wright concentration inequality as well as through a study of the random matrix $XDXT$ and its resolvent $Q =.
  arXiv  Detail & Related papers  (2021-02-16T08:36:28Z)
• Pathwise Conditioning of Gaussian Processes [72.61885354624604]
  Conventional approaches for simulating Gaussian process posteriors view samples as draws from marginal distributions of process values at finite sets of input locations. This distribution-centric characterization leads to generative strategies that scale cubically in the size of the desired random vector. We show how this pathwise interpretation of conditioning gives rise to a general family of approximations that lend themselves to efficiently sampling Gaussian process posteriors.
  arXiv  Detail & Related papers  (2020-11-08T17:09:37Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
  arXiv  Detail & Related papers  (2020-06-11T19:40:38Z)
• Marginal likelihood computation for model selection and hypothesis testing: an extensive review [66.37504201165159]
  This article provides a comprehensive study of the state-of-the-art of the topic. We highlight limitations, benefits, connections and differences among the different techniques. Problems and possible solutions with the use of improper priors are also described.
  arXiv  Detail & Related papers  (2020-05-17T18:31:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.