Đây là bài mở đầu cho chuỗi bài mình sắp viết về thuật toán gradient descent (GD) dưới góc nhìn sâu hơn về mặt độ phức tạp tính toán cũng như tính hội tụ của thuật toán này. Trong bài này mình chủ yếu nhắc lại một số khái niệm cơ bản và giới thiệu sơ qua thuật toán gradient descent. Do dung lượng bài viết có hạn, mình không thể nhắc lại hết toàn bộ các khái niệm cơ bản liên quan đến giải tích. Bạn đọc có thể xem thêm một số khái niệm đó trên blog machine learning cơ bản (bài 1, bài 2, bài 3, bài 4).

Kiến thức duy nhất bạn cần nhớ trong bài này là khai triển Taylor. Bạn sẽ thấy ứng dụng của khai triển Taylor trong rất nhiều bài viết sắp tới đây.

Một số khái niệm và quy ước

Ta sẽ dùng chữ in đậm $\mathbf{x}$ để kí hiệu một vector (hay một điểm) trong không gian Euclidean $d$ chiều, kí hiệu $\mathbb{R}^d$. Giá trị trong chiều thứ $i$ của $\mathbf{x}$ là $x_i$. Ta kí hiệu tích vô hướng giữa hai vector $\mathbf{x}$ và $\mathbf{y}$ bởi $\langle \mathbf{x}, \mathbf{y}\rangle$.

Gọi $f: \mathbb{R}^d \rightarrow R$ là một hàm số liên tục, nhiều biến. Nếu $f$ là một hàm khả vi (differentiable), ta sử dụng $\nabla f(\mathbf{x})$ để kí hiệu gradient của $f$ tại điểm $\mathbf{x}$. Gradient $\nabla f(\mathbf{x})$ là một vector $d$ chiều, trong đó chiều thứ $i$ là đạo hàm riêng (partial derivative) $ \frac{\partial f}{\partial x_i}$ tại $\mathbf{x}$.

Nếu hàm $f$ là có đạo hàm cấp 2 (twice-differentiable), ta sử dụng $\nabla^2 f(\mathbf{x})$ để kí hiệu ma trận Hessian của $f$ tại điểm $\mathbf{x}$. Ma trận Hessian $\nabla^2 f(\mathbf{x})$ là một ma trận vuông kích thước $d \times d$; hàng thứ $i$ và cột thứ $j$ có giá trị $\nabla^2 f(\mathbf{x})[i,j] = \frac{\partial^2 f}{\partial x_i \partial x_j}$. Hầu hết các trường hợp ta gặp trong thực tế, ma trận Hessian là một ma trận đối xứng. Trong chuỗi bài này rất ít khi ta sử dụng ma trận Hessian nên bạn đọc có thể không cần phải nhớ chi tiết.

Một tập $K \subseteq \mathbb{R}^d$ được gọi là một tập lồi (convex set) nếu cho trước hai điểm bất kì $\mathbf{x},\mathbf{y}\in K$, với mọi $\lambda \in [0,1]$, điểm $\lambda \mathbf{x} + (1-\lambda) \mathbf{y}$ cũn nằm trong $K$. Ta gọi điểm $\lambda \mathbf{x} + (1-\lambda)\mathbf{y}$ là một tổ hợp lồi (convex combination) của hai điểm $\mathbf{x},\mathbf{y}$. Trong tất cả các bài viết ở đây, ta sẽ sử dụng $K$ để kí hiệu một tập lồi đóng (a closed convex set).

Hàm $f: \mathbb{R}^d \rightarrow R$ với miền xác định lồi $K$ là một hàm lồi (convex function) nếu:

$f(\lambda \mathbf{x} + (1-\lambda)\mathbf{y}) \leq \lambda f(\mathbf{x}) + (1-\lambda)f(\mathbf{y}) \quad \forall \mathbf{x},\mathbf{y} \in K, \forall \lambda \in [0,1] \qquad (1)$

Điều kiện lồi trong (1) được gọi là điều kiện lồi bậc không (zeroth-order condition) bởi vì điều kiện lồi này không liên quan tới đạo hàm/gradient. Ngoài bậc không, ta còn có điều kiện lồi bậc một (first-order condition): hàm khả vi $f$ là một hàm lồi nếu:

$f(\mathbf{y}) \geq f(\mathbf{x}) + \langle \nabla f(\mathbf{x}), \mathbf{y}-\mathbf{x} \rangle \quad \forall \mathbf{x},\mathbf{y} \in K \qquad (2)$

Điều kiện lồi bậc một sẽ được sử dụng đi sử dụng lại rất nhiều lần trong chuỗi bài nên mình khuyến khích bạn đọc dành nhiều thời gian để hiểu thật kĩ điều kiện này. Chỉ nhìn vào công thức thì điều kiện (2) sẽ hơi khó hiểu và khó nhớ. Tuy nhiên, ý nghĩa hình học của nó rõ ràng hơn nhiều.

Để đơn giản, ta xét trường hợp $f$ là hàm một biến. $\nabla f(x)$ chính là đạo hàm của $f$ tại $x$ và $\langle \nabla f(x), y-x \rangle = f'(x)(y-x)$ (ta sử dụng chữ cái thường thay vì sử dụng chữ in đậm ở đây). Khi đó, $f(x) + \langle \nabla f(x), y-x \rangle$ chính là phương trình của một đường thẳng, gọi là $(P)$, đi qua điểm $(x, f(x))$ và có hệ số góc $f'(x)$. Ý nghĩa của phương trình $(2)$ lúc này là mọi điểm nằm trên đường cong biểu diễn bởi $f$ sẽ nằm bên trên đường thẳng $(P)$.

Figure 1: Ý nghĩa hình học của điều kiện lồi bậc một.

Cách hiểu $(2)$ trong không gian nhiều chiều cũng tương tự như vậy. Tuy nhiên ta không gọi $f(\mathbf{x}) + \langle \nabla f(\mathbf{x}), \mathbf{y}-\mathbf{x} \rangle $ là một đường thẳng mà ta gọi nó là một siêu phẳng (hyperplane).

Bổ đề dưới đây cho chúng ta biết điều kiện lồi bậc không và bậc một là tương đương đối với các hàm khả vi. Mình sẽ hướng dẫn chứng minh bổ đề này trong bài tập 1.

Ngoài điều kiện lồi bậc không và một thì ta còn có điều kiện lồi bậc hai đối với các hàm có đạo hàm cấp 2 (twice-diffirentiable): hàm $f$ có đạo hàm cấp 2 là một hàm lồi nếu $\nabla^2 f(\mathbf{x})$ là một ma trận nửa xác định dương (positive semi-definite). Ở đây ta rất ít khi sử dụng điều kiện này ở đây nên bạn đọc cũng không cần phải nhớ. (Ngược lại, trong toán phổ thông ta hay sử dụng điều kiện bậc hai để kiểm tra tính lồi/lõm của một hàm.)

Remark 1: Khi ta nói $f$ là một hàm lồi, ta mặc định tập xác định $K$ của nó cũng phải là một tập lồi.

Bài toán tối ưu lồi

Cho một hàm lồi $f: \mathbb{R}^d \rightarrow \mathbb{R}$ với tập xác định lồi $K$, bài toán tối ưu lồi (convex optimization) là bài toán tìm một điểm $\hat{\mathbf{x}}$ sao cho:

$ f(\hat{\mathbf{x}}) - \min_{\mathbf{x} \in K}f(\mathbf{x}) \leq \epsilon \qquad (3)$

với $\epsilon$ là một số thực cho trước nhỏ hơn $1$. Nếu tập xác định $K$ là toàn bộ không gian $\mathbb{R}^d$ thì ta gọi bài toán (3) là bài toán unconstrained convex optimization. Ngược lại, ta gọi (3) là bài toán constrained convex optimization. Goi $\mathbf{x}^*$ là một điểm thuộc $K$ mà tại đó $f$ có giá trị nhỏ nhất. Ta gọi $\mathbf{x}^*$ là một điểm tối ưu (minimizer).

Remark 2: Một hàm lồi $f$ có thể có nhiều điểm tối ưu và điểm $\hat{\mathbf{x}}$ trong bài toán (3) mà ta tìm được có thể không gần với $\mathbf{x}^*$ mặc dù giá trị của hàm $f$ tại hai điểm này lại gần với nhau.

