2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It seems like this could be boiled down to a question about the log partition function $f(\vec{z}) = \ln(\sum_j \exp(z_j))$, without needing so much of the background... $\endgroup$ – usul Nov 30 '18 at 15:34
  • $\begingroup$ Sorry for the late reply. If I know a bit about the LogSumExp function, I am not so familiar with the log partition function. I tried to dig around for some properties of the function that could help in my case without much success. I agree that all the gory details that I added here might not be necessary but I chose to keep them in case some of them end up being relevant... $\endgroup$ – M. P. Dec 13 '18 at 11:14

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.