📐 Learning Theory

🔬 ICLR2026 · 4 paper notes

📌 Same area in other venues: 🧪 ICML2026 (17) · 🤖 AAAI2026 (1) · 🧠 NeurIPS2025 (20)

An Efficient, Provably Optimal Algorithm for the 0-1 Loss Linear Classification Problem

This paper proposes the Incremental Cell Enumeration (ICE) algorithm — the first standalone algorithm with rigorous correctness proofs — capable of exactly solving the global optimum of the 0-1 loss linear classification problem in \(O(N^{D+1})\) time, with extensions to polynomial hypersurface classification.

Lipschitz Bandits with Stochastic Delayed Feedback

This paper provides the first systematic study of Lipschitz bandits over continuous arm spaces under stochastic delayed feedback. For bounded delays, it proposes the Delayed Zooming algorithm, which employs a lazy update mechanism to maintain the suboptimality gap bound \(\Delta(x) \leq 6r_t(x)\). For unbounded delays, it proposes DLPP, a phased pruning strategy whose regret is tied to the delay quantile \(Q(p)\). Instance-dependent lower bounds are established to prove that DLPP is nearly optimal.

Scalable Random Wavelet Features: Efficient Non-Stationary Kernel Approximation with Convergence Guarantees

This paper proposes Random Wavelet Features (RWF), a scalable non-stationary kernel approximation framework constructed by randomly sampling from a family of wavelets. RWF preserves the linear-time complexity of random feature methods while offering guarantees of positive definiteness, unbiasedness, and uniform convergence.

The Price of Robustness: Stable Classifiers Need Overparameterization

This paper establishes stability-generalization bounds for discontinuous classifiers and proves a "law of robustness" for classification: any interpolating classifier with \(p \approx n\) parameters is necessarily unstable, and achieving high stability requires overparameterization on the order of \(p \approx nd\).