Pith. sign in

REVIEW 1 major objections 5 minor 37 references

Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization

T0 review · 1 major / 5 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read This paper establishes variance-reduced, projection-free conditional-gradient guarantees when gradients arrive from one ergodic Markov chain.

desk verdict Genuine Markovian-to-i.i.d. reduction for projection-free composite methods; coherent proof, but the transfer leans on an unpublished base analysis and a referee needs that paper. read the letter →

arxiv 2607.25785 v1 pith:SO3W752I submitted 2026-07-28 math.OC cs.LG

Zhaojun Peng This is my paper · ORCID
classification math.OCcs.LG MSC 90C2690C1590C25
keywords nonconvexcompositeoptimizationMarkoviansamplingvariancereductionconditionalgradientmethodsFrank–WolfemultilevelMonteCarloclippingmixingtime
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

The paper introduces MC-ALFCG, the first variance-reduced conditional-gradient method for nonconvex composite optimization in which gradient samples arrive as consecutive states of a single ergodic Markov chain. It reaches an expected generalized Frank–Wolfe gap at most ε using eO((τmix^2Gσ + τmix^{5/2}Gσ^2)ε^{-3} + τmix^5 ε^{-2}) consumed samples; a mixing-time-oblivious variant needs eO(τmix^6 ε^{-3} + τmix^3 ε^{-2}) and no knowledge of the mixing time or noise level. The core is a reduction: a coupled capped multilevel Monte Carlo estimator absorbs the state-dependent conditional bias, clipping supplies a pathwise error bound, and the resulting momentum error recursion matches the independent-sampling recursion after substituting σ² ↦ 2ΛGσ² and L² ↦ 2ΛL² with Λ = O(τmix log T). If correct, this closes the previously unanalyzed intersection of recursive variance reduction, projection-free composite oracles, and Lipschitz-constant-free adaptive steps under single-trajectory Markovian data. The paper flags its own scope clearly: guarantees are in expectation, clipping requires a known radius, and the unclipped estimator's pathwise bound is left open.

What carries the argument

The load-bearing mechanism is a coupled capped multilevel Monte Carlo (MLMC) gradient estimator combined with per-iteration clipping. Each step draws a geometric level J, advances the chain by 2^J states (capped at log T), and forms a telescoping estimator whose conditional mean equals a deep prefix average of length ~T/2, giving conditional bias O(τmix/T) uniformly over the starting chain state. Evaluating the same burst at x_t and x_{t−1} makes the gradient-difference second moment scale with the iterate displacement. Clipping to a ball of radius bG ≥ G enforces the pathwise bound the adaptive step-size analysis requires, because the raw MLMC estimator is heavy-tailed — its essential supre

What would settle it

On the paper's own two-state chain (Z={±1}, symmetric kernel, stationary law uniform, f(x;z)=f0(x)+Gσ z⟨u,x⟩), measure the essential supremum of the unclipped initial estimator error: if it is bounded independently of T, Proposition 4.1 is false. For the complexity claim, run MC-ALFCG on a lazy-refresh chain with exactly known τmix and measure the sample count needed to reach generalized Frank–Wolfe gap ε across a range of large τmix; the tuned bound predicts the ε^{-2} term scales as τmix^5, so a mixing-free constant there would contradict Theorem 5.5.

Watch

Extended reading notes

Core claim

The paper's central claim is that Markovian sampling need not break recursive variance reduction in projection-free composite optimization. After coupling the multilevel Monte Carlo estimator across the two iterates and clipping the recursive gradient estimate, the conditional error recursion has exactly the same form as the i.i.d. recursion, with noise σ² replaced by 2ΛGσ² and smoothness L² replaced by 2ΛL², where Λ = O(τmix log T). This transfers the adaptive Lipschitz-constant-free conditional-gradient analysis, yielding expected sample complexity eO((τmix^2Gσ + τmix^{5/2}Gσ^2)ε^{-3} + τmix^5 ε^{-2}) for the generalized Frank–Wolfe gap. An exactly noiseless specialization attains eO(ε^{-2

Load-bearing premise

The load-bearing premise is Assumption 3.2 — every sample function f(·;z) is L-smooth on X — because the coupled gradient-difference estimator's displacement-variance bound and hence the reduction (Theorem 5.4) collapse if only the population average f is smooth; the paper itself flags this, along with the needed known clipping radius bG ≥ G and, for the tuned rates, certified mixing-time and noise bounds.

