Thuật toán Gradient Descent cập nhật tham số dựa trên nguyên lý toán học nào?

Gradient Descent cập nhật ngược hướng của vector đạo hàm riêng (gradient ∇f) theo công thức: θ_{k+1} = θ_k - η ∇f(θ_k), trong đó η là tốc độ học (learning rate), đảm bảo hàm mục tiêu giảm nhanh nhất tại mỗi bước lặp.

Sự khác biệt giữa tối ưu hóa lồi (Convex Optimization) và phi lồi (Non-Convex Optimization) là gì?

Trong tối ưu hóa lồi, mọi điểm cực tiểu địa phương (local minimum) đều là điểm cực tiểu toàn cục (global minimum) duy nhất; trong khi bài toán phi lồi có thể chứa rất nhiều cực tiểu địa phương và điểm yên ngựa (saddle points) khiến thuật toán dễ bị mắc kẹt.

Các biến thể tối ưu hóa phổ biến trong Deep Learning gồm những gì?

Gồm: Stochastic Gradient Descent (SGD) với Momentum, RMSprop (thích ứng theo bình phương gradient), và Adam (kết hợp cả quán tính moment bậc 1 và chuẩn hóa phương sai moment bậc 2).

Thuật toán tối ưu hóa là gì? Phân loại, Gradient Descent và bài toán lồi

Thuật toán tối ưu hóa (optimization algorithm) là các phương pháp tính toán số học được thiết kế có hệ thống nhằm tìm ra phần tử tốt nhất $x^*$ (điểm cực tiểu hóa hoặc cực đại hóa) của một hàm mục tiêu $f(x)$ trong một tập hợp các giá trị khả thi $\Omega$ chịu sự chi phối của các điều kiện ràng buộc. Tối ưu hóa là nền tảng cốt lõi của toán học ứng dụng, khoa học dữ liệu, học máy (Machine Learning), kinh tế lượng và kỹ thuật công nghiệp.

Dạng bài toán tối ưu hóa tổng quát

Một bài toán quy hoạch toán học liên tục tổng quát được phát biểu dưới dạng chuẩn tắc:

\min_{x \in \mathbb{R}^n} f(x)

thỏa mãn các hệ điều kiện ràng buộc:

\begin{cases} g_i(x) \le 0, & i = 1, 2, \dots, m \quad \text{(Ràng buộc bất đẳng thức)} \\ h_j(x) = 0, & j = 1, 2, \dots, p \quad \text{(Ràng buộc đẳng thức)} \end{cases}

Nếu hàm mục tiêu $f(x)$ và tập chấp nhận được $\Omega$ là lồi (convex), bài toán được gọi là Tối ưu hóa lồi (Convex Optimization). Điểm độc đáo của bài toán lồi là bất kỳ điểm cực tiểu cục bộ nào cũng đồng thời là điểm cực tiểu toàn cục duy nhất.

Phân loại các nhóm thuật toán tối ưu hóa

1. Các thuật toán bậc nhất dựa trên Gradient (First-Order Methods)

Sử dụng thông tin đạo hàm bậc nhất (vector gradient $\nabla f(x)$ ) để xác định hướng suy giảm nhanh nhất:

Hạ Gradient cơ bản (Batch Gradient Descent):
$x_{k+1} = x_k - \eta \nabla f(x_k)$
Trong đó $\eta > 0$ là tốc độ học (learning rate). Thuật toán tính toán gradient trên toàn bộ tập dữ liệu mẫu ở mỗi bước lặp.
Hạ Gradient ngẫu nhiên (Stochastic Gradient Descent - SGD): Ước tính gradient chỉ trên một mẫu đơn lẻ hoặc một lô dữ liệu nhỏ (Mini-batch), giúp giảm đáng kể chi phí tính toán trên tập dữ liệu lớn và hỗ trợ thoát khỏi các điểm yên ngựa (saddle points).
Thuật toán tối ưu hóa thích ứng (Adam - Adaptive Moment Estimation): Kết hợp ước lượng moment bậc nhất (quán tính chuyển động) và moment bậc hai (phương sai của gradient) để tự động điều chỉnh tốc độ học riêng biệt cho từng tham số.