Điều kiện tối ưu: Để tìm được một điểm tối ưu (minimizer) ta cần phải biết được các tính chất của nó. Nếu $K = \mathbb{R}^d$ (bài toán là unconstrained), điểm $\mathbf{x}^*$ sẽ thỏa mãn tính chất gradient của $f$ tại $\mathbf{x}^*$ là 0 (hay chính xác hơn là một vector 0):

$ \nabla f(\mathbf{x}^*) = \mathbf{0} \qquad (4)$

Mình nghĩ rằng bạn đọc đã quá quen với tính chất này vì ở toán phổ thông, ta thường tìm điểm cực tiểu của một hàm bằng cách cho đạo hàm bằng 0. Phương trình (4) chỉ là biến thể của thủ tục này trong không gian nhiều chiều.

Tuy nhiên, nếu $K \not= \mathbb{R}^d$ (bài toán là constrained) thì gradient của $f$ tại $\mathbf{x}^*$ có thể không bằng 0. Thay vào đó, $\mathbf{x}^*$ sẽ thỏa mãn:

$ \langle \nabla f(\mathbf{x}^*), \mathbf{x} - \mathbf{x}^*\rangle \geq 0 \quad \forall \mathbf{x} \in K \qquad (5)$

Điều kiện $(5)$ là một điều kiện rất quan trọng trong constrained convex optimization. Trong ví dụ 3 phần khai triển Taylor dưới đây, ta sẽ chứng minh $(5)$. Về ý nghĩa hình học của $(5)$ thì mình cũng không chắc lắm; bạn nào biết thì xin để lại phần comment.

Bài toán tối ưu lồi online

Bạn đọc không quan tâm đến tối ưu lồi online (online convex optimization) thì có thể bỏ qua phần này. Trong các bài toán online, ta có khái niệm thời gian $t = 0,1,2,\ldots$. Giả sử chúng ta có một thuật toán $A$.
Tại thời điểm $t$, ta có (i) $\mathbf{x}_t \in K$ là điểm tối ưu đầu ra của $A$ và (ii) và mất mát tương ứng $f_t(\mathbf{x}_t)$. Ở đây $f_t$ là hàm mất mát (loss function) tại thời gian $t$ và là một hàm lồi với tập xác định lồi $K$. Ta định nghĩa regret của thuật toán $A$ là đại lượng:

$\sum_{t=0}^T f_t(\mathbf{x}_t) - \min_{\mathbf{x} \in K} \sum_{t=0}^T f_t(\mathbf{x}) \qquad (6)$

Bài toán đặt ra đối với tối ưu lồi lonline là tìm thuật toán có regret nhỏ nhất.

Thuật toán gradient descent

Thuật toán gradient descent là thuật toán rất đơn giản để giải bài toán (3). Thuật toán bắt đầu bằng việc dự đoán một điểm $x_0$ và từ đó tìm một điểm mới bằng cách cập nhật ngược theo chiều của vector gradient nếu như điểm hiện tại chưa thỏa mãn (3). Giả mã dưới đây minh họa thuật toán gradient descent cho bài toán unconstrained convex optimization ($K = \mathbb{R}^d$).

Chính vì sự đơn giản mà thuật toán gradient descent là thuật toán quan trọng nhất trong tối ưu, cả về lý thuyết những thực tế. Tất cả sự phức tạp của gradient descent lại nằm ở phép phân tích:

1. Điểm đầu ra $\mathbf{x}_T$ có thỏa mãn $f(\mathbf{x}_T) - \min_{\mathbf{x} \in K}f(\mathbf{x}) \leq \epsilon$ hay không? Với giá trị nào của $T$ thì đầu ra thỏa mãn điều kiện đó?
2. Chọn $\eta_t$ như thế nào, lớn hay nhỏ?
3. Tại sao không chọn đúng một giá trị $\eta$ rồi áp dụng cho tất cả các bước lặp mà lại chọn $\eta_t$ riêng biệt cho từng bước lặp?
4. Tại sao ta lại cập nhật ngược hướng gradient? Chọn hướng cập nhật khác với gradient sẽ có ảnh hưởng như thế nào?

