Isotropic Noise in Stochastic and Quantum Convex Optimization

Thank you for your feedback and questions on our paper.

To respond to the weaknesses you raised:

• "The improved query complexity results are obtained under stronger theoretical assumptions, such as isotropy and sub-exponential tails."

Though we do require these assumptions for our non-quantum results, we want to emphasize that in our main application to quantum stochastic convex optimization, the isotropic noise model is not an assumption. For quantum stochastic convex optimization, we only assume access to a quantum analog of a VSGO (Definition 6), whose stochastic noise is not guaranteed to be isotropic. In other words, the isotropic noise model is a technical tool which we use to achieve improved rates in a quantum noise model which has been studied previously in the literature.

• "The quantum speedup yields only a $d$-factor improvement, which is relatively modest..."

Regarding your comment that our quantum speedup is relatively modest and comes with an additional $d$ factor, we agree that this may limit the applicability of our algorithm on near-term quantum devices. Nevertheless, we would like to note that, as shown in prior work [1], achieving a quantum speedup in $\epsilon$ without incurring additional $d$-dependence is impossible in the worst case. We believe it is an interesting and natural open problem to explore whether our techniques can lead to more practical quantum algorithms given additional assumptions on the stochastic optimization problem.

[1]. Aaron Sidford and Chenyi Zhang. Quantum speedups for stochastic optimization. NeurIPS 2023

To respond to your questions:

• "The isotropic noise model seems to be a technical requirement in the proof. Except for sub-Gaussian noise, is there any practical model that exhibits this type of noise distribution?"

Just to emphasize the point we made above, for our main application to quantum stochastic convex optimization, the isotropic noise model is a technical tool as opposed to an assumption.

Regarding non-quantum applications beyond sub-Gaussian distributions, that is a great question. We believe isotropic noise constitutes a natural class of distributions where you can achieve improved rates. We leave it to future work to determine whether actual data distributions satisfy this condition, and whether there are additional classes of problems which can be solved more efficiently in this noise model.

• "Is it possible to implement a $(O(1), \delta)$ ISGO with $\mathrm{poly}(d)$ queries to VSGO (without using quantum)? If so, how would it be worse than Theorem 6?"

Regarding your question about implementing an $(O(1), \delta)$-ISGO with $\text{poly}(d)$ queries to a VSGO: Using a sub-Gaussian mean estimator (e.g., Theorem 8 in [2]), a $(O(1), \delta)$-ISGO can be implemented with $d$ queries (up to log factors) to a VSGO, whereas Theorem 6 is able to achieve $\sqrt{d}$ queries (up to log factors).

[2]. Lugosi and Mendelson. Mean Estimation and Regression Under Heavy-Tailed Distributions: A Survey. Foundations of Computational Mathematics.

• “Can you comment on other potential computational problems that would benefit from the quantum isotropifier?”

We think that is a great question. We are only using it inside cutting plane methods for now, but it is an interesting question if other problems, particularly those related to the applications of quantum multivariate mean estimation, might benefit or if it affects practical performance. However, we leave this for future work.

• “Does this technique heavily rely on the assumption of isotropic stochastic noise?”

Isotropic noise is not an assumption for the technique. Rather, it produces isotropic noise from a (potentially) non-isotropic distribution.

Thank you for your feedback and questions on our paper.

To respond to the weaknesses you raised:

• "The posed open problem is not completely resolved (other than sub-exponential noise)."

In regard to open problems, key quantitative contributions of this paper are tight rates for ISGOs and faster quantum stochastic convex optimization. Indeed, we do present what we believe is a natural further open problem suggested by this line or work, but we kindly suggest reviewers view this as an additional open problem or contribution, which is intended to encourage the community to further improve upon our results (rather than a failing of them). Also, note that resolving the open problem wouldn’t immediately yield faster quantum stochastic convex optimization algorithms than our approach, due to our quantum isotropifier. We hope that our work may facilitate further research on this fundamental open problem that we highlight.

• "It would be great if the authors can comment on the sensibility of the noise model. It feels that the noise model was introduced in order to justify the quantum isotropifier."

We want to emphasize that in our main application to quantum stochastic convex optimization, the isotropic noise model is not an assumption. For quantum stochastic convex optimization, we only assume access to a quantum analog of a VSGO (Definition 6), whose stochastic noise is not guaranteed to be isotropic. In other words, the isotropic noise model is a technical tool which we use to achieve improved rates in a quantum noise model which has been studied previously in the literature.

Regarding the sensibility/applicability of the noise model beyond quantum stochastic convex optimization, that is a great question. We identify what we believe is a natural class of distributions where you can achieve improved rates. We leave it to future work to determine whether actual data distributions satisfy this condition, and whether there are additional classes of problems which can be solved more efficiently in this noise model.

