Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper argues for a more general view on strategic classification of objects modified by adversaries. In the standard view, the designer of the classifier is assumed to be the leader and the classifier is optimized with respect to a best response form the data generator to its parameters. This paper argues that in some situations, it may be possible and desirable to reverse the roles and force the rational attacker to create objects first and optimize them with respect to the expected best response classifier. The paper shows how different update frequencies of individual players using no regret and gradient descent learning can lead to convergence to the equilibria in either assignment of the roles. Furthermore, the paper shows that for linear and logistic regression, each of the role assignments can be desirable for each of the players depending on parameters, such as the magnitude of the allowed perturbation by the attacker.

main_review: Originality: I agree with the first parts of the paper that claim that most existing work considers the classifier to be the leader in a Stackelberg game and I am not aware of any work that would reverse the roles. The idea to reverse the roles is not entirely intuitive and therefore sufficiently novel. Also, showing (in highly idealized setting) that the equilibria corresponding to the different orders can be induced by the speed of updating is interesting and novel.

Technical Quality: The main statements of the paper intuitively make sense. I did not carefully check the detailed proofs that are provided in a lengthy appendix. The main text is rather formal and reasonably clear, but some things are missing. For example, it makes an assumption that all best responses and equilibria are unique without any justification. Some of the notation is not properly introduced. For example, a crucial parameter “diam()” used in Theorem 3.1 is undefined, I / I_d in section 4 is undefined, ->_p for “convergence in probability” should also be defined more exactly.

Clarity: The main idea of the role reversal is clear. However, it is not enough on its own for a neurips publication and it is not very clear how some parts of the paper support it. The paper would, in my opinion, be substantially clearer if it introduced a comprehensive detailed description of a realistic problem, that would require the kind of analysis the paper promotes.  In the presented formal model, there is no change of data and the only thing evolving in time are the player’s strategies. Assuming rational players, I do not see much reason for having gradual updating on different time scales. In the given example with spam, the spammer would just craft the hardest to detect template and start using it, while the classifier would create the best classifier for it. If the equilibrium is unique as assumed, the spammers would not have any incentive to change their strategies anymore. Since the data do not change and the equilibria are unique, it is not clear why it is useful to analyze the process of adaptation of the classifier on the level of gradient descent. 
If the gradual updating is somehow justified, the deeper, less trivial analysis in the paper is on the more standard form of the classifier in the role of the leader, which is unexpected after the introduction. There, the result in Theorem 3.1. is interesting and non-trivial. On the other hand, the analysis of the equilibrium for the reversed roles basically assumes that the classifier is trained to full convergence, which is much less interesting and novel.

