<p>This is not a research-level question (is it homework?). Hint: See Massart's Finite Class Lemma, for example here:
<a href="http://ttic.uchicago.edu/~tewari/lectures/lecture10.pdf" rel="nofollow">http://ttic.uchicago.edu/~tewari/lectures/lecture10.pdf</a></p>

CC BY-SA 3.0
2015-06-05T10:23:26.030Z
2015-06-05T10:23:26.030Z
Aryeh
<p>Some additional context would be nice and would help initiate a meaningful discussion, as well as make sure that the requirements to use some bound are fulfilled. Also, while related, the question at hand is strictly not TCS, although such lemmas are frequently used in proofs. Finally, it would be beneficial to acquire to research on your own an answer to your question, since i you are planning of conducting additional research in the future this knowledge will be extremely valuable. </p>

<p>I would suggest looking into the so-called "concentration inequalities", which with little modification should provide an answer to your question. If you are still having trouble finding with an answer after a week, I would also recommend cross-posting this question to <a href="https://math.stackexchange.com/">math.SE</a>, which seems more suited to give an answer. Make sure you indicate the question has already been posted elsewhere and provide a link to it, as is required by our site's <a href="https://cstheory.meta.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231">policy</a>.</p>

<p>Finally, I would suggest you read the relevant information on the <a href="https://cstheory.stackexchange.com/help/on-topic">help center</a>, on what kind of questions are relevant for cstheory.</p>

<p>PS: Posted this as answer as it contains some relevant information and it was too long for a comment.</p>

CC BY-SA 3.0
2015-06-05T09:46:07.030Z
2015-06-05T09:46:07.030Z
2017-04-13T12:32:28.080Z
chazisop
<p>Say $\sigma_1, \sigma_2, \dots, \sigma_m$ are i.i.d distributed $\pm1$ variables. How do I show that for any choice of $S_1, S_2, \dots, S_d$ subsets of $\{1, 2, \dots, m\}$, the expectation of the supremum over $S_i$ of the absolute value of the sum of the $\sigma$'s with indices in $S_i$ is bounded above by $\sqrt{2m \log d}$?</p>

CC BY-SA 3.0
2015-06-05T18:50:26.593Z
Please don't simultaneously cross-post, and always link to other places you've posted the question. http://mathoverflow.net/questions/208499/combinatorial-result-needed-in-machine-learning
usul
<co.combinatorics><machine-learning><pr.probability>
Lemma needed for my machine learning research
user196651
# Lemma needed for my machine learning research

(Asked by: username_0 on 2015-06-05)

Say $\sigma\_1, \sigma\_2, \dots, \sigma\_m$ are i.i.d distributed $\pm1$ variables. How do I show that for any choice of $S\_1, S\_2, \dots, S\_d$ subsets of $\{1, 2, \dots, m\}$, the expectation of the supremum over $S\_i$ of the absolute value of the sum of the $\sigma$'s with indices in $S\_i$ is bounded above by $\sqrt{2m \log d}$?

**Tags:** co.combinatorics, machine-learning, pr.probability

> **Comments:**
> **username_1**: Please don't simultaneously cross-post, and always link to other places you've posted the question. http://mathoverflow.net/questions/208499/combinatorial-result-needed-in-machine-learning  

---

## 2 answers

### Answer by username_2 on 2015-06-05. Score: 2

This is not a research-level question (is it homework?). Hint: See Massart's Finite Class Lemma, for example here:
<http://ttic.uchicago.edu/~tewari/lectures/lecture10.pdf>


---

### Answer by username_3 on 2015-06-05. Score: 0

Some additional context would be nice and would help initiate a meaningful discussion, as well as make sure that the requirements to use some bound are fulfilled. Also, while related, the question at hand is strictly not TCS, although such lemmas are frequently used in proofs. Finally, it would be beneficial to acquire to research on your own an answer to your question, since i you are planning of conducting additional research in the future this knowledge will be extremely valuable.

I would suggest looking into the so-called "concentration inequalities", which with little modification should provide an answer to your question. If you are still having trouble finding with an answer after a week, I would also recommend cross-posting this question to [math.SE](https://math.stackexchange.com/), which seems more suited to give an answer. Make sure you indicate the question has already been posted elsewhere and provide a link to it, as is required by our site's [policy](https://cstheory.meta.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231).

Finally, I would suggest you read the relevant information on the [help center](https://cstheory.stackexchange.com/help/on-topic), on what kind of questions are relevant for cstheory.

PS: Posted this as answer as it contains some relevant information and it was too long for a comment.


---

