![](https://csdnimg.cn/release/download_crawler_static/77926859/bg4.jpg)
DYN AMIC REGRET FOR STRONGLY ADAPTIVE METHODS AND OPTIMALITY OF ONLINE KRR
bounded linear predictors and online kernel regression is presented in Section
5. The lower bound
on penalized regret for online clipped KRR and kernel-AWV is explored in Section
6.
2. Related Work
The notion of static regret is very common and there are many well known algorithms for controlling
it. For example, when the decision set has bounded diameter and the functions have bounded gra-
dients in the Euclidean norm, Online Gradient Descent (OGD) with appropriately chosen step size
can yield a static regret of O(
√
T ) and O(log T ) for convex and strongly convex losses respectively.
When the losses are exp-concave, Online Newton Step (ONS) attains regret bounds of O(d log T )
(
Hazan et al., 2007). For controlling static regret in arbitrary norms, one may use Online Mirror
Descent (see for eg. (
Bubeck, 2015)). Parameter free versions of static regret minimizing algo-
rithms have been proposed in the works of
Orabona and P´al (2016); Cutkosky and Orabona (2018).
Ross et al. (2013); Luo et al. (2016) propose algorithms to control the static regret for competing
against bounded linear predictors.
It is well known that to attain sub-linear dynamic regret, one must impose some regularities on
the comparator sequence or the loss function sequence.
Zinkevich (2003) shows that OGD can be
used to attain O(
√
T (1 + V
T
)) dynamic regret. This has been improved by
Zhang et al. (2018a) to
O(
p
T (1 + V
T
)) which is minimax optimal when the loss functions are convex.
When the losses are strongly convex and if we restrict our comparators to be the sequence of
unique minimizers θ
∗
t
= argmin
x∈D
f
t
(x), one may define a path variational V
∗
T
=
P
T
t=2
kθ
∗
t
−
θ
∗
t−1
k.
Mokhtari et al. (2016) show s that OGD enjoys a dynamic regret of O(1 + V
∗
T
). Though this
can be used to upper bound the dynamic regret against any comparators in Eq.(
1), such an upper
bound can be very vacuous.
The variational in Eq.(2) is introduced by Besbes et al. (2015) and they propose a restarted OGD
procedure to yield dynamic regret of O(T
2/3
C
1/3
T
) and O(
√
T C
T
log T ) for convex and strongly
convex losses respectively. However, they require the apriori knowledge of the bound C
T
which
may not be possible to obtain in practice. Jadbabaie et al. (2015) proposes a unifying strategy that
yields dynamic regret bounds that simultaneously depend on V
T
and C
T
when the only condition
on losses is convexity.
There are a number of works related to non-parametric regression and online learning with
RKHS. We only recall here the ones that are perhaps m ost relevant to our paper. The works of
Zhdanov and Kalnishkan (2010); J´ez´equel et al. (2019) propose algorithms for kernel regression
that control certain penalized regret (see Definition
14) when learning with squared error losses . A
sequential bayesian strategy that controls the penalized regret with log losses has been proposed in
Seeger et al. (2008). Zhang et al. (2015) establishes lower bounds on static regret for kernel regres-
sion with squared error losses, however, the optimality of algorithms in
Zhdanov and Kalnishkan
(2010); J´ez´equel et al. (2019) in terms of penalized regret is still unknown. The key difference is
that in the static regret notion of
Zhang et al. (2015), we are competing against a subset of func-
tions with RKHS norms bounded by some known radius while in the notion of penalized regret we
are competing against the entire RKHS (see Section
6 for more details). In this paper, we provide
a positive result that the algorithms in
Zhdanov and Kalnishkan (2010); J´ez´equel et al. (2019) are
indeed nearly minimax optimal in terms of its penalized regret.
4