Trước hết mình khuyến khích bạn đọc xem lại bài mở đầu trước khi đọc bài này. Tóm gọn lại bài trước trong một câu: thuật toán gradient descent bắt đầu từ một dự đoán ban đầu $\mathbf{x}_0$, sau đó cập nhật điểm kể tiếp, với step size $\eta_t$, theo hướng ngược với hướng của gradient của hàm $f(.)$ ở điểm hiện tại:

Trong thuật toán projected gradient descent, ta có thêm bước chiếu điểm cập nhật xuống miền xác định (lồi) $K$ trước khi thực hiện bước cập nhật kế tiếp.

 
Có vài cách để phân tích tính hội tụ của gradient descent. Cách mà mình sử dụng trong loạt bài này là phương pháp hàm thế năng (potential function), như mô tả trong note của Bansal và Gupta [1].

Trước khi đi vào chi tiết, ta tìm hiểu khái niệm $p$-norm (dịch là chuẩn $p$, nhưng mình không thích từ này lắm vì nó không thể hiện đúng ý nghĩa của từ norm). $p$-norm của một vector (hay điểm) $\mathbf{x} \in \mathbb{R}^d$, kí hiệu $||\mathbf{x}||_p$, được định nghĩa như sau:

$||\mathbf{x}||_p = (\sum_{i=1}^d |x_i|^p)^{1/p} \qquad (3)$

Ba loại norm mà ta thường hay sử dụng là $1$-norm, $2$-norm và $\infty$-norm tương ứng với $p = 1$ ,$p=2$ và $p = \infty$. $2$-norm chính là độ dài Euclidean của vector mà ta thường gặp trong sách giáo khoa phổ thông.

Remark: $||\mathbf{x}||_\infty = \max_{i}(|x_i|)$. Bạn đọc có thể xem thêm về $p$-norm tại đây.

Phương pháp hàm thế năng

Gọi $\mathbf{x}^*$ là một điểm tối ưu (minimizer). Trong các phép phân tích dưới đây, ta sẽ sử dụng một hàm $\Phi_t$, mà ta gọi là hàm thế năng, định nghĩa như sau:

$\Phi_t = a_t(f(\mathbf{x}_t) - f(\mathbf{x}^*)) + b_t \cdot \mathrm{distance}( \mathbf{x}_t, \mathbf{x}^*) \qquad (3)$

Ở đây, $a_t,b_t$ là các số không âm và $\mathrm{distance}( \mathbf{x}_t, \mathbf{x}^*)$ là khoảng cách từ điểm hiện tại $\mathbf{x}_t$ tới điểm $\mathbf{x}^*$. Hàm khoảng cách này có thể không phải là Euclidean (hoặc norm). Ta thường áp dụng hàm thế năng vào phép phân tích tính hội tụ theo một trong hai cách sau:

Cách thứ nhất: Ta sẽ chứng minh:

$\Phi_{t+1} - \Phi_{t} \leq B_t \qquad (4)$

Từ đó, ta có thể suy ra:

$\Phi_{T} - \Phi_{0} \leq \sum_{t=0}^T B_t \Rightarrow f(\mathbf{x}_T) - f(\mathbf{x}^*) \leq \frac{\Phi_{0} + \sum_{t=0}^T B_t }{a_T}\qquad (5)$

Ý nghĩa của $(5)$ đó là ta đã ước lượng được sự khác biệt giữa $f(\mathbf{x}_T)$ và $f(\mathbf{x}^*)$ (ở đây $T$ là thời điểm thuật toán kết thúc), và nếu sự khác biệt này là không quá $\epsilon$, điểm mà thuật toán trả về $\mathbf{x}_T$ là một điểm gần tối ưu.

Cách thứ hai: Ta sẽ chứng minh:

$f(\mathbf{x}_t) + (\Phi_{t+1} - \Phi_{t}) \leq f(\mathbf{x}^*) + B \qquad (6)$

