Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classification

Summary

This paper studies online strategic classification from a combinatorial perspective. The paper defines a new combinatorial dimension called the Strategic Littlestone dimension that jointly captures the complexity of the hypothesis class and the manipulation graph. They show that the Strategic Littlestone dimension exactly quantifies the minimax number of mistakes made by deterministic learners in the realize setting. The paper also provides improved upper bounds in the agnostic setting by modifying the classic agnostic-to-realizable reduction to handle the fact that the learner does not observe true features. Finally, the paper considers the case where the manipulation graph is not known to the learner but belongs to a family of graphs which is known to the learner. They provide bounds on the minimax value in both the realizable and agnostic settings in this case.

Strengths

- The paper is well-written and easy to follow - The problem setting is well-motivated - The technical contributions are novel and improve upon existing results. In particular, I found the proof of the lowerbound in terms of the strategic Littlestone dimension to be nice.

Weaknesses

- Lack of lower bounds. Apart from the known manipulation graph, realizable setting (Theorem 3.2), lower bounds on the minimax regret in terms of the strategic Littlestone dimension are not provided. - Lack of results for randomized learners in the realizable setting. While the authors do discuss randomized learnability, and its difficulty in the discussion section, I find it a bit unsatisfying. Without lower bounds for randomized learners, it is not clear whether the strategic Littlestone dimension characterizes realizable strategic online learnability in full generality. Meaning, as far as I can tell, there could be a separation between deterministic and randomized realizable learnability for strategic online classification (correct me if I'm wrong here). - Deterministic learners in the agnostic setting. It is well known that in order to achieve sub linear regret in the traditional online classification setting, one needs randomization in the agnostic setting. Thus, it is a bit strange to me that the authors study/construct deterministic learners for strategic online classification in the agnostic setting. This also leaves open the question of whether the strategic Littlestone dimension characterizes agnostic online learnability. - The two points above bring into question the utility/usefulness of the strategic Littlestone dimension. Compared to say the Littlestone dimension, which not only qualitatively characterizes online learnability in the realizable and agnostic settings but also exactly quantifies the minimax rates, the same (at least as of right now), cannot be said of the strategic Littlestone dimension. As far as I can tell, the strategic Littletone dimension only characterizes deterministic realizable learnability. - Lack of intuition behind the dimension. In traditional online classification, the intuition behind needing shattered Littlestone trees is very easy from a lower bound perspective - we just need to tell the adversary what to play for every move of the learner. However, this sort of logic does not seem to work for strategic Littlestone trees due to the need for reverse engineering. Unfortunately, I did not fully understand the intuition behind the strategic Littlestone tree from the proof sketch of the lower bound in the main text. I had to read the full proof in the Appendix to fully understanding the structure of the strategic Littlestone tree. I think the paper can benefit from a more detailed discussion about the differences between shattered Littlestone trees and shattered strategic Littlestone trees and how the adversary should use strategic Littlestone trees to construct hard streams. In addition, I think to improve intuition, it would be nice to buff up the proof sketch of Theorem 3.2, and even better to include the full proof in the main text. - Minor: there is a typo in the second bullet point in Def. 3.1. I think it should be $N_G^{-}$.

Questions

- In the case of unknown manipulations graphs, is the finiteness of the graph class necessary? Is there a joint dimension of the graph class and the hypothesis class that captures learnability and the minimax rates in this setting? - Your definition of realizability states that if $(x_1, y_1), ..., (x_T, y_T)$ is the sequence of agents chosen by the adversary, there is a hypothesis $h \in H$ such that $h(br_{G, h}(x_t)) = y_t$. That is, the label $y_t$ agrees with the value of $h$ on the agents best-response to $x_t$ w.r.t $h$. Is this the most natural definition of realizability? What about simply requiring that $h(x_t) = y_t$ for all $t \in [T]$. Then, perhaps the fact that the learner observes $v_t$ instead of $x_t$ but still needs to correctly predict $y_t$ can be viewed as the learner observing noisy features? It would be nice if you can comment about why you choose this particular notion of regret and realizability. - Can you comment about any known separations between deterministic and randomized learnability for strategic online classification in the realizable setting?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

No limitations.

Summary

This paper studies an adversarial online setting where the agents can manipulate their feature vector $x_t$ to some feature vector $x'_t$ given a graph of manipulation rules $G$. The learner observes only $x'_t$ and knows in advance $G$. The usual goal is to obtain sublinear regret, with respect to some hypothesis class. In the realizable setting, this is equivalent to minimizing the number of mistakes, also known as the "mistake bound model". When $G$ is "empty", meaning there are no edges, we get the standard online model. The main contributions are as follows: In the realizable setting, the authors define a Littlestone tree that incorporates the manipulations and defines a notion of the Littlestone dimension for these trees. Extending to the agnostic setting, the authors use a known technique for constructing a finite "online cover" of the hypothesis class, and then apply an algorithm for the finite case (version of multiplicative weights update). Moreover, an extended model is introduced, where there is a finite set of manipulation graphs from which a graph is chosen. When all agents use the same graph from this set this is called the realizable case otherwise it is an agnostic setting.

Strengths

The results in this paper improve upon previous papers that study this question. The techniques are clear, and the proofs are correct (as far as I checked).

Weaknesses

My main concern about the paper is the lack of technical novelty, ideas from standard online learning translate pretty smoothly to the strategic online learning setting. The definition of the Littlestone tree is straightforward, taking the "strategic loss" into account. Indeed, the upper and lower bound proofs are very similar to those of the standard Littlestone dimension and the SOA algorithm. The ideas in the agnostic setting are also quite standard: the agnostic online learning technique of constructing a finite "online cover" for the class (by Ben-David et al.) and using a version of multiplicative weights on the finite class (by Ahmadi et al.). What is the technical contribution of this paper? The writing of the paper could be improved. I understand why the proofs should go through, but some definitions are really confusing. See the next section.

Questions

There are many parts of the paper where the writing/definitions are confusing. Paragraph on the manipulation rule: $h$ denotes the classifier or the loss function? Why does it make sense to define the best response on points where $h$ returns $1$? I don't see how it compiles if it's not the loss function. It's not clear if it is consistent with lines 230-235: how do you define false positive and false negative? with respect to $h$ or the loss of $h$? Line 71 ״under the respective particular parametrization״ what does it mean? I understand what the line afterward means, but line 71 is not clear to me. Lines 94-95: "First, to construct the set of representative challenges". Is it a typo? Minor: Line 34: "decision maker has little or no prior knowledge about the population being classified", this is also the case where the learner has no prior knowledge of the distribution. Sometimes the learner is also referred to as the decision maker (mostly in the intro), it's worth making it clear.

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

The limitations are addressed properly.

Summary

The authors continue the study of strategic classification in the online setting, where an agent can manipulate the instance features to potentially force a positive prediction (governed by a manipulation graph). In the *realizable* case, the authors provide a strategic variant of the Littlestone dimension and the SOA algorithm yielding the exact instance-dependent mistake rate. This improves upon degree-dependent mistake bounds of previous work. They also consider two individual additional directions: the agnostic case and the case when the manipulation graph is unknown. In the first they improve upon existing regret bounds, while in the latter they state novel upper bounds almost matching existing lower bounds.

Strengths

Well written, interesting setting, and natural continuation ob previous work. Tight characterization of the realizable setting. --- rebuttal --- updated from 6 to 7

Weaknesses

Strength of the agnostic result is a bit unclear / open (see questions / limitations below).

Questions

How does Thm 4.1. (the agnostic regret bound) relate to Prop. 30 in Cohen et al. [2024]? Moreover, are there somewhat tight (say up to log factors) lower bounds on the agnostic regret bound? In particular is the $\mathcal{O}(\Delta\cdot\mathrm{SLdim})$ term necessary in the upper bound (Thm 4.1)? (From your remark I understood that only $\Delta\cdot\mathrm{OPT}$ and $\mathrm{SLdim}$ are known lower bounds). Is the assumption that $X$ is discrete a strong one/necessary? We can just model the "manipulation graph" on an arbitrary domain $X$ as a function $f:X\to P(X)$, where $f(x)$ is the set of allowed manipulations of $x$. Are there any difficulties generalizing here? Is a "symmetric" setting possible where the agent can (adversarially) modify $x$ to $v\in N[x]$ no matter the label $h(x)$?. The motivation could be that some agents want to be strategically classified as $-1$ while others as $1$.

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

2

Limitations

The achieved agnostic regret bound is not compared to the agnostic one in Cohen et al. [2024, Prop 30], or perhaps I missed it, see question above. Please clarify as this would help to judge the novelty and strength of the result.

Summary

The paper tackles online binary classification where agents manipulate observable features for positive outcomes. It introduces the Strategic Littlestone Dimension (SLD), a new measure capturing the complexity of the hypothesis class and manipulation graph, demonstrating its role in achieving optimal mistake bounds for deterministic algorithms in the realizable setting. It also improves regret bounds in the agnostic setting by refining agnostic-to-realizable reductions and addressing unobserved original features. Additionally, it relaxes the assumption of a known manipulation graph, deriving regret bounds for scenarios with imperfect graph knowledge in both realizable and agnostic settings.

Strengths

The problem is well-motivated and interesting. The paper is also well-structured. The result based on the notion of the Strategic Littlestone Dimension is tight, with matched lower and upper bounds. Although I did not check the proof, the results of this paper appear to be correct.

Weaknesses

My main concern is twofold: 1. The paper primarily concerns deterministic learning algorithms, while most robust algorithms dealing with adversaries are stochastic, which greatly limits the practical relevance of the paper. 2. The computational complexity of Algorithm 1 is not clear. Line 3 of Algorithm 1 looks computationally expensive. Can authors comment on the computational complexity of the algorithm?

Questions

See weaknesses.

Rating

5

Confidence

2

Soundness

2

Presentation

2

Contribution

3

Limitations

The authors did discuss the limitations of their work.

Summary

This paper considers the problem of online binary classification when each data point can strategically manipulate its features in a discrete way which is captured by a manipulation graph. Protocol and regret: In each round, the learner picks a deterministic classifier $h_t$, and then the data point $(x_t,y_t)$ arrives, and manipulates its feature according to graph $G$ from $x_t$ to $v_t$. The learner receives only $v_t$ and incurs loss $\mathbb{1}[h_t(v_t) \neq y_t]$. The regret is measured with respect to the best fixed $h \in \mathcal{H}$. **contributions** 1. They introduced an elegant notion of Strategic Littlestone Dimension $\mathrm{SLdim}(\mathcal{H}, G)$, which is based on hypothesis class $\mathcal{H}$ and manipulation graph $G$ 2. They showed that $\mathrm{SLdim}(\mathcal{H}, G)$ fully characterizes the optimal mistake bound for a realizable case, by showing a lower bound on the mistake using a strategic counterpart of shattering tree and an upper bound using a strategic version of SOA. (Note: The realizable case here means there exists some $h \in \mathcal{H}$ with no mistakes on the manipulated data. so $h$ does not necessarily need to correctly classify the actual data.) 3. They extended their results for the agnostic case and showed an improved upper bound compared to previous works. They used the idea of approximating the whole class $\mathcal{H}$ using a finite set of representative experts. (Their benchmark is $\Delta_G^+ \cdot OPT$, where $OPT$ is the error of the best hypothesis and $\Delta_G^+$ is maximum out-degree of graph $G$) 4. Finally, they designed algorithms with regret upper bound for the setting where the manipulation graph is unknown to the learner. They consider two cases: (i) all data points use the same unknown manipulation graph from a set of graphs, (ii) each data point uses a separate manipulation graph (case (ii) better captures those real-world applications in which different data points might have different capabilities for manipulation.)

Strengths

This is a very strong paper - Wring is clear easy to follow and well cited. Math notations and technical proofs are also clean and clear. - Significance: the notion of strategic Littlestone dimension: This is a very valuable extension of the Littlestone dimension which characterizes the optimal mistake-bound --> it improves our understanding of the complexity of online binary classification with the presence of strategic behavior - Extension for unknown manipulation graph is valuable and I suspect further research by a broad range of researchers in that line - Some of the previous results relied on knowledge about both pre-manipulation data and post-manipulation data (e.g. [Cohen et al. 2024]) but this paper uses only post-manipulation data - A detailed comparison with previous works in the appendix for the realizable case (I didn't closely check all the details)

Weaknesses

I don't find any major weakness at all.

Questions

1. In line 101, you mentioned that, your approach yields an improved bound for the agnostic setting. Can you please provide more details about this improvement? I believe you are comparing the upper bound in Theorem 4.1. with an upper bound from previous work. 2. In your setting, you assumed that each strategic data point only gets manipulated for a positive classification and if no manipulation leads to a positive classification, then the data point remains unchanged. Is this a necessary assumption for your results? In other words, I was wondering, do you anticipate that your result can be easily extended to the setting where all data points (even those without a chance of getting positive classification) have the potential to be manipulated?

Rating

8

Confidence

3

Soundness

4

Presentation

4

Contribution

4

Limitations

As mentioned by the authors in the checklist, this paper is theoretical with no direct implications. I completely agree with this. However, I want to note that the motivation for strategic classification comes from real-world problems. I think the progress toward this direction by theoretical researchers and practitioners can only be beneficial for society. This paper improves our theoretical understanding of the complexity of this problem in a somewhat stylized case. I can think of only one possible potential limitation (in a very high-level sense). Suppose a practitioner decided to use manipulation robust learning algorithms in their specific application. They need to model a set of manipulation graphs $\mathcal{G}$. If due to inaccuracy in the modelling by the practitioner, $\mathcal{G}$ only captures the certain type of manipulations done by group $A$ and does not capture the type of manipulations done by group $B$, then the resulting learning algorithm will be only robust with respect to a certain type of manipulation from group $A$. Therefore, group $B$ **might** have gained some unfair advantages. Hence, it is important to model the manipulation graph set $\mathcal{G}$ accurately.

Raising my score

Thanks for your response. I believe the contribution is sufficient for acceptance. Please make the relevant changes in the presentation so it will be easier to understand the main definitions.