Fine-grained generalization analysis of vector-valued learning

Liang Wu, Antoine Ledent, Yunwen Lei, Marius Kloft

Research output: Chapter in Book/Report/Conference proceedingConference contribution

54 Downloads (Pure)

Abstract

Many fundamental machine learning tasks can be formulated as a problem of learning with vector-valued functions, where we learn multiple scalar-valued functions together. Although there is some generalization analysis on different specific algorithms under the empirical risk minimization principle, a unifying analysis of vector-valued learning under a regularization framework is still lacking. In this paper, we initiate the generalization analysis of regularized vector-valued learning algorithms by presenting bounds with a mild dependency on the output dimension and a fast rate on the sample size. Our discussions relax the existing assumptions on the restrictive constraint of hypothesis spaces, smoothness of loss functions and low-noise condition. To understand the interaction between optimization and learning, we further use our results to derive the first generalization bounds for stochastic gradient descent with vector-valued functions. We apply our general results to multi-class classification and multi-label classification, which yield the first bounds with a logarithmic dependency on the output dimension for extreme multi-label classification with the Frobenius regularization. As a byproduct, we derive a Rademacher complexity bound for loss function classes defined in terms of a general strongly convex function.
Original languageEnglish
Title of host publicationAAAI'21 Proceedings of the Thirty-fifth AAAI Conference on Artificial Intelligence
PublisherAAAI Press
Pages10338-10346
Number of pages9
ISBN (Print)9781577358664
Publication statusPublished - 18 May 2021
Event35th AAAI Conference on Artificial Intelligence - Vancouver, Canada
Duration: 2 Feb 20219 Feb 2021
Conference number: 35
https://aaai.org/Conferences/AAAI-21/

Publication series

NameProceedings of the AAAI Conference on Artificial Intelligence
PublisherAAAI Press
Number12
Volume35
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468

Conference

Conference35th AAAI Conference on Artificial Intelligence
Abbreviated titleAAAI-21
Country/TerritoryCanada
CityVancouver
Period2/02/219/02/21
Internet address

Keywords

  • Learning Theory

Fingerprint

Dive into the research topics of 'Fine-grained generalization analysis of vector-valued learning'. Together they form a unique fingerprint.

Cite this