PaperlayerView exact revision on arXiv

Source-linked AI summary

Preventing Model Extraction in Contextual Linear Optimization

Adam N. Elmachtoub, Tianyi Lin, Wenxuan Liu

arXiv:2610.29918v1cs.LGmath.OC

TL;DR

Decision outputs in contextual linear optimization can reveal a hidden predictor even though the cost-to-decision map is many-to-one. The paper establishes recovery conditions, proposes an adaptive boundary-sampling attack and a near-boundary perturbation defense, and finds that the defense can increase extraction error for evaluated attacks within tested query budgets.

  • Problem

    The paper asks whether context-query access to decision outputs can recover a hidden prediction model, despite the many-to-one mapping from costs to optimal decisions.

    Source: §1 · p. 1

  • Method

    The paper analyzes predictor recovery conditions, combines inverse optimization with boundary sampling for an adaptive attack, and perturbs decisions near decision boundaries as a defense.

    Source: §1 · p. 2

  • Results

    The defense can increase prediction error for evaluated attacks within the tested query budgets.

    Source: §6 · p. 8

  • Takeaways & Limitations

    The defense’s expected prediction-error lower bound applies to attackers that fit defended responses as optimal decisions under the evaluation distribution, and is nondecreasing in perturbation degree.

    Source: §6 · pp. 7–8

    Loss calibration gives exact global identification at zero inverse feasibility loss, but does not bound prediction error from small loss on a finite dataset.

    Source: §3.1 · p. 4

Abstract

from arXiv · show

Consider a contextual linear optimization problem, where a predict-then-optimize (PTO) system returns optimal decisions without revealing the cost vectors used in its downstream linear program. Our focus is on how to prevent attackers, who can submit context queries, from extracting the underlying prediction model. Although the cost-to-decision map is many-to-one, observations across contexts can reveal the underlying prediction model. For linear models, we provide sufficient conditions where the attacker can learn the model up to positive scaling by only observing the decision. These conditions motivate an adaptive attack that alternates inverse optimization with boundary sampling, i.e., using context queries leading to decision boundaries of the current attacker model. To prevent extraction, we propose a mechanism that perturbs decisions only when the predicted cost vector is near a decision boundary. We establish a regret bound in terms of the perturbation radius. For the attackers that fit the defended responses as optimal decisions under the evaluation distribution, we also prove a lower bound on expected extraction error. Experiments on synthetic instances and real data quantify the security-performance trade-off of the defense mechanism and illustrate that our defense can increase the extraction error.

1 INTRODUCTION

This paper asks when decision outputs in contextual linear optimization reveal a hidden predictor, despite the many-to-one cost-to-decision map, and how extraction can be mitigated without sacrificing decision quality. It establishes sufficient recovery conditions, develops an adaptive boundary-sampling attack and a near-boundary perturbation defense, and reports that the attack outperforms a non-adaptive baseline while the defense can increase extraction error at modest regret.

1 INTRODUCTION

  • The central questions are whether decision-level observations identify the predictor and how to mitigate extraction while preserving decision quality.Although costs are hidden and the decision map is many-to-one, boundary contexts can make small predicted-cost changes alter the returned decision.Source: §1 · p. 1
  • Under loss calibration, global inverse feasibility consistency is sufficient for recovering a linear predictor up to positive scaling under sufficient geometric and regularity conditions.The result motivates an adaptive attack alternating inverse optimization with queries near the current attacker model’s decision boundaries.Source: §1 · p. 2
  • The proposed defense randomizes decisions only near decision boundaries, with a regret upper bound linear in the boundary radius and an expected-error lower bound for response-fitting attackers.The expected-error lower bound is nondecreasing in the boundary radius.Source: §1 · p. 2
  • Boundary sampling achieves lower prediction error than non-adaptive inverse optimization, while the defense can increase evaluated attacks’ prediction error at modest regret.Experiments cover synthetic instances and a short video recommendation task.Source: §1 · p. 2
  • Differential privacy protects data privacy, whereas this work studies extraction of the deployed predictor from decision outputs.Inverse optimization is used to examine when decision consistency identifies that predictor.Source: §1 · p. 2

2 MODEL FORMULATION

The model formulation treats the deployed system as a linear predictor followed by a linear optimization problem over a compact, full-dimensional polytope. The attacker observes decisions from context queries and fits a linear substitute, with extraction measured by angular prediction loss and defense evaluated through security and regret.

