Towards Understanding GD with Hard and Conjugate Pseudo-labels for Test-Time Adaptation
Authors: Jun-Kun Wang
Andre Wibisono
Venue: ICLR 2023 poster (2023)

Abstract: We consider a setting that a model needs to adapt to a new domain under distribution shifts, given that only unlabeled test samples from the new domain are accessible at test time. A common idea in most of the related works is constructing pseudo-labels for the unlabeled test samples and applying gradient descent (GD) to a loss function with the pseudo-labels. Recently, Goyal et al. (2022) propose conjugate labels, which is a new kind of pseudo-labels for self-training at test time. They empirically show that the conjugate label outperforms other ways of pseudo-labeling on many domain adaptation benchmarks. However, provably showing that GD with conjugate labels learns a good classifier for test-time adaptation remains open. In this work, we aim at theoretically understanding GD with hard and conjugate labels for a binary classification problem. We show that for square loss, GD with conjugate labels converges to an $\epsilon$-optimal predictor under a Gaussian model for any arbitrarily small $\epsilon$, while GD with hard pseudo-labels fails in this task. We also analyze them under different loss functions for the update. Our results shed lights on understanding when and why GD with hard labels or conjugate labels works in test-time adaptation.

Published as a conference paper at ICLR 2023
TOWARDS UNDERSTANDING GD WITH HARD AND CON- JUGATE PSEUDO-LABELS FOR TEST- TIME ADAPTATION
Jun-Kun Wang and Andre Wibisono
Department of Computer Science, Yale University (jun-kun. wang, andre. wibi sonosoooolllleee
ABSTRACT
We consider a setting that model needs to adapt to new domain under distribution shifts, given that only unlabeled test samples from the new domain are accessible at test time. A common idea in most of the related works is constructing pseudo- labels for the unlabeled test samples and applying gradient descent (GD) to a loss function with the pseudo-labels Recently, Goyal et al. (2022) propose conjugate labels, which a new kind of pscudo-labels for self-training at test time. They empirically show that the conjugate label outperforms other ways of pscudo- labeling on many domain adaptation benchmarks. However, provably showing that GD with conjugate labels learns good classifier for test-time adaptation remains open. In this work, we aim at theoretically understanding GD with hard and conjugate labels for a binary classification problem. We show that for square loss, GD with conjugate labels converges to an e-optimal predictor under a Gaussian model for any arbitrarily small e, while GD with hard pseudo-labels fails in this task. We also analyze them under different loss functions for the update. Our results shed lights on understanding when and why GD with hard labels or conjugate labels works in test-time adaptation.
INTRODUCTION
Fully test-time adaptation is the task of adapting a model from a source domain so that it fits to a new domain at test time, without accessing the true labels of samples from the new domain nor the
data from the source domain (Goyal et al., 2022; Wang et al., 2021al Li et al.) 2020;; Rusak et al.
2021 Zhang al. 2021a S Fleuret, 2021| Mummadi et al. [202] Iwasawa & Matsuo [022]] Liang et al. 2020 Niu et al. 2022, hopalli et al. [022 Wang et al. 2022b Kurmi et 2021l. Its setting is different from many works in domain adaptation or test time training, where the source
data or statistics of the source data are available, e.g., Xie et al. (2021 1); Liu et al. (202 a); Prabhu
cet al. (202T); Sun et al. 20200; Chen el al. Hoffmmnn el al. (2018); Eastwood et al. (2022);
Kundu et al. (2020); Liu et al. (2021b) Schneider et al. (2020); Gandelsman et al. (2022) Zhang et al. (2021b); Morerio et al. (2020); Su et al. (202)). Test-time adaptation has drawn growing interest recently, thanks its potential in real-world applications where annotating test data from new domain is costly and distribution shifts arise at test time due to some natural factors, e.g.. sensor degradation (Wang et al. (021a), evolving road conditions (Gong et al.] [002]] Kumar al. 2020). weather conditions (Bobu et al. 2018), or change in demographics, users, and time periods Kohh al. 202T
The central idea in many related works is the construction of the pseudo-labels or the proposal of the self-training loss functions for the unlabeled samples, see e.g.. Wa.g et al. (2021a); Goyal et al. (2022). More precisely, at each test time t. one receives some unlabeled samples from new domain, and then one constructs some pseudo-labels and applies a GD step to the corresponding self-training loss function, as summarized in Algorithm [ Recently, Gooal et al. (2022) propose a new type of pseudo-labels called conjugate labels, which is based on an observation that certain loss functions can be naturally connected to conjugate functions, and the pseudo-labels are obtained by exploiting a property of conjugate functions (to be elaborated soon). They provide a modular approach of constructing conjugate labels for some loss functions, e.g., square loss, cross-entropy loss, exponential loss. An interesting finding of Goyal et al. (2022) is that a recently proposed self self-training loss for test-time adaptation of Wang al. (2021a) be recovered from their conjugate-label

---

Published as a conference paper at ICLR 2023
Algorithm 1: Test-time adaptation via pseudo-labeling
1: Init: wi ws, where wy the model learned from source domain.
2: Given: Access to samples from the data distribution Deu a new domain.
3: for I = 1,2. T" do
4: Get a sample 2; ~ Diea from the new domain.
5: Construct pscudo-label ywu y (2z)) and consequently self-training loss function gaelé (w); 27).
6: Apply gradient descent (GD): We+1 Wi 1y goelf baelt (wx; xz).
7: end for
framework. They also show that GD with conjugate labels empirically outperforms that of other pseudo-labels like bard labels and robust pseudo-labels (Rusak et al.] (202T) across many benchmarks, e.g., ImageNet-C (Hendrycks Dietterich, 2019), ImageNet-R (Hendrycks et al. 202T), VISDA-C (Peng et al. 2017), MNISTM (Ganin & Lempitsky 2013). However, certain questions are left open in their work. For example, why does GD with conjugate labels work? Why can it dominate GD with other pseudo-labels? To our knowledge, while pscudo-label are quite indispensable for self- self-training in the literature (Li et al. 2019 Zou et al.] 2019). works that theoretically understand the dynamic of very sparse, and the only work that we aware is of Chen et al. (2020).
GD with pseudo-labels Chen et al. (2020) show that when data have spurious features, if projected GD is initialized with sufficiently high accuracy in new domain, then by minimizing the exponential loss with hard labels, projected GD converges to an approximately Bayes-optimal solution under certain conditions. In this work, we study vamilla GD (without projection) for minimizing the self-training loss derived from square loss, logistic loss, and exponential loss under hard labels and conjugate labels.
We prove performance gap between GD with conjugate labels and GD with hard labels under a simple Gaussian model (Schmidt et al. 2018 Carmon et al. 2019). Specifically, we show that GD with hard labels for minimizing square loss can not converge to an c-optimal predictor (see (8) for the definition) for any arbitrarily small while GD with conjugate labels converge to an c-optimal predictor exponentially fast. Our theoretical result champions the work conjugate labels Goyal et al. (022). We then analyze GD with hard and conjugate labels under logistic loss and exponential loss, and we show that under these scenarios, they converge to an optimal solution at a log(t) rate, where t is the number of test-time iterations. Our results suggest that the performance of GD in test-time adaptation depends crucially on the choice of pseudo-labels and loss functions. Interestingly, the problems of minimizing the associated self- self-training losses of conjugate labels in this work non-convex optimization problems. Hence, our theoretical results find an application in non-convex optimization where GD can enjoy some provable guarantees.
2
PRELIMINARIES
We now give an overview of hard labels and conjugate labels. But we note that there are other proposals of pseudo-labels in the literature. We refer the reader to ti et (2019) Zou al. (0119;
Rusak et al. 2222 and the references therein for details.
Hard labels: Suppose that a model w outputs h (ar) E RR and that each element of ha could be viewed as the predicted score of each class for multi-class classification problem with K classes. hard pscudo-label y/! hard (z: is a one-hot vector which is 1 on dimension i (and elsewhere) k arg max; New (z:) [kc]. i.c., class & has the largest predicted score by the model w for a sample (Goyal et al. 2022). On the other hand, for a binary classification problem by a linear predictor, i.e., h w/ x, hard pseudo-label is simply defined as:
hard see, e.g., Kumar et al. 22200) Chen et al. 2020 GD with hard labels is the case when Algorithm T uses hard label to construct a gradient V. feell (wy; xx)) and update the model w.
sign(w" Tz).
Conjugate labels (Goyal et al., 2022): The approach of using conjugate labels as pseudo-labels crucially relies on the assumption that the original loss function is of the following form:
E(w; (J,x)) == fh (2))
(x),
(2)
where f(-) : R + IR is a scalar-value function, and y E RK is the label of x, which could be one-hot encoding vector in multi-class classification. Since the true label y of sample is not
2

