鲁棒在线凸优化：应对离群点的策略

版权申诉

77 浏览量更新于2024-07-06 收藏 286KB PDF 举报

"这篇论文是关于在线凸优化的鲁棒性研究，特别是在存在离群点(outliers)的情况下。作者包括Tim van Erven、Sarah Sachs、Wouter M. Koolen和Wojciech Kotłowski，来自荷兰阿姆斯特丹大学、荷兰数学与计算机科学研究所(CWI)以及波兰波兹南理工大学。该论文发表于2021年7月6日，归类于计算机科学领域，具体标签可能是机器学习和在线学习。" 在在线凸优化(Online Convex Optimization, OCO)中，通常假设每个数据点都是可靠且有效的输入，但实际情况中可能会存在一些异常值或离群点，这些离群点可能由于各种原因（如噪声、错误、攻击等）导致优化过程受到干扰。论文提出了一个名为“鲁棒后悔”(robust regret)的概念，这是一种新的衡量标准，仅考虑非离群点轮次的后悔值，以评估学习算法在有离群点情况下的性能。当离群点是恶意选择的，即对手可以任意选择哪些数据点作为离群点时，论文展示了通过简单的极端梯度过滤策略，可以在标准后悔界限的基础上增加一个O(k)的额外开销。这里的k表示离群点的数量，这意味着在总的轮次数量中，离群点的数量必须是次线性的，否则无法避免这种开销。这表明了在处理离群点时，算法必须具有一定的鲁棒性。进一步地，论文探讨了在哪些额外假设下，允许的离群点数量可以线性增长。研究发现，通常认为是良性的假设，如独立同分布的数据点，可能不足以应对大量离群点的情况。这提示我们，为了设计能有效处理大量离群点的在线学习算法，可能需要更强的结构假设或者更复杂的策略。这篇论文对在线学习社区提出了新的挑战，尤其是在数据质量不保证时如何设计鲁棒的优化算法。它不仅提供了理论上的分析，还为未来的算法开发和实证研究指明了方向，特别是对于那些可能面临异常值的现实世界应用来说，如在线广告投放、动态定价和推荐系统等。

discussion of possible directions for future work. Some proofs are deferred to the appendix.

2 Setting and Notation

Formally, we consider the following online learning protocol. In each round t = 1, 2, . . . the

learner ﬁrst predicts w

∈ W, where the d o main W is a non-empty, compact and convex subset of

. The adversary t hen reveals a convex loss function f

: W → R, and the learner suffers loss

). We assume throughout that there always exists a gradient or, more generally, a subgradient

:= ∇f

) at the learner’s prediction, which is implied by convexity of f

whenever w

lies

in t he interior of W and also on the boundary if there exists a ﬁnite convex extension o f al l f

to a l arger do main that contains W in its interio r. The performance of the learner with respect

to any ﬁxed parameters u ∈ W is measured by the robust regret R

(u, S) over the rounds S ⊆

[T ] := {1, 2, . . . , T } that are not outli ers, as deﬁned in (1). The deﬁnition of subgradients implies

that f

) − f

(u) ≤ (w

− u)

⊺

, which implies that R

(u, S) is bounded from above by t he

linearized robust regret

(u, S) :=

t∈S

− u)

⊺

We will state our main results for an arbitrary norm k·k on W and measure gradient lengths in

terms of the dual norm kg

∗

= sup

w∈R

:kwk≤1

⊺

. Let D = max

u,w∈W

kw − uk denote the

diameter of the domain. For the analy sis of the robust regret, we need a Lipschitz bo und for the

gradients that are in the set S, which we denote by

G(S) := max

t∈S

∗

3 Robustness to Adversarial Ou tliers

In this section we derive mat ching upper and l ower bounds of the form in (2).

3.1 Upper Bounds

Let ALG be any Lipschitz-adaptive algorithm , which we will use as our base online learning algo-

rithm. Our general approach is to add a ﬁltering meta-algorithm FILTER that examines (the norm

of) incomin g gradients and decides whether to ﬁlt er them or pass them on to ALG for learning. If

S were known in advance, then FILTER could ﬁlter out all outli ers and pass on on ly the rounds

in S, but since S is not known, FILTER needs to learn which rounds to pass on. Although most

online learning algorit hms base their updates only on gradients, we note that we do allow ALG to

use the full loss function f

to update its state when FILTER passes on round t to ALG. When a

round t is ﬁltered, we assume that ALG b ehaves as if that round had not h appened, so w e will have

t+1

= w

. Our FILTER for this section is displayed in Algorithm 1.

Theorem 1. Suppose ALG is an y Lipschitz-adaptive algorithm that guarantees linearized regret

bounded by B

(G) on the rounds that it is passed by FILTER, if the gradients i n those rounds ha ve

剩余22页未读，继续阅读

易小侠

粉丝: 6613
资源: 9万+

鲁棒在线凸优化：应对离群点的策略

使用经典PCA算法验证对离群点的不鲁棒性

基于距离的离群点检测.zip_qundi_剔除 点_剔除离群点_基于距离_基于距离的离群点检测算法

matlab离群点检测

lm和lm_robust

在数据预处理中，如何应用Robust PCA算法来有效识别和剔除数据集中的离群点？

检测并去除离群点的python代码

如何利用Robust PCA来处理含有离群点的数据集，并且相比于传统PCA方法有哪些改进和优势？

python 离群点检测代码实现

如何使用Robust PCA来处理数据中的离群点，并且与传统的PCA方法相比有哪些优势？

最新资源

基于距离的离群点检测.zip_qundi_剔除点_剔除离群点_基于距离_基于距离的离群点检测算法