수익 극대화 학습 알고리즘의 학습 곡선 연구

학습 곡선은 지도 학습에서 기본적인 기본 구성 요소로, 알고리즘의 성능이 더 많은 데이터를 통해 어떻게 개선되는지를 설명하며 일반화 능력을 정량적으로 측정하는 지표입니다. 공식적으로, 학습 곡선은 고정된 근본 분포에 대해 알고리즘의 오차가 훈련 샘플 수의 함수로서 어떻게 감소하는지를 나타냅니다. Cole 과 Roughgarden [STOC, 2014] 의 선구적인 연구로 시작되는 수익 극대화 학습 알고리즘에 대한 기존 작업은 분포 자유 (distribution-free) 관점을 채택하여 학습 이론에서의 PAC 학습 프레임워크와 평행합니다. 이 접근법은 각 샘플 크기에 대해 가장 어려운 가능한 평가 분포 시퀀스에 대해 성능을 평가함으로써, 모든 가능한 분포에 걸친 학습 곡선의 상단 외피를 효과적으로 정의하고, 학습 곡선의 모양을 포착하지 않는 오차 경계로 이어집니다. 본 연구에서는 수익 극대화를 위한 학습 곡선에 대한 연구를 개시하며, 단일 항목과 단일 구매자의 기본 설정에서 그 감소율에 대해 거의 완전한 특징화를 제공합니다. 평가 분포에 대한 어떤 제한도 없는 경우, 임의의 평가 분포에 대해 샘플 수 $n \to \infty$ 일 때 학습 곡선이 0 으로 수렴하는 베이지안 일관성 (Bayes-consistent) 알고리즘이 존재함을 보여줍니다. 그러나 최적 수익이 유한하더라도 이 수렴은 임의로 느릴 수 있습니다. 반면, 최적 수익이 유한한 가격으로 달성되는 경우, 최적 감소율은 대략 $1/\sqrt{n}$ 입니다. 마지막으로, 이산 값 집합을 지지하는 분포에 대해서는 학습 곡선이 거의 지수적으로 빠르게 감소함을 보여주며, 이는 PAC 프레임워크 하에서 도달할 수 없는 속도입니다.