P. Agrawal, K. Vikas, R. Garg, and . Narayanam, Link label prediction in signed social networks, IJCAI, pp.2591-2597, 2013.

W. Bian and D. Tao, Learning a Distance Metric by Empirical Loss Minimization, IJCAI, pp.1186-1191, 2011.

D. Cai and X. He, Manifold Adaptive Experimental Design for Text Categorization, IEEE Transactions on Knowledge and Data Engineering, vol.24, issue.4, pp.707-719, 2012.

Q. Cao, Z. Guo, and Y. Ying, Generalization Bounds for Metric and Similarity Learning, 2012.

Q. Cao, Y. Ying, and P. Li, Distance Metric Learning Revisited, ECML/PKDD, pp.283-298, 2012.

R. Caruana, N. Karampatziakis, and A. Yessenalina, An empirical evaluation of supervised learning in high dimensions, ICML, pp.96-103, 2008.

C. Chih, C. Chang, and . Lin, LIBSVM : a library for support vector machines, ACM Transactions on Intelligent Systems and Technology, vol.2, issue.3, pp.27-27, 2011.

Y. Chang, C. Hsieh, K. Chang, M. Ringgaard, and C. Lin, Training and Testing Low-degree Polynomial Data Mappings via Linear SVM, Journal of Machine Learning Research, vol.11, pp.1471-1490, 2010.

G. Chechik, U. Shalit, V. Sharma, and S. Bengio, An online algorithm for large scale image similarity learning, NIPS, pp.306-314, 2009.

Y. Chen, D. Pavlov, and J. F. Canny, Large-scale behavioral targeting, KDD, 2009.

K. L. Clarkson, Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm, ACM Transactions on Algorithms, vol.6, issue.4, pp.1-30, 2010.

I. Stéphan-clémençon, A. Colin, and . Bellet, Scaling-up Empirical Risk Minimization: Optimization of Incomplete U-statistics, Journal of Machine Learning Research, vol.17, issue.76, pp.1-36, 2016.

. Stéphan-clémençon, N. Lugosi, and . Vayatis, Ranking and Empirical Minimization of Ustatistics, Annals of Statistics, vol.36, issue.2, pp.844-874, 2008.

J. V. Davis, B. Kulis, P. Jain, S. Sra, and I. S. Dhillon, Information-theoretic metric learning, ICML, pp.209-216, 2007.

K. Rong-en-fan, C. Chang, X. Hsieh, C. Wang, and . Lin, LIBLINEAR: A Library for Large Linear Classification, Journal of Machine Learning Research, vol.9, pp.1871-1874, 2008.

S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing, 2013.

D. Fradkin and D. Madigan, Experiments with random projections for machine learning, KDD, pp.517-522, 2003.

M. Frank and P. Wolfe, An algorithm for quadratic programming, Naval Research Logistics Quarterly, vol.3, issue.1-2, pp.95-110, 1956.

M. Robert, P. Freund, and . Grigas, New Analysis and Results for the Conditional Gradient Method, 2013.

X. Gao, C. H. Steven, Y. Hoi, J. Zhang, J. Wan et al., SOML: Sparse Online Metric Learning with Application to Image Retrieval, AAAI, pp.1206-1212, 2014.

J. Goldberger, S. Roweis, G. Hinton, and R. Salakhutdinov, Neighbourhood Components Analysis, NIPS, pp.513-520, 2004.

J. Guélat and P. Marcotte, Some comments on Wolfe's away step, Mathematical Programming, vol.35, issue.1, pp.110-119, 1986.

M. Guillaumin, J. J. Verbeek, and C. Schmid, Is that you? Metric learning approaches for face identification, ICCV, pp.498-505, 2009.
URL : https://hal.archives-ouvertes.fr/inria-00439290

C. Zheng-, Y. Guo, and . Ying, Guaranteed Classification via Regularized Similarity Learning, Neural Computation, vol.26, issue.3, pp.497-522, 2014.

I. Guyon, S. R. Gunn, A. Ben-hur, and G. Dror, Result Analysis of the NIPS 2003 Feature Selection Challenge, NIPS, 2004.

W. Hoeffding, A Class of Statistics with Asymptotically Normal Distribution, The Annals of Mathematical Statistics, vol.19, issue.3, pp.293-325, 1948.
DOI : 10.1007/978-1-4612-0865-5_8

M. Jaggi, Sparse Convex Optimization Methods for Machine Learning, 2011.

M. Jaggi, Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization, ICML, 2013.

