A Batch-to-Online Transformation under Random-Order Model
Authors: Jing Dong
Yuichi Yoshida
Venue: NeurIPS 2023 poster (2023)
Keywords: online learning
random model setting

Abstract: We introduce a transformation framework that can be utilized to develop online algorithms with low $\epsilon$-approximate regret in the random-order model from offline approximation algorithms. We first give a general reduction theorem that transforms an offline approximation algorithm with low average sensitivity to an online algorithm with low $\epsilon$-approximate regret. We then demonstrate that offline approximation algorithms can be transformed into a low-sensitivity version using a coreset construction method. To showcase the versatility of our approach, we apply it to various problems, including online $(k,z)$-clustering, online matrix approximation, and online regression, and successfully achieve polylogarithmic $\epsilon$-approximate regret for each problem. Moreover, we show that in all three cases, our algorithm also enjoys low inconsistency, which may be desired in some online applications.

A Batch-to-Online Transformation under Random-Order Model
Jing Dong
Yuichi Yoshida National Institute of Informatics yyoshida@nii ac.
The Chinese University of Hong Kong, Shenzhen jingdong@link, cuhk, edu.
Abstract
We introduce a transformation framework that can be utilized develop online algorithms with low e-approximate regret in the candom-order model from offline approximation algorithms. We first give a general reduction theorem that trans- forms offline approximation algorithm with low average sensitivity to online algorithm with low e-approximate regret. We then demonstrate that offline approxi- mation algorithms can be transformed into a low-sensitivity version using coreset construction method. To showcase the versatility of our approach, we apply to various problems, including online (A, 2) 2.-ccutteriinng online matrix approximation, and online regression, and successfully achieve polylogarithmic e-approximate regret for each problem. Moreover, show that in all three cases, our algorithm also enjoys low inconsistency, which may be desired in some online applications.
Introduction
In online learning literature, stochastic and adversarial settings are two of the most well-studied cases. Although the stochastic setting is not often satisfied in real applications, the performance and guarantees of online algorithms in the adversarial case considerably compromised. This is particularly true for important online tasks such as k-means clustering, which gives a significantly worse guarantee than their offline stochastic counterparts Klohen-Adda et al. 2021 As result, their practical applicability is greatly limited.
Recently, the random-order model has been introduced means of modeling learning scenarios that fall between the stochastic and adversarial settings [Garber et al. 2020 Sherman et al. 2021]. In the random-order model, the adversary is permitted to choose the set of losses, with full knowledge of the learning algorithm, but has no influence over the order in which the losses are presented to the learner. Instead, the loss sequence is uniformly and randomly permuted. This effectively bridges the gap between the stochastic setting. where only the distribution of losses can be chosen by the setting, and the adversarial setting, where the adversary has complete control over the order of the losses presented to the learner.
In this work, introduce batch-to-online transformation framework designed specifically for the random-order model. Our framework facilitates the conversion of an offline approximation algorithm into online learning algorithm with e-approximate regret guarantees. Our primary technical tool average sensitivity, which was initially proposed by Varma and Yoshida [202]] to describe the algorithm's average-case sensitivity against input perturbations. We demonstrate that any offline approximation algorithm with low average sensitivity will result a transformed online counterpart that has low e-approximate regret. To achieve small average sensitivity for offline algorithms, leverage the idea of coreset [Agarwal et al., 2005 Har-Peled and Mazumdar 2004), which a small but representative subset of larger dataset that preserves important properties of the original data. We present coreset construction method that attains low average sensitivity, and when combined with the approximation algorithm, yields an overall algorithm with low average sensitivity.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