Editorial extensions

If this is right

  • Streaming optimization from a single time series, sensor stream, or MCMC output can now use recursive variance reduction with a projection-free composite oracle, a combination that previously had no guarantee.
  • No smoothness constant is needed: the adaptive step-size machinery and clipping use only the problem-envelope constants bG, Gσ, and, for the tuned variant, the mixing time τmix.
  • The tuned result splits into two stochastic branches: the high-effective-noise branch τmix^{5/2}Gσ^2 ε^{-3} and the low-noise companion τmix^2 Gσ ε^{-3}, which keeps the bound continuous as Gσ → 0.
  • The exactly noiseless case is genuinely easier: a separate parameter branch achieves eO(ε^{-2}) with mixing-time-free constants.
  • Within the transferred analysis, no retuning of the two free parameters can lower the Λ^{5/6} mixing exponent in the leading stochastic coefficient for fixed D > 0 and Gσ > 0.

Reading between the lines

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

  • Editorial inference: the reduction mechanism — mix inside a burst, absorb conditional bias by momentum contraction — looks method-agnostic; if it transfers to other STORM-type recursions such as proximal-linearized ADMM or orthogonalized momentum methods, Markovian data may only cost a Λ inflation in the analysis rather than a bespoke theory.
  • Editorial inference: clipping was rarely active in the paper's experiments (at most about 0.36% of iterations), so the pathwise safeguard may be much looser than the analysis requires in practice; a clipping-aware Lyapunov analysis could sharpen the τmix exponents the paper leaves open.
  • Editorial inference: a direct empirical test of the rate in τmix — varying the transition kernel at fixed stationary objective and measuring the sample count to a fixed gap — would probe whether the τmix^5 ε^{-2} burn-in term is tight or merely an artifact of the transferred constant propagation.
  • Editorial inference: because the guarantees hold in expectation under a fixed transition kernel, the practical reach excludes decision-dependent sampling such as on-policy reinforcement learning; the results apply to fixed-chain, off-policy-style settings only.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 5 minor

Summary. The paper studies stochastic composite nonconvex optimization over a compact convex set when gradient samples arrive along a single trajectory of a fixed ergodic Markov chain. It proposes MC-ALFCG, which combines the momentum conditional-gradient framework ALFCG-MVR2 with coupled capped multilevel Monte Carlo bursts and per-iteration clipping. The central result is Theorem 5.4, which reduces the Markovian conditional error recursion to the independent-sampling recursion under the substitutions σ² ↦ 2ΛGσ² and L² ↦ 2ΛL², where Λ = 306τ_mix(1+log₂T). From this transfer, Theorem 5.5 gives an expected generalized-Frank–Wolfe-gap sample complexity of \tilde O((τ_mix²Gσ + τ_mix^{5/2}Gσ²)ε^{-3} + τ_mix^5 ε^{-2}), while Corollary 5.7 gives a noiseless specialization at \tilde O(ε^{-2}) and Theorem 5.8 gives a mixing-time-oblivious variant at \tilde O(τ_mix^6 ε^{-3}+τ_mix^3 ε^{-2}). Theorem 5.9 provides an in-analysis lower bound on the attainable Λ-exponent within the transferred constant propagation. Appendices contain the MLMC moment bounds, bias absorption, pathwise clipping bounds, and the constant transfer.

Significance. If the main result is correct, the paper closes a genuine gap in Table 1: no prior variance-reduced, projection-free composite optimization method is known for a fixed-chain streaming Markovian oracle. The paper's strengths are substantial: the conditional telescoping Lemma 5.1 is clean; the bias absorption by the (1−α_t) contraction in Theorem 5.4 is explicit and does not require independence between the burst and the previous error; the clipping step is rigorously shown to provide the pathwise displacement bound needed by the adaptive analysis; and the constant propagation is carried out with explicit coefficients, including Table 2 and the master coefficient system (11). The authors are also unusually careful about scope: expectation guarantees, certified bounds, the in-analysis nature of Theorem 5.9, and the fact that clipping sidesteps rather than resolves the original unclipped question are all stated. The main residual risk is external: the transfer inherits the whole base analysis from the unpublished preprint [31], whose lemmas are cited rather than reproduced.

