Rademacher average involving minima

Question

Let $B\subset\mathbb{R}^d$ be the Euclidean $d$-dimensional unit ball. It is well-known that for any $x_1,\ldots,x_n\in B$, we have the following upper bound on the Rademacher complexity $$ R_n := \mathbb{E}\sup_{w\in B}\sum_{i=1}^n \sigma_i(w\cdot x_i)\le\sqrt n, $$ where the expectation is over the Rademacher sequence $\sigma$, distributed uniformly in $\{-1,1\}^n$. Suppose I am interested in the following quantity: $$ R_{n,k} := \mathbb{E} \sup_{w_1,w_2,\ldots,w_k\in B} \sum_{i=1}^n \sigma_i\min\{ w_1\cdot x_i, w_2\cdot x_i, \ldots, w_k\cdot x_i\} . $$ I think I can show that $R_{n,k}=O(k\sqrt n)$, but I'm wondering if a better dependence on $k$ is possible. Logarithmic would be very nice, if true!

Answer 1

Here is a writeup of the $O(\sqrt{k\log k})$ bound: https://www.cs.bgu.ac.il/~karyeh/rademacher-max-hyperplane.pdf

Update: 23-Jul-2018: Assuming the claims here are correct, the $\log k$ factor cannot be removed https://arxiv.org/abs/1807.07924

Update: 17-Sep-2018: The previous calculation at the link had a mistake, giving the wrong dependence on $n$. After fixing it (see link above), we get a bound of $$ O\left(\sqrt{\frac{k\log k\cdot(\log n)^3}{n}}\right). $$

Update: 19-Dec-2021: The claim in my original writeup is correct (up to constants), but the proof is not! Here is (hopefully) a correct proof: https://arxiv.org/abs/2110.04763 (see Thm. 3 for the claim and the Discussion section for a careful explanation of previous mistaken attempts).