Từ đó, ta sẽ suy ra:

$ \frac{\sum_{t=0}^{T-1} f(\mathbf{x}_t)}{T} - f(\mathbf{x}^*) \leq B + \frac{\Phi_0}{T} \qquad (7)$

Nếu $B + \frac{\Phi_0}{T} \leq \epsilon$ thì từ $(7)$, ta biết rằng $ \frac{\sum_{t=0}^{T-1} f(\mathbf{x}_t)}{T}$ rất gần với $f(\mathbf{x}^*)$. Từ đây, ta có hai cách để tìm điểm tối ưu.

Cách thứ nhất, sử dụng điều kiện $f(.)$ là một hàm lồi, $f(\frac{\sum_{t=0}^{T-1}\mathbf{x}_t}{T}) \leq \frac{\sum_{t=0}^{T-1} f(\mathbf{x}_t)}{T} $. Kết hợp với (7), ta có:

$ f(\frac{\sum_{t=0}^{T-1}\mathbf{x}_t}{T}) - f(\mathbf{x}^*) \leq B + \frac{\Phi_0}{T} \qquad (8)$

Như vậy, điểm $\frac{\sum_{t=0}^{T-1}\mathbf{x}_t}{T}$ là một điểm gần tối ưu. Điểm này chính là điểm trung bình cộng của tất cả các điểm trong quá trình ta chạy thuật toán.

Cách thứ hai, ta sẽ lưu lại điểm $\mathbf{x}_{m}$ có $f(\mathbf{x}_{m})$ nhỏ nhất trong tất cả các điểm $\mathbf{x}_{0}, \mathbf{x}_{2}, \ldots, \mathbf{x}_{T-1}$. Điểm $\mathbf{x}_{m}$ đương nhiên sẽ thỏa mãn $f(\mathbf{x}_{m}) \leq \frac{\sum_{t=0}^{T-1} f(\mathbf{x}_t)}{T}$, và như vậy, nó là một điểm gần tối ưu. Cách này không cần sử dụng tính chất $f(.)$ là một hàm lồi.

Remark 1: Trong cách phân tích thứ 2, điểm trả về không phải là $\mathbf{x}_T$ như trong giả mã ở bài trước.

Remark 2: Không có quy tắc chung để chọn các tham số $a_t,b_t$ và hàm khoảng cách $\mathrm{distance}( \mathbf{x}_t, \mathbf{x}^*)$, cũng như không có quy tắc ta nên áp dụng cách phân tích 1 hay 2 (4) hay (6), mà chủ yếu dựa vào kinh nghiệm là chính (trial and error). Tuy nhiên, nếu đọc kĩ chuỗi bài này thì hi vọng bạn cũng sẽ có một chút cảm nhận nên chọn hàm thế năng thế nào với từng trường hợp cụ thể.

Tính hội tụ của GD cho hàm lồi

Trong phần này, ta sẽ minh họa chứng minh tính hội tụ của thuật toán GD cho hàm lồi nói chung. Đối với hàm lồi nói chung, ta sẽ chọn step size $\eta_t$ như nhau sau mỗi bước. Cụ thể, $\eta_1 = \eta_2 = \ldots = \eta_{T-1} = \eta$. Trong bài tiếp theo, ta sẽ xét các hàm lồi có một số tính chất đặc biệt hơn. Trong những trường hợp đó, đôi khi chọn step size $\eta_t$ khác nhau sau mỗi bước sẽ làm thuật toán hội tụ nhanh hơn.

Trước khi chứng minh Theorem 1, ta nói thêm một chút về ý nghĩa của nó.
Đại lượng $D = ||x_0- x^*||_2$ đăc trưng cho dự đoán ban đầu của chúng ta là tốt hay không tốt. Nếu điểm dự đoán càng gần điểm tối ưu thì $D$ càng nhỏ. Thông thường, ta sẽ chọn $\mathbf{x}_0$ ngẫu nhiên xung quanh điểm $0$.

