Oracle Complexity

Ask about this topic

Momentum

9 papers in the last four weeks, with none the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28
View on map

Latest papers 19

All topics
CardsList

  1. Optimal Oracle Complexity for Finite-Sum Monotone Inclusions

    Oct 4, 2026Qihao ZhouStochastic OptimizationOracle Complexity

    Independent Researcher.

  2. Optimal Stochastic Bilevel Optimization with First-Order Oracles

    Oct 1, 2026Linxuan Pan, Junchi YangOracle ComplexityNonconvex Stochastic Optimization

    The Chinese University of Hong Kong, Shenzhen

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

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

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

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

  7. The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization

    Sep 20, 2026Guy KornowskiStochastic OptimizationOracle Complexity

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

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

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

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

  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

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

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

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

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

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

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

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

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