Pith. sign in

REVIEW 2 major objections 5 minor 1 cited by

A matrix-factorization construction cuts pure-DP continual-counting error constants to 0.0778 and 0.0710 times log^{3}_{2} n / ε^{2}.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-13 05:27 UTC pith:LG6N6KFK

load-bearing objection Solid constant improvement for pure-DP continual counting via a new recursive matrix factorization, with certified numerics and a matching 0/1 lower bound; the asymptotic gap for general mechanisms remains open. the 2 major comments →

arxiv 2607.08963 v1 pith:LG6N6KFK submitted 2026-07-09 cs.DS

Improved Error Bounds for Pure Differentially Private Continual Counting via Matrix Factorization

Pavel Arkhipov , Nikita P. Kalinin This is my paper
classification cs.DS MSC 68P2768Q2568W40
keywords differential privacycontinual countingmatrix factorizationpure DPfactorization costprefix sumsLaplace mechanismtree mechanisms
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Private continual counting asks for running prefix sums of a stream while protecting every individual update under pure differential privacy. The best previous pure-DP mechanisms still left a cubic-log upper bound whose leading constant was roughly three times larger than the new construction. The paper shows that any high-quality factorization of a modest-size prefix-sum matrix can be lifted, by an explicit recursive “diamond” operation, into factorizations of every larger size whose squared-error costs improve asymptotically. Numerically optimized 1024-by-1024 bases, verified by exact rational residual bounds, produce concrete MaxSE and MeanSE constants 0.0778 and 0.0710. The same construction yields an O(log n)-space online algorithm, and a matching Ω(log^{3} n) lower bound is proved for every 0-1 factorization, covering all classical tree mechanisms without subtraction.

Core claim

For every stream length n there exist ε-differentially private continual-counting mechanisms whose maximum and mean squared errors satisfy MaxSE ≤ 0.0778 (log_{2} n)^{3}/ε^{2} (1+o(1)) and MeanSE ≤ 0.0710 (log_{2} n)^{3}/ε^{2} (1+o(1)). These constants are obtained by lifting a rigorously verified 1024-dimensional matrix factorization of the prefix-sum matrix through a recursive diamond product that improves the leading asymptotic factor.

What carries the argument

The diamond operation (A,B)♢(C,D) that, given factorizations of T_n and T_k, produces an explicit factorization of T_{2kn+n+k} whose (c_{2})^{2/3} or (c_F)^{2/3} cost is at most the sum of the corresponding costs of the two inputs; iterated on a fixed base factorization it yields the claimed asymptotic constants.

Load-bearing premise

The concrete constants rest on the claim that two particular 1024-by-1024 floating-point matrices, after conversion to rationals and exact residual analysis, satisfy the stated operator-norm bounds.

What would settle it

Re-run the exact rational residual and symbolic-norm verification on the published base matrices; if either residual bound or square-root comparison fails, the numerical constants 0.0778 and 0.0710 are invalid.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • Any pure-DP streaming algorithm that reduces to continual counting immediately inherits the improved MaxSE and MeanSE constants.
  • Tree mechanisms that stay inside 0-1 factorizations cannot beat the new Ω(log^{3} n) lower bound, so further constant-factor progress must leave that class.
  • The same diamond lift works for any base factorization, so better numerical optimizers or larger bases can still tighten the leading constants.
  • The construction supplies an O(log n)-space online noise-correlation algorithm, matching the memory of classical tree methods while improving error.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the open Ω(log^{3} n) lower bound for unrestricted factorizations is eventually proved, the new constants would sit only a small constant factor above optimality.
  • The same lifting idea may apply to other pure-DP linear queries whose sensitivity is measured in ℓ_{1} rather than ℓ_{2}.
  • Because the diamond product improves the constant even for modest base dimensions, hybrid constructions that mix a few optimized bases with classical trees become attractive for practical implementations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies pure differentially private continual counting and improves the leading constants in the best known upper bounds on maximum squared error (MaxSE) and mean squared error (MeanSE). It works in the matrix-factorization framework: a diamond operation (Definition 2.2) combines factorizations of T_n and T_k into a factorization of T_{2kn+n+k} while controlling the c_2 and c_F costs via the 2/3-power inequalities of Theorem 2.1; iterating this lift from a numerically optimized base factorization of T_1024 yields Theorem 1.1 (MaxSE ≤ 0.0778 log_2^3 n / ε^2 (1+o(1)) and MeanSE ≤ 0.0710 log_2^3 n / ε^2 (1+o(1))). The base norms are certified by converting float matrices to rationals and bounding residuals with exact arithmetic (Proposition 2.6). An O(log n)-space, O(n log n)-time online implementation is given, and an Ω(log^{3/2} n) lower bound is proved for 0/1 factorizations via skew Bollobás inequalities, matching the known upper-bound asymptotics inside that class.

