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.
Paper
Similar papers
Peer review
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.
Strengths
The main result is a general tool that potentially can be applied to different problems. Obtaining this result required a certain level of technical mastery, and was not completely trivial. The 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). There 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. Even 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. The 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.
Questions
I’d be curious to see an experimental comparison with [Cohen-Addad et al., 2021]. Definition 3.1 (approximate regret) seems to be a standard one, so you could provide a reference and a bit more of a context. Minor remarks: Line 116: Is F supposed to be A? Lines 123, 235: \citet -> \citep Line 166: data -> data point Line 191: logarithmic -> polylogarithmic Algorithm 3, Input: “approximation ratio eps \in (0, 1)” -> “approximation ratio 1+eps, eps \in (0, 1)” Line 221: square -> squares Lines 227, 259: assumptions are also assumed -> assumptions are also made Line 253: outermost brackets should be bigger, there should not be one O inside of another Line 270: missing closing bracket Line 276: a -> an Line 288: \citep -> \citet Line 295: “an offline approximation algorithm” -> “offline approximation algorithms” Line 364: the second to last inequality requires some justification Line 395: insensitivity -> insensitive, algorithm 6 -> Algorithm 6
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
3 good
Contribution
2 fair
Limitations
The results yield only approximate regret bounds, which seems to me somewhat limiting.
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.
Strengths
1. The framework is very general for the algorithm design of online algorithms based on offline algorithms. 2. 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. 2. it is also better to have some numerical experiments of the performance on some specific problems.
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?
Rating
8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
3 good
Contribution
3 good
Limitations
N/A
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. First, 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. Next, 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. To 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).
Strengths
The algorithmic framework introduced is general, and could be applied to additional online learning problems. The 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. The algorithmic technique used for designing low-sensitivity algorithms in the paper is nice.
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).
Questions
none
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
yes
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 online 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.
Strengths
The 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. The 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. The paper is very carefully written and the main results and proofs were easy to follow.
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) the 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. The 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?
Questions
See weaknesses.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
4 excellent
Presentation
4 excellent
Contribution
3 good
Limitations
Yes
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.
Strengths
* The high level idea is elegant, the paper is coherent and well written. * The proposed method offers novel algorithmic approach for batch-to-online reductions.
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. * 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.
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: * Does big-$O$ hide a dimension factor in Lemma 5.2? * 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? * **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? * **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})$. * **$\epsilon$-regret vs competetive-ratio**. How does $\epsilon$-regret compare to competitive ratio from competitive analysis? * 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? ## Minor comments * "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. * 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$). * 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. * ״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"?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
4 excellent
Presentation
3 good
Contribution
3 good
Limitations
N/A
Thank you for the response. Could you please elaborate a bit more on point 3? How exactly do you apply AM-GM and tune epsilon to get such a bound for online matrix approximation?
Using AM-GM to get exact regret bound
From the definition of regret, we can 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) $. In the case of online matrix approximation and online regression, $ \mathrm{Regret} _\epsilon(n) = O \left(\epsilon^{-2}k \log n\log(\epsilon^{-1}kn)\right)$ and $\mathrm{Regret} _\epsilon(n) = O\left(\epsilon^{-2}d \log n \log (\epsilon^{-1}dn)\right)$ respectively. Let us short hand this term to be $\mathrm{Regret} _\epsilon(n) = O (B / \epsilon^{-2})$. We now use a generalized AM-GM inequality, $\epsilon \mathrm{OPT} + B / \epsilon^{-2} \geq \left( \epsilon^2 \mathrm{OPT}^2 \cdot B/\epsilon^2 \right)^{1/3}$. We then pick $\epsilon = O \left( \frac{B ^{1/3}}{\mathrm{OPT}^{1/3}} \right)$ to make it holds as equality. Take this value of $\epsilon$ in gives a regret bound of $O \left( B^{1/3} \mathrm{OPT}^{2/3}\right)$, which is $O(\mathrm{OPT}^{2/3} (k \log n \log(\epsilon^{-1} kn))^{1/3})$ in the case of matrix approximation.
Thank you for a quick reply. Given all the above explanations of how your contributions fit the context of prior work, I increase my initial evaluation to 6.
Thank you!
We thank the reviewer for the positive feedback!
Thank you for these clarifications and answers. I raise my rating, especially for the answer to the first question.
I would like to thank the authors for their rebuttal. ### 2. Coresets vs UC Could you please clarify the relation between Algorithm 2 and Algorithm 7? ### 3. average stability vs algorithmic stability Whether removing or replacing a datapoint is not important in the definition of algorithmic stability, and a stronger notion (and the one mostly used in practice) of average stability measures the change in output, not loss function. The difference pointed out in Varma, N., & Yoshida, Y. (2021) is with regards to *uniform* stability. I don't see how it applies to average stability (or uniform stability where the datapoints are averaged over; in average stability, both the input sets and datapoints are averaged over).
We thank the reviewer again for the comments. We address the raised question in the following. # 1. Algorithm 2 and Algorithm 7 Algorithm 2 provides us a template for designing coreset construction algorithm with small average sensitivity by perturbing the weights (Line 5 - 10). Algorithm 7 applies this idea to Huang and Vishnoi [2020]'s algorithm. Specifically, Lines 6 and 11 describe the perturbations to the weights. # 2. Average sensitivity vs algorithmic stability We first want to remark that average sensitivity does not take the average over the input set, but average stability does (we follow definition 4 from Lei, Y., & Ying, Y. (2020) here). If the average sensitivity is bounded by beta, then the average stability is bounded by beta times the maximum distance between $\theta$'s, which is the algorithm parameter (or the loss difference incurred by them, if the average stability is defined wrt to the loss). As average sensitivity consider the worst case (in terms of input set), we do not believe that the average stability is sufficient to derive our results. In the stochastic setting, it is not clear whether average stability would be sufficient. In our current analysis, we crucially used the fact that TV is bounded (so we can say that the outputs are the same with high probability). For average stability to be sufficient, the loss has to be Lipschitz, which may not be always true (for example when the matrix has a high condition number in linear regression). We are also a bit confused about why TV upper bounds the Wasserstein distance (we believe that this is true if data are assumed to be in a unit ball, but we do not think this is true in the general case). Lei, Y., & Ying, Y. (2020). Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning (pp. 5809-5819). PMLR.
We thank the reviewer again for the detailed comments. We hope our response answered your questions, and we will be more than happy to answer any additional questions.
Sorry for the late response - I would like to thank the authors for their detailed replies. I do not have further questions. I was and still am in favor of acceptance, of course.
Thank you so much for the positive review and review again!
Thanks for the response
I would like to thank the authors for their response. I remain in favor of acceptance of this work.
Decision
Accept (poster)