Solving Stochastic Fixed-Point Equations with High Probability

• URL: http://arxiv.org/abs/2607.09097v1
• Date: Fri, 10 Jul 2026 04:59:20 GMT
• Title: Solving Stochastic Fixed-Point Equations with High Probability
• Abstract summary: We study oracle fixed-point equations $mathbfT(mathbfx) = mathbfx$ over normed spaces.<n>We introduce VR-GHAL, a variance-reduced gradual Halpern method for quadratically smoothable Banach spaces.
• Score: 22.376855234542813
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study stochastic fixed-point equations $\mathbf{T}(\mathbf{x}) = \mathbf{x}$ over normed spaces $(\mathcal{E}, \|\cdot\|)$, where the operator $\mathbf{T}$ is nonexpansive or contractive and is accessed only through unbiased stochastic evaluations with bounded second central moment. Given $ε> 0, δ\in (0, 1)$, the goal is to output $\mathbf{x} \in \mathcal{E}$ such that $\|\mathbf{T}(\mathbf{x}) - \mathbf{x}\| \leq ε$ with probability at least $1-δ$. We introduce VR-GHAL, a variance-reduced gradual Halpern method for quadratically smoothable Banach spaces. The key algorithmic ingredient is a recursive stochastic estimator based on clipped differences of oracle evaluations: instead of clipping $τ(\mathbf{x}; ξ)$ itself, we clip stochastic differences at the Lipschitz scale $γ\|\mathbf{x} - \mathbf{y}\|$. This makes the estimator pathwise Lipschitz along the algorithmic trajectory while permitting martingale concentration under finite second moments in the native norm. Our main theorem gives an anytime high-probability residual bound: on a single event of probability at least $1 - δ$, the residual decreases nearly geometrically across epochs, up to lower-order logarithmic factors. Under only bounded variance, displaying only the dependence on the target error $ε$ and Lipschitz constant $γ\in (0, 1]$ of $\mathbf{T}$, the resulting oracle complexity is $\min\{ε^{-5}, (1-γ)^{-3}ε^{-2}\}$. Under a Lipschitz-in-expectation oracle, the dependence improves to the corresponding $ε^{-3}$ nonexpansive rate (i.e., for $γ= 1$), and under samplewise nonexpansiveness to $ε^{-2}$.

Related papers

• Simple-regret rates and minimax optimality of fixed-prior expected improvement in Matérn and squared-exponential RKHSs [0.0]
  We study the expected improvement (EI) policy for minimizing a deterministic objective function $f$ on a nonempty compact set $mathcal X subsetmathbb Rd$.
  arXiv  Detail & Related papers  (2026-07-31T10:18:54Z)
• Scaling Limits of Constant-Stepsize SGD at Flat Minima [5.608222858044445]
  We study Markovian noise generated by a contractive driving chain.<n>For gradient descent (SGD) with a constant stepsize $$, the invariant law of the iterates, centered at a minimizer, describes the behavior of the algorithm over long time horizons.<n>We show that this behavior changes fundamentally for convex objectives $H$ with flat minima and (sub)quadratic tails.
  arXiv  Detail & Related papers  (2026-07-17T17:22:46Z)
• A Mathematical Theory of Top-$k$ Sparse Attention via Total Variation Distance [7.014801584517052]
  We develop a unified framework certified Top-$k$ attention truncation that quantifies error at both the distribution and output levels.<n>We show that the total-variation distance coincides with the discarded softmax tail mass and satisfies $mathrmTV(P,hat P)=1-e-mathrmTV(P,hat P)=1-e-mathrmTV(P,hat P)$.
  arXiv  Detail & Related papers  (2025-12-08T15:36:41Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (2025-10-12T15:42:44Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• Estimation and Inference in Distributional Reinforcement Learning [28.253677740976197]
  We show that a dataset of size $widetilde Oleft(frac|mathcalS||mathcalA|epsilon2 (1-gamma)4right)$ suffices to ensure the Kolmogorov metric and total variation metric between $hatetapi$ and $etapi$ is below $epsilon$ with high probability. Our findings give rise to a unified approach to statistical inference of a wide class of statistical functionals of $etapi$.
  arXiv  Detail & Related papers  (2023-09-29T14:14:53Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Near Optimal Heteroscedastic Regression with Symbiotic Learning [29.16456701187538]
  We consider the problem of heteroscedastic linear regression. We can estimate $mathbfw*$ in squared norm up to an error of $tildeOleft(|mathbff*|2cdot left(frac1n + left(dnright)2right)$ and prove a matching lower bound.
  arXiv  Detail & Related papers  (2023-06-25T16:32:00Z)
• Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
  Ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
  arXiv  Detail & Related papers  (2023-02-27T16:34:21Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• AI without networks [0.0]
  We develop a network-free framework for AI incorporating generative modeling. We demonstrate this framework with examples from three different disciplines - ethology, control theory, and mathematics. We also propose an easily computed method of credit assignment based on this framework, to help address ethical-legal challenges raised by generative AI.
  arXiv  Detail & Related papers  (2021-06-07T05:50:02Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  We study the fundamental problems of agnostically learning halfspaces and ReLUs under Gaussian marginals. Our lower bounds provide strong evidence that current upper bounds for these tasks are essentially best possible.
  arXiv  Detail & Related papers  (2020-06-29T17:10:10Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  We consider the problem of learning the best-fitting single neuron as measured by the expected square loss. For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$. For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$.
  arXiv  Detail & Related papers  (2020-05-29T07:20:35Z)

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.