Fetching the paper…
Reading the bibliography…
We study the first-order convex optimization problem, where we have black-box access to a (not necessarily smooth) function $f:\mathbb{R}^n \to \mathbb{R}$ and its (sub)gradient.
The complexity of partial derivatives
Walter Baur and Volker Strassen · 1983
Earlier work this paper cites.
Problem complexity and method efficiency in optimization
Arkadiĭ Nemirovsky and David Borisovich Yudin · 1983
Earlier work this paper cites.
On parallel complexity of nonsmooth convex optimization
A. Nemirovski · 1994
Earlier work this paper cites.
An elementary introduction to modern convex geometry
Keith Ball · 1997
Earlier work this paper cites.
Strengths and weaknesses of quantum computing
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani · 1997
Earlier work this paper cites.
Introductory Lectures on Convex Optimization
Yurii Nesterov · 2004
Earlier work this paper cites.
Fast quantum algorithm for numerical gradient estimation
Stephen P. Jordan · 2005
Earlier work this paper cites.
Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, Second Edition
Andreas Griewank and Andrea Walther · 2008
Earlier work this paper cites.
Quantum algorithms for learning symmetric juntas via adversary bound
Aleksandrs Belovs · 2014
Earlier work this paper cites.
Convex optimization: Algorithms and complexity
Sébastien Bubeck · 2015
Cited alongside, same era.
Quantum SDP-solvers: Better upper and lower bounds
Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf · 2017
Cited alongside, same era.
Quantum speed-ups for solving semidefinite programs
Fernando G.S.L. Brandão and Krysta M. Svore · 2017
Cited alongside, same era.
Lower bound for randomized first order convex optimization
Blake Woodworth and Nathan Srebro · 2017
Cited alongside, same era.
Eric Balkanski and Yaron Singer · 2018
Cited alongside, same era.
Complexity of highly parallel non-smooth convex optimization
Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford · 2019
Later among the works it cites.
Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning
Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu · 2019
Later among the works it cites.
Lower bounds for parallel and randomized convex optimization
Jelena Diakonikolas and Cristóbal Guzmán · 2019
Later among the works it cites.
Optimizing quantum optimization algorithms via faster quantum gradient computation
András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe · 2019
Later among the works it cites.
Quantum gradient descent and Newton’s method for constrained polynomial optimization
Patrick Rebentrost, Maria Schuld, Leonard Wossnig, Francesco Petruccione, and Seth Lloyd · 2019
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Sham M Kakade and Jason D Lee · 2018
Cited alongside, same era.
Lectures on convex optimization
Yurii Nesterov · 2018
Cited alongside, same era.
Improvements in Quantum SDP-Solving with Applications
Joran van Apeldoorn and András Gilyén · 2019
Cited alongside, same era.
Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf · 2020
Closest in time.
Quantum algorithms and lower bounds for convex optimization
Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu · 2020
Closest in time.
Quantum gradient descent for linear systems and least squares
Iordanis Kerenidis and Anupam Prakash · 2020
Closest in time.