To respond to your questions:

• "Why is $R^2 \sigma_V^2 / \epsilon^2$ unimprovable when $d = 1$?"

$R^2 \sigma_V^2 / \epsilon^2$ can be shown to be unimprovable when $d = 1$ using the same lower bound construction which shows that $R^2 \sigma_B^2 / \epsilon^2$ is unimprovable when $d = 1$. Indeed, in that construction (e.g., Section 5 in [1]) it is the case that $\sigma_V^2 = \Theta(\sigma_B^2)$. We will include this point in our revision.

[1]. John Duchi. Introductory Lectures on Stochastic Optimization. IAS/Park City Mathematics Series, American Mathematical Society.

• "What is the query complexity of SGD under the same noise model (ISGO)."

Regarding the query complexity of SGD under an ISGO: When $\delta$ is sufficiently small as an inverse polynomial in the problem parameters (analogously to Theorem 1), then SGD achieves an $\tilde{O} ( R^2 (L^2 + \sigma_I^2) / \epsilon^2)$ rate with high probability. In this case, a $(\sigma_I, \delta)$-ISGO query implements a $O(L + \sigma_I)$-BSGO (Definition 2) query with high probability, in which case we can apply the classical SGD rate for BSGOs.

• "Can the authors comment on the sensibility of the isotropic noise model?"

See above.

• "Is it the same model as what is being referred to in [1]."

We do not believe it is the same model. I could not find a formal definition of “isotropic noise'' in that paper or the papers it cites under the “isotropic noise'' header on the first page. To my understanding, when that paper refers to isotropic noise they mean noise which must have a component in every direction (see "exhibits a certain amount of variance along all directions in $\mathbb{R}^d$" on page 1), namely a lower bound on how much noise the distribution has in each direction, whereas our definition corresponds to an upper bound on how much noise the distribution has in each direction.

• "It seems that there exists dimension independent quantum algorithms for similar problem setting. How does this work compare with [2] for example?"

Thank you for your question regarding the comparison between our work and that of B. Augustino et al. We would like to clarify that these works belong to two distinct lines of research on quantum algorithms for continuous optimization: The first line, which includes [2, 3] and the work by Augustino et al., focuses on algorithms that access a (possibly approximate) quantum value oracle. In this setting, the oracle’s output need not be unbiased but must have small errors. For instance, in Theorem 2.1 of Augustino et al., the required error is of the order $\mathrm{poly}(\epsilon)/\mathrm{poly}(d)$.

The second line, which includes [4] and our work, considers access to a quantum stochastic gradient oracle. In this setting, the oracle provides unbiased gradient estimates with variance that is independent of both $\epsilon$ and $d$. Notably, [4] proves that a dimension-independent quantum speedup is impossible in this setting.

We thank you for pointing out the relevant work by Augustino et al. and may include some discussion of this work in our final version.

[2]. Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Convex optimization using quantum oracles. Quantum 2020

[3]. Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu. Quantum algorithms and lower bounds for convex optimization. Quantum 2020

[4]. Aaron Sidford and Chenyi Zhang. Quantum speedups for stochastic optimization. NeurIPS 2023

Thank you for your feedback and questions on our paper.

To respond to the weaknesses you raised:

• "It would be helpful to state the assumption on the objective functions upfront, i.e., Lipschitz and convex."

Note that we state that $f$ is convex and $L$-Lipschitz in Lines 19 - 22. More broadly, the introduction was structured with the intent of making the assumptions clear. If you could identify places in the paper where you feel we missed a statement or an explanation, please let us know; we would be grateful and are eager to further improve the paper’s clarity.

• "It is not clear how the results for the Lipschitz gradient case is connected to the results in the framework in this paper."

Thank you for this question. We do mention prior dimension-independent work on the Lipschitz gradient case in Line 37 when explaining the prior work on SCO with a VSGO oracle. Additionally, our bounds can be extended immediately to the Lipschitz gradient case at the cost of only logarithmic factors since our bounds have logarithmic dependence on the Lipschitz constant of $f$. This follows because a function with a $G$-Lipschitz gradient which is minimized in a ball of radius $R$ is itself $O(GR)$-Lipschitz in the ball. We will mention this in our revision.

• “A significant limitation of this work is on the quantum formulation, where the authors assumed the quantum oracle essentially provides a pure-state outcome, specifically, the garbage state that is entangled to the gradient outcome $|g>$ is assumed to be known and used in the amplitude amplification part of the algorithm.”

