论文标题
Logistic回归遗憾：有什么收获？
Logistic Regression Regret: What's the Catch?
论文作者
论文摘要
我们通过在线逻辑回归解决了可实现的后悔率的问题。我们在$ l_1 $，$ l_2 $和$ l_ \ infty $约束下以对数后悔的范围得出下限。边界以$ d/2 \ log t $为主，其中$ t $是地平线，$ d $是参数空间的维度。在所有这些情况下，我们都以$ d = o（t^{1/3}）$显示了它们的可实现性，这些情况使用贝叶斯方法，可以将它们实现至$ d/2 \ log d $ term。为了更大的维度显示有趣的不同行为。具体而言，在负面的一面，如果$ d =ω（\ sqrt {t}）$，则保证任何算法的$ω（d \ log t）$（大于$ω（\ sqrt {t}）$的$ω（大于$ l_ \ l_ \ l_ \ f iffty $ consion commoters commoters commoters（和示例功能）。从积极的一面来看，在$ L_1 $的限制下，存在算法，可以实现遗憾的，对于$ d $的$ d $中的亚线性，对于$ d $ $ d $。对于$ l_2 $的约束，表明对于足够大的$ d $，遗憾仍然是$ d $中的线性，但不再以$ t $进行对数。通过信息理论调整冗余容量定理，我们演示了一种基于参数网格以得出下限的原则方法。网格也用于得出一些上限。我们的结果加强了Kakade和Ng（2005）和Foster等人的结果。 （2018）对于此问题的上限，请引入新颖的下限，并适应一种可用于为其他相关问题获得此类界限的方法。当允许参数空间的尺寸以$ t $增长时，它们还对渐近行为进行了新颖的表征。他们还建立了与信息理论文献的联系，表明逻辑回归的实际遗憾取决于参数类的丰富性，即使在这个问题中，更丰富的类别也会带来更大的遗憾。
We address the problem of the achievable regret rates with online logistic regression. We derive lower bounds with logarithmic regret under $L_1$, $L_2$, and $L_\infty$ constraints on the parameter values. The bounds are dominated by $d/2 \log T$, where $T$ is the horizon and $d$ is the dimensionality of the parameter space. We show their achievability for $d=o(T^{1/3})$ in all these cases with Bayesian methods, that achieve them up to a $d/2 \log d$ term. Interesting different behaviors are shown for larger dimensionality. Specifically, on the negative side, if $d = Ω(\sqrt{T})$, any algorithm is guaranteed regret of $Ω(d \log T)$ (greater than $Ω(\sqrt{T})$) under $L_\infty$ constraints on the parameters (and the example features). On the positive side, under $L_1$ constraints on the parameters, there exist algorithms that can achieve regret that is sub-linear in $d$ for the asymptotically larger values of $d$. For $L_2$ constraints, it is shown that for large enough $d$, the regret remains linear in $d$ but no longer logarithmic in $T$. Adapting the redundancy-capacity theorem from information theory, we demonstrate a principled methodology based on grids of parameters to derive lower bounds. Grids are also utilized to derive some upper bounds. Our results strengthen results by Kakade and Ng (2005) and Foster et al. (2018) for upper bounds for this problem, introduce novel lower bounds, and adapt a methodology that can be used to obtain such bounds for other related problems. They also give a novel characterization of the asymptotic behavior when the dimension of the parameter space is allowed to grow with $T$. They additionally establish connections to the information theory literature, demonstrating that the actual regret for logistic regression depends on the richness of the parameter class, where even within this problem, richer classes lead to greater regret.
