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.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers1
Related papers
- 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
- Consistent Polyhedral Surrogates for Top-k Classification and VariantsAnish Thilagar, Rafael M. Frongillo, Jessica Finocchiaro, Emma GoodwillICML 2022 · 15 citations
- Bayes Consistency vs. H-Consistency: The Interplay between Surrogate Loss Functions and the Scoring Function ClassMingyuan Zhang, Shivani AgarwalNeurIPS 2020 · 42 citations
- Multi-Class -Consistency BoundsPranjal Awasthi, Anqi Mao, Mehryar Mohri, Yutao ZhongNeurIPS 2022 · 48 citations
- Towards Consistency in Adversarial ClassificationLaurent Meunier, Raphael Ettedgui, Rafael Pinot, Yann Chevaleyre et al.NeurIPS 2022 · 12 citations