Significance: The paper presents an interesting theoretical idea. However, it does not sufficiently argue for its practical impact. The paper shows some parameter settings, where the players’ payoffs in the different equilibria differ. However, the ability of the attacker needs to be quite extreme (over 1.5 change in data with unit variance (if I interpret the undefined I correctly). A more compelling discussion of practical impact would be necessary to consider the paper significant practically. If we focus on the theory, the paper may inspire future work that will consider the agent modifying the data as the leader.  It sufficiently shows that the case exists, and could potentially have some implications on players strategies, depending on parameters. However, I am not convinced that the paper provides sufficiently novel and interesting tools for deeper analysis of this problem to warrant a publication at NeurIPS.

Summary: This paper presents a very interesting idea of role reversal and argues well for the need to analyse different adaptation speed of the players in adversarial classification. However, I do not think it provides sufficient evidence for its practical impact or sufficiently general, deep and reusable theoretical framework that would make its future analysis substantially simpler.


After the discussion with the authors, they managed to resolve some of my confusions and I was happy to increase my score. While uniqueness would be a problem in non-linear classification or when assuming mixed strategies, I am ok with it in case of linear classifiers and pure strategies. We have also resolved the problem of changing data. I hope a future version of the paper will be much clearer about which agent has access to which information, but I think my main concern is resolved by the realisation that z is likely only a sample of the data that can be different in each round, even though it comes form the same static distribution, generally unknown to the players.

The concern that was not fully resolved is that the more interesting results with regret minimisation are for the more standard setup of the classifier as the leader and the reversed theorem essentially assumes a best-responding opponent, which is much less novel.
limitations_and_societal_impact: The authors should analyse more carefully the limitations of their formal model (i.e., the data not changing) and the empirical results achieved (i.e., how realistic the parameters that lead to the difference are). For societal impact, the authors do not discuss it, however, I do not consider the potential negative impact of this work to be substantially larger than in case of any other work on adversarial classification.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies a variant of strategic classification where there is not instantaneous interaction between the learner and the agents, but rather, there is a “slower” and a “faster” player (i.e., the whole interaction is governed by the frequencies according to which the learner and the agents update their decisions). This variant is closer to real-life settings, where for example the learner may have much more computational power compared to the agents. In their model, the agents are assumed to update their decisions at a fixed rate, and the learner gets to decide whether to be proactive (i.e., update his decisions slower than the agents) or reactive (i.e., update his decisions faster). After the learner announces the deployed model, the agents are broadly “rational”; to be more specific, they decide their reports based on no-regret algorithms (rather than the standard instantaneous best-response in prior work). The difference in timescales results in fact in a change of who the “leader” and who the “follower” is in the setting. The question that the paper addresses is what changes in terms of loss for the learner and the agents if there exists this timescale difference and whether there are settings where it is best for both the agents and the learner to always have one of the two.

The paper has two main results. First, it shows that if the learner is proactive (resp. reactive), then the learning dynamics of the system converge to the learner’s equilibrium (resp. agents’ equilibrium). Second, it shows that if the learner runs linear or logistic regression and the agents aim to maximize their predicted score, it is preferred by both the learner and the agents that the agents “lead” (i.e., that the learner is reactive). In terms of techniques, the paper uses variants of standard tools in Bandit Convex Optimization (BCO), assuming that everything is smooth enough (i.e., convex, smooth, Lipschitz).
main_review: =====  Post Rebuttal  =====

I would like to thank the authors for addressing my comments and participating in the discussion. Please include the BCO discussion in a revision of the paper, together with the other comments you acknowledged. I'm increasing my score to a "weak accept" after our discussion where you stated that the surprising result on the order of play seems to also hold for more "adversarially" produced datapoints.

======================

Evaluation.
I think the paper’s strong trait is the observation of the different timescales, which is definitely novel and closer to reality than the prior models. The technical part of the paper is similar to prior work and in and of itself makes some assumptions on the form of the losses, the risks and the behavior of the agents (I do understand that the paper of [Dong et al., EC18] makes the same assumptions and proves the conditions under which they hold). The reason for my weak reject is that I think that the bound that you should have used for BCO part is the bound of [Bubeck et al., STOC17] and that the paper will benefit from a more clear writeup (I have included extended comments below).

Weaknesses. 

-- The technical part of the paper is similar to prior work. And there is a second layer to that. The paper of [Dong et al., EC18] adapts the algorithm of [Flaxman et al., SODA05], which was indeed the first to achieve no regret in BCO, but ever since there have been much better algorithms. This is also acknowledged by [Dong et al., EC18]. I think that the paper should try to adapt the algorithm of [Bubeck et al., STOC17] which achieves O(poly(d) \sqrt{T}) regret, instead of the O(T^{¾}) one. By the way, I do understand the higher dependence in the dimension, I am just focused on dropping the dependence in T. If this is not possible, is there a fundamental barrier?

-- The two examples showcasing the counterintuitive preferred order of play are nice, but I think it would be more meaningful to consider more “adversarial” settings similar to prior work. Or, what happens if you have separable data (see the paper by [Ahmadi et al., EC21])? Are there any minimal conditions for the data generating process and the risk functions in order to get to the same conclusion that the agents’ leading is preferable for both?

-- I think that the paper could use some clarifications in the write-up. Examples: (and please correct me if I’m wrong in any of the following)

* I believe that you need to assume that the learner knows the agents’ frequencies in order to decide to be proactive/reactive. Why is it OK to assume such knowledge in real-life settings? 
* You assume that the label/score y remains the same even after manipulation. Please state that clearly, since there are a lot of works recently where this is not the case. 
* In 2.2 some details are loosely defined; for example, the “most rational decision” in Line 220 assumes a risk-averse, expected utility maximizer agent, right? Also, the no-regret behavior is not identical to the \mu_{BR}. This is indeed clarified in the first paragraph of page 6, but I was confused reading lines 217 -- 233 and then the definition of the no-regret behavior. 
* What if for the faster player there is an “idle” round? In general, do the rounds for the updates need to “align”? I.e., the slow player plays once every 3 plays for the fast player. 
* It is said early in the paper that the agents’ leading is a “preferred” order of play; please specify earlier that this preference is defined wrt to the accuracy loss for the learner, the loss of the agents, and their manipulation cost. Alternatively, you can formally define welfare in the beginning and argue wrt to it.

Strengths. 

-- The model is very interesting, novel, and indeed it models much better the interactions in strategic classification settings. Frankly, the idea of studying different timescales for the learner and the agents is one of the missing pieces in the strategic classification literature and the main selling point of the paper. 

-- The observation that there are settings where *both* the agents and the learner prefer that the agents’ lead is indeed surprising and counterintuitive. The paper does a good job of explaining also the relationship with zero-sum games.

Additional comments.

-- Missing related works: [Braverman & Garg, FORC20], [Ghalme et al., ICML21], [Levanon & Rosenfeld, ICML21], [Jagadeesan et al., ICML21], [Ahmadi et al., EC21], [Bechavod et al., arXiv21]

-- Line 180: what is m? Why is this not equal to d?

-- Line 315: what is D_{t+1}? 

limitations_and_societal_impact: The limitations of the work are adequately addressed in Section 5. I also particularly enjoyed their observation about the meta-game that might be induced.

I think the potentially negative impact of the work should have been addressed, too. For example, you could include a paragraph citing some of the papers that have proved how strategic classification makes the disadvantaged groups worse off.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Almost all of the literature on strategic classification is situated in a Stackelberg game setting in which the decision-maker leads, committing to a model, after which agents follow, best-responding to the model. The core insight of this work is that in some real life situations, the decision-maker is able to adjust their model more rapidly than agents are able to adjust their strategic adaptation, leading to a reversal of the traditional order of play: the agents become the leader, and the decision-maker becomes the follower. The authors compare the dynamics of these "proactive" and "reactive" regimes, which differ in the comparative frequency of the two parties' updates, under the weak assumption that agents are no-regret learners. In particular they give conditions under which the learning dynamics converge to Stackelberg equilibria. Finally, they show that in two simple examples (linear regression and logistic regression with bounded actions of linear cost), the equilibrium in which the agents lead is at least as preferable (and sometimes more preferable) for _both_ agents.
main_review: This paper makes several contributions:
1) Pointing out that the order of play in strategic classification can be reversed
2) ...and that differences of frequency of updates can determine the order of play
3) Showing that both players might prefer the order in which the agents lead
4) Performing analyses that merely assume agents achieve vanishing regret in comparison to best-response, rather than the traditional stronger assumption that agents instantly play the optimal move

