Why is the Frank-Wolfe algorithm projection-free while gradient descent isn't?
up vote
1
down vote
favorite
While reading this article about the Frank-Wolfe algorithm, I did not understand why the Frank-Wolfe algorithm is projection-free, while the gradient descent is not.
I think the problem is, that I do not understand what it means for an operation to be projection free.
Within linear algebra, I understand that a transformation is a projection if it is idempotent.
I also understand that it is good to have projection-free algorithms (it makes it possible to reduce the complexity) - but I do not know why this is the case. Is it because the Frank-Wolfe uses a linear optimization oracle?
So my question is this: When is an operation projection-free, and why can the complexity of projection-free algorithms be reduced?
algorithms computational-complexity machine-learning gradient-descent projection
asked Nov 29 at 4:02
Allan Erlang Videbæk
64
add a comment |
up vote
1
down vote
favorite
While reading this article about the Frank-Wolfe algorithm, I did not understand why the Frank-Wolfe algorithm is projection-free, while the gradient descent is not.
I think the problem is, that I do not understand what it means for an operation to be projection free.
Within linear algebra, I understand that a transformation is a projection if it is idempotent.
I also understand that it is good to have projection-free algorithms (it makes it possible to reduce the complexity) - but I do not know why this is the case. Is it because the Frank-Wolfe uses a linear optimization oracle?
So my question is this: When is an operation projection-free, and why can the complexity of projection-free algorithms be reduced?
algorithms computational-complexity machine-learning gradient-descent projection
asked Nov 29 at 4:02
Allan Erlang Videbæk
64
Look here: arxiv.org/abs/1206.4657. Especially section 1.1. Projection works by ensuring that when we do our gradient descent or local search we keep in the feasible region. In section 1.1, we see cases where this project is very hard. Projection-free implementation, according to this paper at least, uses solves this using one linear optimization over the convex domain in Thm 1.1.
– twnly
Nov 29 at 7:23
Thank you, the article really helped!
– Allan Erlang Videbæk
Dec 1 at 1:00
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
While reading this article about the Frank-Wolfe algorithm, I did not understand why the Frank-Wolfe algorithm is projection-free, while the gradient descent is not.
I think the problem is, that I do not understand what it means for an operation to be projection free.
Within linear algebra, I understand that a transformation is a projection if it is idempotent.
I also understand that it is good to have projection-free algorithms (it makes it possible to reduce the complexity) - but I do not know why this is the case. Is it because the Frank-Wolfe uses a linear optimization oracle?
So my question is this: When is an operation projection-free, and why can the complexity of projection-free algorithms be reduced?
algorithms computational-complexity machine-learning gradient-descent projection
asked Nov 29 at 4:02
Allan Erlang Videbæk
64
While reading this article about the Frank-Wolfe algorithm, I did not understand why the Frank-Wolfe algorithm is projection-free, while the gradient descent is not.
I think the problem is, that I do not understand what it means for an operation to be projection free.
Within linear algebra, I understand that a transformation is a projection if it is idempotent.
I also understand that it is good to have projection-free algorithms (it makes it possible to reduce the complexity) - but I do not know why this is the case. Is it because the Frank-Wolfe uses a linear optimization oracle?
So my question is this: When is an operation projection-free, and why can the complexity of projection-free algorithms be reduced?
algorithms computational-complexity machine-learning gradient-descent projection
algorithms computational-complexity machine-learning gradient-descent projection
asked Nov 29 at 4:02
Allan Erlang Videbæk
64
asked Nov 29 at 4:02
Allan Erlang Videbæk
64
edited Nov 29 at 4:42
asked Nov 29 at 4:02
Allan Erlang Videbæk
64
asked Nov 29 at 4:02
Allan Erlang Videbæk
64
asked Nov 29 at 4:02
Allan Erlang Videbæk
64
64
Look here: arxiv.org/abs/1206.4657. Especially section 1.1. Projection works by ensuring that when we do our gradient descent or local search we keep in the feasible region. In section 1.1, we see cases where this project is very hard. Projection-free implementation, according to this paper at least, uses solves this using one linear optimization over the convex domain in Thm 1.1.
– twnly
Nov 29 at 7:23
Thank you, the article really helped!
– Allan Erlang Videbæk
Dec 1 at 1:00
add a comment |
Look here: arxiv.org/abs/1206.4657. Especially section 1.1. Projection works by ensuring that when we do our gradient descent or local search we keep in the feasible region. In section 1.1, we see cases where this project is very hard. Projection-free implementation, according to this paper at least, uses solves this using one linear optimization over the convex domain in Thm 1.1.
– twnly
Nov 29 at 7:23
Thank you, the article really helped!
– Allan Erlang Videbæk
Dec 1 at 1:00
Look here: arxiv.org/abs/1206.4657. Especially section 1.1. Projection works by ensuring that when we do our gradient descent or local search we keep in the feasible region. In section 1.1, we see cases where this project is very hard. Projection-free implementation, according to this paper at least, uses solves this using one linear optimization over the convex domain in Thm 1.1.
– twnly
Nov 29 at 7:23
Look here: arxiv.org/abs/1206.4657. Especially section 1.1. Projection works by ensuring that when we do our gradient descent or local search we keep in the feasible region. In section 1.1, we see cases where this project is very hard. Projection-free implementation, according to this paper at least, uses solves this using one linear optimization over the convex domain in Thm 1.1.
– twnly
Nov 29 at 7:23
Thank you, the article really helped!
– Allan Erlang Videbæk
Dec 1 at 1:00
Thank you, the article really helped!
– Allan Erlang Videbæk
Dec 1 at 1:00
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%2f3018157%2fwhy-is-the-frank-wolfe-algorithm-projection-free-while-gradient-descent-isnt%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%2f3018157%2fwhy-is-the-frank-wolfe-algorithm-projection-free-while-gradient-descent-isnt%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
Look here: arxiv.org/abs/1206.4657. Especially section 1.1. Projection works by ensuring that when we do our gradient descent or local search we keep in the feasible region. In section 1.1, we see cases where this project is very hard. Projection-free implementation, according to this paper at least, uses solves this using one linear optimization over the convex domain in Thm 1.1.
– twnly
Nov 29 at 7:23
Thank you, the article really helped!
– Allan Erlang Videbæk
Dec 1 at 1:00