2. Các thuật toán bậc hai (Second-Order Methods)

Sử dụng thêm thông tin độ cong không gian từ ma trận đạo hàm riêng bậc hai (ma trận Hessian $\nabla^2 f(x)$ ):

Phương pháp Newton-Raphson:
$x_{k+1} = x_k - \left[\nabla^2 f(x_k)\right]^{-1} \nabla f(x_k)$
Tốc độ hội tụ bậc hai cực nhanh gần điểm cực trị, tuy nhiên chi phí tính toán và nghịch đảo ma trận Hessian kích thước $n \times n$ là $\mathcal{O}(n^3)$ , rất tốn kém khi số chiều tham số lớn.
Phương pháp Quasi-Newton (BFGS & L-BFGS): Xấp xỉ dần ma trận nghịch đảo Hessian qua các bước lặp chỉ bằng các phép tính gradient bậc nhất, giảm độ phức tạp tính toán xuống $\mathcal{O}(n^2)$ hoặc $\mathcal{O}(mn)$ đối với bộ nhớ giới hạn (Limited-memory BFGS).

3. Thuật toán phỏng đoán và tiến hóa sinh học (Heuristics & Metaheuristics)

Áp dụng cho các bài toán tối ưu tổ hợp rời rạc phi lồi phức tạp (NP-hard, như bài toán người giao hàng TSP):

Giải thuật di truyền (Genetic Algorithms - GA): Mô phỏng chọn lọc tự nhiên qua các phép lai ghép (crossover), đột biến (mutation) và chọn lọc cá thể thích nghi.
Tối ưu hóa bầy đàn (Particle Swarm Optimization - PSO): Mô phỏng hành vi di chuyển tìm mồi của đàn chim hoặc đàn cá.
Mô phỏng tôi luyện kim loại (Simulated Annealing): Cho phép chấp nhận các bước đi làm tăng giá trị hàm mục tiêu với xác suất giảm dần theo hàm nhiệt độ để vượt qua các hố cực tiểu cục bộ nông.

Bảng so sánh hiệu năng các thuật toán tối ưu tiêu biểu

Thuật toán	Bậc đạo hàm	Tốc độ hội tụ	Độ phức tạp bộ nhớ	Khả năng áp dụng với dữ liệu lớn
SGD + Momentum	Bậc 1	Dưới tuyến tính / Tuyến tính	$\mathcal{O}(n)$	Rất xuất sắc (Chuẩn mực trong Deep Learning)
Adam / AdamW	Bậc 1 (Thích ứng)	Tuyến tính	$\mathcal{O}(n)$	Rất xuất sắc (Huấn luyện LLM, Transformer)
L-BFGS	Xấp xỉ bậc 2	Siêu tuyến tính (Superlinear)	$\mathcal{O}(mn)$	Tốt cho mô hình vừa và nhỏ (Logistic Regression, CRF)
Newton thuần túy	Bậc 2	Bậc 2 (Quadratic)	$\mathcal{O}(n^2)$	Kém đối với số chiều tham số lớn

Điều kiện tối ưu hóa Karush-Kuhn-Tucker (KKT)

Đối với bài toán tối ưu có ràng buộc khả vi, nghiệm tối ưu $x^*$ cùng các nhân tử Lagrange $\lambda^*, \mu^*$ phải thỏa mãn hệ điều kiện KKT:

Tính dừng (Stationarity): $\nabla f(x^*) + \sum_{i=1}^m \lambda_i^* \nabla g_i(x^*) + \sum_{j=1}^p \mu_j^* \nabla h_j(x^*) = 0$
Chấp nhận được nguyên thủy (Primal Feasibility): $g_i(x^*) \le 0, \quad h_j(x^*) = 0$
Chấp nhận được đối ngẫu (Dual Feasibility): $\lambda_i^* \ge 0$
Bù trừ triệt tiêu (Complementary Slackness): $\lambda_i^* g_i(x^*) = 0, \quad \forall i=1,\dots,m$