Giảm dần theo gradient (Gradient Descent)

Nguồn và giấy phép. Đây là bản dịch tiếng Việt của tụi mình cho “3 Gradient Descent”, do đội ngũ khóa học MIT 6.390 (trước đây là 6.036) biên soạn; nguồn được truy cập ngày 12/08/2026 và phát hành theo giấy phép CC BY-NC-SA 4.0. Tụi mình diễn đạt lại câu văn bằng tiếng Việt, giữ khối thuật toán algorithmic của nguồn, nhưng không lược bỏ nội dung chuyên môn của nguồn. Bản dịch và phần đóng góp của bami-hub cũng được phát hành theo CC BY-NC-SA 4.0. MIT và đội ngũ khóa học không bảo trợ hay chứng thực bami-hub.

Ở chương trước, chúng ta đã xây dựng một hàm mục tiêu (objective function) hữu ích cho bài toán học máy. Tuy nhiên, ta vẫn cần tìm giá trị tối ưu $Θ^{*} = \arg \min_{Θ} J (Θ)$ , nhất là khi không thể tối ưu hàm mục tiêu bằng phương pháp giải tích. Trường hợp này có thể xảy ra khi $J (Θ)$ dùng một hàm mất mát phức tạp hơn, dùng dạng chính quy hóa tổng quát hơn, hoặc đơn giản là có quá nhiều tham số cần học nên chi phí tính toán trở nên bất khả thi.

Nền tảng toán học và thuật toán của tối ưu hóa là một lĩnh vực nghiên cứu đồ sộ và hấp dẫn. Trong khóa học này, chúng ta sẽ xét một trong những phương pháp đơn giản nhất: phương pháp giảm dần theo gradient (gradient descent, GD).

Nếu có dịp, bạn nên tìm hiểu sâu hơn về tối ưu hóa. Đây vừa là một trong những công cụ nền tảng làm nên học máy, vừa là một lĩnh vực đẹp và sâu sắc.

Trong một hoặc hai chiều, ta dễ hình dung $J (Θ)$ tạo thành một mặt phía trên không gian tham số $Θ$ ; trực giác này vẫn mở rộng được lên số chiều cao hơn. Mục tiêu là tìm giá trị $Θ$ ứng với điểm thấp nhất trên mặt đó. Ta có thể hình dung GD như sau: bắt đầu tại một điểm tùy ý, xác định hướng mà “ngọn đồi” dốc xuống nhanh nhất, bước một bước nhỏ theo hướng ấy, rồi tiếp tục xác định hướng xuống dốc nhanh nhất và lặp lại.

Các mục dưới đây trình bày cụ thể thuật toán GD cho hàm mục tiêu một chiều và nhiều chiều (Mục 3.1 và Mục 3.2), rồi áp dụng nó cho một hàm mất mát khác với mất mát bình phương trung bình (Mục 3.3). Cuối cùng, ta tìm hiểu giảm dần theo gradient ngẫu nhiên (stochastic gradient descent, SGD) (Mục 3.4), một phương pháp đặc biệt hữu ích khi tập dữ liệu quá lớn để xử lý toàn bộ trong mỗi bước và có những hành vi đáng chú ý riêng.

3.1. Giảm dần theo gradient trong một chiều

Trước hết, ta xét GD trong một chiều. Giả sử $Θ \in ℝ$ , và ta biết cả $J (Θ)$ lẫn đạo hàm bậc nhất của nó theo $Θ$ , $J^{'} (Θ)$ . Sau đây là mã giả (pseudocode) của thuật toán GD cho một hàm tùy ý $f$ . Ngoài $f$ và gradient $\nabla_{Θ} f$ — khi $Θ$ là vô hướng, gradient chính là đạo hàm $f^{'}$ và mô tả độ dốc của đồ thị — ta phải chỉ định một số siêu tham số (hyperparameter).

Các siêu tham số này gồm giá trị khởi tạo của tham số $Θ$ , siêu tham số tốc độ học (learning rate) $η$ , và siêu tham số độ chính xác $ϵ$ .

Để đơn giản, ta có thể chọn $η$ là hằng số như trong mã giả dưới đây; ngay sau đây ta sẽ gặp các tốc độ học thích nghi, tức không cố định. Tuy nhiên, ngay cả khi $η$ không đổi, độ lớn của mỗi thay đổi đối với $Θ$ vẫn có thể khác nhau vì nó còn phụ thuộc vào độ lớn của gradient.

Thuật toán 3.1

1:procedure 1D-Gradient-Descent( $Θ_{i n i t}, η, f, f^{'}, ϵ$ )

2: $Θ^{(0)} \leftarrow Θ_{i n i t}$

3: $t \leftarrow 0$

4:repeat

5: $t \leftarrow t + 1$

6: $Θ^{(t)} = Θ^{(t - 1)} - η f^{'} (Θ^{(t - 1)})$

7:until $| f (Θ^{(t)}) - f (Θ^{(t - 1)}) | < ϵ$

8:return $Θ^{(t)}$

9:end procedure

Lưu ý rằng thuật toán dừng khi thay đổi trong giá trị của hàm mục tiêu đủ nhỏ. Có nhiều cách hợp lý khác để quyết định thời điểm dừng, chẳng hạn:

Dừng sau một số vòng lặp cố định $T$ , tức khi $t = T$ . Trên thực tế, đây là lựa chọn phổ biến nhất.
Dừng khi đạo hàm của $f$ đủ nhỏ, tức khi $| f^{'} (Θ^{(t)}) | < ϵ$ .
Dừng khi thay đổi trong giá trị tham số $Θ$ đủ nhỏ, tức khi $| Θ^{(t)} - Θ^{(t - 1)} | < ϵ$ .

Hãy xem xét tất cả tiêu chí dừng tiềm năng của 1D-Gradient-Descent, cả tiêu chí xuất hiện trong thuật toán lẫn những tiêu chí được liệt kê riêng. Bạn có nghĩ ra cách nào cho thấy hai tiêu chí bất kỳ liên hệ với nhau không?

Định lý 3.1.Chọn một khoảng cách nhỏ tùy ý $\tilde{ϵ} > 0$ . Nếu giả sử $f$ có điểm cực tiểu, đủ “trơn” và lồi (convex), đồng thời tốc độ học $η$ đủ nhỏ, thì GD sẽ đi tới một điểm cách một điểm tối ưu toàn cục $Θ$ không quá $\tilde{ϵ}$ .

Tuy vậy, ta phải cẩn thận khi chọn tốc độ học để tránh hội tụ chậm, dao động quanh cực tiểu mà không hội tụ, hoặc phân kỳ.

Hình minh họa trong nguồn cho thấy thuật toán GD chạy ổn định trên hàm lồi $f (x) = {(x - 2)}^{2}$ , bắt đầu tại $x_{init} = 4.0$ với tốc độ học $1 / 2$ .

Nếu $f$ không lồi (non-convex), điểm mà GD hội tụ đến sẽ phụ thuộc vào $x_{init}$ . Trước hết, ta cần một số định nghĩa. Cho $f$ là hàm nhận giá trị thực trên miền $D$ . Một điểm $x_{0} \in D$ được gọi là điểm cực tiểu toàn cục (global minimum point) của $f$ nếu $f (x_{0}) \leq f (x)$ với mọi $x \in D$ khác.

Ghi chú (Ghi chú của biên tập viên)

Trang nguồn có các đồ thị minh họa cho hai đoạn mô tả về hàm lồi và hàm không lồi. Bản dịch hiện giữ lại mô tả và lập luận đi kèm nhưng chưa nhúng các đồ thị vì cần hoàn tất việc kiểm tra và đóng gói tài sản hình ảnh riêng. Đây là giới hạn của bản hiện tại, không phải nội dung bị lược bỏ khỏi nguồn.

Ngược lại, một điểm $x_{0} \in D$ được gọi là điểm cực tiểu cục bộ (local minimum point) của hàm $f$ nếu tồn tại một hằng số $ϵ > 0$ sao cho với mọi $x$ trong khoảng được xác định bởi $d (x, x_{0}) < ϵ$ , ta có $f (x_{0}) \leq f (x)$ . Ở đây, $d$ là một mêtric khoảng cách (distance metric), chẳng hạn $d (x, x_{0}) = ‖ x - x_{0} ‖$ . Điểm cực tiểu toàn cục cũng là điểm cực tiểu cục bộ, nhưng điểm cực tiểu cục bộ không nhất thiết là điểm cực tiểu toàn cục.

Trong ví dụ này, điều gì xảy ra khi $η$ rất nhỏ? Khi $η$ rất lớn?

Nếu $f$ không lồi (và đủ trơn), ta kỳ vọng rằng GD — khi chạy đủ lâu với tốc độ học đủ nhỏ — sẽ tiến rất gần một điểm có gradient bằng 0, dù không thể bảo đảm hội tụ đến một điểm cực tiểu toàn cục.

Có hai ngoại lệ đáng chú ý đối với trực giác này. Thứ nhất, GD có thể đình trệ khi tiến đến một điểm $x$ không phải cực tiểu cục bộ hay cực đại cục bộ nhưng thỏa $f^{'} (x) = 0$ . Chẳng hạn, với $f (x) = x^{3}$ , nếu khởi tạo tại $x_{init} = 1$ và dùng tốc độ học $η < 1 / 3$ , dãy $x^{(k)}$ sẽ hội tụ về 0 khi $k \to \infty$ .

Thứ hai, có những hàm (kể cả hàm lồi) không có điểm cực tiểu, chẳng hạn $f (x) = \exp (- x)$ ; với các hàm như vậy, GD dùng tốc độ học dương sẽ hội tụ đến $+ \infty$ .

Hình tiếp theo trong nguồn cho thấy hai giá trị $x_{init}$ khác nhau khiến GD tiến về hai điểm tối ưu cục bộ khác nhau.

3.2. Nhiều chiều

Ta có thể mở rộng cách làm trên sang trường hợp $Θ$ nhiều chiều mà không cần thay đổi nguyên lý. Giả sử $Θ \in ℝ^{m}$ , nên $f : ℝ^{m} \to ℝ$ .

Gradient của $f$ theo $Θ$ là

\nabla_{Θ} f = [\begin{matrix} \partial f / \partial Θ_{1} \\ ⋮ \\ \partial f / \partial Θ_{m} \end{matrix}] .

Thuật toán vẫn giữ nguyên, chỉ có bước cập nhật ở dòng 5 trở thành

Θ^{(t)} = Θ^{(t - 1)} - η \nabla_{Θ} f (Θ^{(t - 1)}),

và mọi tiêu chí dừng phụ thuộc vào số chiều của $Θ$ cũng phải thay đổi. Cách đơn giản nhất là giữ phép kiểm tra ở dòng 6:

| f (Θ^{(t)}) - f (Θ^{(t - 1)}) | < ϵ,

vì tiêu chí này hợp lý bất kể $Θ$ có bao nhiêu chiều.

Trong các tiêu chí dừng của trường hợp một chiều, tiêu chí nào được định nghĩa theo cách giả định $Θ$ chỉ có một chiều?

3.3. Áp dụng cho hồi quy ridge

Nhắc lại từ chương trước: chọn hàm mất mát là bước đầu tiên khi phát biểu một bài toán học máy dưới dạng bài toán tối ưu. Với hồi quy, ta đã nghiên cứu mất mát bình phương trung bình (mean-squared loss), trong đó mất mát có dạng ${(dự đoán - thực tế)}^{2}$ . Điều này dẫn đến hàm mục tiêu bình phương tối thiểu thông thường:

J (θ) = \frac{1}{n} \sum_{i = 1}^{n} {(θ^{T} x^{(i)} - y^{(i)})}^{2} .

Ta dùng gradient của hàm mục tiêu theo các tham số:

\begin{matrix} \nabla_{θ} J = \frac{2}{n} \underset{d \times n}{\underset{⏟}{X^{T}}} \underset{n \times 1}{\underset{⏟}{(X θ - Y)}} . & (3.1) \end{matrix}

Gradient này cho phép ta thu được nghiệm giải tích của bài toán hồi quy tuyến tính. Ta cũng có thể dùng GD để tính nghiệm gần đúng bằng phương pháp số, với quy tắc cập nhật

θ^{(t)} = θ^{(t - 1)} - η \frac{2}{n} \sum_{i = 1}^{n} ({[θ^{(t - 1)}]}^{T} x^{(i)} - y^{(i)}) x^{(i)} .

3.3.1. Hồi quy ridge

Bây giờ, hãy thêm số hạng chính quy hóa để nhận hàm mục tiêu hồi quy ridge (ridge regression):

J_{ridge} (θ, θ_{0}) = \frac{1}{n} \sum_{i = 1}^{n} {(θ^{T} x^{(i)} + θ_{0} - y^{(i)})}^{2} + λ {‖ θ ‖}^{2} .

Trong bình phương tối thiểu thông thường, ta đã xử lý hệ số chặn $θ_{0}$ bằng cách thêm một chiều chứa toàn số 1. Với hồi quy ridge, ta cần tách vector tham số $θ$ khỏi hệ số chặn $θ_{0}$ . Vì vậy, dưới góc nhìn của thuật toán GD tổng quát, toàn bộ tập tham số được định nghĩa là $Θ = (θ, θ_{0})$ . Ta sẽ tính gradient riêng cho từng phần:

\begin{matrix} \nabla_{θ} J_{ridge} (θ, θ_{0}) & = \frac{2}{n} \sum_{i = 1}^{n} (θ^{T} x^{(i)} + θ_{0} - y^{(i)}) x^{(i)} + 2 λ θ, \\ \frac{\partial J_{ridge} (θ, θ_{0})}{\partial θ_{0}} & = \frac{2}{n} \sum_{i = 1}^{n} (θ^{T} x^{(i)} + θ_{0} - y^{(i)}) . \end{matrix}

Lưu ý rằng $\nabla_{θ} J_{ridge}$ có kích thước $d \times 1$ , còn $\partial J_{ridge} / \partial θ_{0}$ là một vô hướng vì ở đây ta đã tách $θ_{0}$ khỏi $θ$ .

Hãy kiểm tra kích thước của mọi đại lượng trên với giả định $θ$ có kích thước $d \times 1$ . $d$ liên hệ thế nào với $m$ trong cách ký hiệu $Θ$ ở mục trước?

Hãy tính $\nabla_{θ} {‖ θ ‖}^{2}$ bằng cách tìm vector các đạo hàm riêng $(\partial {‖ θ ‖}^{2} / \partial θ_{1}, \dots, \partial {‖ θ ‖}^{2} / \partial θ_{d})$ . $\nabla_{θ} {‖ θ ‖}^{2}$ có kích thước gì?

Hãy tính $\nabla_{θ} J_{ridge} (θ^{T} x + θ_{0}, y)$ bằng cách tìm vector các đạo hàm riêng $(\partial J_{ridge} (θ^{T} x + θ_{0}, y) / \partial θ_{1}, \dots, \partial J_{ridge} (θ^{T} x + θ_{0}, y) / \partial θ_{d})$ .

Dùng hai kết quả vừa tìm để kiểm chứng phép suy diễn ở trên.

Kết hợp các kết quả trên, ta thu được thuật toán GD cho hồi quy ridge:

Thuật toán 3.2

1:procedure RR-Gradient-Descent( $θ_{𝑖𝑛𝑖𝑡}, θ_{0 𝑖𝑛𝑖𝑡}, η, ϵ$ )

2: $θ^{(0)} \leftarrow θ_{𝑖𝑛𝑖𝑡}$

3: $θ_{0}^{(0)} \leftarrow θ_{0 𝑖𝑛𝑖𝑡}$

4: $t \leftarrow 0$

5:repeat

6: $t \leftarrow t + 1$

7: $θ^{(t)} = θ^{(t - 1)} - η (\frac{1}{n} \sum_{i = 1}^{n} ({θ^{(t - 1)}}^{T} x^{(i)} + {θ_{0}}^{(t - 1)} - y^{(i)}) x^{(i)} + λ θ^{(t - 1)})$

8: $θ_{0}^{(t)} = θ_{0}^{(t - 1)} - η (\frac{1}{n} \sum_{i = 1}^{n} ({θ^{(t - 1)}}^{T} x^{(i)} + {θ_{0}}^{(t - 1)} - y^{(i)}))$

9:until $| J_{ridge} (θ^{(t)}, θ_{0}^{(t)}) - J_{ridge} (θ^{(t - 1)}, θ_{0}^{(t - 1)}) | < ϵ$

10:return $θ^{(t)}, θ_{0}^{(t)}$

11:end procedure

Hãy cẩn thận với hai dấu mũ! ${[θ]}^{T}$ là chuyển vị của vector $θ$ .

Có ổn không khi $λ$ không xuất hiện ở dòng 8?

Có ổn không khi các số 2 trong định nghĩa gradient không xuất hiện trong thuật toán?

3.4. Giảm dần theo gradient ngẫu nhiên

Khi gradient có dạng một tổng, thay vì đi một bước tương đối lớn theo hướng âm của toàn bộ gradient, ta có thể chọn ngẫu nhiên một số hạng trong tổng rồi đi một bước rất nhỏ theo hướng âm của số hạng ấy. Cách làm này thoạt nhìn có vẻ khó tin. Tuy nhiên, nếu ta giữ nguyên vị trí, trung bình của tất cả các bước nhỏ sẽ cùng hướng với bước lớn. Trên thực tế vị trí thay đổi sau mỗi bước, nên quỹ đạo có nhiễu nhưng hướng dịch chuyển kỳ vọng vẫn là hướng âm của gradient.

Ghi chú (Ghi chú của biên tập viên)

Nguồn viết tắt là đi “theo hướng của gradient” trong đoạn trực giác này, nhưng các quy tắc cập nhật đều trừ gradient. Tụi mình ghi rõ hướng âm của gradient để nhất quán với công thức và tránh đảo chiều thuật toán.

Hầu hết hàm mục tiêu trong học máy đều có thể viết dưới dạng trung bình trên các điểm dữ liệu. Khi đó, giảm dần theo gradient ngẫu nhiên (stochastic gradient descent, SGD) chọn ngẫu nhiên một điểm dữ liệu, tính gradient như thể tập dữ liệu chỉ chứa điểm đó, rồi đi một bước nhỏ theo hướng âm của gradient vừa tính.

Giả sử hàm mục tiêu có dạng

J (Θ) = \frac{1}{n} \sum_{i = 1}^{n} J_{i} (Θ),

trong đó $n$ là số điểm dữ liệu được dùng trong hàm mục tiêu (và có thể khác số điểm có trong toàn bộ tập dữ liệu).

Sau đây là mã giả áp dụng SGD cho hàm mục tiêu $J$ như vậy; thuật toán giả sử ta biết dạng của $\nabla_{Θ} J_{i}$ với mọi $i$ từ $1$ đến $n$ . Khác với GD chuẩn, tốc độ học $η (t)$ nay phụ thuộc vào chỉ số vòng lặp $t$ , nên có thể giảm dần theo thời gian:

Thuật toán 3.3

1:procedure Stochastic-Gradient-Descent( $Θ_{i n i t}, η, {J_{i}}_{i = 1}^{n}, ϵ$ )

2: $Θ^{(0)} \leftarrow Θ_{𝑖𝑛𝑖𝑡}$

3: $t \leftarrow 0$

4:repeat

5: $t \leftarrow t + 1$

6:chọn ngẫu nhiên $i \in {1, 2, \dots, n}$

7: $Θ^{(t)} = Θ^{(t - 1)} - η (t) \nabla_{Θ} J_{i} (Θ^{(t - 1)})$

8:until $| J (Θ^{(t)}) - J (Θ^{(t - 1)}) | < ϵ$

9:return $Θ^{(t)}$

10:end procedure

Chọn tiêu chí dừng phù hợp cho SGD khó hơn so với GD chuẩn, vì giá trị hàm mục tiêu có thể dao động do nhiễu giữa các bước. Trong thực tế, một phương án phổ biến là dừng sau số vòng lặp cố định $T$ .

Để SGD hội tụ (converge) đến một điểm tối ưu cục bộ khi $t$ tăng, tốc độ học phải giảm theo thời gian. Kết quả tiếp theo chỉ ra một dãy tốc độ học có tính chất này.

Định lý 3.2.

Nếu $f$ lồi và $η (t)$ là một dãy thỏa

\sum_{t = 1}^{\infty} η (t) = \infty và \sum_{t = 1}^{\infty} η {(t)}^{2} < \infty,

thì SGD hội tụ với xác suất một* đến $Θ$ tối ưu.*

Ghi chú (Ghi chú của biên tập viên)

Trong định lý, “với xác suất một” (with probability one) nghĩa là mệnh đề xảy ra với xác suất bằng 1 theo phân phối xác suất đang xét; cách nói này không đồng nghĩa với bảo đảm tuyệt đối cho mọi quỹ đạo riêng lẻ.

Vì sao cần hai điều kiện này? Trực giác là điều kiện thứ nhất, trên $\sum η (t)$ , cần thiết để vẫn cho phép phạm vi thăm dò tiềm năng không bị chặn; điều kiện thứ hai, trên $\sum η {(t)}^{2}$ , bảo đảm tốc độ học nhỏ dần khi $t$ tăng.

Một cách “hợp lệ” để đặt tốc độ học là dùng $η (t) = 1 / t$ , nhưng mọi người thường dùng các quy tắc giảm chậm hơn, và vì thế không hoàn toàn thỏa các tiêu chí hội tụ.

Nếu bắt đầu rất xa điểm tối ưu, việc làm cho $η (t)$ giảm chậm hơn có xu hướng khiến ta đi đến điểm tối ưu nhanh hơn hay chậm hơn?

Có nhiều cách lý giải vì sao SGD đôi khi là lựa chọn thuật toán tốt hơn GD chuẩn:

GD thường phải tính một đại lượng trên mọi điểm trong tập dữ liệu. SGD có thể hoạt động tốt dù mới đi qua một phần dữ liệu, nhờ đó tiết kiệm thời gian chạy và bộ nhớ khi tập dữ liệu rất lớn.
Nếu $J$ không lồi và có nhiều điểm tối ưu cục bộ nông có thể giữ chân GD, nhiễu do lấy mẫu gradient tại $Θ$ có thể “hất” quỹ đạo ra khỏi những điểm ấy để khám phá vùng khác của bề mặt hàm mục tiêu.
Đôi khi tối ưu $J$ thật tốt không phải điều ta muốn, vì nó có thể làm quá khớp tập huấn luyện. Do đó, dù SGD có thể không đạt lỗi huấn luyện thấp hơn GD, nó vẫn có thể cho lỗi kiểm thử thấp hơn.

3.5. Giảm dần theo gradient với mini-batch

Trong thực tế, giảm dần theo gradient với mini-batch (mini-batch gradient descent) là phương án trung gian phổ biến giữa GD và SGD. Thay vì dùng toàn bộ tập dữ liệu như GD hoặc chỉ một điểm dữ liệu như SGD để ước lượng gradient ở mỗi bước, phương pháp này chọn ngẫu nhiên một tập con nhỏ gồm $b$ điểm dữ liệu.

Thuật toán 3.4

1:procedure Mini-batch-Gradient-Descent( $Θ_{i n i t}, η, b, {J_{i}}_{i = 1}^{n}, ϵ$ )

2: $Θ^{(0)} \leftarrow Θ_{𝑖𝑛𝑖𝑡}$

3: $t \leftarrow 0$

4:repeat

5: $t \leftarrow t + 1$

6: $B \leftarrow$ mini-batch ngẫu nhiên kích thước $b$ từ ${1, \dots, n}$

7: $Θ^{(t)} = Θ^{(t - 1)} - η \nabla_{Θ} J_{B} (Θ^{(t - 1)})$

8:until $| J (Θ^{(t)}) - J (Θ^{(t - 1)}) | < ϵ$

9:return $Θ^{(t)}$

10:end procedure

Ở đây,

\nabla_{Θ} J_{B} (Θ) = \frac{1}{b} \sum_{i \in B} \nabla_{Θ} J_{i} (Θ)

là gradient được lấy trung bình trên mini-batch $B$ . Cách này cho ước lượng gradient chính xác hơn SGD, đồng thời chi phí mỗi bước vẫn thấp hơn nhiều so với GD.

Tài liệu tham khảo

MIT 6.390 course staff, “3 Gradient Descent”, truy cập ngày 12/08/2026, giấy phép CC BY-NC-SA 4.0.