Smoothed Variable Sample-Size Accelerated Proximal Methods for Nonsmooth Stochastic Convex Programs

References

• Beck A (2017) First-Order Methods in Optimization (SIAM, Philadelphia).Google Scholar
• Beck A, Teboulle M (2009) A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1):183–202.Google Scholar
• Beck A, Teboulle M (2012) Smoothing and first order methods: A unified framework. SIAM J. Optim. 22(2):557–580.Google Scholar
• Boţ RI, Hendrich C (2013) A double smoothing technique for solving unconstrained nondifferentiable convex optimization problems. Comput. Optim. Appl. 54(2):239–262.Google Scholar
• Boţ RI, Hendrich C (2015) A variable smoothing algorithm for solving convex optimization problems. TOP 23(1):124–150.Google Scholar
• Bubeck S (2015) Convex Optimization: Algorithms and Complexity, Foundations and Trends in Machine Learning (Now Publishers, Inc., Hanover, MA), 8(3–4):231–357.Google Scholar
• Chambolle A, Pock T (2011) A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vision 40(1):120–145.Google Scholar
• Chatzigeorgiou I (2013) Bounds on the Lambert function and their application to the outage analysis of user cooperation. IEEE Comm. Lett. 17(8):1505–1508.Google Scholar
• Dang CD, Lan G (2015) Stochastic block mirror descent methods for nonsmooth and stochastic optimization. SIAM J. Optim. 25(2):856–881.Google Scholar
• Devolder O, Glineur F, Nesterov Y (2012) Double smoothing technique for large-scale linearly constrained convex optimization. SIAM J. Optim. 22(2):702–727.Google Scholar
• Devolder O, Glineur F, Nesterov Y (2014) First-order methods of smooth convex optimization with inexact oracle. Math. Programming 146(1–2):37–75.Google Scholar
• Dvurechensky P, Gasnikov A (2016) Stochastic intermediate gradient method for convex problems with stochastic inexact oracle. J. Optim. Theory Appl. 171(1):121–145.Google Scholar
• Facchinei F, Pang JS (2003) Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer Series in Operations Research, vol. I (Springer-Verlag, New York).Google Scholar
• Ghadimi S, Lan G (2012) Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization I: A generic algorithmic framework. SIAM J. Optim. 22(4):1469–1492.Google Scholar
• Ghadimi S, Lan G (2013) Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization II: Shrinking procedures and optimal algorithms. SIAM J. Optim. 23(4):2061–2089.Google Scholar
• Ghadimi S, Lan G (2016) Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Math. Programming 156(1–2):59–99.Google Scholar
• Hiriart-Urruty JB, Strodiot JJ, Nguyen VH (1984) Generalized Hessian matrix and second-order optimality conditions for problems with C1,1 data. Appl. Math. Optim. 11(1):43–56.Google Scholar
• Jalilzadeh A, Shanbhag UV (2016) eg-VSSA: An extragradient variable sample-size stochastic approximation scheme: Error analysis and complexity trade-offs. Winter Simulation Conf., 690–701.Google Scholar
• Jofré A, Thompson P (2017) On variance reduction for stochastic smooth convex optimization with multiplicative noise. Preprint, submitted May 8, https://arxiv.org/abs/1705.02969.Google Scholar
• Kushner HJ, Yin GG (2003) Stochastic Approximation and Recursive Algorithms and Applications, Applications of Mathematics, vol. 35, 2nd ed. (Springer Science & Business Media, New York).Google Scholar
• Lan G (2012) An optimal method for stochastic composite optimization. Math. Programming (Springer), 133(1):365–397.Google Scholar
• Moreau JJ (1965) Proximité et dualité dans un espace hilbertien. Bull. Soc. Math. France 93(2):273–299.Google Scholar
• Nemirovski A, Juditsky A, Lan G, Shapiro A (2009) Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19(4):1574–1609.Google Scholar
• Nesterov Y (1983) A method for unconstrained convex minimization problem with the rate of convergence O(1/k2). Doklady AN USSR 269:543–547.Google Scholar
• Nesterov Y (2005a) Excessive gap technique in nonsmooth convex minimization. SIAM J. Optim. 16(1):235–249.Google Scholar
• Nesterov Y (2005b) Smooth minimization of non-smooth functions. Math. Programming 103(1):127–152.Google Scholar
• Nesterov Y (2014) Introductory Lectures on Convex Optimization: A Basic Course, 1st ed. (Springer Publishing Company, Inc. Norwell, MA).Google Scholar
• Newton D, Pasupathy R, Yousefian F (2018) Recent trends in stochastic gradient descent for machine learning and big data. Proc. 2018 Winter Simulation Conf. (IEEE Press), 366–380.Google Scholar
• Orabona F, Argyriou A, Srebro N (2012) Prisma: Proximal iterative smoothing algorithm. Preprint, submitted June 11, https://arxiv.org/abs/1206.2372.Google Scholar
• Ouyang H, Gray A (2012) Stochastic smoothing for nonsmooth minimizations: Accelerating SGD by exploiting structure. Preprint, submitted May 21, https://arxiv.org/abs/1205.4481.Google Scholar
• Planiden C, Wang X (2016) Strongly convex functions, Moreau envelopes, and the generic nature of convex functions with strong minimizers. SIAM J. Optim. 26(2):1341–1364.Google Scholar
• Polyak BT (1987) Introduction to Optimization (Optimization Software, Inc., New York).Google Scholar
• Polyak BT, Juditsky AB (1992) Acceleration of stochastic approximation by averaging. SIAM J. Control Optim. 30(4):838–855.Google Scholar
• Robbins H, Monro S (1951) A stochastic approximation method. Ann. Math. Statist. 22(3):400–407.Google Scholar
• Schmidt M, Roux NL, Bach FR (2011) Convergence rates of inexact proximal-gradient methods for convex optimization. Adv. Neural Inform. Processes Systems 24:1458–1466.Google Scholar
• Shamir O, Zhang T (2013) Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. Internat. Conf. Machine Learn., 71–79.Google Scholar
• Shanbhag UV, Blanchet JH (2015) Budget-constrained stochastic approximation. Proc. 2015 Winter Simulation Conf., 368–379.Google Scholar
• Shapiro A, Dentcheva D, Ruszczýnski A (2009) Lectures on Stochastic Programming (SIAM, Philadelphia).Google Scholar
• Tran-Dinh Q (2017) Adaptive smoothing algorithms for nonsmooth composite convex minimization. Comput. Optim. Appl. 66(3):425–451.Google Scholar
• Tran-Dinh Q, Fercoq O, Cevher V (2018) A smooth primal-dual optimization framework for nonsmooth composite convex minimization. SIAM J. Optim. 28(1):96–134.Google Scholar
• Van Nguyen Q, Fercoq O, Cevher V (2017) Smoothing technique for nonsmooth composite minimization with linear operator. Preprint, submitted June 19, https://arxiv.org/abs/1706.05837.Google Scholar
• Veberic D (2010) Having fun with Lambert W(x) function. Preprint, submitted March 8, https://arxiv.org/abs/1003.1628.Google Scholar
• Yousefian F, Nedić A, Shanbhag UV (2012) On stochastic gradient and subgradient methods with adaptive steplength sequences. Automatica J. IFAC 48(1):56–67.Google Scholar
• Zhong W, Kwok J (2014) Accelerated stochastic gradient method for composite regularization. Artificial Intelligence Statist., 1086–1094.Google Scholar