A. Agarwal, P. L. Bartlett, P. Ravikumar, and M. J. Wainwright, Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization, IEEE Transactions on Information Theory, vol.58, issue.5, pp.58-2012
DOI : 10.1109/TIT.2011.2182178

F. Bach and E. Moulines, Non-asymptotic analysis of stochastic approximation algorithms for machine learning, NIPS, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00608041

D. P. Bertsekas, A New Class of Incremental Gradient Methods for Least Squares Problems, SIAM Journal on Optimization, vol.7, issue.4, pp.913-926, 1997.
DOI : 10.1137/S1052623495287022

D. Blatt, A. O. Hero, and H. Gauchman, A Convergent Incremental Gradient Method with a Constant Step Size, SIAM Journal on Optimization, vol.18, issue.1, pp.29-51, 2007.
DOI : 10.1137/040615961

L. Bottou and O. Bousquet, The tradeoffs of large scale learning, NIPS, 2007.

L. Bottou and Y. Lecun, Large scale online learning, NIPS, 2003.

M. A. Cauchy, Méthode générale pour la résolution des systèmes d'´ equations simultanées, Comptes rendus des séances de l'Académie des sciences de Paris, pp.536-538, 1847.

B. Delyon and A. Juditsky, Accelerated Stochastic Approximation, SIAM Journal on Optimization, vol.3, issue.4, pp.868-881, 1993.
DOI : 10.1137/0803045

M. Eberts and I. Steinwart, Optimal learning rates for least squares SVMs using Gaussian kernels, NIPS, 2011.

M. P. Friedlander and M. Schmidt, Hybrid deterministic-stochastic methods for data fitting, SIAM Journal of Scientific Computing, vol.34, issue.3, pp.1351-1379, 2012.
URL : https://hal.archives-ouvertes.fr/inria-00626571

S. Ghadimi and G. Lan, Optimal stochastic' approximation algorithms for strongly convex stochastic composite optimization, Optimization Online, 2010.

E. Hazan and S. Kale, Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization. COLT, 2011.

H. Kesten, Accelerated Stochastic Approximation, The Annals of Mathematical Statistics, vol.29, issue.1, pp.41-59, 1958.
DOI : 10.1214/aoms/1177706705

H. J. Kushner and G. Yin, Stochastic approximation and recursive algorithms and applications, 2003.

P. Liang, F. Bach, and M. I. Jordan, Asymptotically optimal regularization in smooth parametric models, NIPS, 2009.

J. Liu, J. Chen, and J. Ye, Large-scale sparse logistic regression, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD '09, 2009.
DOI : 10.1145/1557019.1557082

J. Martens, Deep learning via Hessian-free optimization, ICML, 2010.

A. Nedic and D. Bertsekas, Convergence rate of incremental subgradient algorithms, Stochastic Optimization: Algorithms and Applications, pp.263-304, 2000.

A. Nemirovski and D. B. Yudin, Problem complexity and method efficiency in optimization, 1983.

A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro, Robust Stochastic Approximation Approach to Stochastic Programming, SIAM Journal on Optimization, vol.19, issue.4, pp.1574-1609, 2009.
DOI : 10.1137/070704277
URL : https://hal.archives-ouvertes.fr/hal-00976649

Y. Nesterov, A method for unconstrained convex minimization problem with the rate of convergence, Doklady AN SSSR, vol.269, issue.1 23, pp.543-547, 1983.

Y. Nesterov, Introductory lectures on convex optimization: A basic course, 2004.
DOI : 10.1007/978-1-4419-8853-9

Y. Nesterov, Primal-dual subgradient methods for convex problems, Mathematical Programming, vol.8, issue.1, pp.221-259, 2009.
DOI : 10.1007/s10107-007-0149-x

Y. Nesterov, Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems, SIAM Journal on Optimization, vol.22, issue.2, 2010.
DOI : 10.1137/100802001

B. T. Polyak and A. B. Juditsky, Acceleration of Stochastic Approximation by Averaging, SIAM Journal on Control and Optimization, vol.30, issue.4, pp.838-855, 1992.
DOI : 10.1137/0330046

H. Robbins and S. Monro, A Stochastic Approximation Method, The Annals of Mathematical Statistics, vol.22, issue.3, pp.400-407, 1951.
DOI : 10.1214/aoms/1177729586

N. Schraudolph, Local gain adaptation in stochastic gradient descent, 9th International Conference on Artificial Neural Networks: ICANN '99, 1999.
DOI : 10.1049/cp:19991170

S. Shalev-shwartz, Y. Singer, and N. Srebro, Pegasos, Proceedings of the 24th international conference on Machine learning, ICML '07, 2007.
DOI : 10.1145/1273496.1273598

M. Solodov, Incremental gradient algorithms with stepsizes bounded away from zero, Computational Optimization and Applications, vol.11, issue.1, pp.23-35, 1998.
DOI : 10.1023/A:1018366000512

K. Sridharan, S. Shalev-shwartz, and N. Srebro, Fast rates for regularized objectives, NIPS, 2008.

C. H. Teo, Q. Le, A. J. Smola, and S. V. Vishwanathan, A scalable modular convex solver for regularized risk minimization, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining , KDD '07, 2007.
DOI : 10.1145/1281192.1281270

P. Tseng, An Incremental Gradient(-Projection) Method with Momentum Term and Adaptive Stepsize Rule, SIAM Journal on Optimization, vol.8, issue.2, pp.506-531, 1998.
DOI : 10.1137/S1052623495294797

L. Xiao, Dual averaging methods for regularized stochastic learning and online optimization, Journal of Machine Learning Research, vol.11, pp.2543-2596, 2010.