Gradient Descent & Optimization Algorithms

Mencari Minimum dalam Ruang Parameter

ml-math

optimization

algorithms

Gradient descent, SGD, Adam, Newton’s method, convergence rates, dan koneksi ke MLE dan IRLS.

Why This Matters for Your Work

Optimization adalah mesin dari ML. Setiap kali kamu call model.fit(), glm(), atau optim(), kamu menjalankan beberapa variant dari gradient descent.

Memahami optimization bukan hanya akademik — ini praktis:

Mengapa model tidak converge? Learning rate terlalu besar atau kecil.
Mengapa training lambat? Mungkin butuh momentum atau adaptive learning rate.
Mengapa loss turun lalu naik lagi? Kemungkinan learning rate terlalu besar, atau ada saddle point.
Kapan pakai Newton’s method vs gradient descent? Newton lebih cepat tapi mahal komputasinya.

Koneksi econometrics: Newton-Raphson untuk MLE adalah Newton’s method pada negative log-likelihood. IRLS (Iteratively Reweighted Least Squares) untuk GLM adalah Newton’s method dengan struktur khusus.

1 Masalah Optimization

Setup umum: kita mau minimasi fungsi $L: \mathbb{R}^p \to \mathbb{R}$:

\[\min_{\theta \in \mathbb{R}^p} L(\theta)\]

di mana $L$ adalah loss function (atau negative log-likelihood, atau whatever we’re minimizing).

Kapan ada closed form? Hanya untuk kasus khusus: - OLS: $L(\beta) = \|y - X\beta\|^2$ → $\hat{\beta} = (X^TX)^{-1}X^Ty$ - Ridge: $L(\beta) = \|y - X\beta\|^2 + \lambda\|\beta\|^2$ → $\hat{\beta} = (X^TX + \lambda I)^{-1}X^Ty$

Untuk hampir semua kasus lain (logistic regression, neural networks, dll.), tidak ada closed form → pakai iterative methods.

2 Gradient Descent

2.1 Intuisi

Bayangkan kamu berdiri di pegunungan dalam kabut, mau turun ke lembah. Kamu tidak bisa lihat jauh, tapi bisa rasakan kemiringan tanah di sekitar kaki kamu. Strategi: selalu ambil satu langkah ke arah paling curam ke bawah.

Itu persis gradient descent.

2.2 Algoritma

Definisi: Gradient Descent

Inisialisasi $\theta_0$ (random atau zero). Untuk $t = 0, 1, 2, \ldots$:

\[\theta_{t+1} = \theta_t - \eta \nabla_\theta L(\theta_t)\]

di mana: - $\nabla_\theta L(\theta_t)$ adalah gradient dari $L$ di $\theta_t$ - $\eta > 0$ adalah learning rate (step size)

Stop ketika $\|\nabla L(\theta_t)\| < \epsilon$ atau setelah $T$ iterasi.

Kenapa negatif gradient? Gradient menunjuk ke arah naik tercuram. Kita mau turun, jadi kita pergi ke arah negatif gradient.

2.3 Learning Rate: The Critical Hyperparameter

Learning rate $\eta$ adalah hyperparameter paling penting dalam gradient descent:

$\eta$ terlalu kecil: - Convergence sangat lambat - Butuh banyak iterasi - Dalam practice: waste of compute

$\eta$ terlalu besar: - “Overshoots” minimum - Loss bisa diverge (terus naik) - Algoritma tidak converge

$\eta$ tepat: - Convergence smooth dan cepat

graph LR
    A["η terlalu kecil"] -->|"konvergensi lambat"| B["butuh ribuan iterasi"]
    C["η tepat"] -->|"konvergensi stabil"| D["optimal dalam ratusan iterasi"]
    E["η terlalu besar"] -->|"diverge/oscillate"| F["loss tidak turun"]
    style C fill:#16a34a,color:#fff
    style E fill:#dc2626,color:#fff

2.4 Convergence untuk Convex Functions

Untuk fungsi convex yang $L$-smooth (gradient Lipschitz dengan konstanta $L$) dan dengan learning rate $\eta = 1/L$:

\[L(\theta_t) - L(\theta^*) \leq \frac{\|\theta_0 - \theta^*\|^2}{2\eta t} = O(1/t)\]

Ini sublinear convergence — untuk mencapai error $\epsilon$, butuh $O(1/\epsilon)$ iterasi.

Untuk strongly convex functions ($\mu$-strongly convex), convergence lebih cepat:

\[L(\theta_t) - L(\theta^*) \leq (1 - \mu\eta)^t [L(\theta_0) - L(\theta^*)]\]

Ini linear convergence — butuh $O(\log(1/\epsilon))$ iterasi.

Worked Example: GD on Quadratic

Minimasi $L(\theta) = \theta^2$.

$\nabla L(\theta) = 2\theta$

Gradient descent update:

\[\theta_{t+1} = \theta_t - \eta \cdot 2\theta_t = (1 - 2\eta)\theta_t\]

Dari $\theta_0$:

\[\theta_t = (1 - 2\eta)^t \theta_0\]

Convergence: $\theta_t \to 0 = \theta^*$ jika dan hanya jika $|1 - 2\eta| < 1$, yaitu $0 < \eta < 1$.

$\eta = 0.4$: $1 - 2\eta = 0.2$, konvergensi lambat
$\eta = 0.5$: $1 - 2\eta = 0$, konvergen dalam 1 langkah!
$\eta = 0.6$: $1 - 2\eta = -0.2$, oscillates tapi konvergen
$\eta = 1.0$: $1 - 2\eta = -1$, oscillates forever
$\eta = 1.5$: $|1 - 2\eta| = 2 > 1$, diverges!

