12
Smoothed Online Optimization with Unreliable Predictions
DAAN RUTTEN,
Georgia Institute of Technology, United States
NICOLAS CHRISTIANSON,
California Institute of Technology, United States
DEBANKUR MUKHERJEE,
Georgia Institute of Technology, United States
ADAM WIERMAN,
California Institute of Technology, United States
We examine the problem of smoothed online optimization, where a decision maker must sequentially choose
points in a normed vector space to minimize the sum of per-round, non-convex hitting costs and the costs of
switching decisions between rounds. The decision maker has access to a black-box oracle, such as a machine
learning model, that provides untrusted and potentially inaccurate predictions of the optimal decision in each
round. The goal of the decision maker is to exploit the predictions if they are accurate, while guaranteeing
performance that is not much worse than the hindsight optimal sequence of decisions, even when predictions
are inaccurate. We impose the standard assumption that hitting costs are globally
훼
-polyhedral. We propose
a novel algorithm, Adaptive Online Switching (AOS), and prove that, for a large set of feasible
훿
>
0
, it
is
(
1
+
훿
)
-competitive if predictions are perfect, while also maintaining a uniformly bounded competitive
ratio of
2
̃
O(
1
/(
훼훿
))
even when predictions are adversarial. Further, we prove that this trade-off is necessary
and nearly optimal in the sense that
any
deterministic algorithm which is
(
1
+
훿
)
-competitive if predictions
are perfect must be at least
2
̃
Ω
(
1
/(
훼훿
))
-competitive when predictions are inaccurate. In fact, we observe a
unique threshold-type behavior in this trade-off: if
훿
is not in the set of feasible options, then
no
algorithm is
simultaneously
(
1
+
훿
)
-competitive if predictions are perfect and
휁
-competitive when predictions are inaccurate
for any
휁
<
∞
. Furthermore, we discuss that memory is crucial in AOS by proving that any algorithm that
does not use memory cannot benefit from predictions. We complement our theoretical results by a numerical
study on a microgrid application.
CCS Concepts:
•
Theory of computation
→
Online algorithms
;
•
Computing methodologies
→
Ma-
chine learning approaches
;
•
Computer systems organization
→
Dependable and fault-tolerant systems
and networks
.
Additional Key Words and Phrases: online algorithms, non-convex optimization, competitive analysis
ACM Reference Format:
Daan Rutten, Nicolas Christianson, Debankur Mukherjee, and Adam Wierman. 2023. Smoothed Online
Optimization with Unreliable Predictions.
Proc. ACM Meas. Anal. Comput. Syst.
7, 1, Article 12 (March 2023),
36 pages. https://doi.org/10.1145/3579442
1 INTRODUCTION
We consider online (non-convex) optimization with switching costs in a normed vector space
(
푋,
∥·∥)
wherein, at each time
푡
, a decision-maker observes a non-convex
hitting cost
function
푓
푡
:
푋
→ [
0
,
∞]
and must decide upon some
푥
푡
∈
푋
, paying
푓
푡
(
푥
푡
) + ∥
푥
푡
−
푥
푡
−
1
∥
, where
∥·∥
characterizes the
switching cost
. Throughout, we assume that
푓
푡
is globally
훼
-polyhedral (see
Authors’ addresses: Daan Rutten, Georgia Institute of Technology, Atlanta, United States; Nicolas Christianson, California
Institute of Technology, Pasadena, United States; Debankur Mukherjee, Georgia Institute of Technology, Atlanta, United
States; Adam Wierman, California Institute of Technology, Pasadena, United States.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee
provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the
full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored.
Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires
prior specific permission and/or a fee. Request permissions from permissions@acm.org.
©
2023 Copyright held by the owner/author(s). Publication rights licensed to ACM.
2476-1249/2023/3-ART12
https://doi.org/10.1145/3579442
Proc. ACM Meas. Anal. Comput. Syst., Vol. 7, No. 1, Article 12. Publication date: March 2023.
12:2
Daan Rutten, Nicolas Christianson, Debankur Mukherjee, and Adam Wierman
Definition 1). Moreover, we assume that the decision maker has access to an
untrusted prediction
̃
푥
푡
of the optimal decision during each round, such as the decision suggested by a black-box AI tool
for that round.
Online optimization is a problem with applications to many real-world problems [
15
,
24
,
34
,
35
,
47
,
50
,
63
,
66
,
67
]. Usually there is a penalty for switching decisions too often: the goal of a decision
maker is not just to minimize the hitting cost functions, but to also minimize the switching cost
between rounds. Online optimization with switching costs has received considerable attention in
the learning, networking, and control communities in recent years [
4
,
28
,
30
,
45
,
46
,
60
]. Moreover,
the crux of many fundamental problems in online algorithms, such as the
푘
-server problem [
37
],
metrical task systems [
17
,
18
], and online convex body chasing [
11
,
59
] is to handle switching costs.
The bulk of the literature on online optimization with switching costs has sought to design
competitive
algorithms for the task, i.e., algorithms with finite competitive ratios. At this point,
competitive algorithms for scenarios with both convex and non-convex hitting costs have been
developed [
21
,
49
,
68
]. However, while competitive analysis yields strong performance guarantees,
it has often been criticized as being unduly pessimistic, since algorithms are characterized by their
worst-case
performance, while worst-case conditions may never occur in practice. As a result, an
algorithm with an improved competitive ratio may not actually lead to better performance in
realistic scenarios.
On the other hand, many real-world applications have access to vast amounts of historical data
which could be leveraged by modern black-box AI tools in order to achieve significantly improved
performance in the typical case. For example, in the context of capacity scaling for data centers,
the historical data reveals reoccurring patterns in the weekly load of a data center. AI models that
are trained on these historical patterns can potentially outperform competitive algorithms in the
typical case. This approach has been successfully used by Google in data center cooling [26].
Making use of modern black-box AI tools is potentially transformational for online optimization;
however, such machine-learned algorithms fail to provide any uncertainty quantification and thus
do not have formal guarantees on their worst-case performance. As such, while their performance
may improve upon competitive algorithms in typical cases, they may perform arbitrarily worse in
scenarios where the training examples are not representative of the real world workloads due to,
e.g., distribution shift. This represents a significant drawback when considering the use of AI tools
for safety-critical applications.
A challenging open question is whether it is possible to provide guarantees that allow black-box
AI tools to be used in safety-critical applications. This paper aims to provide an algorithm that can
achieve the best of both worlds – making use of black-box AI tools to provide good performance in
the typical case while integrating competitive algorithms to ensure formal worst-case guarantees.
We formalize this goal using the notions of
consistency
and
robustness
introduced by [
51
] and used
in the emerging literature on untrusted advice in online algorithms [
32
,
39
,
43
,
51
,
52
,
54
,
58
,
62
].
We consider that the online algorithm is given untrusted advice/predictions, e.g., the output of a
black-box AI tool. The predictions are fully arbitrary, i.e., we impose no statistical assumptions on
the predictions, and the decision maker has no
a priori
knowledge of the predictions’ accuracy. The
goal of the decision maker is to be both
consistent
– that is, to achieve performance comparable to
that of the predictions if they are accurate, while remaining
robust
, i.e., having cost that is never
much worse than the hindsight optimal, even if predictions are completely inaccurate. Thus, an
algorithm that is consistent and robust is able to match the performance of the black-box AI tool
when the predictions are accurate while also ensuring a worst-case performance bound (something
black-box AI tools cannot provide).
Proc. ACM Meas. Anal. Comput. Syst., Vol. 7, No. 1, Article 12. Publication date: March 2023.
Smoothed Online Optimization with Unreliable Predictions
12:3
Main contributions.
We make five main contributions in this paper.
First
, we identify a fun-
damental trade-off between consistency and robustness for any deterministic algorithm. If an
algorithm is
(
1
+
훿
)
-consistent, then this implies a lower bound on its robustness guarantee. In
fact, we identify a region of
(
훼,훿
)
, called the
infeasible region
for which no algorithm can be
simultaneously
(
1
+
훿
)
-consistent and
휁
-robust for any
휁
<
∞
(if the hitting costs are globally
훼
-polyhedral). For any
(
훼,훿
)
outside the infeasible region, we prove that there is an exponential
trade-off between consistency and robustness. More formally, Theorem 11 proves that any algorithm
that is
(
1
+
훿
)
-consistent must be at least
훼훿
4
2
훼
+
훿
(
1
+
훼
)
2
−
훼
(
1
−
훿
2
)
훼훿
(
1
+
훿
)
−O(
1
)
-robust
.
(1)
This threshold-type behavior is unprecedented in the literature on learning-augmented algorithms
and reveals the hardness of the problem instance brought about by the non-convexity of hitting
costs.
Second,
we introduce a new algorithm for online non-convex optimization in a normed vector
space with untrusted predictions,
Adaptive Online Switching
(AOS), and provide bounds on its
consistency and robustness. Our analysis shows that AOS can be used in combination with a
black-box AI tool to match the performance of the black-box AI while also ensuring provable
worst-case guarantees.
The AOS algorithm works as follows. At each time
푡
, AOS either follows the predictions
̃
푥
푡
or
adopts a robust strategy that does not adapt to the predictions, and adaptively switches between
these two. The challenge in the design of AOS is that, on the one hand, switching must be infrequent
in order to limit the switching cost, but, on the other hand, switching must be frequent enough to
ensure that the algorithm does not get stuck following a suboptimal sequence of decisions from
either the predictions or the robust strategy.
Theorem 8 proves that, for
훼
-polyhedral hitting costs (see Definition 1), the competitive ratio
CR
(
휂
)
of AOS is a function of the accuracy
휂
of the predictions and is at most
CR
(
휂
) ≤ (
1
+
훿
+
훾
)(
1
+
2
휂
)
.
(2)
Here,
휂
is an appropriate measure of the accuracy of the predictions (see Definition 3) and relates to
the distance between the prediction
̃
푥
푡
and the optimal decision, and
훿
and
훾
are hyperparameters
of the algorithm. Note that, even though the competitive ratio is a function of the accuracy, the
algorithm is oblivious to it. If the predictions are accurate, i.e., if
휂
=
0
, then the competitive ratio of
AOS is
1
+
훿
+
훾
. In other words, AOS is
(
1
+
훿
+
훾
)
-consistent and almost reproduces the hindsight
optimal sequence of decisions if the predictions are accurate. Moreover, if
(
훼,훿
)
belongs to the
feasible region
, then
CR
(
휂
) ≤
12
+
표
(
1
)
훾
2
훼
+
훿
(
1
+
훼
)
2
/(
훼훿
)
.
(3)
Therefore, even if predictions are completely inaccurate, i.e., if
휂
=
∞
, the competitive ratio of AOS
is uniformly bounded. The trade-off between consistency and robustness is characterized by the
confidence hyperparameters
훿
and
훾
, where the robustness bound depends exponentially on both
훿
and
훼
. In light of our lower bound, this means that AOS reproduces the order optimal trade-off
between robustness and consistency in the feasible region. As a proof technique, the conventional
potential function approach fails due to the non-convexity of the problem and the incorporation of
predictions. Hence, significant novelty in the technique is required for the proof of Theorem 8 (see
Section 3.1 for a discussion).
Proc. ACM Meas. Anal. Comput. Syst., Vol. 7, No. 1, Article 12. Publication date: March 2023.
12:4
Daan Rutten, Nicolas Christianson, Debankur Mukherjee, and Adam Wierman
We complement the theoretical analysis of AOS’s performance with empirical validation in
Section 4, where we report on experiments using AOS to “robustify” the decisions of a machine-
learned algorithm for the problem of optimal microgrid dispatch with added noise and distribution
shift in the predictions. These experiments confirm that AOS effectively bridges the good average-
case performance of black-box AI with worst-case robust performance.
Third,
we extend the above results to the case when only an approximate non-convex solver is
available. As we do not make any assumptions on the convexity of
푓
푡
, it may be computationally
difficult or simply impossible to obtain the exact minimizer of
푓
푡
. We therefore extend AOS to work
with any non-exact, approximate minimizer of
푓
푡
. AOS is oblivious to the accuracy of the solver
and we prove that the competitive ratio decays smoothly in the accuracy of the solver. Moreover,
we provide bounds for the case when predictions cannot be used in every time step due to the
computational expense associated with the non-convex functions. Our bounds characterize how
the consistency-robustness tradeoff is impacted by this computational constraint. In fact, there the
impact on the competitive ratio is linear in the number of time steps between available predictions.
Fourth,
we characterize the importance of memory for algorithms seeking to use untrusted
predictions. Interestingly, AOS requires full memory of all predictions. This is a stark contrast with
well-known memoryless algorithms for online optimization with switching costs, which do not
make use of any information about previous hitting costs or actions. We prove in Theorem 15
that this contrast is no accident and that memory is needed in order to simultaneously achieve
robustness and consistency. Thus,
memory is necessary to benefit from untrusted predictions.
Fifth,
we consider an important special case when the vector space is
푋
=
R
and each function
is convex and show that it is possible to provide an improved trade-off between robustness and
consistency using a memoryless algorithm in this special case. The one-dimensional online convex
optimization setting has received significant attention in the literature, see [
2
,
16
]. In this context,
we introduce a new algorithm, called Adaptive Online Balanced Descent (AOBD), which is inspired
by Online Balanced Descent [
19
]. AOBD has two tunable hyperparameters
̄
훽
≥
훽
>
0
that represent
the confidence of the decision maker in the predictions. Theorem 16 proves that the competitive
ratio
CR
(
휂
)
of AOBD is at most
CR
(
휂
) ≤
min
{
1
+(
2
+
̄
훽
−
1
)
훽
(
1
+
2
휂
)
,
1
+(
2
+
훽
−
1
)
̄
훽
}
.
(4)
The competitive ratio of AOBD has a similar structure to AOS, but improves the robustness bound
significantly by taking advantage of the additional structure available compared to the general non-
convex case. In particular, if
̄
훽
=
1
/
훿
and
훽
=
훿
/(
2
+
훿
)
for
훿
≤
2
, then AOBD is
(
1
+
훿
)
-consistent
and
1
+
3
/
훿
+
2
/
훿
2
-robust. The result is complemented by a lower bound in Theorem 17 that proves
that for
0
<
훿
<
1
/
2
, any algorithm that is
(
1
+
훿
)
-consistent must be at least
1
/(
2
훿
)
-robust.
2 MODEL DESCRIPTION
We examine the problem of online non-convex optimization with switching costs on an arbitrary
normed vector space
(
푋,
∥·∥)
. In this problem, the decision maker starts at an arbitrary point
푥
0
∈
푋
and is presented at each time
푡
=
1
, . . .,푇
with a non-convex function
푓
푡
:
푋
→ [
0
,
∞]
. The decision
maker must then choose an
푥
푡
∈
푋
and pay cost
푓
푡
(
푥
푡
)+∥
푥
푡
−
푥
푡
−
1
∥
, i.e., the sum of the
hitting cost
of
푥
푡
and the
switching cost
from
푥
푡
−
1
to
푥
푡
. The goal of the decision maker is to solve
min
푥
푡
,
1
≤
푡
≤
푇
푇
Õ
푡
=
1
(
푓
푡
(
푥
푡
)+∥
푥
푡
−
푥
푡
−
1
∥
)
s.t.
푥
푡
∈
푋
for
1
≤
푡
≤
푇.
(5)
Note that the input is presented in an online fashion: at time
푡
, the algorithm only knows
푓
1
, . . ., 푓
푡
,
but does not know
푓
푡
+
1
, . . ., 푓
푇
or the finite time horizon
푇
. We call a collection
(
푥
0
, 푓
1
, . . ., 푓
푇
,푇
)
an
Proc. ACM Meas. Anal. Comput. Syst., Vol. 7, No. 1, Article 12. Publication date: March 2023.
Smoothed Online Optimization with Unreliable Predictions
12:5
instance
of the online non-convex optimization problem. The performance of the decision maker is
compared to the hindsight optimal sequence of decisions, defined as
(
표
1
, . . .,표
푇
) ∈
arg min
푦
1
,...,푦
푇
∈
푋
푇
Õ
푡
=
1
(
푓
푡
(
푦
푡
)+∥
푦
푡
−
푦
푡
−
1
∥
)
,
(6)
where we assume that the minimizer exists. We denote by
Opt
(
푡
)
:
=
푓
푡
(
표
푡
)+∥
표
푡
−
표
푡
−
1
∥
the cost
of the hindsight optimal algorithm at time
푡
.
We would like to emphasize the generality of our model. The decisions take values in an arbitrary
normed vector space and the hitting cost functions can be non-convex, allowing our results to be
applied to online decision-making in a variety of settings, including non-Euclidean and function
spaces, as well as to problems where decisions are inherently discrete in nature such as right-sizing
data centers [
3
]. Throughout, unless otherwise mentioned, we assume that the hitting cost functions
are globally
훼
-polyhedral for some
훼
>
0
, defined as follows.
Definition 1.
We say that a function
푓
푡
:
푋
→ [
0
,
∞]
is
globally
훼
-polyhedral
if it has a unique
minimizer
푣
푡
∈
푋
, and, for all
푥
∈
푋
,
푓
푡
(
푥
) ≥
푓
푡
(
푣
푡
)+
훼
·∥
푥
−
푣
푡
∥
.
The assumption that hitting cost functions are
훼
-polyhedral is standard in the literature on
online optimization with switching costs [
21
,
49
,
68
]. This type of structural assumption on hitting
costs is in fact necessary to ensure the existence of a competitive algorithm for online optimization
with switching costs on general vector spaces.
1
The assumption that the switching cost is a metric
is also crucial to our results; as we show in Appendix A, it is impossible to achieve simultaneous
robustness and non-trivial consistency when the switching cost is a Bregman divergence, another
common choice of switching cost, of which the squared Euclidean norm is a special case [29].
The fact that the hitting cost may be non-convex introduces new algorithmic challenges. For
example, one cannot simply interpolate two points to obtain a convex combination of the hitting
cost as done in state-of-the-art literature on online optimization without predictions [
16
,
21
,
29
].
The non-convexity also poses computational challenges as the true minimizer of a non-convex
optimization problem may not be attainable. Throughout, we therefore let our algorithms rely on
approximate solvers, defined as follows.
Definition 2.
Let
푔
:
푋
→ [
0
,
∞]
be any non-convex function. We say that
푟
approximately solves
푔
, denoted by
푟
≈
arg min
푥
∈
푋
푔
(
푥
)
, if
푟
is the result of any non-convex solver applied to
푔
. We define
the
accuracy
of the solution
푟
as
휀
(
푟
)
:
=
푔
(
푟
)
min
푥
∈
푋
푔
(
푥
)
−
1
.
(7)
Also, if
푟
1
,푟
2
, . . .,푟
푇
is the result of a sequence of non-convex solvers, we let
휀
(
푟
)
:
=
max
1
≤
푡
≤
푇
휀
(
푟
푡
)
.
Although our performance guarantees naturally rely on the accuracy of the approximate solution,
our algorithms do not require knowledge of the accuracy upfront.
2.1 Untrusted Predictions
We assume that the decision maker has access to potentially inaccurate predictions of the hindsight
optimal sequence of decisions. At time
푡
, before choosing an action, the decision maker receives a
suggested action
̃
푥
푡
∈
푋
. We want to emphasize that these predictions are of the
optimal decisions
,
1
If hitting costs are allowed to be arbitrary, or if the only imposed assumption is that hitting costs are convex, then the
problem class contains convex body chasing (CBC) as a special case [
59
]. The competitive ratio of any algorithm for CBC on
any
푑
-dimensional normed vector space is
Ω
(
√
푑
)
, so no algorithm can be competitive for CBC on an infinite-dimensional
vector space.
Proc. ACM Meas. Anal. Comput. Syst., Vol. 7, No. 1, Article 12. Publication date: March 2023.
12:6
Daan Rutten, Nicolas Christianson, Debankur Mukherjee, and Adam Wierman
and not of the hitting cost functions, as has been studied previously [
19
,
20
,
44
,
45
,
49
]. This
new model captures scenarios where, for example, a black-box machine learning algorithm is
available and outputs
̃
푥
푡
as the suggested action for time
푡
. Alternatively,
̃
푥
푡
could be the result of
using imperfect forecasts of future hitting cost functions via a look-ahead algorithm for online
optimization such as SFHC [49].
The accuracy of the predictions is measured in terms of the distance to the hindsight optimal
sequence of decisions, which we quantify as follows.
Definition 3.
Consider an instance
(
푥
0
, 푓
1
, . . ., 푓
푇
,푇
)
for the online non-convex optimization problem
and let
̃
푥
=
(
̃
푥
1
, . . .,
̃
푥
푇
) ∈
푋
푇
be a prediction sequence. We say that the prediction
̃
푥
is
휂
-accurate
for the instance if
푇
Õ
푡
=
1
∥
표
푡
−
̃
푥
푡
∥ ≤
휂
푇
Õ
푡
=
1
Opt
(
푡
)
,
(8)
where
표
푡
is the optimal sequence of decisions as defined in
(6)
.
Note that the accuracy is normalized in terms of the total cost of the hindsight optimal algorithm
to make the notion scale-invariant. For example, if the norm
∥·∥
is doubled, then both the left-hand
side of
(8)
and the optimal cost double, and hence,
휂
stays the same. This is natural since the quality
of the predictions in this case does not change. Also, note that
휂
-accuracy is a function of both
the prediction
̃
푥
and the instance
(
푥
0
, 푓
1
, . . ., 푓
푇
,푇
)
. That is, a prediction may be
휂
-accurate for one
instance, but fail to be
휂
-accurate for another.
2.2 Defining Consistency and Robustness
We measure the performance of an algorithm using the competitive ratio, which is a function of
the accuracy in our setting.
Definition 4.
Let
A
be an algorithm for the online non-convex optimization problem in
(5)
that
adapts to the predictions. The
competitive ratio
of
A
is
CR
(
휂
)
, or
A
is
CR
(
휂
)
-competitive
, if
푇
Õ
푖
=
1
(
푓
푡
(
푥
푡
)+∥
푥
푡
−
푥
푡
−
1
∥
)
≤
CR
(
휂
)·
푇
Õ
푡
=
1
Opt
(
푡
)
,
(9)
for all instances
(
푥
0
, 푓
1
, . . ., 푓
푇
,푇
)
and all
휂
-accurate predictions
̃
푥
.
The aim of this work is to design an algorithm for which the competitive ratio improves with the
quality of the predictions. We quantify this in terms of the notions of
consistency
and
robustness
,
which have recently emerged as important measures for the ability of algorithms to effectively
make use of untrusted predictions in online settings [32, 39, 43, 51, 52, 54, 58, 62].
Definition 5.
Let
A
be an algorithm for the online non-convex optimization problem in
(5)
and let
CR
(
휂
)
be its competitive ratio when it has access to
휂
-accurate predictions. We say that
A
is
(a)
(
1
+
훿
)
-consistent
if
CR
(
0
) ≤
1
+
훿
;
(b)
휁
-robust
if
CR
(
휂
) ≤
휁
for any
휂
∈ [
0
,
∞]
.
An algorithm with these qualities of consistency and robustness is guaranteed to have near-
optimal performance when predictions are perfect, along with a constant competitive ratio even
when predictions are arbitrarily bad. If predictions are, for example, the decisions made by a black-
box AI algorithm, a robust and consistent algorithm ensures a worst-case performance guarantee
without having to sacrifice the AI algorithm’s typically excellent performance. Moreover, the
algorithm we propose in this work has performance that
degrades gracefully in
휂
: that is, even if
predictions are not exactly perfect but are near-optimal, our algorithm will still achieve near-optimal
cost.
Proc. ACM Meas. Anal. Comput. Syst., Vol. 7, No. 1, Article 12. Publication date: March 2023.
Smoothed Online Optimization with Unreliable Predictions
12:7
Algorithm 1
Follow the Prediction (FtP)
푝
0
←
푥
0
for
푡
=
1
, . . .,푇
do
푝
푡
≈
arg min
푝
∈
푋
푓
푡
(
푝
)+
2
∥
푝
−
̃
푥
푡
∥
end for
2.3 Warmup: Achieving Consistency Without Robustness
By definition, following the predictions exactly guarantees 1-consistency. However, if the hitting
cost functions are steep and predictions are not perfect, naively following the predictions does not
yield a competitive ratio with a smooth dependence on the accuracy
휂
. By suitably “filtering” the
predictions, it is possible to achieve a competitive ratio that is linear in
휂
.
To this end, we present in Algorithm 1 the filtering procedure called
Follow the Prediction
(
FtP
)
that, at each time
푡
, moves to a point
푝
푡
constituting a “filtered” form of the prediction
̃
푥
푡
. The
FtP
algorithm is the same algorithm in as in [
8
], with an adjustment so that it uses an approximate
solver rather than an exact solver, since an exact solver may not be available for non-convex
problems. As we shall see in the following lemma, the competitive ratio of
FtP
is linear in
휂
.
Lemma 6.
Let
CR
(
휂
)
be the competitive ratio of
FtP
. Then,
CR
(
휂
) ≤
1
+
휀
(
푝
)+
(
4
+
2
휀
(
푝
)
)
휂.
(10)
Note that Lemma 6 does not guarantee that
FtP
is worst-case competitive, a.k.a. robust, and
in fact, it is relatively straightforward to construct example settings where
휂
is arbitrarily large
and
FtP
has an unbounded competitive ratio. For example, consider the metric space
(
R
,
|·|)
and
let
푥
0
=
0
,
푓
푡
(
푥
)
=
|
푥
+
1
|
and
̃
푥
푡
=
푡
. Then,
푝
푡
=
푡
, while
표
푡
=
−
1
. In this case, the prediction is
푇
(
푇
+
2
)
-accurate and the competitive ratio of
FtP
is at least
푇
(
푇
+
2
)
.
3 MAIN RESULTS
Although consistency and robustness are nontrivial to achieve simultaneously, it is straightforward
to obtain consistency and robustness individually. On the one hand, we saw in the previous section
that FtP guarantees consistency, but not robustness. On the other hand, an algorithm that follows
the minimizers
푣
푡
is
max
{
2
/
훼,
1
}
-robust [
68
], but not consistent. Hence, our goal in this section is
to combine the features of both algorithms to construct an algorithm that is both consistent and
robust.
A natural algorithm to consider is a ‘switching type’ algorithm, which chooses between following
the minimizers and the predictions. These switching-type algorithms have already been used
successfully in general problem settings [
8
]. In fact, due to the non-convexity of the hitting cost
functions, any reasonable algorithm must be a switching-type algorithm, since the cost of any state
in between the minimizer
푣
푡
and the prediction
̃
푥
푡
is generally unrelated to and potentially much
higher than the hitting cost at
푣
푡
or
̃
푥
푡
itself. The difficulty of designing these algorithms in our case
lies in the notion of consistency, which dictates that the cost of the algorithm must only be a small
fraction higher than the cost of the predictions. This requires a careful design of the algorithm,
which should only switch away from the prediction if it holds a strong conviction that robustness
would otherwise be violated.
We propose Algorithm 2, named
Adaptive Online Switching
(AOS), which adaptively switches
between following the approximate minimizers and filtered versions of the predictions in a manner
that ensures both robustness and consistency. The conditions in lines 5 and 10 dictate when the
algorithm should switch and are carefully designed to simultaneously guarantee consistency and
Proc. ACM Meas. Anal. Comput. Syst., Vol. 7, No. 1, Article 12. Publication date: March 2023.