On uniform boundedness of the GD algorithm

  • #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$.
 

Answers and Replies

  • #2
14,163
11,464
Do you have a reference where people can look up the algorithm in order to understand your question?
 
  • #3
WWGD
Science Advisor
Gold Member
5,419
3,675
What is ##A## here, a matrix?
 

Related Threads on On uniform boundedness of the GD algorithm

Replies
1
Views
1K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
6
Views
8K
  • Last Post
Replies
10
Views
2K
Replies
8
Views
3K
Replies
6
Views
2K
Replies
2
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
2K
Top