Lune

NeurIPS2024Top-tier venue

Trading off Consistency and Dimensionality of Convex Surrogates for Multiclass Classification

Enrique B. Nueve, Dhamma Kimpara, Bo Waggoner, Jessica Finocchiaro

Abstract

In multiclass classification over n outcomes, we typically optimize some surrogate loss L : R d × Y → R assigning real-valued error to predictions in R d . In this paradigm, outcomes must be embedded into the reals with dimension d ≈ n in order to design a consistent surrogate loss. Consistent losses are well-motivated theoretically, yet for large n, such as in information retrieval and structured prediction tasks, their optimization may be computationally infeasible. In practice, outcomes are typically embedded into some R d for d ≪ n, with little known about their suitability for multiclass classification. We investigate two approaches for trading off consistency and dimensionality in multiclass classification while using a convex surrogate loss. We first formalize partial consistency when the optimized surrogate has dimension d ≪ n. We then check if partial consistency holds under a given embedding and low-noise assumption, providing insight into when to use a particular embedding into R d . Finally, we present a new method to construct (fully) consistent losses with d ≪ n out of multiple problem instances. Our practical approach leverages parallelism to sidestep lower bounds on d.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Consistency Conditions for Differentiable Surrogate LossesDrona Khurana, Anish Thilagar, Dhamma Kimpara, Rafael M. FrongilloNeurIPS 2025 · 2 citations

Related papers

  1. Generalizing Consistent Multi-Class Classification with Rejection to be Compatible with Arbitrary LossesYuzhou Cao, Tianchi Cai, Lei Feng, Lihong Gu et al.NeurIPS 2022 · 42 citations
  2. Consistent Polyhedral Surrogates for Top-k Classification and VariantsAnish Thilagar, Rafael M. Frongillo, Jessica Finocchiaro, Emma GoodwillICML 2022 · 15 citations
  3. Bayes Consistency vs. H-Consistency: The Interplay between Surrogate Loss Functions and the Scoring Function ClassMingyuan Zhang, Shivani AgarwalNeurIPS 2020 · 42 citations
  4. Multi-Class HH-Consistency BoundsPranjal Awasthi, Anqi Mao, Mehryar Mohri, Yutao ZhongNeurIPS 2022 · 48 citations
  5. Towards Consistency in Adversarial ClassificationLaurent Meunier, Raphael Ettedgui, Rafael Pinot, Yann Chevaleyre et al.NeurIPS 2022 · 12 citations
Dusk over the sea between two cliffs drawn in fine vertical lines