Mini-batch stochastic subgradient for functional constrained optimization

References

• Bhattacharyya C, Grate LR, Jordan MI, et al. Robust sparse hyperplane classifiers: application to uncertain molecular profiling data. J Comput Biol. 2004;11(6):1073–1089.
   PubMed Web of Science ®Google Scholar
• Vapnik V. Statistical learning theory. John Wiley; 1998.
   Google Scholar
• Nedelcu V, Necoara I, Tran Dinh Q. Computational complexity of inexact gradient augmented Lagrangian methods: application to constrained MPC. SIAM J Control Optim. 2014;52(5):3109–3134.
   Web of Science ®Google Scholar
• Necoara I. General convergence analysis of stochastic first order methods for composite optimization. J Optim Theory Appl. 2021;189(1):66–95.
   Web of Science ®Google Scholar
• Tibshirani R. The solution path of the generalized Lasso [PhD thesis]. Stanford Univ.; 2011.
   Google Scholar
• Rockafellar RT, Uryasev SP. Optimization of conditional value-at-risk. J Risk. 2000;2(3):21–41.
   Google Scholar
• Jacob L, Obozinski G, Vert JP. Group Lasso with overlap and graph Lasso. In: International conference on machine learning; 2009. p. 433–440.
   Google Scholar
• Yin X, Büyüktahtakın İ. A multi-stage stochastic programming approach to epidemic resource allocation with equity considerations. Health Care Manag Sci. 2021;24(3):597–622.
   PubMed Web of Science ®Google Scholar
• Zafar M, Valera I, Gomez-Rodriguez M, et al. Fairness constraints: a flexible approach for fair classification. J Mach Learn Res. 2019;20(1):2737–2778.
   Google Scholar
• Rosasco L, Villa S, Vu BC. Convergence of stochastic proximal gradient algorithm. Appl Math Optim. 2020;82(3):891–917.
   Web of Science ®Google Scholar
• Hardt M, Recht B, Singer Y. Train faster, generalize better: stability of stochastic gradient descent. In: International conference on machine learning; 2016.
   Google Scholar
• Nemirovski A, Yudin DB. Problem complexity and method efficiency in optimization. New York: Wiley Interscience; 1983.
   Google Scholar
• Robbins H, Monro S. A stochastic approximation method. Ann Math Stat. 1951;22(3):400–407.
   Google Scholar
• Moulines E, Bach F. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In: Advances in neural information processing systems conference; 2011.
   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
• Patrascu A, Necoara I. Nonasymptotic convergence of stochastic proximal point algorithms for constrained convex optimization. J Mach Learn Res. 2018;18(198):1–42.
   Google Scholar
• Asi H, Chadha K, Cheng G, et al. Minibatch stochastic approximate proximal point methods. In: Advances in neural information processing systems conference; 2020.
   Google Scholar
• Duchi J, Singer Y. Efficient online and batch learning using forward backward splitting. J Mach Learn Res. 2009;10:2899–2934.
   Web of Science ®Google Scholar
• Nedich A, Necoara I. Random minibatch subgradient algorithms for convex problems with functional constraints. Appl Math Optim. 2019;80(3):801–833.
   Web of Science ®Google Scholar
• Peng X, Li L, Wang F. Accelerating minibatch stochastic gradient descent using typicality sampling. In: IEEE Trans. Neural Networks Learn. Syst.; 2019.
   Google Scholar
• Gower R, Nicolas L, Xun Q, et al. SGD: general analysis and improved rates. In: International conference on machine learning; 2019.
   Google Scholar
• Renegar J, Zhou S. A different perspective on the stochastic convex feasibility problem; 2021. arXiv preprint: 2108.12029v1.
   Google Scholar
• Polyak BT, Juditsky AB. Acceleration of stochastic approximation by averaging. SIAM J Control Optim. 1992;30(4):838–855.
   Web of Science ®Google Scholar
• Yang T, Lin Q. RSG: beating subgradient method without smoothness and strong convexity. J Mach Learn Res. 2018;19(6):1–33.
   Google Scholar
• Gorbunov E, Hanzely F, Richtarik P. A unified theory of SGD: variance reduction, sampling, quantization and coordinate descent. In: Proceedings of the 23rd international conference on artificial intelligence and statistics; vol. 108, 2020.
   Google Scholar
• Johnson R, Zhang T. Accelerating stochastic gradient descent using predictive variance reduction. In: Advances in neural information processing systems; 2013. p. 315–323.
   Google Scholar
• Lin H, Mairal J, Harchaoui Z. A universal catalyst for first-order optimization. In: Advances in neural information processing systems conference; 2015.
   Google Scholar
• Necoara I, Singh NK. Stochastic subgradient projection methods for composite optimization with functional constraints. J Mach Learn Res. 2022;23:1–35.
   Google Scholar
• Necoara I, Nesterov Y, Glineur F. Linear convergence of first order methods for non-strongly convex optimization. Math Program. 2019;175(1):69–107.
   Web of Science ®Google Scholar
• Lewis A, Pang JS. Error bounds for convex inequality systems. In: Crouzeix J-P, Martinez-Legaz J-E, Volle M, editors. Generalized convexity, generalized monotonicity. Cambridge University Press; 1998. p. 75–110.
   Google Scholar
• Nesterov Y. Lectures on convex optimization, vol. 137. Springer Optimization and Its Applications; 2018.
   Google Scholar
• Richtarik P, Takac M. On optimal probabilities in stochastic coordinate descent methods. Optim Lett. 2016;10(6):1233–1243.
   Web of Science ®Google Scholar
• Polyak BT. Minimization of unsmooth functionals. USSR Comput Math Math Phys. 1969;9(3):14–29.
   Google Scholar
• Gaines BR, Kim J, Zhou H. Algorithms for fitting the constrained Lasso. J Comput Graph Stat. 2018;27(4):861–871.
   PubMed Web of Science ®Google Scholar
• Hu Q, Zeng P, Lin L. The dual and degrees of freedom of linearly constrained generalized Lasso. Comput Stat Data Anal. 2015;86:13–26.
   Web of Science ®Google Scholar
• James GM, Paulsonand C, Rusmevichientong P. Penalized and constrained optimization: an application to high-dimensional website advertising. SIAM J Optim. 2019;30(4):3230–3251.
   Google Scholar
• Grant M, Boyd S. CVX: matlab software for disciplined convex programming, version 2.0 beta; 2013. Available from: http://cvxr.com/cvx.
   Google Scholar