A. and E. Hazan, Variance reduction for faster non-convex optimization, ICML, 2016.

Y. F. Atchade, G. Fort, and E. Moulines, On stochastic proximal gradient algorithms, 2014.

A. Beck and M. Teboulle, A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems, SIAM Journal on Imaging Sciences, vol.2, issue.1, pp.183-202, 2009.
DOI : 10.1137/080716542
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.231.3271

A. Beck and M. Teboulle, Gradient-based algorithms with applications to signal recovery. Convex optimization in signal processing and communications, pp.42-88, 2009.
DOI : 10.1017/cbo9780511804458.003
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.231.2999

M. Robert, Y. Bell, and . Koren, Lessons from the netflix prize challenge, SIGKDD Explor. Newsl, vol.9, issue.2, pp.75-79, 2007.

R. Bhatia, Matrix analysis, volume 169 of Graduate Texts in Mathematics, 1997.

J. Bobadilla, F. Ortega, A. Hernando, and A. Gutiérrez, Recommender systems survey. Knowledge-Based Systems, pp.109-132, 2013.

L. Bottou, Large-scale machine learning with stochastic gradient descent, 2010.
DOI : 10.1201/b11429-4
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.419.462

S. Burer and D. C. Monteiro, Local Minima and Convergence in Low-Rank Semidefinite Programming, Mathematical Programming, pp.427-444, 2005.
DOI : 10.1007/s10107-004-0564-1
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.100.7257

J. Cai, E. J. Candès, and Z. Shen, A Singular Value Thresholding Algorithm for Matrix Completion, SIAM Journal on Optimization, vol.20, issue.4, pp.1956-1982, 2010.
DOI : 10.1137/080738970
URL : http://arxiv.org/abs/0810.3286

T. T. Cai and W. Zhou, Matrix completion via max-norm constrained optimization. CoRR, abs/1303, p.341, 2013.
DOI : 10.1214/16-ejs1147
URL : http://arxiv.org/abs/1303.0341

T. T. Cai and W. Zhou, A max-norm constrained minimization approach to 1-bit matrix completion, J. Mach. Learn. Res, vol.14, pp.3619-3647, 2013.

E. J. Candès and Y. Plan, Matrix Completion With Noise, Proceedings of the IEEE, pp.925-936, 2010.
DOI : 10.1109/JPROC.2009.2035722

E. J. Candès and B. Recht, Exact Matrix Completion via Convex Optimization, Foundations of Computational Mathematics, vol.170, issue.1, pp.717-772, 2009.
DOI : 10.1007/s10208-009-9045-5

E. J. Candès and T. Tao, The Power of Convex Relaxation: Near-Optimal Matrix Completion, IEEE Transactions on Information Theory, vol.56, issue.5, pp.2053-2080, 2010.
DOI : 10.1109/TIT.2010.2044061

C. Chang and C. Lin, LIBSVM, ACM Transactions on Intelligent Systems and Technology, vol.2, issue.3, pp.27-28, 2011.
DOI : 10.1145/1961189.1961199

P. L. Combettes and J. C. Pesquet, Proximal Splitting Methods in Signal Processing, Fixed-Point Algorithms for Inverse Problems in Science and Engineering, pp.185-212, 2011.
DOI : 10.1007/978-1-4419-9569-8_10
URL : https://hal.archives-ouvertes.fr/hal-00643807

M. A. Davenport, Y. Plan, E. Van-den, M. Berg, and . Wootters, 1-bit matrix completion. CoRR, abs/1209, 2012.
DOI : 10.1093/imaiai/iau006

A. Mark, Y. Davenport, and . Plan, Ewout van den Berg, and Mary Wootters. 1-Bit matrix completion, Inf. Inference, vol.3, 2014.

M. Duarte, M. Davenport, D. Takhar, J. Laska, T. Sun et al., Single-pixel imaging via compressive sampling, IEEE Signal Processing Magazine, vol.25, issue.2, pp.83-91, 2008.
DOI : 10.1109/MSP.2007.914730
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.132.703