---

Published as a conference paper at ICLR 2023
Table Summary of (Hard, Conjugate] pseudo-labels and the resulting self-training loss functions using square loss, logistic loss, and exponential loss.
Square loss: (w;; (2,, y)) == (y - w xx)
Hard
Wo (x) sign( w 22)
ghard (w; x) (sigu( w x))
x)²
Conjugate
yw (x) w x
geous (w; x)
(w x)²
Logistic loss: glogit (w: (a. 4)) == log (cosll w x) ) y(w a)). where y = {+1, - 1}.
Hard
bard (x: sign 2²)
ghard (w;
log (cosh (w 2)
1w x
Conjugate
yiu
con) (x) = tanh (w [TTx))
geous (w:; 1) = log (cosh (w T x)
tanh (w x
w
Exponential loss: goxp (wu (z., u]) := exp( you x.), where
{+1, -1).
Hard
bard (x)
sign 2)
guard (w; x) exp( æ))
Conjugate
surn (x) = Lanh (w" Tx)
(coul (w: .r) = sech (w
available in test-time adaptation, it is natural construct pseudo-label yo pooodoo (z) and consequently self-training loss function by replacing y with y (ar) in (2).
geons (w: x) :- f(hw - pooudo (x) how (z).
One can then compute the gradient V cemmi(w; x)) and use GD to adapt the model w at test time.
Define h4 E RK as h. + arg minkeRK f(h y h, where (v) mInBeRK f(h) y h the conjugate function, see e.g, Chapter 3.3 in Boyd et al. (2004). It turns out that he satisfies y fh.). From the similarity, Goyal et al. (2022) propose conjugate labels:
y (z) V fh
(4)
where yo (x) is possibly a real-value vector instead of a one-hot encoding vector. Let y (x))
<-
y ponj
Then, we get the self- self-training loss function using the conjugate label:
groni x) = (()(())) V (he
hy (2r).
(5)
We note that GD with conjugate labels is an instance of Algorithm V we geoni (W;; De) at each test time f.
I when we let V V en (wer
xxe) +
Table I summarizes conjugate labels and hard labels as well as their self- training loss functions using square loss, logistic loss, and exponential loss. We provide the derivation of the case using square loss below, while the rest of them are available in Appendix A
(Square loss) Example of a conjugate label y coml (x)) and its self-training function gooni x):
x)² is in the form of 2 up to constant, where f(-) R- Rt. Substituting f(-) (-)2 and h(w) w x in 44 and 5) we get
Observe that square loss l(w; (I, v)) {
Voon (x) ww x, and geons (w:; x)
2 (w x))
(6)
THEORETICAL FRAMEWORK: GAUSSIAN MODEL
Our theoretical analysis considers a binary classification setting in which samples from the new domain are generated as ~ N (yn, o² E Rd, where μ E Rd is the mean and o² > 0 is the magnitude of the covariance. The label y is assumed to be uniform on [-1, Therefore, we have P(X Y y) [> Nyuu, Lla) and (y -1) Ply 1) 1/ under Gaussian model (Schmidt ct al. 2018 Carmon et al. [2019 Kumar et al. 2020).
Given test sample x, a linear predictor E Rd makes prediction of the label (x) as nn (x) sign(w? T 2). While a model could be self-trained under various loss functions, the natural metric to evaluate model for classification is the expected 0-1 loss. Under Gaussian model, the expected (-- loss enjoys a simple closed-form expression:
(0-1(w) == Ezz. (v) + [}} = Plyw T x < =
< <0) = =
11 w
| |
3

---

Published as a conference paper at ICLR 2023
where (u) := V2n J exp(-22 /2)d2 is the Gaussian error function. From 77
that the predictors that minimize the 0- loss are those that align with y in direction and the minimum error
+ |
In other words, optimal linear predictors w, E _d has to satisfy cos
1. Tall
1
In our theoretical analysis, we let μ = [|| O, .,....,. 0J Rdd namely, the first element is the only non-zero entry. Our treatment is without loss of generality, since we can rotate and change a coordinate
system if necessary. For any vector w E TR. its orthogonal component to هز [Ta Thanks to the assumption of μ., the orthogonal space (to μi) is the subspace of dimension 2 to d. Indeed, for any vector w, its orthogonal component (to j4) [a Tæl TpT w is always 0 in its first entry. Therefore, we can represent an orthogonal component of w as [w (2).........
H [xc |r] w.
E IRd-1
We call a model w E Rd an c-optimal predictor under Gaussian model if it satisfies two conditions:
Condition 1: w. | ) w11] > 0 and Condition 2: cos?
2
| ||ll|
Using 7 the expected 0-1 loss of an c-optimal predictor is (w-(ww + [ell v1 (11-)) c).
To get an e-optimal predictor, we need to satisfy (w, p) > 0 and also need that the ratio of the projection onto to the size of the orthogonal component to z is as large as possible, i.e.,
=11]² is large, which can
Σ [*[
be seen from the following equalities: cos² (1 ||lll
(w) |
2id wit?
wij
The projection of w onto μ has to be positive and large when the size of the orthogonal component is non-zero to get an c-optimal predictor, i.e., w| >> 0.
Finally, in our analysis we will assume that the initial point satisfies Condition I on 8 which means that the initial point forms an acute angle with jr. This is mild assumption, as means that the source model is better than the random guessing in the new domain.
Related works of Gaussian model: In recent years, there are some works that adopt the framework of Gaussian model to show some provable guarantees under various topics. For example, [Schmidt al. (2018) and Carmon et al. (2019) studying it for adversarial robustness. For another example, Kumar et al. (2200) recently show that self- trriniriiig with hard labels can learn good classifier when infinite unlabeled data are available and that the distributions shifts are mild. Their theoretical result perhaps is the most relevant one to ours in the literature, in addition to Chen et all (2020) that we have discussed in the introduction. Kumar et al. (2020) consider the setting of gradual distribution shifts so that the data distribution in each iteration is different and that the update in each f is minimizer of a constrained optimization:
We <- arg min Eg [L (y hard (x)) T x)], where + = {w |||||| < 1. ||w w1-1ll S }
(9)
a continuous decreasing function, D, represents the data distribution at I, and yaard (x) == sign(w? z)) is the hard label for an unlabeled sample æ. The main message of their result that even though the data distribution of the target domain could be very different from that of the source domain, by using data from the intermediate distributions that change gradually, good classifier for the target domain can be obtained in the end. On the other hand, we consider analyzing GD with pseudo-labels distributions. Our goal is to provably show that GD with pseudo-labels can learn an optimal classifier in new domain when only unlabeled samples are available test time, which is different from the setup of Kumar et al. 2020) that simply assumes the access to a minimizer of a certain objective.
D. L(-)
test-time iterations, and we do not assume that there are intermediate
4 (A NEGATIVE EXAMPLE) GD WITH HARD LABELS UNDER SQUARE LOSS
One of the common loss function is square loss. Recent works have shown that even for the task of classification, a model trained under square loss can achieve competitive performance for classification
4

---

Published as a conference paper at ICLR 2023
compared to that of a model trained under certain classification losses like cross-entropy loss (Demirkaya et al. 2020; Han et al. 2022 Hui & Belkin 2020). In this section, we analyze test-time adaptation by GD with hard pscudo-labels under square loss. Recall the definition of square loss:
((u;; (2r, v)) = 2 (y w 2²)². By using hard labels as ( the self-training loss function becomes
1 (shard
ghaedd w x)
(z) ((ar(())
w (0)))))) - (sign(w z) w wT))
(10)
2
It is noted that the derivative of sign(-) is 0 everywhere except the origin. Furthermore, sign(.) is not differentiable at the origin. Define s0)n(0) O. Then, sign(w' x) - w x 0 when w x = O, which allows us to avoid the issue of the non con-differentiabiiity. Specifically, we can write the gradient as V ghaard (w;a x) = - (sign( w z) w 2) x. Using the gradient expression, we obtain the dynamic of GD with hard labels under square loss,
(11) What we show in the following proposition is that the update we of (TT) does not converge to the class mean y in direction. However, it should be noted that a perfect classifier (i.e., one that has the zero 0-1 loss) does not necessarily need to align with the class mean μ depending on the setup.
W++1 W - v/ ghard (wy: zt) wa + 1) (sign(w, 21) w. 21) Zt.-
Proposition 1. GD with hard labels using square loss fails to converge to c-optimal predictor for any arbitrarily small e >> O even under the noiseless setting of Gaussian model (o 0). More precisely, we have cos
TTenl 1 S 1 E,, for some > 0 as t + oo if Woo exists.
Proof. In this proof, we denote ā. :- we [1] = We,
1 THll
From 11.. we have
u ã. + 77 (sign(w) w/ x1) w 23)
Iee |
(12)
Let us consider the simple noiseless setting of Gaussian model, i.c., O, as we aim at giving a non-convergence example. Then, we have xt yo and the dynamic 112
becomes
ā,+1 = (1 - 1|| ya, + 17 sign (d. [d]l)())||
(13)
where we used vo = and yı sign(y:-) sign(-) because y/: [[-1,+1)
Case: 1) < T Given the initial condition ā > 0. we have a. 0, At from 13 and
sign(a; l|ll]) 1, Vt. Then, we can recursively expand obtain
13 from time t + back to time 1 and
Øe+1 (1 ))|"))))² (1
+ nllaa E. (1nllaa1))
(14)
From 14). we know that + 1 ||]] as f + co, where we used that Ee - 12)
On the other hand, the dynamic of the orthogonal component * 1 E [d] is
W w + 17 (sign(w, 21) w 22) x = we(
(15)
where in the last equality we used that xe Youu and μ = ||] f|1 0, .
Oo 0]
Rd so that x[1]]
Disn u |6? Σiz (1] 1/ That is, the ratio converges to a non-zero value, which implies that GD with hard labels fails to converge to an e-optimal predictor for any arbitrarily small c, i.e., cos
0, Vi * 1. By (14 and 15 we get
wo [1]
woo a [|w==] [|AT] S 1 7 for some >
Case: 17 > Te - Suppose ā; > 0. Then, the condition that āe+1 2 āz is TMa| 2 āt from 13 which means that the projection to y is bounded and hence the model w, cannot be an e-optimal classifier for any arbitrarily small e. On the other hand, if ā, > [[]] then ā,41 < āc, and ā could even
be negative when āz > |||- -1/(a|aa| Moreover, if > ||] and |āel > クlا 2-2 = Tpll I then the magnitude |äz| is increasing and the sign of o, is oscillating; more precisely, we will have |ar+1| 2 |āz| and sign (ar+1) = - sign(a.). Consequently, the model w, not better than the random guessing at every other iteration (recall (7)). which is not desirable for test-time adaptation.
all
In the next section, will provably show that GD with conjugate labels under square loss can learn an e-optimal predictor for any arbitrary e, which is the first thcoretical result the literature that shows the advantage of conjugate labels over hard labels, to the best of our knowledge.
5

---

Published as a conference paper at ICLR 2023
(Scenarto Excected besting 0-1 best-timet
[Scenario Expected teating loss best
atapitation
0.18
lobel
6.8
abel
0.16
Expectad saatig
2.5
hard ubel
0.34
coTa coote lacel
Seat manima ent
0.12
Ieak-imm Forna on
Sterstion
(a) Small step size
(b) Large step size 100
Figure 1: Expected 0-1 loss vs. test-time iteration of GD. GD with hard labels under square loss (bluc solid line) can not converge the class mean μ direction, while GD with conjugate labels under square loss (green dash dot line) learns an e-optimal predictor. Here, "no-adaptation" means simply predicting according to the initial model without any updates. The detailed setup is described in Appendix B
CONVERGENCE RESULTS OF GD WITH PSEUDO-LABELS
Recall that have gself ar) 1b(w² w)) for some scalar function vb(.) R R under the scenario of linear predictors. If (b(-) is an even function, i.e., (u) = +b(-)) for all u E R, then
gwelf (w; x)) = v(w" Tw)T) x) = vs (yw" (m+ +
= 1/ (w (u + +o))
(16)
where the second equality uses assumption that (-)) is an even function. We emphasize that the underlying algorithm itself does not have the knowledge of μ., a, &, and the last expression simply arises from our analysis.
y(u + of) under Gaussian model, and the last equality uses the
From 16), we know that the gradient
gollf (w; x)
Vbblw Tx) v/ (w (u+ of)) (a oE).
(17)
Hence, the dynamic of GD with pseudo-labels is
W4++1 W/
gellf (wre x.) w/ mppl (1: (n + oE)) (1c og).
(18)
Now let us analyze the population dynamics, which means that we observe infinitely many unlabeled samples, so we can take expectation on the r.h.s. of (18) We get
W1+1 = wi - n/Rag [v/ (w, (n + +))]] μ - BB [vl (w] (u + +() oE]
(19)
= wt nBE [ (w. (a (+++ p p- - [v" (w.J (u+ oε))]
(1 no [ (w) (n +))]] w. mB [Vl (wl (u aE)]] 14,
(20)
where the second to last equality uses Stein's 's identity (Stein 1981): for any function v/: Rd and { ~ (0, Ia), it holds that [e(Ev((E] = Eg(V
I
Denote a, (w,, 14) the dynamic of the component of w, along μ. Given the dynamic 20 it is clear that the component along μ evolves as:
1 (1-10 [v>" (w. (u + eE)]]) ar - 1/BE [V' (w, (p + +))]]] |
(21)
On the other hand, denote b, := || [2]..... we [d]] || the size of the component orthogonal to μ. Then, its population dynamic evolves as:
b By (1) and 22 we have
no 2 (ut" (w, (n +o)))]] be.
(22)
We further define the ratio ry = b,
TE vb (w) (1 + oE))] |a]2
T1+1 sign (1 n [V" (w. (n oE))])
(23)
- no [sl" (w, (u + +
turns out that cos
we [|
a [[lll
is an increasing function of rts Indeed,
cos
11
(w,, 1))
(we, 11)
sign(r.)
(24)
||ll
[wy
|ill
by ||
+ (we, 1)
/1 1|1113/7?

---

Published as a conference paper at ICLR 2023
(a) Hxrd+Exp.
(b) Conj+Exp.
HardtLogistic.
(d) Conj+Logistic.
Figure 2: Plots of some ceff-training loss functions that satisfy the set of properties
where used ||w:|| (wwT//////// like rr + co.
+ b9. A successful recovery (cos + 1) means that we would
In the of this paper, we will use the notations O+ or + V, where C {conj, hard] and
3 = {square, logistic, exp} for brevity. For example, hard + exp represents the self-training loss based on hard labels under exponential loss, i.e., ghard (w; x) cxp(-lw ==). GD + conj +
square stands for GD with conjugate labels under square loss in test-time adaptation.
5.1 (EXPONENTIAL-RATT CONVERGENCE) GD + conj + square
Proposition 2. (GD + conj + square) The ratio of the projection onto to the size of the orthogonal component grows as
T+1 = r (1 (1+ 1+ no?
log(lla log([la)//(rtt) ((r())
Furthermore, GD learns c-optimal predictor after t [ng[++nllul? [|llu1////0 (1++)o))) iterations.
Proof. For GD conj + square, the self-training loss is geonj xw - )² from 66. Hence, (b)) - 2 ()) in (6); moreover, v/ v)(-) (.) and (:) -1 in 23). Therefore, we have
Ee - (w) (n + [)) = Eg [w + [ = wi l since EEg [w) E) O, and we also have in 23).
Eg 113" (w: (k+ at)]] = Eg [-1]
Consequently, the dynamic of the ratio is
Tw u|llll (1 + no2)b,
7 n|all + non
nllkll (1+
Te+1 = r
1 +
+ no?
(25)
From 24 and 25 the cosine between and μ is positive and increasing, given the initial condition
a1 (or equivalently, r1 > 0). Hence, Condition on 8 holds for all By using (24). we see
that to get 6-optimal predictor at test time 4, we need to satisfy /1/|1// ( (1+
n alla 26
It
S
log(lla 2 ((er))) log(1+ M (1
Simple calculation shows that
Proposition I and together provably show performance gap between GD + conj + square and GD + hard square. Using conjugate labels, GD converges to the class mean /l in direction exponentially fast, while GD with hard labels fails in this task.
5.2 log(!)-RATE CONVERGENCE GD
In this subsection, we consider self- seff-training loss functions, ganlt ganl((w;;)) = v/w (( x), that satisfy the following set of properties & with parameter (L, (minn): ): (i) Even: vb(-a) = (b(a) for R. (i) There exists 0 < L < oo such that -3y' (a) 2 e for all 2 Omin-
Lemma 1. The following relf-training loss functions goelf (w: x) = (bw" (x) satisfy d More precisely,
we have:
1. hard exp: (b)) exp(-lu) satisfies with (T. 1, amin 0).
7

---

Published as a conference paper at ICLR 2023
2. hard logistic: (i(u) log (cosh (u)) |u] satisfies with (L = 2, Omin 0).
3. conj + exp: (1) soch(u) sarisfies with (L 1, Omin 0.75).
4. conj + logistic: (b) log (cosh (u)) tanh (u) satisfies
with (L = 2, Omin 0.5).
The proof of Lemma is available in Appendix C
Figure plots the self-training losses listed in
Lemma [
From the figure, one might find that Property evident for these self-training losses.
We will also need the following supporting lemma to get a convergence rate.
Lemma 2. Consider the dynamic: T++1 2 Ti + ce Ir, foor some L > 0 and c 2 0. Suppose that initially T1 > 0. Then, Tt-r. 2 2L log c(t - for all t > Tx, where Tx 0 Dfv S e Vv 2
otherwise, T. = (L(C/ where v. (L) is the unique fixed point of v. evv., if exits.
Proof. From the dynamic, it is clear that rs+1 2 Te since e 2 0. Then,
e 2 clrttr + (runn)))) 2 e el c er + 2 ct,
(26)
where the last step follows from unrolling the recursion t times.
We first analyze the case that rt e Since rt e we have 2br, 2 dt 1) from 26) Hence, Ti 2 27. log e(t -).- 1).
Now let us switch to the case that r; 2 ee Let v. (L) the unique point of v. such that 1/, = L...
26
rf S (L), then r; 2 g Hence, we have rī 2 rie
dt- - 1). So ve(t- Note
this possibility cannot happen more than == v² [L) times, since we need ri S r. to stay in this regime. So eventually we get out of this regime after a constant number т. iterations.
Now we are ready to state another main result in this paper. Proposition 3 below shows a log(!)- convergence rate of GD with pseudo-labels in the noiseless setting o² if the underlying self- training loss function satisfies + The gap between the exponential rate of GD with conjugate labels using square loss shown Proposition and the logarithmic rate in Proposition B suggests that the performance of GD in test-time adaptation also crucially depends on the choice of loss functions, in addition to the choice of pseudo- labels.
Proposition 3. (Noiseless setting) Apply GD to minimizing grelf (wel(
(M(wTa>), where v(.)
satisfies & If the initial point satisfies a1 amiu then the ratio of w/,s component along i to the size of its orthogonal component to μ at test time t, i.e., Tr in (23, satisfies
1 Lb1
Tt-T-
St
log
by
for all t Ta:
where T, is constant defined in Lemma
we know that the size of the orthogonal component does not change throughout the iterations when x² = 0, i.e., bet1 b,, Vt. On the other hand, the component along μ in the noiseless setting has the dynamic,
Proof. From 19 or
a++1
21
at + 17 (- (ar)) |A|| 2 a, + m7 ne----aa Las
|| Va, 2 amin:
(27)
where we recall := (we, (4) and the inequality uses the property regarding --0(-) as stated in & It noted that (27) implies that a is -ecceecca,,,ng,, and hence the condition about the initial point, i... aj 2 amins guarantees a, 2 amin for all test time f.
By using the above results, we deduce that the dynamic of the ratio F' := Aa satisfies T++1 + by leads to the result.
b,
"e=|ee]| = re + ne boreh where we used that 6,+1 = by = b1, Vt. Invoking Lemma
by
8

---

Published as a conference paper at ICLR 2023
Compartion of [Exocnentia ioss)
Comparison of (Logitt loss) hard laeel
bagon balcl
120
Figure 3: We plot [(2) = (x))) vs. 2, where (-) the first derivative of the underlying self-training
loss. Left: L(2) vs. z of hard + exp and conj + exp. Right: [(z) vs. 2 of hard + logistic and conj + logistic.
eeparemtial Jonn
Ingistir Inve
0.20
0.30
5.10
no cdlpttation
0.310
odasiazion
0.34
0.32
0.12
195
200
$40
200
600
1000
Figure 4: Expected 0-1 loss &b
vs. test-time t. Left: GD + hard exp and GD + conj + exp. Right:
(recall the discussion in Section Both figures show that GD with conjugate labels outperforms GD with hard labels.
GD + hard + logistic and GD couj + logistic. Here "best minimal error" [[ell] o
Proposition 3 implies that GD for minimizing self-training loss with smaller constant T, can result in faster growth of the ratio and consequently faster convergence rate. Recall the definition of L in Property & a smaller constant means that the (minus) derivative (-) of the self-training loss has a heavier tail. We therefore compare the tails of the self-training loss functions by plotting
L(=) := log(-o' (x)) of each on Figure which shows that there exists a threshold 2min such that for all 2 2 Smin. the number L(2) that corresponds to the loss function with the conjugate label is smaller than that of the hard label. This implies that the self-training loss derived from conjugate labels can have a smaller constant L. (for a finite z) compared to that of hard labels, which in turn might hint faster convergence of GD conj compared to GD hard for exponential loss and logistic loss. Figure [4ssowss the experimental results under Gaussian model, where GD uses a received mini-bay batch of samples to conduct the update at each test time. The detailed setup is available in Appendix B We find that GD with conjugate labels dominates GD with hard labels empirically. which is aligned with our theoretical result. It is noted that for the case of exponential loss, Goyal al. (2022) report a similar experimental result under Gaussian model - GD conj exp outperforms GD + hard exp.
LIMITATIONS AND OUTLOOKS
In this paper, we analyze GD with hard and conjugate pseudo-labels for test-time adaptation under different loss functions. We study the performance of each of them under binary classification framework, identify scenario when GD with hard labels cannot converge to an c-optimal predictor for any small while GD with conjugate labels does, and obtain some convergence results of GD with pseudo-labels. However, there are still many directions worth exploring. First of all, while our current analysis in the binary classification setting might be viewed first step towards systematically studying GD with pseuds-labels, analyzing GD with pseudo-labels in multi-class classification is left open in this work and could be potential direction. Second, while analyzing the population dynamics has already given us some insights about GD with pscudo labels, it might be useful to study their finite-sample dynamics. Third, theoretically understanding GD with other pseudo- llbels or combined with other domain adaptation techniques like ensembling (e.g., Wortsman et al. (2022)
or others (e.g.. Li et al. (2019); Schneider et al. (2020); Eastwood et al. (2022)) might be promising Finally, analyzing momentum methods (e.g.. Nesterov (2013); Wibisono et al. (2016); Wang & Aberrnthy (2018): Wang et al. (2022a] 20216 with pseudo-labele is another interesting direction, and one of the open questions is whether they enjoy provable guarantees of faster test-time adaptation compared to GD. Overall, we believe that the connection between optimization, domain adaptation, and machine learning under distribution shifts can be strengthened.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The authors appreciate Shikhar Jaiswal spotting a minor enror in our previous version of the proof of Proposition 1, which has been corrected in this version. The authors thank the constructive feedback from the reviewers and comments from Sachin Goyal, which helps improve the quality of this paper. The authors also thank Chi-Heng Lin for valuable discussions.
REFERENCES
Andreea Bobu, Eric Tzeng, Judy Hoffman, and Trevor Darrell. Adapting continuously shifting domains. ICLR Workshop Track, 2018.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. university press, 2004.
Cambridge
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy Liang. Unlabeled data improves adversarial robustness. NeurIPS, 2019.
Dian Chen, Dequan Wang, Trevor Darrell, and Sayna Ebrahimi. Contrastive test-time adaptation. CVPR, 2022.
Yining Chen, Colin Wei, Ananya Kumar, and Tengyu Ma. Self-training avoids using spurious features under domain shift. NeurIPS, 2020.
Ahmet Demirkaya, Jiasi Chen, and Samet Oymak. Exploring the role of loss functions in multiclass classification. 2020 54th annual conference on information sciences and systems CISS, pp. 1-5, 2020.
Cian Eastwood, lan Mason, Christopher KI Williams, and Bernhard Schölkopf. Source-free adaptation to measurement shift via bottom-up feature restoration. ICLR, 2022.
Yossi Gandelsman, Yu Sun, Xinlei Chen, and Alexei A. Efros. Test-time training with masked autoencoders. NeurlPS, 2022.
Yaroslav Ganin and Victor Lempitsky. Unsupervised domain adaptation by backpropagation. ICML, 2015.
Taesik Gong, Jongheon Jeong, Taewon Kim, Yewon Kim, Jinwoo Shin, and Sung-Ju Lee. Robust continual test-time adaptation: Instance-aware bn and prediction-balancedd memory. NeurIPS, 2022.
Sachin Goyal, Mingjie Sun, Aditi Raghunathan, and Zico Kolter. Test-Time Adaptation via Conjugate Pseudo-labels. NeurlPS, 2022.
XY Han, Vardan Papyan, and David L Donoho. Neural collapse under mse loss: Proximity and dynamics on the central path. ICIRR 2022.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness common corruptions and perturbations. arXiv preprint arXiv: 1903.1221,, 2019.
Dan Hendrycks, Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang, Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli, Mike Guo, et al. The many faces of robustness: A critical analysis of -ui--f-disttibution generalization. ICCV, 2021.
Judy Hoffman, Eric Tzeng, Taesung Park, Jun-Yan Zhu, Phillip Isola, Kate Saenko, Alexei Efros, and Trevor Darrell. Cycada: Cycle-consistent adversarial domain adaptation. In ICML., 2018.
Like Hui and Mikhail Belkin. Evaluation of neural architectures trained with square loss vs cross- entropy in classification tasks. arXiv preprint arXiv:2006.07322 2020.
Yusuke Iwasawa and Yutaka Matsuo. Test-time classifier adjustment module for model-agnostic domain generalization. NeurIPS, 2021.
10

---

Published as a conference paper at ICLR 2023
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Bal- subramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al. Wilds: A benchmark of in-the-wil wild distribution shifts. ICML, 2021.
Ananya Kumar, Tengyu Ma, and Percy Liang. Understanding Self-Training for Gradual Domain Adaptation. ICML, 2020.
Jogendra Nath Kundu, Naveen Venkat, R Venkatesh Babu, et al. Universal source-free domain adaptation. In CVPR, 2020.
Vinod K Kurmi, Venkatesh K Subramanian, and Vinay Namboodiri. Domain impression: A source data free domain adaptation method. WACV, 2021.
Rui Li, Qianfen Jiao, Wenming Cao, Hau-San Wong, and Si Wu. Model adaptation: Unsupervised domain adaptation without source data. CVPR, 2020.
Xinzhe Li, Qianru Sun, Yaoyao Liu, Qin Zhou, Shibao Zheng, Tat-Seng Chua, and Bernt Schiele.
Learning to self-train for semi-supervised few-shot classification. NeurIPS, 32, 2019.
Jian Liang, Dapeng Hu, and Jiashi Feng. Do really need access the source data? source hypothesis transfer for unsupervised domain adaptation. ICML, 2020.
Hong Liu, Jianmin Wang, and Mingsheng Long. Cycle self-training for domain adaptation. Advances in Neural Information Processing Systems, 34:22968-2299 2021a.
Yuejiang Liu, Parth Kothari, Bastien van Delft, Baptiste Gurlet, Taylor Mordan, and Alexandre Alahi. Tut+: When does self-supervised test-time training fail or thrive? NeurIPS, 2021b.
Pietro Morerio, Riccardo Volpi, Ruggero Ragonesi, and Vittorio Murino. Generative pseudo-label re- finement for unsupervised domain adaptation. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, 2020.
Chaithanya Kumar Mummadi, Robin Hutmacher, Kilian Rambach, Evgeny Levinkov, Thomas Brox, and Jan Hendrik Metzen. Test-time adaptation to distribution shift by confidence maximization and input transformation. arXiv preprint arXiv:2106. 14999, 2021.
Yurii Nesterov. Introductory lectures on convex optimization: basic course. Springer, 2013.
Shuaicheng Niu, Jiaxiang Wu, Yifan Zhang, Yaofo Chen, Shijian Zheng, Peilin Zhao, and Mingkui Tan. Efficient test-time model adaptation without forgetting. ICML,, 2022.
Xingchao Peng, Ben Usman, Neela Kaushik, Judy Hoffman, Dequan Wang, and Kate Saenko. Visda: The visual domain adaptation challenge. arXiv preprint arXiv:1710.06924, 2017.
Viraj Prabhu, Shivam Khare, Deeksha Kartik, and Judy Hoffman. Sentry: Selective entropy optimiza- tion via committce consistency for unsupervised domain adaptation. ICCV, 2021.
Evgenia Rusak, Steffen Schneider, George Pachitariu, Luisa Eck, Peter Vincent Gehler, Oliver Bringmann, Wieland Brendel, and Matthias Bethge. If your data distribution shifts, use self- learning. 2021.
Prabhu Teja and Francois Fleuret. Test time adaptation through perturbation robustness. NeurIPS 202/ Workshop on Distribution Shifts: Connecting Methods and Applications, 2021.
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adver- sarially Robust Generalization Requires More Data. NeurIPS, 2018.
Steffen Schneider, Evgenia Rusak, Luisa Eck, Oliver Bringmann, Wieland Brendel, and Matthia Bethge. Improving robustness against common corruptions by covariate shift adaptation. NeurIPS, 2020.
Charles M Stein, Estimation of the mean a multivariate normal distribution. The annals of Statistics, 1981.
11

---

Published as a conference paper at ICLR 2023
Yongyi Su, Xun Xu, and Kui Jia. Revisiting realistic test-time training: Sequential inference and adaptation by anchored clustering. In NeurlPS, 2022.
Yu Sun, Xiaolong Wang, Zhuang Liu, John Miller, Alexei Efros, and Moritz Hardt. Test-time training with self-supervision for generalization under distribution shifts. ICML, 2020.
K Thopalli, P Turaga, and JJ Thiagarajan. Geometric alignment improves fully test timeadaptation. Technical report, Lawrence Livermore National Lab., 2022.
Dequan Wang, Evan Shelhamer, Shaoteng Liu, Bruno Olshausen, and Trevor Darrell. Tent: Fully test-time adaptation by entropy minimization. ICLR, 2021a.
Jun-Kun Wang and Jacob D Abernethy. Acceleration through optimistic no-regret dynamics. Ad- vances in Neural Information Processing Systems, 31, 2018.
Jun-Kun Wang, Jacob Abemethy, and Kfir Y. Levy. No-regret dynamics in the fenchel game: A unified framework for algorithmic convex optimization. arXiv:2111.11309, 2021b.
Jun-Kun Wang, Chi-Heng Lin, and Jacob Abernethy. A modular analysis of provable acceleration via Polyak's momentum: Training wide ReLU network and deep linear network. ICML, 2021c.
Jun-Kun Wang. Chi-Heng Lin, Andre Wibisono, and Bin Hu. Provable Acceleration of Heavy Ball beyond Quadratics for class of Solyykk-Lojsiewiin Functions when the Non-Convexity is Averaged-Out. In ICML, 2022a.
Qin Wang, Olga Fink, Lue Van Gool, and Dengxin Dai. Continual test-time domain adaptation. CVPR, 2022b.
Andre Wibisono, Ashia C Wilson, and Michael I Jordan. A variational perspective on accelerated methods in optimization. Proceedings of the National Academy of Sciences, 113(47):73311-7338 2016.
Mitchell Wortsman, Gabriel Ilharco, Samir Ya Gadre, Rebecca Roelofs, Raphael Gontijo-Lopes, Ari S Morcos, Hongseok Namkoong, Ali Farhadi, Yair Carmon, Simon Korbllihh, et al. Model soups: averaging weights of multiple fine-tuned models improves accuracy without increasing inference time. In International Conference on Machine Learning. PMLR, 2022.
Sang Michael Xie, Ananya Kumar, Robbie Jones, Fereshte Khani, Tengyu Ma, and Percy Liang, In- n-out: Pre-training and self teff-training using auxiliary information for out-of-distribution robustness. ICLR, 2021.
Marvin Zhang, Sergey Levine, and Chelsea Finn. Memo: Test time robustness via adaptation and augmentation. arXiv preprint arXiv:2110.09506, 2021a.
Marvin Zhang, Henrik Marklund, Nikita Dhawan, Abhishek Gupta, Sergey Levine, and Chelsea Finn. Adaptive risk minimization: Learning adapt domain shift. NeurlPS, 2021b.
Yang Zou, Zhiding Yu, Xiaofeng Liu, BVK Kumar, and Jinsong Wang. Confidence regularized self-training. ICCV, 2019.
A DERIVATIONS OF CONJUGATE LABELS AND THE ASSOCIATED SELF-TRAINING LOSSES ON TIBLE
1. (Square loss): Square loss f(w; (Ir, v)) == ( w x)² is in the form of (2). where f(-) = =.)²
R + Substituting f(-) = (-)² and h(w) = w x into (4) and (5) we get
conj (x) = w a, and geoni (w;;)) 2 5( x=) Vw
(28)
On the other hand, let y sign(w) (w) z). we have
hard (x) = sign(w" x), and ghard (w; x) Vou
1
(sign (w 2)) - x)²
(29)
12

---

Published as a conference paper at ICLR 2023
2. (Logistic loss): Recall that logistic regression predicts P(g 1)
exp(" at) I+exp(w 2) and P(ù = 0)
1 P 1), and the loss function is:
plogit (w: (I. 9)) (og = 1)) (1 1) log (P(y =)))
(30)
== log (1 + exp(w z)) jf(w" z).
where U = 10, Lety = 2ÿ- 1E (-1,1}. Then, substituting ý = + //2 back into 30 and using the equation cosh(2) oxp(=) (op(() for any R, we obtain equivalent objective:
plogit (w; (s, v)) = log(1 + exp( (w: T x)) 5(w0 x:)
log(1 + exp(w x))
y
(w
x)
2
w Ø
w
w
(31)
log
exp
+ exp
2
2
W T r ))
w
log
cosh
log 2.
2
Now by renaming "r 2
w. we get
plorit (w: (z, v)) log (cosh (wTz) yw x C,
(32)
where the last term is constant and can be dropped without affecting the training.
Observe that 32 is in the form where f(-) = log (cosh (-)) and (x) = w x. Using
and (5. get
con) (x) tanh (w x),, and (wr; x:) = log (cosh (w x)) tanh (w xx) w To. (33)
On the other hand, let y + sign(w (w x) in 32). we have
hard (x) = sii)=igg(uu (w x), and ghard (w: x) = log (cosh (w (w]x)) - Iw Tul.
(34)
3. (Exponential loss): Recall that exponential loss is (w (x, v)) = exp( yh (x))
exp(-yw v)., where (+1, -1}, which can be rewritten as
goxp (w:; (x. v)) (exp(w x) exp(- -w x) " (exp(wTax -)xx)))-wTap exp(-wTxx x1))
cosh(ut (w xx) y sinh(w" T r).
(35)
The above function is in an expanded conjugate form (Goyal et al. 2022 :
f())(x)) (z)h
where ʃ(.) cosh(-)) g(.) = sinh(-) (.), and (x,(x) = w x. Let h. + arg min, [(h) - (h) Then, h. satisfies (h.)) Vg(h.)u yy- Goyal et al. (2022) define the conjugate label con (x)) via the equality
(hh (x)) = (g(h (x)
for this case. Therefore, we have yo (x: tanh(w' Tx)) 2²). By substituting y y (ar) in 35 get the self-training loss function using the conjugate label: (con = sech(w" x). To conclude, have:
you comj (x) = tanh(u' x), and (omn)(w; = sech(w" Tx).
(36)
On the other hand, let y sign(w T 2)) in (wr (I, v)) = exp(-yhw we have hard
y (x:) sw x)), (x)),
and phard (w;,x) exp(-lw xl). Tx]).
(37)
13

---

Published as a conference paper at ICLR 2023
B SETUP OF THE SIMULATION IN FIGURE 1 AND FIGURE
We first specify the mean and covariance uss, PT; Eg III. Ey oT Ia as follows, where the subseript S stands for the source domain, and the subscript T is the target domain.
Below we describe how to reproduce Figure 1 and Figure 4
We set As e₁ and then set set LT = 0.6567, and the remaining elements of μTT is set randomly from a normal distribution and were normalized to ensure that jrr is a unit norm vector. Then, we set
_TTS oT = 0.6567 /0.14............ This way we have drilus | = 0.8416 so that +b
@T = & (0.8416) =
0.2, i.e., the initial model wi = wi has 20% expected 0-1 loss the new domain T. Also, the best minimal error in the new domain T is +b
[[|r]] o 0..56670.8811
0.1.
or
In the simulation result depicted in Figure 1 sample of (æ = 14) arrives when the test time t is an odd number and a sample (æ = -)) arrives when the test time is an even number. Note that the algorithms do not know the labels.
we consider the setting of noisy data, i.e., 2, R is sampled 2, N(UT, La) instead of yPT. We search the step size n over the 10-0,0233
In the simulation result depicted Figure 4
grid {10 5 x 10 3 10 2,5 5 x 2,10,,,115 x 10 100,, x 100 10', 5 x 10', _10} for each GD + hard + exp, GD conj + exp, GD hard logistic, or GD conj + logistic, and report the best result of each one.
C PROOF OF LEMMA
I
Lemma properties
The following self-training loss functions goell (w:: = (((TT)) satisfy the set of More precisely, we have
1. hard exp: vb(u) exp(-lul) satisfies with (T. = 1, Omin = 0).
2. hard + logistic: (b()) = log (cosh (u)) |u] satisfies with (I. -I= 2, Omin = 0).
3. conj + exp: (u) = (u) satisfies with (L = 1, amin 0.75).
4. conj + logistic: vb(u) = log (cosh (u)) tanh (u) u satisfies with (L = 2, amin = 0.5)..
Proof.
For hard + exp, we have vbu) exp(-lul), ('()) sign(v) exp(- and v'(()) exp(-/ul) + (u)).
It is evident that vuu)= exp(-lul) is an even function and that it is differentiable every- where except at the origin. We also have - ((() < and (v)(u) 2 cxp(-u) for all u 2 0. We conclude that (u)) exp(-lu) satisfies with parameter (L 1, Omin 0).
For hard + logistic, we have (b) log (cosh (u)) [u]. (u) tanh (u) sign(w). and v²(u) = sech (u) (u).
It is evident that (u)) = log (cosh (u) |u| is an even function and that it is differentiable everywhere except at the origin. We also have 15((w)) < 1. Furthermore,
tanh(u) - exp(u) - exp(-u)
2 2exp(-10 w) exp(u) + exp( -u)
exp(u) + exp(-u)
2exp(-u) Hence, for u > 0, -0'(n) = tanh(u) = exp(w)texp(-u)
2 exp(-2u)) since
2exp(-u)
2 exp( -u) + 2exp(-u) 2 exp(-w) exp((3ux)
exp(u) + exp( -u) and the later is evident for u 2 0.
We conclude that (²) log (cosh (u)) |u| satisfies with parameter (T. --=22 2, Omnin 0).
14

---

Published as a conference paper at ICLR 2023
For conj + exp, have (b))) sech(u), (²()) tanh(u))sch(u)) and (l
-sech(u)² + tanh tanh"(u)sechla (u)sech(u).
It is evident that eb(u) = sech(u) is an even function and that it is differentiable everywhere.
We also have (u) - 1, as ttan(u)] - 1 and soch(u) I 1.
Note that (w) tanh tanh(u)sscc((a)
2(exp(u) exp((aa)) Moreover, (exp(x)+exp(=a))=
2(exp(u) exp(-u)) 2 exp(-u) = 2(exp(2u) 1) 2 exp(2u) + 2 e 22) (exp(u) + exp(-u))2
= exp(2u) exp(-2u) + 4,
(38)
which holds when v 2 0.75. That is, (v)(u) 2 exp(-u) for all 2 0.75.
We conclude that (b()) sech(u) satisfies with parameter (L 1, Qmin 0.75).
For conj + logistic, we have (u) log (cosh (u)) tanh (u) v -sech?(u)u and v² (u) sech(u)² + 2u tanh (ssccs(hh))
It is evident that (h)) log (cosh (u)) tanh (u) a is an even function and that it is
differentiable everywhere. We also have 1 (u) (exp(=)+oxp(-w))) ())) S 1.
4u
Note that (v)( = (u)u (exp(u)+ uz) Moreover,
4u (exp(u) exp(-u))2 exp(-2ul 4u 2 1 + 2 eexp( 22) + exp((-41) (39)
which holds when u 2 0.5. That is, (v) 2 exp(-2u) for all 0.5.
We conclude that (u)) log (cosh (u)) tanh (u) u satisfies with parameter
[L 2, amin 0.5).
15


Reviews:
[{"review_id": "veX4x_xx5G", "reviewer": "Reviewer_w2JR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "summary_of_the_review": "Please see Q1 and Q2.", "strength_and_weaknesses": "Strength：\n- The paper is well-organized and clearly written, which is easy to follow.\n- The theoretical work of this paper is sufficient, which improves the value of the paper.\n- The paper provides insights into when and why GD with hard labels or conjugate labels works in test-time adaptation.\n\nWeakness：\n- 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?\n- 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\nsource model is better than the random guessing in the new domain.”, how to illustrate the special case of right angle when $\\epsilon=1$？\n- 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？\n\n[A] Sachin Goyal, Mingjie Sun, Aditi Raghunathan, and Zico Kolter. Test-Time Adaptation via Conjugate Pseudo-labels. NeurIPS, 2022.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "jzM1qq3xV-", "reviewer": "Reviewer_VqqL", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "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.\nAlthough 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.\nThe 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.\n\nThe 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.\n\nFrom 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "FU8dxGpuIH", "reviewer": "Reviewer_4HLp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. \n\n[a] Test-Time Adaptation via Conjugate Pseudo-labels. NeurIPS, 2022.", "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.  ", "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.\n2. 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?\n3. 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?\n4. 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.\n5. How to derive Equation 24 is not very clear.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "BjnGZGwFCqy", "reviewer": "Reviewer_3i1a", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "**Summary**\nThis 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. \n", "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. ", "strength_and_weaknesses": "**Strength**\n\n**[S1]** This paper is generally well written and easy to follow. \n\n**[S2]** Conjugated pseudo label is timely topic in test-time adaptation. Besides, pseudo-label itself is general techniques and worth investigation. \n\n---\n**Weakness**\n\n**[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. \n\nOf 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. \n\n\n**[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. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster