PaperlayerView exact revision on arXiv

Source-linked AI summary

Information Design Against Gaming and Learning Adversaries

Madhava Gaikwad

arXiv:2609.31643v1cs.LGcs.AIcs.CRcs.GT

TL;DR

The paper asks how a classifier operator should choose abstentions when adversaries may either game a known boundary or learn an unknown classifier from responses. It analyzes coarse and boundary-localizing defenses and their trade-offs. At unfavorable distributions, coarse extraction costs a factor of 1/ε more queries, while the rates match up to constants for favorable pairs such as linear classifiers under log-concave µ.

  • Problem

    The principal must choose abstentions under a budget when facing gaming adversaries who know the classifier and learning adversaries who seek to reconstruct it.

    Source: §1 · p. 2

  • Method

    The paper analyzes coarse and boundary-localizing response rules for classifiers of VC dimension d, comparing their learning and gaming guarantees and convex combinations.

    Source: §1 · pp. 3–4

  • Results

    At θB,µ(ε) = Θ(1/ε), coarse abstention costs a factor of 1/ε more queries than boundary-localizing abstention, while favorable pairs such as linear classifiers under log-concave µ have rates matching up to constants.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The two extreme rules are Blackwell-incomparable, and convex combinations trade one adversarial weakness for the other.

    Source: §1 · p. 4

    The boundary-localizing rate requires Assumption 6, which fails for RBF networks and unions of unboundedly many intervals, leaving the right rate for those classes unknown.

    Source: §7 · p. 17

Abstract

from arXiv · show

A principal who deploys a binary classifier with an abstention option must decide which queries the mechanism abstains on. The right choice depends on the adversary. A gaming adversary already knows the classifier and tries to manipulate features across the boundary, so the principal does best by abstaining on queries close to that boundary. The same boundary-localizing rule is the worst possible choice against a learning adversary who does not know the classifier: each abstention now tells the adversary that the boundary is nearby, which is enough to drive a binary search. We analyze this tension. The two natural defenses, abstaining at a fixed rate and abstaining near the boundary, are Blackwell-incomparable: neither can be simulated by post-processing the other's responses. The number of queries needed to reconstruct the boundary to error $\eps$ is $\tilde\Theta(d/\eps)$ under the first defense and $\Theta(d \log(1/\eps))$ under the second, where $d$ is the VC dimension of the classifier family and $\tilde\Theta$ suppresses factors polylogarithmic in $d$ and $1/\eps$. The first rate is a worst case over query distributions; no reconstruction algorithm can close the gap at the distributions that attain it. We characterize the Pareto frontier between the two defense objectives, and confirm both rates on seven binary-classification tasks spanning tabular, image, and language-model-feature inputs: label-plus-counterfactual access extracts the boundary with up to $200\times$ fewer queries than a published label-only baseline.

1 Introduction

The paper studies how a classifier operator should allocate abstentions when facing adversaries who either know the classifier and game its boundary or try to learn it from responses. It compares coarse and boundary-localizing rules, their query costs, and the trade-off between defending against the two adversary types.

1 Introduction

  • The two adversary types create a design conflict: gaming adversaries know the classifier and seek accepted queries near its boundary, while learning adversaries query responses to reconstruct it.The principal commits to one abstention rule within a budget.Source: §1 · p. 2
  • For a learning adversary, a boundary-localizing abstention signals that the boundary is nearby and can drive binary search, whereas coarse abstention does not encode boundary proximity.In the one-dimensional example, boundary localization takes O(log(1/ε)) queries, while sampling under coarse abstention takes on the order of 1/ε queries.Source: §1 · p. 3
  • The framework evaluates ε-learning under a fixed query distribution µ and an abstention budget, with VC dimension d and query complexity L(E; ε) as key quantities.The paper generalizes the two example rules as Ecoarse and Eδloc and studies their convex combinations.Source: §1 · p. 3
  • At worst-case disagreement coefficient θB,µ(ε) = Θ(1/ε), coarse abstention costs a factor of 1/ε more queries than boundary-localizing abstention; for favorable pairs such as linear classifiers under log-concave µ, the rates match up to constants.The localizing rate requires a mild geometric regularity condition on the classifier family.Source: §1 · pp. 3–4
  • The coarse and boundary-localizing experiments are Blackwell-incomparable, and convex combinations trace a Pareto frontier between extraction and gaming objectives.The paper also bounds the welfare cost of robustness to both adversaries.Source: §1 · p. 4
  • Boundary-localizing abstention protects against gaming by blocking accepts near the boundary, while coarse abstention lets 70% of near-boundary queries through.Both rules have average abstention rate 0.3 in the worked example.Source: §1 · pp. 2–4

2 Related Work

The paper connects its abstention design problem to strategic classification, model extraction, active learning, selective classification, and information design. It distinguishes its focus on learning adversaries and query complexity from adjacent work on gaming, post-manipulation loss, and accuracy-oriented rejection.

