一种样本复杂度度量及其在学习最优拍卖中的应用
本文通过研究直接基于分布进行收益最大化拍卖的样本复杂度,探讨了数据量在何种程度下可以保证期望收益最大化接近最优,并且构建了一个解释了拍卖、非常接近最优的收益、参与竞标者出价的估值分布之间相互作用的下界。
Feb, 2015
本论文提出了一种新的拍卖模型,通过使用拍卖者在拍卖时获得的某些侧面信息来区分事先相同的竞标人,通过拓展 Dhangwatnotai et al. 和 Cole 和 Roughgarden 的样本复杂度方法来获得了几乎匹配的上限和下限,使用经验风险最小化技术来改进 Cole 和 Roughgarden 的样本复杂度界限。
Nov, 2015
通过两个步骤,我们提出了一个框架来证明从样本中学习最优拍卖问题的多项式样本复杂性界限,该框架捕捉了包括匿名和非匿名项目和捆绑定价在内的所有最突出的简单拍卖类型,并具有低维度的收益函数。
Apr, 2016
本文探讨了多人博弈中学习的样本复杂性问题,并设计算法在样本复杂度多项式级别下,求解多人一般和马尔可夫博弈的粗略关联均衡和关联均衡,同时提出了针对特定条件下的学习算法,显著提高了现有算法的效率和精度。
Oct, 2021
研究大数据情况下的参数平均化方法在经验风险最小化中的应用,探讨了数据分割对估计误差的影响和高维情况下的表现,得出了适用于两种情况的渐进误差估计和精度和存储复杂度之间的权衡关系。
Jul, 2014
我们在具有均匀遍历的马尔可夫决策过程(MDP)中,通过建立一个估计器来实现平均奖励 MDP 的最优策略,其样本复杂度达到文献中的下界,并借鉴了 Jin 和 Sidford(2021)以及 Li 等人(2020)的算法思想。
Oct, 2023
算法和数据相关的广义化界限是解释现代机器学习算法的广义化行为所必需的。在这个背景下,存在包括 (各种形式的) 互信息和基于假设集稳定性的信息论广义化界限。我们提出了一个概念上相关但技术上独特的复杂度度量方法来控制广义化误差,这就是算法和数据相关的假设类的经验 Rademacher 复杂度。通过结合 Rademacher 复杂度的标准特性和这个类的方便结构,我们能够 (i) 获得基于有限分形维度的新界限,这些界限将之前从连续假设类推广到有限假设类,并避免了先前工作中所需的互信息项;(ii) 大大简化了最近一个和维度无关的随机梯度下降的广义化界限的证明;(iii) 我们轻松恢复了 VC 类和压缩方案的结果,类似于基于条件互信息的方法。
Jul, 2023
本文针对 H-smooth 损失函数和具有 Rademacher 复杂度 R_n 的假设类的经验风险最小化,建立了 O(HR_n^2 + R_n sqrt {HL*})的过量风险界,其中 L * 是假设类可实现的最佳风险。针对典型的假设类,其中 R_n = sqrt(R /n),在可分离(L * = 0)情况下,这相当于 O(RH /n)的学习率,更普遍的情况下为 O(RH /n + sqrt {L * RH /n})。我们还针对具有平滑非负目标的在线和随机凸优化提供类似的保证。
Sep, 2010