Trong loạt bài tiếp theo, chúng ta sẽ tìm hiểu (một phần) câu trả lời cho tất cả các câu hỏi đó.

Nếu $K \not= \mathbb{R}^d$ thì điểm mới cập nhật $\mathbf{x}_{t+1}$ có thể không thuộc $K$. Do đó, ta cần phải chiếu nó xuống $K$ để thu được điểm thuộc $K$ sau mỗi bước cập nhật. Ta gọi điểm $\mathbf{y} \in K$ là một hình chiếu (projection) của điểm $\mathbf{x}$ nếu khoảng cách Euclidean:

$d(\mathbf{x}, \mathbf{y}) \leq d(\mathbf{x}, \mathbf{z}) \quad \forall \mathbf{z}\in K \qquad (7) $

Figure 2: Hình chiếu $\mathbf{y}$ của điể $\mathbf{x}$ trên tập lồi $K$.

Xem minh họa trên Figure 2. Ta kí hiệu hình chiếu của $\mathbf{x}$ trên $K$ là $\Pi_K(\mathbf{x})$. (Nếu $\mathbf{x} \in K$ thì $\Pi_K(\mathbf{x}) = \mathbf{x}$.). Thuật toán gradient descent áp dụng cho bài toán constrained convex optimization sẽ có dạng như sau:

 
Dòng màu đỏ là sự khác biệt cơ bản giữa hai thuật toán gradient descent và projected gradient descent.

Khi phân tích thuật toán projected gradient descent, ta thường hay sử dụng tính chất sau: nếu $\mathbf{y}$ là hình chiếu của $\mathbf{x}$ trên tập lồi $K$ thì với mọi điểm $\mathbf{z} \in K$, góc tại $\mathbf{y}$ của tam giác tạo bởi ba điểm $\mathbf{x}, \mathbf{y}, \mathbf{z}$ là góc tù. Phát biểu một cách hình thức hơn:

 
Chứng minh: Giả sử góc tại $\mathbf{y}$ là một góc nhọn. Đương nhiên góc tại $ \mathbf{z}$ cũng phải là một góc nhọn, vì nếu không cạnh $xy$ lớn hơn cạnh $xz$, trái với giả thiết $\mathbf{y}$ là hình chiếu của $\mathbf{x}$. Gọi $\mathbf{u}$ là hình chiếu của $\mathbf{x}$ trên đoạn $yz$. Ta có $\mathbf{u} \in K$ vì $K$ lồi. Tuy nhiên, đoạn $xu$ lại nhỏ hơn đoạn $xy$, trái với giả thiết $\mathbf{y}$ là hình chiếu của $\mathbf{x}$ (dpcm).

Từ Lemma 1, ta suy ra hệ quả sau:

Ta dùng $||\mathbf{x}||_2$ để kí hiệu độ dài của vector $\mathbf{x}$.

Remark 3: Ở đây ta chưa mô tả phép chiếu xuống một tập lồi được thực hiện như thế này. Trong thực tế, đây là bài toán không tầm thường và độ phức tạp phụ thuộc vào từng trường hợp cụ thể. Tạm thời, ta cứ coi như thực hiện phép chiếu có thể thực hiện được và chỉ mất 1 đơn vị thời gian.

Bài toán online convex optimization Gradient descent cũng áp dụng được cho bài toán online convex optimization. Trong ngữ cảnh này, ta sẽ không "chọn" $T$ vì $T$ sẽ là một phần của đầu vào (input). Bài toán online cũng có hai dạng là constrained và unconstrained. Để đơn giản, ta chỉ xét bài toán unconstrained ($K = \mathbb{R}^d$) ở đây. Câu hỏi đặt ra của bài toán này là regret của thuật toán gradient descent sẽ là bao nhiêu sau $T$ bước. Giả mã của thuật toán như sau:

Nếu bài toán là constrained thì ta chỉ cần thêm một bước chiếu $\mathbf{x}_{t+1}$ xuống $K$.

Khai triển Taylor