2 MODEL FORMULATION

  • The decision-maker predicts costs as P_DM x and returns an optimal vertex of the downstream linear program over S = {w : Aw ≤ b}.S is assumed compact and full-dimensional, with distinct facets represented by the inequalities.Source: §2 · p. 3
  • The attacker knows the linear model structure but not P_DM, and learns P_a from queried contexts and returned decisions.The setup assumes d > n ≥ 2, rank(P_DM) = n, and excludes the zero attacker matrix.Source: §2 · p. 3
  • Prediction loss is the angular distance between P_a x and P_DM x, reflecting that positive rescaling of costs leaves the optimizer unchanged.The attacker succeeds when P_a = γP_DM for some γ > 0.Source: §2 · p. 3
  • A defense replaces the exact optimizer with a perturbed returned decision to impede model reconstruction while maintaining near-optimal decision quality.Classification model extraction can also be represented in the PTO framework as returning an optimal vertex corresponding to a predicted class.Source: §2 · p. 3
  • The framework measures security by expected prediction loss and decision quality by expected regret under an evaluation distribution.The regret analysis assumes finite expected norm of the deployed predicted cost under that distribution.Source: §2 · p. 3

3 MODEL EXTRACTION

The section asks when decision-only queries identify a hidden linear predictor, despite different costs sometimes inducing the same optimizer. Under sufficient geometric conditions, global decision consistency identifies the predictor up to positive scaling, motivating an adaptive attack that samples near decision boundaries.

3.1 Vulnerability identification

  • Loss calibration is an exact global identification property, but small inverse feasibility loss on a finite dataset does not itself bound prediction error.The identification claim concerns zero loss on all nonkernel contexts.Source: §3.1 · p. 4
  • The hypercube does not satisfy loss calibration, whereas the stated sufficient geometric condition applies to certain budget-constrained feasible sets.The hypercube’s calibration failure is established separately; failure of a sufficient condition alone would not prove failure.Source: §3.1 · p. 4
  • Under Assumption 3.4, global decision consistency identifies the attacker model as a positive scalar multiple of the deployed model.The result applies to nonzero attacker models and contexts outside the deployed model’s kernel.Source: §3.1 · p. 4

3.2 Algorithmic framework

  • The adaptive attack alternates inverse-optimization fitting with boundary sampling, querying facet directions and nearby contexts in adjacent normal cones.The sampling parameter M controls proximity to the facet directions.Source: §3.2 · pp. 4–5
  • Algorithm 1 terminates after finitely many updates under bounded-query and zero-loss update assumptions; smaller Δ makes its stopping criterion stricter and may require more updates.The stopping rule requires every observed decision to be Δ-optimal under the current attacker model.Source: §3.2 · p. 5
  • When the attacker model is misaligned, an arbitrarily near-boundary context can expose that misalignment through nonzero inverse feasibility loss.Boundary contexts constrain cost directions, and nearby contexts can enter incident normal cones.Source: §3.1 · p. 4, §3.2 · p. 5
  • Theorem 3.9 gives asymptotic prediction recovery when boundary sampling has uniform regularity and the specified update and stopping conditions hold.Uniform regularity prevents boundary representatives from becoming asymptotically uninformative.Source: §3.2 · pp. 5–6

4 PREVENTING MODEL EXTRACTION

The defense perturbs decisions only when predicted costs are near neighboring decision boundaries, aiming to impede extraction while limiting regret. For response-fitting attackers, the paper proves an expected prediction-error lower bound that is nondecreasing in the boundary radius.

4 PREVENTING MODEL EXTRACTION

  • The Gaussian-noise baseline perturbs predicted costs without using their distance to a decision boundary, and repeated queries can reveal its response distribution.It independently resamples noise for each query.Source: §4 · p. 6
  • The defense returns the true optimizer away from boundaries and randomizes among eligible neighboring decisions near a boundary, reusing cached outputs for repeated candidate sets.The radius ε controls eligibility; each new candidate set receives a uniformly sampled decision.Source: §4 · p. 6
  • The regret upper bound is linear in ε and also depends on feasible-set diameter and predicted-cost scale.The bound holds for every cache realization and test distribution with finite expected predicted-cost norm.Source: §4 · p. 6
  • For attackers fitting defended responses as optimal decisions, the paper proves an expected prediction-error lower bound that is nondecreasing in the boundary radius.The bound is under the stated population fitting condition.Source: §4 · p. 7

5 EXPERIMENTS

Experiments compare adaptive attacks and defenses on synthetic instances and a short-video recommendation task. Boundary sampling generally lowers prediction loss than the inverse-optimization baseline, while decision perturbation increases extraction error at modest regret in the reported settings.

