Gradient Descent

Gradient Descent is an algorithm for online linear regression. In the simplest case, the algorithm predicts a sequence of numbers $ y_t\in[0,1] $. The prediction space is $ [0,1] $. The master's prediction is the weighted average of the input vectors $x_t$. At each step the weights are updated by the rule, which depends on the gradient of a loss function: $w^k_{t+1} := w^k_t - \eta \lambda_\gamma^{'}(\omega_t,\gamma_{t}) \gamma^k_t$.

For the bounded signal $x: ||x_t||_2 \le B$ and convex twice differentiable by the second argument loss function the Gradient Descent algorithm can achieve

$L_T \le L_T(\theta) + BLU\sqrt{T}$,

where $L_T(\theta)$ is the loss of any linear function of $x$, and $L$ is a bound for the derivative of the loss function: $ |\nabla_\gamma\lambda(\omega_t,\gamma_{t})| \le L$. The best $\eta=U \slash{} (BL\sqrt{T})$. Here $U$ us the norm of the experts: $ ||\theta||_2\le U$

The Gradient Descent algorithm was intestigated for this problem by Cesa-Bianchi et al. (1994), and is also known as Least Mean Squares algorithm for the square-loss function.

Bibliography

  • N. Cesa-Bianchi, P.M. Long, and M.K. Warmuth: Worst-case quadratic loss bounds for prediction using linear functions and gradient descent. IEEE Transactions on Neural Networks, 7(3):604-619, 1996.