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!

• 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. – fedja Jun 10 '17 at 4:20
• Hi @fedja! I can get $\sqrt{kn}$ but with extra log factors -- can you get a bound that's strictly $O(\sqrt{kn})$? – Aryeh Kontorovich Jun 11 '17 at 7:27
• 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) :-) – fedja Jun 11 '17 at 19:25
• I do care :) my solution with the log factors is pretty elementary, and I'd love to see how to shave them off... – Aryeh Kontorovich Jun 11 '17 at 21:03
• Your "min" should be a "max", yes? – 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/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).$$