First Order Oracle Complexity

Ask about this topic

Momentum

15 papers in the last four weeks, against 2 the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28
View on map

Latest papers 45

All topics
CardsList

  1. Optimal Oracle Complexity for Finite-Sum Monotone Inclusions

    Oct 4, 2026Qihao ZhouFirst Order Oracle ComplexityMonotone Variational Inequalities

    Independent Researcher.

  2. Optimal Stochastic Bilevel Optimization with First-Order Oracles

    Oct 1, 2026Linxuan Pan, Junchi YangBilevel OptimizationFirst Order Oracle Complexity

    The Chinese University of Hong Kong, Shenzhen

  3. Convex Optimization Is Free When Accuracy Is Expensive

    Sep 28, 2026Arthur Paing, Arthur JacotConvex OptimizationFirst Order Oracle Complexity

    Ecole polytechnique Palaiseau, France · Courant Institute, NYU New York, USA

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

    Sep 24, 2026Ruichen Jiang, TaeHo YoonMonotone Variational InequalitiesProximal Operators

    Google Research · Johns Hopkins University

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

    Sep 21, 2026Dan GarberFirst Order Oracle ComplexityStochastic Convex Optimization

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

  6. The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization

    Sep 20, 2026Guy KornowskiStochastic Convex OptimizationFirst Order Oracle Complexity

  7. Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates

    Sep 17, 2026David Martínez-Rubio, Cristóbal GuzmánConvex OptimizationLipschitz Continuity

    IMDEA Software Institute, Madrid, Spain · Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile, Santiago, Chile

  8. The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings

    Sep 17, 2026David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán +1Convex OptimizationLipschitz Continuity

    IMDEA Software Institute, Madrid, Spain · Purdue University, West Lafayette, IN, USA · Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile, Santiago, Chile +1

  9. Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities

    Sep 14, 2026Jun-Hyun Kim, Ahmet AlacaogluMonotone Variational InequalitiesConvergence

    University of British Columbia, Vancouver. · Department of Mathematics, University of British Columbia, Vancouver.

  10. Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions

    Sep 14, 2026Weiming Ou, Xiao WangLog-Concave DistributionsOptimal Sample Complexity

    Shanghai University of Finance and Economics · MoE Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics

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

    Sep 9, 2026Xuan LiFirst Order Oracle ComplexityIndependent-Pool Single-Draw Oracle

    University of New South Wales, Sydney, Australia

  12. A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over 2−22-\sqrt{2} Entails Exponential Queries or Linear Recourse

    Sep 9, 2026Shi Fu, Qixin Zhang, Dacheng TaoSubmodular FunctionsFirst Order Oracle Complexity

    Nanyang Technological University, Singapore

  13. When Does Low-Bit Quantization Preserve the Decisions of Vector Search?

    Sep 9, 2026Wenxuan Xiao, Xu CaoResidual Vector QuantizationVector Database

    Astrmira Tech.

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

    Sep 8, 2026Jelena Diakonikolas, Cristóbal Guzmán, David Martínez-RubioFirst Order Oracle ComplexityFixed-Point Iteration

    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

  15. How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond

    Sep 8, 2026Ahmet AlacaogluMonotone Variational InequalitiesConvex Optimization

    Department of Mathematics, University of British Columbia

  16. A Contract-Grade Verifier for LLM-Generated GPU Kernels, and a Native Blackwell Backward for the Gated-Linear-Recurrence Family

    Aug 13, 2026Rishi Shah, Rishav ShresthaGraphics Processing Unit KernelsCorrectness

    E3A Healthcare

  17. A Quantum/Classical Example Oracle Separation for Making Things Up

    Aug 12, 2026Kenny ChenQuantum LearningQuantum Processor

    The University of Sydney

  18. Halpern Iteration Achieves O~(ε−1/p)\tilde{\mathcal{O}}(ε^{-1/p}) ppth-Order Oracle Complexity for Monotone Variational Inequalities

    Aug 9, 2026Lesi Chen, Xinliang Zhang, Hengyu Wang +3Monotone Variational InequalitiesFirst Order Oracle Complexity

    1IIIS, Tsinghua University · Apex Intelligence · School of Mathematical Sciences, Tongji University +2

  19. Provably Learning Multi-Head Attention with Queries

    Aug 4, 2026Sunyeop Kim, Insung Kim, Jian GuoMulti-Head AttentionRectified Linear Unit

    Korea University, Republic of Korea · Nanyang Technological University, Singapore

  20. Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes

    Jul 25, 2026Asha Barua, Sajad KhodadadianPolicy GradientMarkov Decision Processes

    Grado Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061, USA.

  21. Closed-Loop Generative Selection: Convergence, Memory, and Noisy Oracles

    Jul 24, 2026Konstantin Fackeldey, Christof SchütteDrug DesignEvolutionary Optimization

    Zuse Institute Berlin, Takustraße 7, 14195 Berlin, Germany · Institute for Mathematics, Technical University Berlin, Fasanenstr 89,10623 Berlin, Germany · Department of Mathematics and Computer Science, Freie Universität Berlin, Arnimallee 6, 14195 Berlin, Germany

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

    Jul 21, 2026Michael Menart, Aleksandar Nikolov, Ohad ShamirFirst Order Oracle ComplexityLower Bounds

    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

  23. Solving Stochastic Fixed-Point Equations with High Probability

    Jul 10, 2026Jelena DiakonikolasFixed-Point IterationStochastic Approximation

    Department of Computer Sciences University of Wisconsin-Madison

  24. Computing with Stochastic Oracles in AI-Augmented Computation

    Jul 8, 2026Jie WangFirst Order Oracle ComplexityCounter Turing Test

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

  25. What Does a Discrete Diffusion Model Learn?

    Jul 6, 2026Rodrigo Casado Noguerales, Bernhard Schölkopf, Thomas Hofmann +1Diffusion ModelsKullback-Leibler Divergence

    1ETH Zurich · 2Max Planck Institute for Intelligent Systems, Tübingen · 3ELLIS Institute Tübingen

  26. Finding Stationary Points by Comparisons

    Jun 25, 2026Helin Wang, Chenyi Zhang, Xiwen Tao +2Stationary PointFirst Order Oracle Complexity

    School of Electronics Engineering and Computer Science, Peking University · Center on Frontiers of Computing Studies, Peking University · Computer Science Department, Stanford University +1

  27. Unbiased Canonical Set-Valued Oracles Via Lattice Theory

    Jun 24, 2026Jobst HeitzigFirst Order Oracle ComplexityProbability

    PIK-Potsdam

  28. Token Complexity of Certifying Stochastic-Oracle Reliability

    Jun 23, 2026Jie WangFirst Order Oracle ComplexityEqual Error Rate

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

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

    Jun 18, 2026Dongmin Lee, William Lu, Anuran MakurGradient DescentFirst Order Oracle Complexity

    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

  30. Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization

    Jun 3, 2026Dongruo ZhouStochastic Convex OptimizationFirst Order Oracle Complexity

    Department of Computer Science, Indiana University Bloomington, IN 47408, USA

  31. Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise

    May 23, 2026Zhuanghua Liu, Luo LuoStochastic Convex OptimizationConvex Optimization

  32. Orthologic for SAT Solving

    May 14, 2026Vladislas de Haldat, Simon Guilloud, Viktor KunčakSatisfiabilityFirst Order Oracle Complexity

    1EPFL

  33. Autoregressive Learning in Joint KL: Sharp Oracle Bounds and Lower Bounds

    May 12, 2026Yunbei Xu, Yuzhe Yuan, Ruohan ZhanAutoregressive ModelKullback-Leibler Divergence

    National University of Singapore · University College London

  34. A Parameter-Free First-Order Algorithm for Non-Convex Optimization with  O~(ε−5/3)\tilde{\mkern1mu O}(ε^{-5/3}) Global Rate

    May 4, 2026Sichao Xiong, Sadok Jerad, Coralia CartisFirst Order Oracle ComplexityOptimal Sample Complexity

    Department of Computer Science University of Oxford Oxford, OX1 3QG · Mathematical Institue University of Oxford Oxford, OX2 6GG

  35. Randomized Subspace Nesterov Accelerated Gradient

    May 1, 2026Gaku Omiya, Pierre-Louis Poirion, Akiko TakedaMomentum Stochastic Gradient DescentFirst Order Oracle Complexity

    Department of Mathematical Informatics, The University of Tokyo, Tokyo, Japan · Center for Advanced Intelligence Project, RIKEN, Tokyo, Japan

  36. Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation

    May 1, 2026Haichen Hu, Jian Qian, David Simchi-LeviModel-Based Reinforcement LearningMarkov Decision Processes

    Laboratory for Information and Decision Systems · Department of AI and Data Science

  37. Matroid Algorithms Under Size-Sensitive Independence Oracles

    Apr 30, 2026Kiarash Banihashem, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz +1First Order Oracle ComplexityUpper Bounds

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

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

    Apr 17, 2026Arda Fazla, Ege C. Kaya, Antesh Upadhyay +1Stochastic Convex OptimizationStochastic Gradient Descent

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

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

    Nov 17, 2025Michael Menart, Aleksandar NikolovFirst Order Oracle ComplexityConvex Loss

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

  40. Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity

    Nov 4, 2025Dan GarberConvex OptimizationFirst Order Oracle Complexity

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

  41. Accelerated stochastic first-order method for convex optimization under heavy-tailed noise

    Oct 13, 2025Chuan He, Bowen Li, Zhaosong LuStochastic Convex OptimizationConvex Optimization

    Department of Mathematics, Linköping University, Sweden · Department of Industrial and Systems Engineering, University of Minnesota, USA

  42. Minimisation of Quasar-Convex Functions Using Random Zeroth-Order Oracles

    May 4, 2025Amir Ali Farzin, Yuen-Man Pun, Philipp Braun +1NonconvexZeroth-Order

    School of Engineering Australian National University · Department of Electrical and Electronic Engineering University of Melbourne · Department of Electrical and Electronic Engineering22 University of Melbourne

  43. Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization

    Apr 13, 2025Qiankun Shi, Han Yuan, Xiao Wang +1Stochastic Convex OptimizationMirror Descent

    Sun Yat-sen University, Guangzhou, 510006, China · Pengcheng Laboratory, Shenzhen, 518066, China · Sun Yat-sen University, Guangzhou, 518066, China +1

  44. TrafficGamer: Reliable and Flexible Traffic Simulation for Safety-Critical Scenarios with Game-Theoretic Oracles

    Aug 28, 2024Guanren Qiao, Guorui Quan, Jiawei Yu +2Microscopic Traffic SimulationsAutomated Vehicles

    Chinese University of Hong Kong, Shenzhen, Guangdong, 518172 China · University of Manchester, Manchester, M13 9PL England · Shenyang MXNavi Co., Ltd, Shenyang, 110169 China

  45. Gradient Testing and Estimation by Comparisons

    May 19, 2024Xiwen Tao, Chenyi Zhang, Helin Wang +2First Order Oracle ComplexityComparison

    School of Electronics Engineering and Computer Science, Peking University · Computer Science Department, Stanford University · Center on Frontiers of Computing Studies, Peking University +1