[论文] On the Learning Curves of Revenue Maximization

## 论文概要 **研究领域**: ML **作者**: Steve Hanneke, Alkis Kalavasis, Shay Moran **发布时间**: 2025-04-30 **arXiv**: [2504.20821](https://arxiv.org/abs/2504.20821) ## 中文摘要 学习曲线是监督学习中的基本原语，描述了算法性能如何随数据量增加而提升，并提供了对其泛化能力的定量度量。形式上，学习曲线绘制了固定底层分布下算法误差随训练样本数量增加而衰减的过程。先前关于收益最大化学习算法的工作，始于Cole和Roughgarden的开创性研究[STOC, 2014]，采用了与PAC学习框架类似的分布无关视角。该方法针对每个样本量下最困难的估值分布序列评估性能，实际上定义了所有可能分布上学习曲线的上包络，从而得到的误差边界无法捕捉学习曲线的形状。在本工作中，我们开创了对收益最大化学习曲线的研究，并在单物品、单买家的基本设置下近乎完整地刻画了其衰减速率。在不对估值分布施加任何限制的情况下，我们证明存在一种贝叶斯一致算法，即其学习曲线对任意估值分布随着样本数n趋于无穷而收敛到零。然而，即使最优收益是有限的，这种收敛也必须是任意慢的。相比之下，如果最优收益由有限价格实现，则最优衰减速率约为1/√n。最后，对于支撑在离散值集合上的分布，我们证明学习曲线几乎指数级快速衰减，这是在PAC框架下无法达到的速率。 ## 原文摘要 Learning curves are a fundamental primitive in supervised learning, describing how an algorithm's performance improves with more data and providing a quantitative measure of its generalization ability. Formally, a learning curve plots the decay of an algorithm's error for a fixed underlying distribution as a function of the number of training samples. Prior work on revenue-maximizing learning algorithms, starting with the seminal work of Cole and Roughgarden [STOC, 2014], adopts a distribution-free perspective, which parallels the PAC learning framework in learning theory. This approach evaluates performance against the hardest possible sequence of valuation distributions, one for each sample size, effectively defining the upper envelope of learning curves over all possible distributions, ... --- *自动采集于 2026-05-01* #论文 #arXiv #ML #小凯