Pith. sign in

REVIEW 4 major objections 5 minor 1 cited by

Reusing Samples in Variance Reduction

T0 review · 4 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Reusing random samples across solver iterations cuts sample queries by an n_outer factor in several optimization problems.

desk verdict Novel and useful sample-reuse framework, but the load-bearing Lemma 2.12 is wrong as written—likely fixable, so the paper deserves revision rather than rejection. read the letter →

arxiv 2509.02526 v1 pith:2OR5EG7Y submitted 2025-09-02 cs.DS math.OC

Yujia Jin , Ishani Karmarkar , Aaron Sidford , Jiayi Wang This is my paper · ORCID
classification cs.DSmath.OC MSC 68Q2568W2090C25
keywords samplereusepseudo-independencevariancereductionquerycomplexityfinite-summinimizationpseudo-determinismbatch-sampletrade-off
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that a wide class of variance-reduction algorithms can be modified to reuse the same random samples across all outer-loop iterations, cutting total sample queries by a factor equal to the number of iterations, without sacrificing correctness. This matters because it improves the best-known trade-off between expensive full-batch queries and cheap individual-sample queries for finite-sum minimization, top-eigenvector computation, matrix games, and Markov decision processes. The central mechanism is a new notion called pseudo-independence, which quantifies when a randomized sub-solver's output is nearly oblivious to its sample randomness once a small amount of uniform noise is added.

What carries the argument

The central object is the notion of pseudo-independence (Definition 2.5): a randomized algorithm A_{xi,chi} is (epsilon,delta)-pseudo-independent of its oblivious seed xi if there exists a smoothing algorithm that, for most draws of xi, produces a distribution within total variation distance epsilon of the original algorithm. The paper proves that adding uniform noise of width tau makes any high-accuracy sub-solver pseudo-independent, and then shows that repeated compositions of pseudo-independent algorithms have TV distance bounded by 2T(delta+epsilon), which yields the sample-reuse guarantee.

What would settle it

One could compute, for a small example (e.g., p=2, a sub-solver with deterministic output), the exact total-variation distance between the distribution of the noisy sub-solver conditioned on a fixed seed and the smoothing distribution, and compare it to the bound eta'/(2*tau) claimed in Theorem 2.12; if it exceeds the bound by a factor proportional to p, the theorem's guarantee is not established as stated.

Watch

Extended reading notes

Core claim

The paper establishes that if an outer-solver is robust to bounded random noise and the sub-solver queries samples obliviously and solves to high accuracy, then the same sample randomness can be reused across all n_outer sub-problem solves. Formally, Theorem 2.6 shows that the sample-reusing version outputs a correct solution with probability 1 - O($n_outer^{2}$ * delta), reducing sample queries by a factor of n_outer. For finite-sum minimization this yields O~tilde($\sqrt$($\alpha$/mu)) batch queries and O~tilde(L/$\alpha$) sample queries for any $\alpha$ >= mu, improving on the prior O~tilde(L/$\sqrt$(mu $\alpha$)) sample bound. The same framework yields improvements for discounted and average-reward MDPs, ell2-ell2 and ell2-ell1 matrix games, and top-eigenvector computation.

Load-bearing premise

The main load-bearing premise is that adding uniform noise of width tau = eta'/(2*epsilon) makes the noisy sub-solver (epsilon, delta)-pseudo-independent; the proof's total-variation bound may omit a factor of the dimension p, so the stated pseudo-independence guarantee may require rescaling in high dimensions.

Editorial extensions

