Note that LGAUC takes the form of a sum over indicators, and can be interpreted as the average 0/1-loss over C. This function is clearly not convex in g, and is therefore difficult to optimize.

Algorithms 2, 3 and 4 instead optimize a convex upper bound on LGAUC by replacing indicators by the hinge loss:

$$h(x)={\begin{cases}0&x\leq0\\ x&x>0\end{cases}}.$$

As in SVM, this is accomplished by introducing a unit margin and slack variable ξ**ijkℓ** for each
(i, j, k, ℓ) ∈ C, and minimizing 1/|C|PC
ξ**ijkℓ**.

## References

Sameer Agarwal, Joshua Wills, Lawrence Cayton, Gert Lanckriet, David Kriegman, and Serge Belongie. Generalized non-metric multi-dimensional scaling. In Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, 2007.

A. V. Aho, M. R. Garey, and J. D. Ullman. The transitive reduction of a directed graph. *SIAM Journal on Computing*, 1(2):131–137, 1972. doi: 10.1137/0201008. URL
http://link.aip.org/link/?SMJ/1/131/1.
Anelia Angelova. Data pruning. Master's thesis, California Institute of Technology, 2004.

Anelia Angelova, Yaser Abu-Mostafa, and Pietro Perona. Pruning training sets for learning of object categories. *Computer Vision and Pattern Recognition, IEEE Computer Society Conference on*, 1:
494–501, 2005. ISSN 1063-6919. doi: http://doi.ieeecomputersociety.org/10.1109/CVPR.2005.

283.
Dana Angluin and Philip Laird. Learning from noisy examples. *Mach. Learn.*, 2(4):343–370, 1988.

ISSN 0885-6125. doi: http://dx.doi.org/10.1023/A:1022873112823.

Francis R. Bach. Consistency of the group lasso and multiple kernel learning. *J. Mach. Learn. Res.*,
9:1179–1225, 2008. ISSN 1532-4435.

Yoshua Bengio, Jean-François Paiement, Pascal Vincent, Olivier Delalleau, Nicolas Le Roux, and Marie Ouimet. Out-of-sample extensions for lle, isomap, mds, eigenmaps, and spectral clustering. 2004.

Bonnie Berger and Peter W. Shor. Approximation alogorithms for the maximum acyclic subgraph problem. In SODA '90: Proceedings of the first annual ACM-SIAM symposium *on Discrete* algorithms, pages 236–243, Philadelphia, PA, USA, 1990. Society for Industrial and Applied Mathematics. ISBN 0-89871-251-3.

Mikhail Bilenko, Sugato Basu, and Raymond J. Mooney. Integrating constraints and metric learning in semi-supervised clustering. In *Proceedings of the Twenty-first International Conference on* Machine Learning, pages 81–88, 2004.
Ingwer Borg and Patrick J.F. Groenen. *Modern Multidimensional Scaling: Theory and Applications*.

Springer-Verlag, second edition, 2005.