When Determinants Are Not Enough: Private Rare Switching

# When Determinants Are Not Enough: Private Rare Switching
Source: [https://arxiv.org/html/2605.23131](https://arxiv.org/html/2605.23131)
###### 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\.

## 1The 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](https://arxiv.org/html/2605.23131#bib.bibx1)\]\. The learner maintains a positive\-definite covariance matrixVt=λ​I\+∑s=1txs​xs⊤V\_\{t\}=\\lambda I\+\\sum\_\{s=1\}^\{t\}x\_\{s\}x\_\{s\}^\{\\top\}fort∈\[T\],λ\>0t\\in\[T\],\\lambda\>0and only updates its policy whendet\(Vt\)\>α​det\(Vτ\)\\det\(V\_\{t\}\)\>\\alpha\\det\(V\_\{\\tau\}\)for someα\>1\\alpha\>1withτ\\taubeing the latest update time slot beforett\. This simple rule is often called*rare\-switching update*which can \(i\) reduce the number of total policy updates toO​\(log⁡T\)O\(\\log T\)\(which directly follows from the standard elliptical potential lemma, Lemma 11 in\[[APS11](https://arxiv.org/html/2605.23131#bib.bibx1)\]\) while \(ii\) only suffers a constant factor blow up in regret \(which directly follows from Lemma 12 in\[[APS11](https://arxiv.org/html/2605.23131#bib.bibx1)\]\)\. In particular, Lemma 12 in\[[APS11](https://arxiv.org/html/2605.23131#bib.bibx1)\]implies that if*Vt⪰VτV\_\{t\}\\succeq V\_\{\\tau\}*, then we have for anyx∈ℝdx\\in\\mathbb\{R\}^\{d\}, we have‖x‖Vτ−1≤α​‖x‖Vt−1\\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:V~t=Vt\+Et\\widetilde\{V\}\_\{t\}=V\_\{t\}\+E\_\{t\}, whereEtE\_\{t\}is symmetric matrix with elements sampled from Gaussian\. A natural question to ask is: Can we still apply the above update rule \(onVt~\\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 isV~t⪰V~τ\\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](https://arxiv.org/html/2605.23131#bib.bibx2)\]\(cf\. Sec\. 6\) and also by my most recent work\[[HZ26](https://arxiv.org/html/2605.23131#bib.bibx3)\]\(cf\. Appendix C\)\. A similar issue but in a different context was also identified in my previous work\[[ZR24](https://arxiv.org/html/2605.23131#bib.bibx4)\]\(cf\. Appendix C\.3\)\.

So, we may ask:*how about a new rare\-switching rule for the private case*111Of 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\.?

## 2The 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 theorem222I clean up and re\-organize the original proof of Codex, which is correct but not that easy to read\.\.

###### Theorem 2\.1\.

Letx1,…,xT∈ℝdx\_\{1\},\\ldots,x\_\{T\}\\in\\mathbb\{R\}^\{d\}satisfy‖xt‖2≤L\\left\\lVert x\_\{t\}\\right\\rVert\_\{2\}\\leq Lfor allt∈\[T\]t\\in\[T\]\. Let the non\-private design matrices be

V1:=λ​I,Vt\+1:=Vt\+xt​xt⊤\.\\displaystyle V\_\{1\}:=\\lambda I,V\_\{t\+1\}:=V\_\{t\}\+x\_\{t\}x\_\{t\}^\{\\top\}\.Assume the private matrices beV~t=Vt\+Et\\widetilde\{V\}\_\{t\}=V\_\{t\}\+E\_\{t\}whereEtE\_\{t\}is a symmetric matrix such that for allt∈\[T\]t\\in\[T\]333For Gaussian matrix, this condition holds with high probability

‖Et‖2≤η​and​0≤2​η≤λ\.\\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 anyt∈\[T\]t\\in\[T\], it updates the policy when

λmax​\(V~τt−1/2​V~t​V~τt−1/2\)\>α,\\displaystyle\\lambda\_\{\\max\}\\left\(\\widetilde\{V\}\_\{\\tau\_\{t\}\}^\{\-1/2\}\\widetilde\{V\}\_\{t\}\\widetilde\{V\}\_\{\\tau\_\{t\}\}^\{\-1/2\}\\right\)\>\\alpha,whereτt\\tau\_\{t\}is again the most recent update beforett\.

Then, letρ:=η/λ\\rho:=\\eta/\\lambdaandcρ:=1\+ρ1−ρc\_\{\\rho\}:=\\frac\{1\+\\rho\}\{1\-\\rho\}, we have

1. \(i\)For anyx∈ℝdx\\in\\mathbb\{R\}^\{d\}andt∈\[T\]t\\in\[T\],‖x‖V~τt−1≤α​‖x‖V~t−1\\left\\lVert x\\right\\rVert\_\{\\widetilde\{V\}\_\{\\tau\_\{t\}\}^\{\-1\}\}\\leq\\sqrt\{\\alpha\}\\left\\lVert x\\right\\rVert\_\{\\widetilde\{V\}\_\{t\}^\{\-1\}\}and‖x‖Vτt−1≤cρ​α​‖x‖Vt−1\\left\\lVert x\\right\\rVert\_\{V\_\{\\tau\_\{t\}\}^\{\-1\}\}\\leq\\sqrt\{c\_\{\\rho\}\\alpha\}\\left\\lVert x\\right\\rVert\_\{V\_\{t\}^\{\-1\}\};
2. \(ii\)The total number of updatesmmis upper bounded bym≲d​logα/cρ⁡\(1\+T​L2λ​d\)=Od​\(log⁡T\)m\\lesssim d\\log\_\{\\alpha/c\_\{\\rho\}\}\\left\(1\+\\frac\{TL^\{2\}\}\{\\lambda d\}\\right\)=O\_\{d\}\(\\log T\)\.

###### 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\.

For1≤a≤b≤T1\\leq a\\leq b\\leq T, letga,b:=λmax​\(Va−1/2​Vb​Va−1/2\)g\_\{a,b\}:=\\lambda\_\{\\max\}\\left\(\{V\}\_\{a\}^\{\-1/2\}\{V\}\_\{b\}\{V\}\_\{a\}^\{\-1/2\}\\right\)andg~a,b:=λmax​\(V~a−1/2​V~b​V~a−1/2\)\\widetilde\{g\}\_\{a,b\}:=\\lambda\_\{\\max\}\\left\(\\widetilde\{V\}\_\{a\}^\{\-1/2\}\\widetilde\{V\}\_\{b\}\\widetilde\{V\}\_\{a\}^\{\-1/2\}\\right\)\. Then, we havecρ−1​ga,b≤g~a,b≤cρ​ga,b\.c\_\{\\rho\}^\{\-1\}g\_\{a,b\}\\leq\\widetilde\{g\}\_\{a,b\}\\leq c\_\{\\rho\}g\_\{a,b\}\.

We start with \(i\)\. For anyτt<t\\tau\_\{t\}<t, i\.e\.,ttis not the update slot, the first inequality follows directly from the update rule\. For the second one, by Claim[2\.3](https://arxiv.org/html/2605.23131#S2.Thmtheorem3)and our update rule, we first have

λmax​\(Vτt−1/2​Vt​Vτt−1/2\)≤cρ​α\.\\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

supx≠0x⊤​Vt​xx⊤​Vτt​x=λmax​\(Vτt−1/2​Vt​Vτt−1/2\)≤cρ​α\.\\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 thatVτt−1⪯cρ​α​Vt−1V\_\{\\tau\_\{t\}\}^\{\-1\}\\preceq c\_\{\\rho\}\\alpha V\_\{t\}^\{\-1\}, and hence‖x‖Vτt−1≤cρ​α​‖x‖Vt−1\\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 slotsi<ji<j\. By the update rule and Claim[2\.3](https://arxiv.org/html/2605.23131#S2.Thmtheorem3), we have

λmax​\(Vi−1/2​Vj​Vi−1/2\)\>α/cρ\.\\displaystyle\\lambda\_\{\\max\}\\left\(\{V\}\_\{i\}^\{\-1/2\}\{V\}\_\{j\}\{V\}\_\{i\}^\{\-1/2\}\\right\)\>\\alpha/c\_\{\\rho\}\.Further, sinceVj⪰ViV\_\{j\}\\succeq V\_\{i\}, all eigenvalues ofVi−1/2​Vj​Vi−1/2\{V\}\_\{i\}^\{\-1/2\}\{V\}\_\{j\}\{V\}\_\{i\}^\{\-1/2\}are least one\. Hence, by the above result and multiplicativity of determinant, we have

det\(Vj\)det\(Vi\)=det\(Vi−1/2​Vj​Vi−1/2\)\>α/cρ\.\\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](https://arxiv.org/html/2605.23131#bib.bibx1)\]\), we have that the total number of updatesmmis upper bounded bym≲d​logα/cρ⁡\(1\+T​L2λ​d\)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](https://arxiv.org/html/2605.23131#S2.Thmtheorem3)\. To show it, we first notice that by the condition onEtE\_\{t\}, we have

−η​I⪯Et⪯η​I\.\\displaystyle\-\\eta I\\preceq E\_\{t\}\\preceq\\eta I\.Further, byVt⪰λ​IV\_\{t\}\\succeq\\lambda I, henceη​I⪯\(η/λ\)​Vt=ρ​Vt\\eta I\\preceq\(\\eta/\\lambda\)V\_\{t\}=\\rho V\_\{t\}\. Combing the above, yields that

\(1−ρ\)​Vt⪯Vt~⪯\(1\+ρ\)​Vt\.\\displaystyle\(1\-\\rho\)V\_\{t\}\\preceq\\widetilde\{V\_\{t\}\}\\preceq\(1\+\\rho\)V\_\{t\}\.
Thus, for any nonzero vectorx∈ℝdx\\in\\mathbb\{R\}^\{d\}, we have

x⊤​V~b​xx⊤​V~a​x≤\(1\+ρ\)​x⊤​Vb​x\(1−ρ\)​x⊤​Va​x=cρ​x⊤​Vb​xx⊤​Va​x\.\\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 thatg~a,b≤cρ​ga,b\\widetilde\{g\}\_\{a,b\}\\leq c\_\{\\rho\}g\_\{a,b\}\. The other direction follows the same proof\. ∎

## 3The 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](https://arxiv.org/html/2605.23131#bib.bibx1)\]\. It then gives me a new proof which actually sheds a lot of light on how Codex comes up with the new update rule and its connection with the old one\.

The new proof is much simpler \(at least to me\) compared with the original proof\. Basically, the proof first notes that LHS in Lemma 12 is equal to

supx≠0x⊤​A​xx⊤​B​x=λmax​\(B−1/2​A​B−1/2\),\\displaystyle\\sup\_\{x\\neq 0\}\\frac\{x^\{\\top\}Ax\}\{x^\{\\top\}Bx\}=\\lambda\_\{\\max\}\(B^\{\-1/2\}AB^\{\-1/2\}\),\(1\)where again we apply identity of generalized Rayleigh quotient, while the RHS in Lemma 12 is equal to

det\(A\)det\(B\)=det\(B−1/2​A​B−1/2\)\.\\displaystyle\\frac\{\\det\(A\)\}\{\\det\(B\)\}=\\det\(B^\{\-1/2\}AB^\{\-1/2\}\)\.\(2\)Note that \([1](https://arxiv.org/html/2605.23131#S3.E1)\)≤\\leq\([2](https://arxiv.org/html/2605.23131#S3.E2)\) by the fact that all eigenvalues ofB−1/2​A​B−1/2B^\{\-1/2\}AB^\{\-1/2\}are at least one, which comes from the monotonicity thatB⪯AB\\preceq A\. This proves Lemma 12\.

So, essentially, the new update rule comes from the new proof of Lemma 12, i\.e\., \([1](https://arxiv.org/html/2605.23131#S3.E1)\)\. Moreover, we can see that under the new update rule, the learner would update less frequent as\([1](https://arxiv.org/html/2605.23131#S3.E1)\)\>α\\eqref\{eq:new\}\>\\alphaimplies\([2](https://arxiv.org/html/2605.23131#S3.E2)\)\>α\\eqref\{eq:old\}\>\\alpha, but not the other direction\.

This new proof also explains why the new update rule can get rid of the issue in the old rule when lacking of monotonicity\. This is because using the old update rule \(cf\. \([2](https://arxiv.org/html/2605.23131#S3.E2)\)\), one has to further leverage the monotonicity to arrive at the bound onsupx≠0x⊤​A​xx⊤​B​x\\sup\_\{x\\neq 0\}\\frac\{x^\{\\top\}Ax\}\{x^\{\\top\}Bx\}, i\.e\., the worst\-case direction\. On the other hand, the new rule directly works withsupx≠0x⊤​A​xx⊤​B​x\\sup\_\{x\\neq 0\}\\frac\{x^\{\\top\}Ax\}\{x^\{\\top\}Bx\}\.

We can now also see that with the old update rule, it is impossible to control the worst case direction without monotonicity since the eigenvalues on other directions can be much smaller and hence a very large value on the worst\-case direction can still make the determinant small\.

## 4The Reflection

Codex suggests a new rare\-switching rule for the private case that preserves the desired guarantees\. Upon closer inspection, the rule can be traced back to an alternative proof of a key lemma\. The ingredients in the proof are not new, but the useful part is the way they are selected, combined, and applied to the right object\. In this sense, this mini example somewhat the same spirit as the unit distance problem\.

This reminds me of several things\. First, for me, the most enjoyable part of doing research is not necessarily its impact, nor the final breakthrough result\. Rather, it is the moment when I understand something a little more deeply444Of course, this is a privilege thing\. Moreover, it can also lead to an embarrassing outcome where there is neither impact nor deep understanding\. You can name me here\.\. In this sense, research carries its own intrinsic reward\. One thing I still remember from high school and college is that I often went to my teachers or professors to ask clarification questions, or to explain my own understanding and hope they could verify it\.555Using today’s fancy language, I was trying to build and calibrate my own world model\.Now, with AI, students may have a much more convenient way to test, refine, and verify their own understanding \(if they want…\)\.

Second, I tend to view deep understanding of a subject as learning a good representation\. A good representation compresses many details into the right concepts, and because of that, it can be flexible and useful when adapted to new problems\. In many cases, what is needed to make a significant impact, either in theory or in practice, is not necessarily a completely new theory or method\. Rather, it may be something that grows naturally out of a better compression or representation of existing knowledge, one that identifies the “core set” of ideas from which a much larger unknown space can be explored\.

So, with today’s AI tools, humans may become more efficient at maximizing this kind of intrinsic reward: understanding more, clarifying faster, and building better representations\. Perhaps we should also think about how to steer AI systems, either during training or through test\-time scaling, toward a similar objective: not merely producing answers, but actively seeking good representations, useful abstractions, and core sets of ideas\. To me, this connects naturally to the fundamental problem of “exploration” in reinforcement learning, which is currently my biggest interest\.

## References

- \[APS11\]Yasin Abbasi\-Yadkori, Dávid Pál and Csaba Szepesvári“Improved algorithms for linear stochastic bandits”In*Advances in neural information processing systems*24, 2011
- \[CZ22\]Sayak Ray Chowdhury and Xingyu Zhou“Shuffle Private Linear Contextual Bandits”In*International Conference on Machine Learning*, 2022, pp\. 3984–4009PMLR
- \[HZ26\]Yi He and Xingyu Zhou“Towards Differentially Private Reinforcement Learning with General Function Approximation”In*arXiv preprint arXiv:2605\.07049*, 2026
- \[ZR24\]Xingyu Zhou and Sayak Ray Chowdhury“On differentially private federated linear contextual bandits”In*International Conference on Learning Representations*2024, 2024, pp\. 30101–30131