Research map / Learning theory and algorithms / Prediction and decision losses

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

NeurIPS 2024 · Learning theory and algorithms › Prediction and decision losses · approach: Adaptive testing and experiments

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives a CGMT-based asymptotic error analysis proving that the SCLS method for the Stackelberg prediction game with least squares loss (SPG-LS) recovers the true learner w0 in probability as n grows, with Gaussian inputs and synthetic simulations.

Problem

The SCLS method is the state-of-the-art solver for the least-squares Stackelberg prediction game (SPG-LS), but it lacks theoretical analysis of its estimation error, which limits its trust in large-scale use.

Approach

Reframes the SCLS estimation error as a primary optimization problem via a first-order linearization of the constraint and conjugate duality, then applies the Convex Gaussian min-max theorem to reduce it to a deterministic auxiliary problem whose minimizer is zero, yielding consistency of the SCLS learner.

Key results

• Under Gaussian inputs with d/n tending to a value in (0,1), the estimation error ||w* - w0|| of SCLS converges to 0 in probability (Theorem 4.3).
• Simulations with d/n = 0.5 and sparsity k/d in {1, 0.1, 0.01, 0.001} show the error decreasing toward 0 as n grows to 16000, for gamma = 0.1 and 0.01.
• Additional experiments at d/n = 1/3 show the same decay to zero, consistent with the theory.

Measured effects reported in the paper

Limitations

• Analysis restricted to Gaussian inputs, responses and noise; non-Gaussian settings left for future work.
• Relies on a first-order linearization of the constraint that is justified only as the estimation error goes to zero.
• Experiments are limited to synthetic data with a single dimension ratio setting for the main figure.

Experimental setup

Datasets: synthetic Gaussian data (x, z ~ N(0, I))

Benchmarks: synthetic SPG-LS simulations with n up to 16000

Metrics: estimation error ||w* - w0||

Baselines: QFP method SOCP method SCLS method

Builds on: SCLS method Convex Gaussian min-max theorem Gordon's Gaussian min-max theorem SPG-LS (Bishop et al. 2020)

Closest papers by meaning

• Solving Stackelberg Prediction Game with Least Squares Loss via Spherically Constrained Least Squares Reformulation (ICML 2022 · similarity 0.96)
• Fast Algorithms for Stackelberg Prediction Game with Least Squares Loss (ICML 2021 · similarity 0.89)
• Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents (NeurIPS 2023 · similarity 0.85)
• Prediction-Intervention Games and Invariant Sets (NeurIPS 2026 · similarity 0.83)
• Learning in Stackelberg Mean Field Games: A Non-Asymptotic Analysis (NeurIPS 2025 · similarity 0.83)
• Bandits with Preference Feedback: A Stackelberg Game Perspective (NeurIPS 2024 · similarity 0.82)