Overview

Oracle complexity measures the number of calls an algorithm needs when it can access a problem only through responses such as gradients, stochastic samples, membership answers, or proximal updates. Researchers develop algorithms and matching lower bounds for settings including convex and nonconvex optimization, online learning, monotone inclusions, and sampling, using methods such as variance reduction, proximal iterations, and higher-order updates. A central finding is that query costs depend not only on accuracy and dimension, but also on randomness, memory, oracle fidelity, and the cost or strength of each response. For many settings upper and lower bounds now match, while gaps remain across oracle models and regimes, including how to trade query budgets against wall-clock cost or memory.

Latest papers

CardsList

35 papers4 papers in the last four weeks, down 67% on the four weeks before. 0.0% of all new papers.

  1. On the Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization with Exact Proximal Oracles

    Nov 3, 2026Yuxing Peng, Zhiqing Tang, Weijia JiaMin-Max OptimizationOracle Complexity

  2. Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex (L0,L1)(L_0,L_1)-Smooth Functions

    Nov 3, 2026Mikhail Rudomanov, Ivan Fomin, Alexander V. Gasnikov +1Smooth Convex OptimizationOracle Complexity

  3. Stochastic and Noisy Oracles in Smooth Continuous Optimization

    Oct 29, 2026Albert S. Berahas, Liyuan Cao, Katya ScheinbergStochastic Optimization ConvergenceOracle Complexity

  4. Acceleration and its Limits in Gaussian Variational Inference

    Oct 14, 2026Jaesung R. Park, Uijeong Jang, Yifan ChenOracle ComplexityVariational Inference

  5. Optimal Stochastic Bilevel Optimization with First-Order Oracles

    Oct 1, 2026Linxuan Pan, Junchi YangStochastic Bilevel OptimizationOracle Complexity

  6. Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games

    Sep 30, 2026Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng XiongLast-Iterate ConvergenceOracle Complexity

  7. Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization

    Sep 21, 2026Dan GarberOracle ComplexityOptimization Convergence Analysis

  8. Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps

    Sep 8, 2026Jelena Diakonikolas, Cristóbal Guzmán, David Martínez-RubioOracle ComplexityStochastic Approximation

  9. Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness

    Aug 30, 2026Yuxing Peng, Zhiqing Tang, Weijia JiaOracle ComplexityNonconvex Optimization

  10. Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory

    Jul 21, 2026Michael Menart, Aleksandar Nikolov, Ohad ShamirQuery ComplexityOracle Complexity

  11. Computing with Stochastic Oracles in AI-Augmented Computation

    Jul 8, 2026Jie WangOracle ComplexityAdaptive Computation

  12. Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model

    Jun 18, 2026Xiaoyu Li, Junwei Yu, Jiaojiao Jiang +2Query ComplexityOracle Complexity

  13. On the Oracle Complexity of Interpolation-Based Gradient Descent

    Jun 18, 2026Dongmin Lee, William Lu, Anuran MakurOracle ComplexityGradient Descent

  14. Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity

    May 29, 2026Alexandra Suvorikova, Igor Pavlov, Artem Vasin +4Stochastic OptimizationOracle Complexity

  15. Complexity of Non-Log-Concave Sampling in Fisher Information

    May 15, 2026Sinho Chewi, Andre WibisonoOracle ComplexityProximal Sampling

  16. Min-Max Optimization Requires Exponentially Many Queries

    May 13, 2026Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1Query ComplexityOracle Complexity

  17. Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning

    May 8, 2026Idan Attias, Steve Hanneke, Arvind RamaswamiOracle ComplexityOnline Learning

  18. Matroid Algorithms Under Size-Sensitive Independence Oracles

    Apr 30, 2026Kiarash Banihashem, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz +1Query ComplexityOracle Complexity