提出首个多项式时间实现精确对称不变性的核回归算法。
Learning with Exact Invariances in Polynomial Time
- 基于输入空间几何性质，设计可高效计算的不变性学习方法。
- 在保持原核回归泛化误差的前提下，实现精确对称性约束。
- 适合需要严格对称性保证的机器学习任务，如物理规律建模。
我们研究了在核回归中学习精确对称性（或不变性）时的统计-计算权衡。传统方法如数据增强、群平均、规范化的处理方式要么无法提供多项式时间解法，要么不适用于核设置。然而，在获得输入空间几何性质的预言机访问权限下，我们提出了一种多项式时间算法，可学习具有精确不变性的分类器。此外，该方法在过剩总体风险（即泛化误差）方面与原始核回归问题保持一致。据我们所知，这是首个在此背景下实现精确（而非近似）不变性的多项式时间算法。证明过程借助了微分几何、谱理论和优化工具。开发中的一个关键成果是将不变性学习问题重新表述为求解无限多个线性约束凸二次规划的问题，这一形式可能具有独立意义。
原文摘要 · Abstract (English)
We study the statistical-computational trade-offs for learning with exact invariances (or symmetries) using kernel regression. Traditional methods, such as data augmentation, group averaging, canonicalization, and frame-averaging, either fail to provide a polynomial-time solution or are not applicable in the kernel setting. However, with oracle access to the geometric properties of the input space, we propose a polynomial-time algorithm that learns a classifier with \emph{exact} invariances. Moreover, our approach achieves the same excess population risk (or generalization error) as the original kernel regression problem. To the best of our knowledge, this is the first polynomial-time algorithm to achieve exact (not approximate) invariances in this context. Our proof leverages tools from differential geometry, spectral theory, and optimization. A key result in our development is a new reformulation of the problem of learning under invariances as optimizing an infinite number of linearly constrained convex quadratic programs, which may be of independent interest.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。