提出高效在线逻辑回归算法，计算复杂度降低近百倍。
Efficient Logistic Regression with Mixture of Sigmoids
- 用高斯先验改进指数权重算法，实现近优后悔界。
- 计算复杂度降至 $O(B^3 n^5)$，相比之前 $O(B^{18}n^{37})$ 大幅优化。
- 揭示算法几何本质，适合关注高效在线分类的读者。
本文研究在各向同性高斯先验下，用于在线逻辑回归的指数权重（EW）算法。我们证明，由 Kakade 与 Ng（2005）建立的、针对范数不超过 $B$ 的最优线性预测器的近优最坏情况后悔界 $O(d"log(Bn))$，可被实现于总最坏情况计算复杂度 $O(B^3 n^5)$。该结果显著优于先前达到相同保证的工作（Foster 等，2018）的 $O(B^{18}n^{37})$ 复杂度。除效率外，我们在线性可分情形下分析了大 $B$ 极限：经 $B$ 缩放后，EW 后验收敛至标准高斯在版本锥内的截断分布。相应预测器收敛为分离方向的球面投票，在每个固定边距切片上，截断高斯的众数与硬边际 SVM 方向对齐。基于此几何结构，我们推导出非渐近后悔界，表明一旦 $B$ 超过依赖边距的阈值，后悔界不再依赖 $B$，仅随逆边距对数增长。总体而言，结果表明 EW 在在线分类中兼具计算可行性与几何自适应性。
原文摘要 · Abstract (English)
This paper studies the Exponential Weights (EW) algorithm with an isotropic Gaussian prior for online logistic regression. We show that the near-optimal worst-case regret bound $O(d\log(Bn))$ for EW, established by Kakade and Ng (2005) against the best linear predictor of norm at most $B$, can be achieved with total worst-case computational complexity $O(B^3 n^5)$. This substantially improves on the $O(B^{18}n^{37})$ complexity of prior work achieving the same guarantee (Foster et al., 2018). Beyond efficiency, we analyze the large-$B$ regime under linear separability: after rescaling by $B$, the EW posterior converges as $B\to\infty$ to a standard Gaussian truncated to the version cone. Accordingly, the predictor converges to a solid-angle vote over separating directions and, on every fixed-margin slice of this cone, the mode of the corresponding truncated Gaussian is aligned with the hard-margin SVM direction. Using this geometry, we derive non-asymptotic regret bounds showing that once $B$ exceeds a margin-dependent threshold, the regret becomes independent of $B$ and grows only logarithmically with the inverse margin. Overall, our results show that EW can be both computationally tractable and geometrically adaptive in online classification.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。