Learning-Augmented Learning of Gaussian Mixture Models

In the pseudocode for Algorithm 1, do the authors mean at line 4 "for $i,j\in[|\mathcal{L}|]$"?

No, the code is correct as written because the second for loop iterates over all groups $a$ and $b$

Is the new list $\mathcal{L}$ made of a single representative for each group (to make then sense of Observation 3.5)?

Yes, that's correct.

In Lemma 3.8, what is $\gamma$? In Algorithm 3 it seems to be put equal to $\frac{1}{2}$ and never updated

Yes, $\gamma=\frac{1}{2}$

In the pseudocode for Algorithm 2, $\mathcal{P}$ never appears to be used after initialization except to be returned

$\mathcal{P}$ is the collection $\{\mathcal{P}_i\}$ of partitions $\mathcal{P}_i$.

The ratio behind the choice for $\Delta$ in line 3 of Algorithm 3 stems, from my understanding, from the proof of Lemma 3.8, and similarly the numerical prefactor appearing in Lemma 3.9: could the authors give an intuition behind them?

Yes, that's correct. The separation needs to be sufficiently high to be detectable.

Would this strategy be feasible if one is only interested in the correct labeling of the data points (and not in the reconstruction of the mixture)? How would this approach compare with the proposed one?

This is an interesting suggestion, but it seems likely an approach to robustly remove gross misclassifications would still be needed, since a few adversarial points could potentially be problematic.

I list below some comments and observations.

Thanks for the other comments and observations, they will greatly help the presentation of future versions of the manuscript!

It seems that the key component is derived from a previous result (Diakonikolas et al., 2020). The rest involves using the labels to ensure that the conditions in the previous result hold, allowing us to apply it. I am not sure if there are fundamentally new techniques introduced.

Perhaps there is a misunderstanding -- the only place we use (Diakonikolas et al., 2020) in the main algorithm is to identify the Gaussian underlying each cluster after the partitioning is complete. This is a standard result that can be cited from other references, since we only have a single cluster. In fact, we note in Appendix B that running the result of (Diakonikolas et al., 2020) on the input would result in prohibitive runtime and sample complexity, exponential in $k$.

The problem is highly fabricated. There is absolutely no motivation provided to study this problem - in which use case can such a scenario occur and why should anybody care about a mixture of gaussian study where the number of components is not a constant? It would be great if the authors can provide some motivating examples/ experiments on real world datasets where the number of components is large enough to actually see a difference.

There is a large body of work on learning Gaussian mixture models in a semi-supervised setting, such as:

• Bingchen Zhao, Xin Wen, Kai Han: Learning Semi-supervised Gaussian Mixture Models for Generalized Category Discovery. ICCV 2023: 16577-16587
• Samet Oymak, Talha Cihad Gulcu: A Theoretical Characterization of Semi-supervised Learning with Self-training for Gaussian Mixture Models. AISTATS 2021: 3601-3609
• Xiaojin Zhu and Andrew B Goldberg. Introduction to semi-supervised learning. Springer Nature, 2022.
• Chen Dan, Liu Leqi, Bryon Aragam, Pradeep Ravikumar, Eric P. Xing: The Sample Complexity of Semi-Supervised Learning with Nonparametric Mixture Models. NeurIPS 2018: 9344-9354
• Xiyu Yu, Tongliang Liu, Mingming Gong, Kayhan Batmanghelich, Dacheng Tao: An Efficient and Provable Approach for Mixture Proportion Estimation Using Linear Independence Assumption. CVPR 2018: 4480-4489
• Nara M Portela, George DC Cavalcanti, and Tsang Ing Ren. Semi-supervised clustering for mr brain image segmentation. Expert Systems with Applications, 41 (4):1492–1497, 2014

Can the authors explain how kmeans++ or other heuristics could be used to generate the list oracle with confidence signals, as this connection is not immediately clear?

We use heuristics to create a (likely erroneous) predictor for our algorithms.

From the example provided in lines 111-123, it seems a robust algorithm for learning mixture of Gaussians will be sufficient - why is this not the case for the general problem?

Non-robust algorithms for learning mixtures of Gaussians already provably require sample complexity and thus exponential in $k$. This work builds upon recent work in the standard setting to achieve robust algorithms for learning mixtures of Gaussians in the semi-supervised setting.

is there a reference which says that large TV distance always implies large parameter distance

This is Lemma 3.2 in the manuscript, which is also Proposition A.1 in Bakshi et al. (2020) and Fact 3.24 in Ivkov & Kothari (2022).

How would the results change if the number of classes in not known before-hand?

A constant-factor upper bound on the number of classes suffices.

In Algorithm 3, why is the list-decoding parameter represented as $\frac{1}{\beta}$?

Under our assumptions, the number of labels in the list translates to a fraction of uncorrupted samples in the list-decoding setting.

What is the explicit dependence of the sample-complexity on $\beta,\alpha$?

We assume $\alpha$ and $\beta$ are constants, but their dependencies are not great, with previous references having an exponential dependencies.