major comments (1)
  1. [Appendix D.3, Theorem 5.5] The headline complexity is not self-contained: it depends on the correctness of the unpublished base analysis [31, Appendix H]. The manuscript verifies three interfaces and reproduces the coefficient system (11), but the actual content of [31, Lemma 6], [31, Lemma 25(c)], [31, Lemma 26(a)–(b)], [31, Lemma 27], and the summations leading to the master bound (12) are not included. Since the ε^{-3} and ε^{-2} exponents and the constants R and S in Theorem 5.5 are produced by that base proof, an independent referee cannot fully certify the main claim without either a final published version of [31] or a self-contained appendix stating and proving the required base lemmas. This is a verification gap rather than an identified error, but it is load-bearing.
minor comments (5)
  1. [Section 3, Notation] The notation "log := log 2" is confusing; it should read "log := log_2" (base-2 logarithm) throughout, especially because Λ and jmax depend on log₂T.
  2. [Appendix E, Lemma E.1] Theorem 5.5 states that C_R and C_S are uniform over 0 < Gσ ≤ \bar Gσ, but the displayed definitions of c1 in Lemma E.1 write Gσ² rather than \bar Gσ². If Gσ denotes the actual instance noise level, uniformity requires replacing it by the envelope \bar Gσ in the constant definitions; as written this is ambiguous.
  3. [Algorithm 1, line 4] The quantities u_i and L_i are used in the definition of α_t before the initialization of L_i is fully specified for i = 0. Please state explicitly the empty-sum convention and the order in which α_t and L_t are evaluated for t = 0 and t = 1.
  4. [Corollary 5.2, table] The table header "eH ≤ conditional bias ≤ conditional 2nd moment" is hard to parse. The rows are separate instantiations of Lemma 5.1; a clearer layout would label the four columns as "eH", "conditional bias", and "conditional second moment" without chained inequalities.
  5. [Remark 5.6 and Theorem 5.9] The phrase "matches the leading mixing exponent within the transferred analysis" is accurate but easy to over-read. The paper correctly states that Theorem 5.9 is neither an algorithmic nor an information-theoretic lower bound; I suggest keeping this caveat in the introduction as well, since the abstract may otherwise be read as claiming full optimality.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the Markovian reduction is derived from first principles and the transfer to the i.i.d. analysis is verified term by term against an external base method.

full rationale

The derivation chain is self-contained under the paper's stated assumptions. The central step, Theorem 5.4, derives recursion (5) directly from Lemma 5.1/Corollary 5.2 and Lemma 5.3; it does not assume the target complexity. The effective noise and smoothness constants σ_M² = 2ΛGσ² and L_M² = 2ΛL² are certified upper bounds, not fitted parameters: Corollary 5.2 bounds the conditional bias and second moment, and the factor 2 is explicitly explained as absorption of the bias through the (1−α_t) contraction, with the threshold T ≥ T0 checked in the proof. The subsequent transfer to [31, Appendix H] uses that paper as an external base analysis; the present paper reproduces the coefficient system (11) and verifies the three required interfaces—pathwise descent inequality, momentum error recursion, and pathwise displacement bound—in Proposition D.1. Nothing in the transfer assumes the result being proved. The complexities in Theorems 5.5 and 5.8 follow by substituting these certified constants into the reproduced chain, and Theorem 5.9 is explicitly scoped as an in-analysis, parameter-tuning lower bound within the transferred constant propagation, not as an algorithmic or information-theoretic lower bound. The paper repeatedly acknowledges its limitations (Remark 5.11, Section 5.7, Remark F.2), including reliance on the unpublished base analysis [31] and the fact that clipping sidesteps, rather than resolves, the original unclipped pathwise-bound question. These are verification and scope risks, not circular reasoning. No fitted value is relabeled as a prediction, no ansatz is smuggled in via citation, and no load-bearing premise depends on a self-citation; the external dependency [31] is cited as prior work and its role is explicitly isolated and checked.

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

No data-fitted free parameters. The algorithm's ρ and β are set by the theory from known problem bounds (tuned, oblivious, or noiseless branches), not from data. The central result rests on the stated domain assumptions plus the correctness of the cited base analysis [31]; the latter is the least independently verified element.

