Error Analysis of Spherically Constrained Least Squares Reformulation in Solving the Stackelberg Prediction Game
Authors: Xiyuan Li
Weiwei Liu
Venue: NeurIPS 2024 poster (2024)
Keywords: Stackelberg Prediction Game
Primary area: learning_theory

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.

Error Analysis of Spherically Constrained Least Squares Reformulation in Solving the Stackelberg Prediction Game
Xiyuan Li Weiwei Liu"
School of Computer Science, Wuhan University National Engineering Research Center for Multimedia Software, Wuhan University Institute of Artificial Intelligence, Wuhan University
Hubei Key Laboratory of Multimedia and Network Communication Engineering, Wuhan University Lee cree_xiyunneee @ outlook.com, liuweiwei863 @ gmmil.com
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 SPGs are often NP-hard, notable special case involving the least squares loss (SPG-LS) has gained significant research attention recently The latest state-of-the- method for solving the SPG-LS problem is the spherically constrained least squares reformulation (SCLS) method proposed in the work of [ However, the paper B 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 a Primary Optimization (PO) problem and utilize the Convex Gaussian min-max theorem (CGMT) to transform the PO problem into Auxiliary Optimization (AO) problem. Subsequently, we provide a theoretical error analysis for the SCLS method based 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 theorems, and the results are in excellent agreement with our theoretical predictions.
Introduction
The Stackelberg prediction games (SPGs) play prominent roles in various applications of the machine learning field, such as intrusion detection 41, spam filtering (5), and malware detection [6] 77. SPG characterizes the interactions between two players, learner and a data provider (attacker), during the training process of various machine learning algorithms (8] 9 [0] [T]] 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 '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 I12
To overcome the NP-hard nature of SPGs, 3 focus 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 set of sample tuples denoted by S = {(z, Vt, 2;) 1
1==1 where
"Corresponding author: Weiwei Liu @ .omm.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Z; E IR is imput data with d' features, Yi is the true output label of z; and 2; is the label that the data provider aims to achieve. The learner of SPG-LS aims to train a linear predictor w R to best estimate the true output label yi of the fake data oj by minimizing the least squares loss:
1 Σ w x --ll
w = arg min
W
Meanwhile, the data provider of SPG-LS, with full knowledge of the learner's predictive model w, selects the following least squares attacking strategy (i.e., modifying the data &;) to make the corresponding prediction w x; close to the desired label ag:
x; = arg min w Tá z. - z1l1² + y1|z; - =
where y > 0 is a regularizer to adjust the trade-off between the deviation from the original data ø; and closeness the target z,. Thus, the SPG-LS model can be expressed as the following bi-level optimization problem, as described in 12 3
min X w yll. W
s.t. X arg min [ z11² + x/l XI
x
where X =
Fnn) T E Raxd is the input sample matrix, y/ = (y1, 3/2 Vy.) E IR" the vector of true output labels, and z (21, 22, 2,,) IR" the vector of labels that the attacker aims to achieve. Moreover, || denotes the Euclidean norm (12) unless otherwise specified.
(z) 22,
There have been several studies solving the SPG-LS (T) to determine the Stackelberg equilibrium point between the learner and the data provider. The imitial step in reformulating SPG-LS 1 is taken by M. who provides 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 solve multiple semidefinite programs (SDPs). Later, 22 improves upon M by showing that the SPG-LS ( can be globally solved by reducing a single SDP to second -oder cone program (SOCP). Despite being faster than the QFP method, the SOCP method is still not well-suited for large-scale SPG-LS [I) due to time-consuming spectral decomposition. Recently, 33 proposes a spherically constrained least squares reformulation (SCL.) method, addressing the mentinee issues with a novel nonlinear change of variables. Furthermore, [3] demonstrates that the SCLS method outperforms the SOCP method and currently the state-of-the-art for solving SPG-LS (T). 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") estimated by the SCLS method and the true learner (denoted as wa) to validate the reliability of w". Specifically, we assume the samples S = {(I;. Vs. 2,)) are generated by the following black box model:
X arg min WG- 2112 + + XI y= XXX'o + E,
(2)
x
where wo E Rd represents the "true" weight parameter of the real learner, and e (c1, .2, ,,,)' T E R" is the noise vector. Moreover, the entries of X and z are drawn i.i.d. from (0, 1); the entries of are drawn i..dd from (N(0, o²); and we assume lim d E (0, 1). Given X, z, and y generated by this model (2), we solve SPG-LS (I by the SCLS method to obtain w" that is used to estimate the target vector Wy. Our task is to measure the optimal estimation error of the SCLS method, represented by ||w" ww
We start by formulating optimization problem regarding the estimation enror (e.t. B == Wo) of the SCLS method. Subsequently, we convert this optimization problem into a Primary Optimization (PO) problem, employing the Fenchel-Morean theorem [3]. 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 theoretical error analysis of the SCLS method based on the AO problem. Our main theoretical result can be summarized as follows:
lim || woll E. O,
(3)
22000
2

---

which guarantees the reliability of 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 oc, the parameter vector w" learned through the SCLS method converges to actual parameter vector wo in probability, which aligns excellently with our theoretical predictions.
1.1 Outline
The structure of the remaining sections in this paper is organized as follows: Additional related work is discussed in Appendix [ 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 the approximated SCLS method and establish the relationship between the original and the approximated SCLS method; In Section 4.22 the estimation error of the approximated SCLS method is transformed into PO problem; In Section 4.3 simplify the PO problem to an AO problem using CGMT; In Section 4.44, we conduct an estimation error analysis 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 Section 6 Moreover, the limitations of our work are detailed in Appendix
2
Related Work
2.1 The Stackelberg prediction game
Stackelberg Prediction Games (SPGs) were initially introduced by [14). drawing inspiration from Stackelberg competition- model initially developed to deseribe market behaviors. notable parallel can be drawn with Stackelberg Security Games (SSGs), as detailed by 44] 6]. In SSGs, 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 polynomial number of queries to the attacker's model. While both SPG and SSG frame the learning of optimal strategy as a bilevel optimization problem, SPGs are distinctly designed to counteract manipulation within machine learning algorithms (
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 solution approach, which was later enhanced by (2). Subsequently, K introduced the Spherical Constrained Least Squares (SCLS) method, currently acknowledged as the state-of-the afttt--r. This paper aims to further elucidate the eπrоr dynamics of the SCLS method (18). thereby solidifying its theoretical foundation for broader practical application.
2.2
The Gaussian Min-max Theorem
The Convex Gaussian Min-max Theorem (CGMT) framework, first introduced by [19], serves as potent analytical tool extensively utilized evaluate the performance of solutions within non-smooth regularized convex optimization problems. This framework is derived from Gordon's Gaussian Min- max 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 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 thorough analysis of the estimation error associated with the SCLS method.
3

---

Preliminaries
3.1 The SCLS method
This section provides comprehensive overview of the SCLS method as introduced by 3 Expanding
upon previous studies by 21 3 reformulates SPG-LS (I) program (QFP) utilizing the Bherman-Morriss formula [26]
into the following quadratic fractional
1 zw w + Xw
T
inf
1 + w
Moreover, introduces an augmented variable a w w/ and further reformulate QFP as:
02 Xw
inf v(w, a) - 1 1 a
yl? s.t. w w raa
(5)
w,a
Subsequently, 3 makes assumption on nonemptiness of the optimal solution set QFP (
Assumption 3.1 (3). Assume that the optimal solution set of (5) (or equivalently, is nonempty.
Under Assumption 3.1 employs a nonlinear variable transformation recast the QFP
as
spherical constrained least squares (SCLS) problem:
VT
2
min A
X
(y
à =1
(6)
2
where á and á are defined in Lemmas 3.2 and 3.3 Upon identifying feasible solution QFP
3
introduces Lemma 3.2 to construct feasible solution in SCLS (6), while Lemma 3.3 describes
the inverse transformation.
Lemma 3.2
Suppose (w, oi) is a feasible solution of QFP 5 Then (w, ā.) defined as
2
w =
w and ā =
+)
a +11
feasible SCLS and v(w, a) viw a).
Lemma 3.3 Suppose (w, (i) is feasible to SCLS 6 with + 1. Then a.), defined as
V w and a = 1 1+a
w = 1 ā
(8)
- ā
is feasible to QFP (5) and ūww, a) = v(w, a).
Let o* and ö* represent the optimal values of QFP (5) and SCLS (6). respectively. Subsequently. B presents Theorem to elucidate the relationship between the solutions of QFP (5) and SCLS (
Theorem 3.4 (B)) Given Assumption 3.1 then there exists an optimal solution (w, â) to SCLSS with â # 1. Moreover, (w,o) o.,, defined by is an optimal solution to 3 and o" vww a)
i(w, à 0*
Theorem 3.4 indicates that optimal solution of SCLS (6) can be utilized to recover optimal solution of SPG-LS (T). Additionally, the converse this theorem also holds, as demonstrated by 3 Specifically, if (w, o:) is optimal solution to QFP 5), (w, ā), as defined by ( is also optimal solution to SCLS (6).
It is important to note that focus on a compact form of SCLS 66:
min q(r), s.l. T
where v(r) || (y 2 2/2) i
and
W
Due to the equivalence of
à
SCLS problems and .his paper focus on the SCLS
6

---

3.2 The Convex Gaussian Min-max Theorem
The Convex Gaussian Min-max Theorem (CGMT) originates from Gordon's Gaussian Min-max Theorem (GMT) (21, which provides probabilistic bounds the optimal cost of PO problem via 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(1))
pb((tt indexed by d, with ( E Rand g(d) E R", A(d) IR B C Rd S C R", sil))
g(() .h S(d) s(d)
dEN
(d)
B
x
(dd) R and ndd), is said to be admissible if, for each d E N, S and Sa are compact sets and wi(() is continuous on its domain. Onwards, we will drop the superscript (d) from G(d), g(d) h(4)
sequence (Gld) ,g())
(d) h (1) S S. 1p(1)) deN defines a sequence of min-max problems
( (G) = min
max u GB + (6(0) (B, u)
(10)
B wES!")
(ld) (g. h) = min BES
max uE
|| uuuus + | B + 1b(0) (B,u)
(11)
Importantly, the formulation I0 is called Primary Optimization (PO) and the formulation 11 is called Auxiliary Optimization (AO). Additionally, let ² (G) denote the optimal minimizer of the
PO problem (10). and ( hg denote the optimal minimizer of the AO problem 11 Define
old) s(d) TR follows,
( (B:gh)) = max | u+ // B (B,
(12)
WESt
Clearly, (g. min Best uld) (B: h). For sequence of random variables (2((4) JaEN and
constant E IR, (d) - c denotes convergence in probability, i.e., Ve > 0, lima- IP ((1x((1)) -cl >
= O. Based on the GMT admissible sequence and the notation introduced above, we present the
CGMT below.
Theorem 3.6 (CGMT 27 Let (G g())
(()) h S(()), s(d) sb((1) JdEN be GMT admissible se- quence as in Definition 3.5 for which additionally the entries of G. g. are drawn i.i.d. from (0, 1).
Let ( (G), (((0) [g. h) be the optimal costs, and, B 4. (G). Blal (g.h) h) the corresponding optimal
minimizers of the PO and AO problems in (10) and [1). The following three statements hold
(i) For any E N and e E IR, P() (G) < <)) S 2P (()) (g. h) S Se).
(ii) For any d E N. Sf s(d) are convex, and, (b (.,-) is convex-concave on s/d) S( then, for any μ E IR and t > 0,
(d)
P( (4) (G) nl) > 1) S (p) nl) > 1)
(ii) Assume the conditions (ii) hold for all d E N. Let [|:]] denote some norm in TRd and recull
12). If. there exist constants (independent of d) n², p² and > such that
(a) (g.h) P. k+)"(b) (1) (g. hlll P3 p", (c) with probability one in the limit d + co
(uld) > (( (g. h) + T (1BB1 (d) (g. h))² vB E s(
then,
[ (d) (G)ll _
5

---

Theorem 3.6 indicates that, if the optimal cost ő(g. h) of converges to some value μ. the same holds true for (G) of PO (10). Furthermore, under appropriate additional assumptions, the optimal solutions of the AO and PO problems are also closely related by
B [G)l - (g, h)ll-
This suggests that within the CGMT framework, a challenging PO problem can be replaced with simplified AO problem, from which the optimal solution of the PO problem be accurately inferred [27]. Subsequently, we rewrite the estimation error of the SCLS method (6) in the form of PO problem (I0) and analyze the minimizer of the simplified AO problem instead.
3.3 Basic Concept
Conjugate pairs: Consider a function f: RR + R. The Fenchel conjugate of f. denoted by f", is defined as f* f*() sup. fv)) which is always convex and lower semi-continuous, By the Fenchel-Moreau theorem [13], if f is both convex and continuous, then f(v) sup (u). In this paper, we consider the following conjugate pairs for the l2 norm:
f(v) = ||a| ++ (u) = ||ul|
(13)
4
First-order approximation: Assume f is differentiable. According to 13 Theorem 23.4]:
s(w) - ((w)) + (f(w)]
O(11B])))
(14)
where w + B and f(wo)
0f Tw w=
The linearization of f(-) around the interest Wo is
f(w) f(wo) [f(w))] B.
(15)
As ||8|| approaches 0, fw) closely approximates f(w).
4 The Error Analysis for the SCLS method
4.1 From the SCLS Method to PO
Given that the sample (x) is generated by black box model 2
we integrate SPG-L.S (1 and
QFP 4 as follows:
0g + Xwo
y = X=Wo WD +
(16)
+ 00
where Ogg _w wo/7. Drawing inspiration from Lemmas 3.2 and
3.3
we define
Wo = Vlago + 1) Wo. āu = 0g with the inverses: wo = āo
2
Wu. == 1 âg
(17)
ag + 1'
1
This representation of wa denotes the true weight parameter of SCLS 6 Notably, (wo, āo) is
valid as long as Ogg 2 0 and ão # 1, which conforms to (w, ā) defined by 3. Specifically, For
ag = w.j wo E (1, +o0), dy > 0; For ag = w E (0,1), 1), āg < 0. Additionally, (Wo, âo) satisfies
the constraint of SCLS (6. due to
7(00 1)2 w wo + (op 1)²
400 + (au - 1)2 1. (Oo + 1)2
w wo + ai
(18)
(oo + 1)2
Taking 17 into [6), the expression of can be rewritten as:
On + XWo
0g
V X
2
+
2 +
Wo + te
+1
2( + 1)
2
V7(00 +1)
2
ōg
7
z
2 +
Xwo
+
te
(19)
2
2
2

---

Substituting in SCLS 6 with
199
7
V
-00 VT
2
X
2
2
X
i +
Xwo +
2
00
2
X (w wn)
(20)
2
Combining formulations
6
188
and 20).. SCLS
6 is equivalent to the optimization problem:
min 1.
α
000
x (w- wp)
s.t. w
+ 1, wo wo + a 1.
(21)
2
Let "" denote the optimal solution to original SCLSS problem (6) then, the estimation error for
SCLS (21) is B := "" Wg. To explore the optimal estimation error for SCLS (21 under different
conditions of āg. we consider two scenarios: Case 1: āo > set a(w)
? Case
If āo < 0, set ((w)) - / |
Both cases lead to consistent error analysis outcomes for SCLS 66. but this paper primarily discusses Case I, with Case 2 detailed in Appendix D According to formulation (14)
(ā(w)
dā
(w)
a i = ((o))
i
wo) + O -wol
(22)
Ow
The first-order approximation of ((w) is:
0ū
(w)) = wp)
wn)
(23)
iw
When
+ -
a(w) converges (w) Using this approximation in SCLS (0) leads to
objective:
0
dā(w)
v7 X
2
X ii-
wo)
(w
wo)= z +
(w w))
2
2 au
10
V7
dā(ū
2E ||
wp) )=+ + X(u wo
Ow
d
D0
v7
Then, obtain approximated problem corresponding to SCLS
21
dā w
2e 2
min
(w wo) +
w w
(24)
Ew
i=wo
Let " denote the optimal solution to the approximated SCLS problem 24 then, the estimation error for approximated SCLS (44 is 3 : ~ wy. Leveraging the simplified representation of ((w). we can conduct precise error analysis for this approximated model (24). Furthermore, if fw)) and f denote the objective functions of SCLS
21 and the approximated version (44.. respectively,
f(w)= = a åg
VT
2
+
X (
wo)
2
2
/ 1
dā(w)
2E ? V7
f(w)
(w wn + X(@ wo)
2
w
we have
lim we
f(w) = f(w).
(25)
Compared with SCLS 21 the approximation 24 is tight when || fildew - woll goes to 0. We later goes co, independent of the original translate the findings about ~" obtained for the approximated SCLS problem (24) to corresponding outcomes of /" for the original SCLS problem (6). Given the constancy 7 the approximated SCLS problem (24) simplifies to:
demonstrate that this convergence condition is satisfied
SCLS (1 This fact allows
2E
min c B2 + X3
(26)
7

---

where B = Wo. and c: c(wo 7) VF
Ocit
i v7 Woll The normalization
She
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 B in
SCLS 21 with the analysis of the optimal solution 3 in the first-order optimization (26
4.2 From PO to AO
A key transformation in our analysis involves converting the optimization (6) into PO problem within the CGMT framework. We apply conjugate pairs (13) for optimization (26
2E 11
2u Te 1
min B
C Bz BBB
min max
X3 + c B u
(27)
B
72
4
where B E RRd E RR. Using formulations
11) and 27 the PO problem associated with (66 is:
1
PSCIS (X)
min max
x + (B)
(28)
B n
where : c 2
2u
1 4
Given that the entries of X are drawn i...d. from ((,0 1) satisfies the conditions of Theorem with a simplified AO problem using
v7
and (B, is convex-concave function, the PO problem 28
3.6 Consequently, we replace the challenging PO problem 28 CGMT:
2u Te
|uul
ØSCLS h) = -min max- - [1131g T u /2ul/ B c ==
B
V7
4
+ cT [[1BB]] 2x
u | T |
min max-
(29)
n
where the entries of g and are drawn i.i.d. from NN 1). Suppose Bosaus represents the optimal
solutions of the PO problem 28 and B danss denotes the optimal solutions of the AO problem 29
3.6 if || docis - p², then |B Bassssll _ p² The reasons why PO
According to Theorem
(8
more complex than AO (29 and the difficulties of (28) are summarized (i) The PO
28 contains
the matrix X xdd and the challenge lies in processing matrices. the AO
(29
only contains
vectors with dimensions or n,, which are easier to handle than matrices; (ii) The AO
29
reduces
the dimension of the PO (28) from d to max/d, n), thereby simplifying the PO
28 (tii) It
is difficult to obtain the value that the PO (88 concentrates on; (ic) The AO problem
(29 can be
further simplified by AO optimization (33 that only includes estimation error variable B, which is
easier to analyze than PO (28). These explanations enable us effectively analyze the minimizer of
the AO problem
29 instead of the more complex PO problem (28).
4.3 Simplification for AO
Considering that the elements of g and are drawn i.idd from (0, 1). and e NNO0, o'Ia), the vector expression || T Bz
2c in AO 29h behaves statistically random vector with entries vP
drawn i..dd from (O || 1 + (c B)²
2g² -
where Ia represents a x d identity matrix. Adopting
the approach outlined by (28). we simplify the first term in AO (9) to /18 + (c B)2 + 1a2 9 w:
min max 1
n ( [1] (c B)² + 2
y g u + ||u|| 3 |
(30)
Defining " |u and recognizing that max, g Tu- |g ||u|| I2), we reformulate the optimization (30 as:
n]lg|1, and considering
min max ] 720 n (v |1 + (c 3)2 + 2 || n nh B 7
(31)
8

---

The formulation 31 is a quadratic function of 17 with the symmetric axis:
1/a 2 ( |B (cT
2
9 + h
|| [Ail).
Additionally, nh (1 concentrate around their means n and d, respectively. Consequently, the value around which Y, concentrates is nonnegative, due to d/n < 1. Moreover, taking 7is into (31) the optimization objective
||bl]) |
[²) Referring to 29 Lem. B.2], l and ||A||?
(31 concentrates around
( (v1811 (cT
4
lgg| + B)
min B
(11B] + (c B)² 2 |[g|| 2- + (h B)² 2h B |18| + B)2 + 402
min B
(32)
Drawing on 29 Lem. B.2], | (h 3)² and h ||1 concentrate around their expected values:
|||g||
= n, E(h B) = |181 and E(h B| g = 0. Besides, define 9xß² := lim ||
Using analytical methods established by 227 29 301,
goes to +oo, the optimal minimizer of converges to the optimal minimizer of the following deterministic optimization in probability:
min | (c 3) +2(B) 4a²
(33)
Here, we successfully reduced the complex AO problem (29) to more manageable deterministic optimization problem (33), effectively focusing only on the estimation error variable B for further analysis.
4.4 Error Analysis
Building on the previous analysis, if the optimal solution of optimization (33 |1B = p², we have
||B decus
p for AO problem (29). Then, by virtue of CGMT, ||B &scus p² also holds for
PO problem
28
If p" further satisties p" 0, based on the relationship between the original and
approximated SCLS in Section 4.1 we have || - woll - 0 for SCLS problems (21) and (6). Therefore, only remains to obtain the optimal value of p 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 is the true weight parameter the original SCLS problem (6). and i
the optimal solution to the objective function of SCLS (6). lom d E (0, 1), the estimation error of SCLS (6) is given by the following probability limul:
x
lim 20-000
woll 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 iindicates that, as n goes to co, the parameter vector w' learned through the SCLS method (6) reliably converges the actual parameter vector wo probability. We then can utilize Theorem 3.4 to establish the estimation error of SPG-LS | solved by the SCLS (
When applying the SCLS method (6) to solve SPG-LS (T. the validity of the solution wn learned by the SCLS method is supported by the following theorem.
Theorem 4.3. Suppose wn is the true weight parameter of the SPG-LS 7 "" is the optimal solution learned by SCLS (6) and w" is the optimal solution recovered from w by Theorem 3.4 If lim,- E (0, 1), the estimation error of SPG-LS 1 solved by the SCLS given by the following probability limit:
lim Iww 220000
woll P O.
The proof relies Theorem 4.1 and can be seen in Appendix
Remark 4.4. Theorem 4.3 demonstrates that,
goes oc, the parameter vector w" learned through the SCLSS method 6 reliably converges actual parameter vector wo in probability. This substantiates the efficacy of the SCLS method ( in solving SPG-LS (

---

Experiment Results
This section outlines numerical experiments conducted synthetic datasets with high feature dimensions [31] and various levels of sparsity to validate our theoretical claims. In alignment with the methodologies described by 2 R the true parameter wo generated randomly with sparsity levels set at / 1, 0.1, 0.01, 0.001, where k is the number of nonzero elements in Wo. And, the regularization parameter y is set to be 0.1,
For each dataset $ { Mr, 2,) output label 2, drawn i.i.d. from (O, 1). Consistent with the noise model used by (2). the noise 6, in our experiments is drawn i.i.d. from NomN((0,)))) (0, According to our data generation model (2). the output labels ys are derived via:
= 1i=1 the input vector æ; is drawn i.i.d. from (00, Ia), the fake
z arg min Iwl 2; zill² + 111x; 2; 2212, = wi + c..
#
Using the samples S ( Ui 23)] f=1 employ the SCLS method described by [3] to address the SPG-LS problem
(T) and assess the estimation error || - Woll- The estimation error is averaged the SCLS method. Results for = 0.5 are shown in
over 10 trials to gauge the effectiveness Figure The computational resources are detailed in Appendix [E.T] Additional experimental results with other parameter settings can be seen Appendix
Ad--1
033
Sparts
Auh 0.33
0.100
1.0
1.2
141
12000
14000
5000
12000
M4000
(a) 0.1
(b) 0.01.
Figure 1: The change of I|w" woll with n for SCLS method under different Sparsity k/d.
The outcomes depicted in Figure] 1 illustrate that the estimation error I|w= wo generated by the SCLS method decreases to 0 as goes co. This trend corroborates the theoretical predictions established in our Theorem
thereby affirming the efficacy and reliability of the SCLS method.
Conclusion
In this paper, we apply the CGMT framework to conduct rigorous theoretical error analysis of the SCLS method proposed by [ Specifically, when SCLS (6) is applied to tackle SPG-LS model (T) T,), and NNO0, o²) ). lim, n (0, 1), establish that:
with (O, Ia),
lim w woll P O.
This result confirms that the learner w" obtained through SCLS 6 accurately estimates the true learner Wp 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 framework for error analysis applicable to other statistical lcarning algorithms.
Acknowledgments and Disclosure of Funding
This work is supported by the Key R&D Program of Hubei Province under Grant 2024BAB038, National Key R&D Program China under Grant DF33F433044 and the Fundamental Research Fund Program of LIESMARS.
10

---

References
[1] Nick Bishop, Long Tran-Thanh, and Enrico H. Gerding. Optimal learning from verified training data. In NeurIPS, 2020.
[2] Jiali Wang, He Chen, Rujun Jiang, Xudong Li, and Zihao Li. Fast algorithms for stackelberg prediction game with least squares loss. In ICML, volume 139, pages 10708-10716, 2021.
[3] Jiali Wang, Wen Huang, Rujun Jiang, Xudong Li, and Alex L. Wang. Solving stackelberg prediction game with least squares Ioss via spherically constrained least squares reformulation. In ICML, volume 162, pages 26669, 2022.
[4] Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, and Ariel D. Procaccia. Commitment without regrets: Online learning in stackelberg security games. In ACM, pages 61-78, 2015.
[5] Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strategic classification from revealed preferences. In ACM, pages 55-70, 2018.
[6] Arunesh Sinha, Fei Fang. Bo An, Christopher Kiekintveld, and Milind Tambe. Stackelberg security games: Looking beyond decade of success. In IJCAI, pages 5494-5501, 2018.
[7] Xinsong Ma. Xin Zou, and Weiwei Liu. A provable decision rule for out-of-distribution detection. ICML, 2024.
[8] Xiyuan Li, Zou Xin, and Weiwei Liu. Defending against adversarial attacks via neural dynamic system. In NeurlPS, 2022.
[9] Yan Zhou and Murat Kantarcioglu. Modeling adversarial learning as nested stackelberg games. In PAKDD, volume 9652 of Lecture Notes in Computer Science, pages 350-362, 2016.
[10] Omar Abdel Wahab, Jamal Bentahar, Hadi Otrok, and Azzam Mourad. A stackelberg game for distributed formation of business-driven services communities. Expert Systems With Applica- tions, 45:359-372, 2016.
[11] Yan Zhou, Murat Kantarcioglu, and Bowei Xi. A survey of game theoretic approach for adversarial machine learning. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 9(3), 2019.
[12] Robert G. Jeroslow. Mathematical Programming, 32(2):146-164, 1985.
The polynomial hierarchy and a simple model for competitive analysis.
[13] R. Tyrelll Rockafellar. Convex Analysis, volume 28. Princeton University Press, 1997.
[14] Michael Brückner and Tobias Scheffer. Stackelberg games for adversarial prediction problems. In KKD, pages 547-555, 2011.
[15] Vincent Conitzer and Tuomas Sandholm. Computing the optimal strategy to commit to. In ACM, pages 82-90, 2006.
[16] Dmytro Korzhyk, Vincent Conitzer, and Ronald Parr. Complexity of computing optimal stackelberg strategies in security resource allocation games. AAAI, pages 805-810, 2010.
[17] Avrim Blum, Nika Haghtalab, and Ariel D. Procaccia. Learning optimal commitment to overcome insecurity. In NewrIPS, pages 1826-1834, 2014.
[18] Xiyuan Li, Xin Zou, and Weiwei Liu. Residual network with self-adaptive time step size. Pattern Recognition, 110081 2025.
[19] Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. Regularized linear regression: A precise analysis of the estimation emror. In COLT, pages 1683-1709, 2015.
[20] Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. The gaussian min-max theorem in the presence of convexity. arXiv preprint arXiv: 1e0..44084433 2014.
[21] Yehoram Gordon. On milman's ss inequality and random subspaces which escape through a mesh in I² In Geometric Aspects of Functional Analysis, 1988.
11

---

[22] Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi. The impact of regularization on high- dimensional logistic regression. In NeurIPS, volume 32, 2019.
[23] Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi. The performance analysis of generalized margin maximizers separable data. In ICML, pages 8417-8426, 2020.
[24] Yanbo Chen and Weiwei Liu. A theory of transfer-based black-box attacks: Explanation and implications. In NeurlPS, 2023.
[25] Jingyuan Xu and Weiwei Liu. Characterization of overfitting in robust multiclass classification. In NeurIPS, 2023.
[26] Jack Sherman and Winifred Morrison. Adjustment an inverse matrix corresponding to change in one element of given matrix. The Annals of Mathematical Statistics, 21(1):124-127, 1950.
[27] Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise error analysis of regularized m-estimators in high dimensions. IEEE Transactions on Information Theory, 64(8):5592-560 2018.
[28] Christos Thrampoulidis, Ashkan Panahi, and Babak Hassibi. Asymptotically exact error analysis for the generalized equation-lasso. In ISIT, pages 2021-2025, 2015.
[29] Samet Oymak, Christos Thrampoulidis, and Babak Hassibi. The squared-error of generalized LASSO: A precise analysis. In Allerton, pages 1002-1009, 2013.
[30] Whitney K Newey and Daniel McFadden. Large sample estimation and hypothesis testing. Handbook of econometrics, 4:2111 12211,2 1994.
[31] Weiwei Liu and Ivor W. Tsang. Making decision trees feasible in ultrahigh feature and label dimensions. Journal Of Machine Learning Research, 18:81:1-81:36, 2017.
[32] Lianghe Shi and Weiwei Liu. Adversarial self-training improves robustness and generalization for gradual domain adaptation. In NeurIPS, 2023.
[33] Yurii E. Nesterov. Introductory Lectures on Convex Optimization A Basic Course, volume 87 of Applied Optimization. Springer, 2004.
12

---

Error Analysis of the SCLS method in solving SPG (Appendix)
A
Limitaion
The SCLS method is currently state-of-the-art for solving SPG-LS, having won the ICML 2022 Outstanding Paper Award []. However, 3 lacks theoretical analysis 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 theoretical perspective SCLS method under Gaussian assumption. It is worth emphasizing that the Gaussian hypothesis is commonly used approach for theoretical analysis 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 non- non-Gaussian input settings, aiming provide insights into the universality of our results.
the error of the
B Proof of Theorem
Theorem 4.1 Suppose Wy is the true weight parameter of the original SCLS problem ( and w²
the optimal solution the objective function of SCLS (6). If lim (0, 1), the estimation
error of SCLS (6) is given by the following probability limit:
lim 10 2000
woll
Proof. Given the simplified AO problem 33 define
40
r(β) = |1B| + (c B)² +
+ 2(B).
(34)
Let B be the optimal solution to I(ß),, then
0L
2B
2B + 2(c B)c+ lim
0 = B 0.
(35)
aB
represents the eigenvalue of cc
A cc |
1 - cc 0= |
Then, the Hessian matrix V2T(3)
0rr 0g*
satisfies:
ct
c1
C1dd
C201
o
C2Ca
T Ia
lim Ia (1 lim n n
Ia + cc
0. (36)
CdC1
C2
This indicates that V2T is positive definite matrix. Consequently, according to
33 r(8) is
strongly convex function of B, and 3 0 is the unique global minimum. Moreover, we note:
4 7
8
0
and T(B")
(37)
Combining (36) and (37 the AO problem 33 satisfies the conditions of CGMT. Since ||ă"|] +
occurs when + oo, the analysis of (25) holds:
lim f(w) f(w).
(38)
Formulation (3 allows us translate the analysis on the optimal solution 8 of the approximated SCLS problem 24 to the analysis on corresponding optimal solution "" of the original SCLS
13

---

problem (1 Therefore, based on the relationship of SCLS problems 21 and
6
by applying the
principles of CGMT, we conclude:
lim R
1
lim 12-00
woll _ 0.
C Proof of Theorem 4.3
Theorem 4.3
Suppose Wo is the true weight parameter of the SPG-LS T "" is the optimal solution learned by SCLS ( and w" is the optimal solution recovered from ü by Theorem 3.4 If lim,,+ E (0, 1), the estimation error of SPG-LS II solved by the SCLS (6) is given by the following probability limit:
lim | 20000
woll P 0.
Proof. According Theorem 3.4 and formulation
17
W
W
Wo. ag
Then, the difference between the estimated and true parameter vectors can be expressed as:
||w woll =
""
W
(39)
Define
V7
T(i)
w
w
(40)
i
2
Based 14
θr(w)
T (w) = T (wo)
+
(w
wo) + +(120 -)
(41)
Oru
100
Combining 39
we get:
Ör i
Iw" woll
(w"
wp) O(I1@" 1
Ow
Ør (
|00"
O(1 w wol wp
-=
Invoking Theorem
we know:
lim
woll
P, O,
200
which implics:
lim 22000
1|w0 woll - 0.
D The Error Analysis in Case 2
Case āg < O, we set a(w) - | Consequently, ão -
| 12
important to note that although the expressions for a(w) and ( differ from those in Case 1, the approach and methodology for the error analysis of the SCLSS (6) in Case 2 remain analogous to those outlined in Case 1.
14

---

D.1 From the SCLS Method to PO According to formulation (14).
Dä @ā(w)
ā (w))
(w
wo) + O(1 -iol12).
(42)
Uw
The first-order upproximation of ((w) is
dā W
a(w) = (
iw (w wo)
(43)
If ④ woll - 0, we have a(w)) ä (w). Substituting a(w) in 20 by its first-order approximation
á 0
VT 2
+
X wp) -cl
Iā (
(w wo + v7
2
X w wo) -E
iw
2
oā
2E
( w + X (w w))
2
Ow
10
10g
Then, we obtain an approximated SCLS problem corresponding to SCLS
21
dā(w) (w)
wg)z + X i wp) 2e
2
min
(w
(44)
tw
i wo
Denote W as the optimal solution to the approximated SCLS problem
(44). Then, the estimation
error for approximated SCLS (44) is B == ~ wn- Taking advantage of the simple characterization
of (w)), we can accurately analyze the error in the resulting approximated SCLS problem (44). In
other words, if (w) and (w) denote the objective functions of SCLS (21 and the approximated SCLS respectively,
āg
V
f(i) =
2
+
X
wp) - -E
2
2
dā
2E |
f(w)
(w wn)z + X (T w))
2
V7
iwi
v1
we have
lim Wo
f(w) = f(w).
(45)
10
Compared with SCLS (1)), the approximation 44 demonstrate that this case occurs independent the original SCL.S (2T) as - +0c. This fact allows to translate the findings about wn obtained for the approximated SCLS problem (44) to
is tight when - woll + 0, and we later
corresponding precise outcomes of w" for the original SCLS problem (
Because 7 is constant, the approximated SCLS problem mization problem:
M4 is equivalent to the following opti-
1 Bz + XB
2e
min B n1
(46)
where the optimization variable changed from w to B = w wo and = c(wo: 7)
v/
(G BiP
Mo The normalization of the loss function is appropriately applied,
which does not alter the optimal solution. Based on the analysis on formulation 45 when | + the approximated SCLS problem (44) becomes equivalent to SCLS (2I) Consequently, the analysis
of the optimal cost 3 SCL.S 21b can be replaced by the analysis of the optimal solution 3 in optimization (46).
15

---

D.2
From PO to AO
The crucial step involves transforming optimization (46 into PO problem within the CGMT framework. We utilize conjugate pairs (13 for optimization 46
min c Bz XB B
2E min max
2u E
XB + u.
(47)
B
where B R2 u R Using formulations
10 and 47).
the PO problem associated with the
estimation error of the approximate SCLS (46)
is
PSCLS (X) min max
uu' XB (B.
(48)
B
n
where
2u Te
|u|l
bBB.u) u) = Buu
4
Given that the entries of X are drawn i.i.d. from (o0, 1) and (B u) is convex-concave function, the PO problem (48) meets the assumptions of Theorem 3.6 Consequently, we replace the challenging PO problem (48) with simplified AO problem using CGMT:
2u
||eal2
ØSCIS (g, h) mjn max - [|8||g T u 1/all B c B.u=
8
V7
4
min max - [[ + c. Bz 2E
||//|
u uu |ulli T
(49)
where the entries of g. are drawn i.d. from NNO,,) 1). Suppose Bosass represents the optimal solutions of the PO problem 48). and dsccs denotes the optimal solutions of the AO problem (49
- p", we have || ||8asas! || P p². Thus, we can analyze the
According to Theorem 3.6 if decss
minimizer of the AO problem 49 instead of the PO problem (48).
D.3 Simplification for AO
Given that the entries of g and z are drawn i..dd from (0, 1), and oo(,, the expression ||B||g t B2 V7
in AO 49) is statistically identical a random vector with entries drawn i.i.d. from
(O,, || 2 + (c B) 4r" where Ia represents d x d identity matrix. Following the methodology
outlined by (28 we substitute the first term in AO (49) with v |/ + (cT B)² + 4a g u. This
yields:
( |BB|2 + (cT + 4g²
7 g u || |
min max
(50)
0 n
Let 7 = |/u/.. Since max g u |g||| ||/||| = nl|g//. and h NN optimization 55 can be equivalently expressed as:
min max 1 (v |B + (cT B)2 + B 920 n
40²
||lll 1/h B n
(51)
The formulation (I is a quadratic function of 17 with the symmetric axis:
4
n -x=24 2 7x=2
(cT
[gll 11++hB]
|| [b]])
1 2.. According to 29 Lem. B.2], || and ||A|[2 concentrate around their means and d, respectively. Thus, the value that 7/ concentrates around is
Furthermore, 77. (Illl |b]l > ||
16

---

nonnegative. Additionally, taking n7s into (31 the objective 51
concentrates around
4g2
min
=(
|181|2 + B)²
| B)²
B
n
7
2
4022 (52)
min B
(11B1 + (c B)²
||||| + (h 3) 2h B ||8 + BcT
n
According to 29 Lem. B.2], | 1. (h 3) and h B||g|| concentrate around their means: El1gg
n, E(h B) | and E h B g = 0. Besides, define 2( := lim,- |/11 Following the
methodology used by [27 29 30).
+oc, the optimal minimizer of (52) converges to the
optimal minimizer of the following deterministic optimization in probability:
2
min B 2 + (c + +2((B)
+
(53)
7
Here, we complete the simplifications by reducing the AO problem 53 that now only involves the estimation error variable B.
(49
to equivalent optimization
D.4
Error Analysis
Building on the previous analysis, if the optimal solution of optimization (53) is ||3 p², have
p" for AO problem (49). Then, by virtue of CGMT, ||B Byeas - p" also holds for PO problem (48.. If p* further satishies p² = 0, based on the relationship between the original and
|| duaus
approximated SCLS in Section 4.1 we have || w _ 0 for SCLS problems (21) and (6). Therefore, it only remains to obtain the optimal value of p 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 wo is the true weight parameter of the original SCLS problem (6) and u²
the optimal solution to the objective function of SCLS (6). If lim d E (0, 1), the estimation error of SCLS (6) is given by the following probability limit:
n
lim 220000
10
woll P 0.
Proof. Given the simplified AO problem (53 define
r(β) = |1 + (c B)² + 402
+ 2(
(54)
7
Let 3" be the optimal solution to 1'(B), then
aL
2B
2B + 2(c² B)c+ + lim 0B
+ =
(55)
no
If represents the eigenvalue of cc
aA cc = - ||c/
Then, the Hessian matrix VTT(B)
8ºr az²
satisfies:
(2r(B) (1+ lim
1 Ia + TC > 0.
(56)
no0 n
This indicates that (²T is positive definite matrix. Consequently, according to 33 T(B) is strongly convex function of B, and 3 is the unique global minimum. Moreover, note:
40 7
8 || = 0 and T(B")
(57)
17

---

Combining (56 and 57 the AO problem 53 satisfies the conditions of CGMT. Since ||B"
||
occurs when n goes to oo, the analysis of holds:
lim ((w) f()).
(58)
Formulation (58) allows us translate the analysis on the optimal solution n of the approximated SCLS problem (44) to the analysis on corresponding optimal solution w' of the original SCLS problem 21.. Therefore, by applying the principles of CGMT, we conclude:
lim || n-000
P, 0 +
lim I 12
wall E 0.
When applying the SCLS method (6 to solve SPG-LS T the reliability of the SCLS method (6) in solving SPG-LS (T is supported by the following theorem..
Theorem D.2. Suppose Wa is the true weight parameter of the SPG-LS Q). w is the optimal
solution learned by SCLS (6) and w" the optimal solution recovered from w" by Theorem 3.4
limm-xx (0, 1). the estimation error of SPG-LS
4
solved by the SCLS (6) is given by the
following probability limit:
lim 22000
woll
P O.
Proof. According Theorem 3.4 and formulation
W
Wo- āo
Then, the difference between the estimated and true parameter vectors can be expressed as:
I woll =
w"
We
(59)
60
Define
(w))
(60)
1
1 2
Based on 14
θT(w)
(w) rww))
(w wo) + +0 w
(61)
Owu
Combining 159
6l
we get:
θr w
Iw" woll
(w" wp
O( wi 1 13)
Ow
i=
θr ir(w) (
||00
wp + O(1 i wo
iw
Invoking Theorem D.1
we know:
lim
-
woll - 0,
70000
which implies:
lim n-000
||00
woll - 0.
E Experiments Appendix
F.1 Computing Platform
All simulations are implemented using MATLAB R2021b on a PC running Windows 10 Intel(R) Xeon(R) E5-2655 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.
18

---

E.2 More experiments
Experimental results for are displayed in Figure F1 As shown in Figure F1 the estimation
enror I|w* woll generated by the SCLS method decreases to 0 as goes to oC. This trend is consistent with the conclusion from Figure Theorems and D.2 thereby affirming the efficacy and reliability of the SCL.S method.
0.82
Spaniyy
Saurtyy
Ard- 1
MM5-1001
1.5
0085
0.03
1.4
4009
12000
10000
1000
12000
14000
7
7 0.01.
Figure F1: The change of I|w woll with for SCLS method under different Sparsity k/d.
19

---

NeurIPS Paper Checklist
1. Claims
Question: 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 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 long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Our paper explicitly acknowledges the dependency on Gaussian inputs limitation, prompting further investigation into applicability to non-Gaussian contexts.
Justification:
Guidelines:
The answer NA means that the paper has 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 (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn 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 few datasets or with 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, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
20

---

Answer: [Yes]
Justification: We provide the assumptions of the theorems and all our theorems are followed by their proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Our paper meticulously details all methodologies, parameters, and experimen- tal conditions necessary for replication.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
21

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: We focus on SCLS method 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.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/
Cooee//dddeeSbmimiia ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Our paper comprehensively details all training and testing protocols, including data management, hyperparameter selection, and optimization techniques.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Our results based averaging the results from 10 trials.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
22

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Our paper specifies the computing platform, processor details, and memory constraints, ensuring accurate replication of the experimental setup and results.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics hattps://neurb/: httpppsscccpppppcepeeeeeeeesseee httpai/ieeehhisuieeeeeeeeeeeeee
Answer: [Yes]
Justification: Our research strictly adheres to the NeurlPS Code of Ethics, focusing theoretical advancements without ethical concerns in implementation or application.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification; Our paper theoretical and includes numerical verification experiments. There is no societal impact.
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 why the paper does not address societal impact.
23

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate 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 intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility MI).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Our paper focuses 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 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 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 encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.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 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 dataset.
The authors should state which version of the asset used and, possible, include 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, paperswi thcode com/dataseta
datasets.papersstt
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
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/codeemmodll as part 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. 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 details about compensation (if any)?
Answer: [NA],
Justification: Our paper is theoretical and includes numerical verification experiments. does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According 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.
15. 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 equivalent approval/teview based 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 crowdsoureing nor research with human subjects.
25

---

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.
26


Reviews:
[{"review_id": "wwvFptZx5W", "reviewer": "Reviewer_rMtE", "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.\n\n\n[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.", "questions": "$\\bullet$ None.", "limitations": "$\\bullet$ Yes, the authors have adequately addressed the limitations.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "$\\bullet$ __Originality__  \n\n1. This paper provides a theoretical error analysis of the SCLS method proposed by the paper `` Solving Stackelberg prediction game with least squares loss via spherically constrained least squares reformulation ’’, which won the ICML 2022 Outstanding Paper Award.  \n\n2. This paper introduces the transformation from the Primary Optimization (PO) problem to the Auxiliary Optimization (AO) problem.  \n\n3. This paper applies the Convex Gaussian min-max theorem.\n\n$\\bullet$ __Quality__ The quality of this paper is good.\n\n$\\bullet$ __Clarity__  The overall expression and proof process of this paper are very clear.\n\n$\\bullet$ __Significance__  The theoretical results further ensure the effectiveness and accuracy of the SCLS method proposed by [3]. This topic is interesting and important.", "weaknesses": "$\\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.\n\n$\\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.\n\n\n$\\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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Answer to Reviewer rMtE\n\nDear Reviewer rMtE,\n\nThank you for your job in reviewing our paper. We are very sorry for the inconvenience caused by our presentations. To this end, following your comments, we correct our work in the revision.\n\nIn regards to the weaknesses:\n\n__Weakness 1.__ 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.\n\n__Answer:__  Thank you for your comments. Theorem 2.6 indicates that, if the optimal cost $\\phi(\\pmb{g},\\pmb{h})$ of $\\textbf{AO}$ concentrates to some value $\\mu$, the same holds true for $\\Phi(\\pmb{G})$ of $\\textbf{PO}$. Furthermore, under appropriate additional assumptions, the optimal solutions of the $\\textbf{AO}$ and $\\textbf{PO}$ problems are also closely related by $\\Vert\\pmb{\\beta}  _{\\Phi}(\\pmb{G})\\Vert = \\Vert \\pmb{\\beta} _{\\phi}(\\pmb{g},\\pmb{h})\\Vert$, as $n\\to \\infty$. This suggests that, within the CGMT framework, a challenging $\\textbf{PO}$ problem can be replaced with a simplified $\\textbf{AO}$ problem, from which the optimal solution of the $\\textbf{PO}$ problem can be accurately inferred. Moreover, we are more concerned about $\\Vert \\pmb{\\beta} _{\\phi}(\\pmb{g},\\pmb{h})\\Vert$. Therefore, if we reduce the AO problem only involves scalar variable about $\\Vert \\pmb{\\beta} _{\\phi}(\\pmb{g},\\pmb{h})\\Vert$, we obtain the error of the SCLS method by the relationship $\\Vert\\pmb{\\beta} _{\\Phi}(\\pmb{G})\\Vert = \\Vert \\pmb{\\beta} _{\\phi}(\\pmb{g},\\pmb{h})\\Vert$.\n\nIf the optimal solution of optimization (33) is $\\Vert\\tilde{\\pmb{\\beta}}\\Vert=\\rho^*$, we have $\\Vert\\tilde{\\pmb{\\beta}} _{\\phi _{\\text{SCLS}}}\\Vert\\stackrel{P}{\\longrightarrow}\\rho^*$ for $\\textbf{AO}$ problem (29). Then, by virtue of CGMT, $\\Vert\\tilde{\\pmb{\\beta}} _{\\Phi _{\\text{SCLS}}}\\Vert\\stackrel{P}{\\longrightarrow}\\rho^*$ also holds for $\\textbf{PO}$ problem (28). If $\\rho^*$ further satisfies $\\rho^* = 0$, based on the relationship between the original and approximated SCLS in Section 3.1, we have $\\Vert\\tilde{\\pmb{w}}-\\tilde{\\pmb{w}} _0\\Vert\\stackrel{P}{\\longrightarrow} 0$ for SCLS problems (21) and (6). Therefore, it only remains to obtain the optimal value of $\\rho$ in optimization (33) that plays the role of $\\Vert\\tilde{\\pmb{\\beta}}\\Vert$.\n\n(Please refer to lines 152-157 and 236-241 of our main paper.)\n\n__Weakness 2.__ 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.\n\n__Answer:__  Thank you for your comments. The equation between lines 154-155 is a further explanation of Theorem 2.6 and the condition ``$n \\to \\infty$’’ is included in Theorem 2.6. \n\n__Weakness 3.__ 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? \n\n__Answer:__ Thank you for your comments. Our Theorem 3.1 reflects that this condition happens independently. Specifically, Theorem 3.1 demonstrates that $\\lim _{n\\to \\infty}\\Vert\\tilde{\\pmb{w}}^*-\\tilde{\\pmb{w}} _0\\Vert \\stackrel{P}{\\longrightarrow} 0$ for the approximated SCLS problem. Then, according to the relationship (25),  we can translate the findings of the approximated SCLS problem to that of the original SCLS problem.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "prLk4rdQ4s", "reviewer": "Reviewer_btrD", "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.", "questions": "- How can the authors derive Eq.(29)?\n- Could the authors specify the feasibility of replacing $d$ required by CGMT with $n$ in their conclusions.", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper studied the seminal work of SPGs published in ICML 2022. They are the first to conduct the estimation error analysis. \n- Technically, they first reformulate the estimation error of the SCLS method as a PO problem. Then, it is novel to use the CGMT to reduce the PO problem into the AO problem. Some derivations are performed to further simplify the AO problem, as shown in Eq. (33). They finally analyze the simple Eq. (33) and present two asymptotic main theories. The empirical studies are also conducted to verify the theory. Overall, the presentation is clear and the paper seems to be a theoretical solid paper.", "weaknesses": "- 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.\n- Eq.(13) and Eq.(14) miss the transpose symbol $T$.\n- Some derivations need to be more clear, for example, in Line 211, how can the author derive the Eq.(29)?\n- 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Answer to Reviewer  btrD\n\nDear Reviewer btrD,\n\nThank you for your job in reviewing our paper. We are very sorry for the inconvenience caused by our presentations. We extend our heartfelt gratitude for your patience and meticulous guidance. Your insightful comments is valuable for us and we appreciate the opportunity to address your concerns.\n\n### In regards to the weaknesses:\n\n__Weakness 1.__  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.\n\n__Answer:__ \n\nThank you for your comments.  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 the Gaussian assumption. It is worth emphasizing that the Gaussian hypothesis is a commonly used approach for theoretical analysis in the field of machine learning, as evidenced by papers [A1~A8]. The error analysis of the SCLS method under general or weaker conditions is beyond the scope of this paper. We will investigate the results of non-Gaussian settings in our future work.\n\n[A1]. Alexander Camuto, Matthew Willetts, Umut Simsekli, Stephen J. Roberts, Chris C. Holmes: Explicit Regularisation in Gaussian Noise Injections. NeurIPS 2020\t\n\n[A2]. Prathamesh Mayekar, Jonathan Scarlett, Vincent Y. F. Tan:\nCommunication-Constrained Bandits under Additive Gaussian Noise. ICML 2023: 24236-24250\n\n[A3]. Matthew Joseph, Alexander Yu: Some Constructions of Private, Efficient, and Optimal K-Norm and Elliptic Gaussian Noise. COLT 2024: 2723-2766\n\n[A4]. Alexander Camuto, Xiaoyu Wang, Lingjiong Zhu, Chris C. Holmes, Mert Gürbüzbalaban, Umut Simsekli: Asymmetric Heavy Tails and Implicit Bias in Gaussian Noise Injections. ICML 2021: 1249-1260\n\n[A5]. Holden Lee, Chirag Pabbaraju, Anish Prasad Sevekari, Andrej Risteski:\nPitfalls of Gaussians as a noise distribution in NCE. ICLR 2023\n\n[A6]. Christos Thrampoulidis, Ehsan Abbasi, Babak Hassibi: Precise Error Analysis of Regularized M-Estimators in High Dimensions. IEEE Trans. Inf. Theory 64(8): 5592-5628 (2018)\n\n[A7]. Yufeng Zhang, Jialu Pan, Li Ken Li, Wanwei Liu, Zhenbang Chen, Xinwang Liu, Ji Wang: On the Properties of Kullback-Leibler Divergence Between Multivariate Gaussian Distributions. NeurIPS 2023\n\n[A8]. Seunghyuk Cho, Juyong Lee, Dongwoo Kim: Hyperbolic VAE via Latent Gaussian Distributions. NeurIPS 2023\n\n__Weakness 2.__ Eq.(13) and Eq.(14) miss the transpose symbol $T$.\n\n__Answer:__  Thank you for your comments. We are very sorry for this clerical error and we will add  the transpose symbol $T$ to rectify Equations (13) and (14) in our revision.\n\n__Weakness 3.__ Some derivations need to be more clear, for example, in Line 211, how can the author derive the Eq.(29)?\n\n__Answer:__  Thank you for your comments.\n$$\n\\Phi _{\\text{SCLS}}(\\pmb{X})= \\min _{\\tilde{\\pmb{\\beta}}} \\max _{\\pmb{u}}\\frac{1}{n}\\big(\n\\pmb{u}^\\top\\pmb{X}\\tilde{\\pmb{\\beta}}+\\psi(\\tilde{\\pmb{\\beta}}, \\pmb{u})\\big),\\tag{28}\n$$\nwhere \n$\\psi(\\tilde{\\pmb{\\beta}}, \\pmb{u}):=\\pmb{c}^\\top\\tilde{\\pmb{\\beta}}\\cdot\\pmb{u}^\\top \\pmb{z}-\\frac{2\\pmb{u}^\\top\\pmb{\\epsilon}}{\\sqrt{\\gamma}}-\\frac{\\Vert\\pmb{u}\\Vert^2}{4}.$\nGiven that the entries of $\\pmb{X}$ are drawn i.i.d. from $\\mathcal{N}(0, 1)$ and $\\psi(\\tilde{\\pmb{\\beta}}, \\pmb{u})$ is a convex-concave function, the $\\textbf{PO}$ problem (28) satisfies the conditions of Theorem 2.6. Consequently, we replace the challenging $\\textbf{PO}$ problem (28) with a simplified $\\textbf{AO}$ problem using CGMT:\n\n$$\\begin{align*}\n    \\phi _{\\text{SCLS}}(\\pmb{g},\\pmb{h}) =& \\min _{\\tilde{\\pmb{\\beta}}} \\max _{\\pmb{u}}\\frac{1}{n}\\big(\\Vert\\tilde{\\pmb{\\beta}}\\Vert\\pmb{g}^\\top\\pmb{u}\n    + \\Vert\\pmb{u}\\Vert\\pmb{h}^\\top\\tilde{\\pmb{\\beta}}\n     +\\pmb{c}^\\top\\tilde{\\pmb{\\beta}}\\cdot\\pmb{u}^\\top \\pmb{z}-\\frac{2\\pmb{u}^\\top\\pmb{\\epsilon}}{\\sqrt{\\gamma}}-\\frac{\\Vert\\pmb{u}\\Vert^2}{4}\\big)\\\\\\\\\n    =&\\min _{\\tilde{\\pmb{\\beta}}} \\max _{\\pmb{u}}\\frac{1}{n}\\big[(\\Vert\\tilde{\\pmb{\\beta}}\\Vert\\pmb{g}+\\pmb{c}^\\top\\tilde{\\pmb{\\beta}}\\pmb{z}-\\frac{2\\pmb{\\epsilon}}{\\sqrt{\\gamma}})^\\top\\pmb{u}\n    + \\Vert\\pmb{u}\\Vert\\pmb{h}^\\top\\tilde{\\pmb{\\beta}}-\\frac{\\Vert\\pmb{u}\\Vert^2}{4}\\big],\\tag{29}\n\\end{align*}$$\n\n(Please refer to lines 129-131 and 207-212 of our main paper.)\n\n__Weakness 4.__  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?\n\n__Answer:__  Thank you for your comments. Definition 2.5 indicates that $n=n(d)$ where $n(d)$ is a funtion of $d$. Additionally, Theorems 3.1 and 3.2 require $\\lim _{n\\to\\infty}\\frac{d}{n}\\in (0,1)$. Therefore, $\\lim _{n\\to infty}$ implies $\\lim _{d\\to \\infty}$. The transformation from $n$ to $d$ doesn't affect our theoretical results. It is worth emphasizing that all deductions should be based on $d$, if we replace $n$ with $d$.\n\n### In regards to your questions:\n\n__Question 1.__ How can the authors derive Eq.(29)?\n\n__Answer:__  Thank you for your comments. Question 1 is similar to Weakness 3. Please see the Answer to Weakness 3.\n\n__Question 2.__ Could the authors specify the feasibility of replacing $d$ required by CGMT with $n$ in their conclusions.\n\n__Answer:__  Thank you for your comments. Question 2 is similar to Weakness 4. Please see the Answer to Weakness 4.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ORKgxNygKV", "reviewer": "Reviewer_PFXk", "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].", "questions": "1. Line 61: What is the main distinction between $w_0$ and $w^*$?\n2. Line 114: The notation ($\\omega,~\\alpha$) appears twice.\n3. 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?\n4. Line 161: $(u)$ should be changed to $f^*(u)$.\n5. Line 170: The authors should explain why the second equation in (16) is valid.\n6. 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).\n7. 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?\n8. 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.\n9. In experiments, why the true parameter $w_0$ is generated randomly?", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper introduces a method to analyze the error of SCLS. And this method is applicable to other statistical learning algorithms.", "weaknesses": "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.\n\n2. 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}$.\n\n3. 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.\n\n4. Section 2.1 of this paper is redundant as all the relevant information is extracted from reference [3].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer PFXk, Thank you for the detailed and thorough review. All the references can be seen in Author Rebuttal by Authors.\n\n### For Weaknesses:\n\n__W1:__ The SCLS method [3] is the latest advanced technique for solving the widely applicable SPG-LS problem, winning the ICML 2022 Outstanding Paper Award. However, the SCLS method lacks error analysis, and we have filled this gap. Error analysis of algorithms is a very crucial and popular topic in the field of machine learning, as evidenced by several papers [B1-B8]. Therefore, it is important to study the error of the SCLS algorithm. \n\nWe will clarify this sentence in the revision as follows: The paper [3] lacks theoretical analysis on the error of the SCLS method.\n\n__W2:__ In our paper, $d$ denotes the sample dimension and $n$ is the number of samples. Thus, $d$ in Definition 2.5 and $d$ in $X\\in R^{n\\times d}$ both represent the sample dimension, meanwhile, $n$ in Definition 2.5 and $n$ in $X\\in R^{n\\times d}$ both denote the number of samples, ensuring consistency and clarity. (See lines 31-33)\n\n__W3:__ The SCLS method is currently the 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. Our limitation section highlights this Gaussian assumption (See lines 372-375). Reviewer btrD also identifies this limitation but acknowledges our contribution under Gaussian settings.\n\nIt is worth emphasizing that the Gaussian hypothesis is a commonly used approach for theoretical analysis of algorithms in machine learning, as evidenced by papers  [C1~C8]. Thus, we investigate the error of the SCLS algorithm under Gaussian settings. \n\n__W4:__ Since our aim is to study the error of the SCLS method, it is important to provide an overview of this method. Section 2.1 is the preliminaries to introduce the necessary concepts and theorems about the SCLS method from [3]. These concepts and theorems are frequently used and play a crucial role in the subsequent derivation of our manuscript. Following your advice, we will simplify Section 2.1 in our revision.\n\n### For Questions:\n\n__Q1:__  $w_0$ is the known parameter of the SPG-LS model (1), while $w^*$ learned by the SCLS method is an estimator of $w_0$. (See lines 61-66)\n\n__Q2:__  We will rectify it in revision.\n\n__Q3:__ PO problem contains the matrix $G\\in R^{n\\times d}$ and the challenge lies in the processing of matrices. The inclusion of a matrix in the PO problem increases the complexity of analysis. In contrast, the AO problem only contains vectors with dimensions $d$ or $n$, where vectors are easier to handle than matrices. Additionally, the AO problem reduces the dimension of the PO problem from $n\\times d$ to max{$d, n$}, thereby simplifying the PO problem.\n\nAccording to the analysis of the PO and AO problems above, the reasons why PO (28) is  more complex than AO (29) and the difficulties of (28) are summarized as follows:\n\n(i). The PO (28) contains the matrix $X\\in R^{n\\times 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.  \n\n(ii). The AO (29) reduces the dimension of the PO (28) from $n\\times d$ to max{$d, n$}, thereby simplifying the PO (28).\n\n(iii). It is difficult to obtain the value that the PO (28) concentrates on. \n  \n(iv). The AO problem (29) can be further simplified by AO optimization (33) that only includes estimation error variable $\\tilde{\\beta}$, which is easier to analyze than PO (28). \n\n__Q4:__ We will rectify it in revision.\n\n__Q5:__ The SPG-LS model (1) can be expressed as :\n$$\\min_ w||X^ *w-y||^2,s.t.X^ * =argmin_ {\\hat X}||\\hat Xw-z||^2+\\gamma|| \\hat X-X||_ F^2.\\tag{1}$$\n\n[1, 2, 3] reformulate SPG-LS (1) into :\n$$\\inf_ {w}\\Big\\Vert\\frac{\\frac{1}{\\gamma}zw^Tw+Xw}{1+\\frac{1}{\\gamma}w^Tw}-y\\Big\\Vert^2,\\tag{4}$$\nwhich indicates that\n$$X^*w = \\frac{\\frac{1}{\\gamma}zw^Tw+Xw}{1+\\frac{1}{\\gamma}w^Tw}.$$\n\nTherefore, if $w=w _0$, we have\n$$y=X^*w _0+\\epsilon=\\frac{\\frac{1}{\\gamma}zw _0^Tw _0+Xw _0}{1+\\frac{1}{\\gamma}w _0^Tw _0}+\\epsilon=\\frac{\\alpha _0z+Xw _0}{1+\\alpha _0}+\\epsilon,\\tag{16}$$\nwhere $\\alpha_0=w_0^Tw_0/\\gamma$. (See lines 92-95 and 169-170)\n\n__Q6:__ According to our answer to Q1, $w_0$ is assumed to be known. Since $\\alpha_0=w_0^Tw_0/\\gamma$, both $\\tilde{w}_0$ and $\\tilde{\\alpha}_0$ are known constants, not variables.\n\n__Q7:__ Following the approach of [D1-D6], (26) is the first-order approximation of (21) where the derivation process is in lines 183-199. We will clarify this point in our revision. \n\n__Q8:__ To the best of our knowledge, we are the first to investigate the error of the SCLS method, and the theoretical analysis in our paper successfully explains the behavior of the SCLS method when $d/n<1$. Thus, the primary contribution of our paper is to provide a theoretical perspective on the error of the SCLS method under certain conditions. Analyzing the error of the SCLS method under broad conditions is beyond the scope of this paper. We plan to investigate the error results of the SCLS method for $d/n>1$ in our future work.\n\n__Q9:__ According to our answer to Q1, $w_0$ represents the ``true'' weight parameter of the SPG-LS model, which is assumed to be known. Therefore, once selected, $w_0$ should be fixed in experiments. In addition to random generation, we can also manually set a constant value for $w_0$. \n\nWe sincerely thank you once again for your time and effort in reviewing our paper. We hope that our answers have met your expectations and satisfaction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hJOJ9LpMpc", "reviewer": "Reviewer_XvKF", "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.", "questions": "See the Weaknesses.", "limitations": "In the Appendix, the limitations are discussed.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The authors focus on the Spherically Constrained Least Squares (SCLS) method which is the state-of-the-art method for solving the SPG-LS problem. The lack of theoretical error analysis of the SCLS method restricts its large-scale applications. The authors investigate the estimation error between the learner obtained by the SCLS method and the actual learner. Therefore, the content of this paper is original. The writing quality is high, and the argumentation process is clear. Moreover, this analysis strengthens the theoretical framework of the SCLS method and confirms the reliability of the learner produced by the SCLS method. Thus, the authors’ contribution is significant in promoting the large-scale applications of the SCLS method.", "weaknesses": "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)?\n\n2. How do the authors derive optimization (32) from (31)?\n\n3. 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.\n\n4. Theorem 3.1 appears very similar to Theorem 3.2. What’s the relationship between Theorem 3.1 and Theorem 3.2?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Answer to Reviewer XvKF\n\nDear Reviewer XvKF,\n\nThank you for your job in reviewing our paper. We are very sorry for the inconvenience caused by our presentations. To this end, following your comments, we correct our work in the revision. All the references appear in our main paper.\n\nIn regards to the weaknesses:\n\n__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)?\n\n__Answer:__  Thank you for your comments. The SCLS problems (6) is equivalent to optimization (9). \n\n$$\\begin{align*}\n\\min _{\\pmb{r}}q(\\pmb{r}), \\quad \\text{s.t.}\\quad \\pmb{r}^T\\pmb{r} = 1,\\tag{9}\n\\end{align*}$$\n\nwhere $ q(\\pmb{r}) = ||\\hat{L}\\pmb{r}-(\\pmb{y}-\\pmb{z}/2)||^2$, $\\hat{L} = \\begin{pmatrix}\\frac{\\sqrt{\\gamma}}{2}\\pmb{X}&\\frac{\\pmb{z}}{2}\\end{pmatrix}$ and $\\pmb{r}^\\top=\\begin{pmatrix}\n\\tilde{\\pmb{w}}\\\\ \\tilde{\\alpha}\n\\end{pmatrix}.$ Then, \n\n$$\n\\begin{align*}\nq(\\pmb{r})&= ||\\hat{L}\\pmb{r}-(\\pmb{y}-\\pmb{z}/2)||^2= ||\\begin{pmatrix}\\frac{\\sqrt{\\gamma}}{2}\\pmb{X}&\\frac{\\pmb{z}}{2}\\end{pmatrix}\\begin{pmatrix}\n\\tilde{\\pmb{w}}\\\\ \\tilde{\\alpha}\n\\end{pmatrix}^\\top-(\\pmb{y}-\\pmb{z}/2) ||^2\\\\\\\\\n&=\\Vert \\frac{\\tilde \\alpha}{2}  \\pmb{z} + \\frac{\\sqrt{\\gamma}}{2}\\pmb{X}\\tilde{\\pmb{w}} - (\\pmb{y} - \\frac{\\pmb{z}}{2})\\Big\\Vert^2.\n\\end{align*}\n$$\nAdditionally, the constraint can be transformed to\n$$\n\\begin{align*}\n1=\\pmb{r}^T\\pmb{r}=\\begin{pmatrix}\n\\tilde{\\pmb{w}}\\\\ \\tilde{\\alpha}\n\\end{pmatrix}^\\top\\begin{pmatrix}\n\\tilde{\\pmb{w}}\\\\ \\tilde{\\alpha}\n\\end{pmatrix}=\\tilde{\\pmb{w}}^\\top\\tilde{\\pmb{w}} + \\tilde \\alpha^2.\n\\end{align*}\n$$\nTherefore, the optimization (9)  is equivalent to SCLS problems (6):\n$$\\begin{align}\n    \\min\\limits _{\\tilde{\\pmb{w}}, \\tilde{\\alpha}}\\quad  {\\tilde v}(\\tilde{\\pmb{w}},\\tilde \\alpha) \\triangleq \\Big\\Vert \\frac{\\tilde \\alpha}{2}  \\pmb{z} + \\frac{\\sqrt{\\gamma}}{2}\\pmb{X}\\tilde{\\pmb{w}} - (\\pmb{y} - \\frac{\\pmb{z}}{2})\\Big\\Vert^2,\\quad \n    {\\text{s.t.} }\\; \\tilde{\\pmb{w}}^\\top\\tilde{\\pmb{w}} + \\tilde \\alpha^2 = 1. \\tag{6}\n\\end{align}$$\n\n\n__Weakness 2.__ How do the authors derive optimization (32) from (31)?\n\n__Answer:__  Thank you for your comments. We are very sorry for the inconvenience caused by our presentations. The detailed derivation process from (31) to (32) is:\n$$\\begin{align*}\n    \\min _{\\tilde{\\pmb{\\beta}}}\\max _{\\eta \\geq 0} \n   \\frac{1}{n}\\Big(\\sqrt{\\Vert\\tilde{\\pmb{\\beta}}\\Vert^2+(\\pmb{c}^\\top\\tilde{\\pmb{\\beta}})^2+\\frac{4\\sigma^2}{\\gamma}}\\cdot\\Vert\\pmb{g}\\Vert \\eta\n    + \\eta\\pmb{h}^\\top\\tilde{\\pmb{\\beta}}\n    -\\frac{\\eta^2}{4}\\Big). \\tag{31}\n\\end{align*}$$\nThe formulation (31) is a quadratic function of $\\eta$ with the symmetric axis:\n$$\\begin{align*}\n    \\eta _s=2\\Big(\\sqrt{\\Vert\\tilde{\\pmb{\\beta}}\\Vert^2+(\\pmb{c}^\\top\\tilde{\\pmb{\\beta}})^2+\\frac{4\\sigma^2}{\\gamma}}\\cdot\\Vert\\pmb{g}\\Vert+\\pmb{h}^\\top\\tilde{\\pmb{\\beta}}\\Big)\n    >\\Vert\\tilde{\\pmb{\\beta}}\\Vert(\\Vert\\pmb{g}\\Vert-\\Vert\\pmb{h}\\Vert).\n\\end{align*}$$\n\nAdditionally, $\\eta _s(\\Vert\\pmb{g}\\Vert+\\Vert\\pmb{h}\\Vert)>\\Vert\\tilde{\\pmb{\\beta}}\\Vert(\\Vert\\pmb{g}\\Vert^2-\\Vert\\pmb{h}\\Vert^2)$.  $\\Vert\\pmb{g}\\Vert^2$ and $\\Vert\\pmb{h}\\Vert^2$ concentrate around their means $n$ and $d$, respectively.  Consequently, the value around which $\\eta _s$ concentrates is nonnegative, due to $d/n<1$.  Moreover, taking $\\eta _s$ into (31):\n$$\\begin{align*}\n    &\\min _{\\tilde{\\pmb{\\beta}}}\n    \\frac{1}{n}\\Big(\\sqrt{\\Vert\\tilde{\\pmb{\\beta}}\\Vert^2+(\\pmb{c}^\\top\\tilde{\\pmb{\\beta}})^2+\\frac{4\\sigma^2}{\\gamma}}\\cdot\\Vert\\pmb{g}\\Vert\n    + \\pmb{h}^\\top\\tilde{\\pmb{\\beta}}\n    \\Big )^2\\\\\\\\\n    =& \\min _{\\tilde{\\pmb{\\beta}}}\n    \\frac{1}{n}\\Big[(\\Vert\\tilde{\\pmb{\\beta}}\\Vert^2+(\\pmb{c}^\\top\\tilde{\\pmb{\\beta}})^2+\\frac{4\\sigma^2}{\\gamma})\\Vert\\pmb{g}\\Vert^2+ (\\pmb{h}^\\top\\tilde{\\pmb{\\beta}})^2+2\\pmb{h}^\\top\\tilde{\\pmb{\\beta}}\\Vert\\pmb{g}\\Vert\n    \\sqrt{\\Vert\\tilde{\\pmb{\\beta}}\\Vert^2+(\\pmb{c}^\\top\\tilde{\\pmb{\\beta}})^2+\\frac{4\\sigma^2}{\\gamma}}\\Big].\\tag{32}\n\\end{align*}$$\n\n(Please refer to lines 221-228 of our main paper.)\n\n__Weakness 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.\n\n__Answer:__  Thank you for your suggestion. Following your recommendation, we will add the following remark for Theorem 3.1 in our revision to explain its content: \n\nRemark: Theorem 3.1 indicates that, as $n$ goes to $\\infty$, the parameter vector $\\tilde{\\pmb{w}}^*$ learned through the SCLS method (6) reliably converges to actual parameter vector $\\tilde{\\pmb{w}} _0$ in probability. \nWe then can utilize Theorem 2.4 to establish the estimation error of SPG-LS (1) solved by the SCLS (6).\n\n__Weakness 4.__ Theorem 3.1 appears very similar to Theorem 3.2. What’s the relationship between Theorem 3.1 and Theorem 3.2?\n\n__Answer:__  Thank you for your comments. Theorem 3.1 indicates that\n$$\\begin{align*}\n    \\lim _{n\\to \\infty}\\Vert\\tilde{\\pmb{w}}^*-\\tilde{\\pmb{w}} _0\\Vert \\stackrel{P}{\\longrightarrow} 0, \n\\end{align*}$$\nwhich corresponds to the estimation error analysis of the SCLS problem (6). Theorem 3.2 demonstrates that\n$$\\begin{align*}\n    \\lim _{n \\to \\infty}\\Vert\\pmb{w}^*-\\pmb{w} _0\\Vert \\stackrel{P}{\\longrightarrow} 0, \n\\end{align*}$$\nwhich corresponds to the estimation error of SPG-LS (1) recovered from the SCLS problem (6). Therefore, Theorem 3.1 is different from Theorem 3.2, and Theorem 3.1 can be used to derive Theorem 3.2.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
## The references mentioned in the Rebuttal to Reviewer PFXk. 

__For Weakness 1.__

[B1] Estimating the Error of Randomized Newton Methods: A Bootstrap Approach. ICML 2020

[B2] $\ell _{1, p}$-Norm Regularization: Error Bounds and Convergence Rate Analysis of First-Order Methods. ICML 2015

[B3] Addressing Function Approximation Error in Actor-Critic Methods. ICML 2018

[B4] Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected Error. NeurIPS 2021

[B5] A Comparison of Hamming Errors of Representative Variable Selection Methods. ICLR 2022

[B6] On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning. ICLR 2020

[B7] Generalization error of spectral algorithms. ICLR 2024

[B8] Error Estimation for Randomized Least-Squares Algorithms via the Bootstrap. ICML 2018

__For Weakness 3.__

[C1] Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression. NeurIPS 2023

[C2] Differentially Private Algorithms for Learning Mixtures of Separated Gaussians. NeurIPS 2019: 168-180

[C3] Some Constructions of Private, Efficient, and Optimal K-Norm and Elliptic Gaussian Noise. COLT 2024

[C4] Convergence of the EM Algorithm for Gaussian Mixtures with Unbalanced Mixing Coefficients. ICML 2012

[C5] Sparse Gaussian Conditional Random Fields: Algorithms, Theory, and Application to Energy Forecasting. ICML 2013

[C6] Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed. ICML 2021: 8936-8947

[C7] On the Properties of Kullback-Leibler Divergence Between Multivariate Gaussian Distributions. NeurIPS 2023

[C8] Precise Error Analysis of Regularized M-Estimators in High Dimensions. IEEE Trans. Inf. Theory, 2018

__For Question 7.__

[D1] Precise error analysis of regularized m-estimators in high dimensions. IEEE Trans. Inf. Theory. 2018.

[D2] The Noise-Sensitivity Phase Transition in Compressed Sensing. IEEE Trans. Inf. Theory. 2011

[D3] Positivity-preserving entropy stable schemes for the 1-D compressible Navier-Stokes equations: First-order approximation. J. Comput. Phys. 2022

[D4]. On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation. ICLR 2024

[D5] Tracking MPC Tuning in Continuous Time: A First-Order Approximation of Economic MPC. IEEE Control. Syst. Lett. 2023

[D6] Sharp MSE Bounds for Proximal Denoising. Found. Comput. Math. 2016

Meta-review: 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.
Decision: Accept (poster)