Reusing Samples in Variance Reduction
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911134607474688 |
|---|---|
| author | Jin, Yujia Karmarkar, Ishani Sidford, Aaron Wang, Jiayi |
| author_facet | Jin, Yujia Karmarkar, Ishani Sidford, Aaron Wang, Jiayi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_02526 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Reusing Samples in Variance Reduction Jin, Yujia Karmarkar, Ishani Sidford, Aaron Wang, Jiayi Data Structures and Algorithms Optimization and Control 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. |
| title | Reusing Samples in Variance Reduction |
| topic | Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2509.02526 |