Statistical Collusion by Collectives on Learning Platforms

We thank the reviewer for their time and appreciate their positive feedback on our paper.

We would like to thank the reviewer for their detailed and constructive review, and their overall positive feedback. We also appreciate them pointing out the typos. We will update $n_{est}$ to $n_{estim}$​, add assumption $A_0$ regarding the collective's access to $N$, and include a running example if it is considered helpful. We will also make sure to include details about the relationship between features and labels in the synthetic dataset.

Concerning the synthetic dataset, which has also been mentioned by other reviewers: our paper provides finite sample guarantees for collective action in classification, and the bounds we derive depend on several parameters. The main purpose of our experiments is to illustrate the bounds we obtained and to gain insights into the influence of the various parameters. We considered it more relevant to use a synthetic dataset to better understand the influence of these parameters. For example, we can deliberately manage the label imbalance (see our response to Reviewer CB4v) and clearly demonstrate that the adaptive strategy outperforms the naive strategies in Figure 3, even outperforming the naive strategy based on the second most frequent global label after $y^*$ (see Figure 3 and Table 1). Furthermore, for a fixed $g$, we can investigate how the composition of the training set elements within the signal set impacts the results using a synthetic dataset, but not with a real-world dataset. In ongoing work we will be working with real-world datasets, but for a first study of this methodology we felt that the priority was to understand its properties rather than simply exhibit an application which would give limited insight into whether our conceptual understanding of the parameters is on solid ground.

Experiments for configurations with $\epsilon > 0$

Yes, the lower bounds will become weaker as $\epsilon$ increases.

Lower bound on the success of signal erasing

The lower bounds are trivial (equal to zero) because the estimation terms are too large, as they depend on the cardinality of $\mathcal{X}$. We briefly mentioned this in the appendix (lines 1104-1105) but we can also include it in the main text if it is considered helpful.

Experiments repeated multiple times

We ran the experiments only once. We expect little variance, except for values very close to the steps, which do not affect the overall trend of the curves highlighted in the paper. However, we can still run additional experiments and average the results if deemed helpful.

We thank the reviewer again for their valuable feedback.

We would like to thank the reviewer for their detailed and technical review, which allows for a discussion of some of the paper’s theoretical aspects. We also appreciate their positive feedback and will now address the questions raised.

Better empirical performance than (Hardt et al 2023) in Figure 4 for large number of samples

Our bounds are not only empirically superior but also theoretically better (see Proposition F.2, for example).

Either more experiments on different datasets/settings should be done or adequate theory provided for such staircase-property before such claims could be made

For a finite signal set, we can theoretically prove that our bounds exhibit a staircase shape, unlike Hardt et al., just by using law of total probability and conditioning on the possible values for $g(x)$. We can include a rigorous proof in the paper if it is considered helpful.

Absence of experiments on signal erasure task / dataset not real

We refer to our response to Reviewer HD8o.

Synthetic Dataset with Label Imbalance

The dataset is truly synthetic and we intentionally introduced this imbalance.

Reproducibility

We fixed the random seed for our experiments (see src file).

Justification of Assumptions 1 and 2

The parameters $\eta$ and $\tau$ are very different. While $\eta$ relates to the nature of the base distribution and ensures that the most frequent label is sufficiently separated from the second most frequent one, $\tau$ reflects how similar the probability of a label given $x$ is to its probability given $g(x)$. In other words, $\tau$ captures the extent to which $g$ already influences the platform’s decisions, whereas $\eta$ is a simple assumption about the base distribution, entirely independent of $g$ or any other parameters specific to the collective. Regarding Assumption 2, we refer to our response to Reviewer 6HMD.

Essential References Not Discussed

Indeed, the paper cited by the reviewer is relevant, and we will ensure it is included in the references.

Convex action

As mentioned by the reviewer, convex risk minimization is also an important framework. We believe that gradient-based learning, as outlined by Hardt et al., is also an important framework. While the focus of our paper is only on classification, exploring these setups is an interesting direction for future work. We believe that our setting could be extended to this case even without assuming strong uniform generalization bounds: one can simply estimate gradients directly using samples from the base distribution and the gradient-neutralizing distribution. One additional difficulty is to compute a gradient-neutralizing strategy. Within our setting, the collective does not directly have access to expected gradients but rather to estimations and the collective may only be able to compute an approximate gradient-neutralizing strategy. This would yield additional error terms.

Identify staircases in Figures 1-3

The steps in the staircase are closely spaced, and the bounds are computed only for fixed values of $n$; this is why the staircase resembles a sigmoid curve.

Bound on $\eta$

We do not assume that $\eta < \frac{1}{Card(\tilde{\mathcal{X}})}$. Regarding the second part of the reviewer’s remark: it is possible to redefine $\eta$ to discard features not in $\tilde{\mathcal{X}}_0 \subseteq \tilde{\mathcal{X}}$, where $\tilde{\mathcal{X}}_0$ is a subset of $\tilde{\mathcal{X}}$ such that $\tilde{x} \sim \tilde{\mathcal{D}}$ has a high probability of belonging to $\tilde{\mathcal{X}}_0$. This aligns with the reviewer’s intuition of asking whether a similar definition of $\eta$ in expectation is possible. In this case, we can derive theoretical guarantees by conditioning the success and saying that the success is equal to the same probability conditional on the fact that the feature $g(x)$ is in $\tilde{\mathcal{X}}_0$ times the probability that $g(x)$ is in $\tilde{\mathcal{X}}_0$, plus a term that depends on the probability of $g(x)$ not being in $\tilde{\mathcal{X}}_0$, that we can typically discard.