# Implementasi sederhana
gd_quadratic <- function(theta0, eta, n_iter = 50) {
  theta <- theta0
  history <- numeric(n_iter + 1)
  history[1] <- theta

  for (t in seq_len(n_iter)) {
    grad <- 2 * theta          # gradient of theta^2
    theta <- theta - eta * grad
    history[t + 1] <- theta
  }
  history
}

# Coba berbagai learning rates
eta_values <- c(0.1, 0.4, 0.9, 1.1)
par(mfrow = c(2, 2))

for (eta in eta_values) {
  traj <- gd_quadratic(theta0 = 5, eta = eta, n_iter = 50)
  plot(traj, type = "l",
       main = paste("eta =", eta),
       xlab = "Iteration", ylab = "theta",
       ylim = c(-6, 6))
  abline(h = 0, lty = 2, col = "red")
}

3 Variants dari Gradient Descent

3.1 Batch Gradient Descent

Setiap update menggunakan semua $n$ sampel:

\[\nabla_\theta L(\theta) = \frac{1}{n}\sum_{i=1}^n \nabla_\theta L(y_i, f_\theta(x_i))\]

Pro: gradient akurat, convergence smooth
Con: komputasi mahal untuk $n$ besar (harus scan seluruh dataset per step)
Disebut juga “full-batch GD”

3.2 Stochastic Gradient Descent (SGD)

Setiap update menggunakan 1 sampel yang dipilih random:

\[\nabla_\theta L(\theta) \approx \nabla_\theta L(y_i, f_\theta(x_i))\]

\[\theta_{t+1} = \theta_t - \eta \nabla_\theta L(y_{i_t}, f_\theta(x_{i_t}))\]

di mana $i_t$ dipilih uniform dari $\{1, \ldots, n\}$.

Pro: update sangat cepat ($O(1)$ per step vs $O(n)$), bisa escape saddle points karena noise
Con: gradient noisy, tidak converge ke minimum tapi berfluktuasi di sekitarnya
Penting: perlu decreasing learning rate $\eta_t \to 0$ untuk convergence teoritis (Robbins-Monro conditions)

3.3 Mini-batch Gradient Descent

Setiap update menggunakan $B$ sampel (batch size $B$, typically 32–512 dalam deep learning):

\[\nabla_\theta L(\theta) \approx \frac{1}{B}\sum_{i \in \mathcal{B}_t} \nabla_\theta L(y_i, f_\theta(x_i))\]

Tradeoff: antara batch GD (akurat, lambat) dan SGD (noisy, cepat)
Dalam practice: hampir semua deep learning pakai mini-batch GD
Disebut “SGD” dalam literature (meskipun teknisnya mini-batch)

Method	Gradient Estimate	Kecepatan per Step	Noise
Batch GD	Exact	Lambat $O(n)$	None
SGD	$n\times$ noisy	Cepat $O(1)$	Tinggi
Mini-batch GD	Moderate noise	Moderate $O(B)$	Moderate

4 Momentum

Problem dengan vanilla GD: di lembah yang panjang dan sempit, GD zigzag dan konvergensi lambat.

Solusi: Momentum — “ingat” arah update sebelumnya dan lanjutkan ke sana.

Definisi: Gradient Descent with Momentum

\[v_{t+1} = \gamma v_t + \eta \nabla_\theta L(\theta_t)\]

\[\theta_{t+1} = \theta_t - v_{t+1}\]

di mana: - $v_t$ adalah velocity (momentum term) - $\gamma \in [0, 1)$ adalah momentum coefficient (typical: 0.9) - $v_0 = 0$

Intuitinya: bayangkan bola menggelinding di permukaan. Bola punya inertia — tidak langsung berhenti, tapi terus melaju ke arah yang sama. Momentum di GD sama: terus bergerak ke arah yang sudah terbukti menurunkan loss.

Nesterov momentum (slight improvement): hitung gradient di posisi “anticipated” bukan posisi sekarang:

\[v_{t+1} = \gamma v_t + \eta \nabla_\theta L(\theta_t - \gamma v_t)\]

5 Adam Optimizer

Adam (Adaptive Moment Estimation) adalah optimizer paling populer di deep learning. Menggabungkan momentum (first moment) dan adaptive learning rate (second moment).

Definisi: Adam Algorithm

Inisialisasi: $m_0 = 0$, $v_0 = 0$, $t = 0$. Hyperparameter: $\eta = 0.001$, $\beta_1 = 0.9$, $\beta_2 = 0.999$, $\epsilon = 10^{-8}$.

Untuk setiap step:

1. Compute gradient: $g_t = \nabla_\theta L(\theta_t)$

2. First moment estimate (momentum): \[m_t = \beta_1 m_{t-1} + (1 - \beta_1) g_t\]

3. Second moment estimate (RMSProp): \[v_t = \beta_2 v_{t-1} + (1 - \beta_2) g_t^2\]

4. Bias correction (karena $m_0 = v_0 = 0$): \[\hat{m}_t = \frac{m_t}{1 - \beta_1^t}, \quad \hat{v}_t = \frac{v_t}{1 - \beta_2^t}\]

5. Update: \[\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{\hat{v}_t} + \epsilon} \hat{m}_t\]

