Sharp Analysis of Learning with Discrete Losses

Alex Nowak, Francis Bach, Alessandro Rudi
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:1920-1929, 2019.

Abstract

The problem of devising learning strategies for discrete losses (e.g., multilabeling, ranking) is currently addressed with methods and theoretical analyses ad-hoc for each loss. In this paper we study a least-squares framework to systematically design learning algorithms for discrete losses, with quantitative characterizations in terms of statistical and computational complexity. In particular, we improve existing results by providing explicit dependence on the number of labels for a wide class of losses and faster learning rates in conditions of low-noise. Theoretical results are complemented with experiments on real datasets, showing the effectiveness of the proposed general approach.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-nowak19a, title = {Sharp Analysis of Learning with Discrete Losses}, author = {Nowak, Alex and Bach, Francis and Rudi, Alessandro}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {1920--1929}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/nowak19a/nowak19a.pdf}, url = {https://proceedings.mlr.press/v89/nowak19a.html}, abstract = {The problem of devising learning strategies for discrete losses (e.g., multilabeling, ranking) is currently addressed with methods and theoretical analyses ad-hoc for each loss. In this paper we study a least-squares framework to systematically design learning algorithms for discrete losses, with quantitative characterizations in terms of statistical and computational complexity. In particular, we improve existing results by providing explicit dependence on the number of labels for a wide class of losses and faster learning rates in conditions of low-noise. Theoretical results are complemented with experiments on real datasets, showing the effectiveness of the proposed general approach.} }
Endnote
%0 Conference Paper %T Sharp Analysis of Learning with Discrete Losses %A Alex Nowak %A Francis Bach %A Alessandro Rudi %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-nowak19a %I PMLR %P 1920--1929 %U https://proceedings.mlr.press/v89/nowak19a.html %V 89 %X The problem of devising learning strategies for discrete losses (e.g., multilabeling, ranking) is currently addressed with methods and theoretical analyses ad-hoc for each loss. In this paper we study a least-squares framework to systematically design learning algorithms for discrete losses, with quantitative characterizations in terms of statistical and computational complexity. In particular, we improve existing results by providing explicit dependence on the number of labels for a wide class of losses and faster learning rates in conditions of low-noise. Theoretical results are complemented with experiments on real datasets, showing the effectiveness of the proposed general approach.
APA
Nowak, A., Bach, F. & Rudi, A.. (2019). Sharp Analysis of Learning with Discrete Losses. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:1920-1929 Available from https://proceedings.mlr.press/v89/nowak19a.html.

Related Material