9
$\begingroup$

The follow-the-regularized-leader proximal gradient descent uses this update step:

$$w_{t+1}= argmin_w( w\cdot \sum_{s=1}^t g_s +\frac{1}{2}\sum_{s=1}^t\sigma_s(w-w_s)^2+\lambda_1|w| )$$

  • We are on the $t+1$ round, we have already seen $t$ data points.

  • $g_s$ is the gradient for the $s$ sample.

  • $\sigma_s$ is a non-increasing learning rate, defined as $\sum_{s=1}^t\sigma_s=\sqrt{t}$

  • and finally $\lambda_1$ is a regularization term.

Can you give a geometric/physical/other simple intuition for what are we doing with the first 2 terms? Does the first one represent some kind of momentum? Does the second one require that our new location be different than our previous locations?

Please be patient if this seems to you like an attempt in over-simplifying a heavy theory...

$\endgroup$
1
  • $\begingroup$ the first 2 terms are actually Mirror Descent which consider all history updates. the last term is just l1 regularization which help get sparsity $\endgroup$
    – Kuo
    Jul 22, 2021 at 7:13

2 Answers 2

2
$\begingroup$

Following McMahan's Follow-the-Regularized-Leader and Mirror Descent: Equivalence theorems.

The paper shows that the simple gradient descent update rule can be written in a very similar way to the above rule.

The intuitive update rule of FOBOS (a gradient descent variant) is:

$$x_{t+1} = argmin_x[g_tx + \frac{1}{2\mu_t}|x-x_t|^2]$$

where

  • $g_t$ is the gradient for the previous sample $t$ - we want to move in a that direction as it decreases the loss of our hypothesis on that sample.
  • However, we don't want to change our hypothesis $x_t$ too much (for fear of predicting badly on examples we have already seen). $\mu_t$ is a step size for this sample, and it should make each step more conservative.

We can find where the derivative is 0 and get an explicit update rule:

$$x_{t+1}=x_t-\mu_tg_t$$

The paper goes on to show that the same intuitive update rule above can be also written as:

$$x_{t+1} = argmin_x[ g_{1:t}x + \phi_{1:t-1}x+\psi(x) + \frac{1}{2}\sum_{s=1}^t{|x-x_s|^2}]$$

Which is pretty similar to the FTRL-proximal formulation. In fact, the gradient part (1st term) and the proximal strong convexity (3rd term) are the same, and these were the interesting parts for me.

$\endgroup$
1
  • $\begingroup$ As the paper goes into technical details that were beyond me, I would be glad if someone can check this answer and make sure this explanation makes sense... $\endgroup$
    – ihadanny
    Feb 10, 2016 at 18:46
1
$\begingroup$

for FOBOS, the original formulation is basically an extension of SGD: http://stanford.edu/~jduchi/projects/DuchiSi09c_slides.pdf

the FTRL paper tries to give a unified view by formulating the Duchi closed-form update in a similar fashion to FTRL. the term g*x (also mentioned in ihadanny's answer) is a bit weird, but if u work from the above pdf, it's pretty clear:

on page 8 of the above pdf, if we ignore the regularization term R for now,

$$ \begin{eqnarray} \mathbf{w}_{t+1} &= &argmin_{\mathbf{w}} \{\frac{1}{2} \| \mathbf{w} - \mathbf{w}_{t+1/2} \|^2 \} \\ &=&argmin_{\mathbf{w}} \{\frac{1}{2} \| \mathbf{w} - (\mathbf{w}_{t} - \eta \mathbf{g}_t) \|^2 \} \mbox{considering page 7 of the Duchi pdf}\\ & = & (\mathbf{w} - \mathbf{w}_t)^t(\mathbf{w} - \mathbf{w}_t) + 2\eta (\mathbf{w} - \mathbf{w}_t)^t\mathbf{g}_t + \eta^2 \mathbf{g}_t^t\mathbf{g}_t \end{eqnarray} $$

the $\mathbf{w}_t$ and $\mathbf{g}_t$ above are all constants for the argmin, so are ignored, then you have the form given by ihadanny

the $\mathbf{w} \mathbf{g}_t$ form makes sense (after the above equivalence derivation from the Duchi form), but in this form it is very unintuitive, and even more so is the $\mathbf{g}_{1:t}\mathbf{w}$ form in the FTRL paper. to understand the FTRL formula in the more intuitive Duchi form, note that the major difference between FTRL and FOBOS is simply the $\mathbf{g}_{1:t}$ -> $\mathbf{g}_{t}$ (see https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37013.pdf note there is actually a typo for FOBOS in the table on page 2, you should look at the equations in the paragraphs) then just change $\mathbf{g}_{t}$ to $\mathbf{g}_{1:t}$ in the above equivalence derivation, and you will find that FTRL is basically the closed-form FOBOS update with a more "conservative" for the value of $\mathbf{g}_{t}$ by using the average of $\mathbf{g}_{1:t}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.