Research map / Learning theory and algorithms / Prediction and decision losses
Strategic Classification with Non-Linear Classifiers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies strategic classification with non-linear classifiers under l2 costs, showing that strategic behavior can raise or lower VC dimension of the effective class and that universal approximators stop being universal under strategic responses.
Problem
Strategic classification research has focused almost entirely on linear classifiers; the effect of strategic user feature manipulation on non-linear decision boundaries, expressivity, and model class complexity is not understood.
Approach
Bottom-up analysis mapping individual boundary points, classifiers, and model classes through the strategic best-response; uses offset-curve geometry to show effective curvature is kappa/(1+alpha*kappa), so strategic behavior smooths positive curvature, creates wipeouts, and makes some decision boundaries unrealizable, breaking universality.
Key results
- Strategic behavior can shrink VC dimension from infinity to 0 (Thm. on VC(H)=inf, VC(H_eff)=0), while for scale-closed classes VC cannot decrease.
- For piecewise-linear classes with m segments and k intersections, effective VC is O(d m log m + nu_p k log k), so strategic behavior keeps learnability.
- Distributions realizable in the standard setting can have maximum strategic accuracy equal to the majority class rate; the synthetic experiments show accuracy drops as alpha grows and mu shrinks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Learn in the strategic setting with an unrestricted effective hypothesis class rather than the standard unrestricted class | Unrestricted hypothesis class · Synthetic dataset (example) | accuracy: 1 to 0.96 | Hurt |
| Increase class separation | Unrestricted effective hypothesis class · Synthetic class-conditional Gaussian data | strategic accuracy | Helped |
| Increase strategic reach (α) | Unrestricted effective hypothesis class · Synthetic class-conditional Gaussian data | strategic accuracy | Hurt |
| Use a nonlinear effective hypothesis class instead of a linear effective class | Strategic classification · Synthetic class-conditional Gaussian data with small class separation | accuracy | Helped |
| Increase strategic reach (α) | Polynomial classifier and its effective boundary · Random degree-k polynomial classifiers | approximation degree kΔ | Mixed |
| Increase strategic reach (α) | Polynomial classifier and its effective boundary · Random degree-k polynomial classifiers | approximation degree kΔ | Helped |
| Increase strategic reach (α) | Polynomial classifier and its effective boundary · Random degree-k polynomial classifiers | approximation degree kΔ | Hurt |
Surprising findings
- Universal approximators (e.g., neural nets, RBF kernels) are no longer universal under strategic behavior.
- Strategic behavior can make model classes that were not learnable in the standard setting learnable.
Limitations
- General upper bound on VC increase for arbitrary model classes remains open (only conjectured)
- Results restricted mainly to l2 costs and the best-response model with uniform utility alpha
- Experiments are small synthetic settings in 2D with polynomial classifiers
Experimental setup
Datasets: synthetic class-conditional Gaussian data
Metrics: VC dimension effective polynomial degree maximum strategic accuracy
Baselines: linear strategic classifiers unrestricted non-strategic class H*
Builds on: strategic classification (Hardt et al.) offset curves from computational geometry strategic VC (Cohen et al.)
Closest papers by meaning
- One-Shot Strategic Classification Under Unknown Costs (ICML 2024 · similarity 0.88)
- Should Decision-Makers Reveal Classifiers in Online Strategic Classification? (ICML 2025 · similarity 0.87)
- Classification Under Strategic Self-Selection (ICML 2024 · similarity 0.87)
- Incentivizing Desirable Effort Profiles in Strategic Classification: The Role of Causality and Uncertainty (NeurIPS 2025 · similarity 0.87)
- Understanding Model Selection for Learning in Strategic Environments (NeurIPS 2024 · similarity 0.86)
- Breaking the Gradient Barrier: Unveiling Large Language Models for Strategic Classification (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.