assumptions (6)
  • domain assumption Assumption 3.2: individual smoothness of f(·;z) for every z.
    Needed for Corollary 5.2 to bound the coupled MLMC gradient-difference estimator by a multiple of ||x_t−x_{t−1}||². If only the average f is smooth, the displacement-variance term in recursion (5) is not justified.
  • domain assumption Assumption 3.3: known clipping radius bG ≥ G, with h G-Lipschitz on X.
    Clipping supplies the pathwise bound in Lemma 5.3, which is the interface required by the adaptive analysis. Without bG the algorithm cannot be instantiated as analyzed.
  • domain assumption Assumption 3.4: bounded centered gradient noise Gσ.
    Gσ enters the effective noise σ_M² = 2ΛGσ² and the tuned parameter β⋆. The oblivious variant avoids knowing Gσ, but its guarantee is not uniform over unbounded noise levels.
  • domain assumption Assumption 3.5: finite mixing time τmix with the standard summability of dmix.
    All Markov bounds scale with τmix; Lemma 5.1 and Lemma B.3 rely on dmix(ℓτmix) ≤ 2^{−ℓ} and on summability of dmix.
  • ad hoc to paper Correctness of the base analysis of [31, Appendix H] and its constant propagation.
    Theorem 5.4 and Proposition D.1 transfer the independent-sampling constant propagation from an arXiv preprint [31]. The paper claims a term-by-term transfer, but if the base analysis contains an error, the stated rates inherit it.
  • standard math Standard probability, convex analysis, and Markov-chain inequalities (total-variation bound, Young, Abel summation, Jensen).
    Used in Lemmas B.1–B.3, C.2, C.3, and in the transferred constant propagation in Appendix D.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization." pith.science (2026). https://pith.science/paper/SO3W752I

@misc{pith2026260725785,
  author       = {Pith},
  title        = {Pith review of: Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SO3W752I}},
  note         = {Machine review of arXiv:2607.25785}
}
abstract

We study stochastic composite nonconvex optimization over a compact convex set when gradient samples arrive along a single trajectory of a fixed ergodic Markov chain. Existing single-trajectory variance-reduction theory covers smooth unconstrained objectives; we address the projection-free composite setting using the generalized Frank-Wolfe gap. We propose MC-ALFCG, which combines a momentum conditional-gradient method with coupled capped multilevel Monte Carlo estimation and per-iteration clipping. The deepest nested average uses consecutive states from the same trajectory, yielding conditional bias $O(\tau_{\mathrm{mix}}/T)$ uniformly over the starting state, while coupling controls the gradient-difference second moment through the iterate displacement. Clipping enforces the pathwise bounds needed by the adaptive analysis. We reduce the Markovian recursion to its independent-sampling counterpart under $\sigma^2\mapsto 2\Lambda G_\sigma^2$ and $L^2\mapsto 2\Lambda L^2$, where $\Lambda=O(\tau_{\mathrm{mix}}\log T)$. For positive centered noise, the tuned method achieves expected sample complexity $\widetilde{O}((\tau_{\mathrm{mix}}^2G_\sigma+\tau_{\mathrm{mix}}^{5/2}G_\sigma^2)\varepsilon^{-3}+\tau_{\mathrm{mix}}^5\varepsilon^{-2})$. The exactly noiseless specialization achieves $\widetilde{O}(\varepsilon^{-2})$ with mixing-time-free constants, while a mixing-time-oblivious variant achieves $\widetilde{O}(\tau_{\mathrm{mix}}^6\varepsilon^{-3}+\tau_{\mathrm{mix}}^3\varepsilon^{-2})$. All guarantees are in expectation under a fixed transition kernel. Controlled numerical studies examine dependence sensitivity, a nonconvex composite instance, and clipping behavior.

Figures

Figures reproduced from arXiv: 2607.25785 by the authors.

