Mirror descent on a 1-ball
I have been recently reading about mirror descent, which essentially generalizes gradient descent to non-Euclidean spaces.
Nearly every reference I find on this subject gives the same example for when mirror descent is better than gradient descent. Specifically, assume your objective function $f$ is such that $|f|_infty leq 1$, and assume the feasible set is the unit simplex in $mathbb{R}^n$. Then by choosing the Bregman divergence to be the KL divergence, gradient descent converges like $n/sqrt{T}$ whereas mirror descent converges like $log(n)/sqrt{T}$. In the mirror descent algorithm, the Bregman projection onto the simplex is simply a rescaling $x mapsto x / | x|_1$. The mirror descent algorithm is equivalent to "exponentiated gradient descent".
What is frustrating me is that I am struggling to find many other examples in the literature. In particular, I'm interested in the setting where the feasible set is not an $n$-dimensional simplex, but rather is the unit ball with respect to the $1$-norm, $B_{1,n}$. It seems that with this feasible set, the KL divergence is no longer appropriate. I am interested in...
(1) Is there an appropriate Bregman divergence (and associated generating function) for this $B_{1,n}$ setup?
(2) If so, is the Bregman projection efficiently computable, as in the case of the simplex setup?
Any references would be much appreciated. I have failed to find this question addressed in the literature, but I feel it must be there somewhere.
optimization convex-optimization machine-learning gradient-descent
asked Dec 7 at 14:52
M. Eieals
61
add a comment |
I have been recently reading about mirror descent, which essentially generalizes gradient descent to non-Euclidean spaces.
Nearly every reference I find on this subject gives the same example for when mirror descent is better than gradient descent. Specifically, assume your objective function $f$ is such that $|f|_infty leq 1$, and assume the feasible set is the unit simplex in $mathbb{R}^n$. Then by choosing the Bregman divergence to be the KL divergence, gradient descent converges like $n/sqrt{T}$ whereas mirror descent converges like $log(n)/sqrt{T}$. In the mirror descent algorithm, the Bregman projection onto the simplex is simply a rescaling $x mapsto x / | x|_1$. The mirror descent algorithm is equivalent to "exponentiated gradient descent".
What is frustrating me is that I am struggling to find many other examples in the literature. In particular, I'm interested in the setting where the feasible set is not an $n$-dimensional simplex, but rather is the unit ball with respect to the $1$-norm, $B_{1,n}$. It seems that with this feasible set, the KL divergence is no longer appropriate. I am interested in...
(1) Is there an appropriate Bregman divergence (and associated generating function) for this $B_{1,n}$ setup?
(2) If so, is the Bregman projection efficiently computable, as in the case of the simplex setup?
Any references would be much appreciated. I have failed to find this question addressed in the literature, but I feel it must be there somewhere.
optimization convex-optimization machine-learning gradient-descent
asked Dec 7 at 14:52
M. Eieals
61
add a comment |
I have been recently reading about mirror descent, which essentially generalizes gradient descent to non-Euclidean spaces.
Nearly every reference I find on this subject gives the same example for when mirror descent is better than gradient descent. Specifically, assume your objective function $f$ is such that $|f|_infty leq 1$, and assume the feasible set is the unit simplex in $mathbb{R}^n$. Then by choosing the Bregman divergence to be the KL divergence, gradient descent converges like $n/sqrt{T}$ whereas mirror descent converges like $log(n)/sqrt{T}$. In the mirror descent algorithm, the Bregman projection onto the simplex is simply a rescaling $x mapsto x / | x|_1$. The mirror descent algorithm is equivalent to "exponentiated gradient descent".
What is frustrating me is that I am struggling to find many other examples in the literature. In particular, I'm interested in the setting where the feasible set is not an $n$-dimensional simplex, but rather is the unit ball with respect to the $1$-norm, $B_{1,n}$. It seems that with this feasible set, the KL divergence is no longer appropriate. I am interested in...
(1) Is there an appropriate Bregman divergence (and associated generating function) for this $B_{1,n}$ setup?
(2) If so, is the Bregman projection efficiently computable, as in the case of the simplex setup?
Any references would be much appreciated. I have failed to find this question addressed in the literature, but I feel it must be there somewhere.
optimization convex-optimization machine-learning gradient-descent
asked Dec 7 at 14:52
M. Eieals
61
I have been recently reading about mirror descent, which essentially generalizes gradient descent to non-Euclidean spaces.
Nearly every reference I find on this subject gives the same example for when mirror descent is better than gradient descent. Specifically, assume your objective function $f$ is such that $|f|_infty leq 1$, and assume the feasible set is the unit simplex in $mathbb{R}^n$. Then by choosing the Bregman divergence to be the KL divergence, gradient descent converges like $n/sqrt{T}$ whereas mirror descent converges like $log(n)/sqrt{T}$. In the mirror descent algorithm, the Bregman projection onto the simplex is simply a rescaling $x mapsto x / | x|_1$. The mirror descent algorithm is equivalent to "exponentiated gradient descent".
What is frustrating me is that I am struggling to find many other examples in the literature. In particular, I'm interested in the setting where the feasible set is not an $n$-dimensional simplex, but rather is the unit ball with respect to the $1$-norm, $B_{1,n}$. It seems that with this feasible set, the KL divergence is no longer appropriate. I am interested in...
(1) Is there an appropriate Bregman divergence (and associated generating function) for this $B_{1,n}$ setup?
(2) If so, is the Bregman projection efficiently computable, as in the case of the simplex setup?
Any references would be much appreciated. I have failed to find this question addressed in the literature, but I feel it must be there somewhere.
optimization convex-optimization machine-learning gradient-descent
optimization convex-optimization machine-learning gradient-descent
asked Dec 7 at 14:52
M. Eieals
61
asked Dec 7 at 14:52
M. Eieals
61
asked Dec 7 at 14:52
M. Eieals
61
asked Dec 7 at 14:52
M. Eieals
61
asked Dec 7 at 14:52
M. Eieals
61
61
add a comment |
add a comment |
active
oldest
votes
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%2f3029978%2fmirror-descent-on-a-1-ball%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3029978%2fmirror-descent-on-a-1-ball%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