Significance. The work is a clear advance on a classical pure-DP problem: it improves the previous best pure-DP constants (k-ary trees with subtraction, and the averaged variant) by roughly 1.5–3× for MaxSE and about 1.6× for MeanSE, and does so with a non-tree matrix factorization. Strengths that raise confidence include (i) a fully analytic recursive lifting theorem independent of numerics, (ii) public code plus an explicit rational residual argument for the base factorization, (iii) a matching-space streaming implementation, and (iv) a combinatorial lower bound that settles the log^3 asymptotics for the natural 0/1 (tree-like) class. The structural observation that c_2 and c_F fail the triangle inequality also clarifies why pure-DP factorization is harder than the approximate-DP γ-norms. The remaining asymptotic gap for general mechanisms is left open, which is appropriately stated.

major comments (2)
  1. Proposition 2.6 (and the analogous MeanSE calculation) is load-bearing for the concrete constants in Theorem 1.1. The argument is carefully described, but the actual float32 matrices, the rational conversion, and the symbolic residual bounds live primarily in an external GitHub repository. For archival soundness the camera-ready version should ship the base matrices (or cryptographic hashes) and a short, self-contained verification script as supplementary material, and should list the key intermediate rational upper bounds (||Δ̃||_F, ||T_k^{-1} Δ̃||_F, ||ΔL||_F, etc.) in the paper or appendix so a reader can re-check without relying on repository longevity.
  2. Theorem 2.5 / Appendix A: the c_2 truncation is immediate, but the c_F argument for non-round n relies on a multi-page induction controlling prefix discrepancies of squared row norms (Claim A.1 and the F_q = O(N_{q-1}) bound). The main text currently only sketches the round case. A short, self-contained high-level paragraph in §2 explaining why 1/√n ||L||_F = (1+o(1)) 1/√N ||L'||_F (using α_i ≤ 1 and the recursive block structure) would make the MeanSE claim easier to audit without diving into the full appendix.
minor comments (5)
  1. Table 1: the caption states bounds up to 1+o(1); it would help to note explicitly which rows are newly computed in Appendix C (smooth binary tree MaxSE/MeanSE, k-ary without subtraction MaxSE, averaged k-ary) versus taken from prior work.
  2. Definition 2.2 / Figure 1: the anti-diagonal matrix E and the sign pattern of ẽA are easy to misread; a one-line remark that EA reverses rows of A (and BE reverses columns of B) already appears later—moving it next to (12) would reduce friction.
  3. §1.3 and Appendix C.3: the averaged k-ary tree with subtraction is attributed to implementation code of Imola et al. with permission; a brief formal statement of the two-decomposition averaging (beyond the figures) in the main related-work paragraph would make the comparison self-contained.
  4. Notation: log vs log_2 is declared, but a few places (e.g., the entropy bounds in §4) switch between natural and base-2 logarithms in intermediate steps; keeping a single base until the final conversion would avoid small constant-tracking errors for readers.
  5. Typos / polish: “Bollob´ as” spacing, “steams” → “streams” in the paragraph after Algorithm 2, and “the average the b_i’s” in the proof of Theorem 4.2.

Circularity Check

0 steps flagged

