# Fast John Ellipsoid Computation with Differential Privacy Optimization

arXiv: https://arxiv.org/abs/2408.06395 · HTML: https://mlsanity.com/paper/2408.06395/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 71 of its 131 references that are in the map.
- First posted on arXiv 12 Aug 2024.

## Builds on (most cited first, 30 of 71)

- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Deep Leakage from Gradients](https://mlsanity.com/paper/1906.08935/) (2019)
- [Understanding Deep Image Representations by Inverting Them](https://mlsanity.com/paper/1412.0035/) (2014)
- [Split learning for health: Distributed deep learning without sharing raw patient data](https://mlsanity.com/paper/1812.00564/) (2018)
- [Evaluating Gradient Inversion Attacks and Defenses in Federated Learning](https://mlsanity.com/paper/2112.00059/) (2021)
- [Inverting Visual Representations with Convolutional Networks](https://mlsanity.com/paper/1506.02753/) (2015)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [InstaHide: Instance-hiding Schemes for Private Distributed Learning](https://mlsanity.com/paper/2010.02772/) (2020)
- [A Refined Laser Method and Faster Matrix Multiplication](https://mlsanity.com/paper/2010.05846/) (2020)
- [Solving Empirical Risk Minimization in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1905.04447/) (2019)
- [A Faster Interior Point Method for Semidefinite Programming](https://mlsanity.com/paper/2009.10217/) (2020)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Robustness Implies Privacy in Statistical Estimation](https://mlsanity.com/paper/2212.05015/) (2022)
- [Relative Error Tensor Low Rank Approximation](https://mlsanity.com/paper/1704.08246/) (2017)
- [Faster Dynamic Matrix Inverse for Faster LPs](https://mlsanity.com/paper/2004.07470/) (2020)
- [A Deterministic Linear Program Solver in Current Matrix Multiplication Time](https://mlsanity.com/paper/1910.11957/) (2019)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [A New Analysis of Differential Privacy's Generalization Guarantees](https://mlsanity.com/paper/1909.03577/) (2019)
- [A Faster Small Treewidth SDP Solver](https://mlsanity.com/paper/2211.06033/) (2022)
- [New Bounds for Matrix Multiplication: from Alpha to Omega](https://mlsanity.com/paper/2307.07970/) (2023)
- [TextHide: Tackling Data Privacy in Language Understanding Tasks](https://mlsanity.com/paper/2010.06053/) (2020)
- [Solving SDP Faster: A Robust IPM Framework and Efficient Implementation](https://mlsanity.com/paper/2101.08208/) (2021)
- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [Sketching for Kronecker Product Regression and P-splines](https://mlsanity.com/paper/1712.09473/) (2017)
- [A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path](https://mlsanity.com/paper/2011.05365/) (2020)
- [Faster Algorithm for Structured John Ellipsoid Computation](https://mlsanity.com/paper/2211.14407/) (2022)
- [Mind the Inconspicuous: Revealing the Hidden Weakness in Aligned LLMs' Refusal Boundaries](https://mlsanity.com/paper/2405.20653/) (2024)
- [More Asymmetry Yields Faster Matrix Multiplication](https://mlsanity.com/paper/2404.16349/) (2024)
- [Generalized Leverage Score Sampling for Neural Networks](https://mlsanity.com/paper/2009.09829/) (2020)

## Built on by (most cited first, 7 of 7)

- [Circuit Complexity Bounds for RoPE-based Transformer Architecture](https://mlsanity.com/paper/2411.07602/) (2024)
- [Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformers](https://mlsanity.com/paper/2412.18040/) (2024)
- [Theoretical Guarantees for High Order Trajectory Refinement in Generative Flows](https://mlsanity.com/paper/2503.09069/) (2025)
- [Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers](https://mlsanity.com/paper/2501.10688/) (2025)
- [Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method](https://mlsanity.com/paper/2408.11267/) (2024)
- [Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiency](https://mlsanity.com/paper/2503.14076/) (2025)
- [Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model](https://mlsanity.com/paper/2606.20082/) (2026)

## Abstract (arXiv)

Determining the John ellipsoid - the largest volume ellipsoid contained within a convex polytope - is a fundamental problem with applications in machine learning, optimization, and data analytics. Recent work has developed fast algorithms for approximating the John ellipsoid using sketching and leverage score sampling techniques. However, these algorithms do not provide privacy guarantees for sensitive input data. In this paper, we present the first differentially private algorithm for fast John ellipsoid computation. Our method integrates noise perturbation with sketching and leverages score sampling to achieve both efficiency and privacy. We prove that (1) our algorithm provides (ε,δ)-differential privacy and the privacy guarantee holds for neighboring datasets that are ε0-close, allowing flexibility in the privacy definition; (2) our algorithm still converges to a (1+xi)-approximation of the optimal John ellipsoid in Theta(xi-2(log(n/δ0) + (Lε0)-2)) iterations where n is the number of data point, L is the Lipschitz constant, δ0 is the failure probability, and ε0 is the closeness of neighboring input datasets. Our theoretical analysis demonstrates the algorithm's convergence and privacy properties, providing a robust approach for balancing utility and privacy in John ellipsoid computation. This is the first differentially private algorithm for fast John ellipsoid computation, opening avenues for future research in privacy-preserving optimization techniques.