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!



Rademacher average involving minima
Here is a writeup of the $O(\sqrt{k\log k})$ bound:
[https://www.cs.bgu.ac.il/~karyeh/rademacher-max-hyperplane.pdf](https://www.cs.bgu.ac.il/%7Ekaryeh/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).


