{"id":48,"date":"2016-03-20T02:06:20","date_gmt":"2016-03-20T02:06:20","guid":{"rendered":"http:\/\/www.aarondefazio.com\/tangentially\/?p=48"},"modified":"2016-03-20T02:06:20","modified_gmt":"2016-03-20T02:06:20","slug":"finally-an-alternative-to-sgd-stochastic-variance-reduction-methods","status":"publish","type":"post","link":"https:\/\/www.aarondefazio.com\/tangentially\/?p=48","title":{"rendered":"Finally an alternative to SGD: Stochastic variance reduction methods"},"content":{"rendered":"

<\/p>\n

This post describes the newly developed class of variance reduction techniques in
\nstochastic optimisation, which are fast and simple alternatives to the traditional
\nstochastic gradient descent (SGD) method. I give a light introduction here, focused
\non actually applying the methods in practice.\n<\/p>\n

<\/p>\n

\n

<\/a>But first: Ye Old SGD<\/h3>\n

<\/p>\n

Quite possibly the most important algorithm in machine learning, SGD is simply a
\nmethod for optimizing objective functions that consist of a sum or average of
\nterms:\n<\/p>\n

\n f<\/mi>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow> =<\/mo> 1<\/mn><\/mrow> \nn<\/mi><\/mrow><\/mfrac>\u2211<\/mo>\n <\/mrow>i<\/mi>=<\/mo>1<\/mn><\/mrow>n<\/mi><\/mrow><\/munderover \n>f<\/mi><\/mrow>\ni<\/mi><\/mrow><\/msub \n>(<\/mo>x<\/mi><\/mrow>)<\/mo><\/mrow>.<\/mo>\n<\/mrow><\/math><\/div>\n

<\/p>\n

\n

<\/p>\n

The SGD method maintains an estimate
\nx<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/math> of the solution
\nat step k<\/mi><\/math>,
\nand at each step:<\/p>\n

<\/p>\n

\n
    \n
  1. Sample: <\/span>Pick an index j<\/mi><\/math>
    \n uniformly at random (a datapoint index).\n <\/li>\n
  2. Step: <\/span>Update x<\/mi><\/math>:\n
    \n x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> =<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> \u03b3<\/mi>f<\/mi><\/mrow>j<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msubsup \n>(<\/mo>x<\/mi><\/mrow>\nk<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow>.<\/mo>\n<\/mrow><\/math><\/div>\n

    <\/p>\n

    \n<\/li>\n<\/ol><\/div>\n

    <\/span>
    \n<\/p>\n

    At it’s most basic, this update is just an approximation of the
    \nclassical gradient descent technique, where we take the non-random step
    \nx<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msub \n> =<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n> \u2212<\/mo> \u03b3<\/mi>f<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msub \n><\/mrow>)<\/mo><\/mrow>.<\/mo><\/math> The step size
    \nparameter \u03b3<\/mi><\/math>
    \nhere is just a constant, which depending on the problem may need to be adjusted
    \ndown at each step. Variance reduction methods build upon SGD by modifying the
    \ncore update in various ways.\n<\/p>\n

    <\/p>\n

    \n

    <\/a>SAGA<\/h3>\n

    <\/p>\n

    The SAGA method<\/a> is a simple modi\ufb01cation of SGD, where we remember
    \nthe last gradient evaluated for each datapoint<\/span>, and use this
    \nto correct the SGD step to reduce its variance. These past gradients are stored in a table. We denote the previous gradient for datapoint j as f<\/mi><\/mrow>j<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msubsup>(<\/mo>\u03d5<\/mi><\/mrow>j<\/mi><\/mrow>k<\/mi><\/mrow><\/msubsup><\/mrow>)<\/mo><\/mrow><\/math>.
    \nThe core step is as<\/p>\n

    follows:<\/p>\n

    \n
      \n
    1. Sample: <\/span>Pick an index j<\/mi><\/math>
      \n uniformly at random.\n <\/li>\n
    2. Step: <\/span>Update x<\/mi><\/math>
      \n using f<\/mi><\/mrow>j<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msubsup \n>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow><\/math>,
      \n f<\/mi><\/mrow>j<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msubsup \n>(<\/mo>\u03d5<\/mi><\/mrow>j<\/mi><\/mrow>k<\/mi><\/mrow><\/msubsup \n><\/mrow>)<\/mo><\/mrow><\/math>
      \n and the table average: <\/p>\n\n\n
      \n \n <\/mstyle>x<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msup \n> =<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msup \n> \u2212<\/mo> \u03b3<\/mi> f<\/mi><\/mrow>\nj<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msubsup \n>(<\/mo>x<\/mi><\/mrow>k<\/mi><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow> \u2212<\/mo> f<\/mi><\/mrow>\nj<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msubsup \n>(<\/mo>\u03d5<\/mi><\/mrow>\nj<\/mi><\/mrow>k<\/mi><\/mrow><\/msubsup \n><\/mrow>)<\/mo><\/mrow> +<\/mo> 1<\/mn><\/mrow> \nn<\/mi><\/mrow><\/mfrac>\u2211<\/mo>\n <\/mrow>i<\/mi>=<\/mo>1<\/mn><\/mrow>n<\/mi><\/mrow><\/munderover \n>f<\/mi><\/mrow>\ni<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msubsup \n>(<\/mo>\u03d5<\/mi><\/mrow>\ni<\/mi><\/mrow>k<\/mi><\/mrow><\/msubsup \n><\/mrow>)<\/mo><\/mrow><\/mrow><\/mfenced>,<\/mo>\n<\/math><\/td>\n(1)<\/td>\n<\/tr>\n<\/table>\n

      <\/p>\n

      \n<\/li>\nUpdate the table: <\/span>Denote \u03d5<\/mi><\/mrow>j<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msubsup \n> =<\/mo> x<\/mi><\/mrow>k<\/mi><\/mrow><\/msup \n><\/math>,
      \n and store f<\/mi><\/mrow>j<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msubsup \n>(<\/mo>\u03d5<\/mi><\/mrow>j<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msubsup \n><\/mrow>)<\/mo><\/mrow><\/math>
      \n in the table. All other entries in the table remain unchanged. The quantity
      \n \u03d5<\/mi><\/mrow>j<\/mi><\/mrow>k<\/mi>+<\/mo>1<\/mn><\/mrow><\/msubsup \n><\/math>
      \n is not explicitly stored.\n <\/li>\n<\/ol><\/div>\n

      <\/span>
      \n<\/p>\n

      Source code for SAGA and the accelerated variant point-saga is available on github<\/a>. Some points about the algorithm: <\/p>\n