M. Dudík, Z. Harchaoui, and J. Malick, Lifted coordinate descent for learning with trace-norm regularization, 2012.

Y. M. Ermol-'ev and P. I. Verchenko, A linearization method in limiting extremal problems, Cybernetics, vol.12, issue.2, pp.240-245, 1976.
DOI : 10.1007/BF01069893

S. Ertekin, L. Bottou, and C. Giles, Nonconvex Online Support Vector Machines, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.33, issue.2, 2011.
DOI : 10.1109/TPAMI.2010.109
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.207.8530

M. Fazel, Matrix rank minimization with applications, 2002.

R. Foygel, R. Salakhutdinov, O. Shamir, and N. Srebro, Learning with the weighted trace-norm under arbitrary sampling distributions, NIPS, pp.2133-2141, 2011.

M. Frank and P. Wolfe, An algorithm for quadratic programming, Naval Research Logistics Quarterly, vol.3, issue.1-2, 1956.
DOI : 10.1002/nav.3800030109

G. Ga¨?ffasga¨?ffas and . Lecué, Sharp Oracle Inequalities for High-Dimensional Matrix Prediction, IEEE Transactions on Information Theory, vol.57, issue.10, pp.6942-6957, 2011.
DOI : 10.1109/TIT.2011.2136318

D. Garber and E. Hazan, Faster rates for the Frank-Wolfe method over strongly-convex sets, ICML, 2015.

D. Garber and E. Hazan, A linearly convergent conditional gradient algorithm with applications to online and stochastic optimization. CoRR, abs/1301, 2015.
DOI : 10.1137/140985366

J. Gaugry, Covering a Ball with Smaller Equal Balls in ?n, Discrete & Computational Geometry, vol.33, issue.1, pp.143-155, 2005.
DOI : 10.1007/s00454-004-2916-2
URL : https://hal.archives-ouvertes.fr/hal-00346015

R. Ge, F. Huang, C. Jin, and Y. Yuan, Escaping from saddle points ? online stochastic gradient for tensor decomposition, COLT, 2015.

S. Ghosh and H. Lam, Computing worst-case input models in stochastic simulation, 2015.

G. H. Golub and C. F. Van-loan, Matrix computations, 1996.

G. H. Golub and C. F. Van-loan, Matrix computations, 2013.

D. Gross, Recovering low-rank matrices from few coefficients in any basis. Information Theory, IEEE Transactions on, vol.57, issue.3, pp.1548-1566, 2011.
DOI : 10.1109/tit.2011.2104999
URL : http://arxiv.org/abs/0910.1879

S. Gunasekar, P. Ravikumar, and J. Ghosh, Exponential family matrix completion under structural constraints, 2014.

Z. Harchaoui, A. Juditsky, and A. Nemirovski, Conditional gradient algorithms for machine learning, NIPS workshop, 2012.

M. Hardt, On the provable convergence of alternating minimization for matrix completion, 2013.

F. M. Harper and J. A. Konstan, The MovieLens Datasets, ACM Transactions on Interactive Intelligent Systems, vol.5, issue.4, 2015.
DOI : 10.1145/2827872

E. Hazan and H. Luo, Variance-reduced and projection-free stochastic optimization, ICML, 2016.

R. A. Horn and C. R. Johnson, Topics in matrix analysis, 1994.
DOI : 10.1017/CBO9780511840371

C. Hsieh and P. A. Olsen, Nuclear norm minimization via active subspace selection, ICML, 2014.

C. Hu, W. Pan, and J. T. Kwok, Accelerated gradient methods for stochastic optimization and online learning, NIPS, pp.781-789, 2009.

J. Hui, L. Chaoqiang, S. Zuowei, and X. Yuhong, Robust video denoising using low rank matrix completion, 2013 IEEE Conference on Computer Vision and Pattern Recognition, pp.1791-1798, 2010.

M. Jaggi, Revisiting Frank-Wolfe: Projection-free sparse convex optimization, 2013.