Kenapa bias correction? Pada awal training ($t$ kecil), $m_t$ dan $v_t$ under-estimate moment sesungguhnya karena diinisialisasi dari 0. Correction $1/(1-\beta^t)$ mengoreksi ini.

Mengapa Adam efektif? - Parameter dengan gradient besar mendapat learning rate kecil (tidak overshoot) - Parameter dengan gradient kecil mendapat learning rate besar (tidak stagnate) - Momentum mengurangi zigzagging - Secara efektif, setiap parameter punya adaptive learning rate sendiri

Worked Example: Adam pada Simple Function

# Implementasi Adam dari scratch
adam_optimizer <- function(L_grad,    # fungsi gradient(theta)
                           theta0,
                           eta   = 0.001,
                           beta1 = 0.9,
                           beta2 = 0.999,
                           eps   = 1e-8,
                           n_iter = 1000) {
  theta <- theta0
  m <- rep(0, length(theta))
  v <- rep(0, length(theta))
  history_loss <- numeric(n_iter)

  for (t in seq_len(n_iter)) {
    g <- L_grad(theta)                           # gradient
    m <- beta1 * m + (1 - beta1) * g            # first moment
    v <- beta2 * v + (1 - beta2) * g^2          # second moment
    m_hat <- m / (1 - beta1^t)                  # bias correction
    v_hat <- v / (1 - beta2^t)
    theta <- theta - eta * m_hat / (sqrt(v_hat) + eps)  # update
    history_loss[t] <- sum(theta^2)             # track loss
  }
  list(theta = theta, history_loss = history_loss)
}

# Test: minimize L(theta) = theta1^2 + 10*theta2^2
# Gradient: [2*theta1, 20*theta2]
grad_fn <- function(theta) c(2 * theta[1], 20 * theta[2])

result <- adam_optimizer(L_grad = grad_fn,
                         theta0 = c(5, 5),
                         eta = 0.1,
                         n_iter = 500)

cat("Final theta:", result$theta, "\n")
plot(result$history_loss, type = "l",
     log = "y",
     xlab = "Iteration", ylab = "Loss (log scale)",
     main = "Adam Convergence")

6 Newton’s Method (Second-Order)

Gradient descent hanya menggunakan first-order information (gradient). Newton’s method menggunakan first AND second order (Hessian).

Definisi: Newton’s Method

\[\theta_{t+1} = \theta_t - H^{-1}(\theta_t) \nabla L(\theta_t)\]

di mana $H(\theta) = \nabla^2 L(\theta)$ adalah Hessian matrix ($p \times p$).

Intuisi: Newton’s method locally approximates $L$ dengan quadratic:

\[L(\theta) \approx L(\theta_t) + \nabla L(\theta_t)^T(\theta - \theta_t) + \frac{1}{2}(\theta - \theta_t)^T H(\theta_t) (\theta - \theta_t)\]

Meminimasi quadratic approximation ini langsung memberikan update Newton.

Pro vs Con Newton’s method:

Aspek	Gradient Descent	Newton’s Method
Per-step cost	$O(p)$	$O(p^2)$ untuk Hessian, $O(p^3)$ untuk invers
Convergence rate	$O(1/t)$ atau linear	Quadratic (doubles precision tiap step!)
Praktis untuk	$p$ sangat besar (deep learning)	$p$ moderate (econometrics)
Butuh Hessian?	Tidak	Ya

Quadratic convergence: dekat minimum, Newton’s method “squares” the error — jika error 0.1, setelah satu step error jadi $\approx 0.01$. Sangat cepat!

Connection: Newton-Raphson untuk MLE

Dalam econometrics, kita sering mau maximasi $\ell(\theta) = \sum_i \log p(y_i|\theta)$.

Newton-Raphson update:

\[\theta_{t+1} = \theta_t - [H_\ell(\theta_t)]^{-1} \nabla_\theta \ell(\theta_t)\]

di mana $H_\ell = \nabla^2 \ell$ adalah Hessian log-likelihood.

Koneksi: - Score function: $s(\theta) = \nabla \ell(\theta)$ - Observed information: $\mathcal{I}(\theta) = -H_\ell(\theta)$ - Fisher information: $\mathcal{I}_F(\theta) = \mathbb{E}[-H_\ell(\theta)]$

Newton-Raphson di log-likelihood = Newton’s method di negated log-likelihood.

IRLS (Iteratively Reweighted Least Squares) untuk GLM adalah Newton’s method di mana setiap step direduksi ke weighted OLS — efisien karena exploits struktur GLM.

7 Quasi-Newton Methods

Newton’s method mahal karena butuh compute dan invert Hessian ($O(p^3)$).

Quasi-Newton: approksimasi $H^{-1}$ tanpa menghitung Hessian secara eksplisit, hanya pakai gradient evaluations.

L-BFGS (Limited-memory BFGS): paling populer untuk medium-scale optimization: - Hanya simpan beberapa vektor gradient terakhir (bukan full Hessian) - Complexity $O(mp)$ per step dimana $m$ adalah memory parameter (typical $m = 10$) - Default optimizer di banyak software statistik: optim() di R, scipy.optimize.minimize di Python

8 Implementasi Sederhana

Worked Example: GD untuk Logistic Regression

# Gradient descent untuk logistic regression dari scratch
sigmoid <- function(z) 1 / (1 + exp(-z))

# Log-loss untuk logistic regression
log_loss <- function(beta, X, y) {
  p_hat <- sigmoid(X %*% beta)
  -mean(y * log(p_hat + 1e-10) + (1 - y) * log(1 - p_hat + 1e-10))
}

