We prove that the $L_1$-discrepancy with arbitrary nonnegative weights suffers from the curse of dimensionality. More precisely, for every $\varepsilon \in (0,1)$ and $d \in \mathbb{N}$, the inverse of the $L_1$-discrepancy satisfies \[ N_{1,+}(\varepsilon, d) \ge \frac{(1-\varepsilon)^2}{1 + \varepsilon} \left( \frac{3+2 \sqrt{3}}{6}\right)^d, \] where $(3+2\sqrt{3})/6 = 1.07735\ldots$. The proof combines a change to a volume-biased probability measure with a fractional-moment estimate for the normalized discrepancy function. The lower bound applies, in particular, to equally weighted point sets. The argument uses the nonnegativity of the weights in an essential way and does not cover arbitrary signed weights.
We give a random-bit-efficient construction for the inverse star discrepancy. For every fixed $u\in(0,1)$, $k$-wise independent uniform points $\boldsymbol{X}_1,\ldots,\boldsymbol{X}_N$ with $k=O(d(1+\log(1+N/d)))$ satisfy the Monte Carlo bound $D_N^*(\boldsymbol{X}_1,\ldots,\boldsymbol{X}_N) =O(\sqrt{d/N})$ with probability at least $u$. Consequently, $N=O(d\varepsilon^{-2})$ and $k=O(d(1+\log\varepsilon^{-1}))$ suffice to attain discrepancy at most $\varepsilon$. The proof isolates the finitely many moments required by a chaining argument and gives explicit constants. A random vector-valued polynomial over a finite field realizes the required bounded independence on a grid using $O(d^2(1+\log(1+N/d))\log N)$ random bits, rather than the $\Theta(dN\log(dN))$ bits used by independent grid sampling.
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 $\Omega_n$ denote the set of $n\times n$ doubly stochastic matrices. Kim and Roush conjectured in 1981 that, for $n=2k+1>1$, $ \max_{A\in\Omega_{2k+1}}\operatorname{per}(I-A)=3\cdot 2^{k-2}$. They proposed the block construction $A_\star=\frac12(J_3-I_3)\oplus P_2^{\oplus(k-1)}$, where $P_2=\begin{pmatrix}0&1\\1&0\end{pmatrix}$. Here $J_3$ is the $3\times3$ all-ones matrix. They did not claim uniqueness. We fully prove their conjecture and classify equality: the maximizers are exactly the simultaneous-permutation conjugates of $A_\star$.
Given observations $\mathbf x=(x_1,\dots,x_n)$, Gaffke (2005) defined \[ K_n(\mathbf x)=\mathbb{P}_{\mathbf D}\!\left\{\sum_{i=1}^n x_iD_i\le 1\right\}, \qquad (D_0,D_1,\ldots,D_n)\sim\mathrm{Dirichlet}(1,\ldots,1), \] and conjectured that it is a $p$-value whenever the inputs are independent e-values. Recently, Vlassis and Thomas (2026) proved this conjecture. Inverting the tests for observations in $[0,1]$ gives the confidence interval studied by Learned-Miller and Thomas (2020), which reduces to Clopper--Pearson for Bernoulli data. We give a finite- and large-sample account of Gaffke's test and interval. First, for every $\mathbf x\in[0,\infty)^n$ and every elementary symmetric polynomial $e_k$, \( K_n(\mathbf x)e_k(\mathbf x)\le {n\choose k}, \) so the Gaffke $p$-value never larger than the SymPol $p$-value of Ming et al. (2026). However, Gaffke's p-value is inadmissible. For $n=2$, we construct a valid rule that is strictly smaller on mixed configurations and is the unique admissible rule that dominates $K_2$. A neutral-face extension proves inadmissibility of $K_n$ for every $n\ge2$. If one independent uniform random variable is allowed, there is an even simpler full-dimensional improvement: on the upper orthant, where $K_n(\mathbf x)=1/\prod_i x_i$, replace it by $U/\prod_i x_i$. The equal-tail Gaffke confidence interval $I_n$ is nevertheless first-order asymptotically efficient: for iid observations on $[0,1]$ with unknown variance $\sigma^2>0$, \[ \sqrt n\,\operatorname{Width}(I_n)\longrightarrow 2\sigma z_{1-\alpha/2}\qquad\text{almost surely}. \] Our simulations also find that, among a variety of bounded-mean intervals considered, the Gaffke interval is the shortest, including comparisons with a recent empirical Berry--Esseen procedure having the same first-order Gaussian target.
Jiahao Ming, Aaditya Ramdas, Yi Shen et al.· arXiv.org· 4 citations· ⚡1
Let $X_1,\ldots,X_n$ be independent Gaussian tensors in $\mathbb{R}^{d_1}\otimes\cdots\otimes\mathbb{R}^{d_k}$ with a common covariance matrix given by the Kronecker product of $k$ unknown positive-definite factors, and let $D=\prod_{a=1}^k d_a$ and $d_{\max}=\max_a d_a$. Franks et al. (2026) established condition-number-free guarantees for the tensor-normal maximum likelihood estimator under the sample-size condition $nD\gtrsim k^2 d_{\max}^3$ and asked whether the cubic dependence on $d_{\max}$ could be reduced to a quadratic one. We answer this question affirmatively. For $t\geq 1$, if $nD\geq C k^2 d_{\max}^2 t^2$, then with high probability the maximum likelihood estimator exists, is unique, and satisfies $d_{\rm FR}(\widehat\Theta,\Theta)\leq C t \sqrt{k} d_{\max}/\sqrt{n}$ and $d_{\rm FR}(\widehat\Theta_a,\Theta_a)\leq C t\sqrt{k d_a} d_{\max}/\sqrt{nD}$ for every mode $a$. For every mode $a$ with $d_a=d_{\max}$, we further establish the sharp Thompson-metric bound $d_{\rm op}(\widehat\Theta_a,\Theta_a)\leq C t d_{\max}/\sqrt{nD}$. These guarantees are uniform over the unknown covariance factors and require neither condition-number bounds nor sparsity assumptions. Gaussian submodel lower bounds match the full and largest-factor Fisher--Rao rates up to a factor of $\sqrt{k}$ and the largest-factor Thompson rate up to universal constants. Consequently, for fixed $k$, the quadratic dependence of the sample-size threshold on $d_{\max}$ is optimal. GPT-5.6 Sol and Claude Fable 5 were used to assist with proof development, verification, and manuscript preparation.
The dense result substantially generalizes a theorem of Bansal and Spencer (2020) for Rademacher inputs and gives an efficient $O(\sqrt{n})$ bound for Gaussian inputs, as conjectured by Gamarnik et al. (2022).
Nicola Wengiel· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
