We design a deterministic algorithm that, given \(n\) points in a typical constant degree regular graph, queries \(O(n)\) distances to output a constant factor approximation to the average distance among those points, thus answering a question posed in [Mendel and Naor 2015]. Our algorithm uses the method of [Mendel and Naor 2015] to construct a sequence of constant degree graphs that are expanders with respect to certain nonpositively curved metric spaces, together with a new rigidity theorem for metric transforms of nonpositively curved metric spaces. The fact that our algorithm works for typical (uniformly random) constant degree regular graphs rather than for all constant degree graphs is unavoidable, thanks to the following impossibility result that we obtain: For every fixed \(k \in \mathbb N\), the approximation factor of any algorithm for average distance that works for all constant degree graphs and queries \(o(n^{1+1/k})\) distances must necessarily be at least \(2(k + 1)\). This matches the upper bound attained by the algorithm that was designed for general finite metric spaces in [Barhum et. al. 2007]. Thus, any algorithm for average distance in constant degree graphs whose approximation guarantee is less than 4 must query \(\Omega(n^2)\) distances, any such algorithm whose approximation guarantee is less than 6 must query \(\Omega(n^{3/2})\) distances, any such algorithm whose approximation guarantee less than 8 must query \(\Omega(n^{3/4})\) distances, and so forth, and furthermore there exist algorithms achieving those parameters.

International audience

We study the entropy and Fisher information of mixtures of centered Gaussian random variables (with respect to the variance). First, we prove that if$X_{1}, X_{2}$are independent scalar Gaussian mixtures, then the entropy of$\sqrt{t}X_{1}+\sqrt{1-t}X_{2}$is concave in$t\in[0,1]$, thus confirming a conjecture of Ball, Nayar and Tkocz (2016) for this class of random variables. In fact, we prove a generalisation of this statement, which also strengthens a result of Eskenazis, Nayar and Tkocz (2018). Secondly, we establish rates of convergence for the Fisher information matrix of the sum of weighted i.i.d. Gaussian mixtures in the operator norm along the central limit theorem under mild moment assumptions. These are obtained by showing that the Fisher information matrix is operator convex as a matrix-valued function acting on densities of mixtures in$\mathbb{R}^{d}$, extending a result of Bobkov (2022). A full version of this paper is available at: arXiv:2308.15997.

Abstract Fix $$p\in [1,\infty )$$ p∈[1,∞) , $$K\in (0,\infty )$$ K∈(0,∞) , and a probability measure $$\mu $$ μ . We prove that for every $$n\in \mathbb {N}$$ n∈N , $$\varepsilon \in (0,1)$$ ε∈(0,1) , and $$x_1,\ldots ,x_n\in L_p(\mu )$$ x1,…,xn∈Lp(μ) with $$\big \Vert \max _{i\in \{1,\ldots ,n\}} |x_i| \big \Vert _{L_p(\mu )} \le K$$ ‖maxi∈{1,…,n}|xi|‖Lp(μ)≤K , there exist $$d\le \frac{32e^2 (2K)^{2p}\log n}{\varepsilon ^2}$$ d≤32e2(2K)2plognε2 and vectors $$y_1,\ldots , y_n \in \ell _p^d$$ y1,…,yn∈ℓpd such that $$\begin{aligned} {\forall }\,\,i,j\in \{1,\ldots ,n\}, \quad \Vert x_i-x_j\Vert ^p_{L_p(\mu )}-\varepsilon\le & {} \Vert y_i-y_j\Vert _{\ell _p^d}^p\le \Vert x_i-x_j\Vert ^p_{L_p(\mu )}+\varepsilon . \end{aligned}$$ ∀i,j∈{1,…,n},‖xi-xj‖Lp(μ)p-ε≤ ‖yi-yj‖ℓpdp≤‖xi-xj‖Lp(μ)p+ε. Moreover, the argument implies the existence of a greedy algorithm which outputs $$\{y_i\}_{i=1}^n$$ {yi}i=1n after receiving $$\{x_i\}_{i=1}^n$$ {xi}i=1n as input. The proof relies on a derandomized version of Maurey’s empirical method (1981) combined with a combinatorial idea of Ball (1990) and a suitable change of measure. Motivated by the above embedding, we introduce the notion of $$\varepsilon $$ ε -isometric dimension reduction of the unit ball $${\textbf {B}}_E$$ BE of a normed space $$(E,\Vert \cdot \Vert _E)$$ (E,‖·‖E) and we prove that $${\textbf {B}}_{\ell _p}$$ Bℓp does not admit $$\varepsilon $$ ε -isometric dimension reduction by linear operators for any value of $$p\ne 2$$ p≠2 .

We prove that every bounded function f:{−1,1}n→[−1,1] of degree at most d can be learned with L2-accuracy ε and confidence 1−δ from log(n/δ) ε−d−1 Cd3/2√logd random queries, where C>1 is a universal finite constant.