Disclaimer: I asked this question on math.stackexchange.com two weeks ago but it has not been answered yet so I figured that I might as well try to also post it here.
I am currently looking at Exercise 10.3, Chapter 10 of the book on Boosting by Schapire and Freund. More precisely, in the middle of the exercise they propose to use, without proof, the technical fact summarized below. Obviously, since it can be used without proof, I am now curious to know how to prove it!
To summarize the problem, let $\mathcal{H}$ bet a set of functions $h : \mathcal{X} \times \mathcal{\bar{Y}} \rightarrow [-1,1]$. Define $\text{co}(\mathcal{H})$ as \begin{align*} \text{co}(\mathcal{H}) = \left\lbrace f : x,\bar{y} \mapsto \sum_{t=1}^T a_t h_t(x,\bar{y}) \left| a_1,\ldots,a_T \geq 0; \sum_{t=1}^Ta_t = 1; h_1,\ldots h_T \in \mathcal{H}; T\geq 1 \right. \right\rbrace\text{.} \end{align*} Notice that $f : \mathcal{X} \times \mathcal{\bar{Y}} \rightarrow [-1,1]$. For $f \in \text{co}\left(\mathcal{H}\right)$, $\eta > 0$, $\bar{K} = |\mathcal{\bar{Y}}|$, and $(x,y) \in \mathcal{X} \times \mathcal{Y}$, let \begin{align*} \nu_{f,\eta}(x,y) = - \frac{1}{\eta} \ln\left(\frac{1}{\bar{K}} \sum_{\bar{y} \in \mathcal{\bar{Y}}} \exp\Big(-\eta \Omega(y,\bar{y}) f(x,\bar{y})\Big)\right) \end{align*} where $\Omega(y,\bar{y}) = 1$ if $\bar{y} \in \Omega(y)$ and $-1$ otherwise. $\Omega(y)$ associates each element from $\mathcal{Y}$ to a subset of $\mathcal{\bar{Y}}$. Notice that $\nu_{f,\eta} : \mathcal{X} \times \mathcal{Y} \rightarrow [-1,1]$.
The technical fact is as follows. Let $1 \geq \theta > 0$ and define the grid: \begin{align*} \varepsilon_\theta = \left\lbrace \frac{4\ln\bar{K}}{i\theta} : i = 1, \ldots, \left\lceil \frac{8\ln\bar{K}}{\theta^2} \right\rceil \right\rbrace\text{.} \end{align*} For any $\eta > 0$, let $\hat{\eta}$ be the closest value in $\varepsilon_\theta$ to $\eta$. Then for all $f \in \text{co}(\mathcal{H})$ and for all $(x,y) \in \mathcal{X} \times \mathcal{Y}$, \begin{align*} \left| \nu_{f,\eta}(x,y) - \nu_{f,\hat{\eta}}(x,y) \right| \leq \frac{\theta}{4}\text{.} \end{align*}
So far, I proved the statement when $\eta > \frac{4\ln\bar{K}}{\theta}$ (using the properties of the LogSumExp function). Furthermore, using the grid, I showed that \begin{align*} && \left| \eta - \hat{\eta} \right| \leq \frac{\ln \bar{K}}{\theta} \\ &\Rightarrow& \left| \eta\nu_{f,\eta}(x,y) - \hat{\eta}\nu_{f,\hat{\eta}}(x,y) \right| \leq \frac{\ln \bar{K}}{\theta}\text{.} \end{align*} However, I did not manage to go further than that.
Am I going in the right direction? If yes, what would be the trick for the last step? If no, what method should I consider to prove this statement? Note that I am not asking for a full proof, but rather some hints on how to proceed to show the result.
