New nonasymptotic convergence rates of stochastic proximal point algorithm for stochastic convex optimization

References

• Choi H, Baraniuk RG. Multiple wavelet basis image denoising using Besov ball projections. IEEE Signal Process Lett. 2004;11:717–720.
   Web of Science ®Google Scholar
• Herman GT. Fundamentals of computerized tomography: image reconstruction from projections. New York: Springer; 2009.
   Google Scholar
• Herman GT, Chen W. A fast algorithm for solving a linear feasibility problem with application to intensity-modulated radiation therapy. Linear Algebra Appl. 2008;428:1207–1217.
   PubMed Web of Science ®Google Scholar
• Censor Y, Chen W, Combettes PL, et al. On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints. Comput Optim Appl. 2012;51(3):1065–1088.
   Web of Science ®Google Scholar
• Gubin LG, Polyak BT, Raik EV. The method of projections for finding the common points of convex sets. USSR Comp Math Phys. 1967;7:1–24.
   Google Scholar
• Nedic A. Random projection algorithms for convex set intersection problems. 49th IEEE Conference on Decision and Control (CDC), 7655–7660, 2010.
   Google Scholar
• Necoara I, Richtarik P, Patrascu A. Stochastic projection methods for convex feasibility problems: conditioning and convergence rates. submitted, arXiv:1801.04873, 2018.
   Google Scholar
• Patrascu A, Necoara I. Nonasymptotic convergence of stochastic proximal point methods for constrained convex optimization. J Mach Learn Res. 2018;19:1–42.
   Google Scholar
• Ryu E, Boyd S. Stochastic proximal iteration: a non-asymptotic improvement upon stochastic gradient descent. 2016. Available from: http://web.stanford.edu/eryu/.
   Google Scholar
• Toulis P, Tran D, Airoldi EM. Towards stability and optimality in stochastic gradient descent. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR Vol. 51. p. 1290–1298, 2016.
   Google Scholar
• Bianchi P. Ergodic convergence of a stochastic proximal point algorithm. SIAM J Optim. 2016;26(4):2235–2260.
   Web of Science ®Google Scholar
• Hazan E, Kale S. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization. J Mach Learn Res. 2014;15:2489-–2512.
   Web of Science ®Google Scholar
• Moulines E, Bach FR. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Adv Neural Inf Process Sys (NIPS). 2011;24:451–459.
   Google Scholar
• Nemirovski A, Juditsky A, Lan G, et al. Robust stochastic approximation approach to stochastic programming. SIAM J Optim. 2009;19(4):1574–1609.
   Web of Science ®Google Scholar
• Nguyen L, NGUYEN PH, Dijk M, et al. SGD and Hogwild! convergence without the bounded gradients assumption. Proceedings of the 35th International Conference on Machine Learning, PMLR; Vol. 80. p. 3750–3758, 2018.
   Google Scholar
• Rakhlin A, Shamir O, Sridharan K. Making gradient descent optimal for strongly convex stochastic optimization. Proceedings of the 29th International Conference on International Conference on Machine Learning. p. 1571–1578, 2012.
   Google Scholar
• Ramdas A, Singh A. Optimal rates for stochastic convex optimization under Tsybakov noise condition. Proc 30th Inter Conf Mach Learn. 2013;28(1):365–373.
   Google Scholar
• Rosasco L, Villa S, Vu BC. Convergence of stochastic proximal gradient algorithm. Arxiv, 2014. Available from: https://arxiv.org/abs/1403.5074.
   Google Scholar
• Shalev-Shwartz S, Singer Y, Srebro N, et al. Pegasos: primal estimated sub-gradient solver for SVM. Math Program. 2011;127(1):3–30.
   Web of Science ®Google Scholar
• Yang T, Lin Q. RSG: beating subgradient method without smoothness and strong convexity. J Mach Learn Res. 2018;19:1-–33.
   Web of Science ®Google Scholar
• Xu Y, Lin Q, Yang T. Stochastic convex optimization: faster local growth implies faster global convergence. International Conference on Machine Learning (ICML), 2017.
   Google Scholar
• Koshal J, Nedic and U. V. Shanbhag A. Regularized iterative stochastic approximation methods for stochastic variational inequality problems. IEEE Trans Automat Contr. 2013;58(3):594–609.
   Web of Science ®Google Scholar
• Wang M, Bertsekas DP. Stochastic first-order methods with random constraint projection. SIAM J Optim. 2016;26(1):681–717.
   Web of Science ®Google Scholar
• Asi H, Duchi JC. Stochastic (Approximate) proximal point methods: convergence, optimality, and adaptivity. Arxiv, 2018.
   Google Scholar
• Rockafellar RT, Wets RJ-B. On the interchange of subdifferentiation and conditional expectation for convex functionals. Stochastics. 1982;7:173–182.
   Google Scholar
• Rockafellar RT. Convex analysis. Princeton (NJ): Princeton University Press; 1998.
   Google Scholar
• Bauschke HH, Borwein J, Li W. Strong conical hull intersection property, bounded linear regularity, Jameson's property (G), and error bounds in convex optimization. Math Program Ser A. 1999;86:135–160.
   Web of Science ®Google Scholar
• Salim A, Bianchi P, Hachem W. Snake: a stochastic proximal gradient algorithm for regularized problems over large graphs. IEEE Trans Automat Contr. 2019;64(5):1832–1847.
   Web of Science ®Google Scholar
• Rockafellar RT, Wets RJ-B. Variational analysis. Berlin Heidelberg: Springer-Verlag; 1998.
   Google Scholar
• Necoara I, Nesterov Yu., Glineur F. Linear convergence of first order methods for non-strongly convex optimization. Math Program. 2018. Available form: https://doi.org/10.1007/s10107-018-1232-1.
   Google Scholar
• Stoican F, Irofti P. Aiding dictionary learning through multi-parametric sparse representation. Algorithms. 2019;12(7):131.
   Web of Science ®Google Scholar
• Bach F, Lanckriet G, Jordan M. Multiple kernel learning, conic duality, and the SMO algorithm. International Conference on Machine Learning (ICML), 2004.
   Google Scholar
• Drusvyatskiy D, Lewis AS. Error bounds, quadratic growth, and linear convergence of proximal methods. Math Oper Res. 2018;43(3):919–948.
   Web of Science ®Google Scholar
• Beck A, Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J Imag Sci. 2009;2(1):183–202.
   Web of Science ®Google Scholar
• Ma S, Bassily R, Belkin M. The power of interpolation: understanding the effectiveness of SGD in modern over-parametrized learning. arXiv:1712.06559, 2018.
   Google Scholar
• Bianchi P, Hachem W. Dynamical behavior of a stochastic forward-backward algorithm using random monotone operators. J Optim Theory Appl. 2016;171(1):90–120.
   Web of Science ®Google Scholar
• Hallac D, Leskovec J, Boyd S. Network lasso: clustering and optimization in large graphs. Proceedings SIGKDD, p. 387–396, 2015.
   Google Scholar