$\newcommand{\R}{\mathbb{R}}$ This question is about Problem 3.16 in Ryan O'Donnell's Analysis of Boolean Functions book. The problem is stated as follows:
Let $f : \{-1,1\}^n\to\R$ and let $\epsilon>0$. Show that $f$ is $\epsilon$-concentrated on a collection $F\subseteq 2^{[n]}$ with $|F|\leq \hat{||}f\hat{||}_1^2/\epsilon$.
Here, $\hat{||}f\hat{||}_1 := \sum_{S\subseteq [n]} |\widehat{f}(S)|$, and $f$ being $\epsilon$-concentrated on $F$ means $\sum_{S\notin F} \widehat{f}(S)^2 \leq \epsilon$. I have tried several approaches for this problem, and all seem to run into the pitfall of relating $\hat{||}f\hat{||}_1^2$ to $||f||_2$ (equivalently $\hat{||}f\hat{||}_2$ by Parseval's) in any nontrivial way. The most fruitful approach was using a probabilistic method: randomly sampling $|\widehat{f}(S)|$ uniformly over $S$, bounding the variance of this random variable, and applying Chebyshev's. But since $\mathbf{E}[|\widehat{f}(S)|]$ might be large and Chebyshev's only dictates deviation from the expectation, I don't think this approach yields the desired concentration bound. Would appreciate any hints or insight!
Edit: I was eventually able to find a solution. As a hint, start by constructing a reasonable set $F$ which trivially satisfies $|F|\leq \hat{||}f\hat{||}_1^2/\epsilon$. To prove $\epsilon$-concentration, recall the fairly simple technique used to bound $\sum \widehat{g}(S)^3$ in the analysis for the BLR test (Section 1.6 in Analysis of Boolean Functions).
