Fundamental Bounds on Online Strategic Classification
Fundamental Bounds on Online Strategic Classification
复制标题
在线战略分类的基本界限
DOI：
10.1145/3580507.3597818
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Yang, Kunhe
中科院分区：
文献类型：
--
作者：
Ahmadi, Saba;Blum, Avrim;Yang, Kunhe
我们研究了在线二分类问题，其中策略主体可以通过预先定义的方式操纵他们的可观测特征，并以操作图的形式建模，以获得肯定的分类。我们表明，这种设置在根本上不同于经典的(非战略性)在线分类。例如，尽管在非战略情况下，当目标函数属于已知类别时，通过减半算法可以达到ln|H|的误差界，但我们证明了在战略环境中没有确定性算法可以达到错误边界(Δ)，其中Δ是操作图的最大度(即使当|H|=O(Δ)时)。我们用一个获得误差界O(Δln|H|)的通用算法来补充这一点。我们还将其推广到不可知性设置中，证明了该算法实现了Δ乘性遗憾(错误界为Δ·opt+Δ·ln|H|)，并且没有确定性算法能够实现(Δ)乘性遗憾.在第一个分数模型中，在每一轮中，学习者确定性地选择分类器上的概率分布，在每个顶点上诱导期望值(被分类为正的概率)，战略代理对此做出响应。我们发现，在这个模型中，任何学习者都会遭受线性后悔。另一方面，在第二随机算法模型中，当选择下一个代理的对手必须对学习者在分类器上的概率分布做出响应时，代理则对从该分布中提取的实际假设分类器做出响应。令人惊讶的是，我们证明了这种模型对学习者更有利，并且我们设计了随机化算法，在对抗遗忘和自适应对手的情况下都实现了次线性后悔界限。
We study the problem of online binary classification where strategic agents can manipulate their observable features in predefined ways, modeled by a manipulation graph, in order to receive a positive classification. We show this setting differs in fundamental ways from classic (non-strategic) online classification. For instance, whereas in the non-strategic case, a mistake bound of ln|H|is achievable via the halving algorithm when the target function belongs to a known classH, we show that no deterministic algorithm can achieve a mistake boundo(Δ) in the strategic setting, where Δ is the maximum degree of the manipulation graph (even when |H| =O(Δ)). We complement this with a general algorithm achieving mistake bound O(Δ ln|H|). We also extend this to theagnosticsetting, and show that this algorithm achieves a Δ multiplicative regret (mistake bound ofO(Δ · OPT + Δ · ln |H|)), and that no deterministic algorithm can achieveo(Δ) multiplicative regret.Next, we study two randomized models based on whether the random choices are made before or after agents respond, and show they exhibit fundamental differences. In the first,fractionalmodel, at each round the learner deterministically chooses a probability distribution over classifiers inducing expected values on each vertex (probabilities of being classified as positive), which the strategic agents respond to. We show that any learner in this model has to suffer linear regret. On the other hand, in the secondrandomized algorithmsmodel, while the adversary who selects the next agent must respond to the learner's probability distribution over classifiers, the agent then responds to the actual hypothesis classifier drawn from this distribution. Surprisingly, we show this model is more advantageous to the learner, and we design randomized algorithms that achieve sublinear regret bounds against both oblivious and adaptive adversaries.
登录
查看更多内容
福利最大化
DOI：
--
发表时间：
1977
期刊：
影响因子：
--
作者：
R. Eisner
通讯作者：
R. Eisner
分类器如何引导智能体进行战略性投入？
DOI：
--
发表时间：
2018
期刊：
ACM Conference on Economics and Computation
影响因子：
--
作者：
J. Kleinberg;Manish Raghavan
通讯作者：
Manish Raghavan
DOI：
--
发表时间：
2021
期刊：
International Conference on Machine Learning
影响因子：
--
作者：
Sagi Levanon;Nir Rosenfeld
通讯作者：
Nir Rosenfeld
获取人口层面的信号是不平等的根源
DOI：
10.1145/3287560.3287579
发表时间：
2018
期刊：
Proceedings of the Conference on Fairness, Accountability, and Transparency
影响因子：
--
作者：
Nicole Immorlica;Katrina Ligett;Juba Ziani
通讯作者：
Juba Ziani
DOI：
10.1145/2020408.2020495
发表时间：
2011-08
期刊：
--
影响因子：
--
作者：
Michael Brückner;T. Scheffer
通讯作者：
Michael Brückner;T. Scheffer