Strategic classification and abstention as a defense

  • Unlike strategic-classification work on known mechanisms and agent behavior, this paper designs the information environment; Alkarmi et al. study abstention against an adversary who already knows the classifier, with rates for post-manipulation loss rather than query complexity.Reject-option classification studies abstention from an accuracy perspective.Source: §2 · p. 4

Model extraction and decision-based attacks

  • Model-extraction work reconstructs classifiers from queries, while decision-based attacks use hard-label feedback and boundary-localizing feedback supplies more information, enabling the exponential improvement in Theorem 7.Counterfactual explanations [1] have been observed to accelerate extraction; Theorem 7 gives an information-theoretic explanation for that pattern.Source: §2 · pp. 4–5

Active learning and selective classification

  • The paper uses the disagreement-coefficient framework from active learning and relates principal-chosen abstention to learner-chosen abstention by Zhu and Nowak.Its abstain signal is an idealization of confidence thresholds or trained rejection heads.Source: §2 · p. 5

Information design

  • The paper adapts information design by giving the receiver inferential utility rather than the action-payoff utilities standard in persuasion.It connects this framing to active-learning rates.Source: §2 · p. 5

3 Model

The model treats abstention as the principal’s design lever: the principal commits to a truthful-response experiment under an abstention budget, while receivers adaptively query and seek either to learn the classifier or game it.

3 Model

  • The principal chooses a label-truthful experiment mapping each query-classifier pair to a signal, with abstention as the design lever and a budget measured under μ.Accept and reject signals cannot contradict the classifier; the abstention budget is a cap on the marginal abstain probability under μ.Source: §3 · pp. 5–6
  • Coarse abstention erases labels independently, whereas boundary-localizing abstention uses a calibrated distance threshold; mixtures of the two form a one-parameter family.The coarse rule abstains independently with probability ᾱ; the localizing rule abstains within distance δ, calibrated to the budget under μ and the prior ν.Source: §3 · p. 6
  • Learning receivers minimize classification error under μ, while gaming receivers know the classifier and seek an accepted query within a manipulation distance of its boundary.Learning is defined by error at most ε with probability at least 2/3; gaming utility is the indicator of obtaining at least one qualifying accept.Source: §3 · p. 7
  • The distribution μ measures learning error and budget use, but does not restrict receiver queries, which may concentrate in regions of vanishing μ-mass.Consequently, the abstention frequency experienced by an adversary may exceed the budget, which binds on benign μ-traffic.Source: §3 · pp. 6–7
  • The disagreement coefficient governs the coarse regime, while boundary-localizing abstention supplies distance-to-boundary information and invokes geometric complexity.Under coarse abstention the labels act as random erasures; at the localizing extreme the abstention signal acts as side information about distance to the boundary.Source: §3 · pp. 7–8

4 Characterization

The characterization compares coarse and boundary-localizing experiments, which are Blackwell-incomparable and require different learning strategies. Their query guarantees differ by regime: coarse abstention has a worst-case lower bound depending on the disagreement coefficient, while localization achieves Θ(d log(1/ε)) under stated conditions.

4 Characterization

  • Coarse abstention yields randomly erased labels for active learning, while localization uses abstentions as proximity witnesses in coordinate-wise binary search.The localizing rate requires boundary regularity, and the threshold must satisfy δ=O(ε).Source: §4 · p. 8, §4.3 · p. 11

4.1 The Two Extremes Are Blackwell-Incomparable

  • For abstention budgets ᾱ∈(0,1/2), neither extremal experiment can be simulated by post-processing the other’s responses.The proof rules out a signal-only Markov kernel in either direction.Source: §4.1 · p. 8

4.2 Rate at the Coarse Extreme

  • The coarse lower bound uses a shattered set weighted Θ(ε/d), making misclassification of a constant fraction of its points exceed the error budget.The total mass on those points is chosen as a sufficiently large constant multiple of ε.Source: §4.2 · pp. 9–10
  • In the worst case, coarse abstention requires at least tilde Ω(d log(1/ε)/((1−ᾱ)ε)) queries; favorable classes with θ=O(1) have Θ(d log(1/ε)/(1−ᾱ)) complexity.For linear classifiers under log-concave μ, the cited passage gives θ=O(1).Source: §4.2 · pp. 10–11

4.3 Rate at the Boundary-Localizing Extreme

  • Θ(d log(1/ε)) queries suffice and are necessary under boundary regularity and δ=O(ε), independently of the abstention budget.The upper bound uses coordinate-wise binary search; the lower bound counts information in ternary responses.Source: §4.3 · pp. 11–12

5 Divergence and the Pareto Frontier

The two extreme abstention rules produce sharply different outcomes for gaming and learning adversaries, and mixtures trade off those objectives. The paper characterizes the frontier within this mixture family, including where its learner-cost regimes change.

