ICML 2026 论文列表

The Rademacher complexity of a function class is among the most basic notions of its ``size'' and yields classical offline generalization bounds for Lipschitz loss functions that lead in turn to a modern understanding of statistical learning. More recently, the *sequential* and *offset* Rademacher complexities were introduced to prove analogous generalization bounds for online learning and for prediction with squared loss. A fundamental structural result in the theory of Rademacher complexity, with many applications to learning theory, is the Ledoux--Talagrand contraction lemma, which states that the Rademacher complexity of a composition of a function class with a fixed Lipschitz function is at most that of the original class. We show that, under structural assumptions on the function class, this contraction extends to sequential and offset Rademacher complexity at the price of polylogarithmic factors. We further show that these logarithmic factors cannot be removed in general and, absent these additional structural assumptions, no such contraction inequality can hold. These results together indicate that the sequential and offset Rademacher complexities behave fundamentally differently from the classical Rademacher complexity with respect to contraction, which in turn has broad implications for understanding the sample complexities of online learning and regression with squared loss for composed function classes.

This paper considers a novel variant of the online fair division problem involving multiple agents in which a learner sequentially observes an indivisible item that must be irrevocably allocated to one of the agents to achieve a desired balance between fairness and efficiency. Existing algorithms assume a small number of items with a sufficiently large number of copies, which ensures a good utility estimation for all item-agent pairs from noisy observed utilities. However, this assumption may not hold in many real-life applications, e.g., an online platform with a large number of users (items) who use the platform's service providers (agents) only a few times (a few copies of items), making it difficult to accurately estimate utilities for all item-agent pairs. To address this limitation, we assume utility is an unknown function of item-agent features. We propose algorithms that model online fair division as a contextual bandit problem, achieving provable sub-linear regret. Our experimental results further validate the effectiveness of the proposed algorithms. The code is publicly available in this [GitHub repository](https://github.com/arunv3rma/SEDMA.git).

We study the fine-grainded uniform convergence behavior of halfspaces beyond worst-case VC bounds. For inhomogeneous halfspaces in $\mathbb{R}^d$ with $d\ge 2$, we show that standard first-order VC bounds are essentially tight: even consistent hypotheses can incur population error $\Theta(d\log(n/d)/n)$, and in the agnostic setting the deviation scales as $\sqrt{\tau\log(1/\tau)}$ at true error $\tau$. In contrast, homogeneous halfspaces in $\mathbb{R}^2$ exhibit a markedly different behavior. In the realizable case, every hypothesis consistent with the sample has error $O(1/n)$. In the agnostic case, we prove a bandwise, log-free deviation bound on each dyadic risk band via a critical-wedge localization argument. Unioning over bands incurs only a $\log\log n$ overhead, and we establish a matching lower bound showing this overhead is unavoidable. Together, these results give a fine-grained and nearly complete picture of uniform convergence for halfspaces, revealing sharp dimensional and structural thresholds.

Adversarial imitation learning (AIL) achieves high-quality imitation by mitigating compounding errors inherent to behavioral cloning (BC), yet its adversarial optimization frequently leads to training instability. A class of non-adversarial Q-based imitation learning (IL) methods, exemplified by IQ-Learn, has emerged to address this instability and is widely believed to outperform BC by leveraging online environment interactions. In this paper, we revisit IQ-Learn and prove that it in fact reduces to BC: it admits an imitation gap lower bound with quadratic dependence on the horizon and therefore remains susceptible to compounding errors. Our theoretical analysis reveals why online interactions fail to help: IQ-Learn uniformly suppresses Q-values for all actions at states not covered by demonstrations, preventing generalization beyond demonstrations. To address this fundamental limitation, we introduce Dual Q-DM, a new Q-based IL method built on Bellman constraints. Crucially, Bellman constraints drive value flow: Q-values propagate from demonstrated to unvisited states through environment dynamics, enabling generalization beyond demonstrations. We prove that Dual Q-DM is equivalent to AIL and can recover expert actions at unvisited states, thereby mitigating compounding errors. To the best of our knowledge, Dual Q-DM is the first non-adversarial IL method that is theoretically guaranteed to eliminate compounding errors. Experimental results further corroborate our theoretical findings.

*Hidden-action principal-agent problems* model scenarios in which a principal induces an agent to take a costly and *unobservable* action through the provision of outcome-dependent payments. These problems find application in a variety of real-world settings, such as crowdsourcing, online labor platforms, and machine learning task delegation. Recently, much of the literature has focused on how to handle the principal’s *uncertainty* about the agent and the surrounding environment, which is often the main challenge in practice. One prominent approach is to adopt an *online learning* framework, where the principal repeatedly interacts with the agent to learn optimal payments from experience. However, existing learning algorithms, while achieving regret that scales sublinearly in the number of interaction rounds $T$, typically suffer from an exponential dependence on the size of the problem instance. In this paper, we show that this problematic exponential growth can be avoided by assuming that the principal has knowledge of a set of possible actions of the agent, while remaining unaware of which actions are actually available---an assumption that is reasonable in many real-world settings.