5 EXPERIMENTS

  • Across tested decision dimensions, boundary sampling has lower median prediction loss than the inverse-optimization baseline, and it attains near-zero median loss across tested settings.At feature dimensions 15 and 20, uniform sampling has substantially higher loss after three iterations, and boundary sampling uses fewer samples to reach the stated threshold.Source: §5 · p. 7
  • At 3000 queries, all three attacks have higher median prediction loss with ε = 0.0015 than without perturbation, indicating finite-budget mitigation in the evaluated settings.The three strategies are boundary sampling, uniform sampling, and their equal mixture.Source: §5 · p. 7
  • Decision perturbation increases attacker prediction loss at modest regret and outperforms prediction perturbation in the reported comparisons.The comparison is limited to the reported attacks and parameter settings.Source: §5 · p. 7
  • On the short-video recommendation task, boundary sampling has lower prediction loss than inverse optimization at the lowest plotted regret levels, with both attacks’ loss increasing at larger regret.The increase is more pronounced for boundary sampling.Source: §5 · p. 7

6 CONCLUSION

The paper characterizes model-extraction vulnerability, develops an adaptive boundary-sampling attack, and proposes a near-boundary decision-perturbation defense. Experiments show that the defense can increase extraction error for evaluated attacks, while the theory bounds regret and expected prediction error under specified conditions.

6 CONCLUSION

  • Loss calibration characterizes vulnerability, while an adaptive inverse-optimization attack combines boundary sampling to reconstruct the hidden predictor from decision-level observations.The proposed defense perturbs decisions only when the predicted cost vector is near a decision boundary.Source: §6 · p. 7
  • The reported empirical trade-offs include attack performance as decision and feature dimensions vary, query-budget curves, and prediction-loss/regret comparisons on synthetic and short-video recommendation instances.Figure 2 reports prediction loss and observations needed to reach loss below 0.001; Figure 3 varies query budgets and defense settings; Figure 4 compares perturbation trade-offs.Source: Figure 2 · p. 8, Figure 3 · p. 8, Figure 4 · p. 8
  • The defense can increase prediction error for evaluated attacks within the tested query budgets.The paper also establishes a regret bound and a lower bound on expected prediction error for attackers fitting defended responses as optimal decisions under the evaluation distribution; that lower bound is nondecreasing in perturbation degree.Source: §6 · pp. 7–8
  • Future work includes analyzing attackers that explicitly model the defense and extending the analysis to nonlinear contextual optimization.Source: §6 · p. 8

A.1 Condition of loss calibration

The candidate space collects matrices consistent with the attacker’s boundary contexts. Under the stated assumptions, its dimension provides a criterion for loss calibration and a diagnostic available to the decision-maker.

A.1 Condition of loss calibration

  • The candidate space contains matrices whose images of contexts on each attacker boundary lie on the corresponding direction lines; it is a linear subspace that includes the zero matrix.The zero matrix is excluded from the attacker class.Source: §A.1 · p. 11
  • Under Assumption 3.4, every full-rank attacker matrix has a one-dimensional candidate space equal to its span.Source: §A.1 · p. 11
  • If the decision-maker’s candidate space is one-dimensional, every inverse-feasibility loss calibrates prediction loss.For a full-rank attacker with global inverse feasibility, this yields a positive-scaled match to the decision-maker’s matrix and zero prediction loss at every context.Source: §A.1 · p. 11
  • The decision-maker can test whether the candidate space is one-dimensional by solving a linear system in the entries of its prediction matrix.For each facet, the diagnostic uses d−n+1 linearly independent contexts whose predicted costs lie along that facet’s direction.Source: §A.1 · p. 11

A.2 Inverse optimization methods

The appendix compares inverse-optimization losses and methods for fitting the attacker’s prediction matrix. It defines distance and CaVE losses, relaxes the distance loss for continuity, and describes an ADMM solution approach.

A.2 Inverse optimization methods

  • The distance loss measures how far an observed decision is from the optimal solution set under the attacker’s predicted cost.It is zero exactly when every observed decision is optimal under the predicted cost, including when that cost is zero.Source: §A.2 · p. 12
  • The optimality-gap relaxation is continuous for positive ϵ, and its global minimizers converge to minimizers of the exact empirical distance loss as ϵ decreases to zero.At ϵ = 0, strong linear programming duality makes the relaxed constraints equivalent to optimality over the feasible set.Source: §A.2 · p. 12
  • CaVE loss measures angular misalignment between predicted costs and the observed decisions’ normal cones, and zero loss is equivalent to decision optimality for nonzero predictors.At zero predicted cost, the angular summand is defined as zero; CaVE loss can be discontinuous there.Source: §A.2 · pp. 12–13
  • ADMM fits the prediction matrix through consensus updates over local matrices, multipliers, and active-constraint variables, but it has no global convergence guarantee.The reported experiment finds near-zero optimality gaps for ADMM and Tang and Khalil’s method; the global solver attains the smallest reported CaVE loss.Source: §A.2 · pp. 13–14

