Ittai Rubinstein
Email: ittai.rubinstein@gmail.com
Hi!
I am a fourth-year PhD student at MIT advised by Sam Hopkins and supported by the MathWorks EECS Fellowship.
I study how training data affects a model’s behavior, with a focus on data attribution, robust statistics, privacy, credit assignment, and machine unlearning.
Before MIT, I led a research team at Qedma working on quantum error mitigation. I received my master’s degree in computer science from Tel Aviv University, where I was advised by Muli Safra, and completed my undergraduate studies in mathematics, physics, and computer science at the Technion.
Data attribution asks how would this model’s behavior change if it were trained on a different training set? It is used in a variety of applications including credit assignment, safety, and interpretability. Influence functions (IF) are efficient and additive, while single Newton steps (NS) are often much more accurate in practice (Koh, Ang, Teo, and Liang 2019), which raises the questions:
Problem Statement. Fix a data universe 𝒰 and training algorithm θ(·). Additionally, let ℓ : 𝓜 → ℝk be an arbitrary measurement function mapping models to real-valued vectors.
The goal of a predictive data attribution method is to output a function f̂ (called a datamodel) such that, for any possible training dataset S ⊂ 𝒰,
We also want the datamodel f̂(S) to be much faster to compute than the training algorithm itself (so that ℓ(θ(·)) itself is not a valid predictive data attribution method).
Source: the ICML 2024 Data Attribution Tutorial.
Influence functions. IF is based on taking a first-order approximation to the effect of downweighting a set of samples and extrapolating to the case of fully removing these samples:
Here H is the Hessian of the loss and gi is the gradient of the ith sample, both evaluated at θ̂. IF is additive: the effect of removing a set of samples is the sum of the effects of removing each sample individually, and it has relatively low query complexity since only a single Hessian inversion is needed.
Single Newton step. NS is based on taking a single Newton step of the new loss function:
The only difference is that NS takes the Hessian HT of the new loss. This seemingly minor detail loses us the additivity of IF and comes at a significant cost to query complexity, but it also makes the predictions of NS much more accurate in practice.
Influence functions are fast and additive, but they often underestimate the effect of removing training samples -- especially in high-dimensional settings. We introduce Rescaled Influence Functions (RIF), a drop-in replacement that incorporates the change in the Hessian caused by removing each individual sample. RIF preserves the additive structure of IF and, for generalized linear models, can be computed with negligible overhead. Across vision, language, and audio datasets, RIF substantially improves prediction accuracy, nearly matching the accuracy of the more expensive Newton-step approximation.
Predicted vs. actual data-attribution effects on training loss. Each point represents the effect of removing a subset of the training data; the horizontal axis is the predicted increase in train-set loss and the vertical axis is the actual increase after retraining. Points close to the y = x line have good predictive value. IF is clearly positively correlated with the actual effect, but badly misses its scale. NS is much more accurate, while RIF nearly matches NS at negligible overhead to IF.
Now that we have seen empirically that NS is more accurate than IF, this leaves the question: why is NS more accurate? Previous analyses of the accuracy of NS relied on global convexity conditions that often do not hold in practice, making it hard to derive concrete error bars on this approximation. So beyond the scientific goal of explaining our experimental observation, we wish to derive error bars that can be used in down-stream applications like unlearning.
We give the first analysis of the accuracy of NS that does not rely on global strong convexity. Instead, we show that it is enough for the loss to be well-behaved only near the first Newton step. For logistic regression, we give the first asymptotically tight bound on the NS error and the first theoretical explanation for the observed accuracy of NS.
Proof idea for the Newton-step error bound. Lipschitzness of the Hessian along the first Newton step gives a concrete bound on the gradient at the Newton-step point. The remaining challenge is to turn a bound on the gradient norm into a bound on the distance to a minimizer without assuming global convexity. The diagram illustrates how we do this: we show that in the outer ring, the loss-gradient vector field points inward toward the Newton step, so a minimizer cannot lie in that ring and must lie in the smaller inner region.
As our lives become more entwined with increasingly complex statistical models, the goal of protecting our privacy becomes ever more important. However, despite decades of research we still do not have good tools to preserve the privacy of individuals when training even the most basic of models. Motivated by this, we study the fundamental problem of private linear regression:
How can we release a useful regression model trained on sensitive data while protecting every individual represented in the dataset?
Differential privacy (DP), introduced by Dwork, Kenthapadi, McSherry, Mironov, and Naor in 2006, has emerged as the gold standard for privacy. However, despite nearly two decades of work, the best private mechanisms for even the simplest learning tasks such as mean estimation or linear regression lag significantly behind their non-private counterparts.
Roughly speaking, a mechanism ℳ is (ε,δ)-private, if with probability 1−δ, ℳ reveals at most ε bits of information about any individual training point. If our learning algorithm is robust — i.e., if no single sample can affect the model too much — then we can make it private by adding enough noise to mask the effect of each individual sample. In fact, this relationship cuts both ways and robustness is also a requisite for privacy.
Informal: A mechanism is (ε,δ)-private ⇒ is robust to k ≈ log(δ−1) / ε adversarial sample changes.
Unfortunately, OLS is not robust to even a single adversarial change, since an adversary can add an extreme outlier that completely rewrites the optimal linear model. Liu, Jain, Kong, Oh, and Suggala 2023 propose using a private variant of SGD, where large gradients are clipped and noise is added at every epoch, but this comes at a significant cost to accuracy if the data is not isotropic. Brown, Hayase, Hopkins, Kong, Liu, Oh, Perdomo, and Smith 2024 improve upon this with a clipping strategy that adapts to the geometry of the data, but then need to ensure that private information is not leaked through the clipping process itself, requiring a significant sample overhead even for mild privacy parameters. Finally, Anderson, Bakshi, Majid, and Tiegel 2025 utilize the Sum-of-Squares based robust regression of Bakshi and Prasad 2021, but this comes at both a significant computational overhead and a sample complexity that is quadratic in the dimension.
Our main contribution is showing that a much milder notion of robustness suffices to construct a private estimator:
Theorem 1 (Informal). For any learning algorithm 𝒜, if we can efficiently test the robustness of 𝒜 to the removal of samples from its training set, we can privatize 𝒜.
This yields the first efficient private regression algorithm whose sample complexity is linear in the dimension and the privacy parameters, and does not scale with the condition number of the features.
Subsample–Test–Aggregate. Starting from the original corrupted dataset, the algorithm draws small random subsamples, tests each subsample for outliers, and aggregates only the estimates from subsamples that pass the test. Input inliers are shown in black and outliers in red; failed subsamples are greyed out and crossed out, white circles denote the empirical means of accepted subsamples, and the black star denotes the final aggregate. In STA, we also add noise to the estimator before release; we omit that step here for simplicity.
To enable our approach to private regression we still need some method of efficiently certifying whether OLS is robust to removing a small number of samples. Previous approaches based only on leverages and residuals (such as Allen 1974) and Sum-of-Squares methods (such as Freund and Hopkins 2023) yield sufficiently strong bounds only when the number of samples is much higher than the dimension of the data. We show that the relatively simple addition of "cross-leverages" suffices to prove substantially stronger robustness guarantees than the traditional checks of just leverages and residuals.
Private Linear Regression via a Down-Sensitivity to Privacy Reduction
Ittai Rubinstein, Chris Ge, Samuel Hopkins
COLT 2026
[PMLR]
On the Accuracy of Newton Step and Influence Function Data Attributions
Ittai Rubinstein, Sam Hopkins
ICML 2026, Spotlight
[arxiv]
Rescaled Influence Functions: Accurate Data Attribution in High Dimension
Ittai Rubinstein, Sam Hopkins
NeurIPS 2025
[arxiv] | [github]
Robustness Auditing for Linear Regression: To Singularity and Beyond
Ittai Rubinstein, Sam Hopkins
ICLR 2025
[arxiv] | [github]
Reliable High-Accuracy Error Mitigation for Utility-Scale Quantum Circuits
Dorit Aharonov, Ori Alberton, …, Ittai Rubinstein, …, Assaf Zubida, Netanel H. Lindner
Preprint
[arxiv] | [media]
The Quasi-Probability Method and Applications for Trace Reconstruction
Ittai Rubinstein
SOSA 2025
[arxiv]
Improved Upper and Lower Bounds on the Capacity of the Binary Deletion Channel
Ittai Rubinstein, Roni Con
ISIT 2023
[arxiv]
Average-Case to (shifted) Worst-Case Reduction for the Trace Reconstruction Problem
Ittai Rubinstein
ICALP 2023
[arxiv]
Explicit and Efficient Construction of (nearly) Optimal Rate Codes for the Binary Deletion Channel and the Poisson Repeat Channel
Ittai Rubinstein
ICALP 2022
[arxiv]
Multivariate Generating Functions for Information Spread on Multi-Type Random Graphs
Yaron Oz, Ittai Rubinstein, Muli Safra
JSTAT 2022
[arxiv]
Heterogeneity and Superspreading Effect on Herd Immunity
Yaron Oz, Ittai Rubinstein, Muli Safra
JSTAT 2021
[arxiv]
Superspreaders and High Variance Infectious Diseases
Yaron Oz, Ittai Rubinstein, Muli Safra
JSTAT 2021
[arxiv]
Deep Learning Reconstruction of Ultrashort Pulses from 2D Spatial Intensity Patterns Recorded by an All-in-Line System in a Single-Shot
Ron Ziv, Alex Dikopoltsev, Tom Zahavy, Ittai Rubinstein, Pavel Sidorenko, Oren Cohen, Mordechai Segev
Optics Express 2020
[arxiv]