# Gradient dari log-loss
log_loss_grad <- function(beta, X, y) {
  p_hat <- sigmoid(X %*% beta)
  t(X) %*% (p_hat - y) / nrow(X)
}

# Mini-batch gradient descent
logistic_gd <- function(X, y, eta = 0.1, n_iter = 500,
                         batch_size = NULL, seed = 42) {
  set.seed(seed)
  n <- nrow(X)
  p <- ncol(X)
  beta <- rep(0, p)
  losses <- numeric(n_iter)

  if (is.null(batch_size)) batch_size <- n  # full batch

  for (t in seq_len(n_iter)) {
    # Sample mini-batch
    idx <- sample(n, min(batch_size, n))
    X_b <- X[idx, , drop = FALSE]
    y_b <- y[idx]

    # Gradient step
    grad <- log_loss_grad(beta, X_b, y_b)
    beta  <- beta - eta * grad
    losses[t] <- log_loss(beta, X, y)
  }
  list(beta = beta, losses = losses)
}

# Simulate data
set.seed(123)
n <- 500; p <- 5
X <- cbind(1, matrix(rnorm(n * (p - 1)), n, p - 1))
beta_true <- c(-1, 2, -1, 0.5, -0.5)
y <- rbinom(n, 1, sigmoid(X %*% beta_true))

# Fit dengan berbagai batch sizes
result_full <- logistic_gd(X, y, eta = 0.5, n_iter = 300, batch_size = NULL)
result_mini <- logistic_gd(X, y, eta = 0.1, n_iter = 300, batch_size = 32)
result_sgd  <- logistic_gd(X, y, eta = 0.01, n_iter = 300, batch_size = 1)

# Compare dengan glm()
glm_fit <- glm(y ~ X - 1, family = binomial)

cat("GD (full batch) beta:", round(result_full$beta, 3), "\n")
cat("GLM (IRLS) beta     :", round(coef(glm_fit), 3), "\n")

# Plot convergence
plot(result_full$losses, type = "l", col = "blue",
     xlab = "Iteration", ylab = "Log Loss",
     main = "Convergence Comparison", ylim = c(0.3, 1))
lines(result_mini$losses, col = "green")
lines(result_sgd$losses,  col = "red")
legend("topright",
       legend = c("Full Batch", "Mini-batch (B=32)", "SGD (B=1)"),
       col = c("blue", "green", "red"), lty = 1)

Perhatikan: glm() converge sangat cepat karena pakai IRLS (Newton’s method), bukan gradient descent!

Practice Problems

Problem 1: Manual GD

Minimasi $L(\theta_1, \theta_2) = \theta_1^2 + 2\theta_2^2$ dengan starting point $(\theta_1, \theta_2) = (3, 2)$ dan $\eta = 0.1$.

Hitung $\nabla L(\theta)$.
Lakukan 3 iterasi gradient descent secara manual. Catat $(\theta_1^{(t)}, \theta_2^{(t)})$ untuk $t = 0, 1, 2, 3$.
Apa nilai minimum $L$? Di titik mana?

Problem 2: Learning Rate Analysis

Untuk $L(\theta) = 5\theta^2$, gradient descent update adalah $\theta_{t+1} = \theta_t - \eta \cdot 10\theta_t = (1 - 10\eta)\theta_t$.

Untuk nilai $\eta$ berapa algorithm converge? (petunjuk: kapan $|1 - 10\eta| < 1$?)
Berapa learning rate optimal yang memberikan convergence paling cepat?
Apa yang terjadi jika $\eta = 0.2$?

Problem 3: Newton’s Method

Minimasi $L(\theta) = \theta^4 - 4\theta^2 + 4$.

