Summary
This paper proposes a non-standard approach to the problem of learning halfspaces, where instead of labelled samples, the learner only receives unlabelled ones as well as strong prior information about the unknown distribution. In particular, the marginal distribution is assumed to correspond to some affinely skewed product distribution, with identical components except from one which is truncated outside some interval. The unsupervised distribution learning problem corresponds to a supervised learning problem when the labels are determined by a halfspace in the direction of the truncation.
The main result shows that when the truncation region is wide enough but not too wide and either symmetric or bounded away from being symmetric, then the direction of truncation can be discovered efficiently from unlabelled samples. The algorithm exploits standard ideas from distribution learning (data normalization, PCA and sample re-weighing), but its proof involves careful application of appropriate tools.
Strengths
The paper proposes and studies an interesting connection between unsupervised and supervised learning. Moreover, I appreciated the technical work required to prove guarantees about the main algorithm, even though it is based on simple and clean algorithmic ideas.
Weaknesses
There are several concerns I have regarding the setup, the impact and the results. In particular:
1. While the model demonstrates an interesting connection between supervised and unsupervised learning, if we focus on either of these aspects, it seems less relevant. For supervised learning, the distributional assumptions are too strong (usually one either makes strong assumptions on the marginal distribution or assumes the existence of margin, but not both). For unsupervised learning, the component we want to discover is too specific (instead of a general property, like matching some Gaussian moments, it is assumed that the component is just a truncation of the distribution of the other components).
2. On the algorithmic level, the impact seems to be limited. Variants of the algorithm presented have largely appeared in the literature for similar problems.
3. The main result (Theorem 1) does not seem to be completely accurate. More specifically, there has been no account for the case where the truncation region $[a,b]$ has $|a+b|>0$ but $|a+b|\approx 0$ (e.g., $|a+b| = 2^{-d}$). While Lemma 4 accounts for the case when $|a+b|$ is large enough, Lemma 5 only accounts for the case $|a+b|=0$. It is not clear what happens in between. In Figure 5.2, it seems that Lemma 5 could be generalized to capture cases when $|a+b|$ is positive but bounded. However, this has not been proven.
Overall, the paper seems to have important unresolved technical issues and also it could highly benefit by relaxing the distributional assumptions. I would encourage the authors to continue working on the paper, but in its current form, it is below the acceptance threshold.
-- The authors fixed an important technical issue in their proof (item 3 above) and I have increased my score (from 3 to 5) to reflect this.
Questions
I would be interested to hear any comments that the authors have regarding the points (1,2 and 3) I made in the weaknesses section. Moreover, I have the following suggestions regarding the presentation.
1. The problem definition (page 2) needs to be clarified further to avoid confusion. In particular, it is not clear what is known and what is unknown. For example, does the learner know $q,a$ and/or $b$?
2. How does the paper [DK'22] compare to your results? On a more general note, I think it would be beneficial to present in section 1.2 some result on NGCA (e.g. [DK'22]) more concretely, as well as some result on supervised learning and emphasize the trade-offs when considering the problem proposed in this paper.
[DK'22]: Diakonikolas, Ilias, and Daniel Kane. "Non-gaussian component analysis via lattice basis reduction." Conference on Learning Theory. PMLR, 2022.
3. Some typos:
- Line 105: double "the".
- Line 106: "follows uses" $\to$ "uses".
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
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.