Help on application of Marton's transportation method (Bucheron-Lugosi-Massart)
$begingroup$
I was trying to apply Marton's transportation inequality in the following exercise from Bucheron, Lugosi, Massart's text on concentration inequalities:
Exercise 8.1. Use Marton's transportation inequality to show that if $P$ is a product probability measure on $mathcal{X}^n$, then for any $A, B subset mathcal{X}^n$ measurable,
$$
d_H(A, B) leq sqrt{frac{n}{2} log frac{1}{P(A)}} +
sqrt{frac{n}{2} log frac{1}{P(B)}}.
$$
Above, $d_H(A, B) = min_{xin A, y in B} sum_{i=1}^n mathbf{1}_{x_i neq y_i}$ is the Hamming distance between $A$ and $B$.
Any hints at all would be appreciated. The only thing I've gotten is that by Cauchy-Schwarz, we can weaken the version of Marton's inequality given
in the text to
$$
min_{mathbf{P} in mathcal{P}(P, Q)} sum_{i=1}^n mathbf{P}(X_i neq Y_i) leq sqrt{frac{n}{2} D(Q | P)},
$$
where $mathcal{P}(P, Q)$ is, as stated in the text, couplings of $P$ with $Q ll P$. So you may hope to find $Q ll P$ such that the $sqrt{D(Q | P)} leq sqrt{log frac{1}{P(A)}} + sqrt{log frac{1}{P(B)}}$, and then take an expectation. That's just a guess, though. I hadn't made much progress trying to construct such $Q$.
probability-theory concentration-of-measure optimal-transport
asked Dec 23 '18 at 19:46
Drew BradyDrew Brady
719315
$endgroup$
add a comment |
$begingroup$
I was trying to apply Marton's transportation inequality in the following exercise from Bucheron, Lugosi, Massart's text on concentration inequalities:
Exercise 8.1. Use Marton's transportation inequality to show that if $P$ is a product probability measure on $mathcal{X}^n$, then for any $A, B subset mathcal{X}^n$ measurable,
$$
d_H(A, B) leq sqrt{frac{n}{2} log frac{1}{P(A)}} +
sqrt{frac{n}{2} log frac{1}{P(B)}}.
$$
Above, $d_H(A, B) = min_{xin A, y in B} sum_{i=1}^n mathbf{1}_{x_i neq y_i}$ is the Hamming distance between $A$ and $B$.
Any hints at all would be appreciated. The only thing I've gotten is that by Cauchy-Schwarz, we can weaken the version of Marton's inequality given
in the text to
$$
min_{mathbf{P} in mathcal{P}(P, Q)} sum_{i=1}^n mathbf{P}(X_i neq Y_i) leq sqrt{frac{n}{2} D(Q | P)},
$$
where $mathcal{P}(P, Q)$ is, as stated in the text, couplings of $P$ with $Q ll P$. So you may hope to find $Q ll P$ such that the $sqrt{D(Q | P)} leq sqrt{log frac{1}{P(A)}} + sqrt{log frac{1}{P(B)}}$, and then take an expectation. That's just a guess, though. I hadn't made much progress trying to construct such $Q$.
probability-theory concentration-of-measure optimal-transport
asked Dec 23 '18 at 19:46
Drew BradyDrew Brady
719315
$endgroup$
add a comment |
$begingroup$
I was trying to apply Marton's transportation inequality in the following exercise from Bucheron, Lugosi, Massart's text on concentration inequalities:
Exercise 8.1. Use Marton's transportation inequality to show that if $P$ is a product probability measure on $mathcal{X}^n$, then for any $A, B subset mathcal{X}^n$ measurable,
$$
d_H(A, B) leq sqrt{frac{n}{2} log frac{1}{P(A)}} +
sqrt{frac{n}{2} log frac{1}{P(B)}}.
$$
Above, $d_H(A, B) = min_{xin A, y in B} sum_{i=1}^n mathbf{1}_{x_i neq y_i}$ is the Hamming distance between $A$ and $B$.
Any hints at all would be appreciated. The only thing I've gotten is that by Cauchy-Schwarz, we can weaken the version of Marton's inequality given
in the text to
$$
min_{mathbf{P} in mathcal{P}(P, Q)} sum_{i=1}^n mathbf{P}(X_i neq Y_i) leq sqrt{frac{n}{2} D(Q | P)},
$$
where $mathcal{P}(P, Q)$ is, as stated in the text, couplings of $P$ with $Q ll P$. So you may hope to find $Q ll P$ such that the $sqrt{D(Q | P)} leq sqrt{log frac{1}{P(A)}} + sqrt{log frac{1}{P(B)}}$, and then take an expectation. That's just a guess, though. I hadn't made much progress trying to construct such $Q$.
probability-theory concentration-of-measure optimal-transport
asked Dec 23 '18 at 19:46
Drew BradyDrew Brady
719315
$endgroup$
I was trying to apply Marton's transportation inequality in the following exercise from Bucheron, Lugosi, Massart's text on concentration inequalities:
Exercise 8.1. Use Marton's transportation inequality to show that if $P$ is a product probability measure on $mathcal{X}^n$, then for any $A, B subset mathcal{X}^n$ measurable,
$$
d_H(A, B) leq sqrt{frac{n}{2} log frac{1}{P(A)}} +
sqrt{frac{n}{2} log frac{1}{P(B)}}.
$$
Above, $d_H(A, B) = min_{xin A, y in B} sum_{i=1}^n mathbf{1}_{x_i neq y_i}$ is the Hamming distance between $A$ and $B$.
Any hints at all would be appreciated. The only thing I've gotten is that by Cauchy-Schwarz, we can weaken the version of Marton's inequality given
in the text to
$$
min_{mathbf{P} in mathcal{P}(P, Q)} sum_{i=1}^n mathbf{P}(X_i neq Y_i) leq sqrt{frac{n}{2} D(Q | P)},
$$
where $mathcal{P}(P, Q)$ is, as stated in the text, couplings of $P$ with $Q ll P$. So you may hope to find $Q ll P$ such that the $sqrt{D(Q | P)} leq sqrt{log frac{1}{P(A)}} + sqrt{log frac{1}{P(B)}}$, and then take an expectation. That's just a guess, though. I hadn't made much progress trying to construct such $Q$.
probability-theory concentration-of-measure optimal-transport
probability-theory concentration-of-measure optimal-transport
asked Dec 23 '18 at 19:46
Drew BradyDrew Brady
719315
asked Dec 23 '18 at 19:46
Drew BradyDrew Brady
719315
asked Dec 23 '18 at 19:46
Drew BradyDrew Brady
719315
asked Dec 23 '18 at 19:46
Drew BradyDrew Brady
719315
asked Dec 23 '18 at 19:46
Drew BradyDrew Brady
719315
719315
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
When applying Marton's inequality you have not mentioned how to link $d_H(A,B)$ to $min sum_i P(X_i ne Y_i)$. In particular, $X$ must come from the $P$-measure and $Y$ must come from the $Q$-measure (or vice versa).
It seems we can WLOG assume $A$ and $B$ have positive $P$-measure, else the right-hand side is undefined.
Let $Z sim P$. Let $X sim Q_A$ and $Y sim Q_B$ where $Q_A$ and $Q_B$ are supported on $A cap text{support}(P)$ and $B cap text{support}(P)$ respectively.
The following inequalities hold almost surely.
$$min_{x in A, y in B} sum_{i=1}^n 1_{x_i ne y_i}
le min_{x in A, y in B} left(sum_{i=1}^n 1_{x_i ne Z_i} + sum_{i=1}^n 1_{Z_i ne y_i}right)
le sum_{i=1}^n 1_{X_i ne Z_i} + sum_{i=1}^n 1_{Z_i ne Y_i}.$$
Taking expectations of both sides yields
$$d_H(A,B) le sum_{i=1}^n P(Z_i ne X_i) + sum_{i=1}^n P(Z_i ne Y_i).$$
Applying your relaxation of Marton's inequality twice yields
$$d_H(A,B) le sqrt{frac{n}{2} D(Q_A|P)} + sqrt{frac{n}{2} D(Q_B|P)}.$$
If $Q_A(E) = P(E cap A) / P(A)$ then
$$D(Q_A | P) = underset{X sim Q_A}{E} log frac{Q_A(X)}{P(X)} = log frac{1}{P(A)}.$$
Define $Q_B$ similarly.
answered Dec 23 '18 at 21:34
angryavianangryavian
41.5k23381
$endgroup$
$begingroup$
Thanks, this made sense and answered my question.
$endgroup$
– Drew Brady
Dec 24 '18 at 15:36
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f3050640%2fhelp-on-application-of-martons-transportation-method-bucheron-lugosi-massart%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
When applying Marton's inequality you have not mentioned how to link $d_H(A,B)$ to $min sum_i P(X_i ne Y_i)$. In particular, $X$ must come from the $P$-measure and $Y$ must come from the $Q$-measure (or vice versa).
It seems we can WLOG assume $A$ and $B$ have positive $P$-measure, else the right-hand side is undefined.
Let $Z sim P$. Let $X sim Q_A$ and $Y sim Q_B$ where $Q_A$ and $Q_B$ are supported on $A cap text{support}(P)$ and $B cap text{support}(P)$ respectively.
The following inequalities hold almost surely.
$$min_{x in A, y in B} sum_{i=1}^n 1_{x_i ne y_i}
le min_{x in A, y in B} left(sum_{i=1}^n 1_{x_i ne Z_i} + sum_{i=1}^n 1_{Z_i ne y_i}right)
le sum_{i=1}^n 1_{X_i ne Z_i} + sum_{i=1}^n 1_{Z_i ne Y_i}.$$
Taking expectations of both sides yields
$$d_H(A,B) le sum_{i=1}^n P(Z_i ne X_i) + sum_{i=1}^n P(Z_i ne Y_i).$$
Applying your relaxation of Marton's inequality twice yields
$$d_H(A,B) le sqrt{frac{n}{2} D(Q_A|P)} + sqrt{frac{n}{2} D(Q_B|P)}.$$
If $Q_A(E) = P(E cap A) / P(A)$ then
$$D(Q_A | P) = underset{X sim Q_A}{E} log frac{Q_A(X)}{P(X)} = log frac{1}{P(A)}.$$
Define $Q_B$ similarly.
answered Dec 23 '18 at 21:34
angryavianangryavian
41.5k23381
$endgroup$
$begingroup$
Thanks, this made sense and answered my question.
$endgroup$
– Drew Brady
Dec 24 '18 at 15:36
add a comment |
$begingroup$
When applying Marton's inequality you have not mentioned how to link $d_H(A,B)$ to $min sum_i P(X_i ne Y_i)$. In particular, $X$ must come from the $P$-measure and $Y$ must come from the $Q$-measure (or vice versa).
It seems we can WLOG assume $A$ and $B$ have positive $P$-measure, else the right-hand side is undefined.
Let $Z sim P$. Let $X sim Q_A$ and $Y sim Q_B$ where $Q_A$ and $Q_B$ are supported on $A cap text{support}(P)$ and $B cap text{support}(P)$ respectively.
The following inequalities hold almost surely.
$$min_{x in A, y in B} sum_{i=1}^n 1_{x_i ne y_i}
le min_{x in A, y in B} left(sum_{i=1}^n 1_{x_i ne Z_i} + sum_{i=1}^n 1_{Z_i ne y_i}right)
le sum_{i=1}^n 1_{X_i ne Z_i} + sum_{i=1}^n 1_{Z_i ne Y_i}.$$
Taking expectations of both sides yields
$$d_H(A,B) le sum_{i=1}^n P(Z_i ne X_i) + sum_{i=1}^n P(Z_i ne Y_i).$$
Applying your relaxation of Marton's inequality twice yields
$$d_H(A,B) le sqrt{frac{n}{2} D(Q_A|P)} + sqrt{frac{n}{2} D(Q_B|P)}.$$
If $Q_A(E) = P(E cap A) / P(A)$ then
$$D(Q_A | P) = underset{X sim Q_A}{E} log frac{Q_A(X)}{P(X)} = log frac{1}{P(A)}.$$
Define $Q_B$ similarly.
answered Dec 23 '18 at 21:34
angryavianangryavian
41.5k23381
$endgroup$
$begingroup$
Thanks, this made sense and answered my question.
$endgroup$
– Drew Brady
Dec 24 '18 at 15:36
add a comment |
$begingroup$
When applying Marton's inequality you have not mentioned how to link $d_H(A,B)$ to $min sum_i P(X_i ne Y_i)$. In particular, $X$ must come from the $P$-measure and $Y$ must come from the $Q$-measure (or vice versa).
It seems we can WLOG assume $A$ and $B$ have positive $P$-measure, else the right-hand side is undefined.
Let $Z sim P$. Let $X sim Q_A$ and $Y sim Q_B$ where $Q_A$ and $Q_B$ are supported on $A cap text{support}(P)$ and $B cap text{support}(P)$ respectively.
The following inequalities hold almost surely.
$$min_{x in A, y in B} sum_{i=1}^n 1_{x_i ne y_i}
le min_{x in A, y in B} left(sum_{i=1}^n 1_{x_i ne Z_i} + sum_{i=1}^n 1_{Z_i ne y_i}right)
le sum_{i=1}^n 1_{X_i ne Z_i} + sum_{i=1}^n 1_{Z_i ne Y_i}.$$
Taking expectations of both sides yields
$$d_H(A,B) le sum_{i=1}^n P(Z_i ne X_i) + sum_{i=1}^n P(Z_i ne Y_i).$$
Applying your relaxation of Marton's inequality twice yields
$$d_H(A,B) le sqrt{frac{n}{2} D(Q_A|P)} + sqrt{frac{n}{2} D(Q_B|P)}.$$
If $Q_A(E) = P(E cap A) / P(A)$ then
$$D(Q_A | P) = underset{X sim Q_A}{E} log frac{Q_A(X)}{P(X)} = log frac{1}{P(A)}.$$
Define $Q_B$ similarly.
answered Dec 23 '18 at 21:34
angryavianangryavian
41.5k23381
$endgroup$
When applying Marton's inequality you have not mentioned how to link $d_H(A,B)$ to $min sum_i P(X_i ne Y_i)$. In particular, $X$ must come from the $P$-measure and $Y$ must come from the $Q$-measure (or vice versa).
It seems we can WLOG assume $A$ and $B$ have positive $P$-measure, else the right-hand side is undefined.
Let $Z sim P$. Let $X sim Q_A$ and $Y sim Q_B$ where $Q_A$ and $Q_B$ are supported on $A cap text{support}(P)$ and $B cap text{support}(P)$ respectively.
The following inequalities hold almost surely.
$$min_{x in A, y in B} sum_{i=1}^n 1_{x_i ne y_i}
le min_{x in A, y in B} left(sum_{i=1}^n 1_{x_i ne Z_i} + sum_{i=1}^n 1_{Z_i ne y_i}right)
le sum_{i=1}^n 1_{X_i ne Z_i} + sum_{i=1}^n 1_{Z_i ne Y_i}.$$
Taking expectations of both sides yields
$$d_H(A,B) le sum_{i=1}^n P(Z_i ne X_i) + sum_{i=1}^n P(Z_i ne Y_i).$$
Applying your relaxation of Marton's inequality twice yields
$$d_H(A,B) le sqrt{frac{n}{2} D(Q_A|P)} + sqrt{frac{n}{2} D(Q_B|P)}.$$
If $Q_A(E) = P(E cap A) / P(A)$ then
$$D(Q_A | P) = underset{X sim Q_A}{E} log frac{Q_A(X)}{P(X)} = log frac{1}{P(A)}.$$
Define $Q_B$ similarly.
answered Dec 23 '18 at 21:34
angryavianangryavian
41.5k23381
edited Dec 23 '18 at 21:44
answered Dec 23 '18 at 21:34
angryavianangryavian
41.5k23381
answered Dec 23 '18 at 21:34
angryavianangryavian
41.5k23381
answered Dec 23 '18 at 21:34
angryavianangryavian
41.5k23381
41.5k23381
$begingroup$
Thanks, this made sense and answered my question.
$endgroup$
– Drew Brady
Dec 24 '18 at 15:36
add a comment |
$begingroup$
Thanks, this made sense and answered my question.
$endgroup$
– Drew Brady
Dec 24 '18 at 15:36
$begingroup$
Thanks, this made sense and answered my question.
$endgroup$
– Drew Brady
Dec 24 '18 at 15:36
$begingroup$
Thanks, this made sense and answered my question.
$endgroup$
– Drew Brady
Dec 24 '18 at 15:36
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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%2f3050640%2fhelp-on-application-of-martons-transportation-method-bucheron-lugosi-massart%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