To showcase the practicality and versatility of our framework, we apply it to three popular online learning problems: online (k, -ccustttrin online matrix approximation, and online regression. In all three cases, our approach yields polylogarithmic e-approximate regret. Furthermore, due to the low average sensitivity of our algorithms, they also enjoy low inconsistency, which is the cumulative number of times the solution changes. This additional property may prove useful in certain online settings. We note that this inconsistency has also been investigated the classic online learning and multi-armed bandits literature [Agrawal et al. 1988. Cesa-Bianchi et al. 2013
2 Related Works
first introduced the notion of average sensitivity and proposed algorithms with low average sensitivity on graph problems such as minimum spanning tree, minimum cut, and minimum vertex cover problems. Various other problems have then been analyzed for the average sensitivity, including dynamic programming problems (Kumabe and Yoshida
Average sensitivity Varma and Yoshida [021]
2022], spectral clustering (Peng and Yoshida 2020). Euclidean k-clustering Yoshida and Ito] 2022] maximum matching problems Yoshida and Zhou 2021]. and decision tree learning problem Hara
and Yoshida 2023].
Online (consistent) (k, 2) >-clustteing While (k, cllusteri,, which includes k-means (2 2) and k-median (z 1) its special cases, has been studied extensively from various perspectives such as combinatorial optimization and probabilistic modeling, it can be NP-hard to obtain the exact solution (Impagliazzo al., [001]. Thus most theoretical works have been focused on designing approximation algorithms. the online setting. et et al.] (2018) proposed a Bayesian adaptive online clustering algorithm that enjoys a minimal sublinear regret. However, the algorithm is allowed to output more than & clusters. Without such assumption, [Cohen-Addad et al. [2021) proposed the first
algorithm that attains e-approximate regret of adversarial setting.
(dkog) for k-means clustering under
On a separate vein, Lattanzi and Vassilvitskij 2017 algorithm that produces a 20(=) apprrxxiite solution for the data points obtained so far at each step while maintaining an inconsistency bound of O log n). This implies that their algorithm only updates the output (k2² log" n) many times. Then, Yoshida and Ito [022 gave an online algorithm with approximation ratio (1 <) and inconsistency poly (d,
proposed an online consistent (k, =) clusstrnng
2=, 2= )) log in the random-ordd order model. We remark that the way how the losses are computed in Lattanzi and Vassilvitskii (2017). Yoshida and Ito (2022) is different from that of the online setting, and our paper considered.
et al. 2021
Online convex optimization and online principle component analysis (PCA) under the random-
order model The online random-orde optimization was proposed in Garber et al. (2020), which established a bound of O (loog n.) for smooth and strongly convex losses. This result is then improved by SSerrman et al. [2021] while still requiring smooth and convex losses.
The techniques and results are then extended to online PCA with the random-order setting, for which a regret of O (c-IV/mn was established, where Ç is an instance-dependent constant. This recovers the regret for online PCA in the stochastic setting (Warmuth and Kuzmin 2008 Nie al. 2016). We remark that PCA can be viewed as a special case of matrix approximation, in which the matrix being approximated is the covariance matrix of the data, and we discuss the more general problem of matrix approximation in this paper.
Preliminaries
For a positive integer n. let [n] denote the set 21, For real values a, b E R, a E (1 1 is a shorthand for (1 c)b= S S (1 c)b.
3.1 Offline Learning
We consider general class of learning problems. Let X' the input space, θ be the parameter space, and É θ x X R. be loss function. For simplicity, assume the loss is bounded, i.c.,

---

(0.2)) S 1. Given a set of n data points X E X", we are asked to learn parameter & E θ that minimizes the objective value ((6,X) == ExEx E(0,2)) x)). We call this problem the offline learning problem.
When the exact minimization of the loss function & is NP-hard computationally demanding, one may only hope to obtain an approximate solution efficiently. Specifically, for a >> O, we say a solution 0 E is a-approximate for X E x if E(O, X) S a mingee É(O, X). The value a is called the approximation ratio of the solution. We say (possibly randomized) algorithm A is a-approximate if the expected approximation ratio of the output solution is at most a.
3.2 Online Learning with Random-Order Model
In the online learning problem, instead of receiving all points once, the data arrives sequentially throughout a time horizon n. Specifically, the data point comes one by one, where Ie comes at time t [n]. At the time f, using the collected data points X; == (I1,..., Tt- 1), we are asked output parameter 0g E e. Then we receive the data point and incur a loss of {(0,, z1). In this work, we consider the vandom-orts order model, which the data points 21....: In may be chosen adversarially, but their ordering is randomly permuted before the algorithm runs.
To evaluate our performance, we use the notion of regret, which is the cumulative difference between our solution and the best solution in hindsight. In cases where obtaining the exact solution is hard, and one may only hope to obtain an approximate solution efficiently, we the e-approximate regret.
Definition 3.1 (e-approximate regret for the random-order model). Given a (randomized) algorithm A that outputs sequence of parameters .1...., On when given input Iı,... En. The e-approximate regret of for the random-order model defined as
(egret,(n)
JE A.f
Σ e(0,, 24) (1+ min Σ BEE t=1
(0, xx)
where the randomness over the internal randomness of A and the ordering of data points. When = 0, we simply call it the regret.
In certain cases, online algorithms required to maintain good solution while minimizing inconsistency, which quantified as the number times the solution changes. This can be expressed formally as Inconsistency(n) = EA.( 1 I(0, * 1. where is the indicator function.
3.3 Average sensitivity
On a high level, the notion of average sensitivity describes the differences in the performance of randomized algorithm with respect to input changes. This difference is captured by the total variation distance, which is defined below.
Definition 3.2. For a measurable space (Ω, F) and probability measures P, P.Q defined on (9, F). The total variation distance between P and Q is defined as TV(P,Q) == = AEF P(()) Q(4)
Equipped with this, the average sensitivity of randomized algorithm is formally defined as the average total variation distance between the algorithm's 's output on two training data sets that differ by deleting one point randomly. For dataset X (II,.... ..,) E n and i [m], let (+) denote the set (I1,-... - Ii+1, .r,,) obtained by deleting the i-th data point. Then, the following definition gives a detailed description of the notion:
Definition 3.3 (Average Sensitivity [Varma and Yoshida 2021 Yoshida and Ito. 2022 D. Let A
(randomized) algorithm that takes an input X E X" and outputs A(X). For B E + R4, we say that the average sensitivity of A at most if
(V(A(X),A(XO)) & B(n),
for any X E X", where we identify A(X) and A(x with their distributions.
3

---

Batch-to-Online Transformation in the Random-Order Model
In this section, describe general framework that transform any offline (1 -)-approximate algorithm into an online algorithm with low c-approximate regret. Our goal is to show the following.
Theorem 4.1. Let A be (randomized) (1 -approxiimate algorithm for the offline learning algorithm with average sensitivity 3 Z - R Then, there exists an online learning algorithm in the random-order model such that Regret, (n) O (E ((8 + 1).
Our method described in Algorithm|] T problem. Then, at each time step, based on the collected data X simply output 02 A(X,-1)
be an approximation algorithm for the offline learning
Algorithm 1: General saach-to-onling conversion
Offline approximation algorithm A. for t I...., do Obtain O, by running A on X₁-1.
Input:
Receive Ty and E(fe, F4).
To show that Algorithm aachieees low approximate regret when A has a low average sensitivity, the following lemma is useful.
Lemma 4.2. Let A be a (randomized) algorithm for the offline learning problem with average sensitivity B Z R4. Then for any input E X", we have
a
Σ
E ),
a.) B())
where: I a aatbb means a
Proof of Theorem 4.1 Consider Algorithm] ! For any E [n], we have
1 (10++1,x))
E
((0111,
E A
(((0441)0411) ((01+1,
A.fxa
((A(())) ((A())))))))()))))))) .21))
E A.x..
S E
+ +(((t)
(By Lemma 4.2)
A.
((A(())) E(A(X)))) ).((x)
E A,zz
+ +
(X(A(X)). + +(1 ((1))22000 23(11,
< E A.fx.)
where the last equality follows by replacing x; with #++1 in ((A(x!)), x.;)) because they have the same distribution, and the last inequality by the average sensitivity of the algorithm.
Rearranging the terms, we have
((0++1,.e))
(1+ t
E [10++1.244111
E A.Ex;)
+ 23(t))
<
E (a:)
+ 23(t),
A.(a:)
where OPT, == ming E(0, X,) is the optimal value with respect to X,, and the second inequality holds because the approximation ratio of 0.+1 is 1 + in expectation.
Taking summation over both sides, we have
E A
Σ ((O,, 2rr) = [((01,
+
E A.
I++1)
A.zi

---

O)PT
n-
11+ E
+ Σ 3(6)
Fix the ordering 01, In, and let (i E [t]) be the loss incurred by in OPT,, In particular, we have OPT, = - C. Note that o; are random variables depending on the ordering of data points, but their sum, OPT is deterministic. Then, we have OPT, s Ei=t. because OPT, minimizes the loss up time f, Hence, we have
OPT,
E
E
E {zc
E [
C
{ar)
t=
OPT,
R
OPT
n OPT..
n
n
Therefore, we have
BAfaa,)
Σ (()
- -11+))OPT, = 300
3(1) +
5
Approximation Algorithm with Low Average Sensitivity via Coreset
To design approximation algorithms for the offline learning problem with low average sensitivity, we consider the following approach: We first construct small subset of the input that well preserves objective functions, called a coreset, with small average sensitivity, and then apply any known approximation algorithm on the coreset. Coreset is formally defined as follows:
Definition 5.1 -lar- and Mazumdar (2004), Agarwal et al. (205]). Let E: θ x X + R+ be loss function and let X E X". For e O, we say that a weighted set (Y,w) with S X and Y + RR4, is an e-coreset of X with respect to l for any 0 E O we have EyEY w w(y)e(0, v) (1+)) FEX 2(0,z))
Now, we consider a popular method for constructing coresets based on importance sampling and show that it enjoys low average sensitivity. For a data E X, its sensitivity ax (x) (x:iis its maximum contribution to the loss of the whole dataset, more formally
[(0,x) x))
x x = sup
eee E(0, X)
Algorithm 2: Coreset Construction Based on Sensitivity Sampling
Input: Loss function f: θ x X - R4, dataset X X², m N, and 0 For each æ X, compute x (z) and set p(x) = ox (z) Exexxxxxxx
Let S be an empty set.
3 for i = ,,..., m do
Sample with probability p(x).
Sample 5 from (p(z), (1 + </2)p(x)) uniformly at random.
(()) is undefined then
5 U (z).
w(x) + 1/p.
else
10
w(x) + w(x)= + 1/p.
11
return w).
It is known that we can construct a coreset follows: A data point E X is sampled with probability
p(x) == x Er x (x'), and then its weight in the output coreset is increased by 1/8. where
'The reader should not confuse sensitivity, which is measure for data points, with average sensitivity, which measure for algorithms.
5

---

P is slight perturbation of p(z). This process is to be repeated for fixed number of times, where the exact number depends on the approximation ratio of the coreset. See Algorithm for details. We can bound its average sensitivity as follows:
Lemma 5.2. The average sensitivity of Algorithm is O (6-+m/n).
general bound on the number times we need to repeat the process, i.e., m in Algorithm 2 to obtain e-coreset is known (see, e.g., Theorem 5.5 Braverman et al.] (2066). However, do not discuss here because better bounds are known for specific problems and we do not use the general bound the subsequent sections.
Online (ki, -
In online applications, unlabelled data are abundant and their structure can be essential, and clustering serves as an important tool for analyzing them. In this section, application of our general batch-to-online transformation, we describe an online (k, -lllusterin method that enjoys low regret.
6.1 Problem setup
The online (k: z)-clustering problem [Cohen-Addad et al. 2021 is an instance the general online learning problem described in Section 3 We describe the problem as follows: Let 2 1 be integer and 2 2 1 be a real value. Over a time horizon n, at each time step t. a data point 2, Rd is given. Using the set of data points X,-1 {z
are asked to compute set Ze { z of k points in _ that minimize E (Z,, T2) minj=I,.... || žj lل which is the z-th power the Euclidean distance between z; and the closest point Z. Note that Z, plays the role of 0, in the general online learning problem. The regret and e-approximate regret are defined accordingly.
6.2 Method and results
One important ingredient to our method is the coreset construction method proposed by HHunn and Vishnoi 22200. The method provides unified two-stage importance sampling framework, which allows for a coreset with a size that is dimension independent. Specifically, the method constructs an e-coreset of size Ô (min {s- 2== 22= 2²==_4k]) in Ö(ddk) time, where the Ô hides polylogarithmic factors in and k. We remark that the importance of sampling steps in the framework is similar to the ones described in Section which thus allows us to analyze its average sensitivity.
Algorithm B giies brief description of our algorithm, while detailed description is presented in the appendix. The algorithm adheres to the standard transformation approach, whereby an offline approximation algorithm is run on the coreset derived from the aggregated data.
Algorithm 3: Online consistent (ks, cllusstrii
Input: Offline algorithm AA for (k, cllusterin, approximation ratio 1 + + (0, c/3.
for tort=1 1...,,,, do
Construct an c'coreeett C,-1 (5,-1. on X,-I-
Obtain cluster set Z, by running PTAS A with approximation ratio of (1 + 6') C.-1.
Receive I, dd and ((Z,, E R..
Theorem 6.1. For any E (0, 1), Algorithm 3 giives regret bound of
Regret, (n) S 50 ((((165))) 10000))002,0--111100 52-15 log kn
kn
+ -2=-22
log log
log m
Moreover, there exists an algorithum that enjoys the same regret bound and an inconsistency bound of Inconsistency(x) 0 ((1682) e --522-13 -22-15.5 log(e" 'kn) e 22- 22 log l log(e kn)) log n) for (k, 2) cluustrring

---

Remark 6.1. When = 2, previous results for the adversarial setting show e-approximate regret bound of O(ky / d dkn)) (Cohen-Addad al. 2021 J. In comparison, although our regret for the random-ords model, our method and results accommodate range of values for 2, and the regret bound is only polylogarithmicall dependent n and is independent of the dimension d.
7 Online Low-Rank Matrix Approximation
Low-rank matrix approximation serves as a fundamental tool statistics and machine learning. The problem is to find rank-k matrix that approximates input matrix A E [2dx as much possible. In this section, we apply the transformation framework to the offline approximation algorithm to obtain a low regret online algorithm.
7.1 Problem setup
Low-rank matrix approximation By the singular value decomposition (SVD), a rank-r matrix A E IRdxn can be decomposed as A = UEV", where U Rdxr and V E R are orthonormal matrices, Σ Rxxr a diagonal matrix with A's singular values on the diagonal. The best rank-k approximation of A is given by
A U
argmin Be BeRdk*rank(BBss
|A - |A-Blp B
where || || denotes the Frobenius norm, Σg E B is diagonal matrix with A₂ 's top l singular values on the diagonal, and U E Bdxk and V E R are orthonormal matrices obtained from U and V, respectively, by gathering corresponding columns. The best rank-k approximation can also be found by projecting A onto the span of its top singular vectors, that is, A = U. A. Then, we can say an orthonormal matrix Z is an e-approximate solution
A zz A S (1 (1++)
U² U
The matrix approximation problem serves as an important tool in data analytics and is closely related to numerous machine learning methods such as principal component analysis and least squares analysis. When dealing with streaming data, the online version the matrix approximation problem becomes vital tool for designing online versions of the machine learning algorithms mentioned above.
Online matrix approximation Through time horizon of receive column of A, a Rd at each time step t. We are then asked to compute Z, [Rd that minimizes
(Z,, 0x) = ||a, Z.Z. 0z lel
Without loss of generality, we will assume that the losses are bounded between [o, 1]. We remark that similar assumptions also made in Nie al. [2016).
The online matrix approximation problem serves as core component of online machine learning algorithms such as principle component analysis. These algorithms are important to range of applications, such as online recommendation systems and online experimental design [Warmuth and
Kuzmin 2008
Nie et al. 2016).
7.2 Method and results
In the context of low-rank matrix approximation, the coreset of matrix is called the projection-cost preserving samples, defined as follows:
Definition 7.1 (Rank-k Projection- Cost Preserving Sample Cohen et al. (017]). For n' n, subset of rescaled columns C E Rdxn' of A E Rd is a (1 + projection-com cost preserving sample if. for all rank-k orthogonal projection matrices X RRddd d (1 - - XA < C XCI S
(1 ++]]]lA XA
Such sketches that satisfy Definition 7.I can be constructed via importance sampling-bass routines, which are modifications of the "leverage scores". Specifically, for the i-th column a, of matrix A.

---

the ridge leverage score is defined (A) a. (AAT + I|A 1AA-Aull 0is where f denotes the Moore-Penrose pscudoinverse of a matrix [Cohen et al. 2017].
Now, we introduce our online matrix approximation algorithm in Algorithm 4 which builds upon transformation framework. It computes the approximation of the matrix from the sketch derived from the aggregated matrix using ridge leverage scores.
Algorithm 4: Online low rank matrix approximation
Input: Approximation parameters E (0, 1). Set 8 = (ce/n) and m O (c=2
for / 1, ....., do
Construct A,-1 Rdx(t-1) by concatenating 01....
Let C,-1 Rd be the zero matrix.
for j = .....; do
Sample the i-th column E Rd of A,-1 with probability ps = (((i1)) Σ,=i 7A((
Sample w R uniformly from [1/vtp:: tps, (1 tp:. Replace the j-th column of C with w 04.
Set Ze E Rdd to the top A: left singular vectors of C,
10
Receive a₂ E R2 and ((Z,, ax) E I.
Theorem 7.2. For any e E (0, 1), Algorithm has regret Regret,(m) ( log n kon) Moreover, there exists an algorithm for online low-rank matrix approximation that enjoys the same regret bound and an inconsistency bound of Inconsistency (n) = 0 (E (
log log(e log(<-Ikm)). kn)).
Remark 7.1. The online matrix approximation with the random-order setting has previously been investigated in the context of principle component analysis by Garber et al. [2020J. They established regret of O (c- where Ç is the smallest difference between eigenvalues of A,A,T In contrast, our result gives polylogarithmic result on e-regret, which translate to an exact regret of O (cOPT (E 2k log log(e kn))), with OPT being the minimum possible cumulative loss attained by the hindsight best approximate.
8 Online Regression
In the online regression problem. at each time step & E [n]] we are asked to output a vector x, E Rd, and then we receive vectors a, E IRd and b, that incurs the loss of E(v,, a,, b,) = ||a,] x, - bl12- Without loss of generality, we assume that the losses are bounded between 00, 1.. We note that similar assumptions are also made in [Cesa-Bianchi Bianchi et al. 1996 Ouhamma et al. 2021
With our general reduction framework, we show an e-regret upper bound as follows.
Theorem 8.1. For any (0, 1), Algorithm 5 has regret Regret, (n) O (E (ee-d log n (ogg(E-ddn)
Moreover, there exists an algorithm for online regression that enjoys the same regret bound and an inconsistency bound of (nconsistencyy() (n) = O (c 2e-22lopp doloo (on(c=)dn))..
Remark 8.1. In the stochastic setting, the online regression problem has been extensively investigated Foster 1991 Littlestone et al. 1995 Cesa-Bianchi et al. 1996 Ouhamma et al. 2027]. Using online ridge regression or forward algorithms, the regret shown be O (d n). In the random-ordd model setting, Garber et al. (2020), Sherman et al. (2021) I give O( O(yn))-tpe regret when the matrix has a small condition number. comparison, our result altains polylogarithmic e-approximate regret, while maintaining no requirement on the loss function or the condition number. Our result can translated an exact regret of O (eOPT + (e- 22d log (dn))))))))), with OPT being the minimum possible cumulative loss attained by the hindsight best parameter.

---

8.1 Method and results
Similar to the low-rank matrix approximation problem, we utilize the leverage score method to learn subspace that preserves information regarding the regression. Specifically, score to learn a e-subspace embedding, which is defined as follows.
the leverage
Definition 8.2 (e-Subspace Embedding). A matrix S E Rmxx is said to be an e-subspace embedding of A Ig for any vector x E R., we have (1 <) |Ar| S ||Aa|]| S (1 + e
The subspace embedding serves the same functionalityy as coreset in the problem of online regression, it preserves the loss information while enjoying a much lower dimension. In the online regression problem context, we define the leverage score follows.
Definition 8.3 (Leverage Score). Let A UEVT be the singular value decomposition of A Raxd For i E [n], the i-th leverage score of A, is defined as |Us,:12
With the leverage score, we propose Algorithm 5 The algorithm follows the general transformation framework, where the regression problem is solved at every step with the sketch derived from the aggregated matrix using leverage score. For notational convenience, construct the sketch by appending rows instead of columns as we did in Section
Algorithm 5: Online consistent regression
Input: Approximation parameters E (0,
Set 8 (e//n) and m O (e 2dlog(8-1dd)
for f ,,...,, do
Construct Aç-1 E (t- by stacking a__ .... a. Construct E I by stacking , b1-1
Set S' (t- be the zero matrix.
for j = 1.... m do
Sample E [t 1] with probability Pi
(A
2 (A 1)
Sample w E R uniformly from Smpt
1+c
v
Smpi
Replace the j-th row of St with w e. where E RR-11 is one-hot vector with on the i-th index.
L
10
Solve the regression problem F; = min, |S'A,11 S' e.g., by an iterative method such as Newton's 's method.
Receive a, E 12d be E IR, and loss E(x,, ae, be).
The subspace embedding result of Woodruff
2014 immediately shows the following:
Theorem 8.4. For any ō E (0, 1), if m an e-subspace embedding for A,- with (e dogg(6 d)) columns.
O (6- ((2llogg55-1)) then with probability 2 1 -, S
To obtain Theorem 8.1
we first analyze the average sensitivity of the leverage score sampling. Then, with Theorem 8.4 and the general reduction Theorem 4.1 we obtain the regret bound.
Experiments
We here provide preliminary empirical evaluation of our framework in the context of online k-means clustering, and online linear regression, with the result shown in Figure | Our experiments are conducted with various approximation ratios and experimental setups
0.1, 0.01, 0.001, with k = 3 or k 5 clusters). We then compare the performance of the proposed algorithm to the hindsight optimal solution. For k-means clustering, we obtain the hindsight optimal solution by applying k-means++ to all the data. In the context of regression, we utilize the least square formula to compute the hindsight optimal solution. Our experimental results demonstrate that the proposed algorithm is highly effective, and its performance aligns with our thcoretical findings.

---

Semmans duueriig
Kemeers ckantering
Deline Regreesion
OuTs, -
20
Ours, 596 0.01
0,002
Hindlight octimdl
Aeceoppe uoa
Dam, eps 5.1
OuTs, epe =
Zumt epe 0.01
ape 0.01
Ours, opc 1.001
OU 055 0.001
optina
Timsalop
(a) h-means, clusters
(b) k-means, clusters
(c) Regression
Figure I: Experimental results for k-means clustering with 3, clusters and online regression. Each experiment is repeated with 5 different random seed to ensure reproducible results. The shaded region indicates the 1 standard deviation.
10 Conclusion
In this paper, proposed batch-to-online transformation framework that designs consistent online approximation algorithms from offline approximation algorithms. Our framework transforms an offline approximation algorithm with low average sensitivity to online algorithm with low approximate regret. We then show a general method that can transform any offline approximation algorithm into with low sensitivity by using stable coreset. To demonstrate the generality of our framework, we applied it to online (k, =)-custtri online matrix approximation, and online regression. Through the transformation result, obtain polylogarithmic approximate regret for all of the problems mentioned.
Acknowledgement
This work is supported by JSPS KAKENHI Grant Number 20H05965 and 22H05001.
References
Pankaj K Agarwal, Sariel Har-Peled, Kasturi R Varadarajan, et al. Geometric approximation via coresets. Combinatorial and computational geometry, geametrr 52(1):1-30, 2005.
Rajeev Agrawal, MV Hedge, and Demosthenis Teneketzis. Asymptotically efficient adaptive alloca- tion rules for the multiarmed bandit problem with switching cost. IEEE Transactions on Automatic Control, 33(10)8899990) 906,9999,11110 1988.
Vladimir Braverman, Dan Feldman, Harry Lang, Adiel Statman, and Samson Zhou. New frameworks for offline and streaming coreset constructions. arXiv preprint 16Xiv: 2016.
Nicolo Cesa-Bianchi, Philip M Long, and Manfred K Warmuth. Worst-case quadratic loss bounds for prediction using linear functions and gradient descent. IEEE Transactions on Neural Networks, 7(3))604-6199 1996.
Nicolo Cesa-Bianede Ofer Dekel, and Ohad Shamir. Online learning with switching costs and other adaptive adversaries. Advances in Neural Information Processing Systems, 2013.
Michael B Cohen, Cameron Musco, and Christopher Musco. Input sparsity time low-rank approxima- tion via ridge leverage score sampling. In Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithums, 2017.
Vincent Adden-Addad, Benjamin Guedj, Varun Kanade, and Guy Rom. Online k-means clustering. In International Conference on Artificial Intelligence and Statistics, 2021.
Dan Feldman and Michael Langherg. A unified framework for approximating and clustering data. In Proceedings of the 43th Annual ACM SIGACT Symposium Theory of Computing, 2011.
10

---

Dean P Foster. Prediction in the worst case. The Annals of Statistics, pages 1084-1090, 1991.
Dan Garber, Gal Korcia, and Kfir Levy. Online convex optimization in the random order model. In International Conference on Machine Learning, 2020.
Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In Proceedings of the 36th Annual ACM SIGACT Symposium Theory of Computing, 2004.
Satoshi Hara and Yuichi Yoshida. Average sensitivity of decision tree learning. In International Conference on Learning Representations 2023.
Lingxiao Huang and Nisheeth K Vishnoi. Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal. In Proceedings of the 52nd Anmual ACM SIGACT Symposium on Theory of Computing, 2020.
Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponen- tial complexity? Journal of Computer and System Sciences, 63(4):51 2001.
Soh Kumabe and Yuichi Yoshida. Average sensitivity of dynamic programming. In Proceedings of the 2022 Annual ACM-SIAM Symposium Discrete Algorithms,, 2022.
Silvio Lattanzi and Sergei Vassilvitskii. Consistent k-clustering. In International Conference Machine Learning 2017.
L Li, B Guedj, and S Loustau. A quasi-bayesiar perspective to online clustering, Electronic Journal of Statistics, 12(2):307-3311 001-3771-3133 2018
Nicholas Littlestone, Manfred K Warmuth, and Philip Long. On-line learning of linear functions. Computational Complexity, 5:1-23, 1995.
Jiazhong Nie, Wojciech Kotlowski, and Manfred K Warmuth. Online PCA with optimal regret. The Journal of Machine Learning Research, 17(1) 60700 2016.
Reda Ouhamma, Odalric-Ambrym Maillard, and Vianney Perchet. Stochastic online linear regression: the forward algorithm replace ridge. Advances in Neural Information Processing Systems, 2021.
Pan Peng and Yuichi Yoshida. Average sensitivity of spectral clustering. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2020.
Uri Sherman, Tomer Koren, and Yishay Mansour. Optimal rates for random order online optimization. Advances in Neural Information Processing Systems, 2021.
Nithin Varma and Yuichi Yoshida. Average sensitivity of graph algorithms. In Proceedings of the 2021 ACM-SIAM Symposium Discrete Algorithmss, 2021.
Manfred K Warmuth and Dima Kuzmin. Randomized online PCA algorithms with regret bounds that are logarithmic in the dimension. Journal of Machine Learning Research, (00c)):287-2332, 2008.
David P Woodruff. Sketching as tool for numerical linear algebra. Foundations and Trends@ in Theoretical Computer Science, 10(1-2):1-155 2014.
Yuichi Yoshida and Shinji Ito. Average sensitivity of Euclidean k-clustering. In Advances in Neural Information Processing Systems, 2022.
Yuichi Yoshida and Samson Zhou. Sensitivity analysis of the maximum matching problem. In Innovations in Theoretical Computer Science Conference, pages 58:1-58:20, 2021.
11

---

A Proofs for Section 4
Lemma 4.2. Let A be a (randomized) algorithm for the offline learning problem with average
sensitivity B Z4 + R4. Then for any input X E X,, we have
a
n B a() + B(n),
(l(((A(X (1)
xi)1
where x= = a t means a bbb
Proof. We have
E((((()) saa] + 2xa) -EIA -I((A(A x.))
x=)) Σ IV(A(X).
xx)) + (m))
The other direction can be shown analogously.
12

---

B Proofs for Section 5
In this section, we prove Lemma 5.2
[(0,xx) Lemma B.I. For any i E [n] and x E X((,, ler lerg()) = argmaxp - ((0,x') Then, we have
& {00(),,;) (0()),x)
0 0 - Exexo & (0(0, x') -Evex (0(0)xx))
((0.w)) Proof. Denote 0 = argmaxg Evexx ((0,z))
then for the left-hand side of the inequality, we have
((0,z)
2(0,z)
xx (xx
Σ Exex 8 20,xx)
Evex (0,
0.
For the second inequality, we have
e (((()),))
e(0()),)) .x)
xxo ox(x) S
Σ Ex (0(0))z) Erex (0(1)
{0((), (r.)),))) .f ((((),
Erexo 8 (000, Ex'x e (0(0),z))
Lemma B.2. For any i [m], we have
Σ
ox(x) Σ (x)
- (x(x).
ZX
NEX
Proof. By Lemma B.I
we have
Σ [x(x))
Σ
xxta (x') =ox (x;) - E
(xx (x) S sox (xi)
ZEX
x
ZEX(0
and we have
Σax(x)= - Σ xxw(x') = ox ox((xi)
Σ
-x)
xEX
2'ex
xeX())
{((()), E((()), ,2)
2 2x (xi) Σ
Evexw (00))x') Ev'ex e ((())xx)
=EX())
((((),z))
=0x
20.
Exe E (0(10,z')
Then, have
Σ (x((x)=
Σ (xm(x')
= Σ
Σ [x(x)) Σ Exte (2))
Ø
z'EX(0
1=1
xEX
x'EX(0)
ox (x:) < Σ ox(x).
x
Lemma B.3. We have
ox(x)
(x)
Σ
2.
Exex Ox
Erexto (x)) (x)
1=1 z6
13

---

Proof. First, we have
ox(xx
(x)
Ex(x
(x(o (()
Σx
(x(x)
(x()(1)
1- Exeert Exxx
Exex
Exex
EveXw (x))
(x) Er'xm (x - Exex
1
Exexax(a) (xxw( -ox (2))
ΣxEx (x(x) Evexo (x((('))
We can bound this quantity from below and above by Lemma B.I
(x) Emexo (xw(x') - Exex
{(0(), l (((()
1
ExEx 0x(x) Evexo (xi((a)) (xw() Exexx(x(())
ExEx ex(x) xx(xxxx) & (0(0, EEvex e x0(0,x))
ox(x)
(x
I Ex
Ex Exexm0x0 (x")
(xxw(x) Emexts (xw((") - Exex 0x(2)
Σxex xx (x) Ex'ex (x)
Then, we have
xx(x) E xx(x)
(x)(x))
Exexx (x
5 ExEx ox(x)) (x)
Σ (xc( -xo(
>'eX(0)
FEX
((00), ,00) 21) (8()),, zz)
1
Exexox(x) Exex ((0)) x²) Exexx (f11),x')
It then follows,
(x(x) ExEX ox xx(x)
(x()
Σ
EveXO (xi(x)
1= x)
(x)
Σ xxw(x')- - Σ ox(xx
<
ExEx Ex'xx (x)) ('EX(()
XmI ()
#EX
1
e ((B()), E (((())
ExEx xx(x) EXEEX (00) x²) Ex E (0(1) xx))
Ev'xx E
xxio (x') ExEx [x(x
l ((0()),2) .2.)
ox(x) Exex e (B()),
+ ExEx 0x (x)
2,
where the second to last inequality is from Lemma B.2 and the last inequality is by E Fx(x) >
Lemma B.4. For 0, let X and X' be sampled from the uniform distribution over [B, (1 c)
and [B', (1 + e)B'), respectively. Then, we have
1 1
B'
TV(XX')
<
E
B
14

---

Proof. The proof is implicit in Lemma 2.3 of Kumabe and Yoshida [2022]
Lemma 5.2. The average sensitivity of Algorithm is (c mm/n).
Proof. The average sensitivity of importance sampling can be bounded by the of the average total variation distance between selected elements and that between assigned weights, conditioned on that the selected elements are the same. The former is bounded by
I
Σ
CI-
ox (x;)
Σ #EX()
xx(x) ΣzEx ox(x) Evexw (x0
(x( (x)
Σxex
C
C
+0
+
C
=0
where the first equality is Lemma
B.3
With Lemma B.4 we have the latter as
Σ
ox(x)
(x)
1te
(x)(
(Er'xxo xxio
min
E Exexox
2' (x()
ox(x)) 2xex
1+E ox(x)
(x(o
|C|.
Σ
ErEx (x(x)
ExexO (xw((x)
11
1=1
C
0
en
Combining the two terms, we have the average sensitivity of importance sampling be bounded as
C
0
[
0
[
15

---

C Proofs for Section 6
C.1 Algorithm
We now introduced the detailed version of Algorithm In Algorithm 7 we provide a detailed description of the coreset construction method for clustering, which based on [Huag and Vishnoi [2020]. To make the coreset construction enjoys small average sensitivity, we perturbe the weights assigned (Line and Line 11). We show that this preserves the approximation ratio while makes the overall algorithm insensitive. With this, we obtain the online consistent clustering Algorithm 6 which clusters data from coreset at each step.
Algorithm 6: Online consistent (ki, =)clusttrrin
Input: PTAS algorithm D for (k, cluustriii approximation ratio e, 6 E (0, 1).
for t = 1,..., 7t do
Construct e-coreset C.-1 (St-1,Wt-1) by running Algorithm 7 on X,-1-
Obtain cluster set Ze by running PTAS with approximation ratio of (1 + E) on Ct-1-
Receive I₁ and (4).
Algorithm Coreset construction for clustering Huang and Vishnoi [2020]
Input: A set of point X, approximation parameter e, (0, 1), integer k Set c = e/c for some large constant c 0.
2 Compute a k-center set C₁ C TR' as an e-approximation of the (k, dt.=ssccltteerng problem over X with the D*-sampling algorithm with approximation ratio of O log k))
3 For each x E X, compute the closest point to x C", c² (z), with ties broken arbitrarily. For each C denote X be the set of points X with c* (x)
For each x E X, let (x) 22
2 (x)11
Σrex [(C²(z)
Pick a non-uniform random sample D Ni ((1682)10; 10 e 55 15 log () points from X,
where each E X is selected with probability Evex 11 (v)
x(x)(()
For each x E DJ, sample äx (2) from
Σnex (1) [
(1 +
FxEx z1x(1) [
Set ux (x) u (x)
For each c E C compute De to be the set of points in D whose closest point in C" is with ties broken arbitrarily.
For each x E D1, (x) = EpEDi EX( :9)
"x(x))-f(" .2)
10 Pick non-uniform random sample D of N₂ (c--2222 k log k points from X₂, where each x E X2 is selected with probability Eyenl (2
x2.((x)
Lyepl x2,)(1) 199
> Enent (x)
11 For each æ E D2, sample x (z) from
(1 + E) (2x(())
12 Set wx (x) = (x) For each C let (c) (1+ 10e) ExED, ux(x) - wx(x).
14 D2 U C*
15 wr(x) (x)
16 Output (S, w)
C.2 Analysis
Theorem C.1. Algorithm Sasimmmoutttp outputs an e-coreset with probability least 1 8 and has average
sensitivity of
t (168z)10z -52 log $ 22- 2 log & log & (1 + 6 2--2 2 log k log k)
n
16

---

Proof. We first show that our coreset construction method gives an e-coreset.
We remark that the way we assigned the weights is perturbed version of the method presented in Huang and Vishnoi (2020). Then, to show that the perturbed version of the assignment of the weight still preserves the coreset approximation ratio, show that the perturbed version still satisfies Corollary 15.3 Feldman and Langberg [201]] and Theorem 14.5. Then using the same argument as Theorem 15.4 4.4 of Feldman and Langberg [01 our coreset construction method gives an e-coreset.
In the first importance sampling stage, we only perturb ū (a) by a ratio of + e, for each x E D The same is applied in the second stage with (1),, for all x D For E C*, we have
(1 + 10c)
Σ (x) ZED.
Σ wx(x) 5 (1+)
( (1+ (1+10c) 10c)
Σ ūx(x) ZED:
Σ
öx (x)
DEDDDD.
REDIND.
In all cases, the result from [Feldman and Langberg. 2011] still holds, the weights are scaled by 61+ at most. By the same argument that all perturbed weights are scaled by (1 ++ <) at most, we have Theorem 15.4 of Feldman and Langberg [2011) holds with ratio of e( <). This results in an approximation of 1 + <(1++) by applying the argument of Theorem 15.4 of Feldman and Langberg [201T]. Rescale e/c for some constant > 0 gives approximation ratio of I + and completes our argument that Algorithm produces an c-coreset with probability at least - 6.
To show that our method enjoys low average sensitivity, we upper bound the average sensitivity of the two importance sampling stage of Algorithm S separately.
The average sensitivity of importance sampling in the first stage can be bounded by the average total variation distance between selected elements and that between assigned weights, conditioned on the selected elements are the same. By Lemma 5.2, we can upper bound the average sensitivity of the first importance sampling stage to O(N1 I)), where N1 = O ((168z)10z 52 15 ()))).
In the second stage, as points are selected with probability Σyex 02,x we bound the total variation distance between selected points similar way as to that for the first stage. This gives bound of (NN//n) where N2 O (e 2===22k log k log & ). To bound the average total variation distance between assigned weights, we again apply the same argument as above and obtain bound of (N2/n).
x3.x(a)
Combining these and that the average sensitivity of Line of Algorithm 7 is Olk//n) (by Lemma 2.2 of Yoshida and Ito (2022), we have the average sensitivity as
+ Ni + N2
k (168:)10ze-58) 52- 52-15 1.t log t/h + 22 2 log log & cb
=
71
Theorem 6.1. For any E (0, 1), Algorithm gives regret bound of
Regret, (n) s s ((11632)20
log + -2--2k log & log
kn
kn
logn)
Moreover, there exists an algorithum that enjoys the same regret bound and an inconsistency bound of Inconsistency(n) = (((182)) 10z -22 k.5 log(e- kkk) + E -2--2k log k log(e log(E-)kn) log n) for (k, cluustrrnn
Proof. First, we note that the approximation ratio of the algorithm with respect the aggregated loss is at most
(1- d) (1+ ;) (1+ + on 11t
from the choice of 6, i.e., 5 = O(e/n).
Also, we note that the overall average sensitivity is
" Σ 3(t)= = 0
(1682) 10z 15 log $ + - --2- -2 2/ log k log
t=1
=0
((1688))10s 155 log - 2 log k log
k
logn
ed
17

---

Then substituting this into Theorem 4.1 for 2 2 1, we have regret bound of
(( (168:) 10= -0a- E0 15 log k
Regret, (n) - 0
5 + 2-22-2k log k log ed
log n
(( (168:) 102 (068=)100--62-1111 -52-15 log +e 2= log k log =0
kn
kn
log
For the second claim about inconsistency, we first convert the average sensitivity bound an inconsistency bound of the same order. This can be done by Lemma 4.2 of (Yohhida and Ito 2022] and by arguing similar way as Lemma 4.5 of (Yoshida and Ito 2022 by showing that there exists computable probability transportation for the output of Algorithm 3 This thus yields an inconsistency of ((16682)102 102 1 52- 15 log(e kn)e 2: 2 log k log(e kn)) log n)..
18

---

D Proofs for Section 7
Theorem 7.2, For any E (0, 1), Algorithm has regret Regret, (k log n lon) Moreover, there exists an algorithm for online low-rank matrix approximation that enjoys the same regret bound and an inconsistency bound of Inconsistency (n) = (c log n log(c-1kn)
Proof. Let 8 0 be determined later. By Theorem 6 from Cohen et al. for any rank-k orthogonal projection X, by sampling m = ( log k)) columns, in Line of Algorithm 5] we have,
2017 with probability 1 5.
(1-2) |A. - XA, -A- & |IC, XC,II S (1 ;) | XA.
With this, note that the algorithm has approximation of 1 choosing the hidden constant in å small enough.
c/2 + on S 1 + e b
Note that by applying Lemma 5.2 this routine has average sensitivity of O(m/l)
O (E- log( log(b-1k)/t) at any step t. Then set Z, to the top & left singular vectors of C, and
we have
A Z, A S {1+c)| U.U.AN -
To obtain the regret, we calculate the overall average sensitivity as E" 1i= B(t) Σx=1 O 1og(6)))))) choice Oc//n), we have Regret, (n) = 0 (e-2% log log(c- (kk))
(c log 1o)( Applying Theorem 4.1 and from the
For the second claim about inconsistency, we prove this convert the average sensitivity bound to an inconsistency bound of the same order. This can be done by Lemma 4.2 of (Yoshida and Ito 2022] and by arguing in a similar way as Lemma 4.5 of Yoshida and Ito 2022 by showing that there exists a computable probability transportation for the output of Algorithm 3
19

---

E Proof for Section 8
Theorem 8.1. For any E E (0, 1), Algorithm has regret Regret, (n) 2 n log(e- dn)).
Moreover, there exists an algorithm for online regression that enjoys the same regret bound and an inconsistency bound of (nconsistencyyn)
d log(c-Idn))
Proof. By Theorem 8.4 the algorithm has an approximation of 1 + + c/2 on S + by choosing the hidden constant in ó small enough.
Similar to the low-rank case, the average sensitivity of leverage sampling at step t is Summing over the average sensitivity
doog (log(d/))
22t
dlog(d/0)
(dlog n log(d/))
Eo t=1 eat
= =0
Take this into Theorem and with 5 (e//n). have e-regret of O 2d log(dn/e)).
Similar that Theorem 6. and Theorem 7.2 we prove the second claim by converting the average sensitivity bound to inconsistency bound of the same order. This can be done by Lemma 4.2 of (Ysshida and Ito 2022] and by arguing in a similar way as Lemma 4.5 of (oshidaa and Ito 2022 by showing that there exists computable probability transportation for the output of Algorithm
20


Reviews:
[{"review_id": "mcdSq8jll2", "reviewer": "Reviewer_mLKj", "summary": "The paper considers the random order model originally proposed by Garber et al. '20, and presents a generic framework to take any (approximate) offline algorithm and via usage of coresets turn it into an online algorithm with low average sensitivity, which can be then used to obtain an (approximate) regret bound. Some specific cases are considered where this framework is applied, including online clustering, online low-rank matrix approximation, and online regression.\n", "questions": "* **Coresets vs direct uniform convergence of the cumulative loss.** At a high level, is it correct to say that the coreset construction is based on uniform concentration of the loss, and that in some specific cases this uniform concentration comes cheap? If so, could we alternatively take the offline algorithm and run it on the cumulative loss as is, then claim a regret bound owed to uniform concentration of the cumulative loss directly? Some more questions related to this point:\n\t* Does big-$O$ hide a dimension factor in Lemma 5.2?\n\t* Section 5 presents a coreset construction method, but then in the section that follows (6.2) a different method (that of y Huang and Vishnoi '20) is used. Why?\n* **Average sensitivity vs algorithmic stability.** TV is the infimum (over all couplings of the two RVs) of the expected 0-1 distance. This is an upper bound on the Wasserstein distance which is the infimum (over all couplings of the two RVs) of the expected euclidean distance. This Wasserstein distance is basically average algorithmic stability. Is it correct that average sensitivity is a strictly stronger notion?\n* **Applicability in the full adversarial setup.** It seems to me the method you propose should also work in a fully adversarial setup. Average sensitivity is akin to uniform stability; the output of your offline algorithm \"stabilized\" via coresets does not care about stochasticity in the examples. If the output of an approximate ERM does not change much between rounds this should lead to a regret bound, perhaps? Roughly; $\\sum_{t} \\ell(A(X_t), x_{t+1}) - \\ell(A(X_{t+1}), x_{t+1}) \\leq \\sum_t \\beta(t)$ and by \"Be-the-Leader\" Lemma (Kalai & Vempala '03), $\\sum_{t} \\ell(A(X_{t+1}), x_{t+1}) \\leq \\sum_{t} \\ell(\\theta^\\star, x_{t+1})$.\n* **$\\epsilon$-regret vs competetive-ratio**. How does $\\epsilon$-regret compare to competitive ratio from competitive analysis?\n* Lines 36-37 \"... and when combined with the approximation algorithm ...\" - to my understanding, whether the the offline algorithm that operates on the coreset is approximate or exact is irrelevant to the point you are trying to make, here and in the paper more generally, no? \n\n\n\n## Minor comments\n* \"Although the stochastic setting is not often satisfied in real applications, the performance 15 and guarantees of online algorithms in the adversarial case are considerably compromised\" - the meaning of this sentence is not clear to me.\n* Lemma 4.2: I didn't see the notation \"$x = r \\pm \\beta$\" defined anywhere (I gather it signifies $r-\\beta \\leq x\\leq r+\\beta$).\n* What does it mean to \"run $\\mathcal A$ with approximation ratio of $(1-\\epsilon')$...\" (line 4 of Algorithm 3)? Theorem 6.1 does not mention explicitly any requirements from $\\mathcal A$. Looking into the detailed version of the algorithm (Algorithm 6), it seems $\\mathcal A$ should be a PTAS. Perhaps putting this in the main text could make this a bit clearer. \n* ״We remark that the importance of sampling steps in the framework is similar to 193 the ones described in Section 5, which thus allows us to analyze its average sensitivity.״ --> \"the importance sampling steps\"?\n", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The high level idea is elegant, the paper is coherent and well written.\n* The proposed method offers novel algorithmic approach for batch-to-online reductions.\n", "weaknesses": "* I was missing some context that would allow better understanding the approach presented in the paper; specifically comparison to the approaches considered in [Garber et al., 2020, Sherman et al., 2021]. The role of uniform convergence in coresets construction vs running the offline algorithm directly on the cumulative loss, and average sensitivity vs algorithmic stability. See some of my questions below.\n* Perhaps this is not a weakness per se, but (please correct me if I'm wrong - this was not entirely clear to me) the rates obtained do not strictly improve any prior art excluding Section 6 which improves Cohen-Addad et al., '21 but applies less generally. The rest of the results pertain to $\\epsilon$-approximate regret while the previous works mentioned obtain standard regret bounds.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments! Due to the space limit, we address the major comments here.  \n# 1. Comparison to previous works.\nIt is possible to convert our results to standard regret bounds. Using the definition of approximate regret, we can rearrange the terms and obtain $\\mathbb{E} _{\\mathcal{A},\\\\{x_t\\\\}}\\left[\\sum^n _{t=1} \\ell(\\theta_t, x_t) - \\mathrm{OPT}\\right] = \\epsilon  \\mathrm{OPT} + \\mathrm{Regret} _\\epsilon(n) $. Then by applying the (generalized) AM-GM inequality to the right-hand side and tuning $\\epsilon$ appropriately so the inequality holds as equality, we can obtain an exact regret. \nFrom the approximate regret of our online matrix approximation result, we can translate it to $O(\\mathrm{OPT}^{2/3} (d \\log n \\log(\\epsilon^{-1} kn))^{1/3}) $.   \nFrom the approximate regret of our online regression result, we can translate it to $O(\\mathrm{OPT}^{2/3} (d \\log n \\log(\\epsilon^{-1} dn))^{1/3})$.  We also want to highlight that our results may be more general in some applications. For online matrix approximation with the random-order setting, the previous result by [Garber et al., 2020] is $O \\left(\\zeta^{-1} \\sqrt{kn}\\right)$, where $\\zeta$ is the smallest difference between two eigenvalues of $\\boldsymbol{A} \\boldsymbol{A}^\\top$. In contrast, our result does not depend on this $\\zeta$. For online regression, [Garber et al., 2020] give $O(\\sqrt{n})$-type regret when the matrix $\\boldsymbol{A}$ has a small condition number. In comparison, our result maintains no requirement on the condition number. \n# 2. Coresets vs direct uniform convergence of the cumulative loss.\nWe agree with the reviewer's comment on a high level. Yet the coreset construction method is still different from the uniform concentration of loss on the technical details because the former guarantees that the multiplicative error is small whereas the latter usually refers to guarantees on additive error. In the case where the offline algorithm is approximate, optimizing the cumulative loss at each step may not lead to small regret. The following shows that at least the be-the-leader lemma does not work. Suppose that at each time step, we run an offline algorithm to obtain an $(1+\\epsilon)$-approximate solution on the cumulative loss. Let $\\theta^\\ast = \\min_\\theta \\sum^t_{i=1} \\ell(\\theta, x_i)$, we obtain $\\theta_t$ such that $\\sum^t_{i=1} \\ell(\\theta_t, x_i) \\leq (1 + \\epsilon)\\sum^t_{i=1} \\ell(\\theta^\\ast, x_i)$. Note that we assume that one has access to $x_t$ before making the decision at time $t$, in our setting one does not even have this. \nThen the regret is\n$$\\left(\\ell(\\theta_1, x_1) + \\ldots + \\ell(\\theta_T, x_T)\\right) - (1+\\epsilon)\\left(\\ell(\\theta^\\ast, x_1) + \\ldots + \\ell(\\theta^\\ast, x_T)\\right) \\leq \\left(\\ell(\\theta_1, x_1) + \\ldots + \\ell(\\theta_T, x_T)\\right) - \\left(\\ell(\\theta_T, x_1) + \\ldots + \\ell(\\theta_T, x_T)\\right) $$\nBecause $\\{\\theta_t\\}^T_{t=1}$ are approximate solutions, we cannot proceed the be the leader lemma as we cannot say \n$\\left(\\ell(\\theta_T, x_1) + \\ldots + \\ell(\\theta_T, x_{T-1})\\right) \\geq \\left(\\ell(\\theta_{T-1}, x_1) + \\ldots + \\ell(\\theta_{T-1}, x_{T-1})\\right) $.\nIn the case where the offline algorithm is exact, optimizing with respect to the cumulative loss at each step (follow the leader) works in the stochastic setting. Yet it remains unclear to us whether this result still holds in the random order setting. \n\nRelated questions: No, Lemma 5.2 is independent of dimension $d$. The coreset construction method required to derive Theorem 5.1 is obtained by applying Algorithm 2 and the coreset construction proposed by Huang and Vishnoi '20 together to obtain dimension-independent results. The overall algorithm is given in the appendix (Algorithm 7). We will revise this in the final version to make this more explicit. \n\n# 3. Average sensitivity vs algorithmic stability. \nThe average sensitivity cannot be directly compared to the algorithmic stability. The algorithm stability describes the change in loss functions by removing or replacing a data point while the average sensitivity describes the change in the algorithm's output by removing a data point. For more discussion on this, we refer to Varma, N., \\& Yoshida, Y. (2021). Average sensitivity of graph algorithms. SODA. \n\n# 4. Applicability in the full adversarial setup\nWe do not think the argument applies to the adversarial setting, as $\\sum_{t} \\ell(A(X_t), x_{t+1}) - \\ell(A(X_{t+1}), x_{t+1}) \\leq \\sum_t \\beta(t)$ does not hold in the adversarial setting. This is because we can only guarantee that on average, removing a point does not change $X_{t+1}$. Yet for every $t$, removing $x_{t+1}$ might be the worst change to $X_{t+1}$. \n\n# 5. $\\epsilon$-regret vs competetive-ratio\nThe $\\epsilon$-regret quantifies the cumulative discrepancy between the losses incurred by an online algorithm and the $\\epsilon$-approximation of the losses obtained by the optimal hindsight solution. The competitive ratio determines the maximum factor by which the online algorithm's cost could exceed the cost of an optimal offline solution in the worst case. The optimal solution is also defined differently, in regret analysis, we consider $\\min_\\theta \\sum_t \\ell(\\theta,x_t)$ as the optimal value, but in competitive analysis, we consider $\\sum_t \\min_\\theta \\ell(\\theta,x_t)$ as the optimal value. In general, $\\epsilon$-regret and the competitive ratio are not interchangeable.\n\n# 6. Line 36-37\nThe approximation ratio of the coreset is irrelevant to the point we are trying to make, but we do need to operate the offline algorithm on the obtained coreset (which enjoys low average sensitivity) to have the overall algorithm enjoy low average sensitivity, and hence low regret.\n\n# Misc\n\"the importance sampling steps\": We are referring to the importance sampling (based on sensitivity scores) mentioned in Section 5 in the overall coreset construction algorithm for clustering (which is in the appendix, Algorithm 7). \n"}, {"review_id": "EEmffmNe8X", "reviewer": "Reviewer_A1nn", "summary": "The authors present a framework for reducing online to offline learning. More presicely, they consider random order online learning where at each round a random point of some domain $X$ is presented to the learner (as opposed to some adversary choosing the example). They first show that an offline algorithm with low average sensitivity, i.e., the output of the algorithm does not depend too much on any single point, then it can be effectively used to solve the corresponding online problem via a standard \"follow-the-leader\" type reduction. In particular, at round $t$ having observed the points $X_{t-1} = x_1,\\ldots, x_{t-1}$ in the\nonline learning setting, the learner runs the offline algorithm on $X_{t-1}$ and uses its answer to play at the current round. They next show how to obtain offline algorithms with low average sensitivity by constructing a coreset via sensitivity sampling.  They apply their framework to various problems such as online clustering and online linear regression.\n", "questions": "See weaknesses.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "\nThe online-to-batch problem considered in this work is well-motivated and interesting. The authors provide a unified approach to obtain online algorithms for random-order online learning tasks and show some non-trivial results for popular online problems such as online regression.  I believe that those results are going to be of interest for the NeurIPS community.\n\nThe applications of the framework proposed in this work yield improved regret bounds compared to the prior work.  In the case of online matrix approximation application, this work provides a regret bound that is only logarithmic in the horizon $n$ while the prior work the regret was roughly $\\sqrt{n}$ and also depended on a ``condition number'' of the observed matrices.\n\nThe paper is very carefully written and the main results and proofs were easy to follow.\n", "weaknesses": "This work considers the weaker online learning model of random order (instead of the more standard adversarial model).  In Remark 6.1 (online clustering)\nthe authors compare with online algorithms that dealt with the adversarial setting.  I think a table with precise comparisons with prior work would help this paper.\n\nThe online to offline reduction in the random ordering assuming low average sensitivity is not very surprising and the proof (see proof of Lemma 4.2) is rather straightforward. Also, it seems to crucially rely on the fact that the online learning is random order. Would a this or a similar approach based on low average sensitivity yield any guarantee for online learning in the adversarial setting?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments!\n\n# Applicability in adversarial setting and comparison to the previous bounds\nWe thank the reviewer for the constructive advice, we added a comparison table for the results we obtained in our manuscript. \n\nWe believe that the online-to-offline reduction through low average sensitivity, while may be seemingly straightforward, can provide insights into developing new online learning algorithms. Specifically, the general transformation framework provides a recipe for designing low-regret algorithms for a range of online learning problems with off-the-shelf offline algorithms. We also want to remark that in section 5, we show that the low average sensitivity assumption can be realized via insensitive coreset construction methods. \n\nRegarding the applicability of our framework in the adversarial setting, we do not think the argument applies to the adversarial setting, as $\\sum_{t} \\ell(A(X_t), x_{t+1}) - \\ell(A(X_{t+1}), x_{t+1}) \\leq \\sum_t \\beta(t)$ (Lemma 4.2) does not hold in the adversarial setting. This is because we can only guarantee that on average, removing a point does not change $X_{t+1}$. However, we cannot guarantee the worst case. So for every $t$, removing $x_{t+1}$ might be the worst change to $X_{t+1}$. "}, {"review_id": "2LATnz3kaB", "reviewer": "Reviewer_4met", "summary": "The paper presents a general method for converting an offline approximation to a learning problem into an online algorithm for the random-order problem which enjoys low (epsilon-approximate) regret. Specifically, the regret of this method depends on the sensitivity of the offline approximation; intuitively, this is the amount by which the distribution of outputs for the algorithm changes upon a small change to the input. \n\nFirst, the paper presents the construction for converting offline approximation algorithms to online algorithms for the random-order model. This construction is quite simple: at any step, we run the offline approximation on the part of the input that has already arrived, and use the output as the choice of the online algorithm for the next step. This is shown to yield low epsilon-approximate regret when the offline algorithm has low sensitivity. \n\nNext, the paper presents/analyzes low-sensitivity offline algorithms for a few online problems (online clustering, online matrix approximation and online regression); these algorithms can then be plugged into the aforementioned framework in order to yield regret bounds for these online problems. \n\nTo my understanding, the main algorithmic concept used in designing low-sensitivity offline approximation is using coresets, which are subsets of the input that accurately represent the overall input. The paper analyzes a method for constructing such coresets, and shows that it has low-sensitivity. This coreset construction is then used to choose stable subsets of the input, yielding online algorithms with low regret and low inconsistency (which is a measure of changes in the online algorithm's output over time). ", "questions": "none", "limitations": "yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The algorithmic framework introduced is general, and could be applied to additional online learning problems. \nThe paper introduces the goal of having low-sensitivity offline approximations for the sake of this offline-to-online conversion; this could be used to guide future research efforts. \nThe algorithmic technique used for designing low-sensitivity algorithms in the paper is nice.\n", "weaknesses": "The offline-to-online conversion itself is quite simple, and does not introduce any algorithmic techniques (arguably, this is the first conversion that comes to mind). \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments! We hope to address the concerns raised in the following response. \n\n> The offline-to-online conversion itself is quite simple and does not introduce any algorithmic techniques (arguably, this is the first conversion that comes to mind).\n\nWe believe that the online-to-offline reduction through low average sensitivity, while may be seemingly straightforward, can provide insights into developing new online learning algorithms. Specifically, the general transformation framework provides a simple recipe for designing low-regret algorithms for a range of online learning problems with off-the-shelf offline algorithms. \n\nWe would also like to note that although the overall conversion might seem straightforward, much more algorithmic techniques and insights are required to design appropriate coreset construction methods and obtain the theoretical guarantee. For example, in order to obtain a low average sensitivity coreset construction method, Algorithm 2 is proposed with a careful perturbation on the weights of coresets. The specific algorithm used for deriving the results for the applications, such as clustering, requires even more design techniques to obtain such dimension-independent results.  \n\n"}, {"review_id": "h9taKYmnSh", "reviewer": "Reviewer_uJY4", "summary": "This paper provides a general framework for how to use good offline methods to construct online methods under the random-order setting.  It points out the importance of the average sensitivity in the transformation from good offline methods to good online methods.", "questions": "1. can this method also solve the case with $\\epsilon=0$? At least for the online linear programming problem, offline LPs can be accurately solved, and the regret (epsilon=0) can also be small under the random-order setting. Can this setting also be converted by your paper?", "limitations": "N/A", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The framework is very general for the algorithm design of online algorithms based on offline algorithms.\n\n2. The connection between regret and average sensitivity is beautifully characterized.", "weaknesses": "1. It looks the method cannot cover the setting with $\\epsilon=0$. If you can, please clarify it and I will further raise my rating.\n\n2. it is also better to have some numerical experiments of the performance on some specific problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful and positive comments! In the following, we address the raised concerns point by point.\n\n# 1. Recover $\\epsilon = 0$ (exact regret)\n\nWe can obtain exact regret for our algorithms. Using the definition of approximate regret, we can rearrange the terms and obtain $\\mathbb{E} _{\\mathcal{A},\\\\{x_t\\\\}}\\left[\\sum^n _{t=1} \\ell(\\theta_t, x_t) - \\mathrm{OPT}\\right] = \\epsilon  \\mathrm{OPT} + \\mathrm{Regret} _\\epsilon(n) $. Then by applying the (generalized) AM-GM inequality to the right-hand side and tuning $\\epsilon$ appropriately so the inequality holds as equality, we can obtain an exact regret. \nFrom the approximate regret of our online matrix approximation result, we can translate it to $O(\\mathrm{OPT}^{2/3} (d \\log n \\log(\\epsilon^{-1} kn))^{1/3}) $.   \nFrom the approximate regret of our online regression result, we can translate it to $O(\\mathrm{OPT}^{2/3} (d \\log n \\log(\\epsilon^{-1} dn))^{1/3})$. \n\n# 2. Online LP\nWe believe that our general transformation framework can provide insights into new algorithms for online LPs in the random-order setting. Let us consider the following online integer LP (the binary version of this is also studied in [Li et al., 2020], \n$ \\max \\ r^{\\top} x , \\text { s.t. } A x \\leq b$, where $r =\\left(r_1, \\ldots, r_n\\right)^{\\top} \\in \\mathbb{R}^n, \\boldsymbol{A}=\\left(a_1, \\ldots, a_n\\right) \\in \\mathbb{R}^{m \\times n}$, and $b =\\left(b_1, \\ldots, b_m\\right)^{\\top} \\in \\mathbb{R}^m$. Here $a_j=\\left(a_{1 j}, \\ldots, a_{m j}\\right)^{\\top}$ denotes the $j$-th column of the constraint matrix $\\boldsymbol{A}$. At each time step $t$, we receive $r_t, a_t$ and are asked to compute $x_t$. In the offline case, this can be exactly solved by the cutting plane or ellipsoid methods. In the online case, we first want to choose a subset of columns and weights, \n\n$A=(a'_i,\\ldots,a'_k), w_1,\\ldots,w_k$ \n\nsuch that $Ax \\leq b$ (approximately) holds whenever $\\sum_{i=1}^k w_i a'_i x_i \\leq b$ holds. This step is similar to lines $6$-$9$ of Algorithm 5. Then one can use an exact method at each step on the sketched matrix. Using a similar analysis of Theorem 8.1, one should be able to obtain a regret bound for online linear programming. We leave the detailed derivation of the algorithm and analysis for future work. \n\nLi, X., Sun, C., \\& Ye, Y. (2020). Simple and fast algorithm for binary integer and online linear programming. Advances in Neural Information Processing Systems, 33, 9412-9421.\n\n# 2.  Experiments\n\nWe would first like to highlight that our work is primarily theoretical in nature, as our focus lies in exploring and analyzing the theoretical foundations of the general framework proposed. Moreover, the related works are mostly theoretical as well, such as [Cohen-Addad et al., 2021] (for online clustering), [Garber et al., 2020] (for online regression, and online matrix approximation in PCA). Due to the scarcity of available code for baseline algorithms, it is hard to conduct a fair empirical evaluation of our approach in the limited time of the author's response period.  \n\nNonetheless, we here provide a preliminary empirical evaluation of our framework in the context of online $k$-means clustering, online linear regression (see the additional file in the overall rebuttal file), and various approximation ratios and experimental setup ($\\epsilon = 0.1, 0.01, 0.001$, with $k=3$ or $k=5$ clusters). We compare the performance of the proposed algorithm to the hindsight optimal solution. For $k$-means clustering, we obtain the hindsight optimal solution by applying $k$-means++ to all the data. In the context of regression, we utilize the least square formula to compute the hindsight optimal solution. Our experimental results demonstrate that the proposed algorithm is highly effective, and its performance aligns with our theoretical findings."}, {"review_id": "qdL7N23Nzx", "reviewer": "Reviewer_zXrL", "summary": "This is a paper about online learning in the random arrival/order model, i.e., the adversary chooses samples but they are randomly permuted before being presented to an online algorithm. The authors propose a general tool that establishes a reduction to the offline/batch setting. The bounds that one can obtain with that tool are in terms of approximate regret, i.e., on top of the standard regret one also loses an epsilon fraction of the optimum.  The key idea behind the reduction is to use a coreset to reduce the sensitivity of the offline algorithm; the rest is fairly straightforward. After presenting the general tools, the authors show how to apply it to three specific problems: clustering, low-rank matrix approximation, regression.", "questions": "I’d be curious to see an experimental comparison with [Cohen-Addad et al., 2021].\n\nDefinition 3.1 (approximate regret) seems to be a standard one, so you could provide a reference and a bit more of a context.\n\nMinor remarks:\n\nLine 116: Is F supposed to be A?\n\nLines 123, 235: \\citet -> \\citep\n\nLine 166: data -> data point\n\nLine 191: logarithmic -> polylogarithmic\n\nAlgorithm 3, Input: “approximation ratio eps \\in (0, 1)” -> “approximation ratio 1+eps, eps \\in (0, 1)”\n\nLine 221: square -> squares\n\nLines 227, 259: assumptions are also assumed -> assumptions are also made \n\nLine 253: outermost brackets should be bigger, there should not be one O inside of another\n\nLine 270: missing closing bracket\n\nLine 276: a -> an\n\nLine 288: \\citep -> \\citet\n\nLine 295: “an offline approximation algorithm” -> “offline approximation algorithms”\n\nLine 364: the second to last inequality requires some justification\n\nLine 395: insensitivity -> insensitive, algorithm 6 -> Algorithm 6", "limitations": "The results yield only approximate regret bounds, which seems to me somewhat limiting.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The main result is a general tool that potentially can be applied to different problems.\n\nObtaining this result required a certain level of technical mastery, and was not completely trivial.\n\nThe paper is well written and easy to read.", "weaknesses": "Technical novelty is very limited. The paper combines known results in a very natural (though technically difficult) way. One could argue that the hard (and novel) part of the job was choosing the right pieces to put them together – but e.g. the idea of using coresets in a very similar context appears already e.g. in [Cohen-Addad et al., 2021] (the authors do not mention that).\n\nThere are no experiments – even though one of the applications is a clustering problem studied by Cohen-Addad et al. [2021], who provided some preliminary experimental results, so it would be fairly easy to compare to them. It would be particularly interesting because the theoretical bounds in the two papers are not directly comparable.\n\nEven though the paper provides new algorithms for three problems previously studied in the literature, because of the specific setup, the theoretical bounds are, as far as I understand, incomparable to the previous ones.\n\nThe results allow only for approximate regret bounds (and only under random arrivals). It seems to me to be a big limitation, and the authors did not manage to convince me that this is not the case.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments. In the following, we address the raised concerns point by point. Minor comments and typos have already been addressed and corrected in our manuscript. \n\n# 1. Technical Novelty\nWe respectfully **disagree** with the reviewer's comment suggesting that our results are merely a combination of known results. The example from [Cohen-Addad et al., 2021], which uses coresets for $k$-means clustering, does not diminish the originality and novelty of our approach. It is important to note that while both works employ coresets, they serve different purposes in entirely distinct contexts. In [Cohen-Addad et al., 2021], coresets are used to reduce the number of experts in the MWUA algorithm, whereas, in our work, coresets are used to achieve a small average sensitivity. \n\nOur main technical contribution is to the general framework for batch-to-online transformation via the notion of average sensitivity, which applies to a range of applications. Our results for $(k,z)$-clustering is only an example of applications of the general transformation framework. \n\nOn the $(k,z)$-clustering problem, we also want to emphasize that the scope of our results extends beyond the $k$-means clustering discussed in [Cohen-Addad et al., 2021]. Our findings are applicable to the general $(k, z)$ clustering problem, where $k$-means represents a specific case for $z = 2$. It is also worth noting that using a dimension-independent coreset method for general clustering with the algorithm proposed by [Cohen-Addad et al., 2021] does not automatically lead to sublinear and dimension-independent regret. This is primarily because other components of their algorithm still rely on the assumption that $z = 2$, and they do not permit dimension-independent results.\n\n# 2. Experiments \nWe first would like to remark that Cohen-Addad et al.~[2021] only provided an example of FTL and FLT-MWUA in $k$-means clustering to demonstrate their poor performance. The proposed algorithm (Algorithm 1, $\\epsilon$-regret minimization) is not empirically evaluated. This, as well as the absence of released example code, prevents us from conducting a direct comparison to their approach. \n\nIt is also important to highlight that our work is primarily theoretical in nature, as our focus lies in exploring and analyzing the theoretical foundations of the general framework proposed. Nonetheless, we provide a preliminary empirical evaluation of our framework in the context of online $k$-means clustering, online linear regression (see the additional file in the general rebuttal), and with various approximation ratios and experimental setup ($\\epsilon = 0.1, 0.01, 0.001$, with $k=3$ or $k=5$ clusters). We compare the performance of the proposed algorithm to the hindsight optimal solution. For $k$-means clustering, we obtain the hindsight optimal solution by applying $k$-means++ to all the data. In the context of regression, we utilize the least square formula to compute the hindsight optimal solution. Our experimental results demonstrate that the proposed algorithm is highly effective, and its performance aligns with our theoretical findings. \n\n# 3. Exact regret bound and comparison to previous bounds\nIn the case where the problem is NP-complete (for example, $(k,z)$-clustering), no efficient algorithm can attain sublinear exact regret, and thus our framework can only obtain approximate regret. \n\nUsing the definition of approximate regret, we can rearrange the terms and obtain \n$$\\mathbb{E} _{\\mathcal{A},\\\\{x _t \\\\}}\\left[\\sum^n _{t=1} \\ell(\\theta _t, x _t) - \\mathrm{OPT}\\right]  = \\epsilon  \\mathrm{OPT} + \\mathrm{Regret} _\\epsilon(n) .$$\nThen by applying the (generalized) AM-GM inequality to the right-hand side and tuning $\\epsilon$ appropriately so the inequality holds as equality,  we can obtain an exact regret. \n\nFor example, from the approximate regret of our online matrix approximation result, we can translate it to $O(\\mathrm{OPT}^{2/3} (d \\log n \\log(\\epsilon^{-1} kn))^{1/3})$. From the approximate regret of our online regression result, we can translate it to $O(\\mathrm{OPT}^{2/3} (d \\log n \\log(\\epsilon^{-1} dn))^{1/3})$. \n\nWe also want to highlight that, in the case of $k$-means ($z = 2$), our Theorem 5.1 gives a logarithmic regret bound (on $n$), which is also dimension independent. In comparison [Cohen-Addad et al., 2021] depend on the dimension $d$ and give a $O(\\sqrt{n})$ for regret. For online regression, [Garber et al., 2020] give $O(\\sqrt{n})$-type regret when the matrix $\\boldsymbol{A}$ has a small condition number. In comparison, our result attains polylogarithmic $\\epsilon$-approximate regret, while maintaining no requirement on the loss function or the condition number. \n\n# 4. Line 364, Lemma 4.2, second to last inequality\n Let $\\mathcal{D}$ be the distribution over pairs of outputs that attains $\\mathrm{TV}(\\mathcal{A}(X), \\mathcal{A}(X^{(i)}))$.\n    Then, we have\n$$\\mathbb{E }_{\\mathcal{A}}[\\ell(\\mathcal{A}(X),x_i)] - \\mathbb{E} _{\\mathcal{A}} [\\ell(\\mathcal{A}(X^{(i)}), x_i)] =\n \\mathbb{E} _{(\\theta,\\theta^{(i)}) \\sim \\mathcal{D}}[\\ell(\\theta,x_i) - \\ell(\\theta^{(i)}, x_i)] $$\n$$\\leq \\mathrm{TV}(\\mathcal{A}(X), \\mathcal{A}(X^{(i)})) \\cdot \\max _{\\theta'} \\ell(\\theta', x_i)\n        \\leq \\mathrm{TV}(\\mathcal{A}(X), \\mathcal{A}(X^{(i)})) , $$\nwhere the last inequality is by the assumption that $\\ell(\\cdot,\\cdot) \\leq 1$ (In the case where this is not true, we can normalize the losses to satisfy this assumption).\n\n"}]

Author rebuttal:
We thank the reviewers for their insightful comments and constructive advice!

We would first like to highlight that our work is primarily theoretical in nature, as our focus lies in exploring and analyzing the theoretical foundations of the general framework proposed. Moreover, the related works are mostly theoretical as well, such as [Cohen-Addad et al., 2021] (for online clustering), [Garber et al., 2020] (for online regression, and online matrix approximation in PCA). Due to the scarcity of available code for baseline algorithms, it is hard to conduct a fair empirical evaluation of our approach in the limited time of the author's response period.  

We here provide a preliminary empirical evaluation of our framework in the context of online $k$-means clustering, online linear regression (see the additional file), and various approximation ratios and experimental setup ($\epsilon = 0.1, 0.01, 0.001$, with $k=3$ or $k=5$ clusters). We compare the performance of the proposed algorithm to the hindsight optimal solution. For $k$-means clustering, we obtain the hindsight optimal solution by applying $k$-means++ to all the data. In the context of regression, we utilize the least square formula to compute the hindsight optimal solution. Our experimental results demonstrate that the proposed algorithm is highly effective, and its performance aligns with our theoretical findings.

Meta-review: All five reviewers are positive about this paper and think it should be accepted and I support their decision. Please take into account to reviewers comments when preparing the final version.
Decision: Accept (poster)