Đại lượng $G = \max_{t}||\nabla f(\mathbf{x}_t)||_2$ đặc trưng cho sự biến động của hàm mà ta đang tối ưu. Nếu gradient của hàm là lớn, thì hàm có biên độ dao động lớn. Tức là chỉ một thay đổi nhỏ của $\mathbf{x}$ cũng làm cho giá trị của hàm $f(.)$ thay đổi một lượng lớn. Các hàm như vậy thường khó tối ưu hơn. Phương trình (10) phần nào thể hiện tính chất này.

Ta coi hai đại lượng $D$ và $G$ là hai đại lượng đặc trưng cho độ khó của bài toán, vì nói chung, ta không có cách nào để kiểm soát hai đại lượng này. Hai tham số mà ta có thể kiểm soát được là $T$ và step size $\eta$. Từ $(10)$, ta có nhận xét sau:

1. Số lần cập nhật $T$ càng lớn thì giá trị của hàm $f(.)$ tại điểm đầu ra của thuật toán càng gần với điểm tối ưu. Nếu ta chọn:

   $T = (\frac{DG}{\epsilon})^2 \qquad (11)$

   thì từ $(10)$ và tính lồi của $f(.)$, ta suy ra:

   $f(\frac{\sum_{t=0}^{T-1}\mathbf{x}_t}{T}) - f(\mathbf{x}^*) \leq \frac{1}{T}\sum_{t=0}^{T-1}f(\mathbf{x}_t) - f(\mathbf{x}^*) \leq \epsilon \qquad (12)$

   Như vậy, điểm đầu ra của thuật toán $\frac{\sum_{t=0}^{T-1}\mathbf{x}_t}{T}$ là điểm gần tối ưu.

2. Nếu $\eta$ nhỏ thì đại lượng $\eta\frac{G^2}{2}$ nhỏ và $\frac{D^2}{2\eta T}$ sẽ lớn, và ngược lại. Như vậy, muốn thuật toán hội tụ nhanh, ta không được chọn $\eta$ quá nhỏ hoặc quá lớn. Giá trị tốt nhất của $\eta$ là $\frac{D}{G\sqrt{T}}$. Khi $T = (\frac{DG}{\epsilon})^2$ thì $\eta =\frac{\epsilon}{G^2}$. Trong hầu hết các trường hợp, ta sẽ không biết được giá trị $G$. Thay vào đó, cách ta hay làm là thử các giá trị $\eta$ từ lớn đến nhỏ và chọn giá trị $\eta$ mà thuật toán hội tụ nhanh nhất. Phương trình (10) cho ta biết, chỉ cần giá trị $\eta$ gần với $\frac{D}{G\sqrt{T}}$ thì tốc độ hội tụ của thuật toán cũng khá tốt rồi.

Chứng minh Theorem 1: Để chứng minh Theorem 1, ta phải sử dụng tính chất lồi của $f(.)$. Ở đây, ta sẽ sử dụng điều kiện lồi bậc 1. Điều kiện này mình đã nhắc đến trong bài trước. Mình copy lại điều kiện này ra đây để bạn đọc dễ theo dõi:

$f(\mathbf{y}) \geq f(\mathbf{x}) + \langle \nabla f(\mathbf{x}), \mathbf{y}-\mathbf{x} \rangle \quad \forall \mathbf{x},\mathbf{y} \in \mathbb{R}^d \ \qquad (13)$

Chú ý, ở đây ta đang phân tích thuật toán GD cho bài toán unconstrained nên tập xác định của $f(.)$ là $\mathbb{R}^d$.

Ta sẽ áp dụng cách thứ 2 của phương pháp hàm thế năng. Hàm thế năng ta định nghĩa trong trường hợp này là:

$\Phi_t = \frac{1}{2\eta} ||\mathbf{x}_t - \mathbf{x}^*||_2^2\qquad (14)$

