Let $B\subset\mathbb{R}^d$ be the Euclidean $d$dimensional unit ball. It is wellknown 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!

$\begingroup$ Logarithmic is surely out of question. You cannot do better than $\sqrt{kn}$. Let me know if $\sqrt k$ instead of $k$ makes any difference for you. $\endgroup$ – fedja Jun 10 '17 at 4:20

$\begingroup$ Hi @fedja! I can get $\sqrt{kn}$ but with extra log factors  can you get a bound that's strictly $O(\sqrt{kn})$? $\endgroup$ – Aryeh Kontorovich Jun 11 '17 at 7:27

$\begingroup$ Not at the moment, but I certainly can try when I have free time and am not too tired. It is a funny problem. Just confirm that you still do care about it (otherwise I'll think of something else) :) $\endgroup$ – fedja Jun 11 '17 at 19:25

$\begingroup$ I do care :) my solution with the log factors is pretty elementary, and I'd love to see how to shave them off... $\endgroup$ – Aryeh Kontorovich Jun 11 '17 at 21:03

$\begingroup$ Your "min" should be a "max", yes? $\endgroup$ – usul May 16 '18 at 15:53
Here is a writeup of the $O(\sqrt{k\log k})$ bound: https://www.cs.bgu.ac.il/~karyeh/rademachermaxhyperplane.pdf
Update: 23Jul2018: Assuming the claims here are correct, the $\log k$ factor cannot be removed https://arxiv.org/abs/1807.07924
Update: 17Sep2018: 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). $$