Optimistic Bounds for Multi-output Learning

Henry W. J. Reeve, Ata KabánICML 2020 · OpenReview

Introduction

In the realm of multi-output learning—where the goal is to learn a vector-valued function from a supervised dataset—theoretical guarantees often struggle to keep pace with empirical success. Reeve and Kabán address this gap by introducing a novel "self-bounding Lipschitz condition" for multi-output loss functions. This condition elegantly bridges the gap between standard Lipschitz continuity and smoothness. By leveraging this framework, the authors derive "optimistic" generalization bounds that achieve fast convergence rates (up to $O(1/n)$) when the empirical error is small, while maintaining a highly favorable, often logarithmic, dependence on the number of output dimensions.

The Challenge of Multi-Output Learning

Modern machine learning frequently tackles "multi-output" problems, such as extreme classification with thousands of categories or complex multi-label tagging. Theoretical guarantees for these models typically face two major hurdles:

  1. Slow Convergence: Most standard generalization bounds converge at a rate of $O(1/\sqrt{n})$, where $n$ is the sample size. Achieving "fast rates" of $O(1/n)$ usually requires restrictive assumptions about the underlying data distribution (such as the Tsybakov margin condition), which are virtually impossible to verify in practice.
  2. The Curse of Dimensionality: Many existing bounds scale linearly with the number of outputs ($q$). In extreme classification scenarios involving tens of thousands of labels, a linear dependence renders the theoretical bound practically useless.

The authors seek a framework that provides fast convergence rates based on the properties of the loss function itself—which practitioners can choose and analyze—rather than relying on the unknown data distribution, all while keeping the dependence on $q$ sub-linear.

Methodology: The Self-Bounding Lipschitz Condition

The core innovation of this paper is the self-bounding Lipschitz condition.

  • The Condition: A loss function is defined as $(\lambda, \theta)$-self-bounding if the difference in loss between two predictions is bounded by the maximum of those losses (raised to the power $\theta$) multiplied by the distance between the predictions, measured in the $\ell_\infty$ norm.
  • Interpolation: This condition is highly expressive because it interpolates between known properties: when $\theta=0$, it recovers a standard Lipschitz condition; when $\theta=1/2$, it yields a multi-dimensional version of a "smoothness" condition.
  • Local Rademacher Complexity: To tighten the bounds, the authors employ "local" Rademacher complexity, which effectively "zooms in" on the subset of functions that perform well on the training data.
  • Vector Contraction: They prove a new contraction inequality for this local complexity. Crucially, they utilize a minoration inequality to handle the $\ell_\infty$ norm, which serves as the key mechanism for keeping the dependence on the number of classes ($q$) low.

Key Insights

  • Verifiable Fast Rates: Unlike previous "fast rate" theories that depend on opaque data distributions, the self-bounding property is a characteristic of the loss function. Researchers can analytically verify if their chosen loss satisfies the condition.
  • The Power of the $\ell_\infty$ Norm: By measuring prediction distance using the $\ell_\infty$ norm (the maximum difference across any single output) rather than the $\ell_2$ norm (the sum of squares), the error does not accumulate as the number of classes grows. This strategic choice leads to bounds that scale with $\log(q)$ instead of $q$.
  • Optimism Pays Off: The derived bounds are "optimistic" because they naturally tighten as the model's performance improves. If the training error is near zero, the generalization gap shrinks much faster ($O(1/n)$) compared to scenarios with large training errors ($O(1/\sqrt{n})$).

Key Results and Applications

While this is a theoretical paper and does not rely on empirical datasets for benchmarking, the authors demonstrate the utility of their theory by applying it to widely used loss functions and model classes:

  • Softmax is Self-Bounding: The authors rigorously prove that the ubiquitous multinomial logistic (softmax) loss is $(2, 1/2)$-self-bounding. This foundational result immediately provides tighter bounds for many existing deep learning and boosting models.
  • State-of-the-Art Bounds for Boosting: They derive a new generalization bound for ensembles of multi-output decision trees (e.g., Gradient Boosting). This bound exhibits a logarithmic dependence on the number of classes, significantly outperforming previous bounds that scaled linearly with $q$.
  • Minimax Optimality: The convergence rates achieved under this framework are shown to be minimax optimal—representing the best possible rate any algorithm could achieve—up to logarithmic factors.

Limitations and Future Directions

Despite its strong theoretical contributions, the paper notes a few limitations and avenues for future work:

  • Unspecified Constants: The bounds involve numerical constants that, while finite, are not explicitly tightened for practical, "plug-and-play" value calculation.
  • Function Class Restrictions: The current analysis for tree ensembles assumes specific constraints, such as $\ell_1$ constraints on leaf values. Extending this analysis to unconstrained or differently regularized architectures remains an open research path.
  • Empirical Validation: The theory elegantly explains why certain methods succeed in high-dimensional spaces; however, the paper does not include large-scale experiments to compare the tightness of these theoretical bounds against actual empirical generalization gaps on standard benchmarks.

Summary updated

Abstract

We investigate the challenge of multi-output learning, where the goal is to learn a vector-valued function based on a supervised data set. This includes a range of important problems in Machine Lea...
BibTeX
@inproceedings{reeve2020optimistic,
  author = {Henry W. J. Reeve and Ata Kabán},
  title = {{Optimistic Bounds for Multi-output Learning}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=PWLVmPzMR6},
}
Figure