Online Newton algorithm in optax?

[eserie]

Do you think optax could have an implementation of the online newton algorithm as in [1] ?

[1] Hazan, E., Agarwal, A. and Kale, S., 2007. Logarithmic regret algorithms for
online convex optimization. Machine Learning, 69(2-3), pp.169-192

[mkunesch]

Hi! This looks interesting - thanks!
Judging by a first look, this would probably not be a standard optax optimizer (i.e. gradient transformation) but it could consist of new utility functions in the second_order module.

I don't think we currently have the capacity to implement this, but we would welcome contributions if you are keen to implement it or already have an implementation! Since it probably requires a few non-standard decisions, it would be good to outline the design before writing everything so that we could review and discuss it.

Thanks a lot again for the suggestion!

[eserie]

Hi,
thanks for your interest!
In fact it's a first order method in the sens that it only need gradients. However it exploits strong-convexity (or exp-concavity) of the function to optimize to converge faster.

If you want to have a look, I 've already implemented an optax extension in wax-ml: https://github.com/eserie/wax-ml/blob/main/wax/optim/newton.py
I have also some working examples with online learning experiments for time-series prediction where I compare the optimizer with others from optax.

[mkunesch]

Hi!

In fact it's a first order method in the sens that it only need gradients.
Ah nice - I clearly misread the paper 😅.

The implementation looks great - would you like to file a PR? It would be great to have this in optax!

[eserie]

Sure! I will prepare a PR in coming days!

[eserie]

I created the PR #258.