A primary goal in strategic classification is to learn decision rules which
are robust to strategic input manipulation. Earlier works assume that strategic
responses are known; while some recent works address the important challenge of
unknown responses, they exclusively study sequential settings which allow
multiple model deployments over time. But there are many
domains$\unicode{x2014}$particularly in public policy, a common motivating
use-case$\unicode{x2014}$where multiple deployments are unrealistic, or where
even a single bad round is undesirable. To address this gap, we initiate the
study of strategic classification under unknown responses in the one-shot
setting, which requires committing to a single classifier once. Focusing on the
users' cost function as the source of uncertainty, we begin by proving that for
a broad class of costs, even a small mis-estimation of the true cost can entail
arbitrarily low accuracy in the worst case. In light of this, we frame the
one-shot task as a minimax problem, with the goal of identifying the classifier
with the smallest worst-case risk over an uncertainty set of possible costs.
Our main contribution is efficient algorithms for both the full-batch and
stochastic settings, which we prove converge (offline) to the minimax optimal
solution at the dimension-independent rate of
$\tilde{\mathcal{O}}(T^{-\frac{1}{2}})$. Our analysis reveals important
structure stemming from the strategic nature of user responses, particularly
the importance of dual norm regularization with respect to the cost function.

在策略分类中，我们研究了在一次性场景下未知响应的策略分类问题，通过最小化最坏情况下的风险来确定最优的分类器，并提出了高效的算法以及对于成本函数的双范数正则化的重要性。

未知成本下的一次性战略分类

One-Shot Strategic Classification Under Unknown Costs

Machine learning algorithms with empirical risk minimization are vulnerable
under distributional shifts due to the greedy adoption of all the correlations
found in training data. Recently, there are robust learning methods aiming at
this problem by minimizing the worst-case risk over an uncertainty set.
However, they equally treat all covariates to form the decision sets regardless
of the stability of their correlations with the target, resulting in the
overwhelmingly large set and low confidence of the learner.In this paper, we
propose Stable Adversarial Learning (SAL) algorithm that leverages
heterogeneous data sources to construct a more practical uncertainty set and
conduct differentiated robustness optimization, where covariates are
differentiated according to the stability of their correlations with the
target. We theoretically show that our method is tractable for stochastic
gradient-based optimization and provide the performance guarantees for our
method. Empirical studies on both simulation and real datasets validate the
effectiveness of our method in terms of uniformly good performance across
unknown distributional shifts.

本文提出了一种 Stable Adversarial Learning（SAL）算法，该算法通过利用异构数据源构建更实用的不确定性集合，并针对与目标之间的相关性稳定性进行差异化的强鲁棒性优化，在随机梯度优化的情况下证明了可行性和提供了性能保证。该算法的实证研究在模拟和实际数据集上验证了其总体表现较好的有效性。