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

Authors: xiyuan  li
weiwei  liu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 12:58:09

Abstract: 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, (Bishop et al. 2020; Wang et al. 2021; Wang et al. 2022). 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 Wang et al. (2022). However, the lack of theoretical analysis on the error of the SCLS method 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 ($\textbf{PO}$) problem and utilize the Convex Gaussian min-max theorem (CGMT) to transform the $\textbf{PO}$ problem into an Auxiliary Optimization ($\textbf{AO}$) problem. Subsequently, we provide a theoretical error analysis for the SCLS method based on this simplified $\textbf{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.

Main paper: 
 introduction: 
 The Stackelberg prediction games (SPGs) play prominent roles in various applications of the machine learning field, such as intrusion detection [4] , spam filtering [5] , and malware detection [6, 7] . SPG characterizes the interactions between two players, a learner and a data provider (attacker), during the training process of various machine learning algorithms [8, 9, 10, 11] . Specifically, the learner first selects a learning model to fit the given data. The data provider, with full knowledge of the learner's model, then attacks the learner by modifying the data. The learner's goal is to minimize its loss function under the assumption that the training data has been optimally modified from the data provider's perspective. Therefore, the SPG model is often formulated as a bi-level optimization problem, which is generally NP-hard even in the simplest case with linear constraints and objectives [1, 12] .To overcome the NP-hard nature of SPGs, [1, 2, 3] focus on a commonly used subclass of SPGs, termed as the SPG-LS, whose loss functions for the learner and the data provider are least squares. Specifically, SPG-LS has access to a set of n sample tuples denoted by S = {(x x x i , y i , z i )} n i=1 , wherex x x i ∈ R d is input data with d features, y i is the true output label of x x x i , and z i is the label that the data provider aims to achieve. The learner of SPG-LS aims to train a linear predictor w w w ∈ R d to best estimate the true output label y i of the fake data x x x * i by minimizing the least squares loss:w w w * = arg minw w w 1 n n i=1 ∥w w w ⊤ x x x * i -y i ∥ 2 .Meanwhile, the data provider of SPG-LS, with full knowledge of the learner's predictive model w w w, selects the following least squares attacking strategy (i.e., modifying the data x x x i ) to make the corresponding prediction w w w ⊤ x x x * i close to the desired label z i :x x x * i = arg minx x x ∥w w w ⊤ x x x i -z i ∥ 2 + γ∥x x x i -x x x i ∥ 2 ,where γ > 0 is a regularizer to adjust the trade-off between the deviation from the original data x x x i and closeness to the target z i . Thus, the SPG-LS model can be expressed as the following bi-level optimization problem, as described in [1, 2, 3] :EQUATIONwhere X X X = (x x x 1 , x x x 2 , • • • , x x x n ) ⊤ ∈ R n×d is the input sample matrix, y y y = (y 1 , y 2 , • • • , y n ) ⊤ ∈ R n is the vector of true output labels, and z z z = (z 1 , z 2 , • • • , z n ) ⊤ ∈ R n is the vector of labels that the attacker aims to achieve. Moreover, ∥ • ∥ denotes the Euclidean norm (l 2 ) unless otherwise specified.There have been several studies solving the SPG-LS (1) to determine the Stackelberg equilibrium point between the learner and the data provider. The initial step in reformulating SPG-LS (1) is taken by [1] , who provides a single-level quadratic fractional program (QFP) that can be globally solved by a bisection algorithm. However, this QFP method is computationally prohibitive in practice due to the need to solve multiple semidefinite programs (SDPs). Later, [2] improves upon [1] by showing that the SPG-LS (1) can be globally solved by reducing a single SDP to a second-order cone program (SOCP). Despite being faster than the QFP method, the SOCP method is still not well-suited for large-scale SPG-LS (1) due to time-consuming spectral decomposition. Recently, [3] proposes a spherically constrained least squares reformulation (SCLS) method, addressing the above-mentioned issues with a novel nonlinear change of variables. Furthermore, [3] demonstrates that the SCLS method outperforms the SOCP method and is currently the state-of-the-art for solving SPG-LS (1) , having won the ICML 2022 Outstanding Paper Award.However, the lack of theoretical analysis on the error of the SCLS method limits its large-scale practical applications. In this paper, we investigate the estimation error between the learner (e.t.w w w * ) estimated by the SCLS method and the true learner (denoted as w w w 0 ) to validate the reliability of w w w * . Specifically, we assume the samples S = {(x x x i , y i , z i )} n i=1 are generated by the following black box model:EQUATIONwhere w w w 0 ∈ R d represents the "true" weight parameter of the real learner, and ϵ ϵ ϵ = (ϵ 1 , ϵ 2 , • • • , ϵ n ) ⊤ ∈ R n is the noise vector. Moreover, the entries of X X X and z z z are drawn i.i.d. from N (0, 1); the entries of ϵ ϵ ϵ are drawn i.i.d. from N (0, σ 2 ); and we assume lim n→∞ d n ∈ (0, 1). Given X X X, z z z, and y y y generated by this model (2) , we solve SPG-LS (1) by the SCLS method to obtain w w w * that is used to estimate the target vector w w w 0 . Our task is to measure the optimal estimation error of the SCLS method, represented by ∥w w w * -w w w 0 ∥.We start by formulating an optimization problem regarding the estimation error (e.t. β β β := w w w -w w w 0 ) of the SCLS method. Subsequently, we convert this optimization problem into a Primary Optimization (PO) problem, employing the Fenchel-Moreau theorem [13] . Following this, we utilize the Convex Gaussian min-max theorem (CGMT) to simplify the PO problem into an Auxiliary Optimization (AO) problem. Finally, we conduct a theoretical error analysis of the SCLS method based on the AO problem. Our main theoretical result can be summarized as follows:EQUATIONwhich guarantees the reliability of w w w * learned by the SCLS method. Our analysis strengthens the theoretical foundations of the SCLS method and provides theoretical support for its broad applications.We also conduct experiments to validate our theorems. The results show that, as n goes to ∞, the parameter vector w w w * learned through the SCLS method converges to actual parameter vector w w w 0 in probability, which aligns excellently with our theoretical predictions.The structure of the remaining sections in this paper is organized as follows: Additional related work is discussed in Appendix 2. Section 3 provides an overview of the SCLS method, CGMT technology, and foundational concepts. Our main inference processes are detailed in Section 4. Specifically, in Section 4.1, we present an optimization problem concerning the estimation error of the approximated SCLS method and establish the relationship between the original and the approximated SCLS method; In Section 4.2, the estimation error of the approximated SCLS method is transformed into a PO problem; In Section 4.3, we simplify the PO problem to an AO problem using CGMT; In Section 4.4, we conduct an estimation error analysis of the SCLS method based on the AO problem and the relationship between the original and the approximated SCLS method. We then present the experimental results in Section 5. Finally, a summary is provided in Section 6. Moreover, the limitations of our work are detailed in Appendix A2 Related WorkQuestion: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: We highly summarize what we do in the abstract. The introduction clearly introduces the concepts and issues that are related to our main results.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
the stackelberg prediction game: 
 Stackelberg Prediction Games (SPGs) were initially introduced by [14] , drawing inspiration from Stackelberg competition-a model initially developed to describe market behaviors. A notable parallel can be drawn with Stackelberg Security Games (SSGs), as detailed by [4, 6] . In SSGs, a defender strategically allocates resources to protect targets from an attacker. The optimal defense strategy in SSGs typically involves solving multiple linear programs [15, 16] , and [17] demonstrates that a near-optimal strategy can be efficiently approximated through a polynomial number of queries to the attacker's model. While both SPG and SSG frame the learning of an optimal strategy as a bilevel optimization problem, SPGs are distinctly designed to counteract manipulation within machine learning algorithms [1] .Recognized as NP-hard hierarchical mathematical challenges [12] , SPGs have been extensively examined. However, existing research predominantly addresses scenarios where data providers exhibit partial adversarial behaviors or possess constrained adversarial capabilities. The study by [1] explores SPGs within the context of linear least squares regression (e.g., SPG-LS), assuming data providers are neither fully adversarial nor entirely honest. To address the SPG-LS problem, [1] initially formulated a solution approach, which was later enhanced by [2] . Subsequently, [3] introduced the Spherical Constrained Least Squares (SCLS) method, currently acknowledged as the state-of-the-art. This paper aims to further elucidate the error dynamics of the SCLS method [18] , thereby solidifying its theoretical foundation for broader practical application.The Convex Gaussian Min-max Theorem (CGMT) framework, first introduced by [19] , serves as a potent analytical tool extensively utilized to evaluate the performance of solutions within non-smooth regularized convex optimization problems. This framework is derived from Gordon's Gaussian Minmax Theorem (GMT) [20, 21] , which provides foundational insights into the behavior of Gaussian processes in optimization scenarios. Over the years, the CGMT has enabled significant advancements across a spectrum of practical applications. Notable examples include enhancements in regularized logistic regression [22] , max-margin classifiers [23] and adversarial training [24, 25] . Motivated by these successful applications, we are encouraged to employ the CGMT framework to conduct a thorough analysis of the estimation error associated with the SCLS method.3 PreliminariesQuestion: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: Our paper explicitly acknowledges the dependency on Gaussian inputs as a limitation, prompting further investigation into its applicability to non-Gaussian contexts.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
the scls method: 
 This section provides a comprehensive overview of the SCLS method as introduced by [3] . Expanding upon previous studies by [1, 2] , [3] reformulates SPG-LS (1) into the following quadratic fractional program (QFP) utilizing the Sherman-Morrison formula [26] :EQUATIONMoreover, [3] introduces an augmented variable α = w w w ⊤ w w w/γ and further reformulate QFP (4) as:EQUATIONSubsequently, [3] makes a assumption on the nonemptiness of the optimal solution set of QFP (5) .). Assume that the optimal solution set of (5) (or equivalently, ( 4)) is nonempty.Under Assumption 3.1, [3] employs a nonlinear variable transformation to recast the QFP (5) as a spherical constrained least squares (SCLS) problem:EQUATIONwhere w w w and α are defined in Lemmas 3.2 and 3.3. Upon identifying a feasible solution in QFP (5), [3] introduces Lemma 3.2 to construct a feasible solution in SCLS (6) , while Lemma 3.3 describes the inverse transformation.). Suppose (w w w, α) is a feasible solution of QFP (5) . Then ( w w w, α), defined asw w w := 2 √ γ(α + 1)w w w and α :=EQUATIONis feasible to SCLS (6) and v(w w w, α) = ṽ( w w w, α).). Suppose ( w w w, α) is feasible to SCLS (6) with α ̸ = 1. Then (w w w, α), defined asEQUATIONis feasible to QFP (5) and ṽ( w w w, α) = v(w w w, α).Let v * and ṽ * represent the optimal values of QFP (5) and SCLS (6) , respectively. Subsequently, [3] presents Theorem 3.4 to elucidate the relationship between the solutions of QFP ( 5) and SCLS (6) .). Given Assumption 3.1, then there exists an optimal solution ( w w w, α) to SCLS (6) with α ̸ = 1. Moreover, (w w w, α), defined by (8) , is an optimal solution to (5) and v * = v(w w w, α) = ṽ( w w w, α) = ṽ * .Theorem 3.4 indicates that an optimal solution of SCLS (6) can be utilized to recover an optimal solution of SPG-LS (1) . Additionally, the converse of this theorem also holds, as demonstrated by [3] . Specifically, if (w w w, α) is an optimal solution to QFP (5), ( w w w, α), as defined by (7) , is also an optimal solution to SCLS (6) .It is important to note that [3] focus on a compact form of SCLS (6): min r r r q(r r r), s.t. r r r T r r r = 1,where q(r r r) = ∥ Lr r r -(y y y -z z z/2)∥ 2 , L = √ γ 2 X X X z z z 2 and r r r = w w w α . Due to the equivalence of SCLS problems ( 6) and ( 9),this paper focus on the SCLS (6).The Convex Gaussian Min-max Theorem (CGMT) originates from Gordon's Gaussian Min-max Theorem (GMT) [21] , which provides probabilistic bounds on the optimal cost of PO problem via a simpler AO problem. CGMT further tightens the bounds under convexity assumptions. Building on GMT, [20] introduces the following asymptotic sequence and notation.Definition 3.5 (GMT admissible sequence). The sequence G G G (d) , g g g (d) , h h h (d) , SEQUATIONEQUATIONβ β β and S (d) u u u are compact sets and ψ (d) is continuous on its domain. Onwards, we will drop the superscript (d) from G G G (d) , g g g (d) , h h h (d) .A sequence G G G (d) , g g g (d) , h h h (d) , S (d)β β β , S (d) u u u , ψ (d)d∈N defines a sequence of min-max problemsEQUATIONEQUATIONImportantly, the formulation ( 10) is called Primary Optimization (PO) and the formulation ( 11) is called Auxiliary Optimization (AO). Additionally, let β β β(d)Φ (G G G) denote the optimal minimizer of the PO problem (10) , and β β β(d)ϕ (g g g, h h h) denote the optimal minimizer of the AO problem (11) . DefineEQUATIONClearly, ϕ (d) (g g g, h h h) := min β β β∈S (d)β β β υ (d) (β β β; g g g, h h h).For a sequence of random variables {X (d) } d∈N and a constant c ∈ R, X (d) P -→ c denotes convergence in probability, i.e., ∀ϵ > 0, lim d→∞ P |X (d) -c| > ϵ = 0. Based on the GMT admissible sequence and the notation introduced above, we present the CGMT below. Theorem 3.6 (CGMT [27] ). Let G G G (d) , g g g (d) , h h h (d) , S (d)EQUATIONu u u , ψ (d) d∈N be a GMT admissible sequence as in Definition 3.5, for which additionally the entries of G G G, g g g, h h h are drawn i.i.d. from N (0, 1). Let Φ (d) (G G G), ϕ (d) (g g g, h h h) be the optimal costs, and, β β β(d) Φ (G G G), β β β (d)ϕ (g g g, h h h) the corresponding optimal minimizers of the PO and AO problems in (10) and (11) . The following three statements holdEQUATIONu u u are convex, and,ψ (d) (•, •) is convex-concave on S (d) β β β × S (d)u u u , then, for any µ ∈ R and t > 0,P |Φ (d) (G G G) -µ|) > t ≤ 2P |ϕ (d) (g g g, h h h) -µ|) > t(iii) Assume the conditions of (ii) hold for all d ∈ N. Let ∥ • ∥ denote some norm in R d and recall (12) . If, there exist constants (independent of d) κ * , ρ * and τ > 0 such that (a) ϕ (d) (g g g, h h h)P -→ κ * , (b) ∥β β β (d) ϕ (g g g, h h h)∥ P -→ ρ * , (c) with probability one in the limit d → ∞ υ (d) (β β β; g g g, h h h) ≥ ϕ (d) (g g g, h h h) + τ ∥β β β∥ -β β β (d) ϕ (g g g, h h h) 2 , ∀β β β ∈ S (d) β β β , then, ∥β β β (d) Φ (G G G)∥ P -→ ρ * .Theorem 3.6 indicates that, if the optimal cost ϕ(g g g, h h h) of ( 11) converges to some value µ, the same holds true for Φ(G G G) of PO (10) . Furthermore, under appropriate additional assumptions, the optimal solutions of the AO and PO problems are also closely related by∥β β β Φ (G G G)∥ = ∥β β β ϕ (g g g, h h h)∥.This suggests that within the CGMT framework, a challenging PO problem can be replaced with a simplified AO problem, from which the optimal solution of the PO problem can be accurately inferred [27] . Subsequently, we rewrite the estimation error of the SCLS method (6) in the form of PO problem (10) and analyze the minimizer of the simplified AO problem instead.Conjugate pairs:Consider a function f : R d → R. The Fenchel conjugate of f , denoted by f * , is defined as f * (u u u) = sup v v v v v v ⊤ u u u -f (v v v), which is always convex and lower semi-continuous. By the Fenchel-Moreau theorem [13] , if f is both convex and continuous, thenf (v v v) = sup u u u u u u ⊤ v v v -f * (u u u).In this paper, we consider the following conjugate pairs for the l 2 norm:EQUATIONFirst-order approximation: Assume f is differentiable. According to [13, Theorem 23.4] :EQUATION)where w w w = w w w 0 + β β β and ḟ (w w w 0 ) = ∂f ∂w w w w w w=w w w0 . The linearization ofEQUATIONAs ∥β β β∥ approaches 0, f (w w w) closely approximates f (w w w).4 The Error Analysis for the SCLS method 4.1 From the SCLS Method to PO Given that the sample (X X X, y y y, z z z) is generated by black box model (2), we integrate SPG-LS (1) and QFP (4) as follows:EQUATIONwhere α 0 = w w w ⊤ 0 w w w 0 /γ. Drawing inspiration from Lemmas 3.2 and 3.3, we defineEQUATIONThis representation of w w w 0 denotes the true weight parameter of SCLS (6) . Notably, ( w w w 0 , α0 ) is valid as long as α 0 ≥ 0 and α0 ̸ = 1, which conforms to ( w w w, α) defined by [3] . Specifically, Forα 0 = w w w ⊤ 0 w w w0 γ ∈ (1, +∞), α0 > 0; For α 0 = w w w ⊤ 0 w w w0 γ ∈ (0, 1), α0 < 0.Additionally, ( w w w 0 , α0 ) satisfies the constraint of SCLS (6), due toEQUATIONTaking ( 17) into ( 16), the expression of y y y can be rewritten as:EQUATIONSubstituting y y y in SCLS ( 6) with ( 19):EQUATION)Combining formulations ( 6), (18) , and ( 20), SCLS ( 6) is equivalent to the optimization problem:EQUATIONLet w w w * denote the optimal solution to original SCLS problem (6) , then, the estimation error for SCLS ( 21) is β β β * := w w w * -w w w 0 . To explore the optimal estimation error for SCLS (21) under different conditions of α0 , we consider two scenarios: Case 1:If α0 > 0, set α( w w w) = 1 -∥ w w w∥ 2 . Case 2: If α0 < 0, set α( w w w) = -1 -∥ w w w∥ 2 .Both cases lead to consistent error analysis outcomes for SCLS (6) , but this paper primarily discusses Case 1, with Case 2 detailed in Appendix D. According to formulation (14) ,EQUATIONThe first-order approximation of α( w w w) is:EQUATIONWhen ∥ w w w -w w w 0 ∥ → 0, α( w w w) converges to α( w w w). Using this approximation in SCLS ( 20) leads to a objective:α -α0 2 z z z + √ γ 2 X X X( w w w -w w w 0 ) -ϵ ϵ ϵ 2 = 1 2 • ∂ α( w w w) ∂ w w w w w w= w w w0 • ( w w w -w w w 0 )z z z + √ γ 2 X X X( w w w -w w w 0 ) -ϵ ϵ ϵ 2 = √ γ 2 1 √ γ • ∂ α( w w w) ∂ w w w w w w= w w w0 • ( w w w -w w w 0 )z z z + X X X( w w w -w w w 0 ) - 2ϵ ϵ ϵ √ γ 2 .Then, we obtain an approximated problem corresponding to SCLS (21) :EQUATIONLet ŵ w w * denote the optimal solution to the approximated SCLS problem (24) , then, the estimation error for approximated SCLS ( 24) is β β β * := ŵ w w * -w w w 0 . Leveraging the simplified representation of α( w w w), we can conduct a precise error analysis for this approximated model (24) . Furthermore, if f ( w w w) and f ( w w w) denote the objective functions of SCLS (21) and the approximated version (24) , respectively,f ( w w w) = α -α0 2 z z z + √ γ 2 X X X( w w w -w w w 0 ) -ϵ ϵ ϵ 2 , f ( w w w) = √ γ 2 1 √ γ • ∂ α( w w w) ∂ w w w w w w= w w w0 • ( w w w -w w w 0 )z z z + X X X( w w w -w w w 0 ) - 2ϵ ϵ ϵ √ γ 2 ,we haveEQUATIONCompared with SCLS (21), the approximation ( 24) is tight when ∥ tildew w w -w w w 0 ∥ goes to 0. We later demonstrate that this convergence condition is satisfied as n goes to ∞, independent of the original SCLS (21) . This fact allows us to translate the findings about ŵ w w * obtained for the approximated SCLS problem (24) to corresponding outcomes of w w w * for the original SCLS problem (6) . Given the constancy of γ, the approximated SCLS problem (24) simplifies to:EQUATION)where β β β := w w w -w w w 0 , and c c c:= c c c( w w w 0 , γ) = 1 √ γ • ∂ α( w w w) ∂ w w w w w w= w w w0 = 1 √ γ • -w w w0 √ 1-∥ w w w0∥ 2 .The normalization of the loss function is appropriately applied, which does not alter the optimal solution. Based on the relationship (25) , when ∥ β β β∥ tends to 0, the approximated SCLS problem (24) effectively aligns with SCLS (21) . This equivalence allows for the substitution of the analysis of the optimal cost β β β * in SCLS (21) with the analysis of the optimal solution β β β * in the first-order optimization (26).Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [NA] Justification: We focus on the SCLS method in our paper. The codes of the SCLS method are from [3] , which is open. Guidelines:• The answer NA means that paper does not include experiments requiring code. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
