CS4ML: A general framework for active learning with arbitrary data based on Christoffel functions

Summary

This paper studies an extremely general notion of active learning in the $\ell_2$ norm. Suppose we are able to actively observe data in many different modalities. "Active Learning" means we can choose where we observe data in a domain, and "different modalities" means there are fundamentally different ways to observe the data. For example, an MRI machine can have many different coils in it, and for each coil we can measure data at a user-specified frequency. The fact that there are different coils with different physical properties corresponds to having "different modalities". The fact that we can choose which frequencies to measure data at corresponds to "active learning". The paper studies an extremely general formalization of active learning in the $\ell_2$ norm with different modalities in active learning. Specifically, it suggests computing a "Generalized Christoffel Function" (i.e. leverage score function) for each modality, and to sample from each modality at random places, chosen with probability proportional to the generalized Christoffel function. The paper allows for an exceptionally general notion of "sampling", where a sample could entail something classical in numerical linear algebra, like observing a row from a matrix. It can also mean something broader, like observing the gradient of a function. Also, while the error in each modality is measured with respect to the $\ell_2$ norm, it is the weighted $\ell_2$ norm with respect to a given measure $\rho$ for each modality. So, the user can choose to have (e.g.) a uniform error metric on a small interval, or to instead have a Gaussian-weighted error measure on the real line. Lastly, the framework also has enough flexibility to give guarantees in some nonlinear spaces, with the main example being the union-of-subspaces. Theoretical guarantees on sample complexity are given, roughly matching the rates that would appear in the special case of leverage score sampling for matrices. Further, many experiments and concrete instantiations of the general framework are presented. Applications vary from approximating function with multivariate polynomials, to optimizing MRI reconstructions, to solving PDEs with physically informed neural nets.

Strengths

The paper is also 40 pages of really intense serious research. The appendix is chalk full of interesting special case studies, demonstrating the flexibility of their theory and the practical algorithms it suggests. The paper is so big and full of ideas that the NeurIPS peer review system, where I don't have enough time to read it cover-to-cover, really does this paper a disservice. I'd love to have 2 months to focus on this paper and understand the ins-and-outs of every case study and theorem. However, I don't have that time, so I'll presume the correctness of everything in the appendix and strongly recommend publishing this paper. The paper is exceptionally general, doing a great job of generalizing much of the recent research on leverage score sampling beyond matrices. Lots of existing work has slowly generalized one or two ideas from leverage score sampling to Hilbert spaces or non-linearity or whatever else fits that work's setting. This paper really goes the extra mile and writes out a ridiculously general setting that covers: - Fitting a polynomial to a function, where we can observe both the function and it's gradient - Fitting a polynomial to a function, where we can choose if we want to observe the function or it's gradient at each query (in case one is more expensive than the other, we can consider them separate modalities with separate sample complexities). - Iteratively refined approximations to solving a PDE - Reconstructing MRI data from observations at carefully chosen frequencies The general framework is phrased in terms of normed spaces, Hilbert spaces, measurable functions, and other abstract math that really gives the user freedom to do what the want. The theorems also apply to this extremely general framework, so the user immediately has Christoffel sampling guarantees with a likely near-optimal sample complexity out-of-the-box. I think this paper is original in it's powerful results in extreme generality, and is general in it's applications. The paper's results are high quality sample complexity guarantees. The paper is broadly well written (but this is a bit of a weaker point). The paper should be significant in its expressive power owing to its applicability to many domains. I strongly recommend publishing it.

Weaknesses