If this is right

  • Finite-sum minimization can be solved with O~tilde(sqrt(alpha/mu)) full-batch queries and only O~tilde(L/alpha) sample queries, a strictly better trade-off than prior work for any alpha >= mu.
  • Generalized linear model regression can be solved reusing the same cached samples across all outer iterations, which may reduce memory retrieval and communication costs in distributed settings.
  • Discounted MDPs can be solved by a new Proximal Reward Method (PRM) that reduces a gamma-discounted problem to a sequence of gamma'-discounted problems, yielding a faster runtime in sparse-transition regimes.
  • ell2-ell2 matrix games are solvable in O~tilde(||A||_F^{2/3} epsilon^{-2/3}) matrix-vector queries, which is near-optimal due to known lower bounds.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The pseudo-independence framework could plausibly extend to non-oblivious sample queries if the sub-solver's adaptive randomness is also smoothed, though the paper only handles the oblivious case.
  • The improved sample-reuse trade-off for FSM suggests that the information-theoretic lower bound for sample complexity may need to be re-examined in the batch-sample model, since prior lower bounds do not account for sample reuse.
  • The PRM outer-solver for DMDPs may be applicable beyond variance reduction, e.g., to policy-gradient methods that solve lower-discount subproblems, though the paper does not explore this direction.
  • The numerical-stability variant in Appendix A suggests the framework can be implemented in finite precision with only a constant-factor degradation in the noise parameters, which is worth verifying empirically.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper proposes a general framework for reusing oblivious sample randomness across the outer iterations of variance-reduction algorithms. It introduces a notion of pseudo-independence and claims that adding uniform noise to a high-accuracy sub-solver makes the sub-solver pseudo-independent, so the same sample queries can be reused across n_outer sub-problem solves. The framework is applied to finite-sum minimization, discounted and average-reward MDPs, matrix games, and top-eigenvector computation, yielding improved full-batch/sample query trade-offs. A new outer-solver for discounted MDPs (the Proximal Reward Method) is also presented. The main technical engine is Theorem 2.6, which relies on Theorem 2.12 to convert a high-accuracy approximation into a pseudo-independent algorithm.

Significance. If correct, the sample-reuse framework would be a valuable and versatile contribution: it gives improved query-complexity trade-offs across several important optimization problems, and the PRM outer-solver for discounted MDPs has independent interest. The reductions in Sections 3-7 are mostly clean and build carefully on prior work; the pseudo-independence definition is a useful conceptual generalization of pseudo-determinism. However, the central technical lemma, Theorem 2.12, is false as stated, and the proof of Theorem 2.6 is therefore not established. Because every application theorem invokes Theorem 2.6, the claimed results are conditional on a repair of this lemma. The framework appears potentially repairable, but the required changes affect the definition of the approximation condition and the noise scaling, so the paper needs substantial revision before the results can be accepted.

