Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: **Summary**
This paper investigates why conjugated pseudo label in test-time adaptation (TTA), which is recently proposed approach, perform better than hard pseudo-labeling. Specifically, they show that under Gaussian model, GD with hard pseudo-labels fails to find optimal solution while GD with conjugated pseudo label reaches optimal solution. 

strength_and_weaknesses: **Strength**

**[S1]** This paper is generally well written and easy to follow. 

**[S2]** Conjugated pseudo label is timely topic in test-time adaptation. Besides, pseudo-label itself is general techniques and worth investigation. 

---
**Weakness**

**[W1] Assumption of the analysis is not tailored for TTA. ** While this paper mainly focus on the test-time adaptation setup (as clearly shown in the title), the current analysis seems to be hold for general pseudo-label setup. In other words, it is unclear what is the uniqueness of the TTA setup, and how the analysis explain the nature of conjugated pseudo-label. 

Of course, the generality of the analysis itself is not a bad thing, however, it is unclear for me how the analysis is significant if it is not tailored for TTA. The paper should clearly discuss whether the current analysis is specialized for TTA setup, or more general one. Besides, if the later case, the paper should discuss more on what was already well investigated in pseudo-labeling and how the analysis in this paper is significant compared to existing findings. 


**[W2]Practical implication is limited. ** Since the analysis conducted only for the simple case on binary classification with Gaussian model, practical implication is limited. They also provide only limited toy empirical investigations. 
clarity,_quality,_novelty_and_reproducibility: **[Clarity and Quality]**
This paper is generally well written. 

---
**[Novelty]**
See weakness section. 

---
**[Reproducibility]**
Not applicable. 

summary_of_the_review: Overall, I agree that the conjugated pseudo label is timely and worth to investigate topic, but the current analysis is limited to very limited setup and therefore the practical impact is limited. Since I am not the theory person, I might underestimate the significance of the theoretical advancement.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper tries to theoretically understand why GD with conjugate labels outperform other pseudo labels. Further results focus on the role of the loss function and provide certain guarantees on the convergence.
strength_and_weaknesses: There has been much work on test-time adaption in recent years. Although certain behaviours are empirically understood, we often do not understand the underlying principles yet.
Although the authors make certain assumptions (e.g., binary labels, population dynamics), these assumptions are probably necessary for coming up with theoretical guarantees and are not too limiting.
The main results are well-explained and technically sound. As such, they do not only provide as with a better understanding, but might spur future research for more general settings.

The empirical evaluation is restricted to a small synthetic example. These experiments corroborate the theoretical findings and as such are sufficient for the scope of this paper. Yet, one could argue that coming up with constructive insights from the theoretical work and showing some improvements on some more realistic test-time adaptation problems would have been nice.

From Algorithm 1 I further take that the samples are all drawn from the same new domain. It can make a drastic difference whether this is the case or if the domain changes more frequently. Although this assumption makes sense in many settings, I miss a brief discussion on it.
clarity,_quality,_novelty_and_reproducibility: The paper is well-motivated and well written. As far as I can tell, the theoretical work is of good quality. I particularly like that the authors are very honest about the scope and the limitations of the work, i.e., the paper actually delivers what is promised. Moreover, I really enjoyed that the main arguments of the proofs (which are arguable the main contribution of the paper) can be found in the main text and are not hidden in the appendix.
summary_of_the_review: The main contribution of the paper is that it provides a novel understanding on the role of the labels (conjugate vs. hard) and the loss function on the potential for test-time adaption. As such, I think it is an interesting theoretical piece of work that might spur further research in this direction.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper is a theoretical analysis of a recent work [a]. They use the Gaussian model to explain and understand the gradient descent with hard-label and conjugate labels. For convenience analysis, they only consider the binary classification problem. The theoretical results and analysis are interesting. 

