Sample Complexity of Policy Gradient for Log-Growth Control

• URL: http://arxiv.org/abs/2605.26640v1
• Date: Tue, 26 May 2026 07:24:14 GMT
• Title: Sample Complexity of Policy Gradient for Log-Growth Control
• Abstract summary: We study the sample complexity of policy gradient for log-growth control.<n>We prove that projected mini-batch policy gradient attains total sample complexity.
• Score: 23.86784769848408
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the sample complexity of policy gradient for log-growth control -- the problem of learning, from observed state transitions, a feedback gain that optimally stabilizes a scalar linear system driven through a multiplicative-noise actuation channel. The objective $J(K) = \mathbb{E}[\log|1+BK|]$ is the top Lyapunov exponent of the closed loop. This problem carries a structural difficulty we call the cusp obstruction: the optimal gain $K^*$ always places the noise singularity $b_{\rm sing}(K) = -1/K$ in the interior of the support. At this singular optimum the policy gradient exists only as a Cauchy principal value, not as a Lebesgue integral, and the natural single-sample gradient estimator has infinite variance. Standard first-order stochastic-optimization analysis is thus inapplicable at the optimum, and merely smoothing the objective does not resolve the difficulty. The obstruction, however, has an exploitable symmetry: the Cauchy kernel is an odd function of the displacement from the moving pole, so pairing each observation with its reflection through the pole cancels the divergent part. This one cancellation simultaneously controls the population curvature, the gradient-estimator variance, and the bias incurred when the noise density is estimated. Combining these bounds with a closed-form single-transition gradient oracle, we prove that projected mini-batch policy gradient, initialized in any compact subset of the stabilizing region, attains total sample complexity $\tilde{O}(1/η)$ when the noise density is known and $\tilde{O}(η^{-(2s+1)/(2s)})$ when it must be estimated, for $C^s$ noise densities with $s \geq 2$.

Related papers

• Beyond Bounded Variance: Variance-Reduced Normalized Methods for Nonconvex Optimization under Blum-Gladyshev Noise [7.692336118507715]
  We study non-smoother optimization under the Blum-Gladyshev ($mathsfBG$-0) noise model.<n>We prove that normalized gradient descent with momentum, using only one parameter per gradient, converges under $mathsfBG$-0 noise with complexity $O(varepsilon-6)$.
  arXiv  Detail & Related papers  (2026-05-14T18:27:49Z)
• Grokking as a Variance-Limited Phase Transition: Spectral Gating and the Epsilon-Stability Threshold [0.0]
  Generalization requires the textitanisotropic rectification unique to adaptives, which directs noise into the tangent space of the solution.<n>This work analyzes AdamW dynamics on modular arithmetic tasks, revealing a Spectral Gating'' mechanism that regulates the transition from generalization to memorization.
  arXiv  Detail & Related papers  (2026-03-16T16:18:18Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Discrete Double-Bracket Flows for Isotropic-Noise Invariant Eigendecomposition [7.186083931122418]
  We study matrix-free eigendecomposition under a matrix-vector product (MVP) oracle.<n>Standard approximation methods either use fixed steps that couple stability to $|C_k|$, or adapt steps that slow down due to vanishing updates.<n>We establish global convergence via strict-saddle for the diagonalization objective and an input-to-state stability analysis, with complexity scaling as $O(|C_e|2 / (2))$ under trace-free perturbations.
  arXiv  Detail & Related papers  (2026-02-14T13:09:29Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  We analyze $f$-divergence-regularized offline policy learning.<n>For reverse Kullback-Leibler (KL) divergence, we give the first $tildeO(epsilon-1)$ sample complexity under single-policy concentrability.<n>We extend our analysis to dueling bandits, and we believe these results take a significant step toward a comprehensive understanding of $f$-divergence-regularized policy learning.
  arXiv  Detail & Related papers  (2025-02-09T22:14:45Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  We consider clipped optimization problems with heavy-tailed noise with structured density. We show that it is possible to get faster rates of convergence than $mathcalO(K-(alpha - 1)/alpha)$, when the gradients have finite moments of order. We prove that the resulting estimates have negligible bias and controllable variance.
  arXiv  Detail & Related papers  (2023-11-07T17:39:17Z)
• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  We show that wetailed high-prob convergence guarantees of learning on streaming data in the presence of heavy-tailed noise. We demonstrate analytically and that $ta$ can be used to the preferred choice of setting for a given problem.
  arXiv  Detail & Related papers  (2023-10-28T18:53:41Z)
• Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach [36.88301225561535]
  offline reinforcement learning aims to learn from pre-collected datasets without active exploration. Existing approaches adopt a pessimistic stance towards uncertainty by penalizing rewards of under-explored state-action pairs to estimate value functions conservatively. We show that the distributionally robust optimization (DRO) based approach can also address these challenges and is asymptotically minimax optimal
  arXiv  Detail & Related papers  (2023-05-22T17:50:18Z)
• Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization [11.017632675093628]
  Coordinate-type subgradient methods for addressing nonsmooth problems are relatively underexplored due to the set of properties of the Lipschitz-type assumption.
  arXiv  Detail & Related papers  (2022-06-30T02:17:11Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• A gradient estimator via L1-randomization for online zero-order optimization with two point feedback [93.57603470949266]
  We present a novel gradient estimator based on two function evaluation and randomization. We consider two types of assumptions on the noise of the zero-order oracle: canceling noise and adversarial noise. We provide an anytime and completely data-driven algorithm, which is adaptive to all parameters of the problem.
  arXiv  Detail & Related papers  (2022-05-27T11:23:57Z)
• Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance [14.06947898164194]
  Heavy tails emerge in gradient descent (SGD) in various scenarios. We provide convergence guarantees for SGD under a state-dependent and heavy-tailed noise with a potentially infinite variance. Our results indicate that even under heavy-tailed noise with infinite variance, SGD can converge to the global optimum.
  arXiv  Detail & Related papers  (2021-02-20T13:45:11Z)

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.