Observe that like for the \(R^2\)  objective, our upper bound for \(\beta \)  is the the inverse of the lower bound for \(\gamma \) .

The lower bound on \(\gamma \)  is shown is [1]}. It remains to prove the upper bound on \(\beta \) .
Let \(B\)  be some set of observations and \(A \subseteq B\)  with \(k = |A|\)  and for convenience, define \(T = B\setminus A\) .
By the matrix inversion lemma REF , we have
\(F(B) - F(A)& = \operatornamewithlimits{\mathrm {tr}}( M_A^{-1}) - \operatornamewithlimits{\mathrm {tr}}(M_{B}^{-1}) \\& = \operatornamewithlimits{\mathrm {tr}}\bigl ( (M_{B} - \sigma ^{-2} X_T X_T^T)^{-1}\bigr ) - \operatornamewithlimits{\mathrm {tr}}( M_{B}^{-1}) \\& = \operatornamewithlimits{\mathrm {tr}}\bigl (M_{B}^{-1} + M_{B}^{-1}X_T(\sigma ^2 I - X_T^T M_{B}^{-1} X_T)^{-1}X_T^T M_{B}^{-1}\bigr ) - \operatornamewithlimits{\mathrm {tr}}(M_{B}^{-1}) \\& = \operatornamewithlimits{\mathrm {tr}}\bigl (M_{B}^{-1}X_T(\sigma ^2 I - X_T^T M_{B}^{-1} X_T)^{-1}X_T^T M_{B}^{-1}\bigr ) \\& = \operatornamewithlimits{\mathrm {tr}}\bigl ((\sigma ^2 I - X_T^T M_{B}^{-1} X_T)^{-1}X_T^T M_{B}^{-2}X_T\bigr ).\) 
