3
$\begingroup$

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!

$\endgroup$
7
  • $\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
    Commented Jun 10, 2017 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$ Commented Jun 11, 2017 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
    Commented Jun 11, 2017 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$ Commented Jun 11, 2017 at 21:03
  • $\begingroup$ Your "min" should be a "max", yes? $\endgroup$
    – usul
    Commented May 16, 2018 at 15:53

1 Answer 1

4
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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