Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userToy examples for effective concentration bounds
75
0
0.0
(
0
)
Authors
Beno^it Kloeckner
Ask ChatGPT about the research
No Arabic abstract
In this note we prove a spectral gap for various Markov chains on various functional spaces. While proving that a spectral gap exists is relatively common, explicit estimates seems somewhat rare.These estimates are then used to apply the concentration inequalities of Effective limit theorems for Markov chains with a spectral gap (most of the present material was part of Section 3 of that article, which has been reduced to its core in the published version).
rate research
Read More
The problem of constructing pseudorandom generators that fool halfspaces has been studied intensively in recent times. For fooling halfspaces over the hypercube with polynomially small error, the best construction known requires seed-length O(log^2 n) (MekaZ13). Getting the seed-length down to O(log(n)) is a natural challenge in its own right, which needs to be overcome in order to derandomize RL. In this work we make progress towards this goal by obtaining near-optimal generators for two important special cases: 1) We give a near optimal derandomization of the Chernoff bound for independent, uniformly random bits. Specifically, we show how to generate a x in {1,-1}^n using $tilde{O}(log (n/epsilon))$ random bits such that for any unit vector u, <u,x> matches the sub-Gaussian tail behaviour predicted by the Chernoff bound up to error eps. 2) We construct a generator which fools halfspaces with {0,1,-1} coefficients with error eps with a seed-length of $tilde{O}(log(n/epsilon))$. This includes the important special case of majorities. In both cases, the best previous results required seed-length of $O(log n + log^2(1/epsilon))$. Technically, our work combines new Fourier-analytic tools with the iterative dimension reduction techniques and the gradually increasing independence paradigm of previous works (KaneMN11, CelisRSW13, GopalanMRTV12).
The brightness theorem---brightness is nonincreasing in passive systems---is a foundational conservation law, with applications ranging from photovoltaics to displays, yet it is restricted to the field of ray optics. For general linear wave scattering, we show that power per scattering channel generalizes brightness, and we derive power-concentration bounds for systems of arbitrary coherence. The bounds motivate a concept of wave {e}tendue as a measure of incoherence among the scattering-channel amplitudes, and which is given by the rank of an appropriate density matrix. The bounds apply to nonreciprocal systems that are of increasing interest, and we demonstrate their applicability to maximal control in nanophotonics, for metasurfaces and waveguide junctions. Through inverse design, we discover metasurface elements operating near the theoretical limits.
This paper gives a review of concentration inequalities which are widely employed in non-asymptotical analyses of mathematical statistics in a wide range of settings, from distribution-free to distribution-dependent, from sub-Gaussian to sub-exponential, sub-Gamma, and sub-Weibull random variables, and from the mean to the maximum concentration. This review provides results in these settings with some fresh new results. Given the increasing popularity of high-dimensional data and inference, results in the context of high-dimensional linear and Poisson regressions are also provided. We aim to illustrate the concentration inequalities with known constants and to improve existing bounds with sharper constants.
Consider the set of all sequences of $n$ outcomes, each taking one of $m$ values, that satisfy a number of linear constraints. If $m$ is fixed while $n$ increases, most sequences that satisfy the constraints result in frequency vectors whose entropy approaches that of the maximum entropy vector satisfying the constraints. This well-known entropy concentration phenomenon underlies the maximum entropy method. Existing proofs of the concentration phenomenon are based on limits or asymptotics and unrealistically assume that constraints hold precisely, supporting maximum entropy inference more in principle than in practice. We present, for the first time, non-asymptotic, explicit lower bounds on $n$ for a number of variants of the concentration result to hold to any prescribed accuracies, with the constraints holding up to any specified tolerance, taking into account the fact that allocations of discrete units can satisfy constraints only approximately. Again unlike earlier results, we measure concentration not by deviation from the maximum entropy value, but by the $ell_1$ and $ell_2$ distances from the maximum entropy-achieving frequency vector. One of our results holds independently of the alphabet size $m$ and is based on a novel proof technique using the multi-dimensional Berry-Esseen theorem. We illustrate and compare our results using various detailed examples.
Let $(X, mathcal{B},mu,T)$ be an ergodic measure preserving system, $A in mathcal{B}$ and $epsilon>0$. We study the largeness of sets of the form begin{equation*} begin{split} S = left{ ninmathbb{N}colonmu(Acap T^{-f_1(n)}Acap T^{-f_2(n)}Acapldotscap T^{-f_k(n)}A)> mu(A)^{k+1} - epsilon right} end{split} end{equation*} for various families ${f_1,dots,f_k}$ of sequences $f_icolon mathbb{N} to mathbb{N}$. For $k leq 3$ and $f_{i}(n)=i f(n)$, we show that $S$ has positive density if $f(n)=q(p_n)$ where $q in mathbb{Z}[x]$ satisfies $q(1)$ or $q(-1) =0$ and $p_n$ denotes the $n$-th prime; or when $f$ is a certain Hardy field sequence. If $T^q$ is ergodic for some $q in mathbb{N}$, then for all $r in mathbb{Z}$, $S$ is syndetic if $f(n) = qn + r$. For $f_{i}(n)=a_{i}n$, where $a_{i}$ are distinct integers, we show that $S$ can be empty for $kgeq 4$, and for $k = 3$ we found an interesting relation between the largeness of $S$ and the abundance of solutions to certain linear equations in sparse sets of integers. We also provide some partial results when the $f_{i}$ are distinct polynomials.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