The paper does suffer a bit on the clarity front. I'm familiar with leverage score sampling (and even some infinite-dimensional generalizations thereof), so I'd think that a generalized Christoffel function framework would be easy enough to understand. This was not the case though, and the extremely general framework was daunting an unapproachable to read about. There's even an appendix subsection devoted to relating the extremely general framework back to the leverage score form I'm comfortable with. However, this description isn't super clear and even has (as far as I can tell) several minor errors which really harm legibility. The general framework (section 2.1) is just a list of math definitions stated without any running example of what each mathematical object is. It's very unintuitive what the difference between a "measurement domain" and a "measurement space" are [Lines 85-87]. I'd strongly recommend the authors decide on a running example to present alongside all of the math definitions, which would make such definitions more intuitively distinct and clear. The experiment and case study examples (section 3) are also pretty hard to approach. Section 3 consistently summarizes ideas at an extremely high level, and pushes the rigorous instantiations of the general framework to the appendix. While this makes sense from a page-limit perspective, it does harm the clarity and reading experience. Unfortunately, under the constraints of the NeurIPS format, I'm not sure a better option is available. Perhaps the authors can avoid this extreme appendicizing in the arXiv version of their paper? Even when reading the appendices in good detail, there's bits and pieces that I don't follow (especially in the MRI example). Everything I understood was clearly correct, but sometimes the technical domain-specific language gets a bit overwhelming making the examples hard to follow. This clarity point is not a game-breaking issue, but another pass at making the technical material more approachable would benefit the paper, especially when it's targeting such a broad audience of both theoretical and empirical data scientists. _As a side note, it's curious to note one particular limitation of the framework -- it cannot explicitly handle ridge regression and ridge leverage scores, which is essential for some prior work on infinite dimensional leverage score sampling, like paper [12] in the references. I don't see any reason why CS4ML couldn't handle ridge regression / ridge leverage scores though._

Questions

First, I have some moderately technical qualms with the paper: 1. In Figure 1, if I understand Appendix B.6 correctly, is it correct that MCS (monte carlo sampling / non-christoffel sampling) is performing worse with more samples because of numerical instability / poor conditioning? Or, like [Line 194] says, is it because the sample complexity of MCS sampling is so bad that the error.... _gets worse_ as the sample complexity grows? 1. The Appendix doesn't seem to have a fully accurate and consistent instantiation of leverage scores into the CS4ML framework. Specifically, $\mathbb{U} = \mathbb{C}$ on [Line 672] seems at odds with $\mathbb{U} \subseteq \mathbb{X}$ when $\mathbb{X} = L\_\rho^2(D)$. I'm pretty sure that $\mathbb{U} = \text{span}(A)$ in leverage score sampling? Also, it feels pretty inconsistent to describe $\mathbb{V}$ as a subset of $\mathbb{R}^N$ but to describe $\mathbb{X}$ as a weighted $L_2$ function space on $[n]$. Understanding that much is already non-obvious from the notation, but would be much clearer if you just wrote $\mathbb{X}=(\mathbb{R}^N, \|\|\cdot\|\|\_{\mathbb{X}})$ where $\|\|\vec v\|\|\_\mathbb{X}^2 = \frac1N \|\|\vec v\|\|_2^2$. Also, there's no reason (afaik) for $\mathbb{Y}$ to be complex instead of real. Further, the sampling function should more explicitly be about looking up an item from a vector, something like $L(y)(\vec u) = \sqrt{p(y)}u(y) = \frac{1}{\sqrt N} [u]\_{y}$. Lastly, from my algebra, I found that $\alpha=\beta=\frac1N$ in equation (2.4) for the leverage score setting. Did I make an error, or is there an adjustment to the instantiation that can instead make $\alpha=\beta=1$? --- After that, I've got smaller qualms / typos / recommended edits: 1. [Line 92] The choice to make $(D_c,\mathcal{D}_c)$ makes for two symbols which look identical at a first (and second) glance. I'd change at least one of these symbols so it's clear that the first and second items in the pair are different. 1. [Line 116] Add parenthesis around 2.1 1. [Line 142] Remove $K=$ 1. [Line 156] Why isn't there rescaling by $\sqrt{p(y)}$ here, like there was in the leverage score appendix's definition of $L$? 1. [Figure 1] Explain the confidence intervals in the caption 1. [Line 168] The placement of "See Section 4.3" is not great, since Section 4.3 is about translating an "in-probability bound" into an "expectation bound". I'd move "See Section 4.3" one sentence earlier. 1. [Line 226] Redefine PINN here. I know it's defined in the abstract, but I'd do it again here. 1. [Figure 3] Add titles to the plots 1. [Lines 230-239] I completely failed to understand what this paragraph is trying to say.... I just don't understand the problem or how it's being solved. 1. [Section 4] Swap $\varepsilon$ and $\delta$. I'd **very heavily** recommend this. The choice of $\delta$ to mean failure probability and $\varepsilon$ to mean accuracy is extremely standard. I would not mess with this; it's very confusing to read. 1. [Line 269] Interpret this big messy norm $\|\|\|\cdot\|\|\|$ somewhere. It looks scary, but I don't think it really should be that scary? 1. [Line 269] Missing $c$ subscript on $\nu$. 1. [Equation 4.1] Explore this sampling complexity. What is it really saying, comparing our sampling distribution to the Christoffel function? Can we use it to get a sorta "coherence assumption" for uniform sampling / MCS? This should be somewhat intuitive, but it really stands to be formally explored a bit more in the writing. 1. [Lines 271-272] Why is it "particularly relevant"? Why's it hard to understand the Christoffel function of the cover but easy to understand the Christoffel function of $\mathbb{U}$. I sorta intuitively believe it's true, but you should justify it. 1. [Line 311] Consider calling $\mathcal{T}_\theta$ a "shrinking operator" maybe? or a "regularization operator" or something? It's not very truncation-like imo, but it's really a small preference. This is a very mild/soft recommendation. 1. [Lines 316-318] Please formalize this added-penalty approach. It's the generalization of ridge regression, which feels very worth exploring.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