A.3 Sampling algorithms

Boundary sampling targets contexts near the attacker model’s decision boundaries, while uniform sampling explores predicted cost directions without targeting those boundaries. Under stated regularity conditions, the analysis establishes recovery guarantees for unrestricted and restricted context regions.

A.3 Sampling algorithms

  • Uniform sampling draws predicted-cost directions uniformly from the unit sphere and maps them to contexts, whereas boundary sampling specifically targets downstream decision boundaries.Both are adaptive because contexts are chosen using the current attacker matrix.Source: §A.3 · pp. 14, 16
  • Boundary sampling queries contexts along facet boundary directions and nearby contexts inside incident normal cones, where a misaligned attacker model can be exposed by a nonzero inverse-feasibility loss.The parameter M controls proximity to the boundary directions.Source: §A.3 · pp. 14–15
  • A near-boundary query that returns a vertex other than the attacker’s predicted optimizer has suboptimality loss above ∆, preventing termination at that call.The stopping condition couples M and ∆ so the procedure cannot stop while a prescribed near-boundary response disagrees with its unique predicted optimizer.Source: §A.3 · p. 15
  • Under the theorem’s regularity and update assumptions, boundary sampling terminates in finitely many inverse-optimization updates and its normalized attacker matrix converges to the deployed matrix up to positive scaling.The sufficient coupled choice M(∆) → ∞ and ∆M(∆) → 0 as ∆ ↓ 0 supports the stated stopping condition.Source: §A.3 · pp. 15–16

A.4 Restricted context region

  • For a restricted query region, n + 1 suitably positioned facet normals suffice for decision consistency to identify the predictor up to positive scaling; restricted boundary sampling also has a convergence guarantee under stated regularity conditions.For each selected facet, the region must contain an interior context whose deployed cost points along that facet’s inward direction.Source: §A.4 · p. 16

A.5 Experiment setup

The experiments evaluate attacks and defenses on synthetic linear data and KuaiRand recommendation data. They compare adaptive sampling strategies with a nonadaptive inverse-optimization baseline and measure extraction error alongside decision-maker regret.

Synthetic instances

  • Synthetic instances use randomly generated contexts and costs to train a linear-regression decision-maker model, followed by fractional-knapsack optimization on queried contexts.Context features are drawn coordinatewise from U[0, 20], and the downstream problem models resource allocation.Source: §A.5 · p. 17

Experimental protocol

  • Boundary sampling, uniform sampling, and a nonadaptive inverse-optimization baseline are compared, with adaptive methods alternating sampling and fitting while the baseline uses a nonadaptive context batch.Attack comparisons report median prediction loss across 100 repetitions; defense trade-off experiments record attacker prediction loss and decision-maker regret.Source: §A.5 · p. 17

Real data

  • The KuaiRand experiment trains on 800 users and tests on the remaining users, using 18-dimensional user features and five clustered video types to estimate click-through rates.The platform fits a linear predictor and optimizes recommendations with k = ⌈n/2⌉.Source: §A.5 · p. 17

A.6 Additional experimental results

Additional experiments examine attack behavior under parameter changes, model misspecification, and larger problem sizes, alongside the defense’s security–regret trade-off. Results show lower prediction loss with boundary sampling than with the non-adaptive inverse-optimization baseline in tested settings, while defense outcomes depend on its parameter and implementation assumptions.

Attacker’s coefficient

  • For fixed M, larger Δ is generally associated with fewer iterations and greater prediction loss, while both change little once Δ is sufficiently small.The condition Δ(M + K − 1) < ηS suffices for the stopping argument but is not established as a sharp threshold.Source: §A.6 · p. 18
  • The update bound has no explicit dependence on M under a common query-norm bound R, although observed iterations can depend on M.Prediction recovery is established in a coupled limit in M and Δ under uniform-sampling regularity.Source: §A.6 · p. 18