P. Jain, P. Netrapalli, and S. Sanghavi, Low-rank matrix completion using alternating minimization, Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, STOC '13, pp.665-674, 2013.
DOI : 10.1145/2488608.2488693
URL : http://arxiv.org/abs/1212.0467

L. Ji, P. Musialski, P. Wonka, and Y. Jieping, Tensor Completion for Estimating Missing Values in Visual Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.35, issue.1, pp.208-220, 2013.

B. Jiang, T. Lin, S. Ma, and S. Zhang, Structured nonconvex and nonsmooth optimization: Algorithms and iteration complexity analysis, 2016.

A. B. Juditsky and A. S. Nemirovski, First-Order Methods for Nonsmooth Convex Large-Scale Optimization, I: General Purpose Methods, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00981863

A. B. Juditsky and A. S. Nemirovski, First-Order Methods for Nonsmooth Convex Large-Scale Optimization, II: Utilizing Problem's Structure, 2012.

R. H. Keshavan, A. Montanari, and S. Oh, Matrix completion from noisy entries, J. Mach. Learn. Res, vol.11, pp.2057-2078, 2010.
DOI : 10.1109/isit.2009.5205567
URL : http://arxiv.org/abs/0901.3150

R. Hulikal-keshavan, Efficient algorithms for collaborative filtering, 2012.

O. Klopp, Rank penalized estimators for high-dimensional matrices, Electronic Journal of Statistics, vol.5, issue.0, pp.1161-1183, 2011.
DOI : 10.1214/11-EJS637
URL : https://hal.archives-ouvertes.fr/hal-00583884

O. Klopp, Noisy low-rank matrix completion with general sampling distribution, Bernoulli, vol.20, issue.1, pp.282-303
DOI : 10.3150/12-BEJ486
URL : https://hal.archives-ouvertes.fr/hal-00675413

O. Klopp, J. Lafond, E. Moulines, and J. Salmon, Adaptive multinomial matrix completion, Electronic Journal of Statistics, vol.9, issue.2, 2014.
DOI : 10.1214/15-EJS1093
URL : https://hal.archives-ouvertes.fr/hal-01058447

V. Koltchinskii, A remark on low rank matrix recovery and noncommutative Bernstein type inequalities, Collections, vol.9, pp.213-226, 2013.
DOI : 10.1214/12-IMSCOLL915

V. Koltchinskii, A. B. Tsybakov, and K. Lounici, Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion, The Annals of Statistics, vol.39, issue.5, pp.2302-2329, 2011.
DOI : 10.1214/11-AOS894
URL : https://hal.archives-ouvertes.fr/hal-00676868

Y. Koren, R. Bell, and C. Volinsky, Matrix Factorization Techniques for Recommender Systems, Computer, vol.42, issue.8, pp.30-37, 2009.
DOI : 10.1109/MC.2009.263
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.147.8295

. Lacoste-julien, Convergence rate of frank-wolfe for non-convex objectives, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01415335

S. Lacoste-julien and M. Jaggi, An affine invariant linear convergence analysis for Frank- Wolfe algorithms, NIPS, 2013.

M. Lacoste-julien and . Jaggi, On the global linear convergence of Frank-Wolfe optimization variants, NIPS, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01248675

J. Lafond, Low Rank Matrix Completion with Exponential Family Noise, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01120132

J. Lafond, O. Klopp, E. Moulines, and J. Salmon, Probabilistic low-rank matrix completion on finite alphabets, NIPS, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01081805

J. Lafond, H. T. Wai, and E. Moulines, On the stochastic frank-wolfe algorithms for convex and non-convex optimizations, 2016.

G. Lan and Y. Zhou, Conditional Gradient Sliding for Convex Optimization, SIAM Journal on Optimization, vol.26, issue.2, 2014.
DOI : 10.1137/140992382

M. Ledoux and M. Talagrand, Probability in Banach spaces, 1991.
DOI : 10.1007/978-3-642-20212-4

P. Massart, About the constants in Talagrand's concentration inequalities for empirical processes, Ann. Probab, vol.28, 2000.