Dễ thấy $\Phi_0 = \frac{D^2}{2\eta}$. Để ước lượng sự thay đổi của hàm thế năng, ta xét hiệu:

$\begin{array} {l} ||\mathbf{x}_{t+1} - \mathbf{x}^*||_2^2 - ||\mathbf{x}_t - \mathbf{x}^*||_2^2 & = ||\mathbf{x}_{t+1}||_2^2 - ||\mathbf{x}_{t}||_2^2 -2\langle \mathbf{x}_{t+1} -\mathbf{x}_{t}, \mathbf{x}^* \rangle \\ & = ||\mathbf{x}_{t} - \eta \nabla f(\mathbf{x}_{t})||_2^2 - ||\mathbf{x}_{t}||_2^2 + 2 \eta\langle \nabla f(\mathbf{x}_{t}), \mathbf{x}^* \rangle \\
&= \eta^2 \nabla^2f(\mathbf{x}_{t}) + 2\eta\langle\nabla f(\mathbf{x}_{t},\mathbf{x}^* - \mathbf{x}_t \rangle \\
&\leq \eta^2 G^2 + 2\eta \langle\nabla f(\mathbf{x}_{t},\mathbf{x}^* - \mathbf{x}_t \rangle \end{array} \quad (15)$

Từ đó ta suy ra:

$\begin{array} {l} f(\mathbf{x}_{t}) + \Phi_{t+1} - \Phi_t & = f(\mathbf{x}_{t}) + \frac{1}{2\eta} ( ||\mathbf{x}_{t+1} - \mathbf{x}^*||_2^2 - ||\mathbf{x}_t - \mathbf{x}^*||_2^2) \\
& \leq f(\mathbf{x}_{t}) + \eta \frac{G^2}{2} + \langle\nabla f(\mathbf{x}_{t},\mathbf{x}^* - \mathbf{x}_t \rangle \\
& \leq f(\mathbf{x}^*) + \eta \frac{G^2}{2} \end{array} \quad (16)$

Trong dòng cuối cùng của $(16)$, ta áp dụng $(13)$ với $\mathbf{y} = \mathbf{x}^*$. Do đó, ta có thể áp dụng $(7)$ với $B = \eta \frac{G^2}{2}$ và $\Phi_0 = \frac{D^2}{2\eta}$ để suy ra dpcm.

Tính hội tụ của projected GD cho hàm lồi

Trong thuật toán projected GD, sau khi cập nhật xong điểm hiện tại, ta còn thêm một bước chiếu xuống miền xác định (lồi) $K$ của $f(.)$ (xem phương trình (2)). Bước chiếu này làm cho phép phân tích khó hơn một chút. Tuy nhiên, kết quả hội tụ thì vẫn không thay đổi.

Chứng minh Theorem 2: Nhắc lại, hình chiếu $\mathbf{y}$ của điểm $\mathbf{x}$ trên $K$ là điểm thuộc $K$ gần $\mathbf{x}$ nhất. Ta sẽ sử dụng Corollary 1 của bài trước (xem Figure 1).

Figure 1: Hình chiếu của $\mathbf{x}'_{t+1}$ trên $K$.

Vì $\mathbf{x}_{t+1}$ là hình chiếu của $\mathbf{x}'_{t+1}$, ta có:

$||\mathbf{x}_{t+1} - \mathbf{x}^*||^2_2 \leq ||\mathbf{x}'_{t+1} - \mathbf{x^*}||^2_2 $

Phần còn lại của chứng minh ta lặp lại theo các bước trong chứng minh Theorem 1. Chi tiết coi như bài tập cho bạn đọc

Tham khảo

[1] Bansal, Nikhil, and Anupam Gupta. Potential-Function Proofs for First-Order Methods. arXiv preprint arXiv:1712.04581 (2017).

Bài tập

Bài 1. Hoàn thành chứng minh đầy đủ của Theorem 2.