Khai triển Taylor là một công cụ rất hữu dụng để chứng minh cũng như giải thích một số phương pháp/điều kiện liên quan tới tối ưu lồi mà ta sẽ xét sau này. Công thức khai triển Taylor cho trường hợp một biến khá đẹp, nhưng khi hàm có nhiều hơn một biến thì công thức này hơi phức tạp. Tuy nhiên, về mặt trực quan thì tổng quát khai triển Taylor từ trường hợp một biến lên nhiều biến không phải là quá khó. Do đó, mình tập trung vào trường hợp một biến và sẽ nói ngắn gọn về trường hợp nhiều biến.

Cách mình phát biểu định lý Taylor ở đây hơi khác với cách phát biểu bạn thường thấy như trên Wikipedia, do cách phát biểu này phù hợp hơn với các phân tích mà mình sẽ trình bày trong chuỗi bài này. Về ý nghĩa của kí hiệu $o(.)$ (đọc là $o$-nhỏ), bạn có thể xem lại tại đây.

Rất ít khi ta phải dùng đến khai triển Taylor cấp $k$, mà chủ yếu là cấp 1:

$f(x + \epsilon) = f(x) + f'(x)\epsilon + o(\epsilon) \qquad (11)$

hoặc cấp 2:

$f(x + \epsilon) = f(x) + f'(x)\epsilon + \frac{f''(x)}{2!}\epsilon^2 + o(\epsilon^2) \qquad (12)$

Để hiểu ý nghĩa của khai triển Taylor, ta xét một số ví dụ áp dụng.

Ví dụ 1: Giả sử bạn tính được dạng đóng (closed form) đạo hàm của một hàm $f: R\rightarrow R$ và để tính đạo hàm tại $x$, bạn thay giá trị $x$ vào công thức dạng đóng đó. Tuy nhiên, để kiểm tra xem dạng đóng đó có đúng hay không, cách hay dùng là chọn một điểm ngẫu nhiên $x$ (trong tập xác định), một số $\epsilon$ đủ nhỏ và so sánh $\frac{f(x + \epsilon) - f(x-\epsilon)}{2\epsilon}$ với $f'(x)$ xem hai giá trị này có gần với nhau hay không. Nếu công thức dạng đóng của bạn là đúng thì hai giá trị này phải gần nhau vì:

$f'(x)= \lim_{\epsilon \rightarrow 0}\frac{f(x + \epsilon) - f(x-\epsilon)}{2\epsilon}\qquad (13)$

Cách khác là thay vì tính $\frac{f(x + \epsilon) - f(x-\epsilon)}{2\epsilon}$, bạn có thể tính $\frac{f(x) - f(x-\epsilon)}{\epsilon}$ và so sánh với $f'(x)$ vì:

$f'(x)= \lim_{\epsilon \rightarrow 0}\frac{f(x ) - f(x-\epsilon)}{\epsilon}\qquad (14)$

Cách nào cho độ chính xác cao hơn? Hay câu hỏi chính xác hơn là với cùng một $\epsilon$ đủ nhỏ, giá trị nào trong hai giá trị (a) $\frac{f(x + \epsilon) - f(x-\epsilon)}{2\epsilon}$ và (b) $\frac{f(x) - f(x-\epsilon)}{\epsilon}$ sẽ gần với $f'(x)$ hơn? Câu trả lời là (a) sẽ gần với $f'(x)$ hơn vì, theo khai triển Taylor bậc 2, ta có:

$\begin{array} {l} f(x+\epsilon) & = f(x) + f'(x)\epsilon + \frac{f''(x)}{2!}\epsilon^2 + o(\epsilon^2) \\ f(x-\epsilon)& = f(x) - f'(x)\epsilon + \frac{f''(x)}{2!}\epsilon^2 + o(\epsilon^2) \end{array}$

Do đó:

$\begin{array} {l} \frac{f(x + \epsilon) - f(x-\epsilon)}{2\epsilon} & = f'(x) + o(\epsilon) \\ \frac{f(x) - f(x-\epsilon)}{\epsilon} & = f'(x) + \frac{f''(x)}{2!}\epsilon + o(\epsilon) \end{array}$

Như vậy, khi $\epsilon$ đủ nhỏ thì giá trị (a) sẽ gần $f'(x)$ hơn giá trị (b). Do đó, cách đầu tiên là cách hay dùng để kiểm tra đạo hàm.

Ví dụ 2: Tại sao trong phương pháp gradient descent ta lại cập nhật $x_t$ ngược hướng với gradient (đạo hàm) tại $x_t$? Câu này có thể trả lời sử dụng khai triển Taylor cấp 1:

