Low-Complexity Algorithm for Stackelberg Prediction Games with Global Optimality

1. Problem Definition

The paper addresses Stackelberg Prediction Games (SPGs), a framework modeling strategic interactions between a learner (leader) and a self-interested data provider (follower) in adversarial machine learning settings.

• The Setting: The learner trains a model (predictor $w$) to minimize prediction loss. The data provider, observing the model, strategically manipulates their input features ($x$) to influence the learner's prediction toward a desired label ($z$), subject to a regularization cost for manipulation.
• The Challenge: This interaction forms a bilevel optimization problem. The outer level minimizes the learner's loss, while the inner level represents the provider's best response. Even with least-squares losses (SPG-LS), this problem is generally NP-hard and non-convex due to the coupling between the leader's decision and the follower's response.
• Existing Limitations: Previous global solvers relied on reformulating the problem into Semidefinite Programming (SDP) or Second-Order Cone Programming (SOCP). While these guarantee global optimality, they require expensive spectral decompositions and conic programming, making them computationally intractable for high-dimensional or sparse datasets.

2. Methodology

The authors propose a novel, low-complexity solver based on the Alternating Direction Method of Multipliers (ADMM) applied to a specific reformulation of the problem.

A. Problem Reformulation (SCLS)

Building on recent work (Wang et al., 2022), the authors utilize the Spherically Constrained Least-Squares (SCLS) reformulation.

• Through a nonlinear change of variables, the original bilevel SPG-LS problem is transformed into minimizing a quadratic least-squares objective over the unit sphere:
  $$\min_{r} \| \hat{L}r - b \|_2^2 \quad \text{s.t.} \quad \|r\|_2 = 1$$
• This eliminates the need for conic constraints, reducing the problem to a standard quadratic program with a spherical constraint.

B. ADMM Formulation

To solve the SCLS problem efficiently, the authors introduce a consensus splitting strategy:

1. Variable Splitting: An auxiliary variable $s$ is introduced to separate the quadratic objective (dependent on $r$) from the spherical constraint (dependent on $s$).
   $$\min_{r,s} f(r) \quad \text{s.t.} \quad s - r = 0, \quad \|s\|_2 = 1$$
2. Augmented Lagrangian: The problem is solved using the scaled augmented Lagrangian, leading to three closed-form update steps per iteration:
   • $r$-update: Solves a linear system with a fixed, positive-definite coefficient matrix $(H + \frac{\rho}{2}I)$.
   • $s$-update: A simple projection of a vector onto the unit sphere.
   • Dual update: A standard scaled ascent step.

C. Low-Complexity Implementation (CD-ADMM)

A key innovation is the Cholesky Decomposition-based ADMM (CD-ADMM):

• Pre-factorization: Since the coefficient matrix in the $r$-update is constant throughout the iterations, the authors perform a one-time Cholesky factorization ($F = U^T U$) before the iterative loop begins.
• Inverse-Free Updates: Instead of explicitly computing the matrix inverse (which is $O(n^3)$ and numerically unstable), each iteration only requires two triangular solves ($O(n^2)$).
• Sparse Optimization: For sparse datasets, this approach leverages sparse Cholesky factorization, drastically reducing memory and computational overhead.

3. Key Contributions

1. Closed-Form ADMM Solver: Development of a simple, scalable ADMM algorithm for SCLS with fully explicit closed-form updates, avoiding complex manifold optimization or conic solvers.
2. Global Optimality Guarantees:
   • The authors prove strong duality for the consensus reformulation of the non-convex SCLS problem.
   • They demonstrate that the Lagrangian saddle point corresponds to the global optimum.
   • Under mild conditions, they prove that the ADMM iterates converge monotonically to a primal-dual limit point satisfying the global KKT conditions.
3. Inverse-Free Efficiency: The introduction of the CD-ADMM variant eliminates explicit matrix inversion, replacing it with a one-time factorization and cheap triangular solves. This makes the method particularly suitable for high-dimensional and sparse regimes.
4. Theoretical Convergence: Rigorous proofs showing that the proposed method converges to the global optimum, aligning with the theoretical guarantees of the underlying SCLS reformulation.

4. Experimental Results

The authors evaluated their method against state-of-the-art baselines: SDP, SOCP (global optimality benchmarks), and LTRSR (a leading iterative solver).

• Solution Quality: The proposed ADMM and CD-ADMM methods achieved global optimality comparable to SOCP/SDP, with relative errors ranging from $10^{-5}$ to $10^{-12}$ across real-world and synthetic datasets.
• Computational Efficiency:
  • Real-World Data: On datasets like Wine Quality and Residential Building, the proposed methods were orders of magnitude faster than SDP/SOCP.
  • High-Dimensional Sparse Data: In synthetic experiments with dimensions up to $n=30,000$ and sparsity $0.0001$, CD-ADMM was up to 500 times faster than SOCP.
  • Comparison with LTRSR: While LTRSR is efficient in low dimensions, CD-ADMM outperformed it in high-dimensional sparse regimes ($m \le n$) due to the efficiency of pre-computed sparse factorization. In over-determined regimes ($m \gg n$), LTRSR remained competitive, but CD-ADMM still offered significant speedups over conic solvers.
• Scalability: The method demonstrated robust scalability, with runtime growing linearly or near-linearly with problem size in sparse settings, whereas conic solvers struggled with memory and time constraints.

5. Significance

This paper provides a practical and theoretically sound solution to a class of adversarial learning problems that were previously limited to small-scale or low-dimensional applications due to computational bottlenecks.

• Bridging Theory and Practice: It proves that non-convex bilevel problems in SPGs can be solved globally without resorting to expensive conic programming.
• Enabling Large-Scale Adversarial Learning: By reducing the complexity from cubic (conic) to quadratic (triangular solves) with pre-computation, the method enables the deployment of Stackelberg prediction games in real-world, high-stakes scenarios (e.g., spam filtering, malware detection) involving massive, sparse datasets.
• Algorithmic Innovation: The specific adaptation of ADMM with consensus splitting and Cholesky pre-factorization for spherical constraints offers a template for solving similar non-convex constrained optimization problems efficiently.