No significant circularity: numerical base factorizations are independently certified by exact rational residual analysis; the diamond lifting and 0/1 lower bounds are self-contained algebraic/combinatorial derivations.

full rationale

The central upper-bound claim (Theorem 1.1) rests on two independent pillars that do not reduce to each other by construction. First, Definition 2.2 and Theorem 2.1 give an explicit algebraic operation that, given any factorization of T_k and T_n, produces a factorization of T_{2kn+n+k} whose c_2 and c_F costs satisfy a strict 2/3-power subadditivity; iterating it (Construction 2.4, Theorem 2.5) yields the asymptotic improvement factor (log_2 k / log_2(2k+1))^{3/2} purely analytically. Second, a single finite-dimensional base factorization of T_1024 is obtained by numerical optimization and then re-certified from scratch by conversion to rationals, exact residual computation, and symbolic Frobenius-norm bounds (Proposition 2.6 and the accompanying GitHub code). The optimizer is used only to propose candidates; the claimed operator-norm numbers that enter the final constants 0.0778 and 0.0710 are proved independently of floating-point search. The 0/1 lower bounds (Theorems 4.1–4.2) reduce to classical skew-Bollobás inequalities and likewise contain no fitted parameters or self-referential definitions. No step equates a claimed prediction with a fitted input, imports uniqueness from overlapping authors, or renames a known result. The only non-analytic ingredient is a publicly verifiable computer-assisted certificate for one concrete matrix; that does not create circularity under the stated criteria.

Axiom & Free-Parameter Ledger

1 free parameters · 3 axioms · 1 invented entities

The central upper-bound claim rests on (i) the classical Laplace mechanism and pure-DP post-processing, (ii) the algebraic identity that the diamond operation multiplies to the larger prefix matrix, and (iii) a rigorously verified numerical base factorization. No free parameters are fitted to the final error; the only numerical objects are intermediate bases whose norms are re-proved exactly. The lower-bound claim rests solely on the skew Bollobás theorem from extremal set theory.

free parameters (1)
  • base factorization dimension k=1024
    Chosen by the authors after scanning several powers of two; larger k yields better raw C_{2}/C_F but a smaller lifting improvement factor. The final constants are computed for this fixed k and then lifted; the choice is not fitted to any external data set.
axioms (3)
  • domain assumption Laplace mechanism is ε-DP for ℓ₁-sensitivity and pure DP is closed under post-processing
    Standard facts from Dwork et al. (TCC 2006) used throughout Sections 1–3 to convert factorization costs into MaxSE/MeanSE.
  • standard math Skew Bollobás inequality (and its weighted form) for set systems
    Invoked in Theorems 4.1–4.2 to bound the product of row/column norms of 0/1 factors; cited from Frankl (1982) and Yue (2024).
  • ad hoc to paper The diamond operation of Definition 2.2 multiplies to T_{2kn+n+k}
    Proved as Lemma 2.3 by block-matrix algebra; the algebraic identity is original to the paper but elementary once stated.
invented entities (1)
  • diamond (♢_α) operation on matrix factorizations independent evidence
    purpose: Combines factorizations of T_n and T_k into a factorization of T_{2kn+n+k} while adding the 2/3-powers of the costs, enabling asymptotic constant improvement.
    Defined in Definition 2.2; no independent existence outside the paper, but fully constructive and verified by direct multiplication.

pith-pipeline@v1.1.0-grok45 · 35602 in / 2663 out tokens · 30858 ms · 2026-07-13T05:27:11.655357+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of Improved Error Bounds for Pure Differentially Private Continual Counting via Matrix Factorization." pith.science (2026). https://pith.science/paper/LG6N6KFK