Thank you for this question. We would like to clarify that the garbage state is not assumed to be known by our algorithm. This is because quantum amplitude amplification requires only the ability to apply the oracle and its inverse as a black box, without knowledge of the garbage state. Accordingly, our algorithm only needs to maintain coherence with the environment but does not require knowledge of its identity.

• “While this is a typical assumption in related works, it is technically incorrect to claim that this formulation is a generalization to the classical case and the proposed algorithm achieves a "quantum speedup", as in the classical case the garbage states are viewed as part of the environment of which the identity is unknown and is not accessible by the algorithm.”

Thank you for raising the question regarding our use of the term “quantum speedups.” We adopted this terminology in part because it is commonly used in the literature (e.g., [1, 2]), and also due to the widespread convention of referring to Grover’s algorithm as achieving a “quadratic speedup.” That said, we can see how this phrasing may lead to confusion, and will look into alternative expressions in the final version.

• "While the bounds under isotropic and sub-exponential noise are tight up to log factors, the main open problem of achieving optimal sample complexities for variance-bounded noise remains unresolved."

In regard to open problems, key quantitative contributions of this paper are tight rates for ISGOs and faster quantum stochastic convex optimization. Indeed, we do present what we believe is a natural further open problem suggested by this line of work, but we kindly suggest reviewers view this as an additional open problem or contribution, which is intended to encourage the community to further improve upon our results (rather than a failing of them). Also, note that resolving the open problem wouldn’t immediately yield faster quantum stochastic convex optimization algorithms than our approach, due to our quantum isotropifier. We hope that our work may facilitate further research on this fundamental open problem that we highlight.

To respond to your questions:

• We thank you for raising the question regarding our use of the term “generalization” for our quantum oracle. We use this term to convey that the quantum stochastic gradient oracle is strictly more powerful than its classical counterpart, since the latter can be obtained by measuring the quantum oracle. Given known query complexity lower bounds for algorithms using classical stochastic oracles, improved rates are only possible with access to strictly more powerful oracles. We acknowledge that the term “generalization” may cause confusion in this context, and will fix this in our final version.

• Thank you for your question regarding the implementation and motivation of the quantum oracle. We would like to clarify that, in the worst case, we do not see how to implement the quantum oracle efficiently using a classical oracle without incurring a loss in query complexity. We did not intend to suggest otherwise, and if any part of the paper leads to this confusion, we are happy to try to revise it for clarity.

• Regarding your question on the access to the identity for the circuit to the classical oracle, indeed, knowing the gradient circuit makes the query complexity of the problem trivial. However, it doesn’t necessarily make the problem computationally trivial. As discussed in [3, 4], even if the classical oracle’s internal circuit is known, computing the gradient exactly from this description may require exponential time in the circuit size (as far as we know). Therefore, it remains meaningful to study algorithms that access the oracle in a black-box manner, which is the motivation behind the transformation we described. If there are specific parts of the paper that would benefit from further clarification, we would be more than happy to expand on them in the final version.

• Regarding the motivation of the quantum oracle, we are not aware of any key motivation for considering this setting that was not already present in prior works. For this reason, we simply cited the prior work rather than repeat these motivations.

• Regarding your question on lower bounds in the quantum setting, we agree that this is a good question. We would like to note that a lower bound is established in prior work [2]. However, this lower bound does not match our algorithmic result, and it is unclear to us how to improve the existing construction. We may include this as an open question in the revised version.

[1]. Ashley Montanaro. Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 2015.

[2]. Aaron Sidford and Chenyi Zhang. Quantum speedups for stochastic optimization. NeurIPS 2023

[3]. Robin Kothari, and Ryan O’Donnell. Mean estimation when you have the source code; or, quantum Monte Carlo methods. SODA 2023.

[4]. Clément L. Canonne, Robin Kothari, and Ryan O'Donnell. Uniformity testing when you have the source code. 2024.

Thank you for your feedback on our paper and positive recognition of our contributions. We will correct the typos that you raised in our revised version.

“The major weakness lies in the motivation of the oracle: are there real-time applications of convex optimization that can provide the isotropic oracle without significant overhead?”

We want to emphasize that in our main application to quantum stochastic convex optimization, the isotropic noise model is not an assumption. For quantum stochastic convex optimization, we only assume access to a quantum analog of a VSGO oracle (Definition 6), whose stochastic noise is not guaranteed to be isotropic. In other words, the isotropic noise model is a technical tool which we use to achieve improved rates in a quantum noise model which has been studied previously in the literature.

Regarding non-quantum applications, that is a great question. We identify what we believe is a natural class of distributions where you can achieve improved rates. We leave it to future work to determine whether actual data distributions satisfy this condition, and whether there are additional classes of problems which can be solved more efficiently in this noise model.