Research map / Learning theory and algorithms / Prediction and decision losses
One-Shot Strategic Classification Under Unknown Costs
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 one-shot minimax strategic classification under unknown (PSD-norm) costs, proving that cost misestimation can be catastrophic and giving subgradient and mirror-descent algorithms with O~(T^-1/2) convergence to the minimax classifier using the strategic hinge loss with dual-norm regularization.
Problem
Strategic classification assumes the users' cost function is known; when the true cost is unknown and only one deployment is possible, a classifier tuned to a wrong cost can have very high error.
Approach
Optimize the minimax strategic hinge risk over an uncertainty set of PSD-norm costs, with the inner worst-case cost solved efficiently via dual norm structure, and use dual-norm regularization which makes the objective convex for sufficiently large regularization weight.
Key results
- Proves that for PSD-norm costs, small mis-estimation of the cost can induce error arbitrarily close to 1 in the worst case.
- Subgradient and mirror descent algorithms converge at O~(T^-1/2) to the minimax optimal classifier, with a dimension-independent rate despite non-concave inner maximization.
- Dual norm regularization with lambda >= tau+ makes the regularized strategic hinge loss convex, whereas l2 regularization needs much larger lambda.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Optimize the classifier with the subgradient method over the cost uncertainty set | Strategic classification · Uncertainty set of costs | suboptimality: \frac{LB}{\sqrt{T}} | Helped |
| Use online mirror descent with discretized cost choices | Strategic classification · Uncertainty set of costs | convergence error: B \uinv \left[ (1 - \lambda) \max_i \sqrt{\epsilon \left( \mincostscale{i}^{-2} - \maxcostscale{i}^{-2} \right)} + \sqrt | Helped |
| Choose discretization \epsilon = \Theta\left( \frac{\log T}{T} \right) | Online mirror descent · Uncertainty set of costs | convergence error: B (\uinv + X) \max_i \mincostscale{i}^{-1} \cdot \sqrt{\frac{\log T}{T}} | Helped |
| Use dual norm regularization instead of \ell_2 regularization | Strategic hinge risk · Fixed cost | regularization threshold sufficient for convexity: \lambda \geq \tau^+; \quad \lambda \geq \frac{\tau^+}{2} \sqrt{\sigma_1^2 + \sigma_2^2} | Helped |
| Optimize for an incorrect cost instead of the true cost | Strategic classifier · Strategic classification with two non-equal cost matrices | error under the other cost: \epsilon; 1-\epsilon | Hurt |
| Optimize for an incorrect cost matrix | Strategic classifier · Isotropic Gaussian data | additional risk: 2\left( \Phi\left( \frac{\norm{\mu_0}}{\sigma} \right) - \frac{\Phi\left( \frac{\norm{\mu_0} + \epsilon}{\sigma} \right) | Hurt |
| Optimize for an incorrect cost matrix | Strategic classifier · Gaussian data with appropriately chosen μ0 | additional risk: .2 | Hurt |
Surprising findings
- Small errors in estimating the cost matrix can cause the classifier to perform no better than random under the true cost.
- The commonly used l2 regularization requires substantially stronger regularization than dual norm regularization to guarantee convexity.
Limitations
- Does not account for social cost.
- Considers a fixed shared eigenvector basis and a single utility level for all users.
- Uses a discretization for mirror descent, leading to an extra log factor in the rate.
Experimental setup
Metrics: worst-case risk strategic 0-1 loss
Builds on: strategic hinge loss strategic classification Danskin's theorem mirror descent
Closest papers by meaning
- Strategic Classification with Non-Linear Classifiers (NeurIPS 2025 · similarity 0.88)
- Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning (NeurIPS 2025 · similarity 0.86)
- Strategic PAC Learnability via Geometric Definability (NeurIPS 2026 · similarity 0.86)
- Bayesian Strategic Classification (NeurIPS 2024 · similarity 0.86)
- Strategic Classification With Externalities (ICLR 2025 · 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.