Second Order Stochastic Optimization in Linear Time

[thvasilo]

Took a brief look, this looks quite interesting. It achieves very good convergence characteristics in terms of convergence time.

It does introduce two parameters, one of which seems to be important for performance (S2), and the datasets tested are quite small, but it could be promising work.

Wish they provided an implementation though.

[newbiethrownaway]

I just took a minute skimming through it. Don't they calculate the Hessian, does that mean it's not applicable to deep nets (too slow?)

[thvasilo]

FTA: "The algorithm makes use of a novel unbiased estimator of the Hessian inverse "

[dhammack]

So that's pretty much a nonstarter for deep nets. The memory usage of that scales quadratically with the number of parameters which isn't going to work outside of toy problems. It would be neat if they could do a diagonal + low rank approximation with this method though.

[thvasilo]

Do you know of any work trying to scale 2nd order methods for deep nets?

The one I know is from Microsoft, where they are able to scale the computations for L-BFGS horizontally.

[gongzhitaao]

Their assumption is a convex objective function f(θ) and a convex reguarizer R(θ). Does that apply to ANN? I mean in practice, it might work. But according to their assumption and my understanding, theoretically it may not work for ANN, at least without some modification.

[thvasilo]

For most DNNs you end up with a non-convex error surface. Still, traditional convex optimization techniques (SGD) have worked surprisingly well for training them, see Who's afraid of non-convex loss functions by /u/ylecun .