@misc{pith2026260708963,
  author       = {Pith},
  title        = {Pith review of: Improved Error Bounds for Pure Differentially Private Continual Counting via Matrix Factorization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LG6N6KFK}},
  note         = {Machine review of arXiv:2607.08963}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Continual counting under pure differential privacy is one of the simplest and most well-studied problems in the continual observation model. Nevertheless, an asymptotic gap remains between the best known upper and lower bounds for maximum squared error and mean squared error: the upper bound is $O(\epsilon^{-2}\log^3 n)$, while the lower bound is $\Omega(\epsilon^{-2}\log^2 n)$, for both error metrics. The best known constant in the upper bound is achieved by the $k$-ary tree mechanism with the subtraction trick, due to Andersson, Pagh, Steiner, and Torkamani (FORC 2025). In this work, we improve the leading constant in the maximum squared error and the mean squared error. Our approach uses a general matrix factorization mechanism, yielding an improved bound for pure-DP continual counting that does not rely on a tree-based construction. The mechanism starts from a good-quality low-dimensional factorization, obtained via gradient-based optimization, and gives an explicit matrix construction that lifts this factorization to arbitrarily large dimensions, further improving its error guarantees. We offer an efficient algorithmic implementation of our mechanism. On the lower-bound side, we prove an $\Omega(\epsilon^{-2}\log^3 n)$ lower bound for the class of factorizations whose matrices have entries in $\{0,1\}$, matching the upper-bound asymptotics for this class. This class includes the binary tree mechanism and $k$-ary tree mechanisms without the subtraction trick. Extending this lower bound to arbitrary matrix factorizations, and beyond the matrix mechanism altogether, remains an open problem.

Figures

Figures reproduced from arXiv: 2607.08963 by Nikita P. Kalinin, Pavel Arkhipov.

