Error Analysis of Spherically Constrained Least Squares Reformulation in Solving the Stackelberg Prediction Game

The Stackelberg prediction game (SPG) is a popular model for characterizing strategic interactions between a learner and an adversarial data provider. Although optimization problems in SPGs are often NP-hard, a notable special case involving the least squares loss (SPG-LS) has gained significant research attention recently [1, 2, 3]. The latest state-of-the-art method for solving the SPG-LS problem is the spherically constrained least squares reformulation (SCLS) method proposed in the work of [3]. However, the paper [3] lacks theoretical analysis on the error of the SCLS method, which limits its large-scale applications. In this paper, we investigate the estimation error between the learner obtained by the SCLS method and the actual learner. Specifically, we reframe the estimation error of the SCLS method as a Primary Optimization (PO) problem and utilize the Convex Gaussian min-max theorem (CGMT) to transform the PO problem into an Auxiliary Optimization (AO) problem. Subsequently, we provide a theoretical error analysis for the SCLS method based on this simplified AO problem. This analysis not only strengthens the theoretical framework of the SCLS method but also confirms the reliability of the learner produced by it. We further conduct experiments to validate our theorems, and the results are in excellent agreement with our theoretical predictions.