We study the online variant of GentleAdaboost, where we combine a weak
learner to a strong learner in an online fashion. We provide an approach to
extend the batch approach to an online approach with theoretical justifications
through application of line search. Finally we compare our online boosting
approach with other online approaches across a variety of benchmark datasets.

我们研究了在线版本的 GentleAdaboost，通过在线方式将弱学习器与强学习器相结合。我们提供了一种将批量方法扩展为在线方法的途径，并通过线搜索的应用进行了理论上的证明。最后，我们将我们的在线增强方法与其他在线方法在各种基准数据集上进行了比较。

在线 GentleAdaBoost -- 技术报告

Online GentleAdaBoost -- Technical Report

Submodular function maximization has been studied extensively in recent years
under various constraints and models. The problem plays a major role in various
disciplines. We study a natural online variant of this problem in which
elements arrive one-by-one and the algorithm has to maintain a solution obeying
certain constraints at all times. Upon arrival of an element, the algorithm has
to decide whether to accept the element into its solution and may preempt
previously chosen elements. The goal is to maximize a submodular function over
the set of elements in the solution.
We study two special cases of this general problem and derive upper and lower
bounds on the competitive ratio. Specifically, we design a $1/e$-competitive
algorithm for the unconstrained case in which the algorithm may hold any subset
of the elements, and constant competitive ratio algorithms for the case where
the algorithm may hold at most $k$ elements in its solution.

本文研究基于在线变体的子模函数最大化问题，探讨了两种特殊情况并得出了竞争比的上下界。具体而言，设计了一个 $1/e$ 竞争算法和一个针对最多只包含 k 个元素的解的常数竞争比算法。