高效的混合性: 快速的在线多类别逻辑回归
本研究探讨了一类广泛问题的在线可学性,并将其扩展到远超过外部遗憾的性能评估简单规范。我们的框架同时捕捉了其他著名规范,例如内部和一般Phi规范、学习使用非加性全局成本函数、Blackwell的可挑战性、预测者的校准、自适应遗憾等。我们展示了在所有这些情况下的可学习性归因于控制相同的三个量:马田哥小定理收敛项、如果已知未来则能够表现良好的能力描述项、以及顺序Rademacher复杂性的概括,该复杂性在(Rakhlin, Sridharan, Tewari, 2010)中得到研究。由于我们直接研究问题的复杂性,而不是专注于高效算法的开发,因此我们能够改进和扩展许多已知结果,这些结果之前是通过算法构造推导出来的。
Nov, 2010
研究多类预测中的样本复杂度,并提出了设计ERM学习器的原则以及使用这些原则来证明对称的多类假说类的样本复杂度的紧束缚定理。此外,通过对Littlestone维度的新概括,提供了在线背景和强盗问题中多类学习的错误和遗憾界限的描述。
Aug, 2013
基于顺序熵,确立了在线回归的最佳速率,发现最佳速率具有类似于独立同分布/统计学习情况的相变。此外,展示了一种享有建立的最佳速率的通用预测器和一种设计在线回归算法且计算高效的方法。
Feb, 2014
本文介绍了一种用于在线稀疏线性回归问题的算法,并在每次迭代时使用多项式时间限制来使遗憾较小。结果证明对于任何常数δ> 0,没有算法可以使遗憾在O(T ^(1-δ))以内,即使允许算法访问比最佳稀疏线性回归器更多的特征。
Mar, 2016
我们提出了一种高效的二阶算法,用于处理带依赖的多分类问题,同时考虑了由ETA参数化的一系列损失函数与竞争者的范式限制。算法能够同时处理从铰链损失(ETA=0)到平方铰链损失(ETA=1)的这一系列损失函数,这解决了Abernethy和Rakhlin在COLT 2009中的一个开放性问题,并通过实验与早期算法得到了良好的效果。
Feb, 2017
通过发现logistic loss是1-mixable,我们设计了一个新的高效的improper learning algorithm,解决了COLT 2012 open problem variant中的问题,并在预测器范数上具有双重指数提高的遗憾限制,这提供了一种解决在线学习领域中的问题的方法,我们还展示了这种改进对多类学习和在线提升等应用的影响。
Mar, 2018
本文研究在线逻辑回归的问题,提出了一种高效的不合适算法,它避免了指数倍的常数,并保持了对数回归。通过采用经验风险最小化的正则化和替代损失,我们的新算法仅需O(B log(Bn))的损失缩放,每轮的时间复杂度为O(d ^ 2)。
Mar, 2020
研究在线情况下的不确定性量化问题,提出新的自适应后悔最小化算法用于在线共形预测,证明了该方法实现了近似最优的自适应后悔和适当的预测覆盖,同时在时间序列预测和图像分类等实际任务上对现有方法具有明显的优势。
Feb, 2023
该研究在在线结构预测中应用了Fenchel-Young loss以及随机解码方法,并通过引入利用替代差距框架获得了有限的代价后悔界限,对多类别分类问题中的在线多类别分类进行了改进,得到了精确度以域直径的对数因子优化的有限代价后悔界限。
Feb, 2024