[a] Test-Time Adaptation via Conjugate Pseudo-labels. NeurIPS, 2022.
strength_and_weaknesses: 1. This paper focuses on binary classification problem, and the authors analyze three classical loss functions: square loss, logistic loss, and exponential loss. But binary cross-entropy loss has been widely studied in community, especially for training deep models. So, I am interested in the results of this loss function.
2. The assumptions adopted by the author seem to be somewhat strict, such as that the conjugate function must be an even function. We know that not all functions satisfy this constraint. If it is an odd function, does the conclusion in the paper still hold?
3. We find that the Gaussian models used in Section 3 and Section 5 are different. How much does this different choice affect the conclusion? If we still use the Gaussian model in Section 3, will the conclusions of Section 5 not hold?
4. In section 5, we observe that the normalized operation of the parameter w is ignored. Whether or not to use normalized has a large impact on the results, and the authors need to clarify this modification.
5. How to derive Equation 24 is not very clear.

clarity,_quality,_novelty_and_reproducibility: The theoretical analysis and results are novel enough and the presentation is clear. However, the assumptions of the paper are a bit too strong, and the conclusions of the paper have limitations.
summary_of_the_review: This paper gives an interesting understanding of the GD with hard and conjugate labels for test-time training. I think this will bring new insights to the community.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents theoretical insight to explain GD with hard and conjugate labels for a binary classification problem.This paper shows that for square loss, GD with conjugate labels converges to a solution that minimizes the testing 0-1 loss under a Gaussian model, while GD with hard pseudo-labels breaks down. Besides，the authors discuss them under different loss functions.
strength_and_weaknesses: Strength：
- The paper is well-organized and clearly written, which is easy to follow.
- The theoretical work of this paper is sufficient, which improves the value of the paper.
- The paper provides insights into when and why GD with hard labels or conjugate labels works in test-time adaptation.

Weakness：
- The original conjugate pseudo-labels[A] perform results across different domain adaptation. The author neglect the explaination of this scenarios. Is the convergence analysis general for diverse domain with large gap?
- My concern is the assumption in equation (8). The authors have not provided the value range of $\epsilon$. Although the authors mention,”... as it means that the
source model is better than the random guessing in the new domain.”, how to illustrate the special case of right angle when $\epsilon=1$？
- The convergence of GD was analyzed in section 5. What is the main obstacle to investigating convergence according to the idea proposed in this paper？ Moreover, in section 5.2, does $log(t)$-rate convergence boost compared to the convergence rate of related pseudo labels？

[A] Sachin Goyal, Mingjie Sun, Aditi Raghunathan, and Zico Kolter. Test-Time Adaptation via Conjugate Pseudo-labels. NeurIPS, 2022.


clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is well-organized and clearly written.

Quality: Technically solid paper.

Novelty: The paper makes non-trivial advances over the current state-of-the-art.

Reproducibility: Key details are sufficiently well-described for competent researchers to confidently reproduce the main results.
summary_of_the_review: Please see Q1 and Q2.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Thanks for your submission to ICLR.

Three of the four reviewers were positive about the paper, and the fourth reviewer was borderline by the end of the discussion period.  Strengths of the paper: the paper is well-written, on an interesting topic, and contains an interesting theoretical analysis.  Weaknesses: several reviewers noted some issues with assumptions required for the theory, limited practicality, and a somewhat restrictive empirical evaluation.

The most negative reviewer did raise their score during discussion, and indicated that they were not opposed to accepting the paper.  The authors did a good job in responding to the concerns of the reviewers.  Thus, I am recommending accepting the paper.
justification_for_why_not_higher_score: The reviewers were overall positive, but one reviewer stayed on the fence and there remain some concerns about assumptions made in the paper (along with practicality of the results).
justification_for_why_not_lower_score: In the end, three of the four reviewers advocated for accepting the paper, and the weaknesses noted by the reviewers seem not large enough to warrant rejecting the paper.
Decision: Accept: poster