Attacker’s robustness to misspecification

  • Prediction loss is below 0.01 for the evaluated linear attacks against both MLP and SVR deployed models, showing approximation of their prediction directions in these experiments.The linear attacker is evaluated against a one-hidden-layer ReLU MLP and Gaussian-kernel SVR.Source: §A.6 · pp. 18–19
  • Larger γ is generally associated with greater prediction loss over the tested range for data with a quadratic component and zero-mean Gaussian noise.The decision-maker fits an MLP or SVR, while the attacker retains a linear model class.Source: §A.6 · p. 19

Large-scale optimization problem

  • Uniform sampling uses 5n new queries per iteration, but time per iteration increases as n grows despite small prediction losses without defense.The inverse-fitting problem size depends on the accumulated dataset, so linear new queries per iteration alone does not establish a polynomial bound on total attack time.Source: §A.6 · pp. 19–20, Figure 9 · p. 19

Defender’s robustness

  • The restricted-neighbor defense shows a security–performance trade-off on fractional Knapsack instances with n = 20, and prediction loss and regret generally increase across tested ϵ values.The regret bound requires every selected neighbor to pass the angular eligibility test; the expected-error bound assumes all eligible neighbors are included.Source: Figure 10 · p. 19, §A.6 · p. 20, Figure 11 · p. 20

B PROOF

The proofs establish conditions for positive-scale identification of the underlying model and derive extraction-error and algorithmic guarantees, including convergence of the normalized projected attacker model as the perturbation radius vanishes.

Proof of Lemma 3.3

  • All inverse feasibility losses share the same global zero-loss set, and calibration holds exactly when that set equals the set of matrices with globally correct prediction directions.If the sets differ, a matrix in their difference has zero inverse feasibility loss everywhere but positive prediction loss at some nonkernel context.Source: B PROOF · p. 21
  • On an n-dimensional hypercube, an admissible attacker can preserve every optimal decision while having nonzero prediction loss, so no inverse feasibility loss calibrates prediction loss.The construction rescales one transformed cost coordinate by 2, preserving coordinate-wise signs and optimal sets but changing the direction at a selected context.Source: B PROOF · p. 21

Proof of Theorem 3.5

  • Under Assumption 3.4, global decision consistency forces the attacker matrix to equal a positive scalar multiple of the deployed matrix.The proof first establishes ker(P_DM) ⊆ ker(P_a), writes P_a = B P_DM, and then shows B = γI_n for γ > 0.Source: B PROOF · p. 21

Proof of Proposition 3.6

  • If a full-row-rank attacker matrix is globally decision-consistent, then its prediction loss is zero at every context where its cost lies on a facet ray.Consistency yields P_a = B P_DM with B r_i = λ_i r_i and λ_i > 0; the boundary costs are positively aligned.Source: B PROOF · p. 22

Proof of Proposition 3.7

  • The adaptive algorithm terminates after finitely many updates because any two nonterminal iterates are separated by more than ∆/(R L_e) in Frobenius norm.The proof bounds the number of inverse optimization updates by at most (1 + 2R L_e/∆)nd.Source: B PROOF · p. 22

Proof of Proposition 3.8

  • If prediction loss is nonzero, some inverse-infeasible context must lie within ϵ of a decision boundary of the attacker model.Otherwise, consistency near every facet and the stated assumptions imply P_DM = γP_a for γ > 0, contradicting nonzero prediction loss.Source: B PROOF · p. 22

Proof of Theorem 4.2

  • A defended response different from the true optimizer requires angular separation, while fitting it as attacker-optimal is guaranteed under a stated margin-gap condition.The proof uses the distance between the true and attacker normal cones to bound separation by the two costs’ margins; it also derives a cache-randomness mismatch probability of 1 − 1/|Wϵ(x)| and shows Bϵ(Q) is nondecreasing in ϵ.Source: B PROOF · p. 23

Proof of Theorem A.3

  • With the stated sampling and conditioning assumptions, the algorithm’s terminal attacker matrices converge, after normalization, to the deployed matrix and their prediction loss vanishes off its kernel.The proof obtains approximate alignment on boundary representatives, then uses the representative conditioning bound to establish matrix convergence.Source: B PROOF · pp. 24–25

B PROOF

  • The selected n + 1 normals force B = γI_n with γ > 0, yielding P a = γP DM.This follows from the selected normals’ independent directions and the condition P a ≠ 0.Source: B PROOF · p. 25
  • As ∆p → 0, the normalized projected attacker matrix Up converges to P DM/∥P DM∥F under Assumption 3.4 and σmin(Xi,p) ≥ κ.The proof uses retained queries from selected blocks, whose boundary representatives have norm at most R, and shows their projected costs approach nonnegative multiples of the selected normals.Source: B PROOF · p. 25

Related papers

Loading 2610.29918v1…