arXiv:2604.26922cs.LGcs.DS2026-04被引 1

研究拍卖中收益最大化的学习曲线,揭示数据量与收益提升的关系。

On the Learning Curves of Revenue Maximization

论文配图:On the Learning Curves of Revenue Maximization
图 1 · 摘自论文原文
  • 从收益角度分析学习曲线,区分不同估值分布下的收敛速度。
  • 无限制时收敛可任意慢,有限最优价格下速率达1/√n,离散分布下近乎指数快。
  • 适用于机制设计、拍卖理论和强化学习中的收益优化研究者。

学习曲线是监督学习中的基础概念,描述算法性能随训练样本数量增加而提升的过程,量化其泛化能力。传统收益最大化学习算法采用无分布假设视角,类似PAC学习框架,评估最坏情况下的表现,导致误差界无法反映学习曲线的实际形态。本文首次系统研究收益最大化场景下的学习曲线,在单物品单买家的基本设定下,给出近乎完整的衰减速率刻画:在无任何估值分布限制时,存在贝叶斯一致算法,对任意分布均有当n→∞时误差趋于零;但收敛速度可任意缓慢,即使最优收益有限。若最优收益由有限价格实现,则最优衰减速率约为1/√n。对于支持在离散值集上的分布,学习曲线几乎以指数速度衰减,这一速率在PAC框架下不可达。

原文摘要 · Abstract (English)

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, thus leading to error bounds that do not capture the shape of the learning curves. In this work we initiate the study of learning curves for revenue maximization and provide a near-complete characterization of their rate of decay in the basic setting of a single item and a single buyer. In the absence of any restriction on the valuation distribution, we show that there exists a Bayes-consistent algorithm, meaning that its learning curve converges to zero for any arbitrary valuation distribution as the number of samples $n \to \infty$. However, this convergence must be arbitrarily slow, even if the optimal revenue is finite. In contrast, if the optimal revenue is achieved by a finite price, then the optimal rate of decay is roughly $1/\sqrt{n}$. Finally, for distributions supported on discrete sets of values, we show that learning curves decay almost exponentially fast, a rate unattainable under the PAC framework.

机制设计学习曲线收益最大化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。