Neural Sync Active

Randomized Optimization

Registry Synced

Randomized Optimization

117 words

1 min read

Reading compass

Now · 10.1 Stochastic Gradient Descent

Randomized Optimization

10.1 Stochastic Gradient Descent

\mathbf{w}^{(t+1)} = \mathbf{w}^{(t)} - \eta_t \nabla \ell(\mathbf{w}^{(t)}; x_{i_t}, y_{i_t})

Convergence:

E[||\nabla f(\mathbf{w}_t)||^2] \leq O(1/\sqrt{t})


python
import numpy as np
def sgd(X, y, lr=0.1, epochs=100):
    n, p = X.shape
    w = np.zeros(p)
    for t in range(epochs * n):
        idx = np.random.randint(n)
        grad = 2 * X[idx] * (X[idx] @ w - y[idx])
        w -= lr * grad / np.sqrt(t + 1)
    return w

10.2 SVRG (Stochastic Variance Reduced Gradient)

Maintains a snapshot of the full gradient periodically, reducing variance at each step.

10.3 Convergence Comparison

Method	Convergence Rate	Per-Iteration Cost
Full GD	$O(1/\sqrt{T})$	$O(n)$
SGD	$O(1/\sqrt{T})$	$O(1)$
SVRG	$O(1/T)$	$O(1)$

Join Discord PreviousHyperLogLogNextCount Sketch

Randomized Optimization

Randomized Optimization

10.1 Stochastic Gradient Descent

10.2 SVRG (Stochastic Variance Reduced Gradient)

10.3 Convergence Comparison

Intelligence Hub