Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
37,302 characters · 13 sections · 23 citation commands
PPI-SVRG: Unifying Prediction-Powered Inference and Variance Reduction for Semi-Supervised Optimization
\noindentKeywords: Prediction-Powered Inference, Stochastic Variance Reduced Gradient, Semi-supervised Learning, Variance Reduction, Control Variates, Stochastic Optimization
A central bottleneck in machine learning and statistical inference is the cost of obtaining labeled data. Reliable estimation typically requires substantial labeled samples, yet collecting labels can be expensive, slow, or ethically constrained. At the same time, many applications provide abundant unlabeled covariates and access to externally trained models that generate cheap outcome predictions.
This data landscape---scarce labels, abundant predictions---arises across domains. In remote sensing, satellite imagery is plentiful but ground-truth labels require costly field surveys jean2016combining. In clinical trials, patient outcomes take months to observe, yet prognostic models can predict responses from baseline characteristics schmidli2020beyond, rahman2021leveraging. In computational biology, protein structures were historically determined through expensive crystallography, but AlphaFold now predicts structures with near-experimental accuracy jumper2021highly. These examples share a common structure: labeled data is the bottleneck, while predictions from pre-trained models are readily available.
Prediction-Powered Inference (PPI) angelopoulos2023prediction formalizes this setting for statistical estimation. PPI uses predictions as control variates: even imperfect predictions carry information about the target, enabling lower-variance estimators. The key insight is that predictions, though potentially biased, are correlated with true outcomes. This correlation drives variance reduction through the classical control variate mechanism.
PPI was designed for statistical estimation---computing confidence intervals, testing hypotheses, and estimating population parameters. But many machine learning tasks require optimization: training models by minimizing empirical loss. Can the same control variate principle accelerate stochastic optimization?
SVRG johnson2013accelerating reduces variance in stochastic optimization through a complementary strategy: it uses a reference gradient computed at a snapshot point as a control variate, achieving linear convergence for strongly convex objectives. The snapshot gradient anchors the stochastic updates, reducing variance without introducing bias.
We observe that PPI and SVRG share the same mathematical structure: both subtract a correlated term and add back its expectation. PPI uses predictions; SVRG uses reference gradients. Despite their different origins---statistical estimation for PPI, optimization for SVRG---they implement the same variance reduction mechanism. This structural equivalence suggests a natural combination.
We develop PPI-SVRG, which combines both control variates to accelerate semi-supervised optimization. Our contributions are:
How do prediction errors affect convergence? One might expect errors to slow convergence, as in noisy gradient descent. Our analysis shows a different picture: the two contributions are additive and independent. Better predictions shrink the error floor but do not speed up the rate; worse predictions enlarge the neighborhood but do not slow it down. When predictions equal true labels ($F = Y$), the conditional variance vanishes and our bound reduces to the standard SVRG rate---confirming that PPI-SVRG generalizes SVRG.
Prediction-Powered Inference. Prediction-powered inference (PPI) angelopoulos2023prediction, angelopoulos2023ppi++, zrnic2024cross assumes access to true labels for only a subset of data, with predictions from an external model for the remainder. PPI uses predictions as control variates to reduce variance when estimating population parameters. Extensions include active label collection zrnic2024active and joint optimization of sampling and measurement ao2024predictionguided. These methods target parameter estimation---means, quantiles, regression coefficients---rather than optimization. We extend PPI to minimizing empirical loss, where the goal is finding optimal parameters rather than estimating fixed quantities.
Variance Reduction in Stochastic Optimization. SVRG johnson2013accelerating achieves faster convergence than SGD by using the full gradient at a reference point as a control variate, enabling linear convergence for strongly convex objectives. Related methods include SAGA defazio2014saga, which maintains per-sample gradient estimates, and SARAH nguyen2017sarah, which uses stochastic recursive gradients. For nonconvex objectives, SPIDER fang2018spider and PAGE li2021page achieve optimal gradient complexity. Loopless variants such as L-SVRG kovalev2020dont eliminate the outer loop. SVRG++ allenzhu2016improved handles non-strongly-convex objectives via epoch doubling; we adapt this approach in PPI-SVRG++.
Connection Between PPI and SVRG. PPI and SVRG both use control variates, but in different contexts: PPI for estimation, SVRG for optimization. Both construct an unbiased estimator by adding and subtracting a correlated auxiliary quantity. When predictions equal labels ($F = Y$), the PPI-based gradient update reduces to the SVRG update. (ref) develops this connection; (ref) derives convergence bounds.
We consider loss function $\ell_\theta (X,Y)$ with inputs $X\in\mathcal X,Y\in\{-1,+1\}$, parameterized by $\theta\in\mathbb{R}^k.$ We seek to minimize the expected loss:
Given samples $\{(X^i,Y^i)\}_{i=1}^n$, the empirical loss is
In many applications, labels are expensive but predictions from pre-trained models are cheap. When predictions $F$ are available for unlabeled data, we can augment the objective to reduce variance. Let $F(X) \in \{-1,+1\}$ denote a predictor. The augmented objective is:
where $g_\theta$ is an auxiliary function and $F^i = F(X^i)$ denotes the prediction for sample $i$. We only need labels for $n$ samples; the remaining $N$ samples require only predictions.
The simplest choice for the auxiliary function is $g = \ell$. A refined choice sets $g$ to satisfy
where the expectation is over label $Y$ conditional on input $X$ and prediction $F.$ This choice achieves semi-parametric asymptotic optimality as $n,N\to\infty$.
PPI and SVRG both achieve variance reduction through control variates. We first review SVRG, then show how PPI shares its structure.
The stochastic variance-reduced gradient descent method (SVRG) johnson2013accelerating considers optimizing the empirical loss (ref). It uses a double-loop strategy with $m$ inner steps. Let $\tilde\theta_s$ denote the parameter at outer loop $s$, and let
be the full gradient at $\tilde\theta_s$. The inner loop starts with $\theta_0 = \tilde\theta_s$ and, for $t=1,\dots,m-1$, randomly picks $i_t\in\{1,\dots,n\}$ and updates:
The outer loop then sets $\tilde \theta_{s+1}=\theta_t$ for a randomly chosen $t\in\{0,\dots,m-1\}$.
Under the standard smoothness and strong convexity assumptions:
SVRG achieves exponential convergence with rate $\alpha = 1/[\gamma\eta(1-2\lambda\eta)m]+2\lambda\eta/(1-2\lambda\eta) < 1$ johnson2013accelerating.
Prediction-Powered Inference angelopoulos2023prediction augments the empirical loss with a correction term using predictions on unlabeled data. Recall the PPI objective (ref):
The auxiliary function $g_\theta(X, F)$ satisfies the moment condition (ref): $\nabla_\theta g_\theta(X,F) = \mathbb{E}[\nabla_\theta\ell_\theta(X,Y) | X,F]$. This ensures that $\nabla_\theta g_\theta$ is an unbiased proxy for the true gradient, enabling variance reduction through the control variate mechanism.
The gradient of the PPI objective decomposes as:
When $N \gg n$, the second term has low variance---it is computed on abundant unlabeled data---and serves as a control variate for the stochastic gradient.
Consider the PPI-augmented loss (ref) with auxiliary function $g_\theta(X, F)$. Define the augmented gradient as
which can be estimated using the unlabeled data. The PPI-based update is:
When $g = \ell$ and $F = Y$, the PPI update (ref) has the same structure as the SVRG update (ref). The term $\nabla_\theta g_{\tilde\theta_s}(X^{i_t}, F^{i_t})$ becomes $\nabla_\theta \ell_{\tilde\theta_s}(X^{i_t}, Y^{i_t})$, matching SVRG, and the augmented gradient $\tilde\mu_s = \mathbb{E}[\nabla_\theta \ell_{\tilde\theta_s}(X, Y)]$ equals the full gradient used in SVRG (in the population sense).
The difference lies in the snapshot gradient $\tilde\mu_s$: SVRG uses the empirical average over $n$ labeled samples, while PPI uses the expectation estimated from $N+n$ samples with predictions.
Both updates have identical structure: subtract a correlated term and add back its expectation. When $F = Y$, the variance term in our convergence bound vanishes, recovering the SVRG rate. When $F \neq Y$, the control variate $\nabla_\theta g_{\tilde\theta_s}(X, F)$ uses predictions instead of true labels. Large unlabeled datasets reduce variance, and the convergence bound includes an additional term quantifying prediction uncertainty.
Algorithm (ref) presents PPI-SVRG, which maintains SVRG's double-loop structure but computes the snapshot gradient over both labeled and unlabeled data.
The key difference from standard SVRG is Line 5: the snapshot gradient $\tilde\mu_s$ uses all $N+n$ samples, not just the $n$ labeled samples. The inner loop (Lines 7--9) samples a labeled point at each iteration and applies update (ref), using predictions $F^{i_t}$ in the control variate. Lines 10--11 randomly select one inner iterate as the next snapshot, following standard SVRG.
When $F = Y$, Algorithm (ref) reduces to standard SVRG.
\paragraph{Intuition: Why does the control variate help?} The update (ref) can be rewritten as: \[ \theta_t = \theta_{t-1} - \eta \left[ \underbrace{\nabla\ell_{\theta_{t-1}}(X^{i_t}, Y^{i_t}) - \nabla g_{\tilde\theta_s}(X^{i_t}, F^{i_t})}_{\text{residual}} + \underbrace{\tilde\mu_s}_{\text{anchor}} \right]. \] The residual term $\nabla\ell - \nabla g$ has lower variance than $\nabla\ell$ alone when $\nabla g$ is correlated with $\nabla\ell$---this is the essence of control variates. Adding back the anchor $\tilde\mu_s$ ensures the update direction is unbiased. When $F$ is informative about $Y$, the conditional expectation $\nabla g = \mathbb{E}[\nabla\ell | X, F]$ closely tracks the true gradient, and the residual captures only the unpredictable component. The variance reduction is greatest when predictions are accurate and abundant unlabeled data makes $\tilde\mu_s$ nearly deterministic.
PPI-SVRG++ extends PPI-SVRG to general convex objectives (without strong convexity), adapting the SVRG++ framework allenzhu2016improved.
The key idea is epoch doubling: instead of a fixed inner loop length $m$, the number of inner iterations $m_s$ doubles each epoch. In strongly convex settings, fixed epoch length suffices for exponential convergence. Without strong convexity, we must balance early exploration (short epochs) with final refinement (long epochs). Setting $m_s = m_0 \cdot 2^{s-1}$ achieves $O(1/T)$ convergence, matching the optimal rate for general convex optimization.
Let $m_0$ be the initial inner loop length. For each outer loop $s=1, \dots, S$, the algorithm proceeds as follows. The epoch length is set to $m_s = m_0 \cdot 2^{s-1}$, doubling each epoch. The snapshot gradient is computed on all samples:
The inner loop initializes $\theta_0^s = \theta_{m_{s-1}}^{s-1}$ (continuing from the previous epoch's last iterate, with $\theta_0^1 = \tilde\theta_0$) and updates for $t=0, \dots, m_s-1$:
The snapshot is updated by averaging: $\tilde\theta_s = \frac{1}{m_s}\sum_{t=0}^{m_s-1} \theta_{t}^s$, ensuring optimal variance reduction as in standard SVRG++. The next epoch then starts from the last iterate: $\theta_0^{s+1} = \theta_{m_s}^s$.
With this modification, PPI-SVRG++ achieves fast convergence rates even when the objective is not strongly convex (e.g., Lasso-PPI). Algorithm (ref) presents the complete PPI-SVRG++ with epoch doubling.
Algorithm (ref) extends Algorithm (ref) in three ways. First, the epoch length doubles each epoch (Line 6). Second, the inner loop continues from the previous epoch's last iterate rather than restarting from the snapshot. Third, the snapshot is the average of all inner iterates (Line 12), not a random selection.
These modifications enable $O(1/T)$ convergence without strong convexity, whereas Algorithm (ref) requires strong convexity for exponential convergence.
We analyze the convergence of Algorithm (ref) under strong convexity. The bound decomposes into the standard SVRG rate plus a term capturing prediction uncertainty.
When $g = \theta^\top \mathbb{E}_{}\left[\ell|X,F\right]$, we have the following result.
The first term, $\alpha^s\mathbb{E}[L_{\tilde\theta_{0}}^n-L_{\theta_{\star}}^n]$, is the standard SVRG rate---exponential decay with $\alpha < 1$, identical to johnson2013accelerating. The second term captures prediction uncertainty: $\operatorname{Var}(\nabla_\theta\ell_{\theta_\star}(X,Y) | X, F)$ measures the gradient information that remains hidden after observing the prediction $F$.
When $F = Y$, the conditional variance vanishes because $Y$ is determined by $(X, F)$: \[ \operatorname{Var}\left({\nabla_\theta\ell_{\theta_\star}(X,Y) \,\big|\, X, F=Y}\right) = 0. \] The bound (ref) then reduces to the standard SVRG bound: \[ \mathbb{E}[L_{\tilde\theta_{s}}^n-L_{\theta_{\star}}^n] \le \alpha^s\mathbb{E}[L_{\tilde\theta_{0}}^n-L_{\theta_{\star}}^n]. \] This confirms that PPI and SVRG share the same control variate structure.
The bound interpolates between two extremes. Perfect predictions ($F = Y$) recover the SVRG rate. Imperfect predictions cause convergence to a neighborhood whose size depends on prediction quality---better predictions shrink this neighborhood, but the exponential rate $\alpha$ remains unchanged. The two contributions are additive and independent: $\alpha$ depends only on loss geometry $(\lambda, \gamma, \eta, m)$, while the error floor depends only on how informative $F$ is about $Y$. This separation ensures stability---the algorithm never diverges due to poor predictions; it simply converges to a larger neighborhood.
The auxiliary function $g_\theta(X,F) = \mathbb{E}[\ell_\theta(X,Y) \mid X, F]$ makes $\ell_\theta - g_\theta$ have zero conditional mean given $(X, F)$. This allows the law of total variance to decompose the gradient variance into optimization and prediction components. The residual variance is exactly $\operatorname{Var}(\nabla\ell_\theta | X, F)$---the gradient uncertainty that remains after observing the prediction.
Proof sketch. Decompose the variance of the update direction $v_t$ into two components: one depending on distance to the optimum (as in SVRG), one capturing prediction uncertainty. The first is bounded via smoothness, following standard SVRG analysis. For the second, since $\nabla_\theta g_\theta(X,F) = \mathbb{E}[\nabla_\theta \ell_\theta(X,Y) | X,F]$, the residual variance equals the conditional variance given predictions. Summing over iterations and applying the total variance formula yields the bound. See (ref) for details.
We extend the analysis to general convex objectives using Algorithm (ref).
Note that $\sigma_{PPI}^2 = \max_\theta \mathrm{Var}(\nabla\ell_\theta | X, F)$, since $\nabla g = \mathbb{E}[\nabla\ell | X, F]$. This upper bounds the variance at the optimum appearing in Theorem (ref).
PPI-SVRG++ converges at $O(1/T)$ to a prediction-dependent error floor, matching the optimal rate for smooth convex optimization. The error floor $O(\eta \sigma_{PPI}^2)$ shrinks with more accurate predictors (smaller $\sigma_{PPI}$) or larger unlabeled datasets (smaller $\epsilon_{bias}$).
We evaluate PPI-SVRG on two tasks: mean estimation under label scarcity, and deep learning with limited supervision. PPI-SVRG reduces MSE by 43--52% under label scarcity ($\gamma=0.1$) on the mean estimation tasks and improves test accuracy by 2.7--2.9 % on MNIST.
We consider estimating the population mean $\theta_\star = \mathbb{E}[Y]$ using a small labeled set and a large pool of predictions. We compare three methods: Naive (labeled data only), PPI, and PPI-SVRG (Algorithm (ref)).
We use two datasets from the PPI benchmark angelopoulos2023prediction: forest for deforestation in the Amazon Rainforest ($n=160$ labeled, $N=1{,}436$ unlabeled), and galaxies for galaxy morphology classification ($n=1{,}674$ labeled, $N=15{,}069$ unlabeled). We obtain calibrated predictions via CatBoost prokhorenkova2018catboost with 5-fold cross-fitting to ensure predictor independence from labeled samples (details in Appendix (ref)). For each labeled proportion $\gamma \in \{0.1, 0.2, 0.3, 0.4, 0.5\}$, we perform 200 Monte Carlo repetitions and report MSE, 95% CI width, and coverage probability.
Figures (ref) and (ref) show that PPI-SVRG achieves lower MSE and narrower confidence intervals than both Naive and PPI, while maintaining valid coverage. The gains are largest under label scarcity: at $\gamma=0.1$, PPI-SVRG reduces MSE by 52.1% (forest) and 43.4% (galaxies) relative to PPI. This aligns with Theorem (ref): the convergence bound depends on the conditional variance $\mathbb{E} \left[ \operatorname{Var} \left( \nabla_{\theta} \ell_{\theta_*} \,\middle|\, X, F \right) \right]$, which calibrated predictions reduce.
Some patterns stand out. First, the relative improvement decreases as $\gamma$ increases: at $\gamma=0.5$, MSE reduction drops to 46.41% (forest) and 19.98% (galaxies). This is expected as abundant labeled data already yields low-variance baselines, leaving less room for improvement. Second, PPI-SVRG exhibits relatively high coverage probability across both datasets with greater stability than PPI, and stays closest to the nominal 95% level on galaxies. Naive tends to over-cover on forest but under-covers on galaxies; PPI occasionally under-covers at small $\gamma$.
We apply PPI-SVRG to semi-supervised image classification on MNIST using DeepOBS benchmark suite schneider2019deepobs. Note that PPI is not included as a baseline: PPI targets statistical estimation (e.g., computing population means or confidence intervals), not optimization. Standard SVRG, conversely, is an optimization algorithm that cannot leverage unlabeled data. PPI-SVRG bridges this gap---it applies variance reduction to optimization while using predictions on unlabeled data.
We split the 60K MNIST training set into two parts: 30K for training a predictor (2C2D architecture, 99.16% test accuracy), and 30K for the main experiment, of which only 10% (3K) have labels. The student model is an MLP. We compare Baseline (Adam/Momentum) against PPI-SVRG variants using the same optimizer. All methods train for 50 epochs with batch size 256 over 5 random seeds (implementation details in Appendix (ref)).
Figure (ref) shows validation and test metrics across training. PPI-SVRG initially underperforms (weak correlation between snapshot and current parameters) but surpasses baselines as training progresses and variance reduction takes effect. The learning curves reveal three phases. In the warm-up phase, PPI-SVRG trails baselines. The snapshot gradient $\tilde{\mu}_s$ is computed at the previous epoch's parameters, which poorly approximate the current gradient when parameters change rapidly. The ramp-up coefficient $\lambda_u(t)$ (Appendix (ref)) mitigates this by down-weighting the control variate early on. In the transition phase, the gap narrows as parameters stabilize. The snapshot becomes a better anchor. In the steady-state phase, PPI-SVRG dominates. Variance reduction takes over, and the large unlabeled dataset ($N=27$K vs.\ $n=3$K) provides a nearly deterministic snapshot gradient.
Table (ref) reports final test accuracy with 95% confidence intervals. PPI-SVRG-Momentum improves over Baseline-Momentum by +2.69 %; PPI-SVRG-Adam improves over Baseline-Adam by +2.94 %. These gains are consistent across seeds and orthogonal to the choice of optimizer, confirming that the benefit stems from improved gradient estimation rather than optimizer-specific effects.
The strong predictor ($F$ with 99.16% accuracy) ensures that $\nabla_\theta g_\theta(X,F) \approx \mathbb{E}[\nabla_\theta \ell_\theta(X,Y) \mid X,F]$, enabling effective variance reduction. As $N \gg n$, the snapshot gradient $\tilde{\mu}_s$ has low variance, providing a stable anchor for the control variate correction.
These results validate Theorem (ref). First, the rate is preserved: PPI-SVRG and baselines both reach near-final performance by around 200 iterations, but PPI-SVRG converges to a better solution. This matches the theorem---$\alpha$ is independent of prediction quality. Second, the error floor shrinks with better predictions: the near-perfect predictor (99.16% accuracy) yields small $\mathrm{Var}(\nabla\ell | X, F)$, explaining the +2.7--2.9 pp gains. Third, the algorithm remains stable even when the control variate is misaligned (warm-up phase): the additive structure of the bound ensures PPI-SVRG does not diverge but simply converges more slowly. For practitioners, two guidelines emerge: PPI-SVRG benefits most from large unlabeled datasets ($N \gg n$) and accurate predictors; and patience is required during warm-up while early stopping at beginning stage would incorrectly favor baselines.
PPI and SVRG both reduce variance through control variates. We combined them into PPI-SVRG, with convergence bounds that decompose into optimization error and prediction error. The rate $\alpha$ depends on loss geometry; predictions affect only the neighborhood size. Poor predictions enlarge the neighborhood but do not cause instability. Experiments confirm this: PPI-SVRG reduces MSE by 43--52% under label scarcity ($\gamma=0.1$) on the forest and galaxies datasets, and improves test accuracy by 2.7--2.9 percentage points on MNIST.
The experiments show three patterns. First, improvements are largest under label scarcity: at 10% labeled data, PPI-SVRG achieves over 50% MSE reduction, while the gap narrows at higher labeled proportions. Second, the method requires a warm-up phase in deep learning: PPI-SVRG initially underperforms baselines (epochs 1--10) before surpassing them once parameters stabilize. Third, predictor quality matters: higher-correlation predictors yield larger gains, as reflected in the conditional variance term of Theorem (ref).
Two limitations: (i) PPI-SVRG requires predictions on unlabeled data, so its benefits diminish when predictions are unavailable or poorly calibrated; (ii) highly inaccurate predictors provide limited variance reduction, though the algorithm remains stable.
Future work could extend PPI-SVRG to non-convex objectives, develop adaptive step size and epoch length selection, explore combinations with SAGA or momentum-based methods, and investigate automatic warm-up scheduling based on snapshot-parameter correlation.