N/A

Summary

This paper proposes a general framework for active learning. It claims that the proposed method can help achieve near-optimal sample complexity. In additional to the theoretical results, this paper also present 3 use cases, showing favorable results for the proposed method.

Strengths

Important topic with claimed good results.

Weaknesses

1. Poor presentation: Very heavy theoretical setup buried the connection to solving any real active learning problem. No high-level description of the algorithm and its advantages over the existing active learning algorithms. No insights are provided based on the theoretical derivation. 2. Poor experiment comparison: The proposed method was only compared with random sampling. There's no comparison with any existing active learning method.

Questions

1. line 19, p. 1: In ML literature, features are represented by $x_i$ instead of $y_i$ while the latter denotes the label, which is $f(y_i)$ in your case. 2. line 38, p. 2: In your example of computational imaging, is one image an example or one pixel an example? Both cases can occur in real applications. 3. line 60, p. 2: Do you mean the label function $f$ is in a Hilbert space? For any function with a set of real-valued parameters (e.g., a neural network), if it's represented by a vector of its real-valued parameters, is such a function in a Hilbert space? 4. line 61, p. 2: What does "data" in "data arises" mean? Examples of features and label pair? 5. line 179, p. 5: You claim "there are many settings where one can acquire both function values and values of its gradient." Can you give some real examples of such settings?

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

1 poor

Presentation

1 poor

Contribution

1 poor

Limitations

n/a

Summary

The paper proposes a framework for active learning (here meaning that the user controls the sampling strategy according to which the locations of the measurements are made) designed to handle various cases of regression (vector-valued, multimodal, and more). To do so, it introduces the concept of generalized Christoffel functions, that will drive the choice of sampling strategies. A statistical analysis of the risk associated to the empirical risk minimizer associated to the square loss is conducted, showing that a log-linear number of observations (with respect to quantities related to the geometry of the hypothesis space) allows for efficient training using the Christoffel sampling strategy. Numerical experiments on three different problems (all cast inside the cs4ml framework) complement the approach, showing improvements over the naive Monte-Carlo sampling.

Strengths

- The proposed approach is novel and encompasses many valuable problems to the machine learning community. - Mathematical details are sound. - Experiments show clear improvements. - The appendix contains a lot of remarks, additional experiments, that further develop the framework. - I share the author's enthusiasm regarding the potential of the framework, which is far from explored.

Weaknesses

- It sometimes feels that the paper is overly complicated for the sake of generality, without benefits (see questions). - While fairly general, the framework assumes that the user has access to the data generation strategy (not the targets, but the inputs) which is often not the case in practice. - Overall, the paper is very dense and notation heavy. It is impossible to read it without a constant back and forth to the (31 pages long) appendix, which makes the reviewer wonder why the 9 pages limit exists for this conference. In my opinion, it would be beneficial to have a longer (i.e. journal) version of the paper, as the supplementary contains many interesting remarks that help a lot to the understanding of the ideas.

Questions

