NIPSJan, 2011

Boosting 的原始 - 对偶收敛分析

PDF
TL;DR本文探讨了 Boosting 算法在包括 AdaBoost 和 logistic loss 的一系列算法下，通过将弱分类器组合成低风险预测器，构建高熵分布以使得弱分类器和训练标签互不相关，证明了弱可学习性有助于整个算法族，所有 epsilon>0 情况下，只需 O (ln (1/epsilon)) 次迭代即可生成预测器，使得其经验风险与最小值之间的误差为 epsilon，同时证明了将任意实例分解为两个步骤，从而为逻辑回归损失提供匹配的下限。
发现论文，激发创造
  • 提升算法的双重表述

    研究使用新视角的提升算法，证明 AdaBoost、LogitBoost 和软边界 LPBoost 的拉格朗日对偶问题都是熵最大化问题，并通过研究这些算法的对偶问题，表明了提升算法的成功可以从最大化边缘并同时控制边缘方差的角度来理解。通过列生成优化算法，实现了更快的收敛率，并使得使用提议的优化技术建立集成所需的弱分类器更少。

    Jan, 2009

  • AdaBoost 算法的收敛速度

    本文研究了 AdaBoost 算法的收敛速度，证明了其迭代收敛速度具有多项式上界，同时提供了针对多项式依赖的下界，在不需要弱学习假设和指数损失最小值有限等限制的情况下实现了优化的结果。

    Jun, 2011

  • 利用原始对偶一阶算法从数据中挖掘强凸性

    本文提出了批处理和随机的原始 - 对偶算法，可以自适应地利用数据的强凸性，即使在没有正则化的情况下也能实现线性收敛，并介绍了适用于逻辑回归的免双重正演算法。

    Mar, 2017

  • 提升、投票分类器与随机样本压缩方案

    通过提出一种随机增强算法，我们构建了一个通用框架，将样本压缩方法扩展到支持基于子采样的随机学习算法，并输出具有单对数依赖性的投票分类器的泛化误差，相比于已知可实现的一般的弱到强学习器，我们的算法在训练样本数量方面具有更好的表现。

    Feb, 2024

  • 通过原始 - 对偶分析表征隐式偏差

    本文证明了对于线性可分数据，梯度下降的隐式偏差可以通过最优解的双重优化问题完全描述，从而实现了对一般损失的训练。此外，使用 L2 最大间隔方向的恒定步长可以获得 O (ln (n)/ln (t)) 的收敛速率，而使用适当选择的主动步长时间表，则可以获得对于 L2 间隔和隐式偏差的 O (1/t) 收敛速率。

    Jun, 2019

  • 并行提升的成本

    在这篇论文中，我们研究了用于学习的弱到强增强算法的并行成本，结果表明即使是对增强的轻微并行化也需要训练复杂度指数级增长，我们证明了这个上限并且给出了一些补充的结果和权衡，首次提供了并行性和增强所需总工作之间的权衡。

    Feb, 2024

  • 弱监督分类的下界适当损失

    本文讨论了弱监督分类的问题，介绍了一种名为广义逻辑挤压的正则化方案，该方案能使任何合适的弱标签损失函数在下界处有界，而不丢失合理性，并实验验证了该方法的有效性，结果突出了合理性和保下界的重要性。

    Mar, 2021

  • 多类别 Boosting 理论

    本文提出了一种广泛且通用的框架，通过精确分析和确定弱分类器的最优需求，以及设计最有效的某种算法来应对多类别分类中存在的问题。

    Aug, 2011

  • 大规模多类别分类的高效原始 - 对偶算法

    本文介绍了如何使用随机镜像下降法和非均匀采样方案，来快速训练高维度特征空间、多分类通用的线性分类器，特别是在多类 Hinge 损失下，本文提出了一个迭代次数为 $O (d+n+k)$ 的子线性算法。

    Feb, 2019

  • 凸优化的广义 Boosting 算法

    该研究分析了梯度下降算法，引入了新的弱学习器性能度量，并扩展了 Boosting 方法，以支持任意凸损失函数，并给出了相应的弱到强的收敛结果。

    May, 2011