Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper is motivated by the problem of learning n-qubit quantum states in different learning models, such as differentially private PAC learning and online learning with imprecise feedback, and proves information-theoretic equivalences and implications between them. One of the main results of the paper is proving that pure DP PAC learning of quantum states implies learning of quantum states in the online learning model with imprecise feedback.

The line of implications goes as follows: a bound on the sample complexity of Pure DP PAC learning implies a bound on the probabilistic representation dimension of the class, which implies a bound on the one-way communication complexity of quantum learning, which bounds the *sequential-fat-shattering* dimension of the class (a generalization of the Littlestone dimension from boolean to real-valued function classes). 
If the sequential-fat-shattering dimension is bounded then there exists an online learning algorithm which is robust to imprecise feedback (as must be the case for the training samples-measurements of quantum states), called Robust-SOA. 

The authors then also prove that this online learner implies the existence of a learning algorithm that satisfies a type of stability, called quantum stability, which says that there exists a state such that the algorithm’s output is within a ball of this state with high probability.

Among others, a significant implication included in the results is a new bound on the complexity of shadow tomography which includes the sequential-fat-shattering dimension (sfat) instead of the number of qubits n (and sfat<=n for any class but there exist classes with sfat significantly smaller than n).

main_review: The reasoning behind the “pure DP PAC learning->online learning of quantum states->stability “ result follows a recent line of papers which prove that for the case of classification (Boolean function classes), DP PAC learning implies online learning which implies a type of stability, called global stability, which in turn, implies DP PAC learning, with the main quantity in these implications being the Littlestone dimension of the class. However, learning of quantum states seems to come with additional difficulties, since the classes are real-valued and the measurements are noisy (which leads to the online learning with imprecise feedback model and to the proposed “quantum stability” being an approximate version of global stability). Getting over these challenges seems to require many new (intermediate) results and connections, which could also be of independent interest, especially given that the paper considers many different types of learning models and combinatorial quantities, not necessarily tied to quantum learning.

=============
I have read the authors' responses and still think that overall this paper's results merit acceptance. I also found the paper a bit hard to read in places but cannot come up with concrete suggestions, since the issue seems to be the breadth of results and the effort to compile them together is clear. I do second adding clarifications to the reduction as per Reviewer C1db's comments. Finally, (again, not having changed my opinion on the paper) I think it is beneficial to refer to the recent paper "Differentially Private Nonparametric Regression Under a Growth Condition" by Noah Golowich which appeared at COLT 2021 : it studies private learnability in the real-valued domain and gives a relaxed sufficient condition, compared to Jung et al, which includes the eta-sequential-fat-shattering dimension.
limitations_and_societal_impact: Sufficiently discussed.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper derives relationships between several models of approximately learning quantum states. Specifically, it extends results in learning boolean functions to learning real-valued functions with imprecise feedback, and shows that the complexity of learning in Pure DP PAC upper bounds quantum CC and the sequential fat-shattering dimension. The Sfat dimension in turn implies online learnability. A conceptual contribution of this paper is quantum stability, and the authors show that online learnability implies the existence of stable learners, but contrary to results on boolean functions, quantum stability does not imply Approximate DP PAC. The authors also propose the RSOA algorithm, which is central to proving the results. 
main_review: The paper makes solid technical contributions towards addressing the motivating question of relating different learning models. The learning models are designed with learning quantum states in mind and extend previous settings on exact feedback to imprecise feedback. The results answer an important question and make progress in understanding the complexity of learning quantum states. Overall the paper is well-written, and the following minor points might improve the clarity of the paper: 1) can the authors comment on the computational complexity of the RSOA algorithm? 2) does the improved bound on sfat() use techniques in the previous sections of the paper? It’s not clear to me how this is an application of the previous results, but it is a well-motivated task. 