$f(x_t - \eta f'(x_t))= f(x_t) - f'(x_t)^2\eta + o(\eta) \qquad (15)$

Trong (15), ta giả sử $f'(x_t)$ là một hằng số khác 0. (Nếu $f'(x_t) = 0$ thì $x_t$ đã là điểm cực tiểu rồi, ta không cần phải cập nhật $x_t$ nữa). Khi $\eta$ đủ nhỏ, $o(\eta) \leq f'(x_t)^2\eta/2$. Do đó, từ (13) ta suy ra:

$f(x_t - \eta f'(x_t)) \leq f(x_t) - f'(x_t)^2\eta/2 \mbox{ < } f(x_t)$

Như vậy, bằng cách cập nhật ngược hướng với gradient, $f(x_{t+1})$ nhỏ hơn $f(x_t)$, i.e, ta tiến gần hơn tới một minimizer. Trong thực tế, cách chứng minh ở ví dụ này sử dụng công thức Taylor cũng là cách phổ biến để phân tích xem nếu ta chọn hướng khác với gradient thì liệu giá trị của hàm có giảm sau mỗi bước hay không. (Đôi khi không nhất thiết phải chọn hướng cập nhật ngược với hướng gradient.)

Trường hợp nhiều chiều. Trường hợp nhiều chiều ta thường chỉ dùng khai triển Taylor tới cấp 1 hoặc 2.

Ví dụ 3: Ta sẽ sử dụng khai triển Taylor cấp 1 để chứng minh tiêu chuẩn tối ưu trong công thức (5). Giả sử tồn tại $\mathbf{x}$ sao cho:

$\langle \nabla f(\mathbf{x}^*), \mathbf{x} - \mathbf{x}^* \rangle$ < $0 \qquad (17)$

Theo công thức Taylor, ta có:

$ f(\mathbf{x}^* + \eta (\mathbf{x} - \mathbf{x}^*)) = f(\mathbf{x}^*) - \eta \langle \nabla f(\mathbf{x}^*),\mathbf{x}^* - \mathbf{x} \rangle + o(\eta) \qquad (18)$

Theo (17), khi $\eta$ đủ nhỏ, ta có:

$ - \eta/2 \langle \nabla f(\mathbf{x}^*),\mathbf{x}^* - \mathbf{x} \rangle + o(\eta) \leq 0$

Do đó, khi $\eta$ đủ nhỏ, từ (18), ta suy ra:

$ f(\mathbf{x}^* + \eta (\mathbf{x} - \mathbf{x}^*)) \leq f(\mathbf{x}^*) - \eta/2 \langle \nabla f(\mathbf{x}^*),\mathbf{x}^* - \mathbf{x}\rangle$ < $f(\mathbf{x}^*)$

Do $K$ là một tập lồi, ta có $\mathbf{x}^* + \eta (\mathbf{x} - \mathbf{x}^*) =\eta \mathbf{x} + (1-\eta) \mathbf{x}^* \in K$; trái với giả thiết $\mathbf{x}^*$ là điểm nằm trong $K$ có $f(\mathbf{x}^*)$ nhỏ nhất. Như vậy, $(5)$ phải thỏa mãn với mọi $\mathbf{x} \in K$.

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. Bài này mình sẽ hướng dẫn các bạn chứng minh Lemma 1.

• Từ (1) suy ra (2). Biến đổi phương trình (1) để suy ra:

  $f(\mathbf{x}) \geq f(\mathbf{y}) + \frac{f(\mathbf{y} + \lambda(\mathbf{x}-\mathbf{y})) - f(\mathbf{y})}{\lambda} $

  Cho $\lambda \rightarrow 0$, ta sẽ suy ra được dpcm.

• Từ (2) suy ra (1). Đặt $z = \lambda \mathbf{x} + (1-\lambda)\mathbf{y}$. Áp dụng (2) hai lần, đối với cặp $(\mathbf{x}, \mathbf{z})$ và với cặp $(\mathbf{y}, \mathbf{z})$, ta sẽ suy ra được dpcm.

Lời giải đầy đủ của bài này có thể xem tại đây.