ProxSARAH swMATH ID: 35438 Software Authors: Pham, Nhan H.; Nguyen, Lam M.; Phan, Dzung T.; Tran-Dinh, Quoc Description: ProxSARAH: an efficient algorithmic framework for stochastic composite nonconvex optimization. We propose a new stochastic first-order algorithmic framework to solve stochastic composite nonconvex optimization problems that covers both finite-sum and expectation settings. Our algorithms rely on the SARAH estimator and consist of two steps: a proximal gradient and an averaging step making them different from existing nonconvex proximal-type algorithms. The algorithms only require an average smoothness assumption of the nonconvex objective term and additional bounded variance assumption if applied to expectation problems. They work with both constant and dynamic step-sizes, while allowing single sample and mini-batches. In all these cases, we prove that our algorithms can achieve the best-known complexity bounds in terms of stochastic first-order oracle. One key step of our methods is the new constant and dynamic step-sizes resulting in the desired complexity bounds while improving practical performance. Our constant step-size is much larger than existing methods including proximal SVRG scheme in the single sample case. We also specify our framework to the non-composite case that covers existing state-of-the-arts in terms of oracle complexity bounds. Our update also allows one to trade-off between step-sizes and mini-batch sizes to improve performance. We test the proposed algorithms on two composite nonconvex problems and neural networks using several well-known data sets. Homepage: https://arxiv.org/abs/1902.05679 Keywords: stochastic proximal gradient descent; variance reduction; composite nonconvex optimization; finite-sum minimization; expectation minimization Related Software: Saga; SpiderBoost; LIBSVM; Adam; Finito; AdaGrad; CIFAR; FPC_AS; SUTIL; Pegasos; SparseLOGREG; TensorFlow; ElemStatLearn; L-BFGS; PRMLT; blockSQP; QUIC; LIBLINEAR; UNLocBoX; PyTorch Cited in: 26 Documents Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year ProxSARAH: an efficient algorithmic framework for stochastic composite nonconvex optimization. Zbl 1508.90041Pham, Nhan H.; Nguyen, Lam M.; Phan, Dzung T.; Tran-Dinh, Quoc 2020 all top 5 Cited by 61 Authors 5 Nguyen, Lam M. 4 Phan, Dzung T. 3 Driggs, Derek 3 Schönlieb, Carola-Bibiane 3 Tran Dinh Quoc 2 Dai, Yu-Hong 2 Liang, Jingwei 2 Liu, Xinwei 2 Nguyen, Phuong Ha 2 Pham, Nhan H. 2 Sun, Jie 2 van Dijk, Marten 2 Xiao, Lin 2 Yu, Tengteng 2 Zhang, Junyu 1 Boob, Digvijay 1 Chen, Zengping 1 Cheng, Guang 1 Cheng, Wanyou 1 Davies, Mike E. 1 Deng, Qi 1 Ehrhardt, Matthias Joachim 1 Guo, Tiande 1 Han, Congying 1 He, Lulu 1 Hou, Di 1 Hu, Jia 1 Jianwei, E. 1 Jin, Lingzi 1 Kalagnanam, Jayant R. 1 Kar, Soummya 1 Khan, Usman Ali 1 Lan, Guanghui 1 Li, Wenjie 1 Li, Xinxin 1 Metel, Michael R. 1 Milzarek, Andre 1 Scheinberg, Katya 1 Shao, Yuanhai 1 Song, Haiming 1 Takáč, Martin 1 Takeda, Akiko 1 Tang, Junqi 1 Wang, Cheng 1 Wang, Lichun 1 Wang, Ruyu 1 Wang, Xiao 1 Wang, Zhanyu 1 Wen, Zaiwen 1 Weng, Tsui-Wei 1 Xin, Ran 1 Xu, Yangyang 1 Xu, Yibo 1 Yang, Jinda 1 Yang, Minghan 1 Yang, Zhuang 1 Ye, Jimin 1 Zhang, Hongchao 1 Zhang, Tong 1 Zhang, Yichen 1 Zhao, Tong all top 5 Cited in 12 Serials 5 Mathematical Programming. Series A. Series B 4 Journal of Machine Learning Research (JMLR) 3 Journal of Scientific Computing 3 Optimization Methods & Software 2 Journal of Optimization Theory and Applications 2 SIAM Journal on Optimization 2 Computational Optimization and Applications 1 Information Sciences 1 Machine Learning 1 Journal of Industrial and Management Optimization 1 SIAM Journal on Imaging Sciences 1 Journal of the Operations Research Society of China all top 5 Cited in 9 Fields 21 Operations research, mathematical programming (90-XX) 8 Computer science (68-XX) 5 Numerical analysis (65-XX) 2 Calculus of variations and optimal control; optimization (49-XX) 1 Operator theory (47-XX) 1 Statistics (62-XX) 1 Biology and other natural sciences (92-XX) 1 Systems theory; control (93-XX) 1 Information and communication theory, circuits (94-XX) Citations by Year