Fine-grained Generalization Analysis of Vector-Valued Learning

Authors

  • Liang Wu Southwestern University of Finance and Economics
  • Antoine Ledent TU Kaiserslautern
  • Yunwen Lei University of Birmingham TU Kaiserslautern
  • Marius Kloft TU Kaiserslautern

Keywords:

Learning Theory

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.

Downloads

Published

2021-05-18

How to Cite

Wu, L., Ledent, A., Lei, Y., & Kloft, M. (2021). Fine-grained Generalization Analysis of Vector-Valued Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12), 10338-10346. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17238

Issue

Section

AAAI Technical Track on Machine Learning V