I found the notation to be quite heavy and not intuitive at all. I suggest to change the name convention adopted here - while all notation choices are arbitrary, they need to be driven by simplicity and logic. In particular: - I suggest adopting $x_{ic}$ for the measurement locations, to be conform to the classical $y = f(x) + \epsilon$ regression statistical model. Anything evoking something we usually put inside a function call or put measures on is ok ($\theta_{ic}$ ?). - It feels weird not to have the random variable $Y_c$ living in the space $\mathbb{Y}$. Measurements could be $y_{ic}$ instead of $b_{ic}$. - To lower the number of different letters, the true function associated to the generating process could be $f^\star$, and the candidates could be $f$ (instead of $u$), keeping the estimate $\hat{f}$. - In the regression literature, hypothesis spaces are usually referred to as $H$ or $F$. If the measurements locations are $x$, the name of the object space has to change as well. - In definition 2.4, you introduce yet another variable name $\mathbb{V}$ that could just be the variable name of the hypothesis space, to improve clarity. Other questions/comments: - Where do you use non-boundedness of the measurement operators ? Could you not use the standard notation that elements of $\mathcal{L}(\mathbb{X}, \mathbb{Y}_c)$ are bounded linear operators ? Usually unbounded operators are not defined on the whole space $\mathbb{X}$ but only on their domain. - Could you comment on the need to parameterize the measures using two other measures ? $\mathrm{d}\mu_c(y) = \nu_c(y) \mathrm{d}\rho_cc(y)$ ? In the end, we first choose $\rho$ then take $\nu$ according to the CS strategy, so what is the influence different choices of $(\rho, \nu)$ yielding the same $\mu$ ? - Empirical nondegeneracy as presented in Eq. 2.5 is a void concept, unless $\alpha' \approx \alpha$ and $\beta' \approx \beta$ are made precise. - In Theorem 2.5, the symbol you use for the estimator is not defined until way too long after. - The notion of optimal sample complexity is not well explained enough and I struggle to see exactly with respect to what it is optimal. How can it be optimal given the crude estimate for the sum of Christoffel functions ? - Section 3.1: Have you studied the impact of the choice of $\rho$ on numerical performances ? What if $\rho$ were a laplace measure ? How do you choose $f$ in the experiments ? Also, why not write $(y_i, f(y_i), \nabla f (y_i))$ ? This avoids the supercharge of the subscript notation in line 752. - Proposition 4.3, 4.4 could be renamed corollaries or examples. Typos: - Line 61: vector-valued instead of vector space valued - In assumption 2.2, the mappings $L_c$ are from $D_c$ to $\mathbb{Y}_c$. (also in definition 2.4, check the whole text) - In Eq. (2.2) and (2.3) it should be $\forall u \in \mathbb{U}$. - "Hence, the sampling operators and measures preserve the X-norm in expectation" is very vague. - Appendix B1: line 759: no need for the complex conjugate. Why do you need to work in C after having defined your function as R-valued ? Line 763 rho is the same measure for all indexes k.

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Most limitations are discussed in the paper. I would also like to mention that the cs4ml framework is not suited to all regression problems, but only to those where one controls the sampling strategy. Alas, in practice you seldom know $\rho$, because the data distribution is often unknown. (Correct me if I'm wrong)

Summary

The authors introduce an active learning framework for regression problems based on the concept of generalized Christoffel functions. The proposed approach is applicable to a broad range scenarios and it is evaluated on several scientific computing tasks.

Strengths

The manuscript present a comprehensive explanation over the main ideas behind the proposed CS4ML framework. The main motivation is relevant (active learning for diverse data scenarios) and the authors point promising directions for further investigations. The work is well organized, which is especially important for theory focused contributions. I also praise the detailed provided supplementary material.

Weaknesses

The experimental section, although tackling diverse tasks, unfortunately compares the proposal only to an inactive learning strategy (Monte Carlo sampling), which diminishes the relative impact of the introduced method. I appreciate this point being highlighted as a limitation by the authors, but it does leave the reader wanting a bit more.

Questions

Although the manuscript lists 118 references, I think it lacks a more thorough in-text discussion with other available active learning strategies. Which literature gaps are addressed? Which scenarios are not entirely covered by standard methods? As a final minor observation, the left plot in Fig. 2 present some difficult to distinct line patterns which could be improved.

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.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The manuscript states sufficiently its limitations.

Acknowledging the rebuttal

I thank the authors for their detailed answer. I have no doubt that the paper's quality will be greatly improved once the proposed changes will be implemented, and I have raised my score accordingly.

Thanks for the response!

Apologies for the delay in my response. This was a delightful response from the authors, and I remain very very inclined to accept this paper. I look forward to reading this again, with updated notations and intuitions. As an additional side note, it may be interesting to see if the infinite-dimensional work of [[Shustin Avron]](https://arxiv.org/pdf/2104.05687.pdf) on leverage scores for general quasimatrices can be formalized as a special case of your results (when not regularizing so that $\lambda = 0$). No pressure to actually include it, but might be cool to look at, and also might provide proof strategies for ridge regression that work even if [12] doesn't provided anything immediately useful.