{"ID":2875557,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.02526","arxiv_id":"2509.02526","title":"Reusing Samples in Variance Reduction","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.","short_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 modi...","url_abs":"https://arxiv.org/abs/2509.02526","url_pdf":"https://arxiv.org/pdf/2509.02526v1","authors":"[\"Yujia Jin\",\"Ishani Karmarkar\",\"Aaron Sidford\",\"Jiayi Wang\"]","published":"2025-09-02T17:27:33Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.OC\"]","methods":"[]","has_code":false}