What is the difference between implicit and explicit stochastic gradient descent?

Question

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.

Answer 1

...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.