Logistic Regression: The Importance of Being Improper
Logistic Regression: The Importance of Being Improper
复制标题
逻辑回归：不当的重要性
DOI：
10.1109/tit.2012.2195769
复制
发表时间：
2018
影响因子：
2.5
通讯作者：
Karthik Sridharan
中科院分区：
文献类型：
--
作者：
Dylan J. Foster;Satyen Kale;Haipeng Luo;M. Mohri;Karthik Sridharan
在随机设置和在线设置中学习线性预测指标，都是机器学习和统计数据的基本任务，与分类和增强的直接连接是一项基本任务。此设置的现有“快速率”表现出对预测指标规范的指数依赖性，Hazan等人。 （2014年）表明，不幸的是，这是不足的。从一个简单的观察开始，即逻辑损失为$ 1 $可混合，我们为在线逻辑回归设计了一种新的有效学习算法，以绕过上述下部的下限，并遗憾的是表现出对预测指标的依赖性的双重指数改进。当允许学习不当时，这为麦克马汉和Streeter（2012）的Colt 2012开放问题的变体提供了积极的分辨率。在在线环境中以及在批处理统计环境中具有很高可能性的批处理设置，都可以获得这种改进。我们还表明，对预测指标规范的依赖性的改善是几乎最佳的。
利用这种改进的对预测指标规范的依赖性得出以下应用程序：（a）我们为在线强盗多类学习提供算法，并使用$ \ tilde {o}（\ sqrt {n}）$相对错误跨越本质上的所有限制参数范围，因此为Colt 2009 Abernethy和Rakhlin（2009）的开放问题提供了解决方案，并且（b）我们给出了一种自适应算法，用于在线多类促进，并以最佳的样本复杂性，部分解决了Beygelzimer等人的开放问题。 （2015）和Jung等。 （2017）。最后，我们提供有关通用功能类别不当逻辑回归的最佳速率的信息理论界限，从而表征了我们的线性类别的改进范围在多大程度上扩展到其他参数甚至非参数设置。
Learning linear predictors with the logistic loss---both in stochastic and online settings---is a fundamental task in machine learning and statistics, with direct connections to classification and boosting. Existing "fast rates" for this setting exhibit exponential dependence on the predictor norm, and Hazan et al. (2014) showed that this is unfortunately unimprovable. Starting with the simple observation that the logistic loss is $1$-mixable, we design a new efficient improper learning algorithm for online logistic regression that circumvents the aforementioned lower bound with a regret bound exhibiting a doubly-exponential improvement in dependence on the predictor norm. This provides a positive resolution to a variant of the COLT 2012 open problem of McMahan and Streeter (2012) when improper learning is allowed. This improvement is obtained both in the online setting and, with some extra work, in the batch statistical setting with high probability. We also show that the improved dependence on predictor norm is near-optimal.
Leveraging this improved dependency on the predictor norm yields the following applications: (a) we give algorithms for online bandit multiclass learning with the logistic loss with an $\tilde{O}(\sqrt{n})$ relative mistake bound across essentially all parameter ranges, thus providing a solution to the COLT 2009 open problem of Abernethy and Rakhlin (2009), and (b) we give an adaptive algorithm for online multiclass boosting with optimal sample complexity, thus partially resolving an open problem of Beygelzimer et al. (2015) and Jung et al. (2017). Finally, we give information-theoretic bounds on the optimal rates for improper logistic regression with general function classes, thereby characterizing the extent to which our improvement for linear classes extends to other parametric and even nonparametric settings.