Prerequisites Lipschitz Continuity A function f : R n → R m f: \mathbb{R}^n \rightarrow \mathbb{R}^m f : R n → R m L L L ∃ L > 0 \exists L > 0 ∃ L > 0 ∀ x , y ∈ R n \forall x, y \in \mathbb{R}^n ∀ x , y ∈ R n
∥ f ( x ) − f ( y ) ∥ ≤ L ∥ x − y ∥ \|f(x) - f(y)\| \le L \|x - y\| ∥ f ( x ) − f ( y ) ∥ ≤ L ∥ x − y ∥ Lipschitz Smoothness Similarly, f : R n → R m f: \mathbb{R}^n \rightarrow \mathbb{R}^m f : R n → R m L L L ∃ L > 0 \exists L > 0 ∃ L > 0 ∀ x , y ∈ R n \forall x, y \in \mathbb{R}^n ∀ x , y ∈ R n
∥ ∇ f ( x ) − ∇ f ( y ) ∥ ≤ L ∥ x − y ∥ \|\nabla f(x) - \nabla f(y)\| \le L \|x - y\| ∥∇ f ( x ) − ∇ f ( y ) ∥ ≤ L ∥ x − y ∥ Convex Function A function f : R n → R f: \mathbb{R}^n \rightarrow \mathbb{R} f : R n → R ∀ x , y ∈ R n \forall x, y \in \mathbb{R}^n ∀ x , y ∈ R n ∀ λ ∈ [ 0 , 1 ] \forall \lambda \in [0, 1] ∀ λ ∈ [ 0 , 1 ]
f ( λ x + ( 1 − λ ) y ) ≤ λ f ( x ) + ( 1 − λ ) f ( y ) ⇔ f ( y ) ≥ f ( x ) + ∇ f ( x ) T ( y − x ) ⇔ ∇ 2 f ( x ) ≽ 0 f(\lambda x + (1 - \lambda) y) \le \lambda f(x) + (1 - \lambda) f(y) \\ \Leftrightarrow f(y) \ge f(x) + \nabla f(x)^T (y - x) \\ \Leftrightarrow \nabla^2 f(x) \succcurlyeq 0 f ( λ x + ( 1 − λ ) y ) ≤ λ f ( x ) + ( 1 − λ ) f ( y ) ⇔ f ( y ) ≥ f ( x ) + ∇ f ( x ) T ( y − x ) ⇔ ∇ 2 f ( x ) ≽ 0 For a matrix A ∈ R n × n A \in \mathbb{R}^{n\times n} A ∈ R n × n ∀ x ∈ R n \forall x \in \mathbb{R}^n ∀ x ∈ R n
If x T A x ≥ 0 x^T A x \ge 0 x T A x ≥ 0 A A A A ≽ 0 A \succcurlyeq 0 A ≽ 0 If x T A x > 0 x^T A x > 0 x T A x > 0 A A A A ≻ 0 A \succ 0 A ≻ 0 From the perspective of eigenvalues, for all eigenvalues λ i , ∀ i = 1 , ⋯ , n \lambda_i, \forall i=1,\cdots,n λ i , ∀ i = 1 , ⋯ , n A A A
A ≽ 0 A \succcurlyeq 0 A ≽ 0 λ i ≥ 0 \lambda_i \ge 0 λ i ≥ 0 A ≻ 0 A \succ 0 A ≻ 0 λ i > 0 \lambda_i > 0 λ i > 0 Strongly Convex Function A function f : R n → R f: \mathbb{R}^n \rightarrow \mathbb{R} f : R n → R ∃ μ > 0 \exists \mu > 0 ∃ μ > 0 ∀ x , y ∈ R n \forall x, y \in \mathbb{R}^n ∀ x , y ∈ R n ∀ λ ∈ [ 0 , 1 ] \forall \lambda \in [0, 1] ∀ λ ∈ [ 0 , 1 ]
f ( λ x + ( 1 − λ ) y ) ≤ λ f ( x ) + ( 1 − λ ) f ( y ) − μ 2 λ ( 1 − λ ) ∥ x − y ∥ 2 ⇔ f ( y ) ≥ f ( x ) + ∇ f ( x ) T ( y − x ) + μ 2 ∥ x − y ∥ 2 ⇔ ∇ 2 f ( x ) ≽ μ I f(\lambda x + (1 - \lambda) y) \le \lambda f(x) + (1 - \lambda) f(y) - \frac{\mu}{2} \lambda (1 - \lambda) \|x - y\|^2 \\ \Leftrightarrow f(y) \ge f(x) + \nabla f(x)^T (y - x) + \frac{\mu}{2} \|x - y\|^2 \\ \Leftrightarrow \nabla^2 f(x) \succcurlyeq \mu I f ( λ x + ( 1 − λ ) y ) ≤ λ f ( x ) + ( 1 − λ ) f ( y ) − 2 μ λ ( 1 − λ ) ∥ x − y ∥ 2 ⇔ f ( y ) ≥ f ( x ) + ∇ f ( x ) T ( y − x ) + 2 μ ∥ x − y ∥ 2 ⇔ ∇ 2 f ( x ) ≽ μ I Gradient Descent Gradient descent is an iterative algorithm. Here we only consider its simplest form, which requires the function f f f
f ( x k + 1 ) ≤ f ( x k ) + ∇ f ( x k ) T ( x k + 1 − x k ) + L 2 ∥ x k + 1 − x k ∥ 2 f(x_{k+1}) \le f(x_k) + \nabla f(x_k)^T (x_{k+1} - x_k) + \frac{L}{2} \|x_{k+1} - x_k\|^2 f ( x k + 1 ) ≤ f ( x k ) + ∇ f ( x k ) T ( x k + 1 − x k ) + 2 L ∥ x k + 1 − x k ∥ 2 Thus, even though f f f f ( x k ) + ∇ f ( x k ) T ( x − x k ) + L 2 ∥ x − x k ∥ 2 f(x_k) + \nabla f(x_k)^T (x - x_k) + \frac{L}{2} \|x - x_k\|^2 f ( x k ) + ∇ f ( x k ) T ( x − x k ) + 2 L ∥ x − x k ∥ 2
q x k ( x ) = f ( x k ) + ∇ f ( x k ) T ( x − x k ) + L 2 ∥ x − x k ∥ 2 ≈ f ( x ) q_{x_k}(x) = f(x_k) + \nabla f(x_k)^T (x - x_k) + \frac{L}{2} \|x - x_k\|^2 \approx f(x) q x k ( x ) = f ( x k ) + ∇ f ( x k ) T ( x − x k ) + 2 L ∥ x − x k ∥ 2 ≈ f ( x ) To minimize the quadratic function q x k ( x ) q_{x_k}(x) q x k ( x )
∇ q x k ( x ) = ∇ f ( x k ) + L ( x − x k ) = ! 0 ⇒ x k + 1 = x = x k − 1 L ∇ f ( x k ) \nabla q_{x_k}(x) = \nabla f(x_k) + L (x - x_k) \xlongequal{!} 0 \\ \Rightarrow x_{k+1} = x = x_k - \frac{1}{L} \nabla f(x_k) ∇ q x k ( x ) = ∇ f ( x k ) + L ( x − x k ) ! 0 ⇒ x k + 1 = x = x k − L 1 ∇ f ( x k ) Here, − ∇ f ( x k ) -\nabla f(x_k) − ∇ f ( x k ) 1 L \frac{1}{L} L 1 α \alpha α
f ( x k + 1 ) ≤ f ( x k ) + ∇ f ( x k ) T ( x k + 1 − x k ) + L 2 ∥ x k + 1 − x k ∥ 2 = f ( x k ) − 1 L ∥ ∇ f ( x k ) ∥ 2 + 1 2 L ∥ ∇ f ( x k ) ∥ 2 = f ( x k ) − 1 2 L ∥ ∇ f ( x k ) ∥ 2 \begin{align*} f(x_{k+1}) \le & f(x_k) + \nabla f(x_k)^T (x_{k+1} - x_k) + \frac{L}{2} \|x_{k+1} - x_k\|^2 \\ = & f(x_k) - \frac{1}{L} \|\nabla f(x_k)\|^2 + \frac{1}{2L} \|\nabla f(x_k)\|^2 \\ = & f(x_k) - \frac{1}{2L} \|\nabla f(x_k)\|^2 \end{align*} f ( x k + 1 ) ≤ = = f ( x k ) + ∇ f ( x k ) T ( x k + 1 − x k ) + 2 L ∥ x k + 1 − x k ∥ 2 f ( x k ) − L 1 ∥∇ f ( x k ) ∥ 2 + 2 L 1 ∥∇ f ( x k ) ∥ 2 f ( x k ) − 2 L 1 ∥∇ f ( x k ) ∥ 2 Newton's Method
Besides gradient descent, we can also use Newton’s method for optimization. To solve h ( x ) = 0 h(x)=0 h ( x ) = 0 g ( x ) = x − α h ( x ) g(x)=x-\alpha h(x) g ( x ) = x − α h ( x ) α > 0 \alpha>0 α > 0
x k + 1 = g ( x k ) x_{k+1} = g(x_k) x k + 1 = g ( x k ) When the iteration converges, we have
x ∗ = g ( x ∗ ) = x ∗ − α h ( x ∗ ) ⇒ h ( x ∗ ) = 0 x_* = g(x_*) = x_* - \alpha h(x_*) \\ \Rightarrow h(x_*) = 0 x ∗ = g ( x ∗ ) = x ∗ − α h ( x ∗ ) ⇒ h ( x ∗ ) = 0 Convergence Criteria Assume that x ∗ ∈ Ω x_*\in\Omega x ∗ ∈ Ω f f f f ( x ∗ ) = f ∗ f(x_*) = f_* f ( x ∗ ) = f ∗ ∀ ε > 0 \forall\varepsilon > 0 ∀ ε > 0
If f ( x ) − f ∗ ≤ ε f(x)-f_* \le\varepsilon f ( x ) − f ∗ ≤ ε x x x ε \varepsilon ε If ∥ ∇ f ( x ) ∥ ≤ ε \|\nabla f(x)\| \le\varepsilon ∥∇ f ( x ) ∥ ≤ ε x x x ε \varepsilon ε Convergence Analysis In the previous derivation, we obtained the step size α = 1 L \alpha = \frac{1}{L} α = L 1
Lipschitz Smooth Functions For a Lipschitz smooth function f f f
f ( x + α d ) ≤ f ( x ) + α ∇ f ( x ) T d + L 2 α 2 ∥ d ∥ 2 ⇒ f ( x k + 1 ) ≤ f ( x k ) − 1 2 L ∥ ∇ f ( x k ) ∥ 2 ⇒ f ( x T ) ≤ f ( x 0 ) − 1 2 L ∑ k = 0 T − 1 ∥ ∇ f ( x k ) ∥ 2 ⇒ ∑ k = 0 T − 1 ∥ ∇ f ( x k ) ∥ 2 ≤ 2 L ( f ( x 0 ) − f ( x T ) ) ≤ 2 L ( f ( x 0 ) − f ∗ ) ⇒ min 0 ≤ k ≤ T − 1 ∥ ∇ f ( x k ) ∥ 2 ≤ 2 L T ( f ( x 0 ) − f ∗ ) ⇒ min 0 ≤ k ≤ T − 1 ∥ ∇ f ( x k ) ∥ ≤ 2 L T ( f ( x 0 ) − f ∗ ) \begin{align*} f(x+\alpha d) \le & f(x) + \alpha\nabla f(x)^Td + \frac{L}{2}\alpha^2\|d\|^2 \\ \Rightarrow f(x_{k+1}) \le & f(x_k) - \frac{1}{2L}\|\nabla f(x_k)\|^2 \\ \Rightarrow f(x_T) \le & f(x_0) - \frac{1}{2L}\sum_{k=0}^{T-1}\|\nabla f(x_k)\|^2 \\ \Rightarrow \sum_{k=0}^{T-1}\|\nabla f(x_k)\|^2 \le & 2L\left(f(x_0) - f(x_T)\right) \\ \le & 2L\left(f(x_0) - f_*\right) \\ \Rightarrow \min_{0\le k\le T-1}\|\nabla f(x_k)\|^2 \le & \frac{2L}{T}\left(f(x_0) - f_*\right) \\ \Rightarrow \min_{0\le k\le T-1}\|\nabla f(x_k)\| \le & \sqrt{\frac{2L}{T}\left(f(x_0) - f_*\right)} \end{align*} f ( x + α d ) ≤ ⇒ f ( x k + 1 ) ≤ ⇒ f ( x T ) ≤ ⇒ k = 0 ∑ T − 1 ∥∇ f ( x k ) ∥ 2 ≤ ≤ ⇒ 0 ≤ k ≤ T − 1 min ∥∇ f ( x k ) ∥ 2 ≤ ⇒ 0 ≤ k ≤ T − 1 min ∥∇ f ( x k ) ∥ ≤ f ( x ) + α ∇ f ( x ) T d + 2 L α 2 ∥ d ∥ 2 f ( x k ) − 2 L 1 ∥∇ f ( x k ) ∥ 2 f ( x 0 ) − 2 L 1 k = 0 ∑ T − 1 ∥∇ f ( x k ) ∥ 2 2 L ( f ( x 0 ) − f ( x T ) ) 2 L ( f ( x 0 ) − f ∗ ) T 2 L ( f ( x 0 ) − f ∗ ) T 2 L ( f ( x 0 ) − f ∗ ) Thus, to achieve an ε \varepsilon ε
2 L T ( f ( x 0 ) − f ∗ ) ≤ ε ⇒ T ≥ 2 L ε 2 ( f ( x 0 ) − f ∗ ) \begin{align*} \sqrt{\frac{2L}{T}\left(f(x_0) - f_*\right)} \le & \varepsilon \\ \Rightarrow T \ge & \frac{2L}{\varepsilon^2}\left(f(x_0) - f_*\right) \end{align*} T 2 L ( f ( x 0 ) − f ∗ ) ≤ ⇒ T ≥ ε ε 2 2 L ( f ( x 0 ) − f ∗ ) Therefore, the required time complexity is O ( 1 ε 2 ) O\left(\frac{1}{\varepsilon^2}\right) O ( ε 2 1 )
For a sequence { a n } \{a_n\} { a n } lim n → ∞ a n → 0 \lim_{n\to\infty}a_n\to0 lim n → ∞ a n → 0
lim n → ∞ a n + 1 a n = ρ \lim_{n\to\infty}\frac{a_{n+1}}{a_n} = \rho n → ∞ lim a n a n + 1 = ρ If ρ = 0 \rho=0 ρ = 0 { a n } \{a_n\} { a n } If ρ ∈ ( 0 , 1 ) \rho\in(0,1) ρ ∈ ( 0 , 1 ) { a n } \{a_n\} { a n } If ρ = 1 \rho=1 ρ = 1 { a n } \{a_n\} { a n } Lipschitz Smooth + Convex Function For a convex function f f f
f ( y ) ≥ f ( x ) + ∇ f ( x ) T ( y − x ) Let { y = x ∗ x = x k ⇒ f ∗ ≥ f ( x k ) + ∇ f ( x k ) T ( x ∗ − x k ) ⇒ f ( x k ) ≤ f ∗ + ∇ f ( x k ) T ( x k − x ∗ ) \begin{align*} f(y) \ge & f(x) + \nabla f(x)^T(y - x) \\ \text{Let} \begin{cases} y=x_*\\ x=x_k \end{cases} \Rightarrow f_* \ge & f(x_k) + \nabla f(x_k)^T(x_* - x_k) \\ \Rightarrow f(x_k) \le & f_* + \nabla f(x_k)^T(x_k - x_*) \end{align*} f ( y ) ≥ Let { y = x ∗ x = x k ⇒ f ∗ ≥ ⇒ f ( x k ) ≤ f ( x ) + ∇ f ( x ) T ( y − x ) f ( x k ) + ∇ f ( x k ) T ( x ∗ − x k ) f ∗ + ∇ f ( x k ) T ( x k − x ∗ ) Combining with the inequality for Lipschitz smooth functions f ( x k + 1 ) ≤ f ( x k ) − 1 2 L ∥ ∇ f ( x k ) ∥ 2 f(x_{k+1}) \le f(x_k)-\frac{1}{2L}\left\|\nabla f(x_k)\right\|^2 f ( x k + 1 ) ≤ f ( x k ) − 2 L 1 ∥ ∇ f ( x k ) ∥ 2
f ( x k + 1 ) ≤ f ∗ + ∇ f ( x k ) T ( x k − x ∗ ) − 1 2 L ∥ ∇ f ( x k ) ∥ 2 f(x_{k+1}) \le f_* + \nabla f(x_k)^T(x_k - x_*) - \frac{1}{2L}\left\|\nabla f(x_k)\right\|^2 f ( x k + 1 ) ≤ f ∗ + ∇ f ( x k ) T ( x k − x ∗ ) − 2 L 1 ∥ ∇ f ( x k ) ∥ 2 Furthermore,
∥ ∇ f ( x k ) ∥ 2 = L 2 ∥ x k + 1 − x k ∥ 2 = L 2 ( ∥ x k + 1 − x ∗ ∥ 2 + ∥ x k − x ∗ ∥ 2 − 2 < x k + 1 − x ∗ , x k − x ∗ > ) = L 2 ( ∥ x k + 1 − x ∗ ∥ 2 + ∥ x k − x ∗ ∥ 2 − 2 < x k − 1 L ∇ f ( x k ) − x ∗ , x k − x ∗ > ) = L 2 ( ∥ x k + 1 − x ∗ ∥ 2 − ∥ x k − x ∗ ∥ 2 + 2 L < ∇ f ( x k ) , x k − x ∗ > ) = L 2 ( ∥ x k + 1 − x ∗ ∥ 2 − ∥ x k − x ∗ ∥ 2 + 2 L ∇ f ( x k ) T ( x k − x ∗ ) ) \begin{align*} \left\|\nabla f(x_k)\right\|^2 = & L^2\left\|x_{k+1} - x_k\right\|^2 \\ = & L^2 \left(\left\|x_{k+1} - x_*\right\|^2 + \left\|x_k - x_*\right\|^2 - 2 \left<x_{k+1}-x_*,x_k-x_*\right>\right) \\ = & L^2 \left(\left\|x_{k+1} - x_*\right\|^2 + \left\|x_k - x_*\right\|^2 - 2 \left<x_k-\frac{1}{L}\nabla f(x_k)-x_*,x_k-x_*\right>\right) \\ = & L^2 \left(\left\|x_{k+1} - x_*\right\|^2 - \left\|x_k - x_*\right\|^2 + \frac{2}{L} \left<\nabla f(x_k),x_k-x_*\right>\right) \\ = & L^2 \left(\left\|x_{k+1} - x_*\right\|^2 - \left\|x_k - x_*\right\|^2 + \frac{2}{L} \nabla f(x_k)^T(x_k-x_*)\right) \\ \end{align*} ∥ ∇ f ( x k ) ∥ 2 = = = = = L 2 ∥ x k + 1 − x k ∥ 2 L 2 ( ∥ x k + 1 − x ∗ ∥ 2 + ∥ x k − x ∗ ∥ 2 − 2 ⟨ x k + 1 − x ∗ , x k − x ∗ ⟩ ) L 2 ( ∥ x k + 1 − x ∗ ∥ 2 + ∥ x k − x ∗ ∥ 2 − 2 ⟨ x k − L 1 ∇ f ( x k ) − x ∗ , x k − x ∗ ⟩ ) L 2 ( ∥ x k + 1 − x ∗ ∥ 2 − ∥ x k − x ∗ ∥ 2 + L 2 ⟨ ∇ f ( x k ) , x k − x ∗ ⟩ ) L 2 ( ∥ x k + 1 − x ∗ ∥ 2 − ∥ x k − x ∗ ∥ 2 + L 2 ∇ f ( x k ) T ( x k − x ∗ ) ) Substituting into the inequality above yields
f ( x k + 1 ) ≤ f ∗ + ∇ f ( x k ) T ( x k − x ∗ ) − L 2 ( ∥ x k + 1 − x ∗ ∥ 2 − ∥ x k − x ∗ ∥ 2 + 2 L ∇ f ( x k ) T ( x k − x ∗ ) ) = f ∗ − L 2 ( ∥ x k + 1 − x ∗ ∥ 2 − ∥ x k − x ∗ ∥ 2 ) ⇒ ∑ k = 0 T − 1 f ( x k + 1 ) ≤ T f ∗ − L 2 ( ∥ x T − x ∗ ∥ 2 − ∥ x 0 − x ∗ ∥ 2 ) ≤ T f ∗ + L 2 ∥ x 0 − x ∗ ∥ 2 \begin{align*} f(x_{k+1}) \le & f_* + \nabla f(x_k)^T(x_k - x_*) \\ & - \frac{L}{2}\left(\left\|x_{k+1} - x_*\right\|^2 - \left\|x_k - x_*\right\|^2 + \frac{2}{L} \nabla f(x_k)^T(x_k-x_*)\right) \\ = & f_* - \frac{L}{2}\left(\left\|x_{k+1} - x_*\right\|^2 - \left\|x_k - x_*\right\|^2\right) \\ \Rightarrow \sum_{k=0}^{T-1}f(x_{k+1}) \le & Tf_* - \frac{L}{2}\left(\left\|x_T - x_*\right\|^2 - \left\|x_0 - x_*\right\|^2\right) \\ \le & Tf_* + \frac{L}{2}\left\|x_0 - x_*\right\|^2 \end{align*} f ( x k + 1 ) ≤ = ⇒ k = 0 ∑ T − 1 f ( x k + 1 ) ≤ ≤ f ∗ + ∇ f ( x k ) T ( x k − x ∗ ) − 2 L ( ∥ x k + 1 − x ∗ ∥ 2 − ∥ x k − x ∗ ∥ 2 + L 2 ∇ f ( x k ) T ( x k − x ∗ ) ) f ∗ − 2 L ( ∥ x k + 1 − x ∗ ∥ 2 − ∥ x k − x ∗ ∥ 2 ) T f ∗ − 2 L ( ∥ x T − x ∗ ∥ 2 − ∥ x 0 − x ∗ ∥ 2 ) T f ∗ + 2 L ∥ x 0 − x ∗ ∥ 2 Since for each step we have f ( x k + 1 ) ≤ f ( x k ) − 1 2 L ∥ ∇ f ( x k ) ∥ 2 f(x_{k+1}) \le f(x_k)-\frac{1}{2L}\left\|\nabla f(x_k)\right\|^2 f ( x k + 1 ) ≤ f ( x k ) − 2 L 1 ∥ ∇ f ( x k ) ∥ 2 ∀ k = 0 , ⋯ , T − 1 , f ( x T ) < f ( x k ) \forall k=0,\cdots,T-1,\quad f(x_T)<f(x_k) ∀ k = 0 , ⋯ , T − 1 , f ( x T ) < f ( x k )
T f ( x T ) ≤ T f ∗ + L 2 ∥ x 0 − x ∗ ∥ 2 ⇒ f ( x T ) − f ∗ ≤ L 2 T ∥ x 0 − x ∗ ∥ 2 \begin{align*} T f(x_T) \le & T f_* + \frac{L}{2}\left\|x_0 - x_*\right\|^2 \\ \Rightarrow f(x_T) - f_* \le & \frac{L}{2T}\left\|x_0 - x_*\right\|^2 \\ \end{align*} T f ( x T ) ≤ ⇒ f ( x T ) − f ∗ ≤ T f ∗ + 2 L ∥ x 0 − x ∗ ∥ 2 2 T L ∥ x 0 − x ∗ ∥ 2 To achieve an ε \varepsilon ε
L 2 T ∥ x 0 − x ∗ ∥ 2 ≤ ε ⇒ T ≥ L 2 ε ∥ x 0 − x ∗ ∥ 2 \begin{align*} \frac{L}{2T}\left\|x_0 - x_*\right\|^2 \le & \varepsilon \\ \Rightarrow T \ge & \frac{L}{2\varepsilon}\left\|x_0 - x_*\right\|^2 \end{align*} 2 T L ∥ x 0 − x ∗ ∥ 2 ≤ ⇒ T ≥ ε 2 ε L ∥ x 0 − x ∗ ∥ 2 Thus, the required time complexity is O ( 1 ε ) O\left(\frac{1}{\varepsilon}\right) O ( ε 1 )
Lipschitz Smooth + Strongly Convex Function For a strongly convex function f f f
f ( y ) ≥ f ( x ) + ∇ f ( x ) T ( y − x ) + μ 2 ∥ y − x ∥ 2 Let { y = x ∗ y − x = − ∇ f ( x ) μ ⇒ f ∗ ≥ f ( x ) − 1 μ ∥ ∇ f ( x ) ∥ 2 + μ 2 ⋅ 1 μ 2 ∥ ∇ f ( x ) ∥ 2 = f ( x ) − 1 2 μ ∥ ∇ f ( x ) ∥ 2 ⇒ f ( x ) − f ∗ ≤ 1 2 μ ∥ ∇ f ( x ) ∥ 2 \begin{align*} f(y) \ge & f(x) + \nabla f(x)^T(y - x) + \frac{\mu}{2}\|y - x\|^2 \\ \text{Let} \begin{cases} y=x_*\\ y-x=-\frac{\nabla f(x)}{\mu} \end{cases} \Rightarrow f_* \ge & f(x) - \frac{1}{\mu}\left\|\nabla f(x)\right\|^2 + \frac{\mu}{2}\cdot\frac{1}{\mu^2}\left\|\nabla f(x)\right\|^2 \\ = & f(x) - \frac{1}{2\mu}\left\|\nabla f(x)\right\|^2 \\ \Rightarrow f(x)-f_* \le & \frac{1}{2\mu}\left\|\nabla f(x)\right\|^2 \end{align*} f ( y ) ≥ Let { y = x ∗ y − x = − μ ∇ f ( x ) ⇒ f ∗ ≥ = ⇒ f ( x ) − f ∗ ≤ f ( x ) + ∇ f ( x ) T ( y − x ) + 2 μ ∥ y − x ∥ 2 f ( x ) − μ 1 ∥ ∇ f ( x ) ∥ 2 + 2 μ ⋅ μ 2 1 ∥ ∇ f ( x ) ∥ 2 f ( x ) − 2 μ 1 ∥ ∇ f ( x ) ∥ 2 2 μ 1 ∥ ∇ f ( x ) ∥ 2 Combining with the inequality for Lipschitz smooth functions f ( x k + 1 ) ≤ f ( x k ) − 1 2 L ∥ ∇ f ( x k ) ∥ 2 f(x_{k+1}) \le f(x_k)-\frac{1}{2L}\left\|\nabla f(x_k)\right\|^2 f ( x k + 1 ) ≤ f ( x k ) − 2 L 1 ∥ ∇ f ( x k ) ∥ 2
f ( x k + 1 ) ≤ f ( x k ) − 2 μ 2 L ( f ( x k ) − f ∗ ) ⇒ f ( x k + 1 ) − f ∗ ≤ f ( x k ) − f ∗ − μ L ( f ( x k ) − f ∗ ) = ( 1 − μ L ) ( f ( x k ) − f ∗ ) ⇒ f ( x T ) − f ∗ ≤ ( 1 − μ L ) T ( f ( x 0 ) − f ∗ ) \begin{align*} f(x_{k+1}) \le & f(x_k) - \frac{2\mu}{2L}\left(f(x_k)-f_*\right) \\ \Rightarrow f(x_{k+1})-f_* \le & f(x_k)-f_* - \frac{\mu}{L}\left(f(x_k)-f_*\right) \\ = & \left(1-\frac{\mu}{L}\right)\left(f(x_k)-f_*\right) \\ \Rightarrow f(x_T)-f_* \le & \left(1-\frac{\mu}{L}\right)^T\left(f(x_0)-f_*\right) \end{align*} f ( x k + 1 ) ≤ ⇒ f ( x k + 1 ) − f ∗ ≤ = ⇒ f ( x T ) − f ∗ ≤ f ( x k ) − 2 L 2 μ ( f ( x k ) − f ∗ ) f ( x k ) − f ∗ − L μ ( f ( x k ) − f ∗ ) ( 1 − L μ ) ( f ( x k ) − f ∗ ) ( 1 − L μ ) T ( f ( x 0 ) − f ∗ ) To achieve an ε \varepsilon ε
( 1 − μ L ) T ( f ( x 0 ) − f ∗ ) ≤ ε ⇒ f ( x 0 ) − f ∗ ε ≤ ( 1 − μ L ) − T ⇒ log f ( x 0 ) − f ∗ ε ≤ T log 1 1 − μ L ⏟ ≈ μ L ⇒ T ≥ L μ log f ( x 0 ) − f ∗ ε \begin{align*} \left(1-\frac{\mu}{L}\right)^T\left(f(x_0)-f_*\right) \le & \varepsilon \\ \Rightarrow \frac{f(x_0)-f_*}{\varepsilon} \le & \left(1-\frac{\mu}{L}\right)^{-T} \\ \Rightarrow \log\frac{f(x_0)-f_*}{\varepsilon} \le & T\underbrace{\log\frac{1}{1-\frac{\mu}{L}}}_{\approx \frac{\mu}{L}} \\ \Rightarrow T \ge & \frac{L}{\mu}\log\frac{f(x_0)-f_*}{\varepsilon} \end{align*} ( 1 − L μ ) T ( f ( x 0 ) − f ∗ ) ≤ ⇒ ε f ( x 0 ) − f ∗ ≤ ⇒ log ε f ( x 0 ) − f ∗ ≤ ⇒ T ≥ ε ( 1 − L μ ) − T T ≈ L μ log 1 − L μ 1 μ L log ε f ( x 0 ) − f ∗ Therefore, the required time complexity is O ( log 1 ε ) O\left(\log\frac{1}{\varepsilon}\right) O ( log ε 1 )
Miscellaneous Notes Midterm season is incredibly busy. There are many things I want to write about, but I don’t even have time to write code for the project I’m currently working on, let alone these topics. I can only jot down what might be most useful for now and leave the rest for later.
There is much more to convex optimization, including accelerated gradient descent algorithms, stochastic gradient descent algorithms, constrained optimization, and so on. These are all very interesting topics. Of course, conducting convergence analysis for them can be quite challenging. I’ll write about them when I get the chance. Most likely they are too difficult, so I won’t.
References Wright, S., & Recht, B. (2022). Optimization for Data Analysis. Cambridge: Cambridge University Press. doi:10.1017/9781009004282