Research map / Optimization / Nonconvex and smooth optimization
Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity
Boris Prokhorov, Semyon Chebykin, Alexander Gasnikov, Aleksandr Beznosikov
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase mixing time tau when gradient noise is negligible (sigma_2^2 = 1e-5) | zero-order accelerated SGD with randomized batching · Synthetic quadratic, two-point lazy Gaussian Markov noise | optimization error after 1000 iterations | No clear effect |
| increase mixing time tau when stochastic noise dominates (sigma_2^2 = 1e-3) | zero-order accelerated SGD with randomized batching · Synthetic quadratic, two-point lazy Gaussian Markov noise | optimization error after 1000 iterations | Hurt |
| increase dimension d | zero-order accelerated SGD with randomized batching · Synthetic quadratic, two-point lazy Gaussian Markov noise | optimization error after 1000 iterations | Hurt |
Closest papers by meaning
- Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling (ICML 2025 · similarity 0.91)
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.90)
- Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batching (ICML 2025 · similarity 0.88)
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity (NeurIPS 2024 · similarity 0.88)
- A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization (ICML 2025 · similarity 0.87)
- Convergence Rate in a Nonlinear Two-Time-Scale Stochastic Approximation with State (Time)-Dependence (AAAI 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
