Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper considers the setting where an algorithm/data structure has to give responses to a sequence of adversarially chosen inputs.
The paper considers tow separate settings:
1. The consider linear regression $min_x \|Ax =b\|_2^2$ where the target $b$ can be updated in $K$ locations at each step. The goal is approximate the squared error.
2. They consider a setting where you have a non-adaptive data structure for a problem. They show that in order to answer $Q$ adversarial queries,  rather than use $Q$ independent copies of the. data structure, one can use privacy amplification techniques to only maintain $\sqrt{Q}$ copies.
strength_and_weaknesses: I am not quite convinced by the first problem. I think the problem of how to not resolve linear regression under updates is natural, but I am not sure why you would only care about approximating the squared error rather computing a near-optimal solution. Typically, the loss is a means to the end of finding a good $x$, not the end in itself.

I found the second result much more interesting and general. The use of differential privacy is nice (and is somewhat reminiscent of the adaptive data analysis paper of Dwork et. al). It gives them  black box results for distance and kernel density estimation, which they are able to improve on in some settings. Similar techniques seem to have been used earlier in work on the streaming model. 
clarity,_quality,_novelty_and_reproducibility: Good. 
summary_of_the_review: I think this paper is nice and ought to be accpted.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper introduces training algorithms that are robust to bounded dynamics in the data, with a focus on label updates. 


----------------------
Update: I thank the authors for their informative feedback. I have updated my overall recommendation but remain unconfident about it.  
strength_and_weaknesses: The work seems theoretically solid. However, it doesn't seem to fit into the representation learning context, especially the robustness questions. First, the models are primarily linear ones and the authors didn't give insight how these might scale to non-linear ones. Second, the perturbation in the target is interesting but the authors didn't explain what kind of applications it may find in reality. The paper seems fairly theoretical and very difficult to follow without the specific background. I'm wondering if the work would fit better in another venue. 
clarity,_quality,_novelty_and_reproducibility: Clarity: being unable to follow all the details, I find the presentation of the paper actually quite clear. 
Quality: I cannot evaluate the quality due to lack of the knowledge of this specific field. 
Reproducibility: it is a purely theoretical work. 
summary_of_the_review: My main concern is that it may not fit into the ICLR context. I'll be happy to change my evaluation if the authors and other reviewers may enlighten me regarding this point.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors investigate the space complexity and amortized round time or query time of the sequential (approximate) query answering problem under adversarial queries. First, they deal with the problem of sequentially answering the least-square objective value with an adversary who modifies the outcome values with L0 restriction. Second, they develop a general framework that can convert an algorithm working with stochastic queries to one for adversarial queries. They demonstrate many applications of their framework, including matrix-vector norm, linear regression, half-space query, point query on turnstile streams, distance estimation, and kernel density estimation. A general idea for dealing with these tasks is to hide the internal state from the adversary by utilizing the differentially private median. 
strength_and_weaknesses: Strength:
- Sequential estimation under adversarial queries is interesting and well-motivated.
- This paper gives novel and significant results for the sequential least-square objective value estimation under L0-restricted adversarial queries.

Weakness:
- The implication of the sequential least-square objective value estimation results is somewhat unclear.
- This paper lacks a detailed comparison with some crucial related works, which makes me unsure about the significance of the results. 
clarity,_quality,_novelty_and_reproducibility: The robustness in estimation is in high demand even for the sequential estimation problem. The sequential estimation problem under adversarial queries is thus well-motivated. For the first problem of the sequential least-square objective value estimation, the authors employ L0 restriction for an adversary. The L0 restriction is a reasonable restriction on the adversary and is motivated to investigate. The algorithm for the first problem builds from a novel combination of the JL sketch technique and differentially private median estimation. The theoretical analyses provide an interesting characterization of the amortized update time and preprocessing time. 

One this unclear to me in the first problem is the implication of Theorem 2.1. The authors state that a naive approach costs $\mathrm{nnz}(\mathbf{A})+\mathrm{poly}(d)$ for the amortized time. On the other hand, the amortized time for the proposed algorithm is $\sqrt{K\mathrm{nnz}(\mathbf{A})}/\epsilon^3$. So, if $\epsilon \le (\sqrt{K\mathrm{nnz}(\mathbf{A})}/(\mathrm{nnz}(\mathbf{A})+\mathrm{poly}(d)))^{1/3}$, is it better to use the naive approach? If so, it is better to clarify such a threshold for $\epsilon$ is meaningfully small. 

I'm currently unsure about the significance of the results for the second problem of the general sequential estimation under adversarial queries. The unclarity comes from a lack of detailed comparison with Beimel et al.'s results. Beimel et al. also develop a general reduction framework for the sequential estimation problem under adversarial queries. The basic approach looks equivalent; they also utilize the differentially private median estimation and amplification via sampling technique to guarantee robustness against malicious queries. Similar theoretical results are presented in Theorem 3.1 in the original paper. Hence, the detailed comparison with Beimel et al.'s results is mandatory for clarifying the significance of this paper's results regarding the general sequential estimation problem. 


Minor comment:
- While the amortized time is $\tilde{O}(1/\epsilon^{2.5})$ in Theorem 1.1, it is $\tilde{O}(1/\epsilon^{3})$ in Theorem 2.1. I guess Theorem 2.1 is correct.   


summary_of_the_review: The sequential estimation problem under adversarial queries is interesting and crucial. The first result for the sequential estimation of the least-square objective value is novel and significant. I'm thus currently recommending acceptance. However, I have some concerns regarding the implication of the first result and the originality of the second result of the general framework for adversarial sequential estimation. I'd like the authors to address such concerns in the rebuttal.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies algorithms that are robust to adversaries of limited power. This is interesting since the input to an algorithm in many situations can change dynamically, either natural or as the consequence of  an attack. The paper considers two such models: in the first one the adversary can only alter a few elements of the input (and this model is applied to linear algebraic algorithms). In the second setting the adversary is allowed a limited number of (adaptive) queries to the algorithm. In the latter setting, an idea from differential privacy is employed to hide the internals of the algorithm to the adversary and thus guarantee robustness. This setting is applied to a sequence of problems.


strength_and_weaknesses: Strengths:
- interesting topic
- well written paper
- neat way of incorporating differential privacy result

Weaknesses:
- no empirical evaluation. It would be interesting to see how the algorithms perform in practice against other algorithms that are not-robust to adversarial intervention.
clarity,_quality,_novelty_and_reproducibility: The paper is clear, interesting and to my understanding novel. There are no experiments so reproducibility is irrelevant.
summary_of_the_review: This is a good paper and I recommend acceptance.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This submission studies algorithms robust to adaptive/adversarial input generated from sources with bounded capabilities.

All the reviewers found the paper interesting and solid. I recommend acceptance.
justification_for_why_not_higher_score: In my view, this is a very technical paper that might be interesting only to a small subset of the community. However, I am fine if the senior AC decides to bump it up.
justification_for_why_not_lower_score: Clear accept.
Decision: Accept: poster