Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity

• URL: http://arxiv.org/abs/2601.01160v1
• Date: Sat, 03 Jan 2026 11:27:07 GMT
• Title: Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity
• Authors: Boris Prokhorov, Semyon Chebykin, Alexander Gasnikov, Aleksandr Beznosikov,
• Abstract summary: We present and analyze a novel derivative-free method for solving such problems.<n>We show that when mixing time $$ of the underlying noise sequence is less than the dimension of the problem $d$, the convergence estimates of our method do not depend on $$.
• Score: 80.65200796386168
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper deals with stochastic optimization problems involving Markovian noise with a zero-order oracle. We present and analyze a novel derivative-free method for solving such problems in strongly convex smooth and non-smooth settings with both one-point and two-point feedback oracles. Using a randomized batching scheme, we show that when mixing time $τ$ of the underlying noise sequence is less than the dimension of the problem $d$, the convergence estimates of our method do not depend on $τ$. This observation provides an efficient way to interact with Markovian stochasticity: instead of invoking the expensive first-order oracle, one should use the zero-order oracle. Finally, we complement our upper bounds with the corresponding lower bounds. This confirms the optimality of our results.

Related papers

• Continuum-armed Bandit Optimization with Batch Pairwise Comparison Oracles [14.070618685107645]
  We study a bandit optimization problem where the goal is to maximize a function $f(x)$ over $T$ periods.<n>We show that such a pairwise comparison finds important applications to joint pricing and inventory replenishment problems.
  arXiv  Detail & Related papers  (2025-05-28T13:41:00Z)
• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  We show that SignSGD with Majority Voting can robustly work on the whole range of complexity with $kappakappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappa
  arXiv  Detail & Related papers  (2025-02-11T19:54:11Z)
• Stochastic Halpern iteration in normed spaces and applications to reinforcement learning [0.30693357740321775]
  We analyze the oracle complexity of the Halpern iteration with minibatch.<n>We propose new model-free algorithms for average and discounted reward MDPs.
  arXiv  Detail & Related papers  (2024-03-19T01:07:35Z)
• Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles [13.077441411315759]
  We consider bilevel optimization when the lower-level problem is strongly convex.<n>We incorporate a two-time-scale update to improve their method to achieve the near-optimal $tilde mathcalO(epsilon-2)$ first-order oracle complexity.
  arXiv  Detail & Related papers  (2023-06-26T17:07:54Z)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  We present a unified approach for the theoretical analysis of first-order variation methods. Our approach covers both non-linear gradient and strongly Monte Carlo problems. We provide bounds that match the oracle strongly in the case of convex method optimization problems.
  arXiv  Detail & Related papers  (2023-05-25T11:11:31Z)
• Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods [57.050204432302195]
  This work proposes a universal and adaptive second-order method for minimizing second-order smooth, convex functions. Our algorithm achieves $O(sigma / sqrtT)$ convergence when the oracle feedback is with variance $sigma2$, and improves its convergence to $O( 1 / T3)$ with deterministic oracles.
  arXiv  Detail & Related papers  (2022-11-03T14:12:51Z)
• A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization [12.096252285460814]
  We propose a projection-free conditional gradient-type algorithm for composition optimization. We show that the number of oracles and the linear-minimization oracle required by the proposed algorithm, are of order $mathcalO_T(epsilon-2)$ and $mathcalO_T(epsilon-3)$ respectively.
  arXiv  Detail & Related papers  (2022-02-09T06:05:38Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  We investigate the active pure exploration problem in Markov Decision Processes. Agent sequentially selects actions and, from the resulting system trajectory, aims at the best as fast as possible.
  arXiv  Detail & Related papers  (2021-06-05T09:16:28Z)
• Zeroth-Order Algorithms for Smooth Saddle-Point Problems [117.44028458220427]
  We propose several algorithms to solve saddle-point problems using zeroth-order oracles. Our analysis shows that our convergence rate for the term is only by a $log n$ factor worse than for the first-order methods. We also consider a mixed setup and develop 1/2th-order methods that use zeroth-order oracle for the part.
  arXiv  Detail & Related papers  (2020-09-21T14:26:48Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  We find an algorithm which finds. epsilon$-approximate stationary point (with $|nabla F(x)|le epsilon$) using. $(epsilon,gamma)$surimate random random points. Our lower bounds here are novel even in the noiseless case.
  arXiv  Detail & Related papers  (2020-06-24T04:41:43Z)
• Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise [28.891930079358954]
  We provide a finite-time analysis for linear two timescale SA scheme. Our bounds show that there is no discrepancy in the convergence rate between Markovian and martingale noise. We present an expansion of the expected error with a matching lower bound.
  arXiv  Detail & Related papers  (2020-02-04T13:03:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.