Source-linked AI summary
Strategic Classification from Revealed Preferences
Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, Zhiwei Steven Wu
TL;DR
The paper asks how to learn linear classifiers when strategic agents with unknown utilities and costs manipulate their features, while the learner observes only their revealed responses. It develops convexity-based online methods and obtains diminishing Stackelberg regret for a broad family of agent cost functions, including adversarially chosen agents. The approach is computationally efficient but excludes some natural utility and cost settings, including important non-convex cases.
Problem
The central challenge is online classification when agents strategically manipulate features but the learner does not know their true features, utilities, or agent-specific manipulation costs.
Method
The paper models learner-agent interaction as an online Stackelberg game and identifies cost and utility conditions that make the learner’s strategic objective convex.
Results
The algorithms obtain diminishing Stackelberg regret for adversarially chosen agents, with expected regret bounds given for different ranges of θ.
Takeaways & Limitations
Stackelberg regret evaluates classifiers against the best fixed hindsight policy while accounting for how agents would respond differently to that policy.
Takeaways & Limitations
The convexity-based approach excludes several natural agent utility functions, especially utilities defined by 0/1 classification loss, and norm costs may fail to yield well-defined best responses.
Abstract
from arXiv · showhide
We study an online linear classification problem, in which the data is generated by strategic agents who manipulate their features in an effort to change the classification outcome. In rounds, the learner deploys a classifier, and an adversarially chosen agent arrives, possibly manipulating her features to optimally respond to the learner. The learner has no knowledge of the agents' utility functions or "real" features, which may vary widely across agents. Instead, the learner is only able to observe their "revealed preferences" --- i.e. the actual manipulated feature vectors they provide. For a broad family of agent cost functions, we give a computationally efficient learning algorithm that is able to obtain diminishing "Stackelberg regret" --- a form of policy regret that guarantees that the learner is obtaining loss nearly as small as that of the best classifier in hindsight, even allowing for the fact that agents will best-respond differently to the optimal classifier.
1 Introduction
The paper studies online strategic classification when agents may manipulate features, their utilities and manipulation costs are unknown, and only their revealed choices are observed. It develops Stackelberg-regret methods for adversarially chosen agents while modeling only negative-label agents as strategic.
- Motivation: Prior strategic-classification work assumes substantial knowledge of agents’ true features and manipulation costs, enabling one-shot Stackelberg-equilibrium computation.The paper instead removes these information assumptions and allows manipulation costs to differ across agents.
- Problem: Unknown agent utilities make one-shot equilibrium computation inappropriate, so the paper models learning as an iterative online procedure.Each round presents a classifier to an arriving agent, whose response provides information the learner must use to improve.
- Objective: Stackelberg regret compares the learner’s loss with that of the best fixed hindsight classifier after accounting for agents’ different best responses.The guarantee applies even when agents are adversarially chosen and implies convergence to a one-shot Stackelberg equilibrium in repeated-agent or fixed-distribution settings.
- Modeling choice: The model treats negative-label agents as strategic while positive-label agents remain non-strategic, avoiding the assumption that legitimate agents must manipulate.This distinction is motivated by spam filtering, where treating all senders as strategic may yield undesirable equilibrium behavior.
- Techniques and scope: The approach seeks agent utility classes and learner costs that produce a convex objective, while recognizing that 0/1 utility functions create unresolved non-convexity.The paper also exploits structure from non-strategic agents after establishing convexity conditions.
2 Model and Preliminaries
The model is a sequential binary-classification game in which the learner commits to a linear classifier and agents respond by either manipulating or truthfully reporting features. Performance is measured by hindsight Stackelberg regret under these strategic responses.
- Agent model: Each agent is represented by features x_t, label y_t ∈ {−1, 1}, and a distance function d_t that assigns manipulation costs.Negative-label agents are strategic; positive-label agents are non-strategic.
- Agent model: The agent utility is u_t(x, β) = ⟨β, x⟩ − d_t(x_t, x), balancing the classifier score against feature-manipulation cost.Strategic agents choose a best response to the learner’s classifier.
- Interaction: Each round proceeds with the learner committing β_t ∈ K, an adversary selecting an agent, the agent submitting a response, and the learner observing the label and loss.Strategic agents modify features optimally, whereas non-strategic agents submit x_t unchanged.
- Losses and constraints: Logistic loss and hinge loss are the two standard learner losses considered, corresponding respectively to logistic regression and support vector machines.The classifier is linear and constrained to a convex feasible set K with bounded norm.
- Regret: Stackelberg regret compares cumulative learner loss with the loss from the best fixed classifier in hindsight for the same agents responding to that classifier.The learner acts as Stackelberg leader and the agent as follower in each strategic round.
3 Conditions for a Convex Learning Problem
The paper identifies conditions under which strategic agents’ best responses preserve convexity of logistic and hinge learner losses. Convex distance functions that are positive homogeneous of degree greater than one yield well-defined best-response structure, while weaker conditions can make responses undefined.
- Convexity challenge: Strategic best responses can destroy convexity even when the original classification loss is convex in the classifier.The learner’s loss depends on the agent’s feature response, so convexity must be established for the strategic interaction itself.
- Sufficient conditions: For d(ˆx, x) = f(ˆx −x), convexity of f and positive homogeneity of degree r > 1 make the strategic learner problem convex.The best-response representation uses the convex conjugate f ∗ and subgradients, yielding a convex inner-product term.
- Convexity criterion: If β 7→⟨ˆx(β), β⟩ is convex, both logistic and hinge losses are convex in β.The result applies to strategic and non-strategic agents through the non-increasing convex form of the classification losses.
- Best-response structure: The resulting inner-product function is well-defined even when agents have multiple best responses.Theorem 2 ensures that ⟨ˆx(β), β⟩ does not depend on which best response is selected.
- Examples and nonexamples: The framework covers norm-based costs after an invertible linear transformation, for any r > 1, while ordinary norms can yield undefined best responses.For d(ˆx, x) = ∥ˆx −x∥, responses are truthful when ∥β∥∗≤1 and undefined with arbitrarily high utility when ∥β∥∗>1.
4 Regret Minimization
The paper presents an online convex-optimization algorithm for strategic classification that combines zeroth-order feedback on strategic rounds with subgradient feedback on non-strategic rounds. Its expected Stackelberg regret is sublinear, with rates depending on the fraction of strategic agents and the norm geometry.
- Mixture Feedback: The algorithm uses zeroth-order feedback on strategic rounds and full subgradient updates on non-strategic rounds.Strategic agents make the loss depend on the classifier through their manipulated features, preventing direct subgradient access.
- Regret Guarantees: The regret rate depends on the fraction of strategic agents, and an upper bound on that fraction suffices with only an additional additive constant.The algorithm assumes the fraction is known when setting η and δ, but a valid upper bound can replace it.
- Bandit Optimization: The method optimizes smoothed convex losses by perturbing each classifier and estimating gradients from function values.The feasible domain is restricted to Kδ so perturbation balls remain inside K.
- Regret Analysis: The resulting regret bound separates non-strategic and strategic rounds and includes an additional error from δ-smoothing.The analysis assumes each loss is L-Lipschitz over K.
- Regret Guarantees: Theorem 6 guarantees sublinear expected Stackelberg regret for any sequence of agents.The bound is developed by combining online subgradient analysis with the separate feedback regimes.
- Alternative Methods: Alternative bandit convex-optimization methods can achieve ˜O(d^9.5√n) regret when all agents are strategic, while this algorithm has milder dimension dependence and interpolates between feedback regimes.The comparison concerns dependence on the time horizon and dimension.
- Dimension Dependence: For 1 ≤ p ≤ 2, the algorithm has fixed mild dependence on dimension d regardless of the power r > 1.When p > 2, dependence on d grows with p and shrinks with r.
5 Discussion and Open Questions
The discussion identifies open questions about broadening the utility-function and problem classes while weakening assumptions about agent behavior and learner knowledge. In particular, the convexity-based approach excludes 0/1 utility functions, and the model assumes exact best responses.
- Broadening the Problem Class: The approach applies to utility-function classes that yield a convex learner objective when paired with natural learner cost functions.This convexity requirement excludes several natural utility functions, especially those defined by 0/1 classification loss.
- Broadening the Problem Class: A central open question is whether structural results for known separable costs and 0/1 loss can extend to unknown agent costs.Prior work obtains efficiently computable Stackelberg equilibria despite non-convexity when costs are known and separable.
- Weakening Agent Assumptions: The model assumes strategic agents play exact best responses, leaving approximate or usually best-responding agents as an open direction.The discussion frames this as part of weakening assumptions about the agents.
A Concrete Regret Bounds for Specific Examples
The section develops explicit Stackelberg-regret bounds by bounding problem-dependent constants for abstract norms and Lp-induced norms. It then expands the resulting assumptions and dimension dependence, including a distinction between p≤2 and p>2.
- Abstract and Lp norms: The analysis bounds Stackelberg regret through problem-dependent constants L and M, first for abstract norms and then for Lp norms.The section works out explicit bounds on these constants.
- Abstract and Lp norms: For loss functions based on logistic or hinge loss, the analysis uses norm and dual-norm relationships to establish boundedness and Lipschitz properties.The Lipschitz analysis decomposes the relevant expression into an inner-product term and a dual-norm term.
- Lp-induced norms: For norms of the form ∥x∥=∥Ax∥p, the bounds assume that the smallest singular value of A is at least ε.This condition makes A ε-far from singular and controls the inverse operator norm.
- Lp-induced norms: The resulting Lp bounds use the dual exponent q and include the factor ε^-1d^(1/q−1/2)+.The factor arises from bounding the norm-equivalence constant C and substituting it into the general theorem.
- Expanded regret bounds: When p>2, the dependence on dimension d grows with p and shrinks with r.This contrasts with the fixed dependence obtained for 1≤p≤2, regardless of r.
Proof of Claim 2
The proof shows that the convex conjugate f* is finite everywhere under the stated assumptions. It does so by establishing continuity and taking a supremum over the compact unit sphere.
- Finiteness of f*: Under the assumptions of Theorem 2, f*(β) is finite for every β∈Rd.The proof establishes this as the target claim.
- Finiteness of f*: Convexity and finiteness of f imply continuity, while positive homogeneity gives f(0)=0.The proof then parameterizes the conjugate using the unit sphere Sd−1.
- Finiteness of f*: For each unit vector v, positivity of f(v) makes the inner supremum finite and explicitly computable.The unit-vector condition excludes v=0, and the first assumption ensures f(v)>0.
- Finiteness of f*: The resulting expression is continuous in v, so its supremum over the compact sphere Sd−1 is finite.Therefore the convex conjugate is finite everywhere.
Proof of Claim 3
The proof derives how convex conjugation transforms a convex function that is homogeneous of degree r>1. The conjugate is shown to be convex and homogeneous of the dual degree s.
- Homogeneity of the conjugate: The proof uses scaling rules for convex conjugates under input rescaling and multiplication of the original function.These rules follow by taking suprema of the corresponding transformed expressions.
- Homogeneity of the conjugate: Applying the rules to f(αx)=α^r f(x) and changing variables yields the homogeneity relation for f*.The substitutions are v=α^-1β and γ=α^(1−r).
Proof of Claim 4
The proof characterizes the convex conjugate of a convex, positively homogeneous function using the dual norm. It establishes matching upper and lower bounds to obtain the stated expression.
- Conjugate characterization: For an abstract norm and r>1, the claim gives a convex-conjugate characterization involving the dual norm and the conjugate exponent s.The exponent relation is 1/r+1/s=1.
- Conjugate characterization: The assumptions required by Theorem 2 are convexity and positive homogeneity of degree r>1.The proof verifies these conditions before deriving the conjugate expression.
- Upper and lower bounds: The upper-bound argument treats the objective as a function of ∥x∥ and uses a norm-constrained maximization.The relevant norm is bounded by the dual-norm expression appearing in the proof.
- Upper and lower bounds: Choosing a suitably scaled vector aligned with β supplies the reverse inequality.The vector satisfies ⟨x~,β⟩=∥x~∥∥β∥* and is scaled so that ∥x~∥^r=∥β∥^s.
- Upper and lower bounds: Because both inequalities hold, the proof concludes equality with the claimed formula for f*(β).The equality follows from matching upper and lower bounds.