Katyusha Acceleration for Convex Finite-Sum Compositional Optimization

References

• Allen-Zhu Z (2017) Katyusha: The first direct acceleration of stochastic gradient methods. J. Machine Learn. Res. 18(1):8194–8244.Google Scholar
• Allen-Zhu Z, Hazan E (2016) Optimal black-box reductions between optimization objectives. Lee DD, Sugiyama M, Luxburg UV, Guyon I, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 29 (Curran Associates, Inc., Red Hook, NY), 1614–1622.Google Scholar
• Allen-Zhu Z, Orecchia L (2014) Linear coupling: An ultimate unification of gradient and mirror descent. Preprint, submitted July 6, https://arxiv.org/abs/1407.1537.Google Scholar
• Chen Z, Zhou Y (2020) Momentum with variance reduction for nonconvex composition optimization. Preprint, submitted May 15, https://arxiv.org/abs/2005.07755.Google Scholar
• Defazio A, Bach F, Lacoste-Julien S (2014) Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ, eds. Advances in Neural Information Processing Systems, vol. 27 (Curran Associates, Inc., Red Hook, NY), 1646–1654.Google Scholar
• Defazio A (2016) A simple practical accelerated method for finite sums. Lee DD, Sugiyama M, Luxburg UV, Guyon I, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 29 (Curran Associates, Inc., Red Hook, NY), 676–684.Google Scholar
• Lin H, Mairal J, Harchaoui Z (2015) A universal catalyst for first-order optimization. Cortes C, Lawrence ND, Lee DD, Sugiyama M, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 28 (Curran Associates, Inc., Red Hook, NY), 3384–3392.Google Scholar
• Ghadimi S, Ruszczynski A, Wang M (2020) A single timescale stochastic approximation method for nested stochastic optimization. SIAM J. Optim. 30(1):960–979.Google Scholar
• Huo Z, Gu B, Liu J, Huang H (2018) Accelerated method for stochastic composition optimization with nonsmooth regularization. Proc. AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA) 32(1).Google Scholar
• Johnson R, Zhang T (2013) Accelerating stochastic gradient descent using predictive variance reduction. Burges CJC, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, eds. Advances in Neural Information Processing Systems, vol. 26 (Curran Associates, Inc., Red Hook, NY), 315–323.Google Scholar
• Lan G (2020) First-Order and Stochastic Optimization Methods for Machine Learning (Springer, Cham, Switzerland).Google Scholar
• Lian X, Wang M, Liu J (2017) Finite-sum composition optimization via variance reduced gradient descent. Proc. 20th Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 54 (PMLR), 1159–1167.Google Scholar
• Lin T, Fan C, Wang M, Jordan MI (2020) Improved sample complexity for stochastic compositional variance reduced gradient. 2020 American Control Conference (ACC 2020) (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 126–131.Google Scholar
• Liu L, Liu J, Tao D (2017) Variance reduced methods for non-convex composition optimization. Preprint, submitted November 13, https://arxiv.org/abs/1711.04416.Google Scholar
• Markowitz HM (1987) Mean-Variance Analysis in Portfolio Choice and Capital Markets (Basil Blackwell, Oxford, UK).Google Scholar
• Markowitz H (2012) Portfolio selection. Financial Risk Measurement and Management, International Library of Critical Writings in Economics, vol. 267 (Edward Elgar, Cheltenham, UK), 197–211. [reprint of J. Finance 7(1):77–91].Google Scholar
• Nesterov YE (1983) A method for solving the convex programming problem with convergence rate O (1/k2). Dokl. Akad. Nauk SSSR 269:543–547.Google Scholar
• Nesterov Y (2013a) Gradient methods for minimizing composite functions. Math. Programming 140(1):125–161.Google Scholar
• Nesterov Y (2013b) Introductory Lectures on Convex Optimization: A Basic Course, vol. 87 (Springer Science & Business Media, Berlin).Google Scholar
• Rigollet P, Tong X (2011) Neyman-Pearson classification, convexity and stochastic constraints. J. Machine Learn. Res. 12(Oct):2831–2855.Google Scholar
• Schmidt M, Le Roux N, Bach F (2017) Minimizing finite sums with the stochastic average gradient. Math. Programming 162(1-2):83–112.Google Scholar
• Shang F, Jiao L, Zhou K, Cheng J, Ren Y, Jin Y (2018) ASVRG: Accelerated proximal SVRG. 10th Asian Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 95 (PMLR), 815–830.Google Scholar
• Tran-Dinh Q, Pham N, Nguyen L (2020) Stochastic Gauss-Newton algorithms for nonconvex compositional optimization. Daumé H, Singh A, eds. Proc. 37th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 119 (PMLR), 9572–9582.Google Scholar
• Wang M, Fang EX, Liu H (2017a) Stochastic compositional gradient descent: Algorithms for minimizing compositions of expected-value functions. Math. Programming 161(1-2):419–449.Google Scholar
• Wang M, Liu J, Fang EX (2017b) Accelerating stochastic composition optimization. J. Machine Learn. Res. 18(105):1–23.Google Scholar
• Woodworth BE, Srebro N (2016) Tight complexity bounds for optimizing composite objectives. Lee DD, Sugiyama M, Luxburg UV, Guyon I, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 29 (Curran Associates, Inc., Red Hook, NY), 3639–3647.Google Scholar
• Xiao L, Zhang T (2014) A proximal stochastic gradient method with progressive variance reduction. SIAM J. Optim. 24(4):2057–2075.Google Scholar
• Xu Y (2019) Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming. Math. Programming 185:199–244.Google Scholar
• Yang S, Wang M, Fang EX (2019) Multilevel stochastic gradient methods for nested composition optimization. SIAM J. Optim. 29(1):616–659.Google Scholar
• Yu Y, Huang L (2017) Fast stochastic variance reduced ADMM for stochastic composition optimization. Proc. Twenty-Sixth Internat. Joint Conf. Artificial Intelligence (International Joint Conferences on Artificial Intelligence), 3364–3370.Google Scholar
• Zafar MB, Valera I, Rogriguez MG, Gummadi KP (2017) Fairness constraints: Mechanisms for fair classification. Proc. 20th Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 54 (PMLR), 962–970.Google Scholar
• Zhang J, Xiao L (2019a) A composite randomized incremental gradient method. Proc. 36th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 97 (PMLR), 7454–7462.Google Scholar
• Zhang J, Xiao L (2019b) Multi-level composite stochastic optimization via nested variance reduction. Preprint, submitted August 29, https://arxiv.org/abs/1908.11468.Google Scholar
• Zhang J, Xiao L (2020) Stochastic variance-reduced prox-linear algorithms for nonconvex composite optimization. Preprint, submitted April 9, https://arxiv.org/abs/2004.04357.Google Scholar