📐 学习理论

🔬 ICLR2026 · 7 篇论文解读

📌 同领域跨会议浏览： 🧪 ICML2026 (17) · 🤖 AAAI2026 (3) · 🧠 NeurIPS2025 (25) · 🧪 ICML2025 (16)

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

提出增量单元枚举算法（ICE），首个具有严格证明的独立算法，可以在 \(O(N^{D+1})\) 时间内精确求解0-1损失线性分类问题的全局最优解，并扩展到多项式超曲面分类。

Deep FlexQP: Accelerated Nonlinear Programming via Deep Unfolding

提出 FlexQP——基于 \(\ell_1\) 弹性松弛的"永远可行"凸二次规划（QP）求解器，结合深度展开（deep unfolding）学习 LSTM 反馈策略加速收敛得到 Deep FlexQP；在 SQP 框架中作为子模块，解非线性轨迹优化比 OSQP 快 4-16 倍，预测安全滤波器的安全违规减少 70%+、任务完成率提升 43%。

Function Spaces Without Kernels: Learning Compact Hilbert Space Representations

证明函数编码器（Function Encoders）通过学习神经网络基函数定义了一个有效的核，建立了神经特征学习与RKHS理论的桥梁，并提出PCA引导的紧凑基选择算法和有限样本泛化界。

Lipschitz Bandits with Stochastic Delayed Feedback

首次系统研究连续臂空间 Lipschitz bandit 在随机延迟反馈下的学习问题，针对有界延迟提出 Delayed Zooming 算法（通过 lazy update 机制保持 \(\Delta(x) \leq 6r_t(x)\) 的子最优 gap 界），针对无界延迟提出 DLPP 分阶段剪枝策略（遗憾与延迟分位数 \(Q(p)\) 挂钩），并建立实例相关下界证明 DLPP 近最优。

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

提出 Random Wavelet Features (RWF)，通过从小波族中随机采样构建可扩展的非平稳核近似，保留随机特征的线性时间复杂度，同时具有正定性、无偏性和一致收敛保证。

The Expressive Limits of Diagonal SSMs for State-Tracking

建立了输入依赖复数对角（DCD）SSM 在群状态追踪任务上的完整表达能力刻画：单层不能追踪任何非阿贝尔群，\(k\) 层能追踪群 \(G\) 当且仅当 \(G\) 存在长度为 \(k\) 的子正规链且因子均为阿贝尔群——精确定义了深度对表达能力的严格提升，同时实验揭示表达能力与可学习性之间的显著 gap。

The Price of Robustness: Stable Classifiers Need Overparameterization

建立了不连续分类器的稳定性-泛化界，证明了分类任务中的"鲁棒性代价定律"：任何参数量 \(p \approx n\) 的插值分类器必然不稳定，实现高稳定性需要 \(p \approx nd\) 量级的过参数化。