Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This work considers the task of minimizing approximately convex functions and that of regret minimization for stochastic convex bandits. The results here using a quantum evaluation oracle offers an improvement (in T for bandits, and dimension for optimization) compared to classical models of access.

strengths_and_weaknesses: For someone unfamiliar with quantum algorithms (like me), the first disclaimer here is that these speed-ups result from the being able to query the noisy function in superposition. These are stronger models of access than classical counterparts, and can therefore overcome classical lower bounds like T^0.5 for regret. 

The optimization result is easier to understand of the two. The speed-ups result from amplitude amplification (of which Grover is an example) like properties of quantum hit-and-run. The algorithmic primitives that avoid decoherence seem sound.

I am concerned regarding the regret result. The minimization of approximately convex immediately yields an improvement (n^5/eps) for sample complexity of the best point with access to noisy evaluations. This is sound and this reduction is present in BLNR; here there’s an added advantage of being able to estimate the mean of a Gaussian at 1/N rate. 

The paper claims a regret result. But to the best of my reading, the regret is not measured on the points the algorithm actually queries (which are quantum superpositions), but an a separate (vector) point chosen as “output”. If so, this goes against the usual definition, where exploration induces a penalty absent here. Can the authors comment on this? Failing this, I think it would be best to present this as a best-arm result (which is also what BLNR does).
questions: Please see above. Additionally—

— Can the authors comment on the number of calls made to the membership oracle for the set K? Quantum algorithms also have an advantage in this sense because separation oracles carry the same complexity as membership ones (e.g. https://arxiv.org/abs/1809.00643)

limitations: Yes
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The manuscript "Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits" investigates the use of quantum algorithms for the optimization of approximately convex functions. In particular, the authors describe how to achieve a polynomial quantum speedup in terms of the dimension $n$ compared to the best-known classical method by exploiting quantum walks. The framework is then adapted to give a quantum algorithm for zeroth-order stochastic convex bandits, showing a exponential speedup in the number of rounds $T$.

strengths_and_weaknesses: The presented work is purely theoretical. The authors start with clear statements of their contributions in form of two major theorems and address open questions. Then, the basic concepts of quantum computing, classical and quantum walks, and Hit-and-Run walks are explained in a clear and comprehensible fashion. Section 3 gives a condensed overview of the main results and their derivations. That is, a "user-friendly" quantum walk framework is introduced and the authors show how to apply this framework for optimizing approximately convex functions. Both parts are reconsidered and described in detail in the Appendix. This way of structuring the paper is a good idea, but leads to some repeated or redundant statements.

Overall, the manuscript is well-written and all algorithms and results are described in greater detail. The work is very interesting and shows that the use of quantum walks can improve the query complexity of sampling methods. I recommend it for publication after minor revision



questions: (1) page 2, line 43: missing comma after "technology"

(2) page 2, line 54: It is clear what is meant by "... if we measure *this* quantum state, ...", but the formulation is confusing.

(3) page 2, lines 61-62: refer to Appendix C for details and proof

(4) page 5, line 177: Why is the integration variable changed in the definition of $\psi_x$? On page 4, line 143 and page 13, line 439, the integral is defined w.r.t. the second variable of $P$. This is also the case in [34,35].

(5) page 5, line 183: "require*s*"

(6) page 6, line 186: Why the term "user-fiendly"? Could you elaborate on that?

(7) page 7, line 244: Instead of having two nearly identical pseudo codes, it might make sense to replace Alg. 1 by Alg. 6 without repetition in Appendix C.3.

(8) page 9, line 283: $\mathcal{O}^{stoc}_f = \mathcal{O}^{\tau,\alpha}_f$ in Alg. 2, line 12?

(9) page 11, lines 380-383: [35] and [36] are identical.

(10) pages 13-21: Three different notations for the transition probabilities are used in the Appendix: $P(x,y)$ and $p_{x \to y}$ on page 13 and $P_{x,y}$ on page 21. The first variant is also used in Sections 2 and 3, so it would be coherent to stick to that.

(11) page 13, line 450: $D$ is not defined.

(12) page 14, lines 460 and 469: The order of integration is not correct.

(13) page 14, line 473: "Theroem"

(14) page 15, lines 516-522: Is Theorem 3 the informal version of Corollary 2?

(15) page 18, Alg. 5, lines 7 and 8: $\Sigma^\prime_i = \Sigma^\prime$?

(16) page 21, lines 632/633: One $\ket{x}$ too much on the right-hand side of the equation.

(17) page 21, lines 637-640: A bit more detail on the last steps of the implementation of the quantum walk operator would be helpful.
limitations: Yes, the authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Main Contributions:
1. The first study of Approximately convex and stochastic convex functions using Quantum Algorithms
2. The application of these algorithms and performance bounds to bandit algorithms resulting in a logarithmic regret

The authors use a more general problem of approximately- and stochastic- convex optimisation using Quantum algorithms to then derive specific results for the Bandit Algorithm Case.
strengths_and_weaknesses: Strenghts:
1. Clever use of stochastic optimisation in general leads to a direct application to Bandit algorithms yielding a logarithmic regret bound. 

Weaknesses:
1. Unclear if you are proposing the first Quantum algorithm that has the Logarithmic Quantum regret bound, if so then it is very big, if not (which is more likely) then a comparison against existing methods is missing.
2. The Theorems 2 & 3 suggest seemingly arbitrary probablity bounds 0.9 and 0.8 resp. this should have more explanation.
3. (ideally) Theorems 2 & 3 would have a delta (representing the probability) with which the result can be found (and it will then also feature in the formula) as opposed to fixed probabilites 0.9 and 0.8.

questions: Questions & Suggestions:
1. What does poly(e, 1/n) mean, as there are two arguments. [Line 32]
2. Zeroth-Order Bandit Algorithms / Oracles are a confusing terminology and a reference, footnote, or detailed explanation would be helpful.

limitations: Limitations:
1. The claim of logarithmic bounds is only true due to an associated probability of achieving the result, hence direct comparison is not possible. A discussion of this would be helpful.
2. How realistic is this algorithm in terms of Qubits required to run (given what problem dimension). Discussion of this would be interesting.

Societal Impact:
1. Everything seems to have been discussed.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies the quantum algorithm for minimizing an approximately convex function. It is faster than the classical algorithm by a factor  O(n^1.5). This is achieved by implementing a quantum version of the classical algorithm which is based on simulated annealing and the hit-and-run walk. It also gives rise to a quantum algorithm for zero-th order stochastic convex bandits with an exponential speedup in time horizon.
strengths_and_weaknesses: originality: the paper initiates the quantum version of minimizing approximately convex functions.

quality: technical depth is sufficient

clarity: not friendly to readers not in this area.

significance: pure theoretical contribution
questions: This paper focuses on zero-th order quantum optimization for the considered problem. I am curious about if there exists any result on first-order quantum optimization. 
limitations: I feel the presentation could be improved a lot so that it is more accessible to general readers. It would better if Eq. (4) can be explained more: how to understand the right-hand side which is a quantum state followed by another quantum state (there seem to be no such definitions in Section 2.1). Also,  $\xi$ is n-dimensional but $y$ is a scalar.
review_title: null

Meta-review: metareview: Interesting paper - a little bit on the weak side in terms of presentation especially given the community. The consensus is around a weak accept and I concur. 
confidence: Less certain
Decision: Accept