Divergence at the extremes

  • With δ ≥ δG, boundary-localizing abstention prevents a gaming receiver from confirming a boundary crossing, while coarse abstention succeeds with probability approaching 1 as queries grow.The gaming success probability under coarse abstention tends to 1 for any abstention budget below 1.Source: §5 · p. 12
  • At worst-case θB,µ(ε) = Θ(1/ε), extraction under coarse abstention requires a factor of 1/ε more queries than under boundary-localizing abstention.The comparison is between the learner query rates established by Theorems 5 and 7.Source: §5 · p. 12

Pareto frontier

  • Within the convex-combination family, no experiment dominates another on both gaming and learning objectives unless it uses the same λ.The family is closed under time-sharing between its extreme rules.Source: §5 · p. 13
  • For small λ, the learner’s binary-search strategy governs while gaming cost grows; as λ rises, learner cost grows until the active-learning strategy takes over.The learner chooses the better of an active-learning branch independent of λ and a binary-search branch whose cost rises with λ.Source: §5 · p. 14
  • The crossover occurs near 1 − λ ≍ 1/θB,µ(ε): it is near λ ≈ 1 − ε at worst-case disagreement, but bounded away from 1 for favorable classes.At the worst-case crossover both branches reach ˜Θ(d log(1/ε)/ε); for favorable classes both reach Θ(d log(1/ε)). The authors do not claim Pareto optimality outside this family.Source: §5 · p. 14

6 Experiments

Across seven binary-classification tasks, label-plus-counterfactual access yields exponential extraction-error decay and a larger query advantage on harder tasks than label-only access. Experiments also test the gaming-resistance prediction and compare against a published active label-only baseline.

Experimental setup

  • The seven tasks span tabular, image, and text-embedding inputs, with dimensions 68, 784, and 384, respectively.The victim is an unregularized logistic regression and extraction error is measured as 1 − F on held-out points.Source: §6 · p. 14

Cross-modal rate verification

  • At ε = 0.02, label-plus-counterfactual access uses 5× to 200× fewer queries than random label-only access across tasks, with the largest gaps on harder text-classification tasks.Protocol B’s exponential fit is positive on all seven datasets with R2 ≥ 0.72; Protocol A’s fitted exponent lies in ρ ∈ [0.32, 0.80] on six datasets.Source: §6 · p. 15, Figure 1 · p. 15, Table 1 · p. 15

Comparison to a published label-only baseline

  • On ACSIncome, Protocol B remains 3–6× ahead of ActiveThief for query budgets L ∈ [200, 1000], despite ActiveThief’s roughly 2× speed over random sampling.ActiveThief is a published active-learning label-only baseline; its exponent above 1 is attributed to finite-sample acceleration on this task.Source: §6 · p. 16

Gaming-resistance verification

  • Across 200 trials on ACSIncome and TREC, gaming success was 1.000 with no abstention or coarse 30% abstention, and 0.000 with boundary-localizing abstention.The simulated attacker knew the boundary and queried victim-accepting points within δG of it, using up to 50 queries per trial.Source: §6 · p. 16

Scope of empirical validation

  • The experiments use counterfactual access, which is more informative than the theorem’s ternary abstention protocol; testing that protocol requires a victim that abstains near the boundary.The paper leaves this as a refinement.Source: §6 · pp. 16–17

7 Discussion

The discussion argues that coarse and boundary-localizing abstention have an enduring tradeoff on hard distributions, then identifies open questions about rates, objectives, dynamics, and empirical scope.

Closing the rate for non-regular boundary classes

  • Roughly d/√ε is observed on synthetic RBF boundaries, while the right rate for non-regular classes remains unknown.The Θ(d log(1/ε)) result requires Assumption 6, which holds for linear classifiers, bounded-degree polynomial thresholds, and bounded-depth decision trees, but fails for RBF networks and unbounded unions of intervals.Source: §7 · p. 17

Multi-class extensions

  • For K > 2, it remains unknown whether the gap survives or which multi-class dimension governs both rates.Binary search becomes structurally harder because paths can cross several pairwise surfaces and abstentions do not identify which surface is nearby.Source: §7 · pp. 17–18

Non-linear principal objectives

  • Under nonlinear principal objectives, the optimum need not be either abstention extreme, and the persuasion analogue for inferential receivers remains unresolved.The paper's linear objective is minimizing adversary value subject to an abstention budget; deployers may also weigh legitimate-user accuracy and nonlinear manual-review costs.Source: §7 · p. 18

Dynamic experiments

  • A history-adaptive rule might close the static rules’ gap, but the authors report no evidence either way.Resetting the rule's state at fixed intervals is one candidate dynamic design.Source: §7 · p. 18

Broader empirical scope

  • Experiments fix victims to logistic regression, and the language-feature studies assume attacker and victim use the same MiniLM-L6 encoder.The authors also call for comparison with decision-based attacks such as HopSkipJumpAttack and note that cross-encoder transfer may not preserve the current analyses.Source: §7 · p. 18
Loading 2609.31643v1…