Large-Scale Quadratically Constrained Quadratic Program via Low-Discrepancy Sequences
We consider the problem of solving a large-scale Quadratically Constrained Quadratic Program. Such problems occur naturally in many scientific and web applications. Although there are efficient methods which tackle this problem, they are mostly not scalable. In this paper, we develop a method that transforms the quadratic constraint into a linear form by sampling a set of low-discrepancy points [16]. The transformed problem can then be solved by applying any state-of-the-art large-scale quadratic programming solvers. We show the convergence of our approximate solution to the true solution as well as some finite sample error bounds. Experimental results are also shown to prove scalability as well as improved quality of approximation in practice.
Contributions:
The paper proposes a sampling based method to approximate QCQPs. The method starts from a sampling of the hypercube, the mapping it to the sphere, and finally to the ellipsoid of interest. Unfortunately the authors don't provide enough evidence why this particular sampling is more efficient than simpler ones. How is the complexity dependence on the dimension? (Net seems to be exponential in dimension). The theorems seem to hide most dimensionality constants. My main question: How does the approach compare experimentally and theoretically to naive sampling? 
While the main advantage of the contribution is the scalability, the authors do unfortunately not in detail compare (theoretically and practically) the resulting method and its scalability to existing methods for QCQP.
The paper is considering convex QCQP only, and does not comment if this problem class is NP hard or not. For the list of applications following this statement, it should be mentioned if those are convex or not, that is if they fall into the scope of the paper or not. This is not the only part of this paper where it occurred to me that the writing lacked a certain amount of rigor and referenced wikipedia style content instead of rigorous definitions.
Experiments: No comparison to state-of-the-art second order cone solvers or commercial solvers (e.g. CPLEX and others) is included. Furthermore, as stated now, unfortunately the claimed comparison is not reproducible, as details on the SDP and RLT methods are not included. For example no stopping criteria and implementation details are included. No supplementary material is provided.
How was x^* computed in the experimental results? How about adding one real dataset as well from the applications mentioned at the beginning?
Riesz energy: "normalized surface measure" either formally define it in the paper, or precisely define it in the appendix, or at least provide a scientific reference for it (not wikipedia). The sentence "We omit details due to lack of space" probably takes as much space as to define it? (Current definition on the sphere is not related to the actual boundary of S).
Style: At several points in the paper you mention "For sake of compactness, we do not go deeper into this" and similar. This only makes sense if you at least more precisely state then why you discuss it, or at least make precise what elements you require for your results. In general, if such elements do add to the value of the paper, then they would be provided in an appendix, which the authors here did not.
line 105: missing 'the'
line 115: in base \eta: Definition makes no sense yet at this point because you didn't specify the roles of m and eta yet (only in the next sentence, for a special case).
line 149: space after 'approaches'. remove 'for sake of compactness'
== update after rebuttal ==
I thank the authors for partially clarifying the comparison to other sampling schemes, and on x^*.
However, I'm still disappointed by the answer "We are presently working on comparing with large scale commercial solvers such as CPLEX and ADMM based techniques for SDP in several different problems as a future applications paper.". This is not to be left for the future, this comparison to very standard competing methods would be essential to see the merits of the proposed algorithm now, and significantly weakens the current contribution.