Sharp Analysis of Learning with Discrete Losses

Alex Nowak-Vila, Francis R. Bach, Alessandro Rudi

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.

Introduction

In modern machine learning, many tasks involve predicting structured outputs where success is measured by discrete, non-smooth losses. Examples include multilabel classification (predicting sets of tags) and ranking (ordering items by relevance). Traditionally, these problems have been tackled using ad-hoc surrogate losses, such as Structured SVMs (SSVM), tailored to specific metrics like Hamming loss or F-score. However, these methods often lack Fisher consistency—meaning they may not converge to the true optimal predictor even with infinite data—and their theoretical guarantees often suffer from an "exponential curse," where complexity bounds grow exponentially with the number of labels ($m$).

This paper introduces a unified, theoretically "sharp" framework based on Quadratic Surrogates (QS). By leveraging a least-squares approach, the authors demonstrate that structured prediction can be solved with statistical guarantees that scale only polynomially with the number of labels, while achieving faster learning rates in low-noise scenarios.

The Quadratic Surrogate Framework

The core of the proposed approach is the transformation of a discrete optimization problem into a continuous regression task. This is achieved through an Affine Decomposition of the loss matrix $L$:

$$L = FU^\top + c\mathbf{1}$$

This decomposition allows the mapping of discrete labels into a lower-dimensional continuous space. The learning process then follows two main steps:

  1. Training: Solve a vector-valued Kernel Ridge Regression (KRR) to estimate the conditional expectation of the labels.
  2. Inference (Decoding): For a new input, find the discrete label that minimizes the inner product between its representative vector in the $F$ matrix and the regression output.

To achieve faster convergence, the authors introduce a generalized Tsybakov margin condition for discrete losses. This condition quantifies the "cleanness" of the data near decision boundaries, allowing the model to learn more efficiently when the noise level is low.

Figure 1: Visualization of decision regions and the generalized Tsybakov margin (2ε) on a simplex for a three-class problem.

Sharp Theoretical Guarantees

A major contribution of this work is the derivation of explicit constants for a wide variety of common losses. Unlike previous frameworks that suggested exponential growth in complexity ($2^m$), this analysis proves that for many complex losses, the statistical cost is remarkably manageable. For instance, the statistical cost for the Hamming loss is shown to be a constant $1/2$, completely independent of the number of labels.

Figure 2: Summary of Multilabel and Ranking measures, including their definitions and complexity parameters (r, A, and inference complexity).

As shown in the table above, the framework covers a broad spectrum of measures, from standard 0-1 loss to sophisticated ranking metrics like NDCG and Mean Average Precision (MAP). By applying the Tsybakov-like margin condition, the authors prove that the learning rate can improve from $O(n^{-1/4})$ to nearly $O(n^{-1/2})$, significantly reducing the sample size required for high accuracy in favorable data conditions.

Empirical Validation and Complexity

The framework was validated across multiple standard benchmarks, including nine multilabeling datasets (e.g., bibtex, mediamill, yeast) and the Ohsumed ranking dataset. In head-to-head comparisons, the QS estimator consistently outperformed Structured SVMs and other baselines, particularly for 0-1 loss and F-score metrics.

To handle large-scale datasets, the authors utilized random projection techniques, reducing the training complexity from $O(n^3)$ to $O(n\sqrt{nr})$. However, they note a remaining challenge in Inference Complexity. While the statistical learning is efficient, the "decoding" step for certain losses like Pairwise Disagreement (PD) or MAP remains NP-Hard. In these cases, while the framework identifies the optimal target to estimate, the final discrete prediction requires efficient approximation algorithms.

Conclusion

This research provides a powerful unified lens for understanding and solving discrete loss problems. By replacing ad-hoc surrogates with a consistent quadratic framework, the authors have debunked the "exponential curse" for many structured prediction tasks and provided a clear path toward faster, more reliable learning algorithms. Future work will likely focus on bridging the gap between these sharp statistical bounds and the computational hurdles of NP-Hard inference for complex ranking metrics.

Summary updated

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.
BibTeX
@inproceedings{nowakvila2019sharp,
  author = {Alex Nowak-Vila and Francis R. Bach and Alessandro Rudi},
  title = {{Sharp Analysis of Learning with Discrete Losses}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=HPmGUb9ZcTg},
}
Figure