R. Mazumder, T. Hastie, and R. Tibshirani, Spectral regularization algorithms for learning large incomplete matrices, J. Mach. Learn. Res, vol.11, pp.2287-2322, 2010.

S. Negahban and M. J. Wainwright, Restricted strong convexity and weighted matrix completion: optimal bounds with noise, J. Mach. Learn. Res, vol.13, 2012.

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

Y. Nesterov, Introductory lectures on convex optimization of Applied Optimization, 2004.

E. Nurminskii, Convergence conditions for nonlinear programming algorithms, Cybernetics, vol.8, issue.6, pp.959-962, 1972.
DOI : 10.1007/BF01068520

M. Raginsky and A. Rakhlin, Information-Based Complexity, Feedback and Dynamics in Convex Programming, IEEE Transactions on Information Theory, vol.57, issue.10, pp.7036-7056, 2011.
DOI : 10.1109/TIT.2011.2154375
URL : http://arxiv.org/abs/1010.2285

B. Recht, A simpler approach to matrix completion, Journal of Machine Learning Research, vol.12, pp.3413-3430, 2011.

B. Recht, M. Fazel, and P. A. Parrilo, Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization, SIAM Review, vol.52, issue.3, pp.471-501, 2010.
DOI : 10.1137/070697835

B. Recht and C. Ré, Parallel stochastic gradient algorithms for large-scale matrix completion, Mathematical Programming Computation, vol.8, issue.2, pp.201-226, 2013.
DOI : 10.1007/s12532-013-0053-8
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.499.9778

H. Robbins and S. Monro, A Stochastic Approximation Method. The Annals of Mathematical Statistics, pp.400-407, 1951.

S. Shalev-shwartz, O. Shamir, and K. Sidharan, Learning Kernel-Based Halfspaces with the 0-1 Loss, SIAM Journal on Computing, vol.40, issue.6, pp.1623-1646, 2011.
DOI : 10.1137/100806126

N. Srebro, Learning with Matrix Factorization, 2004.

N. Srebro and R. R. Salakhutdinov, Collaborative filtering in a non-uniform world: Learning with the weighted trace norm, 2010.

R. Tibshirani, Regression shrinkage and selection via the Lasso, J. R. Stat. Soc. Ser. B Stat. Methodol, vol.58, issue.1, pp.267-288, 1996.

J. A. Tropp, User-Friendly Tail Bounds for Sums of Random Matrices, Foundations of Computational Mathematics, vol.16, issue.2, pp.389-434, 2012.
DOI : 10.1007/s10208-011-9099-z

A. B. Tsybakov, Introduction to nonparametric estimation, 2009.
DOI : 10.1007/b13794

G. A. Watson, Characterization of the subdifferential of some matrix norms, Linear Algebra and its Applications, vol.170, pp.33-45, 1992.
DOI : 10.1016/0024-3795(92)90407-2

P. Wolfe, Convergence theory in nonlinear programming. Integer and Nonlinear Program, 1970.

L. Xiao and T. Zhang, A Proximal Stochastic Gradient Method with Progressive Variance Reduction, SIAM Journal on Optimization, vol.24, issue.4, pp.2057-2075, 2014.
DOI : 10.1137/140961791
URL : http://arxiv.org/abs/1403.4699

H. Xu, W. Jiasong, W. Lu, C. Yang, L. Senhadji et al., Linear Total Variation Approximate Regularized Nuclear Norm Optimization for Matrix Completion, Abstr. Appl. Anal, vol.765782, issue.8, 2014.

Y. Yang, J. Ma, and S. Osher, Seismic data reconstruction via matrix completion, Inverse Problems and Imaging, vol.7, issue.4, pp.1379-1392, 2013.
DOI : 10.3934/ipi.2013.7.1379

Y. Yu, X. Zhang, and D. Schuurmans, Generalized conditional gradient for sparse estimation, 2014.

C. H. Zhang and T. Zhang, A General Framework of Dual Certificate Analysis for Structured Sparse Recovery Problems. arXiv.org, 2012.