Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps

• URL: http://arxiv.org/abs/2609.09524v1
• Date: Tue, 08 Sep 2026 23:09:39 GMT
• Title: Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps
• Abstract summary: We study the oracle complexity of computing a point with small fixed-point residual $|T(x)-x| leq $, for a general norm $|cdot|$ and a self-map $T$ of a compact convex set.<n>We provide an algorithm that solves such instances for any norm with a weak Rademacher type $q > 1$, with high probability.
• Score: 28.438129186461598
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the oracle complexity of computing a point with small fixed-point residual $\|T(x)-x\| \leq ε$, for a general norm $\|\cdot\|$ and a self-map $T$ of a compact convex set. We study this problem in the setting where $T$ is nonexpansive with respect to the same norm $\|\cdot\|$ and accessed via an unbiased stochastic oracle with bounded variance $σ^2$. We provide an algorithm that solves such instances for any norm with a weak Rademacher type $q > 1$, with high probability. The algorithm is based on a recursive anchoring technique. For type-$2$ spaces, such as $\ell_p$-spaces for $p \in [2, \infty]$, our algorithm attains stochastic oracle complexity $\tilde O(σ^2 ε^{-3} + ε^{-1})$. We further prove a near-matching lower bound (i.e., matching up to poly-log factors) for such $\ell_{\infty}$-norm instances in high dimensions. Our lower bound holds against any randomized algorithm that succeeds with constant probability. It further extends to settings with ``sparse'' noise, where variance measured with respect to any $\ell_p$ norm is of the same order, ruling out the possibility of improving oracle complexity as a function of $\varepsilon$ by measuring variance in a non-matching $\ell_p$ norm.

Related papers

• Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions [5.603202398374589]
  The potential is $$-strongly convex and $L$-smooth, with an unknown mode in the ball of radius $-1/2$ about the origin.<n>We prove that the tight complexity of sampling a distribution within $$-TV distance from the target distribution is [ Nstar_textTV=!left(log(1+)+ frac2right), ] where $:=frac L$ is the condition number.
  arXiv  Detail & Related papers  (2026-09-11T08:44:06Z)
• SGHA: A Single-Loop Fully First-Order Algorithm for Nonconvex-Strongly-Convex Bilevel Optimization [9.118433290504035]
  We show that Stoc-SGHA achieves an oracle complexity of $Oleft(bar_y-4)$ with at least $1$ for any $in(1)$, and an complexity of $Oleft(bar_y-4)$ under an additional assumption.<n>In a deterministic setting, Stoc-SGHA achieves an oracle complexity of $Oleft(bar_y)$ with at least $1$ for any $in(1)$, and an complexity of $Oleft(bar_y)$ under
  arXiv  Detail & Related papers  (2026-08-24T13:00:40Z)
• A Simple Algorithm for Best Separable State [5.5559749120901385]
  We study the best separable state problem (BSS), which asks for the maximum acceptance probability of a quantum measurement over unentangled states.<n>In classical terms, the goal is to maximize $langle(x otimes y), M (x otimes y)rangle$ over unit vectors $x,y$ where $0 preceq M preceq I$.
  arXiv  Detail & Related papers  (2026-08-10T19:04:15Z)
• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibria is a powerful and flexible framework at the heart of online learning and game theory.<n>We show that an efficient online algorithm incurs average $Phi$-regret at most $epsilon$ using $textpoly(d, k)/epsilon2$ rounds.<n>We also show nearly matching lower bounds in the online setting, thereby obtaining for the first time a family of deviations that captures the learnability of $Phi$-regret.
  arXiv  Detail & Related papers  (2025-02-25T19:08:26Z)
• Fixed Point Computation: Beating Brute Force with Smoothed Analysis [28.978340288565118]
  We propose a new algorithm that finds an $varepsilon$-approximate fixed point of a smooth function from the $n$-dimensional $ell$ unit ball to itself.<n>The algorithm's runtime is bounded by $eO(n)/varepsilon$, under the smoothed-analysis framework.
  arXiv  Detail & Related papers  (2025-01-18T21:32:26Z)
• Algorithms for Sparse LPN and LSPN Against Low-noise [1.2143710013809321]
  We consider sparse variants of the classical Learning Parities with random Noise (LPN) problem.<n>Our main contribution is a new framework that provides learning algorithms against low-noise for both Learning Sparse Parities (LSPN) problem and sparseCSP problem.
  arXiv  Detail & Related papers  (2024-07-27T08:57:04Z)
• Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems [0.0]
  We show that to solve feasibility problems with accuracy any deterministic algorithm either uses $d1+delta$ bits of memory or must make at least $1/(d0.01delta epsilon2frac1-delta1+1.01 delta-o(1))$ oracle queries. We also show that randomized algorithms either use $d1+delta$ memory or make at least $1/(d2delta epsilon2(1-4delta)-o(1))$ queries for any $deltain
  arXiv  Detail & Related papers  (2024-04-10T04:15:50Z)
• On the Complexity of First-Order Methods in Stochastic Bilevel Optimization [9.649991673557167]
  We consider the problem of finding stationary points in Bilevel optimization when the lower-level problem is unconstrained and strongly convex. Existing approaches tie their analyses to a genie algorithm that knows lower-level solutions and, therefore, need not query any points far from them. We propose a simple first-order method that converges to an $epsilon$ stationary point using $O(epsilon-6), O(epsilon-4)$ access to first-order $y*$-aware oracles.
  arXiv  Detail & Related papers  (2024-02-11T04:26:35Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underlying matrix is changing slowly. We provide a novel binary tree summation procedure that simultaneously estimates all $m$ traces up to $epsilon$ error with $delta$ failure probability. Our lower bounds (1) give the first tight bounds for Hutchinson's estimator in the matrix-vector product model with Frobenius norm error even in the static setting, and (2) are the first unconditional lower bounds for dynamic trace estimation.
  arXiv  Detail & Related papers  (2022-09-30T04:15:44Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  We consider online statistical inference of constrained nonlinear optimization problems.<n>We apply the Sequential Quadratic Programming (StoSQP) method to solve these problems.
  arXiv  Detail & Related papers  (2022-05-27T00:34:03Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  We study active sampling algorithms for linear regression, which aim to query only a small number of entries of a target vector. We show that this dependence on $d$ is optimal, up to logarithmic factors. We also provide the first total sensitivity upper bound $O(dmax1,p/2log2 n)$ for loss functions with at most degree $p$ growth.
  arXiv  Detail & Related papers  (2021-11-09T00:20:01Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

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.