4
$\begingroup$

While reading the implicit stochastic gradient descent, I get stuck by its update:

$$w^{new}:=w^{old} - \eta \nabla Q_{i} (w^{new}) $$

I learned from this slide that the above is the implicit style of SGD which can be written as this:

$$\theta_{k+1} = \theta_k - \gamma_k \nabla_k f_i(\theta_{k+1})$$

But I wonder how we can use $\theta_{k+1}$ before even defining it? How does it differ from the explicit stochastic gradient descent in implementation? Why do we need implicit SGD? A simple example for illustration would be very appreciated.

$\endgroup$
1
  • $\begingroup$ One method is suggested in the description of SAG a few slides further. at each step you iterate until the implicit equation is achieved (eg starting with regular gradient descent step as initial guess???). The problem I believe its aiming to tackle is a high condition number for your Hessian of the objective function - causing high curvature in certain directions and low curvature in others. which means you need a very small learning rate (to not oscillate in high curvature, but then slow convergence in low curvature directions) $\endgroup$
    – seanv507
    Apr 25, 2021 at 8:55

1 Answer 1

1
$\begingroup$

...how we can use $\theta_{k+1}$ before even defining it?

It's actually defined by the update rule:

$$ \theta_{k+1} = \theta_k - \gamma_k \nabla f(\theta_{k+1}) $$

What you do is you search for a $\theta_{k+1}$ that satisfies this equation. You could also rewrite this as follows:

$$ \begin{aligned} &\text{Find }\theta_{k+1}\text{ such that:}\\ &h(\theta_{k+1}) = \theta_{k+1} - \left[ \theta_k - \gamma_k \nabla f(\theta_{k+1}) \right] = 0 \end{aligned} $$

To solve this, one could use any root finding method, including fixed-point iteration, as suggested in the comments:

  1. Start from a guess $\theta_{k+1}^{(0)}$.
  2. Update the guess: $\theta_{k+1}^{(1)} = h(\theta_{k+1}^{(0)})$.
  3. Loop step (2) until $\theta_{k+1}^{(n)}$ stops changing.
  4. You found $\theta_{k+1} \equiv \theta_{k+1}^{(n)}$.

Each step of such a fixed-point iteration requires evaluation of the gradient $\nabla f(\theta_{k+1}^{(n)})$, which could be really computationally intensive.


Why do we need implicit SGD?

The paper below shows that:

  1. Implicit and explicit SGD are asymptotically unbiased (Theorem 4.1).
  2. Both algorithms provide the same asymptotic efficiency (Thm. 4.2).
  3. Similarly to implicit Euler method for solving differential equations, implicit SGD is more stable (section 4.3):

...in the standard SGD procedure, the effect from the initial conditions can be amplified in an exponentially large way before fading out, if the learning rate is misspecified...

...the effects of the initial conditions monotonically decrease in the implicit method...

Seems like the main advantage of implicit SGD compared to the regular explicit one is increased stability of the algorithm.

References

  • Toulis, Panagiotis, Jason Rennie, and Edoardo M Airoldi. 2014. "Statistical Analysis of Stochastic Gradient Methods for Generalized Linear Models." In Proceedings of the 31st International Conference on Machine Learning, edited by Eric P. Xing and Tony Jebara, 32:667–75. Bejing, China: PMLR. https://proceedings.mlr.press/v32/toulis14.html.
$\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.