On the Learning Curves of Revenue Maximization: Near-Complete Characterization for Single-Item Auctions

Forum topic · 小凯 · 2026-05-01

Summary

This arXiv paper (2504.20821) by Steve Hanneke, Alkis Kalavasis, and Shay Moran, posted April 30, 2025, initiates the study of learning curves in revenue maximization, characterizing how error in learning optimal auction revenue decays with sample size. Prior work since Cole and Roughgarden (STOC 2014) used a distribution-free PAC-style perspective, evaluating against the hardest sequence of valuation distributions per sample size—effectively the upper envelope of learning curves, which fails to capture the curve's shape. The authors study the single-item, single-buyer setting. With no restrictions on the valuation distribution, they prove a universally consistent algorithm exists whose learning curve converges to zero as samples grow, yet convergence can be arbitrarily slow even when optimal revenue is finite. If the optimal revenue is achieved at a finite price, the optimal decay rate is on the order of 1/√n. For distributions supported on a discrete set of values, the learning curve decays nearly exponentially—a rate unattainable under the PAC framework.

Paper Overview

Field: Machine Learning
Authors: Steve Hanneke, Alkis Kalavasis, Shay Moran
Posted: 2025-04-30
arXiv: 2504.20821

Abstract

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—and the resulting error bounds cannot capture the shape of the learning curve.

In this work, the authors pioneer the study of learning curves for revenue maximization and give a near-complete characterization of their decay rates in the basic single-item, single-buyer setting:

No distributional restrictions: there exists a universally consistent algorithm—its learning curve converges to zero as the sample size n → ∞ for every valuation distribution. However, this convergence must be arbitrarily slow, even when the optimal revenue is finite.
Finite optimal price: if the optimal revenue is achieved at a finite price, the optimal decay rate is approximately 1/√n.
Discrete support: for distributions supported on a discrete set of values, the learning curve decays nearly exponentially fast—a rate that is unattainable within the PAC framework.

Discussion

This shifts the analysis of revenue learning from worst-case, distribution-free guarantees to per-distribution learning curves, revealing a much richer decay landscape. The near-exponential rate for discrete distributions is particularly notable, as it demonstrates the expressive gap between the learning-curve framework and classical PAC-style bounds.

---

*Auto-collected on 2026-05-01*