Stochastic Adaptive Optimization with Unreliable Inputs: A Unified Framework for High-Probability Complexity Analysis

2025/11/24 by Scheinberg, Katya, Xie, Miaolan
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Risk and Portfolio Optimization #Stochastic Gradient Optimization Techniques

paper · doi:10.48550/arxiv.2511.19411

openalex publication_date 2025/11/24 · openalex created_date 2025/11/27 · openalex updated_date 2026/07/28

Abstract

We consider an unconstrained continuous optimization problem where, in each iteration, gradient estimates may be arbitrarily corrupted with a probability greater than 1/2. Additionally, function value estimates may exhibit heavy-tailed noise. This setting captures challenging scenarios where both gradient and function value estimates can be unreliable, making it applicable to many real-world problems, which can have outliers and data anomalies. We introduce an algorithmic and analytical framework that provides high-probability bounds on iteration complexity for this setting. The analysis offers a unified approach, encompassing methods such as line search and trust region.

Citations

• Sample Complexity Analysis for Adaptive Optimization Algorithms with Stochastic Oracles
• A Sequential Quadratic Programming Method with High Probability Complexity Bounds for Nonlinear Equality Constrained Stochastic Optimization
• First- and Second-Order High Probability Complexity Bounds for Trust-Region Methods with Noisy Oracles
• High Probability Complexity Bounds for Adaptive Step Search Based on Stochastic Oracles
• Global Convergence Rate Analysis of a Generic Line Search Algorithm with\n Noise
• Global convergence rate analysis of unconstrained optimization methods\n based on probabilistic models
• Convergence of trust-region methods based on probabilistic models

Related

• High Probability Complexity Bounds for Adaptive Step Search Based on Stochastic Oracles
• Sample Complexity Analysis for Adaptive Optimization Algorithms with Stochastic Oracles
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise
• Optimization under Persistent State-Dependent Bias: Gradient-based Method and Complexity Analysis
• Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems