Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors of this paper present a semisupervised adaptation of the linear least squares-SVM. This formulation trivially contains the LS-SVM and linear spectral clustering as special cases. The bulk of the paper and perhaps its most interesting contribution is its theoretical analysis of the method which utilizes random matrix theory to analyze the asymptotic behavior of the estimator and gives a way to choose hyperparameters. The efficacy of the classifier is experimentally verified against some simple baselines.
strength_and_weaknesses: Strengths:
* Formulation is new as far as I know.
* Asymptotic analysis is nice.

Weaknesses:
* The theory isn't very well-explained and there are small mistakes or at least unclear statements in the math.
* The contributions aren't very significant: the experimental results don't include any strong competitors, the theory is a fairly straightforward application of existing results, and the classifier formulation isn't particularly novel.
clarity,_quality,_novelty_and_reproducibility: Clarity: Okay. The mathematics in this paper are too sloppy for a paper whose main contribution is theoretical. A work like this should have a very polished and essentially self-contained theory. Some examples include:

1. (1) Despite the authors' claims, this is not convex (claim is made above (2)). This is seen easily by simply setting alpha_u to be large, in which case the risk is concave.
2. Theorem 3 in appendix. What is an "observable diameter"? This term appears nowhere else in the work and is quite mysterious.
3. Theorem 3 in appendix. What precisely is a "concentrated random vector"?
4. Theorem 3 in appendix. "small compared to p" is not precise. 
5. Definition 2 in appendix. This limit isn't clear the function f is on a fixed space, but the dimension of the F matrices used as an input are changing. So does f also change? How do we reconcile this?

Quality: Again this is okay, however I don't find the theory to be of good quality.

Novelty: I am not aware of (1) existing elsewhere so it may be novel, however it is not much of a departure from existing formulations. The analysis of random matrix theory is straightforward and applying it in this sort of way has been done elsewhere (see citations in the paper).

Reproducibility: No code provided. 
summary_of_the_review: It seems as though the topic presented here may be a valid line of research, but the paper presented here is not in state that I can recommend acceptance. Additionally the limited experimental evaluation and theoretical contributions are make this work very niche, I do not think this would be of significant interest to the ICLR crowd.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work investigates the performance of a linear semi-supervised learning method named QLDS. The method in formulated in terms of an empirical risk minimisation problem consisting of the standard ridge risk (square loss + $\ell_2$ penalty) for the labelled data and a quadratic term for the unlabelled data encouraging low-density solutions. Since the risk is quadratic, one can write down an explicit solution, therefore mapping the question of computing the performance of QLDS to a random matrix theory problem. The key question of interest is how to optimally tune the hyperparameters gauging the trade-off between the supervised and unsupervised parts in order to minimise the population misclassification error. The main contributions are:

1. Under a concentration assumption on the data, to show that the predictor is an asymptotically Gaussian random variable with mean and standard deviation given by the solution of a set of self-consistent equations (Theorem 1). In particular, this can be used to derive an exact asymptotic formula for the misclassification error depending on the hyperparameters of the problem.

2. The equations above depend on the Gram matrix of the population means of the data. The second result provides a theoretical guarantee on the estimation of these means depending on the quantity of labelled data available (Proposition 2).

Together, these two results are used to study how to design a procedure to tune the hyperparameters in the model (relative strength between supervised and unsupervised terms), summarised in Algorithm 1. Some numerical experiments on both synthetic and real data are provided, comparing cross-validation to the procedure proposed, and the performance of optimally tuned QLDS to other methods from the literature.
strength_and_weaknesses: **Disclaimer**: For full transparency, I have previously reviewed this submission at a different venue where it was evaluated by four referees and the AC as a borderline rejection, with a recommendation to review and resubmit. Quoting the decision:

> *"Ultimately this was a borderline decision, and I reviewed the paper myself to make a final decision. I believe that the paper is in need of a major revision to address the issues raised by the reviewers, and thus cannot recommend acceptance at this time. But I do hope the authors revise and re-submit this paper to another top conference soon."*

Although the content of the work is essentially the same, I am happy to see that the authors have taken most of the suggestions raised by the reviewers into account in this new submission. In my (fresh) review below, I revisit some of the points previously discussed with the authors in view of further improving the submission.

**Strengths**: The paper is well-written and easy to follow. The exact asymptotic analysis of a semi-supervised task adds to a literature which has mostly focused on supervised and unsupervised settings.

**Weaknesses**: On the other hand, on a technical level this work doesn't bring any new significant technical contribution, but rather combine existing tools to analyse a task of interest.

**Comments**

- **[C1]**: I appreciate the authors have made an effort to diversify their bibliography. Just a small note on a new sentence in the *Related work* section:

>To continue with physical statistics-based methods, we highlight (Lelarge and Miolane, 2019) which derived Asymptotic Bayes
risk using theoretical information and a replica method.

