論文の概要: On the Learning Curves of Revenue Maximization

• arxiv url: http://arxiv.org/abs/2604.26922v1
• Date: Wed, 29 Apr 2026 17:38:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-30 15:59:36.524122
• Title: On the Learning Curves of Revenue Maximization
• Title（参考訳）: 収益最大化学習曲線について
• Authors: Steve Hanneke, Alkis Kalavasis, Shay Moran, Grigoris Velegkas,
• Abstract要約: 学習曲線は、トレーニングサンプル数の関数として、固定された基礎分布に対するアルゴリズムの誤差の減衰をプロットする。 収益を最大化する学習アルゴリズムに関する先行研究は、学習理論におけるPAC学習フレームワークと並行して、分散のない視点を採用する。 ベイズ一貫性アルゴリズムが存在し、任意の評価分布に対して学習曲線が0に収束することを示す。
• 参考スコア（独自算出の注目度）: 62.087200798198786
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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, 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.
• Abstract（参考訳）: 学習曲線は教師付き学習において基本的な原始であり、アルゴリズムのパフォーマンスがより多くのデータでどのように改善され、その一般化能力の定量的な尺度を提供するかを記述する。 形式的には、学習曲線は、トレーニングサンプル数の関数として固定された基礎分布に対するアルゴリズムの誤差の減衰をプロットする。 収益を最大化する学習アルゴリズムの研究は、Cole and Roughgarden(STOC, 2014)の独創的な研究から始まり、分散のない視点を採用し、学習理論におけるPAC学習フレームワークと平行にしている。 提案手法は,各サンプルサイズ毎に最も困難な評価分布列に対する性能評価を行い,学習曲線の最大エンベロープを全ての可能な分布に対して効果的に定義し,学習曲線の形状を捉えない誤差境界を導出する。 本研究では、収益最大化のための学習曲線の研究を開始し、1つのアイテムと1つの購入者の基本的な設定において、その崩壊率をほぼ完全に評価する。 評価分布に制限がない場合、ベイズ整合アルゴリズムが存在することが示され、すなわち、学習曲線は任意の評価分布に対して 0 に収束し、サンプルの数が $n \to \infty$ となる。 しかし、最適収益が有限であっても、この収束は任意に遅くなければならない。 対照的に、最適収益が有限価格で達成された場合、最適崩壊率はおよそ1/\sqrt{n}$である。 最後に、離散的な値集合で支えられた分布に対して、学習曲線はほぼ指数関数的に崩壊し、PACフレームワークでは達成できない速度を示す。

関連論文リスト

• Successive Halving with Learning Curve Prediction via Latent Kronecker Gaussian Processes [7.6801618830697285]
  我々は,Kronecker Gaussian Processs に基づく学習曲線予測による逐次ハルヴィングの導出が限界を克服できるかどうかを考察する。 我々は、この予測アプローチを、現在のパフォーマンス値に基づく標準アプローチと比較する。 実験の結果, 予測手法は競争性能を達成できるが, 標準手法により多くの資源を投入するよりも最適ではないことがわかった。
  論文  参考訳（メタデータ） (2025-08-20T16:10:23Z)
• Faster Diffusion Models via Higher-Order Approximation [28.824924809206255]
  本稿では,d1+2/K varepsilon-1/K $$のスコア関数評価のみを必要とする,原則付き無トレーニングサンプリングアルゴリズムを提案する。 我々の理論はロバストなvis-a-vis不正確なスコア推定であり、スコア推定誤差が増加するにつれて優雅に劣化する。 より広範に、我々は高速サンプリングのための高次手法の有効性を理解するための理論的枠組みを開発した。
  論文  参考訳（メタデータ） (2025-06-30T16:49:03Z)
• Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits [58.63897489864948]
  結果に基づくフィードバックによる強化学習は、根本的な課題に直面します。 適切なアクションにクレジットを割り当てるには? 本稿では,一般関数近似を用いたオンラインRLにおけるこの問題の包括的解析を行う。
  論文  参考訳（メタデータ） (2025-05-26T17:44:08Z)
• Bellman Unbiasedness: Toward Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation [8.378137704007038]
  有限エピソードマルコフ決定過程における一般値関数近似を用いた分布強化学習の後悔の解析を行った。 証明可能なアルゴリズムである$textttSF-LSVI$を提案し、$tildeO(d_E Hfrac32sqrtK)$で、$H$は地平線、$K$はエピソード数、$d_E$は関数クラスの退化次元である。
  論文  参考訳（メタデータ） (2024-07-31T00:43:51Z)
• Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
  細長い分布は、少数の少数派が限られた数のサンプルを含む実世界のデータにしばしば現れる。 近年の研究では、教師付きコントラスト学習がデータ不均衡を緩和する有望な可能性を示していることが明らかになっている。 本稿では,特徴空間の各クラスからのサンプルデータ分布を推定する確率論的コントラスト学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-11T13:44:49Z)
• Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time [45.72323731094864]
  本稿では,2層ReLULUネットワーク間における重み減衰と凸緩和の最適性ギャップについて検討する。 私たちの研究は、なぜローカルメソッドがうまく機能するのかを理解することに新たな光を当てています。
  論文  参考訳（メタデータ） (2024-02-06T01:29:35Z)
• Fine-Grained Distribution-Dependent Learning Curves [27.09513298165498]
  学習曲線はラベル付き入力サンプル数の関数として学習アルゴリズムの予測誤差をプロットする。 本稿では,Bousquet et alの最近の成果を改良し,改良する,粒状PACと呼ばれる新しい次元特性について紹介する。 我々の特徴は、きめ細かい境界を提供することによって学習曲線の構造に新たな光を当てることである。
  論文  参考訳（メタデータ） (2022-08-31T03:29:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。