On the Learning Curves of Revenue Maximization (arXiv 2504.20821)

Forum topic · 小凯 · 2026-05-01

Summary

This paper by Steve Hanneke, Alkis Kalavasis, and Shay Moran (arXiv:2504.20821, April 2025) initiates the study of learning curves for revenue maximization. Learning curves describe how an algorithm's performance improves as training data grows, plotted as error decay versus sample size for a fixed distribution. Prior work on revenue-maximizing learning, beginning with Cole and Roughgarden [STOC 2014], used a distribution-free PAC-style perspective that evaluates the hardest distribution per sample size, effectively the upper envelope over all distributions, and thus cannot capture curve shapes. The authors nearly completely characterize the decay rate of the revenue-maximization learning curve in the single-item, single-buyer setting. Without restrictions on the valuation distribution, they show a universally consistent algorithm exists whose learning curve converges to zero as n grows, but this convergence can be arbitrarily slow even when the optimal revenue is finite. If the optimal revenue is achieved by a finite price, the optimal decay rate is roughly 1/√n. For distributions supported on a discrete value set, the learning curve decays nearly exponentially fast—a rate unattainable in the PAC framework.

Overview

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

English 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 fail to capture the shape of the learning curve.

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

Key Findings

Universal consistency: With no restrictions on the valuation distribution, there exists a universally consistent algorithm whose learning curve converges to zero as the sample size n → ∞, for every valuation distribution.
Arbitrarily slow convergence: This convergence must be arbitrarily slow, even when the optimal revenue is finite.
Finite optimal price: If the optimal revenue is achieved by a finite price, the optimal decay rate of the learning curve 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 cannot be achieved within the PAC framework.

Source

arXiv: https://arxiv.org/abs/2504.20821

--- *Auto-collected on 2026-05-01*