실용적인 비선형 전략적 분류 (Non-Linear Strategic Classification)

전략적 분류 (Strategic Classification) 분야의 알고리즘 발전은 최적 대응 (best response)이 폐쇄형 해 (closed-form solution)를 갖거나 쉽게 근사할 수 있는 설정에서의 선형 분류기 (linear classifiers)에 주로 국한되어 왔습니다. 일부 연구에서 전략적 설정 내 비선형 분류기 (non-linear classifiers)의 역할을 탐구하기도 했으나, 이 방향의 진전은 전략적 행동 (strategic behaviour)의 계산적 난해함 (computational intractability)으로 인해 저해되어 왔습니다. 이를 해결하기 위해, 본 논문에서는 라그랑주 쌍대성 (Lagrangian duality)을 활용하여 최적 대응을 근사하는 새로운 방법을 제시합니다. 전략적 대응을 제약 최적화 문제 (constrained optimisation problem)로 재구성함으로써, 1차 최적화 방법 (first order optimisation methods)에 적합한 라그랑주 (Lagrangian)를 구축할 수 있습니다. 이 접근 방식은 선형 설정에서의 폐쇄형 전략적 행동을 재현하며, 비선형 설정에도 직관적으로 적용될 수 있습니다. 우리는 분류기 학습 과정에서 손실의 전체 기울기 (total gradient)를 계산하기 위해, 제안된 대응 공식화와 함께 암시 함수 정리 (Implicit Function Theorem)를 어떻게 사용할 수 있는지 보여줍니다. 이는 분류기 파라미터 (classifier parameters)를 결과적인 전략적 행동과 직접 연결하며, 이러한 관계를 활용할 수 있는 새로운 학습 알고리즘을 생성합니다. 실험적 평가 결과, 결과 모델들이 일반적인 머신러닝 (machine learning) 데이터셋에서 향상된 전략적 정확도 (strategic accuracy)를 달성함을 보여줍니다.