analiza aiqbench
This paper advances stochastic optimization theory by achieving near-optimal oracle complexity for dual-anchoring methods in monotone root-finding problems, effectively closing the gap between deterministic and stochastic performance bounds. By integrating stochastic resolvent approximation with variance control, the authors improve convergence rates in noise-dominated regimes without requiring strong monotonicity assumptions. The work represents a significant theoretical contribution to the foundations of machine learning optimization algorithms.
Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding
arXiv:2609.36033v1 Announce Type: cross Abstract: Among distinct optimal acceleration mechanisms for deterministic monotone root-finding problems and fixed-point problems, dual-anchoring has recently been shown to admit a more robust direct stochastic extension than standard anchor acceleration. However, without additional strong monotonicity, the existing stochastic dual-anchoring guarantee has two limitations: first, it requires cocoercivity in expectation, and second, it attains only $O(\epsilon^{-3})$ oracle complexity, leaving a gap to the near-optimal $\tilde{O}(\epsilon^{-2})$ complexity achieved by other methods. In this work, we address both of these limitations by combining dual-anchoring with stochastic resolvent approximation and optimized variance control. For unbiased stochastic oracles with variance bounded by $\sigma^2$, where sample operators are monotone and uniformly $L$-Lipschitz, our algorithm finds a point with $\epsilon$-residual with a near-optimal oracle complexity of $O ( (LD / \epsilon) \ell + (\sigma^2 / \epsilon^2) \ell^2)$, where $\ell = \log (1 + LD / \epsilon)$ and $D$ is the initial distance to a solution. This result improves the best known oracle complexity in the noise-dominated regime under these samplewise assumptions, reducing the poly-logarithmic factor from cubic to quadratic.
Abstract:Among distinct optimal acceleration mechanisms for deterministic monotone root-finding problems and fixed-point problems, dual-anchoring has recently been shown to admit a more robust direct stochastic extension than standard anchor acceleration. However, without additional strong monotonicity, the existing stochastic dual-anchoring guarantee has two limitations: first, it requires cocoercivity in expectation, and second, it attains only $O(\epsilon^{-3})$ oracle complexity, leaving a gap to the near-optimal $\tilde{O}(\epsilon^{-2})$ complexity achieved by other methods. In this work, we address both of these limitations by combining dual-anchoring with stochastic resolvent approximation and optimized variance control. For unbiased stochastic oracles with variance bounded by $\sigma^2$, where sample operators are monotone and uniformly $L$-Lipschitz, our algorithm finds a point with $\epsilon$-residual with a near-optimal oracle complexity of $O ( (LD / \epsilon) \ell + (\sigma^2 / \epsilon^2) \ell^2)$, where $\ell = \log (1 + LD / \epsilon)$ and $D$ is the initial distance to a solution. This result improves the best known oracle complexity in the noise-dominated regime under these samplewise assumptions, reducing the poly-logarithmic factor from cubic to quadratic.
Optimization and Control (math.OC); Machine Learning (cs.LG)
arXiv:2609.36033 [math.OC]
(or arXiv:2609.36033v1 [math.OC] for this version)
https://doi.org/10.48550/arXiv.2609.36033 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 270 cuvinte
