Reusing Samples in Variance Reduction

Yujia Jin, Ishani Karmarkar, Aaron Sidford, Jiayi Wang
Proceedings of The 37th International Conference on Algorithmic Learning Theory, PMLR 313:1-52, 2026.

Abstract

We provide a general framework to improve trade-offs between the number of _full batch_ and _sample_ queries used to solve structured optimization problems. Our results apply to a broad class of randomized optimization algorithms that iteratively solve sub-problems to high accuracy. We show that such algorithms can be modified to _reuse the randomness_ used to query the input across sub-problems. Consequently, we improve the trade-off between the number of gradient (full batch) and individual function (sample) queries for finite sum minimization, the number of matrix-vector multiplies (full batch) and random row (sample) queries for top-eigenvector computation, and the number of matrix-vector multiplies with the transition matrix (full batch) and generative model (sample) queries for optimizing Markov Decision Processes. To facilitate our analysis we introduce the notion of _pseudo-independent algorithms_, a generalization of pseudo-deterministic algorithms (Gat and Goldwasser 2011) that quantifies how independent the output of a randomized algorithm is from a randomness source.

Cite this Paper

BibTeX
@InProceedings{pmlr-v313-jin26a, title = {Reusing Samples in Variance Reduction}, author = {Jin, Yujia and Karmarkar, Ishani and Sidford, Aaron and Wang, Jiayi}, booktitle = {Proceedings of The 37th International Conference on Algorithmic Learning Theory}, pages = {1--52}, year = {2026}, editor = {Telgarsky, Matus and Ullman, Jonathan}, volume = {313}, series = {Proceedings of Machine Learning Research}, month = {23--26 Feb}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v313/main/assets/jin26a/jin26a.pdf}, url = {https://proceedings.mlr.press/v313/jin26a.html}, abstract = {We provide a general framework to improve trade-offs between the number of _full batch_ and _sample_ queries used to solve structured optimization problems. Our results apply to a broad class of randomized optimization algorithms that iteratively solve sub-problems to high accuracy. We show that such algorithms can be modified to _reuse the randomness_ used to query the input across sub-problems. Consequently, we improve the trade-off between the number of gradient (full batch) and individual function (sample) queries for finite sum minimization, the number of matrix-vector multiplies (full batch) and random row (sample) queries for top-eigenvector computation, and the number of matrix-vector multiplies with the transition matrix (full batch) and generative model (sample) queries for optimizing Markov Decision Processes. To facilitate our analysis we introduce the notion of _pseudo-independent algorithms_, a generalization of pseudo-deterministic algorithms (Gat and Goldwasser 2011) that quantifies how independent the output of a randomized algorithm is from a randomness source.} }
Endnote
%0 Conference Paper %T Reusing Samples in Variance Reduction %A Yujia Jin %A Ishani Karmarkar %A Aaron Sidford %A Jiayi Wang %B Proceedings of The 37th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Matus Telgarsky %E Jonathan Ullman %F pmlr-v313-jin26a %I PMLR %P 1--52 %U https://proceedings.mlr.press/v313/jin26a.html %V 313 %X We provide a general framework to improve trade-offs between the number of _full batch_ and _sample_ queries used to solve structured optimization problems. Our results apply to a broad class of randomized optimization algorithms that iteratively solve sub-problems to high accuracy. We show that such algorithms can be modified to _reuse the randomness_ used to query the input across sub-problems. Consequently, we improve the trade-off between the number of gradient (full batch) and individual function (sample) queries for finite sum minimization, the number of matrix-vector multiplies (full batch) and random row (sample) queries for top-eigenvector computation, and the number of matrix-vector multiplies with the transition matrix (full batch) and generative model (sample) queries for optimizing Markov Decision Processes. To facilitate our analysis we introduce the notion of _pseudo-independent algorithms_, a generalization of pseudo-deterministic algorithms (Gat and Goldwasser 2011) that quantifies how independent the output of a randomized algorithm is from a randomness source.
APA
Jin, Y., Karmarkar, I., Sidford, A. & Wang, J.. (2026). Reusing Samples in Variance Reduction. Proceedings of The 37th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 313:1-52 Available from https://proceedings.mlr.press/v313/jin26a.html.

Related Material