L. Jain, B. Mason, and R. Nowak, Learning Low-Dimensional Metrics, NIPS, 2017.

R. Jin, S. Wang, and Y. Zhou, Regularized Distance Metric Learning: Theory and Algorithm, NIPS, 2009.

D. Kedem, S. Tyree, K. Weinberger, F. Sha, and G. Lanckriet, Non-linear Metric Learning, NIPS, pp.2582-2590, 2012.

B. Kulis, Metric Learning: A Survey. Foundations and Trends in Machine Learning, vol.5, pp.287-364, 2012.
DOI : 10.1561/2200000019

S. Lacoste, -. , and M. Jaggi, On the Global Linear Convergence of Frank-Wolfe Optimization Variants, NIPS, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01248675

R. Andrew, V. J. Leach, and . Gillet, An Introduction to Chemoinformatics, 2007.

A. J. Lee, U-Statistics: Theory and Practice, 1990.

D. K. Lim, B. Mcfee, and G. Lanckriet, Robust Structural Metric Learning, ICML, 2013.

K. Liu, A. Bellet, and F. Sha, Similarity Learning for High-Dimensional Sparse Data, AISTATS, pp.653-662, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01430854

W. Liu, C. Mu, R. Ji, S. Ma, J. R. Smith et al., Low-Rank Similarity Metric Learning in High Dimensions, AAAI, 2015.

C. Mcdiarmid, On the method of bounded differences, vol.141, pp.148-188, 1989.

G. Qi, J. Tang, Z. Zha, T. Chua, and H. Zhang, An Efficient Sparse Metric Learning in High-Dimensional Space via l1-Penalized Log-Determinant Regularization, ICML, 2009.
DOI : 10.1145/1553374.1553482
URL : http://www.cs.mcgill.ca/~icml2009/papers/46.pdf

Q. Qian, R. Jin, S. Zhu, and Y. Lin, An Integrated Framework for High Dimensional Distance Metric Learning and Its Application to Fine-Grained Visual Categorization, 2014.

Q. Qian, R. Jin, L. Zhang, and S. Zhu, Towards making high dimensional distance metric learning practical, 2015.

R. Rosales and G. Fung, Learning Sparse Metrics via Linear Programming, KDD, pp.367-373, 2006.
DOI : 10.1145/1150402.1150444

M. Schultz and T. Joachims, Learning a Distance Metric from Relative Comparisons, NIPS, 2003.

R. J. Serfling, Probability inequalities for the sum in sampling without replacement, The Annals of Statistics, vol.2, issue.1, pp.39-48, 1974.
DOI : 10.1214/aos/1176342611
URL : https://doi.org/10.1214/aos/1176342611

S. Shalev, -. Shwartz, and S. Ben-david, Understanding Machine Learning: From Theory to Algorithms, 2014.

C. Shen, J. Kim, L. Wang, and A. Van-den-hengel, Positive Semidefinite Metric Learning Using Boosting-like Algorithms, Journal of Machine Learning Research, vol.13, pp.1007-1036, 2012.

Y. Shi, A. Bellet, and F. Sha, Sparse Compositional Metric Learning, AAAI, pp.2078-2084, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01430847

J. St, J. Amand, and . Huan, Sparse Compositional Local Metric Learning, KDD, 2017.

N. Verma and K. Branson, Sample complexity of learning mahalanobis distance metrics, NIPS, 2015.

J. Wang, A. Woznica, and A. Kalousis, Parametric Local Metric Learning for Nearest Neighbor Classification, NIPS, pp.1610-1618, 2012.

Q. Kilian, L. K. Weinberger, and . Saul, Distance Metric Learning for Large Margin Nearest Neighbor Classification, Journal of Machine Learning Research, vol.10, pp.207-244, 2009.

D. Yao, P. Zhao, T. Pham, and G. Cong, High-dimensional Similarity Learning via Dual-sparse Random Projection, IJCAI, 2018.
DOI : 10.24963/ijcai.2018/417
URL : https://www.ijcai.org/proceedings/2018/0417.pdf

Y. Ying and P. Li, Distance Metric Learning with Eigenvalue Optimization, Journal of Machine Learning Research, vol.13, pp.1-26, 2012.

Y. Ying, K. Huang, and C. Campbell, Sparse Metric Learning via Smooth Optimization, NIPS, pp.2214-2222, 2009.

J. Zhang and L. Zhang, Efficient Stochastic Optimization for Low-Rank Distance Metric Learning, AAAI, 2017.