Oracle Complexity

Ask about this topic

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

30 papers6 papers in the last four weeks, down 33% on the four weeks before. 0.0% of all new papers.

  1. Acceleration and its Limits in Gaussian Variational Inference

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

    Department of Mathematics, University of California, Los Angeles

  2. Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets

    Oct 9, 2026Sebastian PokuttaLMO MethodsOracle Complexity

    Zuse Institute Berlin and TU Berlin

  3. Optimal Oracle Complexity for Finite-Sum Monotone Inclusions

    Oct 4, 2026Qihao ZhouStochastic OptimizationOracle Complexity

    Independent Researcher.

  4. Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization

    Oct 4, 2026Qihao ZhouMin-Max OptimizationOracle Complexity

    Independent Researcher

  5. Optimal Stochastic Bilevel Optimization with First-Order Oracles

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

    The Chinese University of Hong Kong, Shenzhen

  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

    Department of Computer Sciences, University of Wisconsin-Madison

  7. Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization

    Sep 25, 2026Qihao ZhouOracle ComplexityMin-Max Optimization

    Independent Researcher

  8. LiTe-GS: Oracle-Efficient Next Best View Selection for 3D Gaussian Splatting

    Sep 24, 2026Vivek Pandey, Amirhossein Mollaei Khass, Nader MoteeNext-Best-View PlanningActive View Selection

  9. A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model

    Sep 24, 2026Santosh S. VempalaOracle ComplexityConstrained Optimization

    Georgia Tech

  10. Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems

    Sep 24, 2026Ruichen Jiang, TaeHo YoonOracle ComplexitySecond-Order Optimization

    Google Research · Johns Hopkins University

  11. Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization

    Sep 23, 2026Vaneet AggarwalOnline Convex OptimizationLMO Methods

    Purdue University West Lafayette, Indiana, USA

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

    Sep 21, 2026Dan GarberOracle ComplexityOptimization Convergence Analysis

    Faculty of Data and Decision Sciences Technion - Israel Institute of Technology

  13. The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization

    Sep 20, 2026Guy KornowskiStochastic OptimizationOracle Complexity

  14. An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order

    Sep 9, 2026Xuan LiQuery ComplexityOracle Complexity

    University of New South Wales, Sydney, Australia

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

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

    Department of Computer Sciences, University of Wisconsin-Madison · Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile, Santiago, Chile · IMDEA Software Institute, Madrid, Spain

  16. 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

    Institute of Artificial Intelligence and Future Networks, Faculty of Arts and Sciences, Beijing Normal University, Zhuhai 519087, China · Guangdong Key Lab of AI and Multi-Modal Data Processing, BNU-HKBU United International College, Zhuhai 519087, China

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

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

    Department of Computer Science, University of Toronto, Vector Institute · Department of Computer Science, University of Toronto · Weizmann Institute of Science and University of Toronto +1

  18. Computing with Stochastic Oracles in AI-Augmented Computation

    Jul 8, 2026Jie WangOracle ComplexityAdaptive Computation

    Richard A. Miner School of Computing and Information Sciences, University of Massachusetts, Lowell, MA 01854, USA.

  19. 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

    University of New South Wales · University of California, Berkeley · University of Sydney

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

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

    Department of Computer Science, Purdue University, West Lafayette, IN 47907, USA · Department of Computer Science and the Elmore Family School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA

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

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

    Weierstrass Institute for Applied Analysis and Stochastics, Berlin, Germany · Moscow Independent Research Institute of Artificial Intelligence, Moscow, Russia · MSU Institute for Artificial Intelligence, Moscow, Russia +3

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

    May 15, 2026Sinho Chewi, Andre WibisonoOracle ComplexityLog-Concave Sampling

    Yale University, Department of Statistics and Data Science. · Yale University, Department of Computer Science.

  23. Min-Max Optimization Requires Exponentially Many Queries

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

    Bocconi University · Politecnico di Milano · University of Oxford

  24. Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning

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

    Institute for Data, Econometrics, Algorithms, and Learning (IDEAL), hosted by UIC and TTIC · Department of Computer Science, Purdue University

  25. Matroid Algorithms Under Size-Sensitive Independence Oracles

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

    *Equal contribution 1Department of Computer Science, University of Maryland, College Park, USA.

  26. Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance

    Apr 17, 2026Arda Fazla, Ege C. Kaya, Antesh Upadhyay +1Stochastic OptimizationOracle Complexity

    School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA.

  27. Turing or Cantor: That is the Question

    Apr 12, 2026Eugene EberbachOracle Complexity

    Dept. of Eng. and Science, Rensselaer Polytechnic Institute, Hartford, CT, USA

  28. Mini-Batch Covariance, Diffusion Limits, and Oracle Complexity in Stochastic Gradient Descent: A Sampling-Design Perspective

    Mar 2, 2026Daniel Zantedeschi, Kumar MuthuramanStochastic Gradient DescentStochastic Optimization Convergence

    Muma College of Business, University of South Florida, Tampa, FL, USA · McCombs School of Business, University of Texas at Austin, Austin, TX, USA

  29. On the Condition Number Dependency in Bilevel Optimization

    Nov 27, 2025Lesi Chen, Jingzhao ZhangOracle ComplexityNonconvex Optimization

    IIIS, Tsinghua University

  30. On the Gradient Complexity of Private Optimization with Private Oracles

    Nov 17, 2025Michael Menart, Aleksandar NikolovQuery ComplexityOracle Complexity

    Department of Computer Science, University of Toronto, Vector Institute · Department of Computer Science, University of Toronto