Facebook Page
Twitter
RSS
Thanks Thanks:  0
+ Reply to Thread
Results 1 to 1 of 1
  1. MHB Apprentice

    Status
    Offline
    Join Date
    Jun 2018
    Posts
    4
    Thanks
    1 time
    Thanked
    0 times
    #1
    Consider a function $f\in\mathcal{C}^2$ with Lipschitz continuous gradient (with constant $L$)- we also assume the function is lowerbounded and has at least one minimum. Let $\{x^k\}_k$ be the sequence generated by Gradient Descent algorithm with initial point $x^0$ and step-size $0<\alpha<2/L$:
    \begin{equation}
    x^{k+1}=x^k-\alpha\nabla f (x^k).
    \end{equation}
    We know that the sequence will converge to a critical point.

    Now consider the new function $\tilde{f}(x)=f(x)+x'Ax$ with some $A\succeq\mathbf{0}$. Let $\{\tilde{x}^k\}_k$ be the sequence generated by Gradient Descent algorithm with **the same** initial point $\tilde{x}^0=x^0$ and step-size $0<\alpha<2/L$:
    \begin{equation}
    \tilde{x}^{k+1}=\tilde{x}^k-\alpha\nabla \tilde{f} (\tilde{x}^k).
    \end{equation}

    **Can we prove that $\mathrm{dist}\left(\{\tilde{x}^k\}_k,\{{x}^k\}_k\right)$ is uniformly bounded, independent of $A$ and step-size $\alpha$?**

    I tried to prove it by assuming existence of a compact sublevel set $\mathcal{L}=\{x:f(x)\leq f(x^0)\}$ and using the fact that Gradient Descent generates a decreasing sequence of objective values (implying that the sequence remains in the compact sublevel set). However I cannot prove existence of a set independent of both $A$ and $\alpha$.

  2. # ADS
    Circuit advertisement
    Join Date
    Always
    Posts
    Many
     

Similar Threads

  1. Descent gradient method
    By JS10 in forum Analysis
    Replies: 0
    Last Post: May 1st, 2019, 19:06
  2. How to modify Adaline Stochastic gradient descent
    By vokoyo in forum Computer Science
    Replies: 1
    Last Post: March 14th, 2019, 22:32
  3. Linear Regression: Feature Normalization/Scaling in Gradient Descent: Prediction Step
    By Ackbach in forum Advanced Probability and Statistics
    Replies: 2
    Last Post: June 22nd, 2017, 11:58
  4. [SOLVED] Gradient and scalar function question
    By dwsmith in forum Advanced Applied Mathematics
    Replies: 0
    Last Post: September 6th, 2013, 19:35
  5. Replies: 1
    Last Post: March 3rd, 2013, 23:26

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards