MATLABOctave library for stochastic optimization algorithms

# SGDLibrary : Stochastic Optimization Algorithm Library in MATLAB/Octave ---------- Authors: [Hiroyuki Kasai](http://kasai.comm.waseda.ac.jp/kasai/) Last page update: November 20, 2020 Latest library version: 1.0.20 (see Release notes for more info) <br /> Announcement ---------- We are very welcome to your contribution. Please tell us - Stochastic optimization solvers written by MATLAB, and - your comments and suggestions. <br /> Introduction ---------- The SGDLibrary is a **pure-MATLAB** library or toolbox of a collection of **stochastic optimization algorithms**. This solves an unconstrained minimization problem of the form, min f(x) = sum_i f_i(x). The SGDLibrary is also operable on [GNU Octave](https://www.gnu.org/software/octave/) (Free software compatible with many MATLAB scripts). Note that this SGDLibrary internally contains the [GDLibrary](https://github.com/hiroyuki-kasai/GDLibrary). <br /> Document ---------- The document of SGDLibrary can be obtained from below; - H. Kasai, "[SGDLibrary: A MATLAB library for stochastic optimization algorithms](http://www.jmlr.org/papers/v18/17-632.html)," Journal of Machine Learning Research (JMLR), vol.18, no.215, 2018 (arXiv preprint [arXiv:1710.10951](https://arxiv.org/abs/1710.10951)). <br /> ## <a name="supp_solver"> List of the algorithms available in SGDLibrary </a> - **SGD variants** (stochastic gradient descent) - Vanila SGD - H. Robbins and S. Monro, "[A stochastic approximation method](https://www.jstor.org/stable/pdf/2236626.pdf)," The annals of mathematical statistics, vol. 22, no. 3, pp. 400-407, 1951. - L. Bottou, "[Online learning and stochastic approximations](http://leon.bottou.org/publications/pdf/online-1998.pdf)," Edited by David Saad, Cambridge University Press, Cambridge, UK, 1998. - SGD-CM (SGD with classical momentum) - SGD-CM-NAG (SGD with classical momentum and Nesterov's Accelerated Gradient) - I. Sutskever, J. Martens, G. Dahl and G. Hinton, "[On the importance of initialization and momentum in deep learning](https://dl.acm.org/citation.cfm?id=3043064)," ICML, 2013. - AdaGrad (Adaptive gradient algorithm) - J. Duchi, E. Hazan and Y. Singer, "[Adaptive subgradient methods for online learning and stochastic optimization](http://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf)," Journal of Machine Learning Research, 12, pp. 2121-2159, 2011. - AdaDelta - M. D.Zeiler, "[AdaDelta: An adaptive learning rate method](http://arxiv.org/abs/1212.5701)," arXiv preprint arXiv:1212.5701, 2012. - RMSProp - T. Tieleman and G. Hinton, "Lecture 6.5 - RMSProp", COURSERA: Neural Networks for Machine Learning, Technical report, 2012. - Adam - D. Kingma and J. Ba, "[Adam: A method for stochastic optimization](http://arxiv.org/pdf/1412.6980.pdf)," International Conference for Learning Representation (ICLR), 2015. - AdaMax - D. Kingma and J. Ba, "[Adam: A method for stochastic optimization](http://arxiv.org/pdf/1412.6980.pdf)," International Conference for Learning Representation (ICLR), 2015. - **Variance reduction variants** - SVRG (stochastic variance reduced gradient) - R. Johnson and T. Zhang, "[Accelerating stochastic gradient descent using predictive variance reduction](http://papers.nips.cc/paper/4937-accelerating-stochastic-gradient-descent-using-predictive-variance-reduction.pdf)," NIPS, 2013. - SAG (stochastic average gradient) - N. L. Roux, M. Schmidt, and F. R. Bach, "[A stochastic gradient method with an exponential convergence rate for finite training sets](https://papers.nips.cc/paper/4633-a-stochastic-gradient-method-with-an-exponential-convergence-_rate-for-finite-training-sets.pdf)," NIPS, 2012. - SAGA - A. Defazio, F. Bach, and S. Lacoste-Julien, "[SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives](https://papers.nips.cc/paper/5258-saga-a-fast-incremental-gradient-method-with-support-for-non-strongly-convex-composite-objectives.pdf),", NIPS, 2014. - SARAH (StochAstic Recusive gRadient algoritHm) - L. M. Nguyen, J. Liu, K. Scheinberg, and M. Takac, "[SARAH: A novel method for machine learning problems using stochastic recursive gradient](https://arxiv.org/abs/1703.00102)," ICML, 2017. - **Quasi-Newton variants** - SQN (stochastic quasi-Newton) - R. H. Byrd, ,S. L. Hansen J. Nocedal, and Y. Singer, "[A stochastic quasi-Newton method for large-scale optimization](http://epubs.siam.org/doi/abs/10.1137/140954362?journalCode=sjope8)," SIAM Journal on Optimization, vol. 26, Issue 2, pp. 1008-1031, 2016. - SVRG-SQN (denoted as "Stochastic L-BFGS" or "slbfgs" in the paper below.) - P. Moritz, R. Nishihara and M. I. Jordan, "[A linearly-convergent stochastic L-BFGS Algorithm](http://www.jmlr.org/proceedings/papers/v51/moritz16.html)," International Conference on Artificial Intelligence and Statistics (AISTATS), pp.249-258, 2016. - SVRG-LBFGS (denoted as "SVRG+II: LBFGS" in the paper below.) - R. Kolte, M. Erdogdu and A. Ozgur, "[Accelerating SVRG via second-order information](http://www.opt-ml.org/papers/OPT2015_paper_41.pdf)," OPT2015, 2015. - SS-SVRG (denoted as "SVRG+I: Subsampled Hessian followed by SVT" in the paper below.) - R. Kolte, M. Erdogdu and A. Ozgur, "[Accelerating SVRG via second-order information](http://www.opt-ml.org/papers/OPT2015_paper_41.pdf)," OPT2015, 2015. - oBFGS-Inf (Online BFGS, Infinite memory) - N. N. Schraudolph, J. Yu and Simon Gunter, "[A stochastic quasi-Newton method for online convex optimization ](http://www.jmlr.org/proceedings/papers/v2/schraudolph07a/schraudolph07a.pdf)," International Conference on Artificial Intelligence and Statistics (AISTATS), pp.436-443, Journal of Machine Learning Research, 2007. - oLBFGS-Lim (Online BFGS, Limited memory) - N. N. Schraudolph, J. Yu and S. Gunter, "[A stochastic quasi-Newton method for online convex optimization ](http://www.jmlr.org/proceedings/papers/v2/schraudolph07a/schraudolph07a.pdf)," International Conference on Artificial Intelligence and Statistics (AISTATS), pp.436-443, Journal of Machine Learning Research, 2007. - A. Mokhtari and A. Ribeiro, "[Global convergence of online limited memory BFGS](www.jmlr.org/papers/volume16/mokhtari15a/mokhtari15a.pdf )," Journal of Machine Learning Research, 16, pp. 3151-3181, 2015. - Reg-oBFGS-Inf (Regularized oBFGS, Infinite memory) (denoted as "RES" in the paper below.) - A. Mokhtari and A. Ribeiro, "[RES: Regularized stochastic BFGS algorithm](http://ieeexplore.ieee.org/document/6899692/)," IEEE Transactions on Signal Processing, vol. 62, no. 23, pp. 6089-6104, Dec., 2014. - Damp-oBFGS-Inf (Regularized damped oBFGS, Infinite memory) (denoted as "SDBFGS" in the paper below.) - X. Wang, S. Ma, D. Goldfarb and W. Liu, "[Stochastic quasi-Newton methods for nonconvex stochastic optimization](https://arxiv.org/pdf/1607.01231v3.pdf)," arXiv preprint arXiv:1607.01231, 2016. - IQN (incremental Quasi-Newton method) - A. Mokhtari, M. Eisen and A. Ribeiro, "[An Incremental Quasi-Newton Method with a Local Superlinear Convergence Rate](https://arxiv.org/abs/1702.00709)," ICASSP2017, 2017. - **Inexact Hessian variants** - SCR (Sub-sampled Cubic Regularization) - J. M. Kohler and A. Lucchi, "[Sub-sampled Cubic Regularization for non-convex optimization](http://proceedings.mlr.press/v70/kohler17a.html)," ICML, 2017. - Sub-sampled TR (trust region) - A. R. Conn, N. I. Gould and P. L. Toint, "[Trust region methods](https://epubs.siam.org/doi/book/10.1137/1.9780898719857)," MOS-SIAM Series on Optimization, 2000. - **Else** - SVRG-BB (stochastic variance reduced gradient with Barzilai-Borwein) - C. Tan, S. Ma, Y. Dai, Y. Qian, "[Barzilai-Borwein step size for stochastic gradient descent](https://arxiv.org/pdf/1605.04131