Hi, this is the first time I post a question here, so I'd be glad to have comments to make it better. So here it goes.
The problem
I am looking to compute the Rademacher complexity of a class of function and I have reduced the problem to this. Let $\vec{\sigma} \in \{\pm 1\}^m$ be a set of $m$ Rademacher variables (i.e. taking value $\pm 1$ with probability $\frac{1}{2}$ each). Split $\vec{\sigma}$ in two consecutive sequences: sum each sequence individually, then take the absolute value of these sums before summing them together. I am looking for the split which will achieve the maximum value for this operation. More formally, we write:
\begin{align} T(\vec{\sigma}) = \displaystyle\sup_{1 \leq i < m} \left( \left| \sum_{k \leq i} \sigma_k \right| + \left| \sum_{k > i} \sigma_k \right| \right). \end{align}
We need to take the expectation over $\vec{\sigma}$ of this expression to obtain the Rademacher complexity: \begin{align} R_m = \E_{\vec{\sigma}} \left[ T(\vec{\sigma}) \right]. \end{align}
I am looking for an analytical expression for $R_m$.
Questions
- Is this problem known or equivalent to another one? If yes, I'd like references.
- If not, is there a way to compute exactly $R_m$?
- If not, is it possible to upper bound it non-trivially? (A trivial bound would be $R_m \leq m$.)
Any insight about how to tackle the problem would be appreciated, and could be accepted as an answer if none of the above is provided.
What I've tried
I have computed the sum over all $\vec{\sigma}$ up to $m=12$ to find a pattern, without success. Here they are: \begin{equation} \begin{array}\\ m & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ 2^m R_m & 2 & 8 & 20 & 48 & 112 & 248 & 548 & 1184 & 2540 & 5408 & 11420 & 24048 \end{array} \end{equation} This sequence is not in the OEIS, so no luck there.
I have tried to express $R_m$ in terms of $R_{m-1}$. I was not able to find a pattern there either.
Finally, I have tried to express the numbers $2^m R_m$ as a sum by counting the number of $\vec{\sigma}$ for which $T(\vec{\sigma})$ would give $m$, then how many would give $m-2$, then $m-4$, etc. up to $m=2$ or $1$ (if $m$ is even or odd). (It is easy to convince yourself that $m$ minus an odd number is not possible.) Mathematically speaking, we have: \begin{align} 2^m R_m = \sum_{i=0}^{\lfloor \frac{m}{2} \rfloor} a^m_i (m-2i). \end{align}
I have found that:
- for all $m\geq 1$, $a^m_0 = 2m$
- for all $m\geq 4$, $a^m_1 = 2m(m-3)$
- for all $m\geq 7$, $a^m_2 = m(m^2 -7m +8)$
- for all even $m=2n$, the last coefficient is $a^m_{n-1} = 2^{n+1}$
- for all odd $m=2n+1$, the last coefficient is $a^m_n = 2$
I have yet to find a general formula for $a^m_i$, but it would be a nice starting point.
Related problem
I have considered the following related simpler problem \begin{align} T^0(\vec{\sigma}) = \left| \sum_{k=1}^m \sigma_k \right|, \qquad R^0_m = \E_{\vec{\sigma}} \left[ T^0(\vec{\sigma}) \right]. \end{align} We have that for all $\vec{\sigma}$, $T^0(\vec{\sigma}) \leq T(\vec{\sigma})$.
This problem has an exact solution. We have that \begin{align} 2^m R_m = \sum_{i=0}^{\lfloor \frac{m}{2} \rfloor} 2 \binom{m}{i} (m-2i) = 2m \binom{m-1}{\lfloor \frac{m}{2} \rfloor}. \end{align}
Just to give an idea, this function is upper bounded by \begin{align} 2m \binom{m-1}{\lfloor \frac{m}{2} \rfloor} \leq \sqrt{\frac{2}{\pi}} \frac{2^m m}{\sqrt{m+\frac{1}{2}}}. \end{align}
Hope this can give some insights.