Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: I am not familiar with the quantum algorithm literature, hence I cannot judge the novelty of the proposed algorithm. Basically, this is a quantum algorithm for computing the smallest negative eigenvalue (and the associated eigenvector) of square matrices. It is worth noting that the algorithm is built on top of the existing SVE model. The authors don't compare this method with any existing work in quantum singular value transformation and decomposition. A throughout discussion and comparison should be made in Section 1.1

Despite the title, I can't find a strong connection between the proposed algorithm and machine learning. Given a loss function f and the parameters x, the paper doesn't specify how to construct the quantum state in the step 2 of Algorithm 2. Is there a cheap way to construct the quantum state from (f, x)? If not, and if one has to compute the Hessian matrix H from (f, x), then the complexity of this pre-processing step will be on the order of O(d^2), which already makes the quantum efficiency meaningless. 

Escaping saddle point is usually an iterative process, because the curvature varies across from place to place. The paper focuses on an individual step of a single iteration (i.e. finding the negative curvature), but it doesn't mention how would the iterative process look like.

Finally, although the quantum complexity is poly-log in dimension d, it has a terrible dependence on the rank r and the Frobenius norm of the Hessian matrix. The potential issues of such dependencies should be discussed.




review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: This paper proposes a new quantum algorithm which can efficiently estimate the eigen vectors of a Hessian matrix with negative eigenvalue.

Decision

I would vote for a weak accept although this is somewhat an educated guess. Finding efficient ways to estimate eigen-vectors of the Hessian would have a dramatic impact on second-order optimization techniques (neglecting the practical implications of it being a quantum algorithm). Since the paper is submitted to a machine learning conference I believe more efforts should be done to make the paper accessible to researchers unfamiliar to quantum computing.

Comments

I appreciate the clarification of the notation at section 2.1, however many exotic notation for machine learning researchers are presented before this section without any reference to 2.1. The operation `\propto` (latex) is never explained. My understanding is that it is the update of a quantum state?

The section 2.2 should give a brief overview of why both techniques will be useful for the many parts of the contributed algorithms.

I could not find definition of T_H anywhere.
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: This paper proposes a quantum algorithm aiming to solve the eigenvalue decomposition for the Hessian matrix in second-order optimization. The main body of this paper is the quantum singular value decomposition algorithm from Kerenidis & Prakash, 2016. The authors propose some plug-in algorithms in the context of quantum computing. Moreover, this paper does not evaluate the proposed algorithm with any comparative experiments. Personally speaking, it is better to submit the work to the physics journals. 
review_title: Official Blind Review #2

Meta-review: There was some support for the ideas presented, but this paper was on the borderline, and ultimately not able to be accepted for publication at ICLR.

Concerns raised included level of novelty, and clarity of the exposition to an ML audience.
Decision: Reject