Convergence rate of Gradient Descent
$begingroup$
I was trying to solve a simple gradient descent problem. If we have $f(x) = x^2$, and a learning rate, $eta$, that guarantees that the algorithm converges, then in how many steps will my algorithm be $epsilon$ away from the minimum (which is $0$), i.e. how many steps are required to get $vert x_i - x_{min} vert < epsilon $ which is basically $vert x_i vert < epsilon$.
My first approach was to try break down $x_i$ and reformulate it in terms of $x_0$, because it the answer will obviously depend on my starting point, but I got somewhere a bit lost there. Does anyone have a hint to share?
Thank you!
optimization convex-optimization gradient-descent
asked Dec 19 '18 at 17:39
stellarhawk 34stellarhawk 34
2726
$endgroup$
add a comment |
$begingroup$
I was trying to solve a simple gradient descent problem. If we have $f(x) = x^2$, and a learning rate, $eta$, that guarantees that the algorithm converges, then in how many steps will my algorithm be $epsilon$ away from the minimum (which is $0$), i.e. how many steps are required to get $vert x_i - x_{min} vert < epsilon $ which is basically $vert x_i vert < epsilon$.
My first approach was to try break down $x_i$ and reformulate it in terms of $x_0$, because it the answer will obviously depend on my starting point, but I got somewhere a bit lost there. Does anyone have a hint to share?
Thank you!
optimization convex-optimization gradient-descent
asked Dec 19 '18 at 17:39
stellarhawk 34stellarhawk 34
2726
$endgroup$
add a comment |
$begingroup$
I was trying to solve a simple gradient descent problem. If we have $f(x) = x^2$, and a learning rate, $eta$, that guarantees that the algorithm converges, then in how many steps will my algorithm be $epsilon$ away from the minimum (which is $0$), i.e. how many steps are required to get $vert x_i - x_{min} vert < epsilon $ which is basically $vert x_i vert < epsilon$.
My first approach was to try break down $x_i$ and reformulate it in terms of $x_0$, because it the answer will obviously depend on my starting point, but I got somewhere a bit lost there. Does anyone have a hint to share?
Thank you!
optimization convex-optimization gradient-descent
asked Dec 19 '18 at 17:39
stellarhawk 34stellarhawk 34
2726
$endgroup$
I was trying to solve a simple gradient descent problem. If we have $f(x) = x^2$, and a learning rate, $eta$, that guarantees that the algorithm converges, then in how many steps will my algorithm be $epsilon$ away from the minimum (which is $0$), i.e. how many steps are required to get $vert x_i - x_{min} vert < epsilon $ which is basically $vert x_i vert < epsilon$.
My first approach was to try break down $x_i$ and reformulate it in terms of $x_0$, because it the answer will obviously depend on my starting point, but I got somewhere a bit lost there. Does anyone have a hint to share?
Thank you!
optimization convex-optimization gradient-descent
optimization convex-optimization gradient-descent
asked Dec 19 '18 at 17:39
stellarhawk 34stellarhawk 34
2726
asked Dec 19 '18 at 17:39
stellarhawk 34stellarhawk 34
2726
asked Dec 19 '18 at 17:39
stellarhawk 34stellarhawk 34
2726
asked Dec 19 '18 at 17:39
stellarhawk 34stellarhawk 34
2726
asked Dec 19 '18 at 17:39
stellarhawk 34stellarhawk 34
2726
2726
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
For this simple problem, argue that the gradient descent update is $x_t = (1-2eta) x_{t-1}$. Then, argue that
$$
x_t = (1-2eta)^t x_0.
$$
Then, see if this sequence converges for all $eta$ or if you need some condition on $eta$ for that to happen.
answered Dec 19 '18 at 17:56
passerby51passerby51
2,076918
$endgroup$
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%2f3046660%2fconvergence-rate-of-gradient-descent%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$
For this simple problem, argue that the gradient descent update is $x_t = (1-2eta) x_{t-1}$. Then, argue that
$$
x_t = (1-2eta)^t x_0.
$$
Then, see if this sequence converges for all $eta$ or if you need some condition on $eta$ for that to happen.
answered Dec 19 '18 at 17:56
passerby51passerby51
2,076918
$endgroup$
add a comment |
$begingroup$
For this simple problem, argue that the gradient descent update is $x_t = (1-2eta) x_{t-1}$. Then, argue that
$$
x_t = (1-2eta)^t x_0.
$$
Then, see if this sequence converges for all $eta$ or if you need some condition on $eta$ for that to happen.
answered Dec 19 '18 at 17:56
passerby51passerby51
2,076918
$endgroup$
add a comment |
$begingroup$
For this simple problem, argue that the gradient descent update is $x_t = (1-2eta) x_{t-1}$. Then, argue that
$$
x_t = (1-2eta)^t x_0.
$$
Then, see if this sequence converges for all $eta$ or if you need some condition on $eta$ for that to happen.
answered Dec 19 '18 at 17:56
passerby51passerby51
2,076918
$endgroup$
For this simple problem, argue that the gradient descent update is $x_t = (1-2eta) x_{t-1}$. Then, argue that
$$
x_t = (1-2eta)^t x_0.
$$
Then, see if this sequence converges for all $eta$ or if you need some condition on $eta$ for that to happen.
answered Dec 19 '18 at 17:56
passerby51passerby51
2,076918
answered Dec 19 '18 at 17:56
passerby51passerby51
2,076918
answered Dec 19 '18 at 17:56
passerby51passerby51
2,076918
answered Dec 19 '18 at 17:56
passerby51passerby51
2,076918
2,076918
add a comment |
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%2f3046660%2fconvergence-rate-of-gradient-descent%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