[Lelarge, Miolane '19] *do not* employ the replica method. Instead, they do give a heuristic derivation of their result based on the *cavity method*, which is closely related to the "leave-one-out" method from RMT (and which I believe the authors are more familiar). This result is then proven using Guerra's interpolation technique [Guerra '03] and the Aizenman-Sims-Starr scheme [Aizenman et al. '03].

- **[C2]**: Although this is now mentioned en passant below eq. (1), the assumption that the regularisation $\lambda$ needs to be fixed to the top singular value of the features in order to make the empirical risk convex is very important for Theorem 1. This should be made more explicit in the assumptions.

- **[C3]**: In my previous review, I noted to the authors that the claim that it is a *"well-stablished fact that quadratic cost function are asymptotically optimal"* is both strong and inaccurate in the stated generality, since it is setting specific. For instance, for a simple binary classification task in a teacher-student setting with Gaussian covariates, optimally regularised ridge regression has a generalisation decay of $\sim n^{-1/2}$ while optimally regularised logistic regression has a generalisation decay rate of $\sim n^{-1}$, which matches the Bayes-optimal rate for this problem [Aubin et al. '20]. But other examples of settings where there is a clear benefit of using other losses over the square loss abound, e.g. random features model [Gerace et al. '20] or kernel classification with source and capacity conditions [Cui et al. '22] to mention a few.

The authors now mention they added a Table 4 in the appendix justifying this claim in their setting, but I was surprised to find Table 4 doesn't exist in the appendix.

Honestly, I don't understand why the authors insist in such a strong claim which is setting specific and wrong in general.


- **[C4]**: One of the key points of the paper is that SSL improves over the supervised baseline by using the theory motivated Algorithm 1 (QLDS). Therefore, a fair comparison should benchmark QLDS against both the fully supervised and unsupervised settings at *optimal* (and not fixed) regularisation (as done in the main text). Unless I missed it, this is only discussed in Appendix G:

>[...] Figure 5 which looks like a "phase diagram" shows that a non-trivial
gain is obtained with respect to a fully supervised case. In particular, one can see that the gain of
using a semi-supervised approach is relevant when few labeled samples are available and when the
task is difficult. This conclusion is similar to existing conclusion from (Mai and Couillet, 2021;
Lelarge and Miolane, 2019).

I believe the discussion of when one gains using SSL with respect to the baseline is quite a quite relevant outcome of this work. Therefore, I would strongly suggest the authors to mention it in the discussion of the theoretical results in the main text.


**Small typos**:

- *"[...] using theoretical information"* -> *"[...] using information theory"*

**References**:

[[Aizenman et al. '03]](https://journals.aps.org/prb/abstract/10.1103/PhysRevB.68.214403) M Aizenman, R Sims, and SL Starr. *Extended variational principle for the Sherrington-Kirkpatrick spin-glass model*. Physical Review B, 68(21):214403, 2003.

[[Guerra '03]](https://link.springer.com/article/10.1007/s00220-002-0773-5) F Guerra. *Broken replica symmetry bounds in the mean field spin glass model*. Communications
in mathematical physics, 233(1):1–12, 2003.

[[Aubin et al. '20]](https://proceedings.neurips.cc/paper/2020/hash/8f4576ad85410442a74ee3a7683757b3-Abstract.html) B Aubin, F Krzakala, Y Lu, L Zdeborová, "Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization", Part of Advances in Neural Information Processing Systems 33 (NeurIPS 2020)

[[Gerace et al. '20]](https://proceedings.mlr.press/v119/gerace20a.html) F Gerace, B Loureiro, F Krzakala, M Mézard, L Zdeborová, "Generalisation error in learning with random features and the hidden manifold model", Proceedings of the 37th International Conference on Machine Learning, PMLR 119:3452-3462, 2020.

[[Cui et al. '22]](https://arxiv.org/abs/2201.12655) H Cui, B Loureiro, F Krzakala, L Zdeborová, "Error Rates for Kernel Classification under Source and Capacity Conditions", arXiv: 2201.12655 [stat.ML]
clarity,_quality,_novelty_and_reproducibility: The manuscript is clear and well-written, and to my best knowledge this is the second work in the literature providing sharp asymptotics for a semi-supervised setting (with [Lelarge, Miolane '19], who analysed the Bayes-optimal performance being the first).

The code to reproduce the plots is not provided with the manuscript.
summary_of_the_review: This works provides a sharp asymptotic analysis of a semi-supervised setting, providing a theory-driven efficient algorithm to optimally tune the hyperparameters, and provides numerical support for the theory. Most of the concerns raised by the reviewers in the previous version have been fixed, and I hope the additional suggestions will further improve the work.

Overall, I believe this work is of interest to the ICLR community.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a linear semi-supervised classification model, where the low density separation assumption is implemented via quadratic margin maximization. 

It bridges supervised and unsupervised learning - the least-square support vector machine in the supervised case, the spectral clustering in the fully unsupervised regime.
strength_and_weaknesses: * Strength

The proposed method bridges supervised and unsupervised learning.

* Weakness

There is a lack of non-asymptotic results.
clarity,_quality,_novelty_and_reproducibility: The proposed method bridges supervised and unsupervised learning - the least-square support vector machine in the supervised case, the spectral clustering in the fully unsupervised regime.
summary_of_the_review: The proposed method bridges supervised and unsupervised learning, and this is very new to me.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper presents a novel asymptotic analysis of semi-supervised learning based on ideas borrowed from random matrix theory. After multiple rounds of discussion, it was clear that this paper is not polished enough in its current form. There are too many typos and missing definitions, particularly in the proofs which at least one reviewer checked carefully. Reviewers agreed that another round of revision is needed.

In their discussion, the authors contend that some of these definitions are standard in other parts of the literature, but I can attest that many of these terms are not mainstream in ML. Since this submission is to a top ML conference, it is essential to properly motivate and define everything so that an ML researcher can verify the claims independently.

I urge the authors to carefully take the feedback from the reviewers into account and prepare a careful revision that defines everything carefully and corrects the many typos found by the reviewers.
justification_for_why_not_higher_score: Concerns about proofs and overall lack of polish in the writing
Decision: Reject