Mixing
Proof of a technical fact in the book of Schapire and Freund on boosting
up vote
1
down vote
favorite
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}) = leftlbrace 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}; Tgeq 1 right. rightrbracetext{.}
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} lnleft(frac{1}{bar{K}} sum_{bar{y} in mathcal{bar{Y}}} expBig(-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)$ is a mapping from $mathcal{Y}$ to $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 = leftlbrace frac{4lnbar{K}}{itheta} : i = 1, ldots, leftlceil frac{8lnbar{K}}{theta^2} rightrceil rightrbracetext{.}
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{4lnbar{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| etanu_{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.
inequality
asked Nov 16 at 11:04
M. P.
35117
This question has an open bounty worth +50
reputation from M. P. ending in 6 days.
This question has not received enough attention.
add a comment |
up vote
1
down vote
favorite
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}) = leftlbrace 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}; Tgeq 1 right. rightrbracetext{.}
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} lnleft(frac{1}{bar{K}} sum_{bar{y} in mathcal{bar{Y}}} expBig(-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)$ is a mapping from $mathcal{Y}$ to $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 = leftlbrace frac{4lnbar{K}}{itheta} : i = 1, ldots, leftlceil frac{8lnbar{K}}{theta^2} rightrceil rightrbracetext{.}
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{4lnbar{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| etanu_{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.
inequality
asked Nov 16 at 11:04
M. P.
35117
This question has an open bounty worth +50
reputation from M. P. ending in 6 days.
This question has not received enough attention.
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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}) = leftlbrace 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}; Tgeq 1 right. rightrbracetext{.}
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} lnleft(frac{1}{bar{K}} sum_{bar{y} in mathcal{bar{Y}}} expBig(-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)$ is a mapping from $mathcal{Y}$ to $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 = leftlbrace frac{4lnbar{K}}{itheta} : i = 1, ldots, leftlceil frac{8lnbar{K}}{theta^2} rightrceil rightrbracetext{.}
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{4lnbar{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| etanu_{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.
inequality
asked Nov 16 at 11:04
M. P.
35117
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}) = leftlbrace 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}; Tgeq 1 right. rightrbracetext{.}
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} lnleft(frac{1}{bar{K}} sum_{bar{y} in mathcal{bar{Y}}} expBig(-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)$ is a mapping from $mathcal{Y}$ to $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 = leftlbrace frac{4lnbar{K}}{itheta} : i = 1, ldots, leftlceil frac{8lnbar{K}}{theta^2} rightrceil rightrbracetext{.}
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{4lnbar{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| etanu_{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.
inequality
inequality
asked Nov 16 at 11:04
M. P.
35117
asked Nov 16 at 11:04
M. P.
35117
asked Nov 16 at 11:04
M. P.
35117
asked Nov 16 at 11:04
M. P.
35117
asked Nov 16 at 11:04
M. P.
35117
35117
This question has an open bounty worth +50
reputation from M. P. ending in 6 days.
This question has not received enough attention.
This question has an open bounty worth +50
reputation from M. P. ending in 6 days.
This question has not received enough attention.
add a comment |
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3001005%2fproof-of-a-technical-fact-in-the-book-of-schapire-and-freund-on-boosting%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
