MLlib - Optimization Module - Updater

@(Hadoop & Spark)[machine learning|algorithm|statistics|Spark]

Topic: Updater - SquaredL2Updater

Inference

• Optimization Equation
  $$l(x, w, \lambda) = \frac{1}{2}\sum_{n=1}^{N}{\{t_n-w^T\phi(x_n)\}} + \frac{\lambda}{2}w^Tw$$
• Gradient Computation
  $$gradient.compute(x_i,y_i,w,g_i)$$
  $$\frac{\partial(x,w,\lambda)}{\partial w_i} = g_i + \lambda w_i$$
• SGD Updater
  $$w_{new} = w_{old} - \sigma(g_i+\lambda w_i)$$

Reference

Bishop CM. Pattern Recognition and Machine Learning. (Jordan M, Kleinberg J, Schölkopf B, eds.). Springer; 2006:738. doi:10.1117/1.2819119. Page144 - Regulariz ed least squares

Code annotation

/**
 * :: DeveloperApi ::
 * Updater for L2 regularized problems.
 *          R(w) = 1/2 ||w||^2
 * Uses a step-size decreasing with the square root of the number of iterations.
 */
@DeveloperApi
class SquaredL2Updater extends Updater {
  override def compute(
      weightsOld: Vector,
      gradient: Vector,
      stepSize: Double,
      iter: Int,
      regParam: Double): (Vector, Double) = {
    // add up both updates from the gradient of the loss (= step) as well as
    // the gradient of the regularizer (= regParam * weightsOld)
    // w' = w - thisIterStepSize * (gradient + regParam * w)
    // w' = (1 - thisIterStepSize * regParam) * w - thisIterStepSize * gradient
    val thisIterStepSize = stepSize / math.sqrt(iter)
    val brzWeights: BV[Double] = weightsOld.toBreeze.toDenseVector
    brzWeights :*= (1.0 - thisIterStepSize * regParam)
    brzAxpy(-thisIterStepSize, gradient.toBreeze, brzWeights)
    val norm = brzNorm(brzWeights, 2.0)

    (Vectors.fromBreeze(brzWeights), 0.5 * regParam * norm * norm)
  }
}