Post rebuttal: I have read the authors' response and I intend to keep my score. I agree with reviewer C1db's point on clarifying the reduction, but overall I think this paper is above the acceptance threshold.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper develop a series of relationship between quantum learning model. 
(1) Pure DP PAC learnability implies finite sequential fat shattering dimension.
(2) Finite sequential fat shattering dimension implies online learnability
(3) Online learnability implies certain notion of quantum stability.
(4) quantum stability may not implies approximate PAC learnability.

The work (especially point 3,4 above) is inspired by the recent breakthrough of Bun, Livni and Moran (Journal of the ACM'21) on proving online learnability implies private PAC learnability, extends the result to real-valued setting.


main_review: Strength: It is certainly exciting to see the relationship between quantum learning class, and as far as I know, this is the first paper that intends to show such equivalence between quantum learning class (although the classical counterpart has been well-studied) The proof is also non-trivial.

Drawback: From my view, the major unsatisfactory of this paper is that the implication (from online learnability) stops at the level of quantum stability, but the major breakthrough of Bun, Livni and Moran (Journal of the ACM'21) actually takes a step further and showing (classical) stability implies private PAC learning. Though the later step is not the technical core of BLM'21 and this paper proves such implications do not hold in quantum regime, it weakens the conceptual contribution of this paper, as it is not clear afterwards why quantum stability is interesting.

Summary: Overall, I think this is a nice paper, but I hope the author could response to my comment above (drawback), and it might be good to put this into discussion or open questions.


I have read the author's response and my evaluation stays the same.
limitations_and_societal_impact: looks good
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents a number of connections between private learning, online learning and stability in the quantum and real-valued settings, generalizing recent work of Bun, Livni and Moran '20 in the Boolean-valued setting. The main results are:
 - An algorithm (termed RSOA) that accomplishes online learning of real-valued functions (requiring feedback only within an $\epsilon$ precision) with a mistake bound given by the sequential fat-shattering (sfat) dimension of the class
 - A notion of real-valued and quantum stability (generalizing Bun et al's "global stability"), along with a proof that online learnability implies this kind of stability
 - A no-go result for (one approach for) converting stability to approximate PAC learnability
 - An improved shadow tomography result with sample complexity in terms of the sfat dimension
 - Bounds on the sfat dimension of quantum state classes in terms of Holevo information

Many of the key notions and proofs are natural generalizations of the Boolean and (exact) real-valued analogs as studied e.g. in Bun et al '20 and Rakhlin et al '10. The concrete applications to quantum state learning are novel and interesting, and address some questions raised in earlier works such as Aaronson et al '18.
main_review: The motivation for this work is primarily to obtain an improved understanding of online learning and shadow tomography of quantum states, as well as to see what the consequences of Bun et al's breakthrough are for the quantum setting. Along the way, one is naturally forced to first consider learning of real-valued functions, and much of the paper deals with generalizing existing results to the real-valued setting with "imprecise feedback". This requires technical care in some places, but to a large extent seems to be reasonably straightforward. These generalizations are arguably not too surprising, but it is still good to have them established.

The authors define a kind of private analog of PAC learning quantum states that is a natural theoretical extension of classical private learning, but privacy for quantum states does not seem particularly well-motivated in its own right, or at any rate could use some more discussion and motivation (other than that it implies other things such as one-way communication and online learning, which is certainly nice).

The RSOA algorithm and its mistake bound in terms of the sfat dimension seems to follow similar ideas to Rakhlin et al's FAT-SOA and indeed Littlestone's original SOA. The proof that online learning implies stability roughly follows Bun et al's elegant approach, except with some definite extra care to handle the real-valued setting properly. The characterization of one-way communication in terms of sfat dimension seems quite interesting, although I do not have too much knowledge of this area. The applications to quantum state learning, especially shadow tomography and online learning, are definitely interesting and make concrete progress in directions suggested by Aaronson et al. The no-go result for online learning implying (approximate) private learning is a little unfortunate, as this was perhaps the main point of Bun et al 20 (although see my question under Limitations below).

The writing is mostly reasonable but not always fully clear, although I do appreciate that the authors have a tricky job on their hands with the scope of this paper and the space constraints. There is some looseness with technical language in a few places. For instance, the definition of stability says "$A$ is stable with respect to distribution $D$ if, given a sample $S \sim D^T$, there exists a state $\sigma$ such that ..." -- but this makes it sound as though $\sigma$ depends on $S$ when in fact it only depends on $D$. That is, it should be something like "$A$ is stable wrt $D$ if there exists $\sigma$ such that whp over sample $S$ ...". (I had to read the original definition in Bun et al to clarify this for myself.) Also, it is a bit confusing that $\mathcal{M}$ is used sometimes to denote all 2-outcome measurements and sometimes just an orthogonal basis; it would be nice to use different letters just for clarity.

Overall, there are many results in this paper, and many of them answer natural questions. Some of them are unsurprising and not necessarily highly original, but have value regardless. With everything added up, this paper definitely makes significant contributions to the area. I did not verify every proof but did try to look over the main ones; I also do not claim familiarity with all of the areas touched upon.

UPDATE: Following discussion with the authors,  I understand the reduction better now but definitely still think it calls for more careful exposition. Overall I continue to think this is a good paper and merits acceptance.
limitations_and_societal_impact: I am not aware of any potential negative societal impact of this work, which is primarily theoretical.

I am a bit confused about the no-go theorem between quantum/approximate stability and approximate DP PAC learnability. The claim is that the approach of BLM20 cannot work (in a domain size-independent way) because it amounts to "query release for function balls" (Problem C.7), which is sufficiently general that clique identification (Problem C.8) (shown to be hard in Claim C.9) can be reduced to it. But this reduction seems to obscure the fact that the type of access to the input seems quite different between the two problems. In clique identification, the algorithm is presumably only told that a size-$n$ clique $D$ _exists_ and must find it using access only to the relation graph, whereas in the instance of "query release for function balls" naturally generated by the BLM20 approach, the set of functions $\\{ f_i \\}_{i \in [n]}$ is very much at hand. If this were the clique (and note that the reduction has $\eta = 1$, so all the functions are in the clique), then one could just output any one of these functions (uniformly at random to ensure privacy, I would think) and one has found the clique trivially. Put differently, "query release for function balls" seems trivial in the $\eta = 1$ regime generated by the reduction; the reduction would only seem to make sense if the query release algorithm could not see the functions as part of the input. I may be misunderstanding something, and would appreciate it if the authors could clarify exactly what is happening. (Incidentally, it would be good to be more careful about the use of the word "given" in Claim C.8 so as to distinguish the assumptions made in the problem versus the input the algorithm is literally given. Similarly with the term "special case": a more explicit reduction would be helpful.)

At a higher level, probably my main (subjective) quibble with the paper is that it feels a little unfocused and is perhaps attempting too many different things. It feels a little hard to take away a set of clean insights, and I do think that despite the collection of nice results this lack of focus is a limitation. I wonder if the paper would have been well served by being split into two roughly-standalone parts, one for the real-valued generalizations and another for the quantum applications. It is likely difficult to make any such changes for this conference, but it could be something to keep in mind when making edits.
review_title: null

Meta-review: Bun, Livni and Moran recently proved that finite littlestone dimension implies private (approximate) PAC learning of a Boolean concept class. This paper generalizes it to 1) learning real valued functions instead of Boolean valued functions and 2) to learning quantum states. In the process, the paper discovers several interesting relationships between different models of learning and points out an interesting "no-go" theorem for relating a (natural notion of ) quantum stability to online learnability. 

The paper makes fundamental connections between learning models: both positive (by translating algorithmic results) and negative (by exhibiting counter-examples for what might be natural conjectured relationships). The reviewers had a high opinion of the paper and authors' response and the ensuing discussion clarified what makes the no-go theorem between quantum stability and private learning non-trivial.   We recommend acceptance.  
Decision: Accept (Spotlight)