Global Convergence of Multiplicative Updates for the Matrix Mechanism: A Collaborative Proof with Gemini 3.
Keith Rush · 2026
Read Global Convergence of Multiplicative Updates for the Matrix Mechanism: A Collaborative Proof with Gemini 3. by Keith Rush (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-2603-19465.txt.
Introduction
Rush proves that a matrix update rule used in private machine learning always converges. The iteration arose from a nuclear norm problem left open by prior work. He shows the steps climb steadily to the single global best point. Most of the proof came from the Gemini 3 model, with human fixes. The note also tells how the prompting was run in practice. From that tale, he draws rules for working with AI on proofs. The result closes a small gap in the field's literature.
Catalog record
| CREATOR | Keith Rush |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39992 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.19465
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Global Convergence of Multiplicative Updates for the Matrix Mechanism: A Collaborative Proof with Gemini 3. Keith Rush Abstract We analyze a fixed-point iteration v ← ϕ ( v ) v\leftarrow\phi(v) arising in the optimization of a regularized nuclear norm objective involving the Hadamard product structure, posed in [ 5 ] in the context of an optimization problem over the space of algorithms in private machine learning. We prove that the iteration v ( k + 1 ) = diag ( ( D v ( k ) 1 / 2 M D v ( k ) 1 / 2 ) 1 / 2 ) v^{(k+1)}=\diag((D_{v^{(k)}}^{1/2}MD_{v^{(k)}}^{1/2})^{1/2}) converges monotonically to the unique global optimizer of the potential function J ( v ) = 2 Tr ( ( D v 1 / 2 M D v 1 / 2 ) 1 / 2 ) − ∑ v i J(v)=2\Tr((D_{v}^{1/2}MD_{v}^{1/2})^{1/2})-\sum v_{i} , closing a problem left open there. We also connect this iteration to known results in quantum information and optimal transport. The bulk of this proof was provided by Gemini 3, subject to some corrections and interventions. Gemini 3 also sketched the initial version of this note. Thus, it represents as much a commentary on the practical use of AI in mathematics as it represents the closure of a small gap in the literature. As such, we include a small narrative description of the prompting process, and some resulting principles (and observed pitfalls) when working with AI to prove mathematics. 1 The Problem and its Brief History We consider the problem of finding the fixed point v^{*}\in\mathbb{R}_{++}^{N} satisfying the equation: v^{*}=\diag\left(\left(D_{v^{*}}^{1/2}MD_{v^{*}}^{1/2}\right)^{1/2}\right) (1) where M\in\mathbb{R}^{N\times N} is a symmetric positive definite matrix ( M\succ 0 ), and D_{v}=\diag(v) . This fixed-point equation arises naturally as the stationarity condition ( \nabla J(v)=0 ) for the potential function J:\mathbb{R}_{++}^{N}\to\mathbb{R} : J(v)=2\Tr\left(\left(D_{v}^{1/2}MD_{v}^{1/2}\right)^{1/2}\right)-\sum_{i=1}^{N}v_{i} (2) To our knowledge, the first occurrence of this potential can be found in [ 5 ] , where it arose in the context of designing matrix factorizations that are in some sense optimal for the matrix mechanism [ 11 ] under a specific notion of error. [ 5 ] was able to show that iterating the mapping Eq. 1 converged locally, and provided empirical evidence that this fixed-point iteration converged extremely rapidly, outpacing pure gradient-based approaches, but global convergence of these iterates was left open. The followup papers in the series of [ 5 ] (see the literature review in [ 14 ] ) generally moved away from the unconstrained optimization problem that yields the potential Eq. 2 , in order to impose structural constraints on matrices which address practical concerns like runtime efficiency and ability to prove privacy amplification results. The specification of the BLT class [ 6 ] providing the ability to compute near-optimal factorizations with complexity independent of matrix size rendered the convergence of the iterates of Eq. 1 even more academic. Still, I always viewed it as unsatisfactory that we were unable to prove global convergence despite reasonably serious attempts by reasonably serious mathematicians. This global convergence always had the feel to me of something which was just an issue of putting together the right tools, which probably all existed. I therefore kept it in my back pocket, and tested it repeatedly on new versions of various AI models as they were released. Given my affiliation, most of these attempts used Gemini. With a few iterations, Gemini 3 was able to identify the crucial piece that we had missed: a variational characterization of the nuclear norm that allows the problem to be diagonalized. This diagonalization of our crucial object essentially required the ability to call certain linear algebra to hand that neither myself nor my collaborators demonstrated, but it was not exactly revolutionary. This is not unreasonable – mathematics is quite large, and not every mathematician can recall every inequality or characterization of an object under study, particularly if this object is far from their main field. We hope that this note can serve as a small example of utilization of AI in mathematics, echoing several that have appeared elsewhere in the literature, and also represent the closure of a problem that had always nagged me. We study the convergence of the parameter-free multiplicative update rule: v^{(k+1)}=\phi(v^{(k)})=\diag\left(\left(D_{v^{(k)}}^{1/2}MD_{v^{(k)}}^{1/2}\right)^{1/2}\right) (3) Our main contribution is a proof that this iteration satisfies the monotonic ascent property J(v^{(k+1)})\geq J(v^{(k)}) , ensuring global convergence to the unique maximum. We also include discussion of the experience of working interactively with natural-language AI models to produce nontrivial mathematics. 2 Theoretical Analysis 2.1 Basic Properties The result here depends critically on a representation of the first term in our potential as the nuclear norm of a matrix, and a particular variational characterization for this norm. Definition 1 (Nuclear Norm) . For any real matrix A , define the nuclear norm \|A\|_{*} as: \|A\|_{*}=\Tr((A^{\top}A)^{1/2}) We will collect the properties of the nuclear norm that we need before we begin. Lemma 1 . For any real A , the nuclear norm can be characterized in the following manner: \|A\|_{*}=\sup_{U\in\mathcal{U}(N)}\Tr(U^{\top}A) where \mathcal{U}(N) is the set of unitary matrices. The supremum is attained when U is the unitary factor from the polar decomposition of A (see Section 7.4 of [ 9 ] ). Proof. We recall the polar factorization of A , the representation A=UP where P=(A^{\top}A)^{1/2} and U is unitary. (Since A is real, U is in fact orthogonal). Therefore U^{\top}A=P , and: \|A\|_{*}=\Tr\left((A^{\top}A)^{1/2}\right)=\Tr(P)=\Tr(U^{\top}A). This shows that \|A\|_{*}\leq\sup_{U\in\mathcal{U}(N)}\Tr(U^{\top}A) . The reverse inequality follows from the Von Neumann trace inequality; for O unitary, its singular values are of absolute value 1, and therefore |\Tr(O^{\top}A)|\leq\sum|\omega_{i}\alpha_{i}|=\sum|\alpha_{i}|=\Tr\left((A^{\top}A)^{1/2}\right) ∎ Lemma 2 (Strict Concavity) . For a symmetric positive definite matrix M\succ 0 , the potential function J(v)=2\Tr\left(\left(D_{v}^{1/2}MD_{v}^{1/2}\right)^{1/2}\right)-\sum_{i=1}^{N}v_{i} is strictly concave on the positive orthant \mathbb{R}_{++}^{N} . Proof. For any matrices A and B , AB and BA share the same non-zero eigenvalues (this is [ 9 ] , Theorem 1.3.22). Let A=D_{v}^{1/2}M^{1/2} and B=M^{1/2}D_{v}^{1/2} . As AB and BA share eigenvalues, the trace of their square roots is identical: \Tr\left((D_{v}^{1/2}MD_{v}^{1/2})^{1/2}\right)=\Tr\left((M^{1/2}D_{v}M^{1/2})^{1/2}\right) Since the mapping v\mapsto M^{1/2}D_{v}M^{1/2} is linear in v and injective, Lieb’s concavity theorem ( [ 12 ] ) combined with concavity for a composition of an injective linear map with a concave map finish the proof. ∎ Lemma 3 (Coercivity) . The potential function J(v) is coercive on \mathbb{R}_{+}^{N} in the sense that J(v)\to-\infty as \left\lVert v\right\rVert_{1}\to\infty . Proof. Let A=D_{v}^{1/2}MD_{v}^{1/2} . Note that \Tr(A^{1/2}) is the nuclear norm of D_{v}^{1/2}M^{1/2} . By the relationship between the nuclear norm and the Frobenius norm, \Tr(A^{1/2})\leq\sqrt{N\Tr(A)} . We have: \Tr(A)=\Tr(D_{v}^{1/2}MD_{v}^{1/2})=\Tr(MD_{v})=\sum_{i=1}^{N}M_{ii}v_{i}\leq\max_{i}(M_{ii})\left\lVert v\right\rVert_{1} Thus, J(v)\leq 2\sqrt{N\max_{i}(M_{ii})\left\lVert v\right\rVert_{1}}-\left\lVert v\right\rVert_{1} . As \left\lVert v\right\rVert_{1}\to\infty , the linear term dominates the square-root term, hence J(v)\to-\infty . This, combined with strict concavity and the fact that J(v) is bounded at the boundary \partial\mathbb{R}_{+}^{N} , ensures the existence of a unique maximizer v^{*}\in\mathbb{R}_{++}^{N} . ∎ Lemma 4 (Positive Invariance) . If v^{(k)}\in\mathbb{R}_{++}^{N} and M\succ 0 , then v^{(k+1)}=\phi(v^{(k)})\in\mathbb{R}_{++}^{N} . Proof. Let X=D_{v^{(k)}}^{1/2}MD_{v^{(k)}}^{1/2} . Since v^{(k)}>0 element-wise, D_{v^{(k)}}^{1/2} is a non-singular diagonal matrix. Because M\succ 0 , the congruence transformation X is also symmetric positive definite ( X\succ 0 ). The unique positive definite square root X^{1/2} is