Introduction
Many decision-making problems can be formulated as optimization problems whose parameters are unknown and must be inferred from contexts. For example, a recommendation system uses user features to predict click probabilities before optimizing which items to display. In portfolio optimization, asset returns must be estimated before making allocation decisions. This class of problems is referred to as contextual optimization [28 ] . A widely adopted approach to contextual optimization is the predict-then-optimize (PTO) framework [10 ] . In the linear optimization setting studied here, PTO proceeds in two stages: (i) a machine learning (ML) model predicts the unknown objective cost vector from a given context and (ii) the predicted cost vector is used to solve the downstream linear optimization problem and produce a decision. Due to its modularity and empirical effectiveness, PTO has been successfully applied across a broad range of application domains, including recommendation systems, e-commerce, logistics, and resource allocation.
This setting raises a model-security question: can an attacker recover the hidden prediction model by interacting only with the optimization system’s decision outputs? Such a threat is known as a model extraction attack: the attacker repeatedly queries the deployed system with contexts (perhaps through an API) and uses the returned decisions to build a substitute prediction model. Successful extraction can allow the attacker to replicate the service while bypassing access costs or usage restrictions, and moreover, can provide a stepping stone for user privacy or inference attacks [21 , 24 , 31 , 29 , 16 ] and information leakage [34 , 39 ] . At first glance, the optimization layer appears to make extraction difficult. The attacker does not observe predicted costs directly, and the map from costs to optimal decisions is many-to-one in linear optimization. This intuition is incomplete: the same polyhedral geometry that hides costs in the interior of normal cones creates boundary contexts where small changes in predicted costs change the returned decision. This leads to two central questions: (i) when do decision-level observations identify the underlying prediction model, and (ii) how can we mitigate extraction while preserving decision quality?
Existing approaches do not answer these questions directly. Prior work on privacy in contextual decision-making has studied differential privacy (DP) [18 ] , which protects training data but does not directly defend the deployed predictive model against extraction. A second related line is inverse optimization [5 ] , which infers unknown parameters of an optimization problem from observed optimal decisions. While inverse optimization includes both fixed-parameter and contextual formulations, our focus is on whether decision-level observations identify the deployed predictor. More importantly, because the decision map is many-to-one, decision consistency does not in general imply prediction recovery.
In this paper, we focus on model extraction in contextual linear optimization. First, we study vulnerability through a loss calibration condition that links global inverse feasibility consistency to prediction recovery. Motivated by this condition, we then develop an adaptive attack that combines inverse optimization with boundary sampling to reconstruct the hidden predictor using only decision-level observations. This insight motivates a defense that perturbs the returned decision only when the deployed predictor’s cost vector is near a decision boundary. Our theory establishes a regret bound for linear predictors and a lower bound on expected prediction error under a response-matching condition. Our experiments on synthetic instances and real data examine the security-performance trade-off.
Contributions. We formalize model extraction in contextual linear optimization under the predict-then-optimize paradigm and study when the decision-level observations identify the predictor and how to mitigate extraction while limiting the loss in decision quality. Our contributions are summarized as follows:
We identify loss calibration as a vulnerability criterion: if it holds, global inverse feasibility consistency is sufficient for prediction recovery up to positive scaling. For linear predictors and unrestricted contextual queries, we use boundary contexts to establish this identification result under sufficient geometric and regularity conditions. This motivates an adaptive attack that alternates inverse optimization with boundary sampling, which targets contexts near decision boundaries of the current attacker model.
We propose a decision perturbation defense that randomizes only near decision boundaries and prove a regret upper bound that is linear in the boundary radius. For attackers that fit the defended responses as optimal decisions under the evaluation distribution, we also prove a lower bound on expected prediction error. This lower bound is nondecreasing in the boundary radius.
In the tested settings, boundary sampling achieves lower prediction error than the non-adaptive inverse-optimization baseline, while the proposed defense can increase the prediction error of the evaluated attacks at modest regret.
Related work. Privacy in contextual optimization has been studied through differential privacy, including personalized pricing and revenue management [7 , 8 , 18 , 20 , 33 , 9 , 30 ] (Fu et al. 2026). These works are complementary to ours: DP protects data privacy, whereas we study model extraction attacks that target the deployed predictor itself. In model extraction attacks, the goal is to recover a substitute model via query access to a target system [38 , 26 , 22 , 19 , 6 , 23 , 37 , 15 , 11 , 17 , 14 ] . Our work is also related to adaptive query attacks [36 , 40 ] . In our setting, the attacker observes downstream decisions but not predicted cost vectors. Since the prediction-to-decision map is generally many-to-one, we examine how the geometry of the downstream feasible set affects predictor recovery.
Another related line concerns inverse optimization, which infers unknown problem parameters from observed decisions [4 , 1 , 2 , 32 , 3 , 5 , 25 ] . We use inverse optimization to study when decision consistency identifies the underlying predictor.
Notation. We write x ⊥ y x \perp y x ⊥ y ∠ ( x , y ) \angle(x,y) ∠ ( x , y ) a 1 , … , a k a_1,\ldots,a_k a 1 , … , a k polycone { a 1 , … , a k } \operatorname{polycone}\{a_1,\ldots,a_k\} polycone { a 1 , … , a k } S ⊆ R n S \subseteq\mathbb{R}^n S ⊆ R n V V V w ∈ V w \in V w ∈ V cone ( w ) \operatorname{cone}(w) cone ( w ) c ∈ R n c \in\mathbb{R}^n c ∈ R n c T ( u − w ) ≥ 0 c^\mathsf{T}(u-w) \ge0 c T ( u − w ) ≥ 0 u ∈ S u \in S u ∈ S N V ( w ) = { v ∈ V : dim ( cone ( v ) ∩ cone ( w ) ) = n − 1 } N_V(w) = \{v \in V : \dim(\operatorname{cone}(v) \cap\operatorname{cone}(w)) = n - 1\} N V ( w ) = { v ∈ V : dim ( cone ( v ) ∩ cone ( w )) = n − 1 } cone ( w ) \operatorname{cone}(w) cone ( w ) c ≠ 0 c \ne0 c = 0 cone ( w ) \operatorname{cone}(w) cone ( w ) ∠ ( c , cone ( w ) ) = inf u ∈ cone ( w ) ∖ { 0 } ∠ ( c , u ) \angle(c,\operatorname{cone}(w)) = \inf_{u \in\operatorname{cone}(w)\setminus\{0\}} \angle(c,u) ∠ ( c , cone ( w )) = inf u ∈ cone ( w ) ∖ { 0 } ∠ ( c , u )
Model Formulation
We study model extraction in contextual linear optimization. This setting involves three roles: a decision-maker, an attacker, and some users. For each user, the decision-maker maps contexts to an action through a predict-then-optimize (PTO) pipeline. Given a cost vector c ∈ R n c \in\mathbb{R}^n c ∈ R n
z ⋆ ( c ) = min w ∈ S c ⊤ w , (1) z^\star(c) = \min_{w \in S} c^\top w, \tag*{(1)} z ⋆ ( c ) = w ∈ S min c ⊤ w , (1) where S = { w ∈ R n : A w ≤ b } S = \{w \in\mathbb{R}^n : Aw \le b\} S = { w ∈ R n : A w ≤ b } A w ≤ b Aw \le b A w ≤ b S S S A A A a 1 ⊤ , … , a m ⊤ a_1^\top,\ldots,a_m^\top a 1 ⊤ , … , a m ⊤ W ⋆ ( c ) = argmin w ∈ S c ⊤ w W^\star(c) = \operatorname*{argmin}_{w \in S} c^\top w W ⋆ ( c ) = argmin w ∈ S c ⊤ w w ⋆ ( c ) ∈ W ⋆ ( c ) ∩ V w^\star(c) \in W^\star(c) \cap V w ⋆ ( c ) ∈ W ⋆ ( c ) ∩ V 1
In the PTO pipeline, the user’s true cost vector is not observed. The decision-maker instead learns a prediction model c ^ = p ( x ) \hat{c} = p(x) c ^ = p ( x ) x ∈ R d x \in\mathbb{R}^d x ∈ R d w ~ ( x ) = w ⋆ ( p ( x ) ) ∈ W ⋆ ( p ( x ) ) \widetilde{w}(x) = w^\star(p(x)) \in W^\star(p(x)) w ( x ) = w ⋆ ( p ( x )) ∈ W ⋆ ( p ( x )) 2 x x x w ~ ( x ) \widetilde{w}(x) w ( x ) 3 p ( x ) = P D M x p(x) = P^{DM}x p ( x ) = P D M x P D M ∈ R n × d P^{DM} \in\mathbb{R}^{n \times d} P D M ∈ R n × d P D M P^{DM} P D M p a ( x ) = P a x p^a(x) = P^a x p a ( x ) = P a x P a ∈ R n × d P^a \in\mathbb{R}^{n \times d} P a ∈ R n × d d > n ≥ 2 d > n \ge2 d > n ≥ 2 rank ( P D M ) = n \operatorname{rank}(P^{DM}) = n rank ( P D M ) = n P a = 0 P^a = 0 P a = 0
Attackers. A key step is to define the attacker’s prediction loss. Since positive scaling of the cost vector does not change the optimal solution set of a linear program, the attacker succeeds whenever it recovers a prediction model P a = γ P D M P^a = \gamma P^{DM} P a = γ P D M γ > 0 \gamma> 0 γ > 0 d > n d > n d > n ∠ ( 0 , 0 ) = 0 \angle(0,0) = 0 ∠ ( 0 , 0 ) = 0 ∠ ( u , v ) = π 2 \angle(u,v) = \frac{\pi}{2} ∠ ( u , v ) = 2 π u u u v v v
Definition 2.1 (Prediction Loss). Given a context x x x P a P^a P a P D M P^{DM} P D M L p r e d ( P a , P D M , x ) = ∠ ( P a x , P D M x ) L_{\mathrm{pred}}(P^a,P^{DM},x) = \angle(P^a x,P^{DM}x) L pred ( P a , P D M , x ) = ∠ ( P a x , P D M x ) D = { ( x i , w i ) } i = 1 N D = \{(x_i,w_i)\}_{i=1}^N D = {( x i , w i ) } i = 1 N L p r e d ( P a , P D M ; D ) = 1 N ∑ i = 1 N ∠ ( P a x i , P D M x i ) L_{\mathrm{pred}}(P^a,P^{DM};D) = \frac{1}{N}\sum_{i=1}^N \angle(P^a x_i,P^{DM}x_i) L pred ( P a , P D M ; D ) = N 1 ∑ i = 1 N ∠ ( P a x i , P D M x i )
We assume that the attacker can make N N N x i ∈ R d x_i \in\mathbb{R}^d x i ∈ R d x i x_i x i w i = w ⋆ ( p ( x i ) ) w_i = w^\star(p(x_i)) w i = w ⋆ ( p ( x i )) D a = { ( x i , w i ) } i = 1 N D^a = \{(x_i,w_i)\}_{i=1}^N D a = {( x i , w i ) } i = 1 N P a = A ( D a ) P^a = \mathcal{A}(D^a) P a = A ( D a ) A \mathcal{A} A Q Q Q E [ L p r e d ( P a , P D M , x ) ] \mathbb{E}[L_{\mathrm{pred}}(P^a,P^{DM},x)] E [ L pred ( P a , P D M , x )] x ∼ Q x \sim Q x ∼ Q
Proposition 2.2. For the simplex S = { w ∈ R n : ∑ j = 1 n w j = 1 } S = \{w \in\mathbb{R}^n : \sum_{j=1}^n w_j = 1\} S = { w ∈ R n : ∑ j = 1 n w j = 1 } p ( x ) p(x) p ( x ) n n n w ⋆ ( p ( x ) ) = e i w^\star(p(x)) = e_i w ⋆ ( p ( x )) = e i i i i n n n p ( x ) p(x) p ( x )
Defense. To defend against extraction, the decision-maker may strategically modify the query interface to restrict the information revealed to adversarial users. Instead of returning the exact optimizer w ⋆ ( p ( x ) ) w^\star(p(x)) w ⋆ ( p ( x )) w ~ ( x ) \widetilde{w}(x) w ( x ) x i x_i x i w i = w ~ ( x i ) w_i = \widetilde{w}(x_i) w i = w ( x i )
This interaction admits a Stackelberg interpretation: the decision-maker commits to a response mechanism before the attacker chooses its queries and learning procedure. For a specified attack, the security-performance trade-off is measured by
Security: E [ L p r e d ( P a , P D M , x ) ] \mathbb{E}[L_{\mathrm{pred}}(P^a,P^{DM},x)] E [ L pred ( P a , P D M , x )]
Performance: E [ p ( x ) ⊤ ( w ~ ( x ) − w ⋆ ( p ( x ) ) ) ] \mathbb{E}[p(x)^\top(\widetilde{w}(x)-w^\star(p(x)))] E [ p ( x ) ⊤ ( w ( x ) − w ⋆ ( p ( x )))]
The expectations are taken over an independent x ∼ Q x \sim Q x ∼ Q E x ∼ Q ∥ p ( x ) ∥ 2 < + ∞ \mathbb{E}_{x\sim Q}\lVert p(x)\rVert_2 < +\infty E x ∼ Q ∥ p ( x ) ∥ 2 < + ∞
Model Extraction
We characterize how decision-level query responses can reveal the underlying prediction model. Throughout this section, we assume that no defensive mechanism is deployed, so the decision-maker returns the true optimal decision w ~ ( x ) = w ⋆ ( P D M x ) \widetilde{w}(x) = w^\star(P^{DM}x) w ( x ) = w ⋆ ( P D M x )
Vulnerability identification
The attacker first assesses whether the decision-maker is vulnerable to model extraction, where vulnerability means that the prediction model can be recovered using decision-level queries. Since P D M x P^{DM}x P D M x L p r e d ( ⋅ , P D M , x ) L_{\mathrm{pred}}(\cdot,P^{DM},x) L pred ( ⋅ , P D M , x ) P D M P^{DM} P D M w ⋆ ( P D M x ) w^\star(P^{DM}x) w ⋆ ( P D M x ) [5 ] . Given a query-response dataset D = { ( x i , w i ) } i = 1 N D=\{(x_i,w_i)\}_{i=1}^N D = {( x i , w i ) } i = 1 N
P i n v ( D ) = { P ≠ 0 n × d : w i ∈ W ⋆ ( P x i ) , ∀ ( x i , w i ) ∈ D } . \mathcal{P}_{\mathrm{inv}}(D)=\{P\ne0^{n\times d}:w_i\in W^\star(Px_i),\ \forall(x_i,w_i)\in D\}. P inv ( D ) = { P = 0 n × d : w i ∈ W ⋆ ( P x i ) , ∀ ( x i , w i ) ∈ D } . We allow P x i = 0 Px_i=0 P x i = 0
Definition 3.1. A nonnegative loss L ( ⋅ , P D M ; D ) L(\cdot,P^{DM};D) L ( ⋅ , P D M ; D ) D D D L ( P , P D M ; D ) = 0 ⟺ P ∈ P i n v ( D ) L(P,P^{DM};D)=0\Longleftrightarrow P\in\mathcal{P}_{\mathrm{inv}}(D) L ( P , P D M ; D ) = 0 ⟺ P ∈ P inv ( D ) L ( P , P D M ; x ) = L ( P , P D M ; { ( x , w ⋆ ( P D M x ) ) } ) L(P,P^{DM};x)=L(P,P^{DM};\{(x,w^\star(P^{DM}x))\}) L ( P , P D M ; x ) = L ( P , P D M ; {( x , w ⋆ ( P D M x ))}) x ∈ R d x\in\mathbb{R}^d x ∈ R d
Achieving zero inverse feasibility loss enforces decision consistency on the observed queries. However, decision consistency alone does not in general imply prediction recovery since different cost vectors can induce the same optimal decision. We thus need to identify when inverse feasibility losses are appropriate surrogates for the prediction loss.
Definition 3.2. An inverse feasibility loss calibrates the prediction loss if, for any attacker model P a P^a P a L ( P a , P D M ; x ) = 0 L(P^a,P^{DM};x)=0 L ( P a , P D M ; x ) = 0 x ∉ ker ( P D M ) x\notin\ker(P^{DM}) x ∈ / ker ( P D M ) L p r e d ( P a , P D M ; x ) = 0 L_{\mathrm{pred}}(P^a,P^{DM};x)=0 L pred ( P a , P D M ; x ) = 0 x ∉ ker ( P D M ) x\notin\ker(P^{DM}) x ∈ / ker ( P D M )
Loss calibration is an exact global identification property: zero inverse feasibility loss on all nonkernel contexts identifies the predictor up to positive scaling. It does not itself bound prediction error from a small loss on a finite dataset. The following lemma shows that for a fixed downstream problem, calibration holds for either all inverse feasibility losses or none.
Lemma 3.3. The loss calibration property holds for either all inverse feasibility losses or none. If S S S n n n
We provide a sufficient condition under which the loss calibration property holds in the following assumption.
Assumption 3.4. There exist n + 1 n+1 n + 1 { a k i } i = 1 n + 1 \{a_{k_i}\}_{i=1}^{n+1} { a k i } i = 1 n + 1 a k 1 , … , a k n a_{k_1},\ldots,a_{k_n} a k 1 , … , a k n a k n + 1 = ∑ i = 1 n β i a k i a_{k_{n+1}}=\sum_{i=1}^n\beta_i a_{k_i} a k n + 1 = ∑ i = 1 n β i a k i β i ≠ 0 \beta_i\ne0 β i = 0 i i i
Theorem 3.5. Suppose Assumption 3.4 holds. Then, if a nonzero attacker model P a P^a P a w ⋆ ( P D M x ) ∈ W ⋆ ( P a x ) w^\star(P^{DM}x)\in W^\star(P^ax) w ⋆ ( P D M x ) ∈ W ⋆ ( P a x ) x ∉ ker ( P D M ) x\notin\ker(P^{DM}) x ∈ / ker ( P D M ) P a = γ P D M P^a=\gamma P^{DM} P a = γ P D M γ > 0 \gamma>0 γ > 0 Consequently, every inverse feasibility loss calibrates the prediction loss.
Table 1.
The geometry behind Theorem 3.5 also motivates the use of boundary contexts . Indeed, we define r i = a i ∥ a i ∥ r_i=\frac{a_i}{\lVert a_i\rVert} r i = ∥ a i ∥ a i i i i P a x ˉ = α r i P^a\bar{x}=\alpha r_i P a x ˉ = α r i α > 0 \alpha>0 α > 0
Proposition 3.6. Suppose that the rank of P a P^a P a n n n w ⋆ ( P D M x ) ∈ W ⋆ ( P a x ) w^\star(P^{DM}x)\in W^\star(P^ax) w ⋆ ( P D M x ) ∈ W ⋆ ( P a x ) x ∉ ker ( P D M ) x\notin\ker(P^{DM}) x ∈ / ker ( P D M ) L p r e d ( P a , P D M , x ˉ ) = 0 L_{\mathrm{pred}}(P^a,P^{DM},\bar{x})=0 L pred ( P a , P D M , x ˉ ) = 0 x ˉ \bar{x} x ˉ
Proposition 3.6 shows that global decision consistency fixes the cost direction at boundary contexts. To establish Theorem 3.5, global consistency first gives P a = B P D M P^a=BP^{DM} P a = B P D M B a k i = λ i a k i Ba_{k_i}=\lambda_i a_{k_i} B a k i = λ i a k i λ i > 0 \lambda_i>0 λ i > 0 B B B β i ( λ k i − λ k n + 1 ) = 0 \beta_i(\lambda_{k_i}-\lambda_{k_{n+1}})=0 β i ( λ k i − λ k n + 1 ) = 0 i i i β i \beta_i β i B B B P a ≠ 0 P^a\ne0 P a = 0
Assumption 3.4 holds for various application problems with S = { w : 0 ≤ w ≤ 1 , a T w ≤ b } S=\{w:0\le w\le1,a^\mathsf{T}w\le b\} S = { w : 0 ≤ w ≤ 1 , a T w ≤ b } a i > 0 a_i>0 a i > 0 i i i 0 < b < ∑ i a i 0<b<\sum_i a_i 0 < b < ∑ i a i − e 1 , … , − e n -e_1,\ldots,-e_n − e 1 , … , − e n a a a a = ∑ i ( − a i ) ( − e i ) a=\sum_i(-a_i)(-e_i) a = ∑ i ( − a i ) ( − e i ) { ± e i } i = 1 n \{\pm e_i\}_{i=1}^n { ± e i } i = 1 n w ⋆ ( c ) = c ∥ c ∥ w^\star(c)=\frac{c}{\lVert c\rVert} w ⋆ ( c ) = ∥ c ∥ c c ≠ 0 c\ne0 c = 0
Algorithmic framework
Under Assumption 3.4, global decision consistency implies prediction recovery. This motivates the adaptive attack in Algorithm 1 that alternates inverse optimization with sampling. The algorithm stops when every observed decision is Δ \Delta Δ P t P^t P t
Proposition 3.7. Suppose ∥ P 0 ∥ F = 1 \lVert P^0\rVert_F=1 ∥ P 0 ∥ F = 1 ∥ x i ∥ ≤ R \lVert x_i\rVert\le R ∥ x i ∥ ≤ R R > 0 R>0 R > 0 Δ > 0 \Delta>0 Δ > 0 ( 1 + 2 R L e Δ ) n d \left(1+\frac{2RL_e}{\Delta}\right)^{nd} ( 1 + Δ 2 R L e ) n d L e = max u , v ∈ V ∥ u − v ∥ L_e=\max_{u,v\in V}\lVert u-v\rVert L e = max u , v ∈ V ∥ u − v ∥
The tolerance Δ \Delta Δ Δ \Delta Δ
Inverse optimization. The inverse optimization step minimizes an inverse feasibility loss on the current dataset D t D^t D t L S O ( P , P D M , x i ) = ( P x i ) ⊤ ( w i − w ∗ ( P x i ) ) L_{\mathrm{SO}}(P,P^{DM},x_i)=(Px_i)^\top(w_i-w^*(Px_i)) L SO ( P , P D M , x i ) = ( P x i ) ⊤ ( w i − w ∗ ( P x i )) w i = w ∗ ( P D M x i ) w_i=w^*(P^{DM}x_i) w i = w ∗ ( P D M x i ) L S O ( P , P D M ; D ) = ∑ ( x i , w i ) ∈ D L S O ( P , P D M , x i ) L_{\mathrm{SO}}(P,P^{DM};D)=\sum_{(x_i,w_i)\in D}L_{\mathrm{SO}}(P,P^{DM},x_i) L SO ( P , P D M ; D ) = ∑ ( x i , w i ) ∈ D L SO ( P , P D M , x i ) w i ∈ W ∗ ( P x i ) w_i\in W^*(Px_i) w i ∈ W ∗ ( P x i ) [2 ] have shown that minimizing the empirical suboptimality loss admits the convex reformulation in the form of
min P , λ i ∑ i = 1 N ∣ ( P x i ) ⊤ w i − b ⊤ λ i ∣ , s . t . A ⊤ λ i = P x i , λ i ≤ 0 for all i . (2) \begin{aligned}
\min_{P,\lambda_i}\quad&\sum_{i=1}^{N}\left|(Px_i)^\top w_i-b^\top\lambda_i\right|,\\
\mathrm{s.t.}\quad&A^\top\lambda_i=Px_i,\ \lambda_i\le0\ \text{for all }i. \tag*{(2)}
\end{aligned} P , λ i min s.t. i = 1 ∑ N ( P x i ) ⊤ w i − b ⊤ λ i , A ⊤ λ i = P x i , λ i ≤ 0 for all i . (2) The above homogeneous formulation admits P = 0 P=0 P = 0 ∑ i = 1 n ∑ j = 1 d P i j ≥ 1 \sum_{i=1}^{n}\sum_{j=1}^{d}P_{ij}\ge1 ∑ i = 1 n ∑ j = 1 d P ij ≥ 1 ∑ i = 1 n ∑ j = 1 d P i j ≤ − 1 \sum_{i=1}^{n}\sum_{j=1}^{d}P_{ij}\le-1 ∑ i = 1 n ∑ j = 1 d P ij ≤ − 1
Sampling. Decision consistency on a finite dataset does not necessarily imply small prediction loss, even under loss calibration, since many cost vectors can induce the same downstream optimizer. The sampling step therefore focuses on contexts where this ambiguity is easiest to expose.
Our key idea is to query boundary and near-boundary contexts. Using the directions r i r_i r i § 3.1 , an ϵ \epsilon ϵ P a x ≠ 0 P^a x\ne0 P a x = 0 ∠ ( P a x , r i ) < ϵ \angle(P^a x,r_i)<\epsilon ∠ ( P a x , r i ) < ϵ i i i Figure 1 ). Formally, we define I ( P a , P D M ) = { x : L S O ( P a , P D M , x ) > 0 } I(P^a,P^{DM})=\{x:L_{\mathrm{SO}}(P^a,P^{DM},x)>0\} I ( P a , P D M ) = { x : L SO ( P a , P D M , x ) > 0 }
Figure 1. Illustration of prediction misalignment. Arrows show negative cost vectors. The two models return different decisions in (a) and the same decision in (b).
Proposition 3.8. Suppose that Assumption 3.4 holds, the rank of P a P^a P a n n n L p r e d ( P a , P D M , x ) > 0 L_{\mathrm{pred}}(P^a,P^{DM},x)>0 L pred ( P a , P D M , x ) > 0 x x x ϵ > 0 \epsilon>0 ϵ > 0 ϵ \epsilon ϵ x ~ ∈ I ( P a , P D M ) \tilde{x}\in I(P^a,P^{DM}) x ~ ∈ I ( P a , P D M )
Proposition 3.8 shows that, whenever the attacker model P a P^a P a P D M P^{DM} P D M P a P^a P a r i r_i r i M M M M M M
We now state the convergence guarantee for Algorithm 1 with boundary sampling.
Theorem 3.9 (Informal). Suppose Assumption 3.4 holds. Run Algorithm 1 with a full-rank initialization and boundary sampling as specified in Appendix A.3. Assume that each inverse optimization update returns a full-rank matrix with zero inverse feasibility loss on the accumulated dataset, and that the samples
Table 2.
satisfy the uniform boundedness and conditioning requirements of Theorem A.3 across all runs. Choose M = M ( Δ ) M=M(\Delta) M = M ( Δ ) M ( Δ ) → + ∞ M(\Delta)\to+\infty M ( Δ ) → + ∞ Δ ↓ 0 \Delta\downarrow0 Δ ↓ 0 ( M , Δ ) (M,\Delta) ( M , Δ ) L p r e d ( P D M ( Δ ) , Δ , P D M , x ) → 0 L_{\mathrm{pred}}(P^{DM(\Delta),\Delta},P^{DM},x)\to0 L pred ( P D M ( Δ ) , Δ , P D M , x ) → 0 x ∉ ker ( P D M ) x\notin\operatorname{ker}(P^{DM}) x ∈ / ker ( P D M )
Theorem 3.9 establishes asymptotic prediction recovery under uniform sampling regularity. This regularity prevents the boundary representatives from becoming asymptotically uninformative. The stopping condition couples M M M Δ \Delta Δ
Preventing Model Extraction
We introduce a prediction perturbation baseline that adds Gaussian noise to the predicted cost before optimization (see Algorithm 2). This scheme perturbs costs without using their distance to a decision boundary. Independent resampling allows an attacker to estimate the response distribution by repeating a query.
We then propose a decision perturbation defense. Since near-boundary queries can expose prediction misalignment, we modify responses in these regions by selecting neighboring decisions whose normal cones are close to the predicted cost. Algorithm 3 first computes the true optimizer and then checks whether the predicted cost P D M x P^{DM}x P D M x ϵ \epsilon ϵ W = { w 0 } \mathcal{W}=\{w_0\} W = { w 0 } W \mathcal{W} W w 0 w_0 w 0 W \mathcal{W} W
The parameter ϵ > 0 \epsilon>0 ϵ > 0 ϵ \epsilon ϵ
Table 3.
Proposition 4.1. Define the regret at context x x x Regret ( w ; x ) = ( P D M x ) T ( w − w ∗ ( P D M x ) ) \operatorname{Regret}(w;x)=(P^{DM}x)^{\mathsf{T}}(w-w^*(P^{DM}x)) Regret ( w ; x ) = ( P D M x ) T ( w − w ∗ ( P D M x )) Q Q Q E x ∼ Q [ ∥ P D M x ∥ ] < + ∞ \mathbb{E}_{x\sim Q}[\lVert P^{DM}x\rVert]<+\infty E x ∼ Q [∥ P D M x ∥] < + ∞
E x ∼ Q [ Regret ( w ~ ( x ) ; x ) ] ≤ L ϵ E x ∼ Q [ ∥ P D M x ∥ ] , \mathbb{E}_{x\sim Q}[\operatorname{Regret}(\widetilde{w}(x);x)]\leq L_{\epsilon}\mathbb{E}_{x\sim Q}[\lVert P^{DM}x\rVert], E x ∼ Q [ Regret ( w ( x ) ; x )] ≤ L ϵ E x ∼ Q [∥ P D M x ∥] , where L ϵ = max u , v ∈ V ∥ u − v ∥ L_{\epsilon}=\max_{u,v\in V}\lVert u-v\rVert L ϵ = max u , v ∈ V ∥ u − v ∥
Proposition 4.1 provides a regret upper bound that is linear in ϵ > 0 \epsilon>0 ϵ > 0
We quantify the prediction error incurred by attackers that fit the defended responses. For a context x x x c = P D M x c=P^{DM}x c = P D M x w 0 = w ∗ ( c ) w_0=w^*(c) w 0 = w ∗ ( c ) c ≠ 0 c\neq0 c = 0 ϵ > 0 \epsilon>0 ϵ > 0
W ϵ ( x ) = { w 0 } ∪ { w ∈ N V ( w 0 ) : ∠ ( c , cone ( w ) ) ≤ ϵ } . \mathcal{W}_{\epsilon}(x)=\{w_0\}\cup\{w\in N_V(w_0):\angle(c,\operatorname{cone}(w))\leq\epsilon\}. W ϵ ( x ) = { w 0 } ∪ { w ∈ N V ( w 0 ) : ∠ ( c , cone ( w )) ≤ ϵ } . In this case, W ϵ ( x ) \mathcal{W}_{\epsilon}(x) W ϵ ( x ) c = 0 c=0 c = 0 ϵ = 0 \epsilon=0 ϵ = 0 W ϵ ( x ) = { w 0 } \mathcal{W}_{\epsilon}(x)=\{w_0\} W ϵ ( x ) = { w 0 } E \mathcal{E} E w ∗ ( c ) w^*(c) w ∗ ( c )
Theorem 4.2. For a context x x x P a x ≠ 0 P^a x\neq0 P a x = 0 P D M x ≠ 0 P^{DM}x\neq0 P D M x = 0 ϕ ( x ) \phi(x) ϕ ( x ) ψ ( x ) \psi(x) ψ ( x ) cone ( w ∗ ( P a x ) ) \operatorname{cone}(w^*(P^a x)) cone ( w ∗ ( P a x )) cone ( w ∗ ( P D M x ) ) \operatorname{cone}(w^*(P^{DM}x)) cone ( w ∗ ( P D M x )) w ~ ( x ) ∈ W ∗ ( P a x ) \widetilde{w}(x)\in W^*(P^a x) w ( x ) ∈ W ∗ ( P a x ) P D M x ∈ E P^{DM}x\in\mathcal{E} P D M x ∈ E
L p r e d ( P a , P D M , x ) ≥ ψ ( x ) + ϕ ( x ) . L_{\mathrm{pred}}(P^a,P^{DM},x)\geq\psi(x)+\phi(x). L pred ( P a , P D M , x ) ≥ ψ ( x ) + ϕ ( x ) . In particular, the loss is at least ϵ \epsilon ϵ ϕ ( x ) ≥ ϵ \phi(x)\geq\epsilon ϕ ( x ) ≥ ϵ
( P a x ) T ( w ~ ( x ) − w ∗ ( P a x ) ) ≪ ∥ P a x ∥ ℓ ϵ sin ( ϕ ( x ) ) , ( 3 ) (3) (P^a x)^{\mathsf{T}}(\widetilde{w}(x)-w^*(P^a x))\ll\lVert P^a x\rVert\ell_{\epsilon}\sin(\phi(x)), \qquad(3) \tag*{(3)} ( P a x ) T ( w ( x ) − w ∗ ( P a x )) ≪ ∥ P a x ∥ ℓ ϵ sin ( ϕ ( x )) , ( 3 ) (3) where ℓ ϵ = min u ≠ v ∈ V ∥ u − v ∥ \ell_{\epsilon}=\min_{u\neq v\in V}\lVert u-v\rVert ℓ ϵ = min u = v ∈ V ∥ u − v ∥ Q Q Q
nonzero and w ~ ( x ) ∈ W ⋆ ( P x a ) \widetilde{w}(x) \in W^\star(P^{a}_x) w ( x ) ∈ W ⋆ ( P x a ) Q Q Q x x x
E [ L p r e d ( P a , P D M , x ) ] ≥ B ϵ ( Q ) , \mathbb{E}[\mathrm{L}_{\mathrm{pred}}(P^{a},P^{\mathrm{DM}},x)] \ge B_{\epsilon}(Q), E [ L pred ( P a , P DM , x )] ≥ B ϵ ( Q ) , where B ϵ ( Q ) = E x ∼ Q [ ψ ( x ) ( 1 − 1 ∣ W ϵ ( x ) ∣ ) ] B_{\epsilon}(Q) = \mathbb{E}_{x\sim Q}[\psi(x)(1-\frac{1}{|W_{\epsilon}(x)|})] B ϵ ( Q ) = E x ∼ Q [ ψ ( x ) ( 1 − ∣ W ϵ ( x ) ∣ 1 )] x ∼ Q x \sim Q x ∼ Q P D M P^{\mathrm{DM}} P DM Q Q Q B ϵ ( Q ) B_{\epsilon}(Q) B ϵ ( Q ) ϵ \epsilon ϵ
Theorem 4.2 formalizes the defense effect for response-fitting attackers: viewing a perturbed decision as optimal can lead to moving away from the true cost direction. Under the population fitting condition, it provides an expected prediction-error lower bound that is nondecreasing in ϵ \epsilon ϵ ϵ \epsilon ϵ
Experiments
We evaluate the proposed attack and defense methods on synthetic instances and a short-video recommendation task. We compare adaptive sampling attacks with inverse optimization baselines and examine the security-regret trade-off induced by the defensive algorithm. We report the angular prediction loss in Definition 2.1 and the decision-maker’s regret in Proposition 4.1.
Synthetic instances. We compare three attacks: boundary sampling (BndS), uniform sampling (Unif), and an inverse optimization baseline method that uses a single nonadaptive fit (INV). Here, the feasible set is S = { w ∈ [ 0 , 1 ] n : a ⊤ w ≤ b } S = \{w \in[0,1]^n : a^\top w \le b\} S = { w ∈ [ 0 , 1 ] n : a ⊤ w ≤ b } a j = 1 + 0.5 ( j − 1 ) a_j = 1 + 0.5(j-1) a j = 1 + 0.5 ( j − 1 ) j = 1 , … , n j = 1,\ldots,n j = 1 , … , n b = 0.6 ∑ j = 1 n a j b = 0.6\sum_{j=1}^{n}a_j b = 0.6 ∑ j = 1 n a j (2) , and the INV comparisons use matched sample sizes. Figure 2 reports prediction loss after three adaptive iterations for BndS and Unif, together with the INV comparison, and the sample sizes required to attain prediction loss below 0.001 as the decision dimension n n n d d d d = 15 d = 15 d = 15 d = 20 d = 20 d = 20
Figure 2. Attack performance on synthetic data as the decision dimension n n n d d d
Figure 3 compares prediction loss under query budgets up to 3000 for BndS, Unif, and a mixture of the two sampling methods (MIX). MIX uses equal numbers of boundary and uniform samples. For ϵ = 0 \epsilon= 0 ϵ = 0 ϵ = 0.0015 \epsilon= 0.0015 ϵ = 0.0015
Figure 3. Prediction loss under increasing query budgets for BndS (M = 20 M = 20 M = 20 ϵ = 0 \epsilon= 0 ϵ = 0 ϵ = 0.0015 \epsilon= 0.0015 ϵ = 0.0015 d = 10 d = 10 d = 10 n = 5 n = 5 n = 5
Figure 4 reports attack-specific prediction loss–regret trade-offs. In particular, Figure 4a compares attacks under decision perturbation: the attacker who aims to get more boundary information (BndS(M=50)) suffers from larger prediction under defense. Figure 4b shows decision perturbation increases the attacker’s prediction loss at modest regret and is more effective than prediction perturbation. These comparisons concern the reported attacks and parameter settings.
Short video recommendation
We examine the performance of our framework on a real dataset. We consider a short video recommendation problem constructed from the public dataset KuaiRand-1K ([13 ] ). We use 800 users for training and 200 for testing, with d = 18 d = 18 d = 18 n = 5 n = 5 n = 5 w ∈ [ 0 , 1 ] 5 w \in[0,1]^5 w ∈ [ 0 , 1 ] 5 ∑ i = 1 5 w i ≤ 3 \sum_{i=1}^{5} w_i \le3 ∑ i = 1 5 w i ≤ 3 § 7 .§ 5 ). The cost vector in Eq. (1) is the negative of the predicted click-through-rate vector in this example.
Figure 4c shows that BndS has lower prediction loss than INV at the lowest plotted regret levels. At larger regret levels, both attacks incur greater prediction loss, with a more pronounced increase for BndS. This is compatible with the mechanism in Theorem 4.2: making boundary query causes perturbed responses, and fitting perturbed responses as optimal decisions can cause higher prediction loss.
Conclusion
This paper studies model extraction and defense in contextual linear optimization under the Pto paradigm. We characterize vulnerability through loss calibration, develop an adaptive inverse optimization attack with boundary sampling, and propose a near-boundary decision-perturbation defense. Our theory bounds the regret of the defense and provides a lower bound on expected prediction error for attackers that fit the defended responses as optimal decisions under the evaluation distribution. This lower bound is nondecreasing in the perturbation degree. Experiments show that the defense can increase prediction error for the evaluated attacks within the tested query budgets. Future work includes analyzing attackers that explicitly model the defense and extending the analysis to nonlinear contextual optimization.
Figure 4. Empirical prediction loss-regret trade-offs: (a) decision perturbation against different attacks on synthetic instances; (b) prediction versus decision perturbation on synthetic instances; and (c) decision perturbation on the short-video recommendation task. Points show median regret and median prediction loss, and shaded bands show the 25th–75th percentiles of prediction loss over 100 repetitions per parameter setting.
ADDITIONAL TECHNICAL MATERIAL
Condition of loss calibration
We present the condition of loss calibration and provide additional insights into how the decision-maker can assess vulnerability. For a full-rank attacker matrix P a P^a P a w ⋆ ( P D M x ) ∈ W ⋆ ( P a x ) w^\star(P^{DM}x) \in W^\star(P^a x) w ⋆ ( P D M x ) ∈ W ⋆ ( P a x ) x ∉ ker ( P D M ) x \notin\operatorname{ker}(P^{DM}) x ∈ / ker ( P D M ) P a x ˉ P^a\bar{x} P a x ˉ P D M x ˉ P^{DM}\bar{x} P D M x ˉ x ˉ \bar{x} x ˉ P a P^a P a
r i = − a i ∥ a i ∥ . r_i=-\frac{a_i}{\lVert a_i\rVert}. r i = − ∥ a i ∥ a i . For a full-rank attacker matrix P a P^a P a
P c ( P a ) = { P ∈ R n × d : P x ˉ ∈ span ( r i ) for every i = 1 , 2 , … , m and every x ˉ ∈ R d satisfying P a x ˉ = r i } . \mathcal{P}_c(P^a)=\left\{P\in\mathbb{R}^{n\times d}:P\bar{x}\in\operatorname{span}(r_i)\text{ for every }i=1,2,\ldots,m\text{ and every }\bar{x}\in\mathbb{R}^d\text{ satisfying }P^a\bar{x}=r_i\right\}. P c ( P a ) = { P ∈ R n × d : P x ˉ ∈ span ( r i ) for every i = 1 , 2 , … , m and every x ˉ ∈ R d satisfying P a x ˉ = r i } . The candidate space is a linear subspace that contains P a P^a P a
If P a P^a P a P D M ∈ P c ( P a ) P^{DM}\in\mathcal{P}_c(P^a) P D M ∈ P c ( P a ) P D M = γ P a P^{DM}=\gamma P^a P D M = γ P a γ \gamma γ P D M ≠ 0 P^{DM}\ne0 P D M = 0 γ > 0 \gamma>0 γ > 0 P c ( P a ) \mathcal{P}_c(P^a) P c ( P a )
Proposition A.1. Suppose that Assumption 3.4 holds. Then, for every full-rank matrix P a ∈ R n × d P^a\in\mathbb{R}^{n\times d} P a ∈ R n × d P c ( P a ) = span { P a } \mathcal{P}_c(P^a)=\operatorname{span}\{P^a\} P c ( P a ) = span { P a } P c ( P a ) \mathcal{P}_c(P^a) P c ( P a )
Proposition A.1 ensures that P c ( P D M ) \mathcal{P}_c(P^{DM}) P c ( P D M )
Corollary A.2. If P c ( P D M ) \mathcal{P}_c(P^{DM}) P c ( P D M )
Corollary A.2 provides a diagnostic for the decision-maker. For each facet i i i d − n + 1 d-n+1 d − n + 1 { x ˉ i , j } j = 1 d − n + 1 \{\bar{x}_{i,j}\}_{j=1}^{d-n+1} { x ˉ i , j } j = 1 d − n + 1 P D M x ˉ i , j = r i P^{DM}\bar{x}_{i,j}=r_i P D M x ˉ i , j = r i j = 1 , 2 , … , d − n + 1 j=1,2,\ldots,d-n+1 j = 1 , 2 , … , d − n + 1 X i = [ x ˉ i , 1 , … , x ˉ i , d − n + 1 ] X_i=[\bar{x}_{i,1},\ldots,\bar{x}_{i,d-n+1}] X i = [ x ˉ i , 1 , … , x ˉ i , d − n + 1 ] P D M P^{DM} P D M H i = { x ∈ R d : P D M x ∈ span ( r i ) } H_i=\{x\in\mathbb{R}^d:P^{DM}x\in\operatorname{span}(r_i)\} H i = { x ∈ R d : P D M x ∈ span ( r i )} d − n + 1 d-n+1 d − n + 1 X i X_i X i H i H_i H i y i y_i y i P D M y i = r i P^{DM}y_i=r_i P D M y i = r i z 1 , … , z d − n z_1,\ldots,z_{d-n} z 1 , … , z d − n ker ( P D M ) \operatorname{ker}(P^{DM}) ker ( P D M ) y i , y i + z 1 , … , y i + z d − n y_i,y_i+z_1,\ldots,y_i+z_{d-n} y i , y i + z 1 , … , y i + z d − n
Since r i r_i r i P x ˉ i , j ∈ span ( r i ) P\bar{x}_{i,j}\in\operatorname{span}(r_i) P x ˉ i , j ∈ span ( r i ) ( I n − r i r i T ) P x ˉ i , j = 0 (I_n-r_ir_i^{\mathsf{T}})P\bar{x}_{i,j}=0 ( I n − r i r i T ) P x ˉ i , j = 0
P c ( P D M ) = { P ∈ R n × d : ( I n − r i r i T ) P X i = 0 for every i = 1 , 2 , … , m } . \mathcal{P}_c(P^{DM})=\left\{P\in\mathbb{R}^{n\times d}:(I_n-r_ir_i^{\mathsf{T}})PX_i=0\text{ for every }i=1,2,\ldots,m\right\}. P c ( P D M ) = { P ∈ R n × d : ( I n − r i r i T ) P X i = 0 for every i = 1 , 2 , … , m } . Thus, the decision-maker can determine the dimension of the candidate space by solving a linear system in the entries of P P P P D M P^{DM} P D M
Inverse optimization methods
We present other loss functions motivated by inverse optimization and the approaches to solve them. Any inverse feasibility loss function can be incorporated into our framework, although the resulting empirical optimization problems are different and may require different solution methods.
Scale normalization of the suboptimality loss function. The suboptimality-loss formulation in Eq. (2) is homogeneous and admits P = 0 P=0 P = 0
∑ i = 1 n ∑ j = 1 d P i j ≥ 1 or ∑ i = 1 n ∑ j = 1 d P i j ≤ − 1. \sum_{i=1}^{n}\sum_{j=1}^{d}P_{ij}\ge1 \quad\text{or}\quad\sum_{i=1}^{n}\sum_{j=1}^{d}P_{ij}\le-1. i = 1 ∑ n j = 1 ∑ d P ij ≥ 1 or i = 1 ∑ n j = 1 ∑ d P ij ≤ − 1. Each constraint excludes the zero matrix. Every matrix with a nonzero entry sum has a positive rescaling satisfying one of these constraints, so zero-loss feasibility is preserved for such matrices. Matrices with zero entry sum are excluded. Since positive rescaling changes the value of the suboptimality loss, the fitted matrix is normalized in Frobenius norm before applying the stopping test in Algorithm 1.
Distance loss function. The distance loss measures the distance from an observed decision to the optimal solution set under P P P
L d ( P , P D M ; x i ) = min w ∈ W ⋆ ( P x i ) ∥ w − w i ∥ . (4) L_d(P,P^{DM};x_i)=\min_{w\in W^{\star}(Px_i)}\lVert w-w_i\rVert. \tag*{(4)} L d ( P , P D M ; x i ) = w ∈ W ⋆ ( P x i ) min ∥ w − w i ∥ . (4) We define the empirical distance loss by
L ^ d ( P , P D M ; D ) = ∑ i = 1 N L d ( P , P D M ; x i ) . \widehat{L}_d(P,P^{DM};D)=\sum_{i=1}^{N}L_d(P,P^{DM};x_i). L d ( P , P D M ; D ) = i = 1 ∑ N L d ( P , P D M ; x i ) . Recall that the set W ⋆ ( P x i ) W^{\star}(Px_i) W ⋆ ( P x i ) (4) is attained and we have L d ( P , P D M ; x i ) = 0 L_d(P,P^{DM};x_i)=0 L d ( P , P D M ; x i ) = 0 w i ∈ W ⋆ ( P x i ) w_i\in W^{\star}(Px_i) w i ∈ W ⋆ ( P x i ) P i n v ( D ) \mathcal{P}_{\mathrm{inv}}(D) P inv ( D ) W ⋆ ( 0 ) = S W^{\star}(0)=S W ⋆ ( 0 ) = S P x i = 0 Px_i=0 P x i = 0
The distance loss is not continuous in general. Following the duality-based approach of Aswani et al. [1 ] , we consider an optimality-gap relaxation for the fixed feasible set S S S ϵ ≥ 0 \epsilon\ge0 ϵ ≥ 0
L ^ d ( P , P D M ; D , ϵ ) = min { w ~ i , λ i } i = 1 N ∑ i = 1 N ∥ w i − w ~ i ∥ , s.t. A T λ i = P x i , i = 1 , … , N , ( P x i ) T w ~ i − b T λ i ≤ ϵ , i = 1 , … , N , A w ~ i ≤ b , i = 1 , … , N , λ i ≤ 0 , i = 1 , … , N . \begin{aligned}
\widehat{L}_d(P,P^{DM};D,\epsilon)
&=\min_{\{\widetilde{w}_i,\lambda_i\}_{i=1}^{N}}\sum_{i=1}^{N}\lVert w_i-\widetilde{w}_i\rVert,\\
\text{s.t.}\quad&A^{\mathsf{T}}\lambda_i=Px_i,\quad i=1,\ldots,N,\\
&(Px_i)^{\mathsf{T}}\widetilde{w}_i-b^{\mathsf{T}}\lambda_i\le\epsilon,\quad i=1,\ldots,N,\\
&A\widetilde{w}_i\le b,\quad i=1,\ldots,N,\\
&\lambda_i\le0,\quad i=1,\ldots,N.
\end{aligned} L d ( P , P D M ; D , ϵ ) s.t. = { w i , λ i } i = 1 N min i = 1 ∑ N ∥ w i − w i ∥ , A T λ i = P x i , i = 1 , … , N , ( P x i ) T w i − b T λ i ≤ ϵ , i = 1 , … , N , A w i ≤ b , i = 1 , … , N , λ i ≤ 0 , i = 1 , … , N . Strong linear programming duality makes these constraints equivalent to ( P x i ) T w ~ i − z ⋆ ( P x i ) ≤ ϵ (Px_i)^{\mathsf{T}}\widetilde{w}_i-z^{\star}(Px_i)\le\epsilon ( P x i ) T w i − z ⋆ ( P x i ) ≤ ϵ w ~ i ∈ S \widetilde{w}_i\in S w i ∈ S i = 1 , 2 , … , N i=1,2,\ldots,N i = 1 , 2 , … , N L ^ d ( P , P D M ; D , 0 ) = L ^ d ( P , P D M ; D ) \widehat{L}_d(P,P^{DM};D,0)=\widehat{L}_d(P,P^{DM};D) L d ( P , P D M ; D , 0 ) = L d ( P , P D M ; D ) ϵ > 0 \epsilon>0 ϵ > 0 P P P P P P
L ^ d ( P , P D M ; D , ϵ ) ↑ L ^ d ( P , P D M ; D ) as ϵ ↓ 0. \widehat{L}_d(P,P^{DM};D,\epsilon)\mathrel{\uparrow}\widehat{L}_d(P,P^{DM};D)\text{ as }\epsilon\downarrow0. L d ( P , P D M ; D , ϵ ) ↑ L d ( P , P D M ; D ) as ϵ ↓ 0. When minimization is over a fixed nonempty compact set of nonzero matrices, every accumulation point of global minimizers of the relaxed loss as ϵ ↓ 0 \epsilon\downarrow0 ϵ ↓ 0
CaVE loss function. Following the approach of Tang and Khalil [35 ] , we define the cone-aligned vector estimation (CaVE) loss function as follows,
L C ( P a , P D M ; x i ) = { 1 − cos ( ∠ ( P a x i , cone ( w i ) ) ) , if P a x i ≠ 0 , 0 , otherwise. (5) L_C(P^a,P^{DM};x_i)=
\begin{cases}
1-\cos\left(\angle(P^a x_i,\operatorname{cone}(w_i))\right), & \text{if }P^a x_i\ne0,\\
0, & \text{otherwise.}
\end{cases} \tag*{(5)} L C ( P a , P D M ; x i ) = { 1 − cos ( ∠ ( P a x i , cone ( w i )) ) , 0 , if P a x i = 0 , otherwise. (5) Its empirical value is
L C ( P a , P D M ; D ) = 1 N ∑ i = 1 N L C ( P a , P D M ; x i ) . L_C(P^a,P^{DM};D)=\frac{1}{N}\sum_{i=1}^{N}L_C(P^a,P^{DM};x_i). L C ( P a , P D M ; D ) = N 1 i = 1 ∑ N L C ( P a , P D M ; x i ) . For nonzero costs, zero angular distance to the closed normal cone is equivalent to being in that cone. At zero cost, every feasible decision is optimal. For every nonzero matrix P a P^a P a
L C ( P a , P D M ; D ) = 0 ⟺ w i ∈ W ⋆ ( P a x i ) for all i = 1 , … , N . L_C(P^a,P^{DM};D)=0\Longleftrightarrow w_i\in W^{\star}(P^a x_i)\text{ for all }i=1,\ldots,N. L C ( P a , P D M ; D ) = 0 ⟺ w i ∈ W ⋆ ( P a x i ) for all i = 1 , … , N . Figure 4 (PDF p. 13). Algorithm 4 Learning the prediction matrix via ADMM
Thus, L C L_C L C
For each observed vertex w i w_i w i I i = { j : a j ⊤ w i = b j } I_i = \{j : a_j^\top w_i = b_j\} I i = { j : a j ⊤ w i = b j } A I i A_{I_i} A I i A A A cone ( w i ) = { − A I i ⊤ λ i : λ i ≥ 0 } \operatorname{cone}(w_i) = \{-A_{I_i}^\top\lambda_i : \lambda_i \ge0\} cone ( w i ) = { − A I i ⊤ λ i : λ i ≥ 0 } λ i ≥ 0 \lambda_i \ge0 λ i ≥ 0 − a j -a_j − a j j ∈ I i j \in I_i j ∈ I i P a x i ≠ 0 P^a x_i \ne0 P a x i = 0
L C ( P a , P D M ; x i ) = min λ i ≥ 0 ∥ A I i ⊤ λ i ∥ = 1 ( 1 + ( A I i ⊤ λ i ) ⊤ P a x i ∥ P a x i ∥ ) . L_C(P^a, P^{DM}; x_i) = \min_{\substack{\lambda_i \ge0 \\ \lVert A_{I_i}^\top\lambda_i\rVert= 1}} \left(1 + \frac{(A_{I_i}^\top\lambda_i)^\top P^a x_i}{\lVert P^a x_i\rVert}\right). L C ( P a , P D M ; x i ) = λ i ≥ 0 ∥ A I i ⊤ λ i ∥ = 1 min ( 1 + ∥ P a x i ∥ ( A I i ⊤ λ i ) ⊤ P a x i ) . With a numerical bound C ≥ 1 n d C \ge\frac{1}{nd} C ≥ n d 1
min P a , λ 1 , … , λ N 1 N ∑ i = 1 N ( 1 + ( A I i ⊤ λ i ) ⊤ P a x i ∥ P a x i ∥ ) s.t. λ i ≥ 0 , ∥ A I i ⊤ λ i ∥ = 1 , i = 1 , … , N , ∑ i = 1 n ∑ j = 1 d P i j a = 1 , ∣ P i j a ∣ ≤ C , i = 1 , … , n , j = 1 , … , d . (6) \begin{aligned}
\min_{P^a,\lambda_1,\ldots,\lambda_N}\quad&\frac{1}{N}\sum_{i=1}^{N}\left(1+\frac{(A_{I_i}^\top\lambda_i)^\top P^a x_i}{\lVert P^a x_i\rVert}\right)\\
\text{s.t.}\quad&\lambda_i\ge0,\ \lVert A_{I_i}^\top\lambda_i\rVert=1,\ i=1,\ldots,N,\\
&\sum_{i=1}^{n}\sum_{j=1}^{d}P^a_{ij}=1,\\
&\lvert P^a_{ij}\rvert\le C,\ i=1,\ldots,n,\ j=1,\ldots,d. \tag*{(6)}
\end{aligned} P a , λ 1 , … , λ N min s.t. N 1 i = 1 ∑ N ( 1 + ∥ P a x i ∥ ( A I i ⊤ λ i ) ⊤ P a x i ) λ i ≥ 0 , ∥ A I i ⊤ λ i ∥ = 1 , i = 1 , … , N , i = 1 ∑ n j = 1 ∑ d P ij a = 1 , ∣ P ij a ∣ ≤ C , i = 1 , … , n , j = 1 , … , d . (6) In this formulation and the expressions below, the entire angular summand is defined to be zero when its predicted cost is zero, as in Eq. (5) . The matrix constraints restrict the admissible predictors.
Introducing a local matrix P i P_i P i
min P a , { P i , λ i } i = 1 N 1 N ∑ i = 1 N ( 1 + ( A I i ⊤ λ i ) ⊤ P i x i ∥ P i x i ∥ ) s.t. λ i ≥ 0 , ∥ A I i ⊤ λ i ∥ = 1 , i = 1 , … , N , P i = P a , i = 1 , … , N , ∑ i = 1 n ∑ j = 1 d P i j a = 1 , ∣ P i j a ∣ ≤ C , i = 1 , … , n , j = 1 , … , d . (7) \begin{aligned}
\min_{P^a,\{P_i,\lambda_i\}_{i=1}^{N}}\quad&\frac{1}{N}\sum_{i=1}^{N}\left(1+\frac{(A_{I_i}^\top\lambda_i)^\top P_i x_i}{\lVert P_i x_i\rVert}\right)\\
\text{s.t.}\quad&\lambda_i\ge0,\ \lVert A_{I_i}^\top\lambda_i\rVert=1,\ i=1,\ldots,N,\\
&P_i=P^a,\ i=1,\ldots,N,\\
&\sum_{i=1}^{n}\sum_{j=1}^{d}P^a_{ij}=1,\\
&\lvert P^a_{ij}\rvert\le C,\ i=1,\ldots,n,\ j=1,\ldots,d. \tag*{(7)}
\end{aligned} P a , { P i , λ i } i = 1 N min s.t. N 1 i = 1 ∑ N ( 1 + ∥ P i x i ∥ ( A I i ⊤ λ i ) ⊤ P i x i ) λ i ≥ 0 , ∥ A I i ⊤ λ i ∥ = 1 , i = 1 , … , N , P i = P a , i = 1 , … , N , i = 1 ∑ n j = 1 ∑ d P ij a = 1 , ∣ P ij a ∣ ≤ C , i = 1 , … , n , j = 1 , … , d . (7) For ρ > 0 \rho> 0 ρ > 0
L ρ ( { P i } , { λ i } , P a , { μ i } ) = ∑ i = 1 N [ 1 N ( 1 + ( A I i ⊤ λ i ) ⊤ P i x i ∥ P i x i ∥ ) + ⟨ μ i , P i − P a ⟩ F + ρ 2 ∥ P i − P a ∥ F 2 ] . L_\rho(\{P_i\},\{\lambda_i\},P^a,\{\mu_i\})=\sum_{i=1}^{N}\left[\frac{1}{N}\left(1+\frac{(A_{I_i}^\top\lambda_i)^\top P_i x_i}{\lVert P_i x_i\rVert}\right)+\langle\mu_i,P_i-P^a\rangle_F+\frac{\rho}{2}\lVert P_i-P^a\rVert_F^2\right]. L ρ ({ P i } , { λ i } , P a , { μ i }) = i = 1 ∑ N [ N 1 ( 1 + ∥ P i x i ∥ ( A I i ⊤ λ i ) ⊤ P i x i ) + ⟨ μ i , P i − P a ⟩ F + 2 ρ ∥ P i − P a ∥ F 2 ] . where μ i ∈ R n × d \mu_i \in\mathbb{R}^{n\times d} μ i ∈ R n × d P i = P a P_i=P^a P i = P a P a P^a P a λ i \lambda_i λ i P i P_i P i L ρ ( P i , λ i , P a , μ i ) L_\rho(P_i,\lambda_i,P^a,\mu_i) L ρ ( P i , λ i , P a , μ i ) i i i Λ i = { λ i ∈ R ∣ I i ∣ : λ i ≥ 0 , ∥ A I i ⊤ λ i ∥ = 1 } \Lambda_i=\{\lambda_i\in\mathbb{R}^{|I_i|}:\lambda_i\ge0,\ \lVert A_{I_i}^\top\lambda_i\rVert=1\} Λ i = { λ i ∈ R ∣ I i ∣ : λ i ≥ 0 , ∥ A I i ⊤ λ i ∥ = 1 }
The local minimizations can be approximated by first-order updates. For P i t x i ≠ 0 P_i^t x_i\ne0 P i t x i = 0 λ i \lambda_i λ i P i P_i P i
λ i t + 1 ∈ Π Λ i ( λ i t − α A I i P i t x i ∥ P i t x i ∥ ) , \lambda_i^{t+1}\in\Pi_{\Lambda_i}\left(\lambda_i^t-\alpha\frac{A_{I_i}P_i^t x_i}{\lVert P_i^t x_i\rVert}\right), λ i t + 1 ∈ Π Λ i ( λ i t − α ∥ P i t x i ∥ A I i P i t x i ) , P i t + 1 = P i t − β ( 1 N ( A I i ⊤ λ i t + 1 ∥ P i t x i ∥ − ( A I i ⊤ λ i t + 1 ) ⊤ P i t x i ∥ P i t x i ∥ 3 P i t x i ) x i ⊤ + μ i t + ρ ( P i t − P a , t + 1 ) ) . (8) P_i^{t+1}=P_i^t-\beta\left(\frac{1}{N}\left(\frac{A_{I_i}^\top\lambda_i^{t+1}}{\lVert P_i^t x_i\rVert}-\frac{(A_{I_i}^\top\lambda_i^{t+1})^\top P_i^t x_i}{\lVert P_i^t x_i\rVert^3}P_i^t x_i\right)x_i^\top+\mu_i^t+\rho(P_i^t-P^{a,t+1})\right). \tag*{(8)} P i t + 1 = P i t − β ( N 1 ( ∥ P i t x i ∥ A I i ⊤ λ i t + 1 − ∥ P i t x i ∥ 3 ( A I i ⊤ λ i t + 1 ) ⊤ P i t x i P i t x i ) x i ⊤ + μ i t + ρ ( P i t − P a , t + 1 ) ) . (8) Table 1 (PDF p. 14). Comparison of three approaches for minimizing the CaVE loss.
where α , β > 0 \alpha,\beta> 0 α , β > 0 Π Λ i \Pi_{\Lambda_i} Π Λ i Λ i \Lambda_i Λ i
The experiment shows that our solution approach can achieve near-zero optimality gap. Apart from ADMM, we tried the heuristic algorithm [35 ] and the global solver in scipy package to solve the optimization problem. Figure 5 shows the convergence of ADMM and Tang and Khalil’s method. We observe that both methods achieve near zero CaVE loss. Table 1 compares all methods and shows that the global solver attains the smallest reported CaVE loss. Furthermore, if we encounter some context such that ∥ P a x i ∥ = 0 \lVert P^a x_i\rVert= 0 ∥ P a x i ∥ = 0
Figure 5. Convergence of the ADMM algorithm and Tang and Khalil’s method. The red line represents the optimization loss, defined as the proportion of incorrect decisions w ⋆ ( P a x i ) ≠ w ⋆ ( P D M x i ) w^\star(P^a x_i) \ne w^\star(P^{DM}x_i) w ⋆ ( P a x i ) = w ⋆ ( P D M x i )
Sampling algorithms
We specify the sampling step of Algorithm 1. Indeed, for a full-rank matrix P a P^a P a R n \mathbb{R}^n R n P a P^a P a
We enumerate the vertices as V = { w 1 , … , w ∣ V ∣ } V = \{w_1,\ldots,w_{|V|}\} V = { w 1 , … , w ∣ V ∣ } C k = cone ( w k ) C_k = \operatorname{cone}(w_k) C k = cone ( w k ) w k ∈ V w_k \in V w k ∈ V I k = { i ∈ { 1 , … , m } : a i ⊤ w k = b i } I_k = \{i \in\{1,\ldots,m\}: a_i^\top w_k = b_i\} I k = { i ∈ { 1 , … , m } : a i ⊤ w k = b i } i i i C i = { k ∈ { 1 , … , ∣ V ∣ } : i ∈ I k } C_i = \{k \in\{1,\ldots,|V|\}: i \in I_k\} C i = { k ∈ { 1 , … , ∣ V ∣ } : i ∈ I k } K = max 1 ≤ k ≤ ∣ V ∣ ∣ I k ∣ K = \max_{1\le k\le|V|}|I_k| K = max 1 ≤ k ≤ ∣ V ∣ ∣ I k ∣ r i = − a i ∥ a i ∥ r_i = -\frac{a_i}{\lVert a_i\rVert} r i = − ∥ a i ∥ a i
C k = polycone { r i : i ∈ I k } , ⋂ k ∈ C i C k = { α r i : α ≥ 0 } . C_k = \operatorname{polycone}\{r_i: i \in I_k\}, \qquad\bigcap_{k\in C_i} C_k = \{\alpha r_i: \alpha\ge0\}. C k = polycone { r i : i ∈ I k } , k ∈ C i ⋂ C k = { α r i : α ≥ 0 } . Figure 6 illustrates the facet-vertex incidences. For each facet i i i d − n + 1 d-n+1 d − n + 1 P a x ˉ i 0 j = r i P^a\bar{x}_{i0j}=r_i P a x ˉ i 0 j = r i j = 1 , … , d − n + 1 j=1,\ldots,d-n+1 j = 1 , … , d − n + 1 X i = [ x ˉ i 01 , … , x ˉ i 0 , d − n + 1 ] X_i=[\bar{x}_{i01},\ldots,\bar{x}_{i0,d-n+1}] X i = [ x ˉ i 01 , … , x ˉ i 0 , d − n + 1 ] ( d − n + 1 ) (d-n+1) ( d − n + 1 ) { x ∈ R d : P a x ∈ span ( r i ) } \{x\in\mathbb{R}^d:P^a x\in\operatorname{span}(r_i)\} { x ∈ R d : P a x ∈ span ( r i )} M ≥ 1 M\ge1 M ≥ 1 k ∈ C i k\in C_i k ∈ C i j = 1 , … , d − n + 1 j=1,\ldots,d-n+1 j = 1 , … , d − n + 1
Figure 6. (a) the tight constraints (also the boundaries of normal cone) incident to the a normal cone C k C_k C k a i a_i a i
x ~ i k j = M x ˉ i 0 j + ∑ ℓ ∈ I k ∖ { i } x ˉ ℓ 0 j ∥ M r i + ∑ ℓ ∈ I k ∖ { i } r ℓ ∥ . \widetilde{x}_{ikj}=\frac{M\bar{x}_{i0j}+\sum_{\ell\in I_k\setminus\{i\}}\bar{x}_{\ell0j}}{\left\|M r_i+\sum_{\ell\in I_k\setminus\{i\}}r_\ell\right\|}. x ik j = M r i + ∑ ℓ ∈ I k ∖ { i } r ℓ M x ˉ i 0 j + ∑ ℓ ∈ I k ∖ { i } x ˉ ℓ 0 j . The vector in the denominator is a positive combination of all active inward normals at w k w_k w k int ( C k ) \operatorname{int}(C_k) int ( C k )
P a x ~ i k j = M r i + ∑ ℓ ∈ I k ∖ { i } r ℓ ∥ M r i + ∑ ℓ ∈ I k ∖ { i } r ℓ ∥ ∈ int ( C k ) . P^a\widetilde{x}_{ikj}=\frac{M r_i+\sum_{\ell\in I_k\setminus\{i\}}r_\ell}{\left\|M r_i+\sum_{\ell\in I_k\setminus\{i\}}r_\ell\right\|}\in\operatorname{int}(C_k). P a x ik j = M r i + ∑ ℓ ∈ I k ∖ { i } r ℓ M r i + ∑ ℓ ∈ I k ∖ { i } r ℓ ∈ int ( C k ) . Thus, w k w_k w k x ~ i k j \widetilde{x}_{ikj} x ik j P a x ~ i k j → r i P^a\widetilde{x}_{ikj}\to r_i P a x ik j → r i M → + ∞ M\to+\infty M → + ∞
In what follows, we describe the stopping condition mentioned in Theorem 3.9. Indeed, we define
η S = min 1 ≤ k ≤ ∣ V ∣ min v ∈ V ∖ { w k } ∑ ℓ ∈ I k r ℓ T ( v − w k ) . \eta_S=\min_{1\leq k\leq|V|}\min_{v\in V\setminus\{w_k\}}\sum_{\ell\in I_k}r_\ell^{\mathsf T}(v-w_k). η S = 1 ≤ k ≤ ∣ V ∣ min v ∈ V ∖ { w k } min ℓ ∈ I k ∑ r ℓ T ( v − w k ) . Clearly, η S ≥ 0 \eta_S\geq0 η S ≥ 0 v ≠ w k v\ne w_k v = w k w k w_k w k R n \mathbb{R}^n R n η S > 0 \eta_S>0 η S > 0 M ≥ 1 M\geq1 M ≥ 1 k ∈ C i k\in C_i k ∈ C i v ≠ w k v\ne w_k v = w k
( P a x ~ i k j ) T ( v − w k ) = ( M − 1 ) r i T ( v − w k ) + ∑ ℓ ∈ I k r ℓ T ( v − w k ) ∥ M r i + ∑ ℓ ∈ I k ∖ { i } r ℓ ∥ ≥ η S M + K − 1 . \left(P^a\widetilde{x}_{ikj}\right)^{\mathsf T}(v-w_k)=\frac{(M-1)r_i^{\mathsf T}(v-w_k)+\sum_{\ell\in I_k}r_\ell^{\mathsf T}(v-w_k)}{\left\|M r_i+\sum_{\ell\in I_k\setminus\{i\}}r_\ell\right\|}\geq\frac{\eta_S}{M+K-1}. ( P a x ik j ) T ( v − w k ) = M r i + ∑ ℓ ∈ I k ∖ { i } r ℓ ( M − 1 ) r i T ( v − w k ) + ∑ ℓ ∈ I k r ℓ T ( v − w k ) ≥ M + K − 1 η S . We impose the sufficient stopping condition as follows,
Δ ( M + K − 1 ) < η S . (9) \Delta(M+K-1)<\eta_S. \tag*{(9)} Δ ( M + K − 1 ) < η S . (9) If a near-boundary query returns any vertex other than w k w_k w k P a P^a P a Δ \Delta Δ
Theorem A.3. Suppose Assumption 3.4 holds. For each Δ > 0 \Delta>0 Δ > 0 M = M ( Δ ) ≥ 1 M=M(\Delta)\geq1 M = M ( Δ ) ≥ 1 R > 0 R>0 R > 0 κ > 0 \kappa>0 κ > 0 Δ \Delta Δ ∥ x ∥ ≤ R \|x\|\leq R ∥ x ∥ ≤ R σ min ( X i ) ≥ κ \sigma_{\min}(X_i)\geq\kappa σ m i n ( X i ) ≥ κ i = 1 , … , m i=1,\ldots,m i = 1 , … , m σ min ( X i ) \sigma_{\min}(X_i) σ m i n ( X i ) d − n + 1 d-n+1 d − n + 1 X i X_i X i M ( Δ ) → + ∞ M(\Delta)\to+\infty M ( Δ ) → + ∞ Δ ↓ 0 \Delta\downarrow0 Δ ↓ 0 (9) holds for all sufficiently small Δ \Delta Δ ( 1 + 2 R L e Δ ) n d \left(1+\frac{2RL_e}{\Delta}\right)^{nd} ( 1 + Δ 2 R L e ) n d P M ( Δ ) , Δ a → P D M ∥ P D M ∥ F P^a_{M(\Delta),\Delta}\to\frac{P^{DM}}{\|P^{DM}\|_F} P M ( Δ ) , Δ a → ∥ P D M ∥ F P D M L p r e d ( P M ( Δ ) , Δ a , P D M , x ) → 0 L_{\mathrm{pred}}(P^a_{M(\Delta),\Delta},P^{DM},x)\to0 L pred ( P M ( Δ ) , Δ a , P D M , x ) → 0 x ∉ ker ( P D M ) x\notin\ker(P^{DM}) x ∈ / ker ( P D M )
:::`
Algorithm 5 Uniform sampling (Unif)
Input: A full-rank matrix P a P^{a} P a N t N_t N t
Initialize: D ← ∅ D \leftarrow\varnothing D ← ∅
for k = 1 , … , N t k = 1,\ldots,N_t k = 1 , … , N t do
Sample u ∼ N ( 0 , I n ) u \sim\mathcal{N}(0,I_n) u ∼ N ( 0 , I n ) u ← u ∥ u ∥ u \leftarrow\frac{u}{\lVert u\rVert} u ← ∥ u ∥ u
Choose x ∈ R d x \in\mathbb{R}^{d} x ∈ R d P a x = u P^{a}x = u P a x = u
Query x x x w = w ∗ ( P D M x ) w = w^{*}(P^{DM}x) w = w ∗ ( P D M x )
D ← D ∪ { ( x , w ) } D \leftarrow D \cup\{(x,w)\} D ← D ∪ {( x , w )}
Return: D D D
Algorithm 6 Boundary sampling (BndS)
Input: A full-rank matrix P a P^{a} P a M ≥ 1 M \ge1 M ≥ 1
Initialize: D ← ∅ D \leftarrow\varnothing D ← ∅
for i = 1 , … , m i = 1,\ldots,m i = 1 , … , m do
Choose linearly independent x ˉ i 0 , 1 , … , x ˉ i 0 , d − n + 1 \bar{x}_{i0,1},\ldots,\bar{x}_{i0,d-n+1} x ˉ i 0 , 1 , … , x ˉ i 0 , d − n + 1 P a x ˉ i 0 , j = r i P^{a}\bar{x}_{i0,j} = r_i P a x ˉ i 0 , j = r i j = 1 , … , d − n + 1 j = 1,\ldots,d-n+1 j = 1 , … , d − n + 1
for j = 1 , … , d − n + 1 j = 1,\ldots,d-n+1 j = 1 , … , d − n + 1 do
Query x ˉ i 0 , j \bar{x}_{i0,j} x ˉ i 0 , j w ˉ i 0 , j = w ∗ ( P D M x ˉ i 0 , j ) \bar{w}_{i0,j} = w^{*}(P^{DM}\bar{x}_{i0,j}) w ˉ i 0 , j = w ∗ ( P D M x ˉ i 0 , j )
D ← D ∪ { ( x ˉ i 0 , j , w ˉ i 0 , j ) } D \leftarrow D \cup\{(\bar{x}_{i0,j},\bar{w}_{i0,j})\} D ← D ∪ {( x ˉ i 0 , j , w ˉ i 0 , j )}
for i = 1 , … , m i = 1,\ldots,m i = 1 , … , m do
for j = 1 , … , d − n + 1 j = 1,\ldots,d-n+1 j = 1 , … , d − n + 1 do
for k ∈ C i k \in C_i k ∈ C i do
x ~ i k j ← M x ˉ i 0 , j + ∑ ℓ ∈ I k ∖ { i } x ˉ ℓ 0 , j ∥ M r i + ∑ ℓ ∈ I k ∖ { i } r ℓ ∥ \tilde{x}_{ikj} \leftarrow\frac{M\bar{x}_{i0,j}+\sum_{\ell\in I_k\setminus\{i\}}\bar{x}_{\ell0,j}}{\left\lVert Mr_i+\sum_{\ell\in I_k\setminus\{i\}}r_\ell\right\rVert} x ~ ik j ← M r i + ∑ ℓ ∈ I k ∖ { i } r ℓ M x ˉ i 0 , j + ∑ ℓ ∈ I k ∖ { i } x ˉ ℓ 0 , j
Query x ~ i k j \tilde{x}_{ikj} x ~ ik j w ~ i k j = w ∗ ( P D M x ~ i k j ) \tilde{w}_{ikj} = w^{*}(P^{DM}\tilde{x}_{ikj}) w ~ ik j = w ∗ ( P D M x ~ ik j )
D ← D ∪ { ( x ~ i k j , w ~ i k j ) } D \leftarrow D \cup\{(\tilde{x}_{ikj},\tilde{w}_{ikj})\} D ← D ∪ {( x ~ ik j , w ~ ik j )}
Return: D D D
The bound on ∥ x ∥ \lVert x\rVert ∥ x ∥ σ min ( X i ) ≥ κ > 0 \sigma_{\min}(X_i) \ge\kappa> 0 σ m i n ( X i ) ≥ κ > 0 X i X_i X i M ( Δ ) → ∞ M(\Delta) \to\infty M ( Δ ) → ∞ Δ M ( Δ ) → 0 \Delta M(\Delta) \to0 Δ M ( Δ ) → 0 Δ ↓ 0 \Delta\downarrow0 Δ ↓ 0 Δ ( M ( Δ ) + K − 1 ) → 0 \Delta(M(\Delta) + K - 1) \to0 Δ ( M ( Δ ) + K − 1 ) → 0 (9) holds eventually. For example, M ( Δ ) = max { 1 , Δ − 1 / 2 } M(\Delta) = \max\{1,\Delta^{-1/2}\} M ( Δ ) = max { 1 , Δ − 1/2 } Δ \Delta Δ
Restricted context region
We consider the undefended interface with query contexts restricted to a set X ⊆ R d \mathcal{X} \subseteq\mathbb{R}^{d} X ⊆ R d
Lemma A.4. Let J ⊆ { 1 , … , m } J \subseteq\{1,\ldots,m\} J ⊆ { 1 , … , m } { a i : i ∈ J } \{a_i: i \in J\} { a i : i ∈ J } n + 1 n+1 n + 1 i ∈ J i \in J i ∈ J x ˉ i ∈ int ( X ) \bar{x}_i \in\operatorname{int}(\mathcal{X}) x ˉ i ∈ int ( X ) P D M x ˉ i = α i r i P^{DM}\bar{x}_i = \alpha_i r_i P D M x ˉ i = α i r i α i > 0 \alpha_i > 0 α i > 0 P a P^{a} P a w ∗ ( P D M x ) ∈ W ∗ ( P a x ) w^{*}(P^{DM}x) \in W^{*}(P^{a}x) w ∗ ( P D M x ) ∈ W ∗ ( P a x ) x ∈ X ∖ ker ( P D M ) x \in\mathcal{X} \setminus\ker(P^{DM}) x ∈ X ∖ ker ( P D M ) P a = γ P D M P^{a} = \gamma P^{DM} P a = γ P D M γ > 0 \gamma> 0 γ > 0
For boundary sampling, fix a set J ⊆ { 1 , … , m } J \subseteq\{1,\ldots,m\} J ⊆ { 1 , … , m } x ˉ i 0 , j \bar{x}_{i0,j} x ˉ i 0 , j x ~ i k j \tilde{x}_{ikj} x ~ ik j i ∈ J i \in J i ∈ J j = 1 , … , d − n + 1 j = 1,\ldots,d-n+1 j = 1 , … , d − n + 1 k ∈ C i k \in C_i k ∈ C i X \mathcal{X} X J J J
Lemma A.5. Suppose { a i : i ∈ J } \{a_i: i \in J\} { a i : i ∈ J } n + 1 n+1 n + 1 Δ > 0 \Delta> 0 Δ > 0 M = M ( Δ ) ≥ 1 M = M(\Delta) \ge1 M = M ( Δ ) ≥ 1 R > 0 R > 0 R > 0 κ > 0 \kappa> 0 κ > 0 Δ \Delta Δ R R R σ min ( X i ) ≥ κ \sigma_{\min}(X_i) \ge\kappa σ m i n ( X i ) ≥ κ i ∈ J i \in J i ∈ J J J J M ( Δ ) → + ∞ M(\Delta) \to+\infty M ( Δ ) → + ∞ Δ ↓ 0 \Delta\downarrow0 Δ ↓ 0 Δ ( M ( Δ ) + K − 1 ) < η \Delta(M(\Delta)+K-1) < \eta Δ ( M ( Δ ) + K − 1 ) < η Δ \Delta Δ ( 1 + 2 R L ε Δ ) n d \left(1+\frac{2R L \varepsilon}{\Delta}\right)^{nd} ( 1 + Δ 2 R L ε ) n d P M ( Δ ) , Δ a → P D M ∥ P D M ∥ F P^{a}_{M(\Delta),\Delta} \to\frac{P^{DM}}{\lVert P^{DM}\rVert_F} P M ( Δ ) , Δ a → ∥ P D M ∥ F P D M L p r e d ( P M ( Δ ) , Δ a , P D M , x ) → 0 L_{\mathrm{pred}}(P^{a}_{M(\Delta),\Delta},P^{DM},x) \to0 L pred ( P M ( Δ ) , Δ a , P D M , x ) → 0 x ∉ ker ( P D M ) x \notin\ker(P^{DM}) x ∈ / ker ( P D M )
Experiment setup
Synthetic instances. In the experiment, the decision-maker first learns the prediction model P D M P^{DM} P D M D = { x i , c i } D = \{x_i, c_i\} D = { x i , c i } x i x_i x i U [ 0 , 20 ] U[0,20] U [ 0 , 20 ] c i = P t r u e x i + ϵ c_i = P^{\mathrm{true}}x_i + \epsilon c i = P true x i + ϵ ϵ ∼ N ( 0 , I n ) \epsilon\sim\mathcal{N}(0,I_n) ϵ ∼ N ( 0 , I n ) P t r u e P^{\mathrm{true}} P true P i j t r u e ∼ U [ − 10 , 10 ] P^{\mathrm{true}}_{ij} \sim U[-10,10] P ij true ∼ U [ − 10 , 10 ]
Given a query context x x x P D M x P^{DM}x P D M x min w ∈ S ( P D M x ) ⊤ w \min_{w \in S}(P^{DM}x)^\top w min w ∈ S ( P D M x ) ⊤ w
min w ∈ R n ( P D M x ) ⊤ w s.t. a ⊤ w ≤ b , 0 ≤ w ≤ 1. (10) \begin{aligned}
\min_{w \in\mathbb{R}^n} \quad& (P^{DM}x)^\top w \\
\text{s.t.} \quad& a^\top w \le b,\quad0 \le w \le1. \tag*{(10)}
\end{aligned} w ∈ R n min s.t. ( P D M x ) ⊤ w a ⊤ w ≤ b , 0 ≤ w ≤ 1. (10) where a ∈ R n a \in\mathbb{R}^n a ∈ R n b = 0.6 ∑ i = 1 n a i b = 0.6\sum_{i=1}^{n} a_i b = 0.6 ∑ i = 1 n a i n n n (2) , however, is a linear program using the inequality representation of the polytope and does not require vertex enumeration.
We compare boundary sampling (BndS), uniform sampling (Unif), and a nonadaptive inverse optimization baseline (INV). Unif and BndS alternate sampling and inverse optimization as in Algorithm 1, using the sampling constructions in Algorithms 5 and 6, respectively. INV performs one inverse optimization fit on a nonadaptive batch of contexts, with sample sizes matched in the reported comparisons. Unif draws predicted cost directions uniformly from the unit sphere in R n \mathbb{R}^n R n (2) .
For the attack comparisons, we perform 100 repetitions, using a different deployed matrix P D M P^{DM} P D M
In the query-budget experiment, we use d = 10 d = 10 d = 10 n = 5 n = 5 n = 5
For each defensive parameter setting, we perform 100 repetitions and record the attacker’s prediction loss and the decision-maker’s regret. The parameter is ϵ \epsilon ϵ δ \delta δ
All experiments were conducted on a machine with two AMD EPYC 7643 48-core processors, with each job allocated one CPU core and 16 GB of memory.
Real data. The KuaiRand-1K dataset [13 ] contains 1000 users and approximately four million videos. Its standard policy portion contains 11713045 interactions. We use the records of 800 users for training and the remaining users for testing. Each user is represented by a feature vector of dimension d = 18 d = 18 d = 18 n = 5 n = 5 n = 5 P D M P^{DM} P D M − P D M x -P^{DM}x − P D M x k = ⌈ n 2 ⌉ k = \left\lceil\frac{n}{2} \right\rceil k = ⌈ 2 n ⌉
min w ∈ R n ( P D M x ) ⊤ w s.t. ∑ i = 1 n w i ≤ k , 0 ≤ w ≤ 1. (11) \begin{aligned}
\min_{w \in\mathbb{R}^n} \quad& (P^{DM}x)^\top w \\
\text{s.t.} \quad& \sum_{i=1}^{n} w_i \le k,\quad0 \le w \le1. \tag*{(11)}
\end{aligned} w ∈ R n min s.t. ( P D M x ) ⊤ w i = 1 ∑ n w i ≤ k , 0 ≤ w ≤ 1. (11) Prediction loss is evaluated using the attacker and deployed cost vectors, and regret is measured under the fitted cost vector P D M x P^{DM}x P D M x
Additional experimental results
Attacker’s coefficient. Figure 7 compares prediction loss and the number of iterations for different values of M M M Δ \Delta Δ Δ \Delta Δ M M M Δ \Delta Δ Δ ( M + K − 1 ) < η S \Delta(M + K - 1) < \eta_S Δ ( M + K − 1 ) < η S
Figure 7. The out-of-sample prediction loss and iterations for the attacking framework in different attacker’s parameter settings.
Proposition 3.7 bounds the number of inverse optimization updates rather than specifying its realized value. With a common query-norm bound R R R M M M M M M M M M Δ \Delta Δ
Attacker’s robustness to misspecification. On the synthetic dataset, we evaluate the linear attack against two nonlinear deployed model classes: a multilayer perceptron (MLP) with one hidden layer and ReLU activation, and support vector regression (SVR) with a Gaussian kernel. The hyperparameters, including hidden-layer width and kernel bandwidth, are selected by cross-validation.
Figure 8 a reports prediction-loss values below 0.01 for the evaluated linear attacks against both deployed models, while Figure 8 b reports their sample sizes. These results show that a linear attacker can approximate the deployed prediction directions in these experiments even when the decision-maker uses a nonlinear model class.
Figure 8. (a) Prediction loss; (b) Sample size for BndS and Unif against MLP and SVR predictors fitted to the linear synthetic data; and (c) Prediction loss of a linear attacker against MLP and SVR predictors as the quadratic coefficient γ \gamma γ
We also evaluate the linear attacker on data with a quadratic component:
c = P t r u e x + γ B ϕ 2 ( x ) + ϵ . c = P^{\mathrm{true}}x + \gamma B\phi_2(x) + \epsilon. c = P true x + γ B ϕ 2 ( x ) + ϵ . Here, ϕ 2 ( x ) \phi_2(x) ϕ 2 ( x ) x x x P i j t r u e ∼ U [ − 10 , 10 ] P^{\mathrm{true}}_{ij} \sim\mathcal{U}[-10, 10] P ij true ∼ U [ − 10 , 10 ] B i j ∼ Bernoulli ( 0.5 ) B_{ij} \sim\operatorname{Bernoulli}(0.5) B ij ∼ Bernoulli ( 0.5 ) ϵ \epsilon ϵ Figure 8 c shows generally larger prediction loss for larger values of γ \gamma γ
Large-scale optimization problem. A call to Algorithm 6 makes ( d − n + 1 ) ( m + ∑ k = 1 ∣ V ∣ ∣ I k ∣ ) (d-n+1)(m+\sum_{k=1}^{|V|}|I_k|) ( d − n + 1 ) ( m + ∑ k = 1 ∣ V ∣ ∣ I k ∣ ) n n n
To control the number of queries in larger problems, we use uniform sampling on the fractional Knapsack problem in Eq. (10) , with d = 2 n d = 2n d = 2 n N = 5 n N = 5n N = 5 n n n n Figure 9 a reports small prediction losses without defense, and Figure 9 b reports increasing time per iteration as n n n
Figure 9. Prediction loss (a) and runtime per iteration (b) of Unif on fractional Knapsack instances of different dimensions.
For the defender, we evaluate decision perturbation restricted to at most three neighboring vertices per query against a uniform-sampling attacker on fractional Knapsack instances with n = 20 n = 20 n = 20 Figure 10 shows a security-performance trade-off for this implementation. The regret bound in Proposition 4.1 remains valid provided every selected neighbor passes the angular eligibility test in Algorithm 3. The expected prediction error bound in Theorem 4.2 assumes that Algorithm 3 includes every neighboring vertex satisfying the angular eligibility condition..
Figure 10. Security-performance trade-off under the fractional Knapsack problem with n = 20 n = 20 n = 20
Prediction loss and regret on defensive parameter. Figure 11 shows that prediction loss and regret generally increase over the tested values of ϵ \epsilon ϵ ϵ \epsilon ϵ Theorem 4.2 gives a nondecreasing lower bound on expected prediction loss under its population-fitting condition.
Figure 11. Prediction loss (left) and decision-maker’s regret (right) as functions of the defensive parameter ϵ \epsilon ϵ
Proof
Proof of Proposition 2.2. Suppose that s ( x ) = − p ( x ) s(x) = -p(x) s ( x ) = − p ( x ) i ( x ) ∈ argmin 1 ≤ i ≤ n p i ( x ) i(x) \in\operatorname*{argmin}_{1 \leq i \leq n} p_i(x) i ( x ) ∈ argmin 1 ≤ i ≤ n p i ( x ) w ∈ S w \in S w ∈ S
w T p ( x ) = ∑ i = 1 n w i p i ( x ) ≥ min i p i ( x ) , w^{\mathsf{T}}p(x) = \sum_{i=1}^{n} w_i p_i(x) \geq\min_i p_i(x), w T p ( x ) = i = 1 ∑ n w i p i ( x ) ≥ i min p i ( x ) , with equality at e i ( x ) e_{i(x)} e i ( x ) i ( x ) ∈ argmin 1 ≤ i ≤ n p i ( x ) i(x) \in\operatorname*{argmin}_{1 \leq i \leq n} p_i(x) i ( x ) ∈ argmin 1 ≤ i ≤ n p i ( x ) i ( x ) i(x) i ( x ) e i ( x ) e_{i(x)} e i ( x )
Proof of Lemma 3.3. The key is to show that calibration is independent of the particular inverse feasibility loss. Indeed, we define the set of globally decision consistent matrices by
F = { P ∈ R n × d ∖ { 0 } : w ⋆ ( P D M x ) ∈ W ⋆ ( P x ) for every x ∉ ker ( P D M ) } , \mathcal{F} = \left\{P \in\mathbb{R}^{n \times d} \setminus\{0\} : w^{\star}(P^{DM}x) \in W^{\star}(Px) \text{ for every } x \notin\operatorname{ker}(P^{DM})\right\}, F = { P ∈ R n × d ∖ { 0 } : w ⋆ ( P D M x ) ∈ W ⋆ ( P x ) for every x ∈ / ker ( P D M ) } , and the set of matrices with globally correct prediction directions by
G = { P ∈ R n × d ∖ { 0 } : L p r e d ( P , P D M ; x ) = 0 for every x ∉ ker ( P D M ) } . \mathcal{G} = \left\{P \in\mathbb{R}^{n \times d} \setminus\{0\} : L_{\mathrm{pred}}(P, P^{DM}; x) = 0 \text{ for every } x \notin\operatorname{ker}(P^{DM})\right\}. G = { P ∈ R n × d ∖ { 0 } : L pred ( P , P D M ; x ) = 0 for every x ∈ / ker ( P D M ) } . For any inverse feasibility loss L L L L ( P , P D M ; x ) = 0 L(P,P^{DM};x)=0 L ( P , P D M ; x ) = 0 w ∗ ( P D M x ) ∈ W ∗ ( P x ) w^*(P^{DM}x)\in W^*(Px) w ∗ ( P D M x ) ∈ W ∗ ( P x ) P P P x x x F \mathcal{F} F F \mathcal{F} F G \mathcal{G} G
We claim that G ⊆ F \mathcal{G}\subseteq\mathcal{F} G ⊆ F P ∈ G P\in\mathcal{G} P ∈ G x ∉ ker ( P D M ) x\notin\ker(P^{DM}) x ∈ / ker ( P D M ) P D M x ≠ 0 P^{DM}x\ne0 P D M x = 0 L p r e d ( P , P D M ; x ) = 0 L_{\mathrm{pred}}(P,P^{DM};x)=0 L pred ( P , P D M ; x ) = 0 P x = γ x P D M x Px=\gamma_xP^{DM}x P x = γ x P D M x γ x > 0 \gamma_x>0 γ x > 0 W ∗ ( P x ) = W ∗ ( P D M x ) W^*(Px)=W^*(P^{DM}x) W ∗ ( P x ) = W ∗ ( P D M x ) w ∗ ( P D M x ) ∈ W ∗ ( P x ) w^*(P^{DM}x)\in W^*(Px) w ∗ ( P D M x ) ∈ W ∗ ( P x ) P ∈ F P\in\mathcal{F} P ∈ F
It suffices to consider two cases. If F = G \mathcal{F}=\mathcal{G} F = G P b a d ∈ F ∖ G P_{\mathrm{bad}}\in\mathcal{F}\setminus\mathcal{G} P bad ∈ F ∖ G L ( P b a d , P D M ; x ) = 0 L(P_{\mathrm{bad}},P^{DM};x)=0 L ( P bad , P D M ; x ) = 0 x ∉ ker ( P D M ) x\notin\ker(P^{DM}) x ∈ / ker ( P D M ) x 0 ∉ ker ( P D M ) x_0\notin\ker(P^{DM}) x 0 ∈ / ker ( P D M ) L p r e d ( P b a d , P D M ; x 0 ) > 0 L_{\mathrm{pred}}(P_{\mathrm{bad}},P^{DM};x_0)>0 L pred ( P bad , P D M ; x 0 ) > 0 L L L
We now show that calibration fails for an n n n w ∈ S w\in S w ∈ S w = w 0 + ℓ U z w=w_0+\ell Uz w = w 0 + ℓ U z w 0 ∈ R n w_0\in\mathbb{R}^n w 0 ∈ R n ℓ > 0 \ell>0 ℓ > 0 z ∈ [ 0 , 1 ] n z\in[0,1]^n z ∈ [ 0 , 1 ] n U U U c ⊤ w c^\top w c ⊤ w S S S ( U ⊤ c ) ⊤ z (U^\top c)^\top z ( U ⊤ c ) ⊤ z [ 0 , 1 ] n [0,1]^n [ 0 , 1 ] n z ∗ z^* z ∗
z i ∗ ∈ { { 0 } , if ( U ⊤ c ) i > 0 , { 1 } , if ( U ⊤ c ) i < 0 , [ 0 , 1 ] , otherwise , for all i = 1 , 2 , … , n . z_i^*\in
\begin{cases}
\{0\}, & \text{if }(U^\top c)_i>0,\\
\{1\}, & \text{if }(U^\top c)_i<0,\\
[0,1], & \text{otherwise},
\end{cases}
\quad\text{for all }i=1,2,\ldots,n. z i ∗ ∈ ⎩ ⎨ ⎧ { 0 } , { 1 } , [ 0 , 1 ] , if ( U ⊤ c ) i > 0 , if ( U ⊤ c ) i < 0 , otherwise , for all i = 1 , 2 , … , n . We define D = diag ( 1 , … , 1 , 2 ) D=\operatorname{diag}(1,\ldots,1,2) D = diag ( 1 , … , 1 , 2 ) P a = U D U ⊤ P D M P^a=UDU^\top P^{DM} P a = U D U ⊤ P D M U D U ⊤ UDU^\top U D U ⊤ P D M P^{DM} P D M P a P^a P a x x x U ⊤ P a x = D U ⊤ P D M x U^\top P^a x=DU^\top P^{DM}x U ⊤ P a x = D U ⊤ P D M x D D D W ∗ ( P a x ) = W ∗ ( P D M x ) W^*(P^a x)=W^*(P^{DM}x) W ∗ ( P a x ) = W ∗ ( P D M x ) x ∈ R d x\in\mathbb{R}^d x ∈ R d L ( P a , P D M ; x ) = 0 L(P^a,P^{DM};x)=0 L ( P a , P D M ; x ) = 0 x ∈ R d x\in\mathbb{R}^d x ∈ R d
Since P D M P^{DM} P D M n ≥ 2 n\ge2 n ≥ 2 x 0 ∈ R d x_0\in\mathbb{R}^d x 0 ∈ R d P D M x 0 = U ( e 1 + e n ) P^{DM}x_0=U(e_1+e_n) P D M x 0 = U ( e 1 + e n ) P a x 0 = U ( e 1 + 2 e n ) P^a x_0=U(e_1+2e_n) P a x 0 = U ( e 1 + 2 e n )
L p r e d ( P a , P D M ; x 0 ) = ∠ ( e 1 + 2 e n , e 1 + e n ) = arccos ( 3 10 ) > 0. L_{\mathrm{pred}}(P^a,P^{DM};x_0)=\angle(e_1+2e_n,e_1+e_n)=\arccos\left(\frac{3}{\sqrt{10}}\right)>0. L pred ( P a , P D M ; x 0 ) = ∠ ( e 1 + 2 e n , e 1 + e n ) = arccos ( 10 3 ) > 0. This implies that x 0 ∉ ker ( P D M ) x_0\notin\ker(P^{DM}) x 0 ∈ / ker ( P D M ) P a ∈ F ∖ G P^a\in\mathcal{F}\setminus\mathcal{G} P a ∈ F ∖ G n n n
For the remaining proofs, we let
r i = − a i ∥ a i ∥ , C k = cone ( w k ) , I k = { i : a i ⊤ w k = b i } , C i = { k : i ∈ I k } . r_i=-\frac{a_i}{\lVert a_i\rVert},\qquad C_k=\operatorname{cone}(w_k),\qquad I_k=\{i:a_i^\top w_k=b_i\},\qquad C_i=\{k:i\in I_k\}. r i = − ∥ a i ∥ a i , C k = cone ( w k ) , I k = { i : a i ⊤ w k = b i } , C i = { k : i ∈ I k } . where I k I_k I k w k w_k w k C i C_i C i i i i C k C_k C k c ∈ int ( C k ) ⇔ W ∗ ( c ) = { w k } c\in\operatorname{int}(C_k)\Leftrightarrow W^*(c)=\{w_k\} c ∈ int ( C k ) ⇔ W ∗ ( c ) = { w k } C k = polycone { r i : i ∈ I k } C_k=\operatorname{polycone}\{r_i:i\in I_k\} C k = polycone { r i : i ∈ I k } ⋂ k ∈ C i C k = { a r i : a ≥ 0 } \bigcap_{k\in C_i}C_k=\{ar_i:a\ge0\} ⋂ k ∈ C i C k = { a r i : a ≥ 0 } i i i r i r_i r i
Proof of Theorem 3.5. Suppose that P a ≠ 0 P^a\ne0 P a = 0 w ∗ ( P D M x ) ∈ W ∗ ( P a x ) w^*(P^{DM}x)\in W^*(P^a x) w ∗ ( P D M x ) ∈ W ∗ ( P a x ) x ∉ ker ( P D M ) x\notin\ker(P^{DM}) x ∈ / ker ( P D M ) ker ( P D M ) ⊆ ker ( P a ) \ker(P^{DM})\subseteq\ker(P^a) ker ( P D M ) ⊆ ker ( P a ) z ∈ ker ( P D M ) z\in\ker(P^{DM}) z ∈ ker ( P D M ) c 0 ∈ int ( C k ) c_0\in\operatorname{int}(C_k) c 0 ∈ int ( C k ) w k w_k w k x 0 x_0 x 0 P D M x 0 = c 0 P^{DM}x_0=c_0 P D M x 0 = c 0 P D M P^{DM} P D M x 0 x_0 x 0 P D M ( x 0 + t z ) = c 0 ≠ 0 P^{DM}(x_0+tz)=c_0\ne0 P D M ( x 0 + t z ) = c 0 = 0 t ∈ R t\in\mathbb{R} t ∈ R W ∗ ( c 0 ) = { w k } W^*(c_0)=\{w_k\} W ∗ ( c 0 ) = { w k } P a ( x 0 + t z ) ∈ C k P^a(x_0+tz)\in C_k P a ( x 0 + t z ) ∈ C k t ∈ R t\in\mathbb{R} t ∈ R C k C_k C k P a z , − P a z ∈ C k P^a z,-P^a z\in C_k P a z , − P a z ∈ C k C k C_k C k P a z = 0 P^a z=0 P a z = 0 ker ( P D M ) ⊆ ker ( P a ) \ker(P^{DM})\subseteq\ker(P^a) ker ( P D M ) ⊆ ker ( P a )
Since P D M P^{DM} P D M ker ( P D M ) ⊆ ker ( P a ) \ker(P^{DM})\subseteq\ker(P^a) ker ( P D M ) ⊆ ker ( P a ) P a = B P D M P^a=BP^{DM} P a = B P D M B : R n → R n B:\mathbb{R}^n\to\mathbb{R}^n B : R n → R n B = γ I n B=\gamma I_n B = γ I n γ > 0 \gamma>0 γ > 0 c ∈ int ( C k ) c\in\operatorname{int}(C_k) c ∈ int ( C k ) x x x P D M x = c P^{DM}x=c P D M x = c w k ∈ W ∗ ( B c ) w_k\in W^*(Bc) w k ∈ W ∗ ( B c ) B c ∈ C k Bc\in C_k B c ∈ C k C k = int ( C k ) C_k=\operatorname{int}(C_k) C k = int ( C k ) B C k ⊆ C k BC_k\subseteq C_k B C k ⊆ C k k k k i i i B C i ⊆ C i = { a r i : a ≥ 0 } BC_i\subseteq C_i=\{ar_i:a\ge0\} B C i ⊆ C i = { a r i : a ≥ 0 } B a k i = λ i a k i Ba_{k_i}=\lambda_i a_{k_i} B a k i = λ i a k i λ i ≥ 0 \lambda_i\ge0 λ i ≥ 0 B B B a k n + 1 = ∑ j = 1 n β j a k j a_{k_n+1}=\sum_{j=1}^n\beta_j a_{k_j} a k n + 1 = ∑ j = 1 n β j a k j ∑ j = 1 n β j ( λ j − λ k n + 1 ) a k j = 0 \sum_{j=1}^n\beta_j(\lambda_j-\lambda_{k_n+1})a_{k_j}=0 ∑ j = 1 n β j ( λ j − λ k n + 1 ) a k j = 0 β j ≠ 0 \beta_j\ne0 β j = 0 λ k j = λ k n + 1 \lambda_{k_j}=\lambda_{k_n+1} λ k j = λ k n + 1 j = 1 , … , n j=1,\ldots,n j = 1 , … , n a k 1 , … , a k n a_{k_1},\ldots,a_{k_n} a k 1 , … , a k n R n \mathbb{R}^n R n B = γ I n B=\gamma I_n B = γ I n γ = λ k n + 1 ≥ 0 \gamma=\lambda_{k_n+1}\ge0 γ = λ k n + 1 ≥ 0 P a ≠ 0 P^a\ne0 P a = 0 γ > 0 \gamma>0 γ > 0 P a = γ P D M P^a=\gamma P^{DM} P a = γ P D M
Proof of Proposition 3.6. The proof of Theorem 3.5 shows that global decision consistency alone gives a linear map B : R n → R n B:\mathbb{R}^{n}\to\mathbb{R}^{n} B : R n → R n P a = B P D M P^{a}=BP^{DM} P a = B P D M B r i = λ i r i Br_{i}=\lambda_{i}r_{i} B r i = λ i r i λ i ≥ 0 \lambda_{i}\ge0 λ i ≥ 0 i i i rank ( P a ) = n \operatorname{rank}(P^{a})=n rank ( P a ) = n P a = B P D M P^{a}=BP^{DM} P a = B P D M B B B r i ≠ 0 r_{i}\ne0 r i = 0 λ i > 0 \lambda_{i}>0 λ i > 0 i i i
Suppose that x ˉ \bar{x} x ˉ P a x ˉ = α r i P^{a}\bar{x}=\alpha r_{i} P a x ˉ = α r i i i i α > 0 \alpha>0 α > 0 B − 1 r i = λ i − 1 r i B^{-1}r_{i}=\lambda_{i}^{-1}r_{i} B − 1 r i = λ i − 1 r i
P D M x ˉ = B − 1 P a x ˉ = α λ i r i = 1 λ i P a x ˉ . P^{DM}\bar{x}=B^{-1}P^{a}\bar{x}=\frac{\alpha}{\lambda_{i}}r_{i}=\frac{1}{\lambda_{i}}P^{a}\bar{x}. P D M x ˉ = B − 1 P a x ˉ = λ i α r i = λ i 1 P a x ˉ . This implies that the two costs are nonzero and positively aligned. Thus, we have L p r e d ( P a , P D M ; x ˉ ) = 0 L_{\mathrm{pred}}(P^{a},P^{DM};\bar{x})=0 L pred ( P a , P D M ; x ˉ ) = 0
Proof of Proposition 3.7. Since ∥ P 0 ∥ F = 1 \lVert P^{0}\rVert_{F}=1 ∥ P 0 ∥ F = 1 ∥ P t ∥ F = 1 \lVert P^{t}\rVert_{F}=1 ∥ P t ∥ F = 1 t t t P s P^{s} P s s ≥ 1 s\ge1 s ≥ 1 D s − 1 D^{s-1} D s − 1 t t t ( x t , w t ) ∈ D t (x_{t},w_{t})\in D^{t} ( x t , w t ) ∈ D t v t ∈ V v_{t}\in V v t ∈ V
( P t x t ) ⊤ ( w t − v t ) > Δ . (P^{t}x_{t})^{\top}(w_{t}-v_{t})>\Delta. ( P t x t ) ⊤ ( w t − v t ) > Δ. For every subsequent iterate P t ′ P^{t'} P t ′ D t ⊆ D t ′ − 1 D^{t}\subseteq D^{t'-1} D t ⊆ D t ′ − 1 ( P t ′ x t ) ⊤ ( w t − v t ) ≤ 0 (P^{t'}x_{t})^{\top}(w_{t}-v_{t})\le0 ( P t ′ x t ) ⊤ ( w t − v t ) ≤ 0
Δ < ( ( P t − P t ′ ) x t ) ⊤ ( w t − v t ) ≤ ∥ P t − P t ′ ∥ F ∥ x t ∥ ∥ w t − v t ∥ ≤ R L e ∥ P t − P t ′ ∥ F . \Delta<((P^{t}-P^{t'})x_{t})^{\top}(w_{t}-v_{t})\le\lVert P^{t}-P^{t'}\rVert_{F}\lVert x_{t}\rVert\lVert w_{t}-v_{t}\rVert\le RL_{e}\lVert P^{t}-P^{t'}\rVert_{F}. Δ < (( P t − P t ′ ) x t ) ⊤ ( w t − v t ) ≤ ∥ P t − P t ′ ∥ F ∥ x t ∥ ∥ w t − v t ∥ ≤ R L e ∥ P t − P t ′ ∥ F . Thus, any two nonterminal iterates are separated by more than Δ R L e \frac{\Delta}{RL_{e}} R L e Δ
For any finite collection of T T T Δ 2 R L e \frac{\Delta}{2RL_{e}} 2 R L e Δ 1 + Δ 2 R L e 1+\frac{\Delta}{2RL_{e}} 1 + 2 R L e Δ
T ( Δ 2 R L e ) n d ≤ ( 1 + Δ 2 R L e ) n d , T\left(\frac{\Delta}{2RL_{e}}\right)^{nd}\le\left(1+\frac{\Delta}{2RL_{e}}\right)^{nd}, T ( 2 R L e Δ ) n d ≤ ( 1 + 2 R L e Δ ) n d , which implies
T ≤ ( 1 + 2 R L e Δ ) n d . T\le\left(1+\frac{2RL_{e}}{\Delta}\right)^{nd}. T ≤ ( 1 + Δ 2 R L e ) n d . Each nonterminal iteration performs one inverse optimization update, and each sampling call is finite. Therefore, Algorithm 1 terminates after at most ( 1 + 2 R L e Δ ) n d \left(1+\frac{2RL_{e}}{\Delta}\right)^{nd} ( 1 + Δ 2 R L e ) n d
Lemma B.1. Let P a P^{a} P a x ˉ ∈ R d \bar{x}\in\mathbb{R}^{d} x ˉ ∈ R d P a x ˉ = α r i P^{a}\bar{x}=\alpha r_{i} P a x ˉ = α r i i i i α > 0 \alpha>0 α > 0 ϵ > 0 \epsilon>0 ϵ > 0 w ⋆ ( P D M x ) ∈ W ⋆ ( P a x ) w^{\star}(P^{DM}x)\in W^{\star}(P^{a}x) w ⋆ ( P D M x ) ∈ W ⋆ ( P a x ) x ∈ R d x\in\mathbb{R}^{d} x ∈ R d P D M x ≠ 0 P^{DM}x\ne0 P D M x = 0 P a x ≠ 0 P^{a}x\ne0 P a x = 0 ∠ ( P a x , r i ) < ϵ \angle(P^{a}x,r_{i})<\epsilon ∠ ( P a x , r i ) < ϵ
P D M x ˉ ∈ { α r i : α ≥ 0 } . P^{DM}\bar{x}\in\{\alpha r_{i}:\alpha\ge0\}. P D M x ˉ ∈ { α r i : α ≥ 0 } . In particular, if P D M x ˉ ≠ 0 P^{DM}\bar{x}\ne0 P D M x ˉ = 0 L p r e d ( P a , P D M ; x ˉ ) = 0 L_{\mathrm{pred}}(P^{a},P^{DM};\bar{x})=0 L pred ( P a , P D M ; x ˉ ) = 0
Proof. If P D M x ˉ = 0 P^{DM}\bar{x}=0 P D M x ˉ = 0 k ∈ C i k\in C_{i} k ∈ C i P a P^{a} P a h k ∈ R d h_{k}\in\mathbb{R}^{d} h k ∈ R d P a h k ∈ int ( C k ) P^{a}h_{k}\in\operatorname{int}(C_{k}) P a h k ∈ int ( C k ) x t = x ˉ + t h k x_{t}=\bar{x}+th_{k} x t = x ˉ + t h k t > 0 t>0 t > 0 x t → x ˉ x_{t}\to\bar{x} x t → x ˉ t ↓ 0 t\downarrow0 t ↓ 0
P a x t = α r i + t P a h k ∈ int ( C k ) . P^{a}x_{t}=\alpha r_{i}+tP^{a}h_{k}\in\operatorname{int}(C_{k}). P a x t = α r i + t P a h k ∈ int ( C k ) . For sufficiently small t > 0 t>0 t > 0 P D M x t ≠ 0 P^{DM}x_{t}\ne0 P D M x t = 0 ∠ ( P a x t , r i ) < ϵ \angle(P^{a}x_{t},r_{i})<\epsilon ∠ ( P a x t , r i ) < ϵ w ⋆ ( P D M x t ) ∈ W ⋆ ( P a x t ) = { w k } w^{\star}(P^{DM}x_{t})\in W^{\star}(P^{a}x_{t})=\{w_{k}\} w ⋆ ( P D M x t ) ∈ W ⋆ ( P a x t ) = { w k } P D M x t ∈ C k P^{DM}x_{t}\in C_{k} P D M x t ∈ C k P D M x ˉ ∈ C k P^{DM}\bar{x}\in C_{k} P D M x ˉ ∈ C k k ∈ C i k\in C_{i} k ∈ C i
P D M x ˉ ∈ ⋂ k ∈ C i C k = { α r i : α ≥ 0 } . P^{DM}\bar{x}\in\bigcap_{k\in C_{i}}C_{k}=\{\alpha r_{i}:\alpha\ge0\}. P D M x ˉ ∈ k ∈ C i ⋂ C k = { α r i : α ≥ 0 } . If P D M x ˉ ≠ 0 P^{DM}\bar{x}\ne0 P D M x ˉ = 0 P D M x ˉ P^{DM}\bar{x} P D M x ˉ P a x ˉ = α r i P^{a}\bar{x}=\alpha r_{i} P a x ˉ = α r i L p r e d ( P a , P D M ; x ˉ ) = 0 L_{\mathrm{pred}}(P^{a},P^{DM};\bar{x})=0 L pred ( P a , P D M ; x ˉ ) = 0
Proof of Proposition 3.8. Suppose that no ϵ \epsilon ϵ I ( P a , P D M ) I(P^{a},P^{DM}) I ( P a , P D M ) I ( P a , P D M ) I(P^{a},P^{DM}) I ( P a , P D M ) w ⋆ ( P D M x ) ∈ W ⋆ ( P a x ) w^{\star}(P^{DM}x)\in W^{\star}(P^{a}x) w ⋆ ( P D M x ) ∈ W ⋆ ( P a x ) P a x ≠ 0 P^{a}x\ne0 P a x = 0 ∠ ( P a x , r i ) < ϵ \angle(P^{a}x,r_{i})<\epsilon ∠ ( P a x , r i ) < ϵ i i i
P D M x ˉ ∈ { α r i : α ≥ 0 } whenever P a x ˉ = r i . P^{DM}\bar{x}\in\{\alpha r_{i}:\alpha\ge0\}\quad\text{whenever }P^{a}\bar{x}=r_{i}. P D M x ˉ ∈ { α r i : α ≥ 0 } whenever P a x ˉ = r i . This implies that P D M ∈ P c ( P a ) P^{DM}\in\mathcal{P}_{c}(P^{a}) P D M ∈ P c ( P a ) P D M = γ P a P^{DM}=\gamma P^{a} P D M = γ P a γ ∈ R \gamma\in\mathbb{R} γ ∈ R P D M ≠ 0 P^{DM}\ne0 P D M = 0 γ > 0 \gamma>0 γ > 0 ϵ \epsilon ϵ I ( P a , P D M ) I(P^{a},P^{DM}) I ( P a , P D M )
Proof of Theorem 3.9. Theorem A.3 shows finite termination and P M a ( Δ ) → P D M ∥ P D M ∥ F P^{a}_{M}(\Delta) \to\frac{P^{DM}}{\lVert P^{DM}\rVert_{F}} P M a ( Δ ) → ∥ P D M ∥ F P D M x ∉ ker ( P D M ) x \notin\ker(P^{DM}) x ∈ / ker ( P D M )
Proof of Proposition 4.1. Fix a cache realization and a context x x x c = P D M x c = P^{DM}x c = P D M x w 0 = w ⋆ ( c ) w_0 = w^\star(c) w 0 = w ⋆ ( c ) w = w ~ ( x ) w = \widetilde{w}(x) w = w ( x ) c = 0 c = 0 c = 0 w = w 0 w = w_0 w = w 0 ∠ ( c , cone ( w ) ) ≤ ϵ \angle(c,\operatorname{cone}(w)) \le\epsilon ∠ ( c , cone ( w )) ≤ ϵ cone ( w ) \operatorname{cone}(w) cone ( w ) u ∈ cone ( w ) u \in\operatorname{cone}(w) u ∈ cone ( w )
∠ ( c , u ) = ∠ ( c , cone ( w ) ) ≤ ϵ . \angle(c,u) = \angle(c,\operatorname{cone}(w)) \le\epsilon. ∠ ( c , u ) = ∠ ( c , cone ( w )) ≤ ϵ . Since w w w u u u u T ( w − w 0 ) ≤ 0 u^{\mathsf T}(w-w_0) \le0 u T ( w − w 0 ) ≤ 0
c T ( w − w 0 ) ≤ ∥ c ∥ ( c ∥ c ∥ − u ) T ( w − w 0 ) ≤ ∥ c ∥ ∥ w − w 0 ∥ ∥ c ∥ c ∥ − u ∥ ≤ 2 L e ∥ c ∥ sin ( ∠ ( c , u ) 2 ) ≤ L e ϵ ∥ c ∥ . c^{\mathsf T}(w-w_0) \le\lVert c\rVert\left(\frac{c}{\lVert c\rVert}-u\right)^{\mathsf T}(w-w_0) \le\lVert c\rVert\lVert w-w_0\rVert\left\lVert\frac{c}{\lVert c\rVert}-u\right\rVert\le2L_e\lVert c\rVert\sin\left(\frac{\angle(c,u)}{2}\right) \le L_e\epsilon\lVert c\rVert. c T ( w − w 0 ) ≤ ∥ c ∥ ( ∥ c ∥ c − u ) T ( w − w 0 ) ≤ ∥ c ∥ ∥ w − w 0 ∥ ∥ c ∥ c − u ≤ 2 L e ∥ c ∥ sin ( 2 ∠ ( c , u ) ) ≤ L e ϵ ∥ c ∥ . Taking expectation under x ∼ Q x \sim Q x ∼ Q
E x ∼ Q [ Regret ( w ~ ( x ) ; x ) ] ≤ L e ϵ E x ∼ Q [ ∥ P D M x ∥ ] . \mathbb{E}_{x\sim Q}[\operatorname{Regret}(\widetilde{w}(x);x)] \le L_e\epsilon\mathbb{E}_{x\sim Q}[\lVert P^{DM}x\rVert]. E x ∼ Q [ Regret ( w ( x ) ; x )] ≤ L e ϵ E x ∼ Q [∥ P D M x ∥] . This completes the proof.
Proof of Theorem 4.2. Fix a cache realization and a context x x x c = P D M x c = P^{DM}x c = P D M x c a = P a x c_a = P^a x c a = P a x w 0 = w ⋆ ( c ) w_0 = w^\star(c) w 0 = w ⋆ ( c ) w a = w ⋆ ( c a ) w_a = w^\star(c_a) w a = w ⋆ ( c a )
Suppose that w ~ ( x ) ∈ W ⋆ ( c a ) \widetilde{w}(x) \in W^\star(c_a) w ( x ) ∈ W ⋆ ( c a ) c ∈ E c \in\mathcal{E} c ∈ E w ~ ( x ) ≠ w 0 \widetilde{w}(x) \ne w_0 w ( x ) = w 0 cone ( w 0 ) \operatorname{cone}(w_0) cone ( w 0 ) cone ( w ~ ( x ) ) \operatorname{cone}(\widetilde{w}(x)) cone ( w ( x )) c ∥ c ∥ \frac{c}{\lVert c\rVert} ∥ c ∥ c c a ∥ c a ∥ \frac{c_a}{\lVert c_a\rVert} ∥ c a ∥ c a c c c cone ( w 0 ) \operatorname{cone}(w_0) cone ( w 0 ) ψ ( x ) \psi(x) ψ ( x ) c a c_a c a cone ( w ~ ( x ) ) \operatorname{cone}(\widetilde{w}(x)) cone ( w ( x )) ϕ ( x ) \phi(x) ϕ ( x )
L pred ( P a , P D M ; x ) = ∠ ( c a , c ) ≥ ψ ( x ) + ϕ ( x ) . L_{\operatorname{pred}}(P^a,P^{DM};x) = \angle(c_a,c) \ge\psi(x) + \phi(x). L pred ( P a , P D M ; x ) = ∠ ( c a , c ) ≥ ψ ( x ) + ϕ ( x ) . In particular, the loss is at least ϵ \epsilon ϵ ϕ ( x ) ≥ ϵ \phi(x) \ge\epsilon ϕ ( x ) ≥ ϵ
Next, we consider the sufficient condition for fitting. If ϕ ( x ) = 0 \phi(x) = 0 ϕ ( x ) = 0 w a w_a w a c a c_a c a v ∈ V ∖ { w a } v \in V \setminus\{w_a\} v ∈ V ∖ { w a } cone ( w a ) ⊆ { u ∈ R n : u T ( v − w a ) ≥ 0 } \operatorname{cone}(w_a) \subseteq\{u \in\mathbb{R}^{n}: u^{\mathsf T}(v-w_a) \ge0\} cone ( w a ) ⊆ { u ∈ R n : u T ( v − w a ) ≥ 0 } c a ∥ c a ∥ \frac{c_a}{\lVert c_a\rVert} ∥ c a ∥ c a u T ( v − w a ) = 0 u^{\mathsf T}(v-w_a)=0 u T ( v − w a ) = 0
0 < ϕ ( x ) ≤ arcsin ( c a T ( v − w a ) ∥ c a ∥ ∥ v − w a ∥ ) ≤ π 2 . 0 < \phi(x) \le\arcsin\left(\frac{c_a^{\mathsf T}(v-w_a)}{\lVert c_a\rVert\lVert v-w_a\rVert}\right) \le\frac{\pi}{2}. 0 < ϕ ( x ) ≤ arcsin ( ∥ c a ∥ ∥ v − w a ∥ c a T ( v − w a ) ) ≤ 2 π . This implies
c a T ( v − w a ) ≥ ∥ c a ∥ ∥ v − w a ∥ sin ( ϕ ( x ) ) ≥ ∥ c a ∥ ℓ e sin ( ϕ ( x ) ) . c_a^{\mathsf T}(v-w_a) \ge\lVert c_a\rVert\lVert v-w_a\rVert\sin(\phi(x)) \ge\lVert c_a\rVert\ell_e\sin(\phi(x)). c a T ( v − w a ) ≥ ∥ c a ∥ ∥ v − w a ∥ sin ( ϕ ( x )) ≥ ∥ c a ∥ ℓ e sin ( ϕ ( x )) . Therefore, we conclude that c a T ( w ~ ( x ) − w a ) < ∥ c a ∥ ℓ e sin ( ϕ ( x ) ) c_a^{\mathsf T}(\widetilde{w}(x)-w_a) < \lVert c_a\rVert\ell_e\sin(\phi(x)) c a T ( w ( x ) − w a ) < ∥ c a ∥ ℓ e sin ( ϕ ( x )) w ~ ( x ) = w a ∈ W ⋆ ( c a ) \widetilde{w}(x)=w_a \in W^\star(c_a) w ( x ) = w a ∈ W ⋆ ( c a )
For the expected bound, the cache can equivalently be generated by assigning an independent uniformly chosen member to every possible candidate set before queries begin. For each fixed x x x W ϵ ( x ) W_\epsilon(x) W ϵ ( x ) w ⋆ ( P D M x ) w^\star(P^{DM}x) w ⋆ ( P D M x )
P { w ~ ( x ) ≠ w ⋆ ( P D M x ) } = 1 − 1 ∣ W ϵ ( x ) ∣ . \mathbb{P}\{\widetilde{w}(x) \ne w^\star(P^{DM}x)\} = 1 - \frac{1}{\lvert W_\epsilon(x)\rvert}. P { w ( x ) = w ⋆ ( P D M x )} = 1 − ∣ W ϵ ( x )∣ 1 . Under the stated assumption, the pointwise bound is at least ψ ( x ) \psi(x) ψ ( x ) x ∼ Q x \sim Q x ∼ Q
E [ L pred ( P a , P D M ; x ) ] ≥ E x ∼ Q [ ψ ( x ) ( 1 − 1 ∣ W ϵ ( x ) ∣ ) ] = B ϵ ( Q ) . \mathbb{E}[L_{\operatorname{pred}}(P^a,P^{DM};x)] \ge\mathbb{E}_{x\sim Q}\left[\psi(x)\left(1-\frac{1}{\lvert W_\epsilon(x)\rvert}\right)\right] = B_\epsilon(Q). E [ L pred ( P a , P D M ; x )] ≥ E x ∼ Q [ ψ ( x ) ( 1 − ∣ W ϵ ( x )∣ 1 ) ] = B ϵ ( Q ) . Finally, W ϵ ( x ) W_\epsilon(x) W ϵ ( x ) ϵ \epsilon ϵ ϵ = 0 \epsilon=0 ϵ = 0 ψ ( x ) ≥ 0 \psi(x) \ge0 ψ ( x ) ≥ 0 ϵ \epsilon ϵ B ϵ ( Q ) B_\epsilon(Q) B ϵ ( Q ) ϵ \epsilon ϵ
Proof of Proposition A.1. Fix a full-row-rank matrix P a P^{a} P a P ∈ P c ( P a ) P \in\mathcal{P}_{c}(P^{a}) P ∈ P c ( P a ) i i i x i ∈ R d x_i \in\mathbb{R}^{d} x i ∈ R d P a x i = r i P^{a}x_i = r_i P a x i = r i z ∈ ker ( P a ) z \in\ker(P^{a}) z ∈ ker ( P a ) P a ( x i + z ) = r i P^{a}(x_i+z)=r_i P a ( x i + z ) = r i P x i P x_i P x i P ( x i + z ) ∈ span ( r i ) P(x_i+z) \in\operatorname{span}(r_i) P ( x i + z ) ∈ span ( r i ) P z ∈ span ( r i ) Pz \in\operatorname{span}(r_i) P z ∈ span ( r i ) P z = 0 Pz=0 P z = 0 ker ( P a ) ⊆ ker ( P ) \ker(P^{a}) \subseteq\ker(P) ker ( P a ) ⊆ ker ( P ) P a P^{a} P a P = B P a P=BP^{a} P = B P a B : R n → R n B:\mathbb{R}^{n}\to\mathbb{R}^{n} B : R n → R n
For each i i i B r i = P x i ∈ span ( r i ) Br_i=Px_i\in\operatorname{span}(r_i) B r i = P x i ∈ span ( r i ) B a i = λ i a i Ba_i=\lambda_i a_i B a i = λ i a i λ i ∈ R \lambda_i\in\mathbb{R} λ i ∈ R B B B ∑ j = 1 n β j ( λ k j − λ k n + 1 ) a k j = 0 \sum_{j=1}^{n}\beta_j(\lambda_{k_j}-\lambda_{k_{n+1}})a_{k_j}=0 ∑ j = 1 n β j ( λ k j − λ k n + 1 ) a k j = 0 β j ≠ 0 \beta_j\ne0 β j = 0 λ k j = λ k n + 1 \lambda_{k_j}=\lambda_{k_{n+1}} λ k j = λ k n + 1 j = 1 , … , n j=1,\ldots,n j = 1 , … , n B = γ I n B=\gamma I_n B = γ I n P = γ P a P=\gamma P^{a} P = γ P a γ ∈ R \gamma\in\mathbb{R} γ ∈ R P a P^{a} P a P c ( P a ) = span { P a } \mathcal{P}_{c}(P^{a})=\operatorname{span}\{P^{a}\} P c ( P a ) = span { P a }
Proof of Corollary A.2. Suppose that P a ≠ 0 P^{a}\ne0 P a = 0 w ⋆ ( P D M x ) ∈ W ⋆ ( P a x ) w^{\star}(P^{DM}x)\in W^{\star}(P^{a}x) w ⋆ ( P D M x ) ∈ W ⋆ ( P a x ) x ∉ ker ( P D M ) x\notin\ker(P^{DM}) x ∈ / ker ( P D M ) B : R n → R n B:\mathbb{R}^{n}\to\mathbb{R}^{n} B : R n → R n P a = B P D M P^{a}=BP^{DM} P a = B P D M B r i ∈ { α r i : α ≥ 0 } Br_i\in\{\alpha r_i:\alpha\ge0\} B r i ∈ { α r i : α ≥ 0 } i i i P a x ˉ ∈ span ( r i ) P^{a}\bar{x}\in\operatorname{span}(r_i) P a x ˉ ∈ span ( r i ) P D M x ˉ = r i P^{DM}\bar{x}=r_i P D M x ˉ = r i P a ∈ P c ( P D M ) P^{a}\in\mathcal{P}_{c}(P^{DM}) P a ∈ P c ( P D M ) P a = γ P D M P^{a}=\gamma P^{DM} P a = γ P D M γ ∈ R \gamma\in\mathbb{R} γ ∈ R x ˉ \bar{x} x ˉ P D M x ˉ = r i P^{DM}\bar{x}=r_i P D M x ˉ = r i γ r i = P a x ˉ = B r i ∈ { α r i : α ≥ 0 } \gamma r_i=P^{a}\bar{x}=Br_i\in\{\alpha r_i:\alpha\ge0\} γ r i = P a x ˉ = B r i ∈ { α r i : α ≥ 0 } P a ≠ 0 P^{a}\ne0 P a = 0 γ > 0 \gamma>0 γ > 0
Lemma B.2. For each p ≥ 1 p\ge1 p ≥ 1 U p ∈ R n × d U_p\in\mathbb{R}^{n\times d} U p ∈ R n × d M p ≥ 1 M_p\ge1 M p ≥ 1 Δ p > 0 \Delta_p>0 Δ p > 0 ∥ U p ∥ F = 1 \lVert U_p\rVert_F=1 ∥ U p ∥ F = 1 J ⊆ { 1 , … , m } J\subseteq\{1,\ldots,m\} J ⊆ { 1 , … , m } i ∈ J i\in J i ∈ J x ˉ i 0 j , p \bar{x}_{i0j,p} x ˉ i 0 j , p x ~ i k j , p \tilde{x}_{ikj,p} x ~ ik j , p j = 1 , … , d − n + 1 j=1,\ldots,d-n+1 j = 1 , … , d − n + 1 k ∈ C i k\in C_i k ∈ C i U p x ˉ i 0 j , p = r i U_p\bar{x}_{i0j,p}=r_i U p x ˉ i 0 j , p = r i J J J R > 0 R>0 R > 0 M p → + ∞ M_p\to+\infty M p → + ∞ Δ p ( M p + K − 1 ) < η S \Delta_p(M_p+K-1)<\eta_S Δ p ( M p + K − 1 ) < η S p p p
inf α ≥ 0 ∥ P D M x ˉ i 0 j , p − α r i ∥ → 0 for all i ∈ J , j = 1 , … , d − n + 1 , \inf_{\alpha\ge0}\lVert P^{DM}\bar{x}_{i0j,p}-\alpha r_i\rVert\to0\quad\text{for all }i\in J,\ j=1,\ldots,d-n+1, α ≥ 0 inf ∥ P D M x ˉ i 0 j , p − α r i ∥ → 0 for all i ∈ J , j = 1 , … , d − n + 1 , where K K K η S \eta_S η S
Proof. Fix i ∈ J i\in J i ∈ J j ∈ { 1 , … , d − n + 1 } j\in\{1,\ldots,d-n+1\} j ∈ { 1 , … , d − n + 1 } k ∈ C i k\in C_i k ∈ C i p p p
( U p x ~ i k j , p ) ⊤ ( v − w k ) ≥ η S M p + K − 1 > Δ p for every v ∈ V ∖ { w k } . (U_p\tilde{x}_{ikj,p})^{\top}(v-w_k)\ge\frac{\eta_S}{M_p+K-1}>\Delta_p\quad\text{for every }v\in V\setminus\{w_k\}. ( U p x ~ ik j , p ) ⊤ ( v − w k ) ≥ M p + K − 1 η S > Δ p for every v ∈ V ∖ { w k } . Since this query is retained in the dataset on which U p U_p U p w k w_k w k P D M x ~ i k j , p ∈ C k P^{DM}\tilde{x}_{ikj,p}\in C_k P D M x ~ ik j , p ∈ C k M p > K − 1 M_p>K-1 M p > K − 1
∥ x ~ i k j , p − x ˉ i 0 j , p ∥ ≤ 2 R ( K − 1 ) M p − ( K − 1 ) → 0 , \lVert\tilde{x}_{ikj,p}-\bar{x}_{i0j,p}\rVert\le\frac{2R(K-1)}{M_p-(K-1)}\to0, ∥ x ~ ik j , p − x ˉ i 0 j , p ∥ ≤ M p − ( K − 1 ) 2 R ( K − 1 ) → 0 , which implies
∥ P D M x ~ i k j , p − P D M x ˉ i 0 j , p ∥ ≤ ∥ P D M ∥ F ∥ x ~ i k j , p − x ˉ i 0 j , p ∥ → 0. \lVert P^{DM}\tilde{x}_{ikj,p}-P^{DM}\bar{x}_{i0j,p}\rVert\le\lVert P^{DM}\rVert_F\lVert\tilde{x}_{ikj,p}-\bar{x}_{i0j,p}\rVert\to0. ∥ P D M x ~ ik j , p − P D M x ˉ i 0 j , p ∥ ≤ ∥ P D M ∥ F ∥ x ~ ik j , p − x ˉ i 0 j , p ∥ → 0. The sequence { P D M x ˉ i 0 j , p } p ≥ 1 \{P^{DM}\bar{x}_{i0j,p}\}_{p\ge1} { P D M x ˉ i 0 j , p } p ≥ 1 C k C_k C k ⋂ k ∈ C i C k = { α r i : α ≥ 0 } \bigcap_{k\in C_i}C_k=\{\alpha r_i:\alpha\ge0\} ⋂ k ∈ C i C k = { α r i : α ≥ 0 } inf α ≥ 0 ∥ P D M x ˉ i 0 j , p − α r i ∥ \inf_{\alpha\ge0}\lVert P^{DM}\bar{x}_{i0j,p}-\alpha r_i\rVert inf α ≥ 0 ∥ P D M x ˉ i 0 j , p − α r i ∥
Lemma B.3. Let J ⊆ { 1 , … , m } J\subseteq\{1,\ldots,m\} J ⊆ { 1 , … , m } { a i : i ∈ J } \{a_i:i\in J\} { a i : i ∈ J } n + 1 n+1 n + 1 { U p } p ≥ 1 ⊆ R n × d \{U_p\}_{p\ge1}\subseteq\mathbb{R}^{n\times d} { U p } p ≥ 1 ⊆ R n × d ∥ U p ∥ F = 1 \lVert U_p\rVert_F=1 ∥ U p ∥ F = 1 i ∈ J i\in J i ∈ J p ≥ 1 p\ge1 p ≥ 1 x ˉ i 0 j , p ∈ R d \bar{x}_{i0j,p}\in\mathbb{R}^{d} x ˉ i 0 j , p ∈ R d U p x ˉ i 0 j , p = r i U_p\bar{x}_{i0j,p}=r_i U p x ˉ i 0 j , p = r i j = 1 , … , d − n + 1 j=1,\ldots,d-n+1 j = 1 , … , d − n + 1 X i , p = [ x ˉ i 0 , 1 , p , … , x ˉ i 0 , d − n + 1 , p ] X_{i,p}=[\bar{x}_{i0,1,p},\ldots,\bar{x}_{i0,d-n+1,p}] X i , p = [ x ˉ i 0 , 1 , p , … , x ˉ i 0 , d − n + 1 , p ] R , κ > 0 R,\kappa>0 R , κ > 0 p p p ∥ x ˉ i 0 j , p ∥ ≤ R \lVert\bar{x}_{i0j,p}\rVert\le R ∥ x ˉ i 0 j , p ∥ ≤ R σ min ( X i , p ) ≥ κ \sigma_{\min}(X_{i,p})\ge\kappa σ m i n ( X i , p ) ≥ κ i ∈ J i\in J i ∈ J j j j σ min \sigma_{\min} σ m i n d − n + 1 d-n+1 d − n + 1 inf α ≥ 0 ∥ P D M x ˉ i 0 j , p − α r i ∥ → 0 \inf_{\alpha\ge0}\lVert P^{DM}\bar{x}_{i0j,p}-\alpha r_i\rVert\to0 inf α ≥ 0 ∥ P D M x ˉ i 0 j , p − α r i ∥ → 0 i ∈ J i\in J i ∈ J j = 1 , … , d − n + 1 j=1,\ldots,d-n+1 j = 1 , … , d − n + 1 U p → P D M ∥ P D M ∥ F U_p\to\frac{P^{DM}}{\lVert P^{DM}\rVert_F} U p → ∥ P D M ∥ F P D M ( U p x , P D M x ) → 0 (U_px,P^{DM}x)\to0 ( U p x , P D M x ) → 0 x ∉ ker ( P D M ) x\notin\ker(P^{DM}) x ∈ / ker ( P D M )
Proof. Since ∥ U p ∥ F = 1 \lVert U_p\rVert_F=1 ∥ U p ∥ F = 1 U p → U ⋆ U_p\to U_{\star} U p → U ⋆ x ˉ i 0 j , p → x ˉ i 0 j , ⋆ \bar{x}_{i0j,p}\to\bar{x}_{i0j,\star} x ˉ i 0 j , p → x ˉ i 0 j , ⋆ i ∈ J i\in J i ∈ J j = 1 , … , d − n + 1 j=1,\ldots,d-n+1 j = 1 , … , d − n + 1
We define X i , ⋆ = [ x ˉ i 01 , ⋆ , … , x ˉ i 0 , d − n + 1 , ⋆ ] X_{i,\star}=[\bar{x}_{i01,\star},\ldots,\bar{x}_{i0,d-n+1,\star}] X i , ⋆ = [ x ˉ i 01 , ⋆ , … , x ˉ i 0 , d − n + 1 , ⋆ ] X i , p → X i , ⋆ X_{i,p}\to X_{i,\star} X i , p → X i , ⋆ ∥ U ⋆ ∥ F = 1 \lVert U_{\star}\rVert_F=1 ∥ U ⋆ ∥ F = 1 U ⋆ x ˉ i 0 j , ⋆ = r i U_{\star}\bar{x}_{i0j,\star}=r_i U ⋆ x ˉ i 0 j , ⋆ = r i σ min ( X i , ⋆ ) ≥ κ \sigma_{\min}(X_{i,\star})\ge\kappa σ m i n ( X i , ⋆ ) ≥ κ U ⋆ U_{\star} U ⋆ r i r_i r i n n n U ⋆ U_{\star} U ⋆
row rank. For each i ∈ J i \in J i ∈ J X i , ⋆ X_{i,\star} X i , ⋆ ( d − n + 1 ) (d-n+1) ( d − n + 1 ) { x ∈ R d : U ⋆ x ∈ span ( r i ) } \{x \in\mathbb{R}^{d}: U_{\star}x \in\operatorname{span}(r_i)\} { x ∈ R d : U ⋆ x ∈ span ( r i )} d − n + 1 d-n+1 d − n + 1 P D M x ˉ i 0 j , ⋆ ∈ { α r i : α ≥ 0 } P^{DM}\bar{x}_{i0j,\star} \in\{\alpha r_i:\alpha\ge0\} P D M x ˉ i 0 j , ⋆ ∈ { α r i : α ≥ 0 } P D M x ∈ span ( r i ) P^{DM}x \in\operatorname{span}(r_i) P D M x ∈ span ( r i ) U ⋆ x ∈ span ( r i ) U_{\star}x \in\operatorname{span}(r_i) U ⋆ x ∈ span ( r i ) U ⋆ x = r i U_{\star}x=r_i U ⋆ x = r i
Since J J J n + 1 n+1 n + 1 i ∈ J i \in J i ∈ J P D M = γ U ⋆ P^{DM}=\gamma U_{\star} P D M = γ U ⋆ γ ∈ R \gamma\in\mathbb{R} γ ∈ R γ r i = P D M x ˉ i 0 j , ⋆ ∈ { α r i : α ≥ 0 } \gamma r_i=P^{DM}\bar{x}_{i0j,\star} \in\{\alpha r_i:\alpha\ge0\} γ r i = P D M x ˉ i 0 j , ⋆ ∈ { α r i : α ≥ 0 } P D M ≠ 0 P^{DM}\ne0 P D M = 0 γ > 0 \gamma>0 γ > 0 γ = ∥ P D M ∥ F \gamma=\lVert P^{DM}\rVert_F γ = ∥ P D M ∥ F U ⋆ = P D M ∥ P D M ∥ F U_{\star}=\frac{P^{DM}}{\lVert P^{DM}\rVert_F} U ⋆ = ∥ P D M ∥ F P D M x ∉ ker ( P D M ) x \notin\ker(P^{DM}) x ∈ / ker ( P D M ) U p x → P D M x ∥ P D M ∥ F ≠ 0 U_p x \to\frac{P^{DM}x}{\lVert P^{DM}\rVert_F}\ne0 U p x → ∥ P D M ∥ F P D M x = 0
Proof of Theorem A.3. Under the stated assumptions, Proposition 3.7 guarantees that every run terminates after at most ( 1 + 2 R L e Δ ) n d \left(1+\frac{2RLe}{\Delta}\right)^n d ( 1 + Δ 2 R L e ) n d Δ p → 0 \Delta_p \to0 Δ p → 0 M p = M ( Δ p ) M_p=M(\Delta_p) M p = M ( Δ p ) U p = P M p , Δ p a U_p=P^a_{M_p,\Delta_p} U p = P M p , Δ p a p p p x ˉ i 0 j , p \bar{x}_{i0j,p} x ˉ i 0 j , p U p U_p U p X i , p = [ x ˉ i 01 , p , … , x ˉ i 0 , d − n + 1 , p ] X_{i,p}=[\bar{x}_{i01,p},\ldots,\bar{x}_{i0,d-n+1,p}] X i , p = [ x ˉ i 01 , p , … , x ˉ i 0 , d − n + 1 , p ] R R R M p → + ∞ M_p \to+\infty M p → + ∞ p p p J = { 1 , … , m } J=\{1,\ldots,m\} J = { 1 , … , m }
inf α ≥ 0 ∥ P D M x ˉ i 0 j , p − α r i ∥ → 0 for all i = 1 , … , m , j = 1 , … , d − n + 1. \inf_{\alpha\ge0}\left\lVert P^{DM}\bar{x}_{i0j,p}-\alpha r_i\right\rVert\to0 \quad\text{for all } i=1,\ldots,m,\ j=1,\ldots,d-n+1. α ≥ 0 inf P D M x ˉ i 0 j , p − α r i → 0 for all i = 1 , … , m , j = 1 , … , d − n + 1. The bound σ min ( X i , p ) ≥ κ \sigma_{\min}(X_{i,p})\ge\kappa σ m i n ( X i , p ) ≥ κ P M p , Δ p a → P D M ∥ P D M ∥ F P^a_{M_p,\Delta_p}\to\frac{P^{DM}}{\lVert P^{DM}\rVert_F} P M p , Δ p a → ∥ P D M ∥ F P D M Δ p → 0 \Delta_p\to0 Δ p → 0 x ∉ ker ( P D M ) x\notin\ker(P^{DM}) x ∈ / ker ( P D M ) L p r e d ( P M ( Δ ) , Δ a , P D M ; x ) → 0 L_{\mathrm{pred}}(P^a_{M(\Delta),\Delta},P^{DM};x)\to0 L pred ( P M ( Δ ) , Δ a , P D M ; x ) → 0
Proof of Lemma A.4. Suppose that P a ≠ 0 P^a\ne0 P a = 0 X ∖ ker ( P D M ) \mathcal{X}\setminus\ker(P^{DM}) X ∖ ker ( P D M ) i ∈ J i\in J i ∈ J x ˉ i ∈ int ( X ) \bar{x}_i\in\operatorname{int}(\mathcal{X}) x ˉ i ∈ int ( X ) α i > 0 \alpha_i>0 α i > 0 P D M x ˉ i = α i r i P^{DM}\bar{x}_i=\alpha_i r_i P D M x ˉ i = α i r i i ∈ J i\in J i ∈ J x ∈ int ( X ) x\in\operatorname{int}(\mathcal{X}) x ∈ int ( X ) P D M x = α r i P^{DM}x=\alpha r_i P D M x = α r i k ∈ C i k\in C_i k ∈ C i h k ∈ R d h_k\in\mathbb{R}^d h k ∈ R d P D M h k ∈ int ( C k ) P^{DM}h_k\in\operatorname{int}(C_k) P D M h k ∈ int ( C k ) P D M P^{DM} P D M t > 0 t>0 t > 0 x + t h k ∈ X x+th_k\in\mathcal{X} x + t h k ∈ X P D M ( x + t h k ) = α r i + t P D M h k ∈ int ( C k ) P^{DM}(x+th_k)=\alpha r_i+tP^{DM}h_k\in\operatorname{int}(C_k) P D M ( x + t h k ) = α r i + t P D M h k ∈ int ( C k ) P a ( x + t h k ) ∈ C k P^a(x+th_k)\in C_k P a ( x + t h k ) ∈ C k t ↓ 0 t\downarrow0 t ↓ 0 P a x ∈ ⋂ k ∈ C i C k = { α r i : α ≥ 0 } P^a x\in\bigcap_{k\in C_i}C_k=\{\alpha r_i:\alpha\ge0\} P a x ∈ ⋂ k ∈ C i C k = { α r i : α ≥ 0 }
We fix z ∈ ker ( P D M ) z\in\ker(P^{DM}) z ∈ ker ( P D M ) i ∈ J i\in J i ∈ J t t t x ˉ i \bar{x}_i x ˉ i x ˉ i + t z \bar{x}_i+tz x ˉ i + t z int ( X ) \operatorname{int}(\mathcal{X}) int ( X ) α i r i \alpha_i r_i α i r i P a x ˉ i , P a ( x ˉ i + t z ) ∈ { α r i : α ≥ 0 } P^a\bar{x}_i,P^a(\bar{x}_i+tz)\in\{\alpha r_i:\alpha\ge0\} P a x ˉ i , P a ( x ˉ i + t z ) ∈ { α r i : α ≥ 0 } P a z ∈ span ( r i ) P^a z\in\operatorname{span}(r_i) P a z ∈ span ( r i ) P a z = 0 P^a z=0 P a z = 0 ker ( P D M ) ⊆ ker ( P a ) \ker(P^{DM})\subseteq\ker(P^a) ker ( P D M ) ⊆ ker ( P a ) P a = B P D M P^a=BP^{DM} P a = B P D M B : R n → R n B:\mathbb{R}^n\to\mathbb{R}^n B : R n → R n x ˉ i \bar{x}_i x ˉ i α i B r i = P a x ˉ i ∈ { α r i : α ≥ 0 } \alpha_iBr_i=P^a\bar{x}_i\in\{\alpha r_i:\alpha\ge0\} α i B r i = P a x ˉ i ∈ { α r i : α ≥ 0 } B r i = λ i r i Br_i=\lambda_i r_i B r i = λ i r i λ i ≥ 0 \lambda_i\ge0 λ i ≥ 0 i ∈ J i\in J i ∈ J n + 1 n+1 n + 1 B = γ I n B=\gamma I_n B = γ I n γ ≥ 0 \gamma\ge0 γ ≥ 0 P a ≠ 0 P^a\ne0 P a = 0 γ > 0 \gamma>0 γ > 0 P a = γ P D M P^a=\gamma P^{DM} P a = γ P D M
Proof of Lemma A.5. Under the stated assumptions, Proposition 3.7 guarantees that every run terminates after at most ( 1 + 2 R L e Δ ) n d \left(1+\frac{2RLe}{\Delta}\right)^n d ( 1 + Δ 2 R L e ) n d Δ p → 0 \Delta_p\to0 Δ p → 0 M p = M ( Δ p ) M_p=M(\Delta_p) M p = M ( Δ p ) U p = P M p , Δ p a U_p=P^a_{M_p,\Delta_p} U p = P M p , Δ p a p p p x ˉ i 0 j , p \bar{x}_{i0j,p} x ˉ i 0 j , p U p U_p U p X i , p = [ x ˉ i 01 , p , … , x ˉ i 0 , d − n + 1 , p ] X_{i,p}=[\bar{x}_{i01,p},\ldots,\bar{x}_{i0,d-n+1,p}] X i , p = [ x ˉ i 01 , p , … , x ˉ i 0 , d − n + 1 , p ] i ∈ J i\in J i ∈ J i ∈ J i\in J i ∈ J J J J R R R
inf α ≥ 0 ∥ P D M x ˉ i 0 j , p − α r i ∥ → 0 for all i ∈ J , j = 1 , … , d − n + 1. \inf_{\alpha\ge0}\left\lVert P^{DM}\bar{x}_{i0j,p}-\alpha r_i\right\rVert\to0 \quad\text{for all } i\in J,\ j=1,\ldots,d-n+1. α ≥ 0 inf P D M x ˉ i 0 j , p − α r i → 0 for all i ∈ J , j = 1 , … , d − n + 1. The selected facets contain n + 1 n+1 n + 1 σ min ( X i , p ) ≥ κ \sigma_{\min}(X_{i,p})\ge\kappa σ m i n ( X i , p ) ≥ κ i ∈ J i\in J i ∈ J U p → P D M ∥ P D M ∥ F U_p\to\frac{P^{DM}}{\lVert P^{DM}\rVert_F} U p → ∥ P D M ∥ F P D M Δ p → 0 \Delta_p\to0 Δ p → 0 x ∉ ker ( P D M ) x\notin\ker(P^{DM}) x ∈ / ker ( P D M ) L p r e d ( P M ( Δ ) , Δ a , P D M ; x ) → 0 L_{\mathrm{pred}}(P^a_{M(\Delta),\Delta},P^{DM};x)\to0 L pred ( P M ( Δ ) , Δ a , P D M ; x ) → 0
