When Determinants Are Not Enough: Private Rare Switching

Xingyu Zhou · 2026

Read When Determinants Are Not Enough: Private Rare Switching by Xingyu Zhou (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-23131.txt.

Introduction

Zhou shares a small research note on adapting rare switching to the private setting for linear bandits and reinforcement learning. The standard determinant based update rule works because the design matrix grows monotonically. Once Gaussian noise is added for privacy, that monotonicity can fail, since determinant growth controls volume while regret analysis requires control of the worst direction. A new rule based on the generalized Rayleigh quotient restores logarithmic policy updates and the wanted confidence width check up to a constant factor.

Catalog record

CREATORXingyu Zhou
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE12942
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.23131

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

When Determinants Are Not Enough: Private Rare Switching Xingyu Zhou Abstract In this note, I would like to share a small research moment where Codex helped me find the right way to adapt rare switching to the private setting. The standard determinant-based update rule in linear bandits and RL works beautifully because the design matrix grows monotonically. But once Gaussian noise is added for privacy, this monotonicity can fail, and the usual analysis no longer goes through. The key reason is that determinant growth controls volume, while regret analysis needs control of the worst direction. To address this, Codex comes up with a different rare-switching rule based on the generalized Rayleigh quotient, which restores logarithmic policy updates and the desired confidence-width comparison up to a constant factor. I present my manually clean-up version of the proof here as well as some personal reflection on this example. 1 The Problem The problem is a variant of the standard rare switching policy update in linear bandit and RL. Let us first recall the standard setting, i.e., Sec. 5.1 in [ APS11 ] . The learner maintains a positive-definite covariance matrix V_{t}=\lambda I+\sum_{s=1}^{t}x_{s}x_{s}^{\top} for t\in[T],\lambda>0 and only updates its policy when \det(V_{t})>\alpha\det(V_{\tau}) for some \alpha>1 with \tau being the latest update time slot before t . This simple rule is often called rare-switching update which can (i) reduce the number of total policy updates to O(\log T) (which directly follows from the standard elliptical potential lemma, Lemma 11 in [ APS11 ] ) while (ii) only suffers a constant factor blow up in regret (which directly follows from Lemma 12 in [ APS11 ] ). In particular, Lemma 12 in [ APS11 ] implies that if V_{t}\succeq V_{\tau} , then we have for any x\in\mathbb{R}^{d} , we have \left\lVert x\right\rVert_{V_{\tau}^{-1}}\leq\sqrt{\alpha}\left\lVert x\right\rVert_{V_{t}^{-1}} . Now, what if the covariance matrix is perturbed, say, due to privacy protection. For example, in private linear contextual bandits or linear RL, Gaussian noisy matrix is often added to the non-private to arrive at the private one: \widetilde{V}_{t}=V_{t}+E_{t} , where E_{t} is symmetric matrix with elements sampled from Gaussian. A natural question to ask is: Can we still apply the above update rule (on \widetilde{V_{t}} ) along with its analysis to arrive at the same performance, i.e., log-order updates with the same-order of regret? The answer is no. The reason is that to apply Lemma 12, we have to guarantee the monotonicity property, which is \widetilde{V}_{t}\succeq\widetilde{V}_{\tau} . This is no longer true due to the private noise. This issue has been pointed by my previous work [ CZ22 ] (cf. Sec. 6) and also by my most recent work [ HZ26 ] (cf. Appendix C). A similar issue but in a different context was also identified in my previous work [ ZR24 ] (cf. Appendix C.3). So, we may ask: how about a new rare-switching rule for the private case 1 1 1 Of course, one may ask if we can keep the same update rule but with a more advanced analysis to maintain the same performance guarantees. It turns out that this is not possible, which will become clear at the end of this post. ? 2 The New Rule I basically present the above write-up as a prompt to Codex 5.5 (Extra High) with all related papers in the folder. The first attempt of Codex gives me the correct answer, which is summarized in the following theorem 2 2 2 I clean up and re-organize the original proof of Codex, which is correct but not that easy to read. . Theorem 2.1 . Let x_{1},\ldots,x_{T}\in\mathbb{R}^{d} satisfy \left\lVert x_{t}\right\rVert_{2}\leq L for all t\in[T] . Let the non-private design matrices be \displaystyle V_{1}:=\lambda I,V_{t+1}:=V_{t}+x_{t}x_{t}^{\top}. Assume the private matrices be \widetilde{V}_{t}=V_{t}+E_{t} where E_{t} is a symmetric matrix such that for all t\in[T] 3 3 3 For Gaussian matrix, this condition holds with high probability \displaystyle\left\lVert E_{t}\right\rVert_{2}\leq\eta\text{ and }0\leq 2\eta\leq\lambda. Suppose that the update rule is that for any t\in[T] , it updates the policy when \displaystyle\lambda_{\max}\left(\widetilde{V}_{\tau_{t}}^{-1/2}\widetilde{V}_{t}\widetilde{V}_{\tau_{t}}^{-1/2}\right)>\alpha, where \tau_{t} is again the most recent update before t . Then, let \rho:=\eta/\lambda and c_{\rho}:=\frac{1+\rho}{1-\rho} , we have (i) For any x\in\mathbb{R}^{d} and t\in[T] , \left\lVert x\right\rVert_{\widetilde{V}_{\tau_{t}}^{-1}}\leq\sqrt{\alpha}\left\lVert x\right\rVert_{\widetilde{V}_{t}^{-1}} and \left\lVert x\right\rVert_{V_{\tau_{t}}^{-1}}\leq\sqrt{c_{\rho}\alpha}\left\lVert x\right\rVert_{V_{t}^{-1}} ; (ii) The total number of updates m is upper bounded by m\lesssim d\log_{\alpha/c_{\rho}}\left(1+\frac{TL^{2}}{\lambda d}\right)=O_{d}(\log T) . Remark 2.2 . Several remarks are in order. First, in most cases, \lambda is set to be 2\eta so that the private design matrix is also positive definite, see the proof of Lemma A.4 in [ CZ22 ] . Hence, \rho=1/2 and c_{\rho}=3 . Now, with the above update rule and guarantees, we have the right way to do rare switching in private linear bandit and RL. Second, note that we often only needs the first inequality in (i) to bound the regret. Finally, we also note that the new update rule is also equivalent to that the learner updates iff \widetilde{V}_{t}\npreceq\alpha\widetilde{V}_{\tau_{t}} , which is more expensive in computation compared with the old determinant-based update rule (which can leverage the efficient rank-one update). Proof. We first present the following claim, which will be useful for the proof with the proof being given at the end. Claim 2.3 . For 1\leq a\leq b\leq T , let g_{a,b}:=\lambda_{\max}\left({V}_{a}^{-1/2}{V}_{b}{V}_{a}^{-1/2}\right) and \widetilde{g}_{a,b}:=\lambda_{\max}\left(\widetilde{V}_{a}^{-1/2}\widetilde{V}_{b}\widetilde{V}_{a}^{-1/2}\right) . Then, we have c_{\rho}^{-1}g_{a,b}\leq\widetilde{g}_{a,b}\leq c_{\rho}g_{a,b}. We start with (i). For any \tau_{t}<t , i.e., t is not the update slot, the first inequality follows directly from the update rule. For the second one, by Claim 2.3 and our update rule, we first have \displaystyle\lambda_{\max}\left({V}_{\tau_{t}}^{-1/2}{V}_{t}{V}_{\tau_{t}}^{-1/2}\right)\leq c_{\rho}\alpha. Further, by the identity of generalized Rayleigh quotient, we have \displaystyle\sup_{x\neq 0}\frac{x^{\top}V_{t}x}{x^{\top}V_{\tau_{t}}x}=\lambda_{\max}\left({V}_{\tau_{t}}^{-1/2}{V}_{t}{V}_{\tau_{t}}^{-1/2}\right)\leq c_{\rho}\alpha. This implies that V_{\tau_{t}}^{-1}\preceq c_{\rho}\alpha V_{t}^{-1} , and hence \left\lVert x\right\rVert_{V_{\tau_{t}}^{-1}}\leq\sqrt{c_{\rho}\alpha}\left\lVert x\right\rVert_{V_{t}^{-1}} . We now move to (ii). Consider two adjacent policy update slots i<j . By the update rule and Claim 2.3 , we have \displaystyle\lambda_{\max}\left({V}_{i}^{-1/2}{V}_{j}{V}_{i}^{-1/2}\right)>\alpha/c_{\rho}. Further, since V_{j}\succeq V_{i} , all eigenvalues of {V}_{i}^{-1/2}{V}_{j}{V}_{i}^{-1/2} are least one. Hence, by the above result and multiplicativity of determinant, we have \displaystyle\frac{\det(V_{j})}{\det(V_{i})}=\det\left({V}_{i}^{-1/2}{V}_{j}{V}_{i}^{-1/2}\right)>\alpha/c_{\rho}. Thus, by the elliptical potential lemma (cf. Lemma 11 in [ APS11 ] ), we have that the total number of updates m is upper bounded by m\lesssim d\log_{\alpha/c_{\rho}}\left(1+\frac{TL^{2}}{\lambda d}\right) . We are left with the proof of Claim 2.3 . To show it, we first notice that by the condition on E_{t} , we have \displaystyle-\eta I\preceq E_{t}\preceq\eta I. Further, by V_{t}\succeq\lambda I , hence \eta I\preceq(\eta/\lambda)V_{t}=\rho V_{t} . Combing the above, yields that \displaystyle(1-\rho)V_{t}\preceq\widetilde{V_{t}}\preceq(1+\rho)V_{t}. Thus, for any nonzero vector x\in\mathbb{R}^{d} , we have \displaystyle\frac{x^{\top}\widetilde{V}_{b}x}{x^{\top}\widetilde{V}_{a}x}\leq\frac{(1+\rho)x^{\top}{V}_{b}x}{(1-\rho)x^{\top}{V}_{a}x}=c_{\rho}\frac{x^{\top}{V}_{b}x}{x^{\top}{V}_{a}x}. Taking sup and applying identity of generalized Rayleigh quotient, yields that \widetilde{g}_{a,b}\leq c_{\rho}g_{a,b} . The other direction follows the same proof. ∎ 3 The Connection One may wonder what’s the difference or connection between the new update rule and the standard one. To see this, it is instructive to see the behavior of the new update rule even in the non-private case and ask whether it leads to a more frequent or less frequent update. To this end, I directly prompt Codex (also with ChatGPT) with the the screenshot of Lemma 12 in [ APS11 ] . It then gives me a new proof which actually sheds a lot of light on how Codex comes up with the new update rule

Read the complete text