Figure 1
Figure 1. FW gap Equation (2) versus samples consumed for four kernels with a common uniform stationary law and different exact mixing times. Lines are means over 10 seeds. Bands are ±1 standard deviation (clipped below at one quarter of the mean for the logarithmic display). and oblivious variants increase by factors of 4.3 and 5.3, compared with 10.3 for the naive base estimator and 37.4 for projected SGD ( [PITH_FULL_IMAG… view at source ↗
Figure 2
Figure 2. Generalized Frank–Wolfe gap for the nonconvex composite instance Equation (17). All methods are evaluated against consumed Markov states. Lines and bands show means and one standard deviation over ten paired seeds. H.5 Nonconvex Composite Regression The second experiment exercises the full model rather than the smooth convex special case of the classification study. For unit-norm ai ∈ R 30, we consider min x∈[−3,3]3… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 3 canonical work pages

  1. [31]

    Adaptive Lipschitz-free conditional gradient methods for stochastic com- posite nonconvex optimization

    Ganzhao Yuan. Adaptive Lipschitz-free conditional gradient methods for stochastic com- posite nonconvex optimization. arXiv preprint arXiv:2603.06369 , 2026. URL https: //arxiv.org/abs/2603.06369. 18

    arXiv 2026

  2. [1]

    Convergence of first-order methods for constrained nonconvex optimization with dependent data

    Ahmet Alacaoglu and Hanbaek Lyu. Convergence of first-order methods for constrained nonconvex optimization with dependent data. In Proceedings of the 40th International Conference on Machine Learning , volume 202 of Proceedings of Machine Learning Research, pages 458–489. PMLR, 2023

    2023

  3. [2]

    Duchi, Dylan J

    Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Program- ming, 199(1–2):165–214, 2023. doi: 10.1007/s10107-022-01822-7

    doi:10.1007/s10107-022-01822-7 2023

  4. [3]

    Blanchet and Peter W

    Jose H. Blanchet and Peter W. Glynn. Unbiased Monte Carlo for optimization and functions of expectations via multi-level randomization. In 2015 Winter Simulation Conference , pages 3656–3667. IEEE, 2015. doi: 10.1109/WSC.2015.7408524

    arXiv 2015

  5. [4]

    High-probability bounds for non-convex stochastic optimization with heavy tails

    Ashok Cutkosky and Harsh Mehta. High-probability bounds for non-convex stochastic optimization with heavy tails. In Advances in Neural Information Processing Systems , volume 34, pages 4883–4895. Curran Associates, Inc., 2021

    2021

  6. [5]

    Momentum-based variance reduction in non- convex SGD

    Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non- convex SGD. In Advances in Neural Information Processing Systems , volume 32, pages 15236–15245. Curran Associates, Inc., 2019

    2019

  7. [6]

    Adapting to mixing time in stochastic optimiza- tion with Markovian data

    Ron Dorfman and Kfir Yehuda Levy. Adapting to mixing time in stochastic optimiza- tion with Markovian data. In Proceedings of the 39th International Conference on Ma- chine Learning, volume 162 of Proceedings of Machine Learning Research, pages 5429–5446. PMLR, 2022. 16

    2022

  8. [7]

    Duchi, Alekh Agarwal, Mikael Johansson, and Michael I

    John C. Duchi, Alekh Agarwal, Mikael Johansson, and Michael I. Jordan. Ergodic mirror descent. SIAM Journal on Optimization , 22(4):1549–1578, 2012. doi: 10.1137/110836043

    work page doi:10.1137/110836043 2012

Show all 37 references
  1. [8]

    Stochastic gradient descent under Markovian sampling schemes

    Mathieu Even. Stochastic gradient descent under Markovian sampling schemes. In Proceed- ings of the 40th International Conference on Machine Learning , volume 202 of Proceedings of Machine Learning Research , pages 9412–9439. PMLR, 2023

    2023

  2. [9]

    SPIDER: Near-optimal non- convex optimization via stochastic path-integrated differential estimator

    Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. SPIDER: Near-optimal non- convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems , volume 31, pages 689–699. Curran Associates, Inc., 2018

    2018

  3. [10]

    An algorithm for quadratic programming

    Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(1–2):95–110, 1956. doi: 10.1002/nav.3800030109

    1956 doi

  4. [11]

    Michael B. Giles. Multilevel Monte Carlo path simulation. Operations Research, 56(3): 607–617, 2008. doi: 10.1287/opre.1070.0496

    2008

  5. [12]

    Stochastic optimization with heavy-tailed noise via accelerated gradient clipping

    Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. In Advances in Neural Information Processing Systems, volume 33, pages 15042–15053. Curran Associates, Inc., 2020

    2020

  6. [13]

    Variance-reduced and projection-free stochastic optimization

    Elad Hazan and Haipeng Luo. Variance-reduced and projection-free stochastic optimization. In Proceedings of the 33rd International Conference on Machine Learning , volume 48 of Proceedings of Machine Learning Research , pages 1263–1271. PMLR, 2016

    2016

  7. [14]

    Revisiting Frank–Wolfe: Projection-free sparse convex optimization

    Martin Jaggi. Revisiting Frank–Wolfe: Projection-free sparse convex optimization. In Proceedings of the 30th International Conference on Machine Learning , volume 28 of Pro- ceedings of Machine Learning Research , pages 427–435. PMLR, 2013

    2013

  8. [15]

    Non-asymptotic analy- sis of biased stochastic approximation scheme

    Belhal Karimi, Błażej Miasojedow, Eric Moulines, and Hoi-To Wai. Non-asymptotic analy- sis of biased stochastic approximation scheme. In Proceedings of the Thirty-Second Confer- ence on Learning Theory , volume 99 of Proceedings of Machine Learning Research , pages 1944–1974. ...

    1944

  9. [16]

    Stochastic-constrained stochastic optimization with Markovian data

    Yeongjong Kim and Dabeen Lee. Stochastic-constrained stochastic optimization with Markovian data. Journal of Machine Learning Research , 25(416):1–69, 2024

    2024

  10. [17]

    Convergence rate of Frank–Wolfe for non-convex objectives

    Simon Lacoste-Julien. Convergence rate of Frank–Wolfe for non-convex objectives. arXiv preprint arXiv:1607.00345 , 2016. URL https://arxiv.org/abs/1607.00345

    2016 arXiv

  11. [18]

    Levin and Yuval Peres

    David A. Levin and Yuval Peres. Markov Chains and Mixing Times . American Mathemat- ical Society, Providence, RI, 2nd edition, 2017. doi: 10.1090/mbk/107

    2017 doi

  12. [19]

    Levy, Ali Kavis, and Volkan Cevher

    Kfir Y. Levy, Ali Kavis, and Volkan Cevher. STORM+: Fully adaptive SGD with recursive momentum for nonconvex optimization. In Advances in Neural Information Processing Systems, volume 34, pages 20571–20582. Curran Associates, Inc., 2021

    2021

  13. [20]

    Stochastic conditional gradient meth- ods: From convex minimization to submodular maximization

    Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Stochastic conditional gradient meth- ods: From convex minimization to submodular maximization. Journal of Machine Learning Research, 21(105):1–49, 2020. 17

    2020

  14. [21]

    Boosted stochastic Frank– Wolfe for constrained nonconvex optimization

    Navil Nandhan, Abbas Khademi, and Antonio Silveti-Falls. Boosted stochastic Frank– Wolfe for constrained nonconvex optimization. arXiv preprint arXiv:2605.25255 , 2026. URL https://arxiv.org/abs/2605.25255

    2026 arXiv

  15. [22]

    Stochastic Frank–Wolfe: Unified analysis and zoo of spe- cial cases

    Ruslan Nazykov, Aleksandr Shestakov, Vladimir Solodkin, Aleksandr Beznosikov, Gauthier Gidel, and Alexander Gasnikov. Stochastic Frank–Wolfe: Unified analysis and zoo of spe- cial cases. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistic...

    2024

  16. [23]

    Stochastic variance-reduced policy gradient

    Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochastic variance-reduced policy gradient. In Proceedings of the 35th Inter- national Conference on Machine Learning , volume 80 of Proceedings of Machine Learning Research, pages 4026–...

    2018

  17. [24]

    A hybrid stochastic policy gradient algorithm for reinforcement learning

    Nhan Pham, Lam Nguyen, Dzung Phan, Phuong Ha Nguyen, Marten van Dijk, and Quoc Tran-Dinh. A hybrid stochastic policy gradient algorithm for reinforcement learning. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 ...

    2020

  18. [25]

    Reddi, Suvrit Sra, Barnabás Póczos, and Alexander J

    Sashank J. Reddi, Suvrit Sra, Barnabás Póczos, and Alexander J. Smola. Stochastic Frank– Wolfe methods for nonconvex optimization. In 2016 54th Annual Allerton Conference on Communication, Control, and Computing , pages 1244–1251. IEEE, 2016. doi: 10.1109/ ALLERTON.2016.7852377

    2016

  19. [26]

    Methods for optimization problems with Markovian stochasticity and non-Euclidean geom- etry

    Vladimir Solodkin, Andrey Veprikov, Alexander Chernyavskiy, and Aleksandr Beznosikov. Methods for optimization problems with Markovian stochasticity and non-Euclidean geom- etry. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 40, pages 25508–25517. AA...

    2026 doi

  20. [27]

    On Markov chain gradient descent

    Tao Sun, Yuejiao Sun, and Wotao Yin. On Markov chain gradient descent. In Advances in Neural Information Processing Systems , volume 31, pages 9917–9926. Curran Associates, Inc., 2018

    2018

  21. [28]

    Learning from a single markovian trajectory: Optimality and variance reduction

    Zhenyu Sun and Ermin Wei. Learning from a single markovian trajectory: Optimality and variance reduction. In D. Belgrave, C. Zhang, H. Lin, R. Pascanu, P. Koniusz, M. Ghassemi, and N. Chen, editors, Advances in Neural Information Processing Systems, volume 38, pages 20004–2003...

    2025

  22. [29]

    Stability and generaliza- tion for Markov chain stochastic gradient methods

    Puyu Wang, Yunwen Lei, Yiming Ying, and Ding-Xuan Zhou. Stability and generaliza- tion for Markov chain stochastic gradient methods. In Advances in Neural Information Processing Systems, volume 35, pages 37735–37748. Curran Associates, Inc., 2022

    2022

  23. [30]

    Adaptive extrapolated proximal gradient methods with variance reduction for composite nonconvex finite-sum minimization

    Ganzhao Yuan. Adaptive extrapolated proximal gradient methods with variance reduction for composite nonconvex finite-sum minimization. arXiv preprint arXiv:2502.21099 , 2025. URL https://arxiv.org/abs/2502.21099

    2025 arXiv

  24. [32]

    Stochastic recursive momentum for policy gradient methods

    Huizhuo Yuan, Xiangru Lian, Ji Liu, and Yuren Zhou. Stochastic recursive momentum for policy gradient methods. arXiv preprint arXiv:2003.04302 , 2020. URL https://arxiv. org/abs/2003.04302

    2003 arXiv

  25. [33]

    Why gradient clipping accel- erates training: A theoretical justification for adaptivity

    Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accel- erates training: A theoretical justification for adaptivity. In International Conference on Learning Representations. OpenReview.net, 2020. URL https://openreview.net/forum? id=BJgnXpVYwS

    2020

  26. [34]

    Stochastic variance-reduced prox-linear algorithms for non- convex composite optimization

    Junyu Zhang and Lin Xiao. Stochastic variance-reduced prox-linear algorithms for non- convex composite optimization. Mathematical Programming, 195(1–2):649–691, 2022. doi: 10.1007/s10107-021-01709-z. 19 A Notation Summary Tables 3 and 4 collect the recurring symbols of the pap...

    2022 doi

  27. [35]

    the base coefficient system

    Drawing Jt first and falling back to the base level when Jt>j max is what makes the expected cost logarithmic. C Proofs for Sections 5.1 and 5.3 We first record two elementary facts about the adaptive weights. Lemma C.1 (Deterministic stepsize floor) . For all t 0, αt (t + 1)−2/3...

  28. [36]

    Moreover, max(β1/3 T ,ϑ 2, 0) ϑ = β1/3 T ϑ = β1/6 T +β1/3 T = O (T + 1)−1/6

    In the transferred constant propagation, the exact-oracle transfer of Lemma E.3 sets both recursion-only coefficients to zero, so ¨B = 0 and Y0 =O(1), Z 0 =O(1), ϑ = β1/6 T 1 +β1/6 T . Moreover, max(β1/3 T ,ϑ 2, 0) ϑ = β1/3 T ϑ = β1/6 T +β1/3 T = O (T + 1)−1/6 . 33 Substitution ...

  29. [37]

    Thus the instance numerically exercises smooth nonconvexity, and h(x) = 0.02kxk1 is nonzero, convex, and nonsmooth

    A deterministic verification found a Hessian eigenvalue 0.0200 for the fixed finite-sum smooth objective, while its directional-gradient finite-difference error was 1.43 10−11. Thus the instance numerically exercises smooth nonconvexity, and h(x) = 0.02kxk1 is nonzero, convex, and ...

    2023

Pith tools

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