from po to ao: 
 A key transformation in our analysis involves converting the optimization (26) into a PO problem within the CGMT framework. We apply conjugate pairs (13) for optimization (26) :EQUATIONwhereβ β β ∈ R d , u u u ∈ R n .Using formulations ( 10) and ( 27), the PO problem associated with ( 26) is:EQUATIONwhereψ( β β β, u u u) := c c c ⊤ β β β •u u u ⊤ z z z -2u u u ⊤ ϵ ϵ ϵ √ γ -∥u u u∥ 2 4 .Given that the entries of X X X are drawn i.i.d. from N (0, 1) and ψ( β β β, u u u) is a convex-concave function, the PO problem (28) satisfies the conditions of Theorem 3.6. Consequently, we replace the challenging PO problem (28) with a simplified AO problem using CGMT:EQUATIONwhere the entries of g g g and h h h are drawn i.i.d. from N (0, 1). Suppose β β β ΦSCLS represents the optimal solutions of the PO problem (28) , and β β β ϕSCLS denotes the optimal solutions of the AO problem (29) .According to Theorem 3.6, if ∥ ββ β ϕSCLS ∥ P -→ ρ * , then ∥ β β β ΦSCLS ∥ P -→ ρ * .The reasons why PO (28) is more complex than AO (29) and the difficulties of (28) are summarized as: (i) The PO (28) contains the matrix X X X ∈ R n×d and the challenge lies in processing matrices. the AO (29) only contains vectors with dimensions d or n, which are easier to handle than matrices; (ii) The AO (29) reduces the dimension of the PO (28) from n × d to max{d, n}, thereby simplifying the PO (28); (iii) It is difficult to obtain the value that the PO (28) concentrates on; (iv) The AO problem (29) can be further simplified by AO optimization (33) that only includes estimation error variable β β β, which is easier to analyze than PO (28) . These explanations enable us to effectively analyze the minimizer of the AO problem (29) instead of the more complex PO problem (28).Considering that the elements of g g g and z z z are drawn i.i.d. from N (0, 1), and ϵ ϵ ϵ ∼ N (0, σ 2 I I I d ), the vector expression ∥ β β β∥g g g +c c c ⊤ β β βz z z -2ϵ ϵ ϵ √ γ in AO (29) behaves statistically as a random vector with entriesdrawn i.i.d. from N (0, ∥ β β β∥ 2 + (c c c ⊤ β β β) 2 + 4σ 2 γ ), where I I I d represents a d × d identity matrix. Adopting the approach outlined by [28] , we simplify the first term in AO (29EQUATIONDefining η = ∥u u u∥ and recognizing that max u u u g g g ⊤ u u u = ∥g g g∥ • ∥u u u∥ = η∥g g g∥, and considering h h h ∼ N (0, I I I d ), we reformulate the optimization (30) as:EQUATIONThe formulation ( 31) is a quadratic function of η with the symmetric axis:η s = 2 ∥ β β β∥ 2 + (c c c ⊤ β β β) 2 + 4σ 2 γ • ∥g g g∥ + h h h ⊤ β β β > ∥ β β β∥(∥g g g∥ -∥h h h∥).Additionally, η s (∥g g g∥ + ∥h h h∥) > ∥ β β β∥(∥g g g∥ 2 -∥h h h∥ 2 ). Referring to [29, Lem. B.2], ∥g g g∥ 2 and ∥h h h∥ 2 concentrate around their means n and d, respectively. Consequently, the value around which η s concentrates is nonnegative, due to d/n < 1. Moreover, taking η s into (31), the optimization objective (31) concentrates aroundEQUATIONDrawing on [29, Lem. B.2], ∥g g g∥ 2 , (h h h ⊤ β β β) 2 and h h h ⊤ β β β∥g g g∥ concentrate around their expected values:E[∥g g g∥ 2 ] = n, E(h h h ⊤ β β β) 2 = ∥ β β β∥ 2 and E(h h h ⊤ β β β∥g g g∥) = 0. Besides, define Ω( β β β) := lim n→∞ ∥ β β β∥ 2n . Using analytical methods established by [27, 29, 30] , as n goes to +∞, the optimal minimizer of (32) converges to the optimal minimizer of the following deterministic optimization in probability:EQUATIONHere, we successfully reduced the complex AO problem (29) to a more manageable deterministic optimization problem (33) , effectively focusing only on the estimation error variable β β β for further analysis.Building on the previous analysis, if the optimal solution of optimization ( 33 6). Therefore, it only remains to obtain the optimal value of ρ in optimization (33) that plays the role of ∥ β β β∥. We conclude the estimation error analysis of the SCLS problem (6) with the following theorem. Theorem 4.1. Suppose w w w 0 is the true weight parameter of the original SCLS problem (6) , and w w w * is the optimal solution to the objective function of SCLS (6) . If lim n→∞ d n ∈ (0, 1), the estimation error of SCLS ( 6) is given by the following probability limit:lim n→∞ ∥ w w w * -w w w 0 ∥ P -→ 0.The proof is based on the simplified AO problem (33) and is detailed in in Appendix B Remark 4.2. Theorem 4.1 indicates that, as n goes to ∞, the parameter vector w w w * learned through the SCLS method (6) reliably converges to the actual parameter vector w w w 0 in probability. We then can utilize Theorem 3.4 to establish the estimation error of SPG-LS (1) solved by the SCLS (6) .When applying the SCLS method (6) to solve SPG-LS (1), the validity of the solution w w w * learned by the SCLS method is supported by the following theorem. Theorem 4.3. Suppose w w w 0 is the true weight parameter of the SPG-LS (1), w w w * is the optimal solution learned by SCLS (6) , and w w w * is the optimal solution recovered from w w w * by Theorem 3.4. If lim n→∞ d n ∈ (0, 1), the estimation error of SPG-LS (1) solved by the SCLS ( 6) is given by the following probability limit:lim n→∞ ∥w w w * -w w w 0 ∥ P -→ 0.The proof relies on Theorem 4.1 and can be seen in Appendix C Remark 4.4. Theorem 4.3 demonstrates that, as n goes to ∞, the parameter vector w w w * learned through the SCLS method (6) reliably converges to actual parameter vector w w w 0 in probability. This substantiates the efficacy of the SCLS method (6) in solving SPG-LS (1). 
experiment results: 
 This section outlines numerical experiments conducted on synthetic datasets with high feature dimensions [31] and various levels of sparsity to validate our theoretical claims. In alignment with the methodologies described by [1, 2, 3] , the true parameter w w w 0 is generated randomly with sparsity levels set at k d = 1, 0.1, 0.01, 0.001, where k is the number of nonzero elements in w w w 0 . And, the regularization parameter γ is set to be 0.1, 0.01.For each dataset S = {(x x x i , y i , z i )} n i=1 , the input vector x x x i is drawn i.i.d. from N (0 0 0, I I I d ), the fake output label z i is drawn i.i.d. from N (0, 1). Consistent with the noise model used by [2] , the noise ϵ i in our experiments is drawn i.i.d. from N (0, 0.1 2 ). According to our data generation model (2), the output labels y i are derived via:x x x * i = arg min x x x ∥w w w ⊤ 0 x x x i -z i ∥ 2 + γ∥x x x i -x x x i ∥ 2 , y i = w w w ⊤ 0 x x x i + ϵ i .Using the samples S = {(x x x i , y i , z i )} n i=1 , we employ the SCLS method as described by [3] to address the SPG-LS problem (1) and assess the estimation error ∥w w w * -w w w 0 ∥. The estimation error is averaged over 10 trials to gauge the effectiveness of the SCLS method. Results for d n = 0.5 are shown in Figure 1 . The computational resources are detailed in Appendix E.1. Additional experimental results with other parameter settings can be seen in Appendix E.2. The outcomes depicted in Figure 1 illustrate that the estimation error ∥w w w * -w w w 0 ∥ generated by the SCLS method decreases to 0 as n goes to ∞. This trend corroborates the theoretical predictions established in our Theorem 4.3, thereby affirming the efficacy and reliability of the SCLS method. 
conclusion: 
 In this paper, we apply the CGMT framework to conduct a rigorous theoretical error analysis of the SCLS method proposed by [3] . Specifically, when SCLS ( 6) is applied to tackle a SPG-LS model (1) with x x x ∼ N (0, I I I d ), z z z ∼ N (0, I I I n ) and ϵ ∼ N (0, σ 2 ),if lim n→∞ d n ∈ (0, 1), we establish that:lim n→∞ ∥w w w * -w w w 0 ∥ P -→ 0.This result confirms that the learner w w w * obtained through SCLS (6) accurately estimates the true learner w w w 0 of SPG-LS model. Our empirical findings are consistent with these theoretical results. This theoretical error analysis not only validate the reliability of the SCLS method but also provides a framework for error analysis applicable to other statistical learning algorithms. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: Our paper focuses on theoretical aspects of the SCLS algorithm and uses synthetic data, mitigating risks associated with real-world data misuse.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: Our paper properly credits the original creators [3] of the SCLS algorithm and adheres to the licensing terms of the cited open resources.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification: We don't introduce new assets in our paper.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] ,Justification: Our paper is theoretical and includes numerical verification experiments. It does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: Our paper is theoretical and includes numerical verification experiments. It does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: The SCLS method is currently state-of-the-art for solving SPG-LS, having won the ICML 2022 Outstanding Paper Award [3] . However, [3] lacks theoretical analysis on the error of the SCLS method. To the best of our knowledge, we are the first to investigate the error of the SCLS method. The primary contribution of our paper is to provide a theoretical perspective on the error of the SCLS method under Gaussian assumption. It is worth emphasizing that the Gaussian hypothesis is a commonly used approach for theoretical analysis of algorithms in machine learning [7, 32] . Thus, we investigate the error of the SCLS algorithm limited to Gaussian settings. For future work, we plan to explore extensions of our findings to non-Gaussian input settings, aiming to provide insights into the universality of our results.B Proof of Theorem 4.1Theorem 4.1. Suppose w w w 0 is the true weight parameter of the original SCLS problem (6), and w w w * is the optimal solution to the objective function of SCLS (6) . If lim n→∞ d n ∈ (0, 1), the estimation error of SCLS ( 6) is given by the following probability limit:lim n→∞ ∥ w w w * -w w w 0 ∥ P -→ 0.Proof. Given the simplified AO problem (33), define Then, the Hessian matrixEQUATIONEQUATION)This indicates that ∇ 2 Γ( β β β) is positive definite matrix. Consequently, according to [33] , Γ( β β β) is a strongly convex function of β β β, and β β β * = 0 0 0 is the unique global minimum. Moreover, we note:EQUATIONCombining (36) and (37), the AO problem (33) satisfies the conditions of CGMT. Since ∥ β β β * ∥ → 0 occurs when n → ∞, the analysis of (25) holds:EQUATIONFormulation (38) allows us translate the analysis on the optimal solution ŵ w w * of the approximated SCLS problem (24) to the analysis on corresponding optimal solution w w w * of the original SCLS problem (21) . Therefore, based on the relationship of SCLS problems ( 21) and ( 6), by applying the principles of CGMT, we conclude:lim n→∞ ∥ β β β * ∥ P -→ 0 ⇔ lim n→∞ ∥ w w w * -w w w 0 ∥ P -→ 0.C Proof of Theorem 4.3Theorem 4.3. Suppose w w w 0 is the true weight parameter of the SPG-LS (1), w w w * is the optimal solution learned by SCLS (6) , and w w w * is the optimal solution recovered from w w w * by Theorem 3.4. If lim n→∞ d n ∈ (0, 1), the estimation error of SPG-LS (1) solved by the SCLS ( 6) is given by the following probability limit:lim n→∞ ∥w w w * -w w w 0 ∥ P -→ 0.Proof. According to Theorem 3.4 and formulation (17) ,w w w = √ γ 1 - α w w w, w w w 0 = √ γ 1 -α0 w w w 0 .Then, the difference between the estimated and true parameter vectors can be expressed as:EQUATIONDefine EQUATIONCase 2: If α0 < 0, we set α( w w w) = -1 -∥ w w w∥ 2 . Consequently, α0 ( w w w) = -1 -∥ w w w 0 ∥ 2 . It is important to note that although the expressions for α( w w w) and α0 ( w w w) differ from those in Case 1, the approach and methodology for the error analysis of the SCLS (6) in Case 2 remain analogous to those outlined in Case 1. If ∥ w w w -w w w 0 ∥ → 0, we have α( w w w) = α( w w w). Substituting α( w w w) in ( 20) by its first-order approximation (23) ,α -α0 2 z z z + √ γ 2 X X X( w w w -w w w 0 ) -ϵ ϵ ϵ 2 = 1 2 • ∂ α( w w w) ∂ w w w w w w= w w w0 • ( w w w -w w w 0 )z z z + √ γ 2 X X X( w w w -w w w 0 ) -ϵ ϵ ϵ 2 = √ γ 2 1 √ γ • ∂ α( w w w) ∂ w w w w w w= w w w0 • ( w w w -w w w 0 )z z z + X X X( w w w -w w w 0 ) - 2ϵ ϵ ϵ √ γ 2 .Then, we obtain an approximated SCLS problem corresponding to SCLS (21) :EQUATIONDenote ŵ w w * as the optimal solution to the approximated SCLS problem (44). Then, the estimation error for approximated SCLS (44) is β β β * := ŵ w w * -w w w 0 . Taking advantage of the simple characterization of α( w w w), we can accurately analyze the error in the resulting approximated SCLS problem (44). In other words, if f ( w w w) and f ( w w w) denote the objective functions of SCLS (21) and the approximated SCLS (44), respectively,f ( w w w) = α -α0 2 z z z + √ γ 2 X X X( w w w -w w w 0 ) -ϵ ϵ ϵ 2 , f ( w w w) = √ γ 2 1 √ γ • ∂ α( w w w) ∂ w w w w w w= w w w0 • ( w w w -w w w 0 )z z z + X X X( w w w -w w w 0 ) - 2ϵ ϵ ϵ √ γ 2 ,we haveEQUATIONCompared with SCLS (21), the approximation (44) is tight when ∥ w w w -w w w 0 ∥ → 0, and we later demonstrate that this case occurs independent on the original SCLS (21) as n → +∞. This fact allows us to translate the findings about ŵ w w * obtained for the approximated SCLS problem (44) to corresponding precise outcomes of w w w * for the original SCLS problem (6) .Because γ is a constant, the approximated SCLS problem (44) is equivalent to the following optimization problem:EQUATION)where the optimization variable is changed from w w w to β β β := w w w -w w w 0 , and c c c:= c c c( w w w 0 , γ) = 1 √ γ • ∂ α( w w w) ∂ w w w w w w= w w w0 = 1 √ γ • w w w0 √ 1-∥ w w w0∥ 2 .The normalization of the loss function is appropriately applied, which does not alter the optimal solution. Based on the analysis on formulation (45), when ∥ β β β∥ → 0, the approximated SCLS problem (44) becomes equivalent to SCLS (21) . Consequently, the analysis of the optimal cost β β β * in SCLS ( 21) can be replaced by the analysis of the optimal solution β β β * in optimization (46). nonnegative. Additionally, taking η s into (31), the objective (51) concentrates aroundEQUATIONAccording to [29, Lem. B.2], ∥g g g∥ 2 , (h h h ⊤ β β β) 2 and h h h ⊤ β β β∥g g g∥ concentrate around their means:E[∥g g g∥ 2 ] = n, E(h h h ⊤ β β β) 2 = ∥ β β β∥ 2 and E(h h h ⊤ β β β∥g g g∥) = 0. Besides, define Ω( β β β) := lim n→∞ ∥ β β β∥ 2n . Following the methodology used by [27, 29, 30] , as n → +∞, the optimal minimizer of (52) converges to the optimal minimizer of the following deterministic optimization in probability:EQUATION)Here, we complete the simplifications by reducing the AO problem (49) to an equivalent optimization (53) that now only involves the estimation error variable β β β.Building on the previous analysis, if the optimal solution of optimization ( 53) is ∥ β β β∥ = ρ * , we have∥ β β β ϕSCLS ∥ P -→ ρ * for AO problem (49).Then, by virtue of CGMT, ∥ β β β ΦSCLS ∥ P -→ ρ * also holds for PO problem (48). If ρ * further satisfies ρ * = 0, based on the relationship between the original and approximated SCLS in Section 4.1, we have ∥ w w w -w w w 0 ∥ P -→ 0 for SCLS problems ( 21) and ( 6). Therefore, it only remains to obtain the optimal value of ρ in optimization (53) that plays the role of ∥ β β β∥. We conclude the estimation error analysis of the SCLS problem (6) with the following theorem.Theorem D.1. Suppose w w w 0 is the true weight parameter of the original SCLS problem (6), and w w w * is the optimal solution to the objective function of SCLS (6) . If lim n→∞ d n ∈ (0, 1), the estimation error of SCLS ( 6) is given by the following probability limit:lim n→∞ ∥ w w w * -w w w 0 ∥ P -→ 0.Proof. Given the simplified AO problem (53), defineEQUATIONLet β β β * be the optimal solution to Γ( β β β), thenEQUATIONIf λ represents the eigenvalue of c c cc c c ⊤ ,|λI I I d -c c cc c c ⊤ | = λ d-1 |λ -c c c ⊤ c c c| = 0 ⇒ λ = 0 or ∥c c c∥ 2 .Then, the Hessian matrixEQUATIONThis indicates that ∇ 2 Γ( β β β) is positive definite matrix. Consequently, according to [33] , Γ( β β β) is a strongly convex function of β β β, and β β β * = 0 0 0 is the unique global minimum. Moreover, we note:EQUATIONCombining ( 56) and (57), the AO problem (53) satisfies the conditions of CGMT. Since ∥ β β β * ∥ → 0 occurs when n goes to ∞, the analysis of (25) holds:EQUATIONFormulation (58) allows us translate the analysis on the optimal solution ŵ w w * of the approximated SCLS problem (44) to the analysis on corresponding optimal solution w w w * of the original SCLS problem (21) . Therefore, by applying the principles of CGMT, we conclude:lim n→∞ ∥ β β β * ∥ P -→ 0 ⇔ lim n→∞ ∥ w w w * -w w w 0 ∥ P -→ 0.When applying the SCLS method ( 6) to solve SPG-LS (1), the reliability of the SCLS method ( 6) in solving SPG-LS ( 1) is supported by the following theorem.. Theorem D.2. Suppose w w w 0 is the true weight parameter of the SPG-LS (1), w w w * is the optimal solution learned by SCLS (6) , and w w w * is the optimal solution recovered from w w w * by Theorem 3.4. If lim n→∞ d n ∈ (0, 1), the estimation error of SPG-LS (1) solved by the SCLS ( 6) is given by the following probability limit:lim n→∞ ∥w w w * -w w w 0 ∥ P -→ 0.Proof. According to Theorem 3.4 and formulation (17) ,w w w = √ γ 1 - α w w w, w w w 0 = √ γ 1 -α0 w w w 0 .Then, the difference between the estimated and true parameter vectors can be expressed as:EQUATIONDefineEQUATIONBased on (14) ,EQUATIONCombining (59) ∼ (61), we get:∥w w w * -w w w 0 ∥ = ∂τ ( w w w) ∂ w w w w w w= w w w0 ( w w w * -w w w 0 ) + O(∥ w w w * -w w w 0 ∥ 2 ) ≤ ∂τ ( w w w) ∂ w w w w w w= w w w0 • ∥ w w w * -w w w 0 ∥ + O(∥ w w w -w w w 0 ∥ 2 ).Invoking Theorem D.1, we know:lim n→∞ ∥ w w w * -w w w 0 ∥ P -→ 0,which implies:lim n→∞ ∥w w w * -w w w 0 ∥ P -→ 0.All simulations are implemented using MATLAB R2021b on a PC running Windows 10 Intel(R) Xeon(R) E5-2650 v4 CPU (2.2GHz) and 64GB RAM. We report the results of synthetic datasets in the main paper and defer other results to the supplementary material.NeurIPS Paper Checklist 


Decision: The spherically constrained least squares reformulation (SCLS) method proposed in a prior paper that won ICML 2022 Outstanding Paper Award is the main method for solving the Stackelberg prediction game with least squares loss. The current paper further enhances the theoretical framework of the SCLS method by providing a theoretical error analysis. The theoretical results indicate that the learner obtained through the SCLS method reliably converges to the actual learner vector of the Stackelberg prediction game. The reviewers were enthusiastic about this paper, nevertheless it feels that the current write-up can be improved in order to get a spotlight presentation (especially in terms of motivation), so the AC recommends acceptance as a poster.

Reviews: review: paper_summary: paper_summary: The spherically constrained least squares reformulation (SCLS) method proposed in paper [3] is the state-of-the-art method for solving the Stackelberg prediction game with least squares loss (SPG-LS), and the paper [3] has won the ICML 2022 Outstanding Paper Award. This paper further enhances the theoretical framework of the SCLS method by providing a theoretical error analysis using the Convex Gaussian Min-Max Theorem (CGMT). The theoretical results indicate that the learner obtained through the SCLS method reliably converges to the actual learner vector of the Stackelberg prediction game. Additionally, the authors conduct experiments to validate their theorems, with the experimental results aligning with their theoretical predictions.


[3] Jiali Wang, Wen Huang, Rujun Jiang, Xudong Li, and Alex L. Wang. Solving Stackelberg prediction game with least squares loss via spherically constrained least squares reformulation. In ICML, volume 162, pages 22665–22679, 2022.
strength_weakness: strength_weakness: $\bullet$ This paper transforms a PO problem related to the error of the SCLS method into a simplified AO problem, but the motivation for this transformation seems weak. More specific reasons for this transformation are needed.

$\bullet$ According to Theorem 2.6, the equation between lines 154-155 should be a result of asymptotic convergence. However, the condition ``$n \to \infty$’’ is missing in the description.


$\bullet$ According to (2), the authors translate the findings of the approximated SCLS problem to that of the original SCLS problem if $\Vert\tilde{w}-\tilde{w}_0\Vert\to 0$ happens independently. Which place reflects that this condition will occur?
questions: questions: $\bullet$ None.
limitations: limitations: $\bullet$ Yes, the authors have adequately addressed the limitations.
paper_summary: paper_summary: The spherically constrained least squares reformulation method proposed by Jiali et al. has shown superior performance in addressing the issues of the Stackelberg prediction game. This paper aims to analyze the error between the estimators and the ground truth. The main theory shows that the estimation error approaches to zero in probability. The empirical studies verify the claims appear in the paper.
strength_weakness: strength_weakness: - As pointed by the author in the checklist, the main weakness is that this paper assumes the Gaussian inputs. This paper may motivate further research to remove or weaken the assumptions.
- Eq.(13) and Eq.(14) miss the transpose symbol $T$.
- Some derivations need to be more clear, for example, in Line 211, how can the author derive the Eq.(29)?
- The asymptotic results of CGMT relies on $d$, while Theorems 3.1 and 3.2 holds when $\lim_{n\to infty}$. Could the authors say something about this?
questions: questions: - How can the authors derive Eq.(29)?
- Could the authors specify the feasibility of replacing $d$ required by CGMT with $n$ in their conclusions.
limitations: limitations: Yes
paper_summary: paper_summary: The paper investigates the estimation error of the learner obtained through the SCLS method proposed in [3] in comparison to the actual learner. It redefines the estimation error of the SCLS method as a Primary Optimization (PO) problem and applies the Convex Gaussian min-max theorem (CGMT) to convert the PO problem into an Auxiliary Optimization (AO) problem. Subsequently, a theoretical error analysis for the SCLS method is presented based on this simplified AO problem. This analysis validates the accuracy of the strategy generated by the SCLS method from [3].
strength_weakness: strength_weakness: 1. The reason for ``the lack of theoretical analysis on the error of the SCLS method limits its large-scale applications'' is unclear, which is very important to the motivation of this paper. Therefore, I failed to understand the importance of studying this problem, as it appears to be artificially created.

2. The notations in this article are somewhat ambiguous, hindering readability. For instance, the notations $d\in \mathbb{N}$ and $n=n(d)$ in Definition 2.5 (GMT admissible sequence) are identical to the notation for the data dimension $X\in \mathbb{R}^{n\times d}$.

3. The assumption ``The data $X$ is drawn i.i.d. from $N(0,1)$'' appears to be overly restrictive within the framework of the Stackelberg prediction game.

4. Section 2.1 of this paper is redundant as all the relevant information is extracted from reference [3].
questions: questions: 1. Line 61: What is the main distinction between $w_0$ and $w^*$?
2. Line 114: The notation ($\omega,~\alpha$) appears twice.
3. Line 155: The authors state that "a challenging PO problem can be replaced with a simplified AO problem." Could the authors provide more explanation on where the challenge in the PO problem lies and why the AO problem is simpler? Additionally, on page 7, line 213, why is PO (28) more complex than AO (29)? Where does the difficulty in (28) lie?
4. Line 161: $(u)$ should be changed to $f^*(u)$.
5. Line 170: The authors should explain why the second equation in (16) is valid.
6. Line 178: I am curious as to why the variables $\tilde{w_0}$ and $\tilde{\alpha_0}$ are not included as variables in the objective function of problem (21).
7. Line 202: As the authors state, "This equivalence allows for the substitution of the analysis of the optimal cost $\tilde{\beta}^*$ in SCLS (21) with the analysis of the optimal solution $\hat{\beta}^*$ in optimization (26)." We can see that (21) is nonconvex, while (26) is an unconstrained convex optimization. Does this mean the authors have equivalently reformulated a nonconvex optimization problem into a convex optimization?
8. It is reasonable to consider whether the limit of $\lim_{n\rightarrow \infty}\frac{d}{n}$ falls within the interval $[(0,1)]$ since this assumption is not adopted in [3]. Furthermore, it is impractical to assume that $d/n < 1$, as the features of the data may surpass the sample size.
9. In experiments, why the true parameter $w_0$ is generated randomly?
limitations: limitations: NA
paper_summary: paper_summary: The Stackelberg Prediction Game (SPG) models with the least squares loss variant (SPG-LS) gaining attention. The spherically constrained least squares (SCLS) method is the latest state-of-the-art method for solving the SPG-LS problem. The authors address the lack of theoretical error analysis for the SCLS method. By transforming the estimation error into an Auxiliary Optimization (AO) problem using the Convex Gaussian Min-Max Theorem (CGMT), the authors provide a theoretical error analysis, confirming the SCLS method's reliability. Experimental results validate the theorems.
strength_weakness: strength_weakness: 1. The original paper of the SCLS method focuses on optimization (9), but the authors explore the SCLS problem (6). What are the differences between (6) and (9)? Why can the authors replace optimization (9) with (6)?

2. How do the authors derive optimization (32) from (31)?

3. There is a remark for Theorem 3.2, however, Theorem 3.1 lacks explanation.  The authors should add explanatory content to Theorem 3.1 to improve its readability.

4. Theorem 3.1 appears very similar to Theorem 3.2. What’s the relationship between Theorem 3.1 and Theorem 3.2?
questions: questions: See the Weaknesses.
limitations: limitations: In the Appendix, the limitations are discussed.

Comments: title: Appreciation to Reviewer XvKF
Appreciation to Reviewer rMtE
Appreciation for Raising Score
responce
response
Kindly Requesting Confirmation on Responses
comment: Thank you very much for your acknowledgment and efforts.
Thank you for the author's response. My issue has been resolved, and I will maintain my score.
Thank you very much for your acknowledgment and efforts.
We deeply appreciate your acknowledgment, praise, and efforts.
We appreciate your decision to raise our score.  We will further emphasize our contribution  in the revision.
I would like to thank the authors for their responses. While I may not be fully familiar with the topic of error analysis, I remain uncertain about the sufficiency of the authors' contribution. However, after considering the feedback from other reviewers, I have decided to raise the score to 5.
The author did a good job in answering my questions. I am happy to recommend the acceptance.
Dear Reviewer  PFXk,

We hope this message finds you well. I am reaching out to kindly request your prompt response to confirm whether our responses adequately address your queries. We sincerely thank you for your time and effort during this discussion period. Your timely feedback is greatly appreciated.
Thanks the authors for the reply. They have addressed my questions well. I am pleased to keep my positive score.