For Gaussian approximation over high-dimensional rectangles under unrestricted covariance, Chernozhukov et al. (2023b) conjectured that the $n^{-1/4}$ rate, up to logarithmic factors, is near-optimal. We show that, under the coordinatewise subexponential condition with scale $B_n$ and the marginal variance lower bound condition with constant $b$ in Chernozhukov et al. (2023b), the approximation error in dimension $d$ is bounded by \begin{align*} C_b\min\left\{ 1,\, \left(\frac{B_n^2}{n}\right)^{1/3}\{\log(2dn)\}^{7/3} + \frac{B_n}{\sqrt n}\{\log(2dn)\}^{5/2} \right\}. \end{align*} In particular, for bounded $B_n$ and polynomial dimension, the new bound is $n^{-1/3}$ and therefore falsifies the polynomial-dimensional $n^{-1/4}$ near-optimality conjecture. The proof uses a two-stage interpolation and a rank-free matrix-weighted Gaussian surface bound, which may be of independent interest. The initial proof attempt was generated by ChatGPT 5.6 Pro (OpenAI) and subsequently corrected and rewritten by the authors. The machine-checked Lean formalization of the proof can be found at the GitHub repository (https://github.com/WeihanZhang2001/cubic-root-gaussian-approximation-under-unrestricted-covariance).
We establish a nonasymptotic Gaussian approximation bound over centered Euclidean balls for sums of independent, not necessarily identically distributed, random vectors in \(\mathbb R^p\). Let \(S_n\) denote the sum, let \(\Sigma=\operatorname{Var}(S_n)\), and let \(G\sim N(0,\Sigma)\). Define the effective rank and th...
A. Naumov, Sergey Samsonov, Vladimir Spokoiny et al.· 0 citations
We characterize, up to logarithmic factors, the minimax expected query complexity of finite-sum nonconvex-strongly-concave optimization under mean-squared averaged smoothness. For randomized zero-respecting incremental first-order algorithms, the complexity is $\tilde{\Theta}(n+\min\{\sqrt{n}\,\kappa,n^{3/4}\sqrt{\kapp...
For sequences of $n$ nonnegative integer vectors in $\mathbb Z^k$ with distinct subset sums, we prove, for fixed $k$, the uniform lower bound $M\ge (C_k-o(1))2^{n/k}/\sqrt n$ for the largest coordinate, where \[ C_k=\sqrt{\frac{2k}{\pi}}\, \frac{(k+1)^{(k-1)/(2k)}}{\sqrt{\lfloor (k+1)^2/4\rfloor}}. \] The proof compare...
We study large deviations of the spectral radius of $X_n=n^{-1/2}(\xi_{ij})_{i,j=1}^n$, where the entries are iid, centered, variance-one, and subgaussian, with zero pseudovariance in the complex case. We write $\rho(X_n)$ for its spectral radius, i.e. the largest modulus among its eigenvalues. For every fixed $r>1$, w...
Let $\nu$ be a compactly supported Borel probability measure on $\mathbb R^{d}$ with $\nu(B(x,r))\leq Cr^{a}$ for some $a>0$. Refine a dyadic cube exactly when its mass is at least $t$, and let $\mathcal{L}_{\nu}(t)$ be the mean depth at which this refinement stops. We show that the lower and upper geometric-mean quant...
M. Kessebohmer, Aljoscha Niemann· arXiv.org· 0 citations
We prove a joint stochastic zeroth-order lower bound for Goldstein stationarity on a Euclidean query ball, even when the ball is guaranteed to contain a stationary point. In dimension $d$, let $f=\mathbb{E}[F(\cdot;\xi)]$, assume $\mathbb{E}[\operatorname{Lip}(F(\cdot;\xi))^2]\le L_0^2$, and bound the initial objective...