A very relevant recent paper seems to have been missed by the authors: ["Scoring Strategic Agents"](https://arxiv.org/abs/1909.01888) by Ian Ball. In this work, Ball studies strategic regression under both orders of play: decision-maker first, and agents first. These correspond to the classic economic settings of _screening_ and _signaling_ respectively. Thus, the current paper is not in fact the first to vary the order of play in the literature on strategic classification, so contribution #1 is not wholly novel.

That notwithstanding, I am recommending acceptance because contributions #2,3,4 are novel as far as I know, and are substantive and interesting. #2 and #3 are neat observations that are presented convincingly. The authors make a good case that the agents-first model is a better fit for many real-life settings than the decision-maker-first model. (The main body of the paper as a whole is admirably well-written). Regarding #4, I appreciate the no-regret model of agent behavior; I would like to see more strategic classification works use this rather than assume agents can instantly best-respond. Moreover, order of play is acutely underdiscussed in the literature even if it has already been brought up once before, and the Ball paper is framed as a work of economics rather than computer science.

One thing that confused me: the authors use a parameter $\mu$ to denote "the agents' action." But of course in many cases different agents take different actions. In the logistic regression example, $\mu$ refers to the one action all the true-negative agents take (the true-positives don't take any action). So I gather that $\mu$ is meant to parameterize the actions collectively taken by the full distribution of agents? It would be nice to have clarity about this from the authors.

I have only given the proofs a cursory skim, not checked them for correctness.
limitations_and_societal_impact: One unaddressed limitation of the work is the assumption that agents act as a unit, maximizing their aggregate utility as a group. I think this is an understandable assumption for reasons of tractability and space. Indeed, when the decision-maker moves first, there is no difference between agents acting in their own self-interest versus in their collective self-interest, since each agent's utility is unaffected by the actions of others. But when the agents move first, the action of one agent can affect the model deployed by the decision-maker and thus the utility of another agent, and so the assumption matters and is in my opinion unrealistic (hence the common use of perfect Bayesian equilibria in the signaling literature).
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors study an extension of strategic classification in which they consider how the time it takes the model designer and agents to react to one another effects the dynamics of strategic classification. Differences in the updating frequencies of the two parties can essentially switch which party is the leader (typically the model designer is the leader).  Different equilibria can arise depending on which party has the faster update frequency. Convergence to these equilibria is characterized in the case of agents leading and also the model designer leading. Additionally, cases in which having the agents be the leaders is desirable for both parties are outlined.
main_review: Strengths:

— The paper examines an important extension of the traditional strategic classification model. Namely consideration of response times, for both the model designer and the agents, adds a number of interesting insights.

— Significant contributions are made in the from of results pertaining to this model extension. Specifically, the authors quantify convergence of strategies for the case of both a reactive and proactive model designer, as well as providing examples in which the latter is preferable to both parties.

— The authors’ assumptions allow their results to be applicable in a wide range of settings.

— It is both counter intuitive and interesting that situations can arise in which both the model designer and the agents prefer the agents to lead. Aside from being generally interesting, this result implies that the strand strategic classification model (model designer leading) can lead to less desirable outcomes and thus motivates the need to consider reactive model design and potential tool for robustness. 

— The paper is well written, the contributions are clearly outlined, and helpful intuition regarding results is provided.


Weaknesses:

— The informal presentation of Theorem 1.2 seems to overstate the actual result (which I believe is Proposition 4.1 and 4.2, although there appears to be no explicit mention of the formal version of 1.2), in that the theorem insinuates both parties prefer agents to lead when linear or logistic regression models are deployed. However, Section 4 appears to only provide sufficient conditions on the distribution of true features for this result to hold, rather than showing that it holds In general. 

— When looking at agents as potentially spending large periods of time to manipulate their features, it could be the case that this process also manipulates their true label, e.g. spending a year doing actions to increase one’s credit score may inadvertently increase one’s true credit-worthiness. Without accounting for this potential shift in labels, the the utility of the model designer may be incorrectly modeled. 

— Additionally if the update frequencies are low enough, such as some type of annual application system, we may be more interested in considering utility within some small number of iterations, rather than quantifying convergence as the number of iterations approach infinity. This is somewhat handled with several of the inequalities presented in section 3, but having a better characterization of utility with respect to each iteration would be helpful since the setting this paper studies is motivated by slow reacting agents.
limitations_and_societal_impact: N/A
review_title: null

Meta-review: While the scores appear marginal, I still recommend this paper for acceptance.  The authors responded well to some points and some issues raised were found not to be much of a problem.  It is clear that some work is needed on the writeup in line with the reviewers' comments (e.g., contrasting with the Ball paper), but it is very reasonable to assume this can be done before the camera ready.

While we certainly can't fault the authors for not having a high enough reference count, there are a few other things that could be expanded.  For example, there is a paragraph on learning in Stackelberg games, but that literature (not necessarily restricted to the classification context) goes back to 2009 if not further, and not just for zero-sum games.  This seems worth discussing.  There is quite a bit of additional recent work on learning in non-zero-sum strategic classification settings, including relationships to mechanism design (which is itself a Stackelberg model), as well; see e.g. "Incentive-Aware PAC Learning" and other work cited therein.  To my knowledge, none of this makes the authors' work less valuable -- if anything, it makes it more so.  Finally, there is work in the economics literature on justifying Stackelberg models/outcomes through different degrees of patience between the players, e.g., "Reputation and Dynamic Stackelberg Leadership in Infinitely Repeated Games" -- it is not quite clear to me what the relationship is to update frequencies, but perhaps something interesting can be said.
Decision: Accept (Poster)