Figure 1
Figure 1. Figure 1: Decomposition of T2kn+n+k into two matrices, example for k = 2. First, we introduce matrices Ae ∈ R (2n+1)×2r and Be ∈ R 2r×(2n+1), defined as Ae =   −EA 0n×r 01×r 01×r 0n×r A   , Be =  B 0r×1 0r×n 0r×n 0r×1 BE  , (12) where E is an n×n matrix with ones on the anti-diagonal: Eij = 1{i+j = n+ 1}. Then we define L =  A 0n×2rk 0n×s 0k(2n+1)×r Ik ⊗ A αC e ⊗ 12n+1 , R =   Ik ⊗ Be 02rk×n 0r×k(2n+1) B 1… view at source ↗
Figure 2
Figure 2. Figure 2: A 3-ary tree of height 2. The red nodes compute [ [PITH_FULL_IMAGE:figures/full_fig_p032_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: A 3-ary tree of height 3. The red nodes compute [ [PITH_FULL_IMAGE:figures/full_fig_p032_3.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting

    cs.CR 2026-07 reject novelty 7.0

    For the pure-DP Laplace matrix mechanism on prefix sums, the paper claims optimized maximum and mean squared errors of order Θ(log^3 n / ε^2) for arbitrary real factorizations, matching the best-known upper bound.

Reference graph

Works this paper leans on

53 extracted references · 5 linked inside Pith · cited by 1 Pith paper

  1. [1]

    Improved accuracy for private con- tinual cardinality estimation in fully dynamic streams via matrix factorization

    Joel Daniel Andersson, Palak Jain, and Satchit Sivakumar. Improved accuracy for private con- tinual cardinality estimation in fully dynamic streams via matrix factorization. InSymposium on Principles of Database Systems (PODS), 2026

    2026

  2. [2]

    A smooth binary mechanism for efficient private continual observation

    Joel Daniel Andersson and Rasmus Pagh. A smooth binary mechanism for efficient private continual observation. InConference on Neural Information Processing Systems (NeurIPS), 2023

    2023

  3. [3]

    Count on your elders: Laplace vs Gaussian noise

    Joel Daniel Andersson, Rasmus Pagh, Teresa Anna Steiner, and Sahel Torkamani. Count on your elders: Laplace vs Gaussian noise. InFoundations of Responsible Computing (FORC), 2025

    2025

  4. [4]

    The binary tree mechanism is optimal for approximate differentially private continual counting, 2026

    Konstantina Bairaktari and Kasper Green Larsen. The binary tree mechanism is optimal for approximate differentially private continual counting, 2026. arXiv:2607.00876

    Pith/arXiv arXiv 2026

  5. [5]

    Differentially private histograms under continual observation: Streaming selection into the unknown

    Adrian Rivera Cardoso and Ryan Rogers. Differentially private histograms under continual observation: Streaming selection into the unknown. InInternational Conference on Artificial Intelligence and Statistics (AISTATS), 2022

    2022

  6. [6]

    Private and continual release of statistics

    T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. In Transactions on Information and System Security (TISSEC), 2011

    2011

  7. [7]

    Multi-epoch matrix factorization mechanisms for private machine learning

    Christopher A Choquette-Choo, H Brendan McMahan, Keith Rush, and Abhradeep Thakurta. Multi-epoch matrix factorization mechanisms for private machine learning. InInternational Conference on Machine Learning (ICML), 2023

    2023

  8. [8]

    Denisov, H

    S. Denisov, H. B. McMahan, J. Rush, A. Smith, and G. A. Thakurta. Improved Differential Privacy for SGD via optimal private linear operators on adaptive streams. InConference on Neural Information Processing Systems (NeurIPS), 2022

    2022

  9. [9]

    A general- ized binary tree mechanism for differentially private approximation of all-pair distances

    Michael Dinitz, Chenglin Fan, Jingcheng Liu, Jalaj Upadhyay, and Zongrui Zou. A general- ized binary tree mechanism for differentially private approximation of all-pair distances. In Conference on Neural Information Processing Systems (NeurIPS), 2025

    2025

  10. [10]

    Efficient and near-optimal noise generation for streaming differential privacy

    Krishnamurthy Dj Dvijotham, H Brendan McMahan, Krishna Pillutla, Thomas Steinke, and Abhradeep Thakurta. Efficient and near-optimal noise generation for streaming differential privacy. InSymposium on Foundations of Computer Science (FOCS), 2024. 20

    2024

  11. [11]

    Calibrating noise to sen- sitivity in private data analysis

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sen- sitivity in private data analysis. InTheory of Cryptography Conference (TCC), 2006

    2006

  12. [12]

    Differential privacy under continual observation

    Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under continual observation. InSymposium on Theory of Computing (STOC), 2010

    2010

  13. [13]

    The power of factorization mechanisms in local and central differential privacy

    Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman. The power of factorization mechanisms in local and central differential privacy. InSymposium on Theory of Computing (STOC), 2020

    2020

  14. [14]

    Differentially private continual releases of streaming frequency moment estimations

    Alessandro Epasto, Jieming Mao, Andres Munoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, and Peilin Zhong. Differentially private continual releases of streaming frequency moment estimations. InInnovations in Theoretical Computer Science Conference (ITCS), 2023

    2023

  15. [15]

    Differentially private algorithms for graphs under continual observation

    Hendrik Fichtenberger, Monika Henzinger, and Lara Ost. Differentially private algorithms for graphs under continual observation. InEuropean Symposium on Algorithms (ESA), 2021

    2021

  16. [16]

    Constant matters: Fine- grained complexity of differentially private continual observation using completely bounded norms

    Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. Constant matters: Fine- grained complexity of differentially private continual observation using completely bounded norms. InInternational Conference on Machine Learning (ICML), 2023

    2023

  17. [17]

    P. Frankl. An extremal problem for two families of sets.European Journal of Combinatorics, 1982

    1982

  18. [18]

    Continual mean estimation under user-level privacy.Journal on Selected Areas in Information Theory, 2024

    Anand Jerry George, Lekshmi Ramesh, Aditya Vikram Singh, and Himanshu Tyagi. Continual mean estimation under user-level privacy.Journal on Selected Areas in Information Theory, 2024

    2024

  19. [19]

    Kalinin, and Jalaj Upadhyay

    Monika Henzinger, Nikita P. Kalinin, and Jalaj Upadhyay. Normalized square root: Sharper matrix factorization bounds for differentially private continual counting. InFoundations of Responsible Computing (FORC), 2026

    2026

  20. [20]

    Differentially private continual release of histograms and related queries

    Monika Henzinger, AR Sricharan, and Teresa Anna Steiner. Differentially private continual release of histograms and related queries. InInternational Conference on Artificial Intelligence and Statistics (AISTATS), 2025

    2025

  21. [21]

    Improved differentially private continual observation using group algebra

    Monika Henzinger and Jalaj Upadhyay. Improved differentially private continual observation using group algebra. InSymposium on Discrete Algorithms (SODA), 2025

    2025

  22. [22]

    Almost tight error bounds on differentially private continual counting

    Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. Almost tight error bounds on differentially private continual counting. InSymposium on Discrete Algorithms (SODA), 2023

    2023

  23. [23]

    Efficient use of differentially private binary trees

    James Honaker. Efficient use of differentially private binary trees. InTheory and Practice of Differential Privacy (TPDP), 2015

    2015

  24. [24]

    Differentially private quantiles with smaller error

    Jacob Imola, Fabrizio Boninsegna, Hannah Keller, Anders Aamand, Amrita Roy Chowdhury, and Rasmus Pagh. Differentially private quantiles with smaller error. InConference on Neural Information Processing Systems (NeurIPS), 2025

    2025

  25. [25]

    Count- ing distinct elements in the turnstile model with differential privacy under continual observa- tion

    Palak Jain, Iden Kalemaj, Sofya Raskhodnikova, Satchit Sivakumar, and Adam Smith. Count- ing distinct elements in the turnstile model with differential privacy under continual observa- tion. InConference on Neural Information Processing Systems (NeurIPS), 2023. 21

    2023

  26. [26]

    Practical and private (deep) learning without sampling or shuffling

    Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. InInternational Conference on Machine Learning (ICML), 2021

    2021

  27. [27]

    Kalinin and Joel Daniel Andersson

    Nikita P. Kalinin and Joel Daniel Andersson. Learning rate scheduling with matrix factoriza- tion for private training. InFoundations of Responsible Computing (FORC), 2026

    2026

  28. [28]

    Kalinin and Christoph H

    Nikita P. Kalinin and Christoph H. Lampert. Banded square root matrix factorization for differentially private model training. InConference on Neural Information Processing Systems (NeurIPS), 2024

    2024

  29. [29]

    Kalinin, Ryan McKenna, Rasmus Pagh, and Christoph H Lampert

    Nikita P. Kalinin, Ryan McKenna, Rasmus Pagh, and Christoph H Lampert. DP-λCGD: Efficient noise correlation for differentially private model training, 2026. arXiv preprint arXiv:2601.22334

    Pith/arXiv arXiv 2026

  30. [30]

    Kalinin, Ryan McKenna, Jalaj Upadhyay, and Christoph H Lampert

    Nikita P. Kalinin, Ryan McKenna, Jalaj Upadhyay, and Christoph H Lampert. Back to square roots: An optimal bound on the matrix factorization error for multi-epoch differentially private SGD. InInternational Conference on Learning Representations (ICLR), 2026

    2026

  31. [31]

    Kalinin, Aki Rehn, Joel Daniel Andersson, Antti Honkela, and Christoph H Lampert

    Nikita P. Kalinin, Aki Rehn, Joel Daniel Andersson, Antti Honkela, and Christoph H Lampert. Beyond square roots: Explicit memory-efficient factorization for multi-epoch private learning,

  32. [32]

    arXiv preprint arXiv:2605.18379

    Pith/arXiv arXiv

  33. [33]

    Adam: A method for stochastic optimization, 2014

    Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2014. arXiv preprint arXiv:1412.6980

    Pith/arXiv arXiv 2014

  34. [34]

    Kwapie´ n and A

    S. Kwapie´ n and A. Pe lczy´ nski. The main triangle projection in matrix spaces and its applica- tions.Studia Mathematica, 1970

    1970

  35. [35]

    Making old things new: a uni- fied algorithm for differentially private clustering

    Max Dupr´ e La Tour, Monika Henzinger, and David Saulpic. Making old things new: a uni- fied algorithm for differentially private clustering. InInternational Conference on Machine Learning (ICML), 2024

    2024

  36. [36]

    The ma- trix mechanism: Optimizing linear counting queries under Differential Privacy.International Conference on Very Large Data Bases (VLDB), 2015

    Chao Li, Gerome Miklau, Michael Hay, Andrew McGregor, and Vibhor Rastogi. The ma- trix mechanism: Optimizing linear counting queries under Differential Privacy.International Conference on Very Large Data Bases (VLDB), 2015

    2015

  37. [37]

    On the limited memory BFGS method for large scale opti- mization.Mathematical programming, 1989

    Dong C Liu and Jorge Nocedal. On the limited memory BFGS method for large scale opti- mization.Mathematical programming, 1989

    1989

  38. [38]

    Factorization norms and hereditary discrepancy.International Mathematics Research Notices, 2020

    Jiˇ r´ ı Matouˇ sek, Aleksandar Nikolov, and Kunal Talwar. Factorization norms and hereditary discrepancy.International Mathematics Research Notices, 2020

    2020

  39. [39]

    Smith, Mateusz Paprocki, Ondˇ rej ˇCert´ ık, Sergey B

    Aaron Meurer, Christopher P. Smith, Mateusz Paprocki, Ondˇ rej ˇCert´ ık, Sergey B. Kirpichev, Matthew Rocklin, Amit Kumar, Sergiu Ivanov, Jason K. Moore, Sartaj Singh, Thilina Rath- nayake, Sean Vig, Brian E. Granger, Richard P. Muller, Francesco Bonazzi, Harsh Gupta, Shivam Vats, Fredrik Johansson, Fabian Pedregosa, Matthew J. Curry, Andy R. Terrel,ˇStˇ...

    2017

  40. [40]

    Correlated noise mechanisms for differentially private learning, 2025

    Krishna Pillutla, Jalaj Upadhyay, Christopher A Choquette-Choo, Krishnamurthy Dvijotham, Arun Ganesh, Monika Henzinger, Jonathan Katz, Ryan McKenna, H Brendan McMahan, 22 Keith Rush, et al. Correlated noise mechanisms for differentially private learning, 2025. arXiv preprint arXiv:2506.08201

    Pith/arXiv arXiv 2025

  41. [41]

    Understanding hierarchical methods for differentially private histograms.Proc

    Wahbeh Qardaji, Weining Yang, and Ninghui Li. Understanding hierarchical methods for differentially private histograms.Proc. VLDB Endow., 2013

    2013

  42. [42]

    Fully dynamic graph algorithms with edge differential privacy.Proceedings of the ACM on Management of Data (PACMMOD), 2024

    Sofya Raskhodnikova and Teresa Anna Steiner. Fully dynamic graph algorithms with edge differential privacy.Proceedings of the ACM on Management of Data (PACMMOD), 2024

    2024

  43. [43]

    Sublinear space private algorithms under the sliding window model

    Jalaj Upadhyay. Sublinear space private algorithms under the sliding window model. In International Conference on Machine Learning (ICML), 2019

    2019

  44. [44]

    round” in the sensen= (2k+1)p−1 2 for somep, then the theorem holds. The remainder of the proof is a careful analysis of what happens fornthat falls in between “round

    Erfei Yue. Some new Bollob´ as-type inequalities.Discret. Math., 2024. A Proof of the upper bound (Theorem 2.5) Proof of Theorem 2.5.In the construction, we first get the matrices (L ′, R′) = (A, B)♢. . .♢(A, B)| {z } ptimes with the size ofL ′R′ at leastn. LetNbe such thatL ′R′ =T N,N≥n. We haveN= (2k+1)p−1 2 , which can be verified by induction onp. Sin...

    2024

  45. [45]

    Then|x j|=∥x∥ ∞

    Choosee j such that|x j|is maximal. Then|x j|=∥x∥ ∞. We have 1 =∥x∥ 2 2 ≤ ∥x∥ ∞∥x∥1 <|x j| √ 2.(74) Then we have|x j|> √ 2/2, and the angleφbetweenRxandRe j is in [0, π/4], with|x j|= cosφ. Moreover, ∥x∥1 − |xj|= X i̸=j |xi| ≥  X i̸=j |xi|2   1/2 = q 1− |x j|2 = sinφ.(75) Therefore,∥x∥ 1 ≥cosφ+ sinφ. By the definition ofβ x, this impliesφ≤β x. Thus, w...

  46. [46]

    Ife≥0, thenD=af−be≤af≤a≤ ∥x∥ 2

  47. [47]

    Iff≤0, thenD=af−be≤ −be≤b≤ ∥x∥ 2

  48. [48]

    Then, sincea≤1 and−e≤1,D=af+b(−e)≤f+b

    The only remaining case ise <0< f. Then, sincea≤1 and−e≤1,D=af+b(−e)≤f+b. Butb+fis the second coordinate ofx+y, soD≤b+f≤ ∥x+y∥ 2. Thus the claim follows. Applying the claim tox=Suandy=Sw, we get 2|∆| ≤max{∥Su∥ ∞,∥Sw∥ ∞}max{∥Su∥ 2,∥S(u+w)∥ 2}.(82) Thus 2|∆| ≤max{∥u∥ 1,∥w∥ 1} √ 2 max{∥u∥2,∥u+w∥ 2}.(83) Therefore we have ∥L∥2→∞ ∥R∥1→1 = max{∥u∥2,∥u+w∥ 2}max{...

  49. [49]

    LetJ= 0 1 −1 0 , so that det(x, y) =xJ y

    Supposexis in the interior of [−1,1] 2. LetJ= 0 1 −1 0 , so that det(x, y) =xJ y. Then ∇xΨ = 2(x−y)−3 det(x, y)J y= 0.(91) Thusx−y= 3 2 det(x, y)J y. Taking the dot product withJ y, and usingyJ y= 0, gives det(x, y) = 3 2 det(x, y)∥y∥2

  50. [50]

    Otherwise,∥y∥ 2 2 = 2/3, and then∥x−y∥ 2 2 = 3 2 det(x, y)2, so Ψ(x, y) = 2/3>0

    If det(x, y) = 0, then Ψ(x, y)≥0. Otherwise,∥y∥ 2 2 = 2/3, and then∥x−y∥ 2 2 = 3 2 det(x, y)2, so Ψ(x, y) = 2/3>0

  51. [51]

    Fixx, and suppose thatyis an interior minimizer

    Supposeyis in the interior of [−1,1] 2. Fixx, and suppose thatyis an interior minimizer. LetJ ′ = 0−1 1 0 , so that det(x, y) = yJ ′x. Then ∇yΨ = 4y−2x−3 det(x, y)J ′x= 0.(92) Taking the dot product withJ ′xgives 4 det(x, y) = 3 det(x, y)∥x∥ 2

  52. [52]

    Otherwise,∥x∥ 2 2 = 4/3, andy= 1 2 x+ 3 4 det(x, y)J ′x

    If det(x, y) = 0, then Ψ(x, y)≥0. Otherwise,∥x∥ 2 2 = 4/3, andy= 1 2 x+ 3 4 det(x, y)J ′x. Therefore∥y∥ 2 2 = ∥x−y∥ 2 2 = 1 3 + 3 4 det(x, y)2, so Ψ(x, y) = 2/3>0

  53. [53]

    Since Ψ is invariant under the symmetries of the square, we may assume thaty= (t,1), where−1≤t≤1

    The remaining case is when bothxandyare on the boundary of [−1,1] 2. Since Ψ is invariant under the symmetries of the square, we may assume thaty= (t,1), where−1≤t≤1. The pointxlies on one of the four edges of [−1,1] 2. Consider cases. 29 (a) Ifx= (s,1), then Ψ(x, y) = 1 2 2−s 2 + 2st+t 2 .(93) For fixedt, this is concave ins, so its minimum on [−1,1] occ...