A Refined Generalization Analysis for Extreme Multi-class Supervised Contrastive Representation Learning

• URL: http://arxiv.org/abs/2605.07596v2
• Date: Mon, 11 May 2026 06:54:45 GMT
• Title: A Refined Generalization Analysis for Extreme Multi-class Supervised Contrastive Representation Learning
• Abstract summary: We prove a bound with a sample complexity of the same order as the number of classes $R$, regardless of the distribution over classes.<n>We also formulate a different estimator that captures the concentration of the risk textitacross classes.
• Score: 15.903047134800453
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Contrastive Representation Learning (CRL) has achieved strong empirical success in multiple machine learning disciplines, yet its theoretical sample complexity remains poorly understood. Existing analyses usually assume that input tuples are identically and independently distributed, an assumption violated in most practical settings where contrastive tuples are constructed from a finite pool of labeled data, inducing dependencies among tuples. While one recent work analyzed this learning setting using U-Statistics to estimate the population risk, the techniques used therein require the risk of each class to concentrate uniformly, making excess risk bounds scale in the order of $ρ_{\min}^{-{1}/{2}}$ where $ρ_{\min}$ denotes the probability of the rarest class. Such a dependency can be overly pessimistic in the extreme multiclass settings where there are many tail classes which contribute minimally to the overall population risk. Our contributions are two-fold. Firstly, we improve upon the previous work and prove a bound with a sample complexity of the same order as the number of classes $R$, regardless of the distribution over classes. Furthermore, we formulate a different estimator that captures the concentration of the risk \textit{across classes}, enabling sharper bounds in extreme multi-class learning scenarios, especially where class distributions are long-tailed. Under mild assumptions on the class distributions, the resulting sample complexity is $\mathcal{O}(k)$ where $k$ is the number of samples per tuple.

Related papers

• Multi-Objective Learning for Diffusion Models: A Statistical Theory under Semi-Supervised Learning [83.65494573724904]
  We develop a principled MOL framework for diffusion models with limited data.<n>We propose a two-stage training procedure that first fits lightweight specialist models from limited paired data.<n>We establish bounds generalization showing that the required number of paired samples only depends on the complexity of the specialist model classes.
  arXiv  Detail & Related papers  (2026-05-24T18:19:40Z)
• Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noise [26.182166506085114]
  We show that learning across $k$ distributions incurs slow rates scaling with $k/2$, even under constant noise levels, unless each distribution is learned separately.<n>A key technical contribution is a structured hypothesis-testing framework that captures the statistical cost of certifying near-optimality.
  arXiv  Detail & Related papers  (2026-02-24T16:00:15Z)
• Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness [63.833913892018536]
  We study sequential decision making under distributional adversaries that can adaptively choose data-generating distributions from a fixed family $U$.<n>We provide a near complete characterization of families $U$ that admit learnability in terms of a notion known as generalized smoothness.<n>We show that the generalized smoothness also characterizes private learnability under distributional constraints.
  arXiv  Detail & Related papers  (2026-02-24T06:15:59Z)
• Sharper Risk Bound for Multi-Task Learning with Multi-Graph Dependent Data [5.42833955464548]
  Existing generalization analyses yield a emphsub-optimal risk bound of $O(frac1sqrtn)$, where $n$ is the number of training samples of each task.<n>This paper proposes a new Bennett-type inequality, enabling the derivation of a sharper risk bound of $O(fraclog nn)$.
  arXiv  Detail & Related papers  (2025-02-25T12:57:53Z)
• Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
  Longtailed distributions frequently emerge in real-world data, where a large number of minority categories contain a limited number of samples. Recent investigations have revealed that supervised contrastive learning exhibits promising potential in alleviating the data imbalance. We propose a novel probabilistic contrastive (ProCo) learning algorithm that estimates the data distribution of the samples from each class in the feature space.
  arXiv  Detail & Related papers  (2024-03-11T13:44:49Z)
• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  We study a variant of Collaborative PAC Learning, in which we aim to learn an accurate classifier for each of the $n$ data distributions. We show that, when the data distributions satisfy a weaker realizability assumption, sample-efficient learning is still feasible.
  arXiv  Detail & Related papers  (2024-02-16T04:32:22Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions.<n>We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  Social and real-world considerations have given rise to multi-distribution learning paradigms. We establish the optimal sample complexity of these learning paradigms and give algorithms that meet this sample complexity. Our algorithm design and analysis are enabled by our extensions of online learning techniques for solving zero-sum games.
  arXiv  Detail & Related papers  (2022-10-22T19:07:26Z)
• Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks [25.832511407411637]
  A fundamental problem in adversarial machine learning is to quantify how much training data is needed in the presence of evasion attacks. We work with probability distributions on the input data that satisfy a Lipschitz condition: nearby points have similar probability. For every fixed $k$ the class of $k$-decision lists has sample complexity against a $log(n)$-bounded adversary.
  arXiv  Detail & Related papers  (2022-05-12T14:40:18Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  We develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers. We find that test errors tend to concentrate around a small typical value $varepsilon*$, which deviates substantially from the test error of worst-case interpolating model. Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice.
  arXiv  Detail & Related papers  (2020-06-22T21:12:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.