major comments (4)
  1. [§2.3, Theorem 2.12] The total-variation calculation in the proof of Theorem 2.12 is incorrect. For a realization y with ||y - f(u)||_∞ ≤ η', the laws of A_{ξ=s,χ=c}(u) + e and f(u) + e are p-dimensional uniform distributions on cubes of side 2τ shifted by y - f(u). Their total-variation distance is 1 - ∏_{i=1}^p (1 - |(y-f(u))_i|/(2τ)), which is at least 1 - (1 - η'/(2τ))^p ≈ p·η'/(2τ), not at most (η'/(2τ))^p. With the stated choice τ = η'/(2ε), this gives roughly pε-pseudo-independence, not (ε,δ)-pseudo-independence. Since Theorem 2.6 invokes Theorem 2.12 with ε = δ, the main sample-reuse theorem is not established as written.
  2. [§2.1, Definition 2.1 and Theorem 2.12] The proof of Theorem 2.12 uses Eq. (1), a joint probability over (ξ,χ), to conclude that for 1-δ of realizations of ξ the law of A_{ξ,χ}+e is within TV distance ε of the smoothing. Joint small failure probability does not imply small failure probability for most realizations of ξ. Concretely, take p = 1, f ≡ 0, δ = ε = 0.2, η = 1, η' = 0.2, τ = 0.5, Dξ = Dχ = Unif[0,1], and A = 1 if ξ ≤ 0.4 and χ ≤ 0.5, and A = 0 otherwise. Then P_{ξ,χ}(|A-f| > 0.2) = 0.2, so A is an (η',δ)-approximation, but for every ξ ≤ 0.4 the law of A+e is a 1/2 mixture of a uniform on [0.5,1.5] and Unif[-0.5,0.5], which is TV distance 0.5 from Unif[-0.5,0.5]. Hence P_ξ(TV ≤ 0.2) = 0.6 < 0.8, and Theorem 2.12 is false as stated. A per-ξ high-probability condition or an amplification of the failure probability is needed; neither appears in the manuscript.
  3. [Appendix A, Theorem A.1] The finite-precision version in Theorem A.1 repeats the two defects of Theorem 2.12. The claimed bound involving (⌈η/β⌉/⌊2t/β⌋)^p is again the wrong order: the relevant total-variation distance is at least a constant times p·η/t, and the inference from the joint approximation in Eq. (1) to a statement holding for 1-δ of realizations of ξ is not justified. Since Theorem A.1 is the implementable version of the construction, it must be corrected together with Theorem 2.12.
  4. [§4.2, Theorem 4.11 and Lemma 4.22] The proof of Theorem 4.11 applies Lemma 4.22 with η = ε/2 · (1-γ)/(1-γ') and then concludes 0 ≤ v⋆ - ε/2 1 ≤ v_{nouter}. However, the 'Consequently' part of Lemma 4.22 yields final error ε for this choice of η, because the lemma's condition is η ≤ (1-γ)/(2(1-γ')) ε_L and taking ε_L = ε makes the condition hold. Moreover, the full bound in Lemma 4.22 contains the positive term ((γ-γ')/(1-γ'))^T max(v⋆ - v(0)) in addition to the η-sum, which the proof bounds only by ε/2. Since v(0) = 0 and v⋆ is generally nonzero, the displayed conclusion 0 ≤ v⋆ - ε/2 1 ≤ v_{nouter} does not follow. The accuracy parameter ε' or the loop length must be adjusted, and this affects the correctness proof of the DMDP trade-off in Theorem 4.13.
minor comments (5)
  1. [§2.3, Definition 2.13, Eq. (4)] In the definition of H^1_Abar, the right-hand side should be ζ(u, Abar_{χ'}(u)), not ζ(Abar_{χ'}(u)); the first argument u is missing.
  2. [Appendix B, Lemma B.2, base case] In the base case, the second argument inside the second total-variation distance is written as ζ(u, A_{ξ=s,χ}(u)); it should be ζ(u, Abar_χ(u)).
  3. [§5.2.2, Theorem 5.15] The theorem states that the algorithm uses sample queries of Type II, but the preceding text and the VRMD2 description say that the oblivious queries are row/column queries, which are Type I. The statement should say Type I.
  4. [§7, Theorem 7.7] The statement says 'For λ ≥ μ', but μ is not defined in the TopEV section; it should either be defined or replaced by the appropriate strong-convexity parameter, likely ρ ≥ λ' - λ1.
  5. [§2.3, Theorem 2.12 proof] In the proof, the naming of the random seeds is confusing: the theorem uses χ' as the concatenated seed, but the proof defines a new A_{ξ,χ} with χ = (χ',ν). Please rename the variables to avoid ambiguity.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the sample-reuse framework is a new composition argument whose premises are proved in-text; the paper's self-citations are independent prior work, not unverified assumptions of the target results.

full rationale

The paper's central claim (Theorem 2.6) is not derived from its own conclusion. It is obtained by combining three genuinely new ingredients: the definition of pseudo-independence (Definition 2.5), a construction showing that adding uniform output noise to a high-accuracy sub-solver induces pseudo-independence (Theorem 2.12), and a total-variation composition bound for reuse versus fresh-seed loops (Theorem 2.14). Each of these is proved in the manuscript or its appendices, and none of them assumes the target query-complexity improvement. The framework is then instantiated on sub-solvers and outer-solvers (APP/SVRG, TVRVI, VRMD1/2, PDFSM) whose guarantees are cited from prior published work. The self-citations, including [7], [26], [27], and [28], are used as black-box subroutines with independent derivations; they are not used to assert the paper's own conclusions. No fitted parameter is renamed as a prediction, no result is assumed by definition, and no uniqueness or ansatz is imported from the authors' prior work to force the framework's choice. The most serious concern in the manuscript, a possible gap in the total-variation calculation in the proof of Theorem 2.12, is a correctness issue rather than a circularity: the theorem's statement is not identical to an input assumption, and the downstream claim does not reduce by construction to a fitted value or to a self-citation. Consequently, no specific circular step can be exhibited.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

Everything the central claim rests on is either standard math, prior variance-reduction results (some self-cited), or the oracle model. The sample-reuse theorem itself is derived via new pseudo-independence definitions and does not reduce to the target results. The main concern is the dimension factor in the TV proof, not the ledger.

free parameters (4)
  • trade-off parameter alpha (also called lambda in FSM) = chosen by user, e.g., alpha >= mu
    User-selected parameter controlling the full-batch versus sample query trade-off; not fitted to data, but a free parameter in the trade-off.
  • sub-solver accuracy eta' = set to min(eta/2, eta*delta)
    Set by Theorem 2.6 from the robustness level eta and failure probability delta.
  • noise width tau = eta'/(2*delta) in Theorem 2.6, eta'/(2*epsilon) in Theorem 2.12
    Determined by the pseudo-independence construction; the dimension p may require rescaling.
  • DMDP discount factor gamma' = chosen with 0 < gamma' < gamma
    Trade-off and runtime parameter in the Proximal Reward Method.
assumptions (6)
  • domain assumption SVRG solves FSM sub-problems to high accuracy with O-tilde(L/lambda) sample queries and O-tilde(1) batch queries.
    Restated from Theorem 3.7, citing [16,29]; used in Lemmas 3.8 and 3.10.
  • domain assumption TVRVI solves DMDP sub-problems to l-infinity accuracy with O-tilde((1-gamma')^{-2}) sample queries.
    Restated from Theorem 4.12, citing [28], a prior work by the same authors; used in Theorem 4.13.
  • domain assumption Conceptual proximal point is l-infinity robust for minimax problems.
    Theorem 5.4 restates Proposition 4 of [7,36]; used for matrix games.
  • domain assumption The sample query oracle reveals a component function fully, so its gradient can be computed at any future point.
    Definitions 3.2 and 3.3 define this stronger oracle model, which is what makes sample reuse meaningful.
  • standard math Standard probability and linear algebra facts, including total variation distance properties.
    Used throughout the proofs, e.g., Fact B.1, Holder's inequality.
  • domain assumption High-accuracy sub-solvers have at most polylogarithmic complexity in error and failure parameters.
    Used to absorb the polynomial blowups from Theorem 2.6 into O-tilde notation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Reusing Samples in Variance Reduction." pith.science (2026). https://pith.science/paper/2OR5EG7Y

@misc{pith2026250902526,
  author       = {Pith},
  title        = {Pith review of: Reusing Samples in Variance Reduction},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2OR5EG7Y}},
  note         = {Machine review of arXiv:2509.02526}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2509.02526 by the authors.

Figure 1
Figure 1. Sample reuse framework. The diagram summarizes our approach for replacing Standard Sub-Solvers with a Sample Reusing Sub-Solver, which reuses the same sample queries across all nouter iterations of the Outer-Solver. In (2), TV abbreviates total variation distance. by much—as measured by total variation (TV) distance. To facilitate our proof of this fact, we describe and analyze a new notion of pseudo-independence of… view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Solving Zero-Sum Games with Fewer Matrix-Vector Products

    math.OC 2025-09 accept novelty 8.0 of 10

    A deterministic algorithm computes an epsilon-approximate Nash equilibrium in zero-sum games using O~(epsilon^{-8/9}) matrix-vector oracle queries, improving the 20-year-old O~(epsilon^{-1}) bound.

Reference graph

Works this paper leans on

46 extracted references · 42 canonical work pages · cited by 1 Pith paper

  1. [1]

    A lower bound for the optimization of finite sums

    Alekh Agarwal and Leon Bottou. A lower bound for the optimization of finite sums. In 32nd International Conference on Machine Learning (ICML) , 2015

    work page 2015

  2. [2]

    Optimization algorithms for faster computa- tional geometry

    Zeyuan Allen-Zhu, Zhenyu Liao, and Yang Yuan. Optimization algorithms for faster computa- tional geometry. In 41st International Colloquium on Automata, Languages and Programming (ICALP), 2014

    work page 2014

  3. [3]

    Near instance-optimality in differential privacy

    Hilal Asi and John C Duchi. Near instance-optimality in differential privacy. In Advances in Neural Information Processing Systems 33 (NeurIPS) , 2020

    work page 2020

  4. [4]

    Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds

    Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds. In 54th Annual ACM Symposium on Theory of Computing (STOC) , 2022

    work page 2022

  5. [5]

    Approximate policy iteration: A survey and some new methods

    Dimitri P Bertsekas. Approximate policy iteration: A survey and some new methods. In Journal of Control Theory and Applications , 2011

    work page 2011

  6. [6]

    Lower Bounds for Pseudo-Deterministic Counting in a Stream

    Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, and Shay Sapir. Lower bounds for pseudo-deterministic counting in a stream. arXiv preprint arXiv:2303.16287 , 2023

    work page Pith review arXiv 2023

  7. [7]

    Variance reduction for matrix games

    Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian. Variance reduction for matrix games. Advances in Neural Information Processing Systems 32 (NeurIPS) , 2019

    work page 2019

  8. [8]

    Maximum flow and minimum-cost flow in almost-linear time

    Li Chen, Rasmus Kyng, Yang P Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS) , 2022

    work page 2022

Show all 46 references
  1. [9]

    On adaptive distance estimation

    Yeshwanth Cherapanamjeri and Jelani Nelson. On adaptive distance estimation. In Advances in Neural Information Processing Systems , 2020

    2020

  2. [10]

    One attack to rule them all: Tight quadratic bounds for adaptive queries on cardinality sketches

    Edith Cohen, Jelani Nelson, Tam´ as Sarl´ os, Mihir Singhal, and Uri Stemmer. One attack to rule them all: Tight quadratic bounds for adaptive queries on cardinality sketches. In arXiv preprint arXiv:2411.06370, 2024

    2024 arXiv

  3. [11]

    Uniform sampling for matrix approximation

    Michael B Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. Uniform sampling for matrix approximation. In 6th Conference on Innovations in Theoretical Computer Science (ITCS), 2015

    2015

  4. [12]

    Cohen, Yin Tat Lee, and Zhao Song

    Michael B. Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. In Journal of the ACM , 2020. 42

    2020

  5. [13]

    Online row sampling

    Michael B Cohen, Cameron Musco, and Jakub Pachocki. Online row sampling. In Theory of Computing, 2020

    2020

  6. [14]

    Pseudodeterminism: promises and lowerbounds

    Peter Dixon, Aduri Pavan, Jason Vander Woude, and NV Vinodchandran. Pseudodeterminism: promises and lowerbounds. In 54th Annual ACM Symposium on Theory of Computing (STOC) , 2022

    2022

  7. [15]

    Faster sgd training by minibatch persistency

    Matteo Fischetti, Iacopo Mandatelli, and Domenico Salvagnin. Faster sgd training by minibatch persistency. In arXiv preprint arXiv:1806.07353 , 2018

    2018 arXiv

  8. [16]

    Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization

    Roy Frostig, Rong Ge, Sham Kakade, and Aaron Sidford. Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization. In 32nd International Conference on Machine Learning (ICML) , 2015

    2015

  9. [17]

    Faster eigenvector computation via shift-and-invert preconditioning

    Dan Garber, Elad Hazan, Chi Jin, Cameron Musco, Praneeth Netrapalli, Aaron Sidford, et al. Faster eigenvector computation via shift-and-invert preconditioning. In 33rd International Conference on Machine Learning (ICML) , 2016

    2016

  10. [18]

    Probabilistic search algorithms with unique answers and their cryptographic applications

    Erann Gat and Shafi Goldwasser. Probabilistic search algorithms with unique answers and their cryptographic applications. In Electronic Colloquium on Computational Complexity: ECCC , 2011

    2011

  11. [19]

    Differentially private all-pairs shortest path distances: Improved algorithms and lower bounds

    Badih Ghazi, Ravi Kumar, Pasin Manurangsi, and Jelani Nelson. Differentially private all-pairs shortest path distances: Improved algorithms and lower bounds. In 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2022

    2022

  12. [20]

    Bipartite perfect matching in pseudo-deterministic nc

    Shafi Goldwasser and Ofer Grossman. Bipartite perfect matching in pseudo-deterministic nc. In 44th International Colloquium on Automata, Languages and Programming (ICALP) , 2017

    2017

  13. [21]

    Pseudo-deterministic proofs

    Shafi Goldwasser, Ofer Grossman, and Dhiraj Holden. Pseudo-deterministic proofs. In arXiv preprint arXiv:1706.04641, 2017

    2017 arXiv

  14. [22]

    A survey of actor- critic reinforcement learning: Standard and natural policy gradients

    Ivo Grondman, Lucian Busoniu, Gabriel AD Lopes, and Robert Babuska. A survey of actor- critic reinforcement learning: Standard and natural policy gradients. In IEEE Transactions on Systems, Man, and Cybernetics, part C (applications and reviews) , 2012

    2012

  15. [23]

    Tight space lower bound for pseudo- deterministic approximate counting

    Ofer Grossman, Meghal Gupta, and Mark Sellke. Tight space lower bound for pseudo- deterministic approximate counting. In 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2023

    2023

  16. [24]

    Reproducibility in learning

    Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning. In Proceedings of the 54th annual ACM SIGACT symposium on theory of computing , 2022

    2022

  17. [25]

    A faster algorithm for solving general lps

    Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. A faster algorithm for solving general lps. In 53rd Annual ACM Symposium on Theory of Computing (STOC) , 2021

    2021

  18. [26]

    Towards tight bounds on the sample complexity of average-reward mdps

    Yujia Jin and Aaron Sidford. Towards tight bounds on the sample complexity of average-reward mdps. In 38th International Conference on Machine Learning (ICML) , 2021

    2021

  19. [27]

    Sharper rates for separable minimax and finite sum optimization via primal-dual extragradient methods

    Yujia Jin, Aaron Sidford, and Kevin Tian. Sharper rates for separable minimax and finite sum optimization via primal-dual extragradient methods. In 35th Annual Conference on Computational Learning Theory (COLT), 2022. 43

    2022

  20. [28]

    Truncated variance reduced value iteration

    Yujia Jin, Ishani Karmarkar, Aaron Sidford, and Jiayi Wang. Truncated variance reduced value iteration. In arXiv preprint arXiv:2405.12952 , 2024

    2024 arXiv

  21. [29]

    Accelerating stochastic gradient descent using predictive variance reduction

    Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems 26 (NeurIPS) , 2013

    2013

  22. [30]

    Finite-sample convergence rates for q-learning and indirect algorithms

    Michael Kearns and Satinder Singh. Finite-sample convergence rates for q-learning and indirect algorithms. In Advances in Neural Information Processing Systems 33 (NeurIPS) , 1998

    1998

  23. [31]

    Path finding methods for linear programming: Solving linear programs in o (vrank) iterations and faster algorithms for maximum flow

    Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in o (vrank) iterations and faster algorithms for maximum flow. In 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , 2014

    2014

  24. [32]

    Efficient inverse maintenance and faster algorithms for linear programming

    Yin Tat Lee and Aaron Sidford. Efficient inverse maintenance and faster algorithms for linear programming. In 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , 2015

    2015

  25. [33]

    A universal catalyst for first-order optimiza- tion

    Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. A universal catalyst for first-order optimiza- tion. In Advances in Neural Information Processing Systems 28 (NeurIPS) , 2015

    2015

  26. [34]

    On the complexity of solving markov decision problems

    Michael L Littman, Thomas L Dean, and Leslie Pack Kaelbling. On the complexity of solving markov decision problems. In 11th Annual Conference on Uncertainty in Artificial Intelligence (UAI), 1995

    1995

  27. [35]

    Accelerated gradient algorithms with adaptive subspace search for instance-faster optimization

    Yuanshi Liu, Hanzhen Zhao, Yang Xu, Pengyun Yue, and Cong Fang. Accelerated gradient algorithms with adaptive subspace search for instance-faster optimization. In arXiv preprint arXiv:2312.03218, 2023

    2023 arXiv

  28. [36]

    Prox-method with rate of convergence o (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems

    Arkadi Nemirovski. Prox-method with rate of convergence o (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. In SIAM Journal on Optimization , 2004

    2004

  29. [37]

    Modern discrete probability: An essential toolkit

    Sebastien Roch. Modern discrete probability: An essential toolkit. In Cambridge Series in Statistical and Probabilistic Mathematics , 2024

    2024

  30. [38]

    High performance parallel stochastic gradient descent in shared memory

    Scott Sallinen, Nadathur Satish, Mikhail Smelyanskiy, Samantika S Sury, and Christopher R´ e. High performance parallel stochastic gradient descent in shared memory. In 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS) , 2016

    2016

  31. [39]

    Near-optimal time and sample complexities for solving markov decision processes with a generative model

    Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model. In Advances in Neural Information Processing Systems 30 (NeurIPS) , 2018

    2018

  32. [40]

    Variance reduced value iteration and faster algorithms for solving markov decision processes

    Aaron Sidford, Mengdi Wang, Xian Wu, and Yinyu Ye. Variance reduced value iteration and faster algorithms for solving markov decision processes. In 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2018

    2018

  33. [41]

    Variance reduced value iteration and faster algorithms for solving markov decision processes

    Aaron Sidford, Mengdi Wang, Xian Wu, and Yinyu Ye. Variance reduced value iteration and faster algorithms for solving markov decision processes. In Naval Research Logistics (NRL), 2023

    2023

  34. [42]

    Solving h-horizon, stationary markov decision problems in time proportional to log (h)

    Paul Tseng. Solving h-horizon, stationary markov decision problems in time proportional to log (h). In Operations Research Letters, 1990. 44

    1990

  35. [43]

    Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang

    Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, mdps, and l1-regression in nearly linear time for dense instances. In 53rd Annual ACM Symposium on Theory of Computing (STOC) , 2021

    2021

  36. [44]

    Liu, Richard Peng, and Aaron Sidford

    Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, and Aaron Sidford. Faster maxflow via improved dynamic spectral vertex sparsifiers. In 54th Annual ACM Symposium on Theory of Computing (STOC) , 2022

    2022

  37. [45]

    Tight complexity bounds for optimizing composite objectives

    Blake E Woodworth and Nati Srebro. Tight complexity bounds for optimizing composite objectives. In Advances in Neural Information Processing Systems 29 (NeurIPS) , 2016

    2016

  38. [46]

    Minibatch vs local sgd for heterogeneous distributed learning

    Blake E Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs local sgd for heterogeneous distributed learning. In Advances in Neural Information Processing Systems , 2020. A Inducing pseudoindependence numerically stably The pseudo-independent algorithm constructed in...

    2020

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.