mlsanityData to 7 Oct 2026

Sharp Analysis of Learning with Discrete Losses

arXiv 1810.06839 ↗First posted 16 Oct 2018cs.LG cs.AI cs.CCcited by 13

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). First posted on arXiv 16 Oct 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 2; 2023: 2; 2024: 3; 2025: 1; 2026: 3.

13 papers.

Sort:

  1. 2024A Universal Growth Rate for Learning with Smooth Surrogate Lossescited by 24
  2. 2021Fast rates in structured predictioncited by 11
  3. 2023Active Self-Supervised Learning: A Few Low-Cost Relationships Are All You Needcited by 9
  4. 2024Online Structured Prediction with Fenchel--Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Losscited by 7
  5. 2022Multiclass learning with margin: exponential rates with no bias-variance trade-offcited by 5
  6. 2023Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernelscited by 5
  7. 2021Disambiguation of weak supervision with exponential convergence ratescited by 4
  8. 2024Deep Sketched Output Kernel Regression for Structured Predictioncited by 2
  9. 2025Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Lossescited by 2
  10. 2026Linear-Core Surrogates: Smooth Loss Functions with Linear Rates for Classification and Structured Predictioncited by 2
  11. 2026Exact Rank and Convex Calibration Dimension Lower Bounds for the Multi-Label F1 Losscited by 1
  12. 2022From Weakly Supervised Learning to Active Learningcited by 0
1 more
  1. 2026Exponential Convex Calibration Dimension for the Multi-Label Jaccard Measurecited by 0