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!

  • $\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/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). $$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.