In boosting, we aim to leverage multiple weak learners to produce a strong
learner. At the center of this paradigm lies the concept of building the strong
learner as a voting classifier, which outputs a weighted majority vote of the
weak learners. While many successful boosting algorithms, such as the iconic
AdaBoost, produce voting classifiers, their theoretical performance has long
remained sub-optimal: the best known bounds on the number of training examples
necessary for a voting classifier to obtain a given accuracy has so far always
contained at least two logarithmic factors above what is known to be achievable
by general weak-to-strong learners. In this work, we break this barrier by
proposing a randomized boosting algorithm that outputs voting classifiers whose
generalization error contains a single logarithmic dependency on the sample
size. We obtain this result by building a general framework that extends sample
compression methods to support randomized learning algorithms based on
sub-sampling.

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

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

Boosting, Voting Classifiers and Randomized Sample Compression Schemes

This paper presents an efficient algorithm to solve the sleeping bandit with
multiple plays problem in the context of an online recommendation system. The
problem involves bounded, adversarial loss and unknown i.i.d. distributions for
arm availability. The proposed algorithm extends the sleeping bandit algorithm
for single arm selection and is guaranteed to achieve theoretical performance
with regret upper bounded by $\bigO(kN^2\sqrt{T\log T})$, where $k$ is the
number of arms selected per time step, $N$ is the total number of arms, and $T$
is the time horizon.

该论文提出了一种在在线推荐系统中解决多次玩睡眠盗贼问题的高效算法，该问题涉及有界的对抗性损失和未知的 i.i.d. 分布，所提出的算法扩展了单次选择臂的睡眠盗贼算法，能够保证理论性能，后悔上限为 O (kN^2√(TlogT))，其中 k 是每个时间步中选择的臂数，N 是总臂数，T 是时间界限。

具有多次游玩的对抗性睡眠强盗问题：算法与排名应用

Adversarial Sleeping Bandit Problems with Multiple Plays: Algorithm and  Ranking Application

In this paper, we propose a nested matrix-tensor model which extends the
spiked rank-one tensor model of order three. This model is particularly
motivated by a multi-view clustering problem in which multiple noisy
observations of each data point are acquired, with potentially non-uniform
variances along the views. In this case, data can be naturally represented by
an order-three tensor where the views are stacked. Given such a tensor, we
consider the estimation of the hidden clusters via performing a best rank-one
tensor approximation. In order to study the theoretical performance of this
approach, we characterize the behavior of this best rank-one approximation in
terms of the alignments of the obtained component vectors with the hidden model
parameter vectors, in the large-dimensional regime. In particular, we show that
our theoretical results allow us to anticipate the exact accuracy of the
proposed clustering approach. Furthermore, numerical experiments indicate that
leveraging our tensor-based approach yields better accuracy compared to a naive
unfolding-based algorithm which ignores the underlying low-rank tensor
structure. Our analysis unveils unexpected and non-trivial phase transition
phenomena depending on the model parameters, ``interpolating'' between the
typical behavior observed for the spiked matrix and tensor models.

本文提出了一种嵌套的矩阵张量模型，用于解决具有多视角的聚类问题，并在理论上证明该模型的最佳秩一张量逼近方法具有更好的精度。