Issue with the earlier proof of (Hardt et al., 2023)

There was a mistake in algebraic manipulations leading to an erroneous bound. In the current version of Hardt et al., Definition F.3 is used, but the bounds remain suboptimal due to unnecessary inequalities.

We sincerely thank the reviewer for the thorough review and for pointing out typos.

First, we would like to thank the reviewer for their time and their insightful comments. As mentioned, our main contribution is introducing a statistical inference component to the collective action framework, which is crucial in practice, as collectives often seek guarantees about the effectiveness of their strategies. We also appreciate the reviewer’s thoughtful questions and will ensure additional clarifications in the final version to enhance intuition and understanding.

It would be nice if the authors could add some intuitions behind theorem 3.7, especially how it differs from the previous theoretical guarantee (Theorem 3.3).

We agree that a discussion here would indeed help provide the reader with more intuition, particularly in comparison to signal planting (Theorem 3.3). In signal planting, the strategy is simple: flood the platform with label $y^*$. In signal unplanting, an intuitive approach is to change the label by choosing the most probable label $\hat{y}\_\tilde{x}$ after $y^∗$ for every $\tilde{x}$, which is exactly the meaning of equation (3). However, $\hat{y}\_\tilde{x}$ is unknown, so we propose estimating it using a subset of the collective of size $n_{est}​$. This results in a two-step inference method, where we first adaptively estimate the label $\hat{y}\_\tilde{x}$, and then use concentration inequalities that depend on $\hat{y}\_\tilde{x}$. To ensure independence and correctly apply Hoeffding’s inequality, we carefully split the datasets of size $n_{est}​$ and the rest of the collective of size $n - n_{est}$. This is why the estimation term for $\Delta_{\tilde{x}}$ in Theorem 3.7 is $R(n - n_{est})$, rather than $R(n)$ in Theorem 3.3. This directly quantifies the impact of not knowing the optimal label to play by the collective (contrary to signal planting where the optimal label to play is known): the counteracting term in the bound is more important since $R(n - n_{est}) > R(n)$.

1.How should I understand the inequality in section 3.3.1? and 2. Does Theorem 3.7 still hold if we randomly choose a label other than $y^\*$ instead of $\hat{y}\_\tilde{x}$ according to equation (3)?

To build intuition, let’s consider the following simplified case: the signal set $\tilde{\mathcal{X}}$ consists of a single feature, and the label frequencies associated with the training set without the collective are as follows: 100 for $y_0=:y^*$, 70 for $y_1$​, 60 for $y_2$​, and 50 for $y_3$​. In this case, the optimal strategy seems to be estimating the most probable label $\hat{y}$ after $y_0$ (here,$\hat{y} = y_1$​) and flooding the platform with it. However, $\hat{y}$​ is unknown by the collective. The collective could naively flood the platform with either $y_2$​ or $y_3​$ as well. This corresponds to planting the signal with those labels, which is exactly the meaning of the inequality in Section 3.3.1. A more effective approach is to estimate $\hat{y}​$, which we formalize in the paper. Regarding the suggestion of using randomness: while it is possible, we believe it is suboptimal, even compared to naive strategies, which is why we did not study it. To get convinced, assume a collective of size $n=60$. Naively flooding the platform with $y_i$ ($i \in \{1,2,3\}$)​ succeeds since $y_i$​ becomes the most frequent label for $\tilde{x}$. However, choosing a label randomly among those $\neq y^*$ leads to expected frequencies: $y_0: 100$, $y_1: \approx 90 < 100$, $y_2: \approx 80 < 100$, and $y_3: \approx 70 < 100$, resulting in an unsuccessful collective action.

3. In section 3.4 (signal erasing), it seems like the success of the proposed signal erasing procedure relies on the transformation function $g$ to be idempotent. What are some examples of idempotent vs. non-idempotent transformations? How practical is it in real life?

We provide examples of idempotent functions $g$ in lines 311-319. This assumption is generally not restrictive, especially in tabular data or opaque watermarking.

Concerning weaknesses:

The experimental section is a bit weaker since it's a simulated setting

We refer to our response to Reviewer HD8o.

Another weakness is that some theoretical claims rely on particular assumptions or particular signal strategies

We study strategies that are intuitively optimal and provide theoretical guarantees. Establishing a unifying framework for analyzing strategy optimality may be an interesting direction for future work. The guarantees we derive depend on assumptions, such as the idempotency of $g$ for signal erasing (line 1025). We do not claim that this assumption is necessary, but we have not found a way to derive guarantees without it. If helpful, we can clarify why we use this assumption, in contrast to Hardt et al.

We sincerely thank the reviewer for their valuable feedback, which helps improve the paper, and we hope we have addressed their concerns.