{"ID":6497826,"CreatedAt":"2026-07-13T01:19:40.13847098Z","UpdatedAt":"2026-07-14T01:36:59.12045529Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.09097","arxiv_id":"2607.09097","title":"Solving Stochastic Fixed-Point Equations with High Probability","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 $ε\u003e 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}$.","short_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 $ε\u003e 0, δ\\in (0, 1)$, the go...","url_abs":"https://arxiv.org/abs/2607.09097","url_pdf":"https://arxiv.org/pdf/2607.09097v1","authors":"[\"Jelena Diakonikolas\"]","published":"2026-07-10T04:59:20Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.DS\",\"cs.LG\",\"stat.ML\"]","methods":"[]","has_code":false}