In this paper, we study the sample complexity of the empirical plug-in estimator for the $2$-Gromov-Wasserstein distance $D_2$ between compactly supported probability measures on Euclidean spaces. Let $\mu$ and $\nu$ be supported on compact subsets of $\mathbb{R}^{d_x}$ and $\mathbb{R}^{d_y}$, respectively, and let $\widehat\mu_n$ and $\widehat\nu_n$ be their empirical measures based on independent samples of size $n$. We prove that \[ \mathbb{E}\left|D_2^2(\widehat\mu_n,\widehat\nu_n)-D_2^2(\mu,\nu)\right| \lesssim n^{-2/((d_x\wedge d_y)\vee 4)} (\log n)^{\mathbf 1_{\{d_x\wedge d_y=4\}}}. \] This rate is sharp up to the logarithmic factor in the critical dimension. The proof is based on a geometric representation of the Euclidean distance as a squared $L^2$-distance between half-space feature maps. This yields a variational dual formulation of the Gromov-Wasserstein functional in terms of a family of classical optimal transport problems indexed by an infinite-dimensional auxiliary parameter. Although the resulting cost functions need not be semiconcave in either argument, we introduce a marginal recentering of the costs that restores the concavity structure needed for sharp metric-entropy bounds. Combining this representation with empirical-process estimates gives a rate governed by the smaller of the two ambient dimensions.
Let $\Pi$ be a $k\times n$ sparse random matrix. For a fixed $r$-dimensional subspace $V\subset{\mathbb R}^n$, let $U_V:{\mathbb R}^r\to{\mathbb R}^n$ denote an isometry from ${\mathbb R}^r$ onto $V$. The product $\Pi U_V$ is a central model in randomized dimension reduction and has been studied primarily through trace and Gaussian comparison inequalities. In this work, we develop an approach to the spectral norm of the matrix product $\Pi U_V$, based on entropy estimates for level sets of vectors $x\in V$. Combining the method with existing estimates, we show the following. Assume that \[ k\ge C\,r(\log\log r)^2,\qquad p\ge (\log k)/k. \] Let $\Pi$ be a $k\times n$ matrix with i.i.d. entries equidistributed with the product $b\,\xi$, where $b$ is a Bernoulli($p$) random variable and $\xi$ is mean-zero, independent of $b$, and satisfies $|\xi|\le1$ almost surely. Then with high probability \[ \|\Pi U_V\|\le C\sqrt{kp}. \] Matching results hold for other random models with negatively associated entries.
For every $n\ge 2$, we prove that there exists an exponent $p_n$ such that, for every even log-concave probability measure $\mu$ on $\mathbb R^n$, all nonempty symmetric convex sets $K,L\subseteq\mathbb R^n$, and all $\lambda\in[0,1]$, $$ \mu(\lambda K+(1-\lambda)L)^{p_n} \ge \lambda\mu(K)^{p_n}+(1-\lambda)\mu(L)^{p_n}, $$ where $$ p_n\ge \frac{c}{n^2\ln n} $$ for some absolute constant $c>0$.
Let $X_1,\ldots,X_N$ be independent random vectors in $\mathbb{R}^n$ with common isotropic log-concave distribution $\mu$ and set $P_{N,n}^{\mu}:=\operatorname{conv}\{\pm X_i:1\leqslant i\leqslant N\}$. Assume that $N/n=\gamma\geqslant \gamma_0$ where $\gamma_0>1$ is an absolute constant. We prove that with probability at least $1-C\gamma\exp(-c n^{1/4})$ every $k$-dimensional subspace $E$ of $(\mathbb{R}^n,\|\cdot\|_{P_{N,n}^{\mu}})$ satisfies $d_{\mathrm{BM}} (E,\ell_\infty^k) \geqslant c\gamma^{-C}k^\alpha$ for every $1\leqslant k\leqslant n$ where $c,C,\alpha>0$ are absolute constants. Consequently, with the same probability, $(\mathbb{R}^n,\|\cdot\|_{P_{N,n}^{\mu}})$ has cotype $q(\gamma)<\infty$ with cotype constant depending only on $\gamma$, in particular the cotype exponent and the cotype constant are independent of $n$ and of $\mu$. The proof adapts the deterministic coefficient scheme of Huang-Tikhomirov replacing the Gaussian estimates in their argument by estimates for isotropic log-concave random matrices. As an application, using the log-concave extension of Gluskin's theorem, we obtain a separable Banach space of finite cotype for which the Banach-Mazur diameter of its $k$-dimensional subspaces is of order $k$ and whose finite-dimensional building blocks are generated by isotropic log-concave random polytopes.
Let $X=(X_1,\ldots,X_n)$ have independent coordinates with mean zero, variance one, and $\|X_i\|_{\psi_2}\le K$, and let $H_d=(\mathbb R^n)^{\otimes_2 d}$. Let $L>0$ and let $f:H_d\to\mathbb R$ be convex and $L$-Lipschitz. We prove that, for $0\le t\le c_KLn^{d/2}$, \[ \textsf{P}\left\{ \left\lvert f(X^{\otimes d})-\textsf{E}f(X^{\otimes d})\right\rvert>t \right\} \le C\exp\left[-c_K\mathcal I_{n,d}\left( \frac{t}{L n^{(d-1)/2}} \right)\right], \] where \[ \mathcal I_{n,d}(s)= \min\left\{ \frac{s^2}{d^2}, \frac{s^2}{d\log(e+nd/s^2)} \right\},\qquad s>0, \qquad \mathcal I_{n,d}(0)=0. \] The first rate is forced by changes in $\|X\|$. The second comes from changes of $X$ when its norm is nearly fixed. The proof constructs one coupling that controls both the coordinatewise conditional displacement and the mean squared Euclidean distance, and combines these bounds with a second-order estimate for $x\mapsto x^{\otimes d}$. The rate is minimax sharp, scale by scale, even when the subgaussian norms are bounded by an absolute constant. For bounded coordinates the logarithm in the second rate disappears.
Let $d\geq 4$ and let $R>0$. When $d=4$, assume that $R^2\in\mathbb{N}\setminus 4\mathbb{N}$; when $d\geq 5$, let $R^2\in\mathbb{N}$ be arbitrary. We prove the fixed-radius estimate $$\|A_R f\|_{\ell^{p'}(\mathbb{Z}^d)}\leq C_{d,p,\varepsilon}R^{-d(2/p-1)+\varepsilon}\|f\|_{\ell^p(\mathbb{Z}^d)}$$ for $(d+2)/d\leq p\leq 2$, where $p'$ is the H\"older conjugate exponent of $p$ and $A_R$ is the probability average over the lattice sphere of radius $R$. This extends the fixed-radius estimates of Kesler--Lacey and Hughes to the sharp lower endpoint $p=(d+2)/d$.
A random $n\times k$ matrix $S$ is an \emph{$(r,\alpha)$-oblivious subspace injection} (OSI) if $\mathbb{E}\|S^\top x\|_2^2=\|x\|_2^2$ for every $x\in\mathbb{R}^n$, and for every fixed $r$-dimensional subspace $V\subset\mathbb{R}^n$, with probability close to one, one has $\alpha\|x\|_2^2\le\|S^\top x\|_2^2$ for all $x\in V$. In this work, we show that in the regime $r=\Omega(k)$ and $\alpha=\Omega(1)$, and under a mild additional structural assumption, no constant-row-sparsity matrix $S$ is OSI, thereby answering, in a strong form, a question raised by Cama\~no, Epperly, Meyer, and Tropp. We show that the failure of the OSI property for sparse random matrices stems from a general deterministic phenomenon, thereby reducing a probabilistic problem to a non-probabilistic one. This phenomenon is related to the restricted invertibility principle introduced in the seminal work of Bourgain--Tzafriri. Let $(n_k)_{k\in\mathbb{N}}$ be a sequence of integers satisfying $\frac{n_k}{k}\to\infty$. For each $k$, let $S^{(k)}$ be a $n_k\times k$ non-random matrix with $O(1)$ nonzero entries per row, whose nonzero entries have average magnitude $O(1)$, and such that the total number of pairs of rows with supports overlapping at two or more indices is $o({n_k}^2/k)$. We prove that for every constant $\varepsilon>0$, as $k\to\infty$, the overwhelming majority of $k\times \lfloor\varepsilon k\rfloor$ submatrices of $(S^{(k)})^\top$ have the smallest singular value $o(1)$. Thus, the well-invertible submatrices whose existence is guaranteed by the Bourgain--Tzafriri theorem are rare. The proof is itself based on probabilistic tools.
Han Huang, M. Rudelson, Konstantin E. Tikhomirov· 0 citations
