Deterministic and Stochastic Primal-Dual Subgradient Algorithms for Uniformly Convex Minimization

References

• Agarwal, A., Bartlett, P. L., Ravikumar, P., Wainwright, M. J., Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization, IEEE Trans. Information Theory, 58, 5, 3235–3249 (2012). MR2952543Google Scholar
• Azé, D., Penot, J.-P., Uniformly convex and uniformly smooth convex functions, Ann. Fac. Sci. Toulouse, VI. Sér., Math. 4, 705–730 (1995). MR1623472Google Scholar
• Chekanov, Yu., Nesterov, Yu., Vladimirov, A., On uniformly convex functionals, Vest. Mosk. Univ., 3, Ser. XV, 12–23 (1978). MR0516874Google Scholar
• Ibragimov, I. A., Linnik, Yu. V., Independent and Stationary Sequences of Random Variables, Wolters-Noordhoff Ser. Pure and Appl. Math. (1971). MR0322926Google Scholar
• Juditsky, A., Nemirovski, A., Large Deviations of Vector-valued Martingales in 2-Smooth Normed Spaces, http://arxiv.org/abs/0809.0813.Google Scholar
• Lemaire, V., Pagès, G., Unconstrained recursive importance sampling, Ann. Appl. Probab., 20, 3, 1029–1067 (2010). MR2680557Google Scholar
• Nadler, B., Srebro, N., Zhou, X., Statistical Analysis of Semi-Supervised Learning: The Limit of Infinite Unlabelled Data, NIPS 2009 Online papers, http://books.nips.cc/nips22.html, to appear in Advances in Neural Information Processing Systems 22, edited by Y. Bengio, et al.. (2009).Google Scholar
• Nemirovski, A. S., Yudin, D. B., Problem Complexity and Method Efficiency in Optimization, Wiley-Interscience Series in Discrete Mathematics, John Wiley, XV (1983). MR0702836Google Scholar
• Nemirovski, A., Juditsky, A., Lan, G., Shapiro, A., Robust stochastic approximation approach to stochastic programming, SIAM J. Optim., 19, 4, 1574–1609 (2009). MR2486041Google Scholar
• Nesterov, Yu., Introductory Lectures on Convex Optimization: A Basic Course, Springer (2003). MR2142598Google Scholar
• Nesterov, Yu., Smooth minimization of nonsmooth functions, Math. Prog. Ser A, 103, 1, 127–152 (2005). MR2166537Google Scholar
• Nesterov, Yu., Excessive Gap Technique in Nonsmooth Convex Minimization, SIAM J. Optim., 16, 1, 235–249 (2005). MR2177777Google Scholar
• Nesterov, Yu., Primal-dual subgradient methods for convex problems, Math. Program., Ser. B (2007) (Online). MR2496434Google Scholar
• Nesterov, Yu., Barrier subgradient method. Ciaco, 2008, CORE DP2008/60 (2008).Google Scholar
• Nesterov, Yu., Vial, J.-Ph., Confidence level solutions for stochastic programming, Automatica, 44, 6, 1559–1568 (2008). MR2531843Google Scholar
• Nesterov, Yu., Accelerating the cubic regularization of Newton’s method on convex problems, Math. Program. Ser. B, 112, 159–181 (2008). MR2327005Google Scholar
• Polyak, B., Existence theorems and convergence of minimizing sequences in extremum problems with restrictions, Sov. Math. Dokl., 7, 72–75 (1967).Google Scholar
• Raginsky, M., Rakhlin, A., Information-based complexity, feedback and dynamics in convex programming, IEEE Trans. on Information Theory, 57, 10, 7036–7056 (2011). MR2882278Google Scholar
• Xiao, L., Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization, ISMP 2009, Chicago, August 23–28 (2009). MR2738777Google Scholar
• Zălinescu, C., On uniformly convex functions, J. Math. Anal. Appl, 95, 344–374 (1983). MR0716088Google Scholar