Hitung $L'(\theta)$ dan $L''(\theta)$.
Temukan semua titik stasioner (set $L' = 0$).
Newton’s method update: $\theta_{t+1} = \theta_t - L'(\theta_t)/L''(\theta_t)$. Mulai dari $\theta_0 = 2.5$, lakukan 3 iterasi. Ke mana converge?
Mulai dari $\theta_0 = 0.1$, lakukan 3 iterasi. Ke mana converge? Apa yang terjadi?

Jawaban Problem 2:

$|1 - 10\eta| < 1 \Rightarrow -1 < 1 - 10\eta < 1 \Rightarrow 0 < \eta < 0.2$
$|1 - 10\eta|$ minimum (= 0) ketika $\eta = 0.1$. Ini optimal — converge dalam 1 langkah untuk quadratic!
$\eta = 0.2$: $1 - 10(0.2) = -1$. $\theta_{t+1} = -\theta_t$ — oscillates forever antara $\theta_0$ dan $-\theta_0$. Tidak converge!

9 Ringkasan Optimizer

Optimizer	Update Rule	Kapan Pakai
GD	$\theta - \eta g$	Convex, small $n$
SGD	$\theta - \eta g_i$	Large $n$, simple
Momentum	$\theta - v$, $v$ accumulates	Narrow valleys
Adam	Adaptive $\eta$ per parameter	Deep learning default
Newton	$\theta - H^{-1}g$	Small $p$, convex, MLE
L-BFGS	Newton approx	Medium $p$, statistical models

Selanjutnya: Regularization: Ridge, LASSO, Elastic Net →

--- title: "Gradient Descent & Optimization Algorithms" subtitle: "Mencari Minimum dalam Ruang Parameter" description: "Gradient descent, SGD, Adam, Newton's method, convergence rates, dan koneksi ke MLE dan IRLS." categories: [ml-math, optimization, algorithms] --- ::: {.callout-note title="Why This Matters for Your Work"} Optimization adalah mesin dari ML. Setiap kali kamu call `model.fit()`, `glm()`, atau `optim()`, kamu menjalankan beberapa variant dari gradient descent. Memahami optimization bukan hanya akademik — ini praktis: - **Mengapa model tidak converge?** Learning rate terlalu besar atau kecil. - **Mengapa training lambat?** Mungkin butuh momentum atau adaptive learning rate. - **Mengapa loss turun lalu naik lagi?** Kemungkinan learning rate terlalu besar, atau ada saddle point. - **Kapan pakai Newton's method vs gradient descent?** Newton lebih cepat tapi mahal komputasinya. Koneksi econometrics: Newton-Raphson untuk MLE adalah Newton's method pada negative log-likelihood. IRLS (Iteratively Reweighted Least Squares) untuk GLM adalah Newton's method dengan struktur khusus. ::: ## Masalah Optimization Setup umum: kita mau minimasi fungsi $L: \mathbb{R}^p \to \mathbb{R}$: $$\min_{\theta \in \mathbb{R}^p} L(\theta)$$ di mana $L$ adalah loss function (atau negative log-likelihood, atau whatever we're minimizing). **Kapan ada closed form?** Hanya untuk kasus khusus: - OLS: $L(\beta) = \|y - X\beta\|^2$ → $\hat{\beta} = (X^TX)^{-1}X^Ty$ - Ridge: $L(\beta) = \|y - X\beta\|^2 + \lambda\|\beta\|^2$ → $\hat{\beta} = (X^TX + \lambda I)^{-1}X^Ty$ Untuk hampir semua kasus lain (logistic regression, neural networks, dll.), tidak ada closed form → pakai iterative methods. ## Gradient Descent ### Intuisi Bayangkan kamu berdiri di pegunungan dalam kabut, mau turun ke lembah. Kamu tidak bisa lihat jauh, tapi bisa rasakan kemiringan tanah di sekitar kaki kamu. Strategi: selalu ambil satu langkah ke arah paling curam ke bawah. Itu persis gradient descent. ### Algoritma ::: {.callout-important title="Definisi: Gradient Descent"} Inisialisasi $\theta_0$ (random atau zero). Untuk $t = 0, 1, 2, \ldots$: $$\theta_{t+1} = \theta_t - \eta \nabla_\theta L(\theta_t)$$ di mana: - $\nabla_\theta L(\theta_t)$ adalah gradient dari $L$ di $\theta_t$ - $\eta > 0$ adalah **learning rate** (step size) Stop ketika $\|\nabla L(\theta_t)\| < \epsilon$ atau setelah $T$ iterasi. ::: **Kenapa negatif gradient?** Gradient menunjuk ke arah *naik* tercuram. Kita mau *turun*, jadi kita pergi ke arah *negatif* gradient. ### Learning Rate: The Critical Hyperparameter Learning rate $\eta$ adalah hyperparameter paling penting dalam gradient descent: **$\eta$ terlalu kecil:** - Convergence sangat lambat - Butuh banyak iterasi - Dalam practice: waste of compute **$\eta$ terlalu besar:** - "Overshoots" minimum - Loss bisa *diverge* (terus naik) - Algoritma tidak converge **$\eta$ tepat:** - Convergence smooth dan cepat ```{mermaid} graph LR A["η terlalu kecil"] -->|"konvergensi lambat"| B["butuh ribuan iterasi"] C["η tepat"] -->|"konvergensi stabil"| D["optimal dalam ratusan iterasi"] E["η terlalu besar"] -->|"diverge/oscillate"| F["loss tidak turun"] style C fill:#16a34a,color:#fff style E fill:#dc2626,color:#fff ``` ### Convergence untuk Convex Functions Untuk fungsi convex yang $L$-smooth (gradient Lipschitz dengan konstanta $L$) dan dengan learning rate $\eta = 1/L$: $$L(\theta_t) - L(\theta^*) \leq \frac{\|\theta_0 - \theta^*\|^2}{2\eta t} = O(1/t)$$ Ini **sublinear convergence** — untuk mencapai error $\epsilon$, butuh $O(1/\epsilon)$ iterasi. Untuk **strongly convex** functions ($\mu$-strongly convex), convergence lebih cepat: $$L(\theta_t) - L(\theta^*) \leq (1 - \mu\eta)^t [L(\theta_0) - L(\theta^*)]$$ Ini **linear convergence** — butuh $O(\log(1/\epsilon))$ iterasi. ::: {.callout-tip title="Worked Example: GD on Quadratic" collapse="true"} Minimasi $L(\theta) = \theta^2$. $\nabla L(\theta) = 2\theta$ Gradient descent update: $$\theta_{t+1} = \theta_t - \eta \cdot 2\theta_t = (1 - 2\eta)\theta_t$$ Dari $\theta_0$: $$\theta_t = (1 - 2\eta)^t \theta_0$$ **Convergence**: $\theta_t \to 0 = \theta^*$ jika dan hanya jika $|1 - 2\eta| < 1$, yaitu $0 < \eta < 1$. - $\eta = 0.4$: $1 - 2\eta = 0.2$, konvergensi lambat - $\eta = 0.5$: $1 - 2\eta = 0$, konvergen dalam **1 langkah**! - $\eta = 0.6$: $1 - 2\eta = -0.2$, oscillates tapi konvergen - $\eta = 1.0$: $1 - 2\eta = -1$, oscillates forever - $\eta = 1.5$: $|1 - 2\eta| = 2 > 1$, **diverges**! ```r # Implementasi sederhana gd_quadratic <- function(theta0, eta, n_iter = 50) { theta <- theta0 history <- numeric(n_iter + 1) history[1] <- theta for (t in seq_len(n_iter)) { grad <- 2 * theta # gradient of theta^2 theta <- theta - eta * grad history[t + 1] <- theta } history } # Coba berbagai learning rates eta_values <- c(0.1, 0.4, 0.9, 1.1) par(mfrow = c(2, 2)) for (eta in eta_values) { traj <- gd_quadratic(theta0 = 5, eta = eta, n_iter = 50) plot(traj, type = "l", main = paste("eta =", eta), xlab = "Iteration", ylab = "theta", ylim = c(-6, 6)) abline(h = 0, lty = 2, col = "red") } ``` ::: ## Variants dari Gradient Descent ### Batch Gradient Descent Setiap update menggunakan **semua $n$ sampel**: $$\nabla_\theta L(\theta) = \frac{1}{n}\sum_{i=1}^n \nabla_\theta L(y_i, f_\theta(x_i))$$ - **Pro**: gradient akurat, convergence smooth - **Con**: komputasi mahal untuk $n$ besar (harus scan seluruh dataset per step) - Disebut juga "full-batch GD" ### Stochastic Gradient Descent (SGD) Setiap update menggunakan **1 sampel** yang dipilih random: $$\nabla_\theta L(\theta) \approx \nabla_\theta L(y_i, f_\theta(x_i))$$ $$\theta_{t+1} = \theta_t - \eta \nabla_\theta L(y_{i_t}, f_\theta(x_{i_t}))$$ di mana $i_t$ dipilih uniform dari $\{1, \ldots, n\}$. - **Pro**: update sangat cepat ($O(1)$ per step vs $O(n)$), bisa escape saddle points karena noise - **Con**: gradient noisy, tidak converge ke minimum tapi berfluktuasi di sekitarnya - **Penting**: perlu decreasing learning rate $\eta_t \to 0$ untuk convergence teoritis (Robbins-Monro conditions) ### Mini-batch Gradient Descent Setiap update menggunakan **$B$ sampel** (batch size $B$, typically 32–512 dalam deep learning): $$\nabla_\theta L(\theta) \approx \frac{1}{B}\sum_{i \in \mathcal{B}_t} \nabla_\theta L(y_i, f_\theta(x_i))$$ - **Tradeoff**: antara batch GD (akurat, lambat) dan SGD (noisy, cepat) - Dalam practice: hampir semua deep learning pakai mini-batch GD - Disebut "SGD" dalam literature (meskipun teknisnya mini-batch) | Method | Gradient Estimate | Kecepatan per Step | Noise | |--------|------------------|-------------------|-------| | Batch GD | Exact | Lambat $O(n)$ | None | | SGD | $n\times$ noisy | Cepat $O(1)$ | Tinggi | | Mini-batch GD | Moderate noise | Moderate $O(B)$ | Moderate | ## Momentum **Problem dengan vanilla GD**: di lembah yang panjang dan sempit, GD zigzag dan konvergensi lambat. **Solusi: Momentum** — "ingat" arah update sebelumnya dan lanjutkan ke sana. ::: {.callout-important title="Definisi: Gradient Descent with Momentum"} $$v_{t+1} = \gamma v_t + \eta \nabla_\theta L(\theta_t)$$ $$\theta_{t+1} = \theta_t - v_{t+1}$$ di mana: - $v_t$ adalah velocity (momentum term) - $\gamma \in [0, 1)$ adalah momentum coefficient (typical: 0.9) - $v_0 = 0$ ::: **Intuitinya**: bayangkan bola menggelinding di permukaan. Bola punya inertia — tidak langsung berhenti, tapi terus melaju ke arah yang sama. Momentum di GD sama: terus bergerak ke arah yang sudah terbukti menurunkan loss. **Nesterov momentum** (slight improvement): hitung gradient di posisi "anticipated" bukan posisi sekarang: $$v_{t+1} = \gamma v_t + \eta \nabla_\theta L(\theta_t - \gamma v_t)$$ ## Adam Optimizer Adam (Adaptive Moment Estimation) adalah optimizer paling populer di deep learning. Menggabungkan momentum (first moment) dan adaptive learning rate (second moment). ::: {.callout-important title="Definisi: Adam Algorithm"} Inisialisasi: $m_0 = 0$, $v_0 = 0$, $t = 0$. Hyperparameter: $\eta = 0.001$, $\beta_1 = 0.9$, $\beta_2 = 0.999$, $\epsilon = 10^{-8}$. Untuk setiap step: **1. Compute gradient**: $g_t = \nabla_\theta L(\theta_t)$ **2. First moment estimate (momentum)**: $$m_t = \beta_1 m_{t-1} + (1 - \beta_1) g_t$$ **3. Second moment estimate (RMSProp)**: $$v_t = \beta_2 v_{t-1} + (1 - \beta_2) g_t^2$$ **4. Bias correction** (karena $m_0 = v_0 = 0$): $$\hat{m}_t = \frac{m_t}{1 - \beta_1^t}, \quad \hat{v}_t = \frac{v_t}{1 - \beta_2^t}$$ **5. Update**: $$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{\hat{v}_t} + \epsilon} \hat{m}_t$$ ::: **Kenapa bias correction?** Pada awal training ($t$ kecil), $m_t$ dan $v_t$ under-estimate moment sesungguhnya karena diinisialisasi dari 0. Correction $1/(1-\beta^t)$ mengoreksi ini. **Mengapa Adam efektif?** - Parameter dengan gradient besar mendapat learning rate kecil (tidak overshoot) - Parameter dengan gradient kecil mendapat learning rate besar (tidak stagnate) - Momentum mengurangi zigzagging - Secara efektif, setiap parameter punya adaptive learning rate sendiri ::: {.callout-tip title="Worked Example: Adam pada Simple Function" collapse="true"} ```r # Implementasi Adam dari scratch adam_optimizer <- function(L_grad, # fungsi gradient(theta) theta0, eta = 0.001, beta1 = 0.9, beta2 = 0.999, eps = 1e-8, n_iter = 1000) { theta <- theta0 m <- rep(0, length(theta)) v <- rep(0, length(theta)) history_loss <- numeric(n_iter) for (t in seq_len(n_iter)) { g <- L_grad(theta) # gradient m <- beta1 * m + (1 - beta1) * g # first moment v <- beta2 * v + (1 - beta2) * g^2 # second moment m_hat <- m / (1 - beta1^t) # bias correction v_hat <- v / (1 - beta2^t) theta <- theta - eta * m_hat / (sqrt(v_hat) + eps) # update history_loss[t] <- sum(theta^2) # track loss } list(theta = theta, history_loss = history_loss) } # Test: minimize L(theta) = theta1^2 + 10*theta2^2 # Gradient: [2*theta1, 20*theta2] grad_fn <- function(theta) c(2 * theta[1], 20 * theta[2]) result <- adam_optimizer(L_grad = grad_fn, theta0 = c(5, 5), eta = 0.1, n_iter = 500) cat("Final theta:", result$theta, "\n") plot(result$history_loss, type = "l", log = "y", xlab = "Iteration", ylab = "Loss (log scale)", main = "Adam Convergence") ``` ::: ## Newton's Method (Second-Order) Gradient descent hanya menggunakan first-order information (gradient). Newton's method menggunakan first AND second order (Hessian). ::: {.callout-important title="Definisi: Newton's Method"} $$\theta_{t+1} = \theta_t - H^{-1}(\theta_t) \nabla L(\theta_t)$$ di mana $H(\theta) = \nabla^2 L(\theta)$ adalah **Hessian matrix** ($p \times p$). ::: **Intuisi**: Newton's method locally approximates $L$ dengan quadratic: $$L(\theta) \approx L(\theta_t) + \nabla L(\theta_t)^T(\theta - \theta_t) + \frac{1}{2}(\theta - \theta_t)^T H(\theta_t) (\theta - \theta_t)$$ Meminimasi quadratic approximation ini langsung memberikan update Newton. **Pro vs Con Newton's method:** | Aspek | Gradient Descent | Newton's Method | |-------|-----------------|-----------------| | Per-step cost | $O(p)$ | $O(p^2)$ untuk Hessian, $O(p^3)$ untuk invers | | Convergence rate | $O(1/t)$ atau linear | Quadratic (doubles precision tiap step!) | | Praktis untuk | $p$ sangat besar (deep learning) | $p$ moderate (econometrics) | | Butuh Hessian? | Tidak | Ya | **Quadratic convergence**: dekat minimum, Newton's method "squares" the error — jika error 0.1, setelah satu step error jadi $\approx 0.01$. Sangat cepat! ::: {.callout-caution title="Connection: Newton-Raphson untuk MLE"} Dalam econometrics, kita sering mau maximasi $\ell(\theta) = \sum_i \log p(y_i|\theta)$. Newton-Raphson update: $$\theta_{t+1} = \theta_t - [H_\ell(\theta_t)]^{-1} \nabla_\theta \ell(\theta_t)$$ di mana $H_\ell = \nabla^2 \ell$ adalah Hessian log-likelihood. Koneksi: - **Score function**: $s(\theta) = \nabla \ell(\theta)$ - **Observed information**: $\mathcal{I}(\theta) = -H_\ell(\theta)$ - **Fisher information**: $\mathcal{I}_F(\theta) = \mathbb{E}[-H_\ell(\theta)]$ Newton-Raphson di log-likelihood = Newton's method di negated log-likelihood. **IRLS** (Iteratively Reweighted Least Squares) untuk GLM adalah Newton's method di mana setiap step direduksi ke weighted OLS — efisien karena exploits struktur GLM. ::: ## Quasi-Newton Methods Newton's method mahal karena butuh compute dan invert Hessian ($O(p^3)$). **Quasi-Newton**: approksimasi $H^{-1}$ tanpa menghitung Hessian secara eksplisit, hanya pakai gradient evaluations. **L-BFGS** (Limited-memory BFGS): paling populer untuk medium-scale optimization: - Hanya simpan beberapa vektor gradient terakhir (bukan full Hessian) - Complexity $O(mp)$ per step dimana $m$ adalah memory parameter (typical $m = 10$) - Default optimizer di banyak software statistik: `optim()` di R, `scipy.optimize.minimize` di Python ## Implementasi Sederhana ::: {.callout-tip title="Worked Example: GD untuk Logistic Regression" collapse="true"} ```r # Gradient descent untuk logistic regression dari scratch sigmoid <- function(z) 1 / (1 + exp(-z)) # Log-loss untuk logistic regression log_loss <- function(beta, X, y) { p_hat <- sigmoid(X %*% beta) -mean(y * log(p_hat + 1e-10) + (1 - y) * log(1 - p_hat + 1e-10)) } # Gradient dari log-loss log_loss_grad <- function(beta, X, y) { p_hat <- sigmoid(X %*% beta) t(X) %*% (p_hat - y) / nrow(X) } # Mini-batch gradient descent logistic_gd <- function(X, y, eta = 0.1, n_iter = 500, batch_size = NULL, seed = 42) { set.seed(seed) n <- nrow(X) p <- ncol(X) beta <- rep(0, p) losses <- numeric(n_iter) if (is.null(batch_size)) batch_size <- n # full batch for (t in seq_len(n_iter)) { # Sample mini-batch idx <- sample(n, min(batch_size, n)) X_b <- X[idx, , drop = FALSE] y_b <- y[idx] # Gradient step grad <- log_loss_grad(beta, X_b, y_b) beta <- beta - eta * grad losses[t] <- log_loss(beta, X, y) } list(beta = beta, losses = losses) } # Simulate data set.seed(123) n <- 500; p <- 5 X <- cbind(1, matrix(rnorm(n * (p - 1)), n, p - 1)) beta_true <- c(-1, 2, -1, 0.5, -0.5) y <- rbinom(n, 1, sigmoid(X %*% beta_true)) # Fit dengan berbagai batch sizes result_full <- logistic_gd(X, y, eta = 0.5, n_iter = 300, batch_size = NULL) result_mini <- logistic_gd(X, y, eta = 0.1, n_iter = 300, batch_size = 32) result_sgd <- logistic_gd(X, y, eta = 0.01, n_iter = 300, batch_size = 1) # Compare dengan glm() glm_fit <- glm(y ~ X - 1, family = binomial) cat("GD (full batch) beta:", round(result_full$beta, 3), "\n") cat("GLM (IRLS) beta :", round(coef(glm_fit), 3), "\n") # Plot convergence plot(result_full$losses, type = "l", col = "blue", xlab = "Iteration", ylab = "Log Loss", main = "Convergence Comparison", ylim = c(0.3, 1)) lines(result_mini$losses, col = "green") lines(result_sgd$losses, col = "red") legend("topright", legend = c("Full Batch", "Mini-batch (B=32)", "SGD (B=1)"), col = c("blue", "green", "red"), lty = 1) ``` Perhatikan: `glm()` converge sangat cepat karena pakai IRLS (Newton's method), bukan gradient descent! ::: ::: {.callout-warning title="Practice Problems" collapse="true"} **Problem 1: Manual GD** Minimasi $L(\theta_1, \theta_2) = \theta_1^2 + 2\theta_2^2$ dengan starting point $(\theta_1, \theta_2) = (3, 2)$ dan $\eta = 0.1$. (a) Hitung $\nabla L(\theta)$. (b) Lakukan 3 iterasi gradient descent secara manual. Catat $(\theta_1^{(t)}, \theta_2^{(t)})$ untuk $t = 0, 1, 2, 3$. (c) Apa nilai minimum $L$? Di titik mana? --- **Problem 2: Learning Rate Analysis** Untuk $L(\theta) = 5\theta^2$, gradient descent update adalah $\theta_{t+1} = \theta_t - \eta \cdot 10\theta_t = (1 - 10\eta)\theta_t$. (a) Untuk nilai $\eta$ berapa algorithm converge? (petunjuk: kapan $|1 - 10\eta| < 1$?) (b) Berapa learning rate optimal yang memberikan convergence paling cepat? (c) Apa yang terjadi jika $\eta = 0.2$? --- **Problem 3: Newton's Method** Minimasi $L(\theta) = \theta^4 - 4\theta^2 + 4$. (a) Hitung $L'(\theta)$ dan $L''(\theta)$. (b) Temukan semua titik stasioner (set $L' = 0$). (c) Newton's method update: $\theta_{t+1} = \theta_t - L'(\theta_t)/L''(\theta_t)$. Mulai dari $\theta_0 = 2.5$, lakukan 3 iterasi. Ke mana converge? (d) Mulai dari $\theta_0 = 0.1$, lakukan 3 iterasi. Ke mana converge? Apa yang terjadi? --- **Jawaban Problem 2:** (a) $|1 - 10\eta| < 1 \Rightarrow -1 < 1 - 10\eta < 1 \Rightarrow 0 < \eta < 0.2$ (b) $|1 - 10\eta|$ minimum (= 0) ketika $\eta = 0.1$. Ini optimal — converge dalam **1 langkah** untuk quadratic! (c) $\eta = 0.2$: $1 - 10(0.2) = -1$. $\theta_{t+1} = -\theta_t$ — oscillates forever antara $\theta_0$ dan $-\theta_0$. Tidak converge! ::: ## Ringkasan Optimizer | Optimizer | Update Rule | Kapan Pakai | |-----------|-------------|-------------| | GD | $\theta - \eta g$ | Convex, small $n$ | | SGD | $\theta - \eta g_i$ | Large $n$, simple | | Momentum | $\theta - v$, $v$ accumulates | Narrow valleys | | Adam | Adaptive $\eta$ per parameter | Deep learning default | | Newton | $\theta - H^{-1}g$ | Small $p$, convex, MLE | | L-BFGS | Newton approx | Medium $p$, statistical models | --- **Selanjutnya:** [Regularization: Ridge, LASSO, Elastic Net →](03-regularization.qmd)