S Espinosa

J F Silva
email: josilva@ing.uchile.cl

2 X n : n (x n 1 ) = 0}) , Q n (A( n ))

Finite-Length Bounds on Hypothesis Testing Subject to Vanishing Type I Error Restrictions

Sebastian Espinosa, Jorge F. Silva ⇤ , and Pablo Piantanida, Abstract-A central problem in Binary Hypothesis Testing (BHT) is to determine the optimal tradeoff between the Type I error (referred to as false alarm) and Type II (referred to as miss) error. In this context, the exponential rate of convergence of the optimal miss error probability -as the sample size tends to infinity -given some (positive) restrictions on the false alarm probabilities is a fundamental question to address in theory. Considering the more realistic context of a BHT with a finite number of observations, this paper presents a new non-asymptotic result for the scenario with monotonic (sub-exponential decreasing) restriction on the Type I error probability, which extends the result presented by Strassen in 2009. Building on the use of concentration inequalities, we offer new upper and lower bounds to the optimal Type II error probability for the case of finite observations. Finally, the derived bounds are evaluated and interpreted numerically (as a function of the number samples) for some vanishing Type I error restrictions.

Index Terms-Hypothesis testing, performance bounds, finitelength analysis, error exponent, concentration inequalities.

I. INTRODUCTION Binary Hypothesis

Testing (BHT) is a common problem in statistics and it has been richly used as a method to statistical signal detection [START_REF] Chamberland | Wireless sensors in distributed detection applications[END_REF], [START_REF] Li | Detection, classification, and tracking of targets[END_REF]. In particular, the celebrated Neyman-Pearson lemma provides the optimal detection scheme for this testing task [START_REF] Tenney | Detection with distributed sensors[END_REF]. On the specifics, let us consider the classical n-length BHT setting given by ⇢ H 0 : X n 1 ⇠ P n , H 1 : X n 1 ⇠ Q n , where P, Q 2 P(X) with D(P kQ) > 0. In this work, we restrict our attention to the case of a finite-alphabet X, where P(X) denotes the family of probabilities on X. A decision rule n of length n is a function n : X n ! ⇥ , {0, 1}, from which two types of errors are induced [START_REF] Kullback | On information and sufficiency[END_REF]:

with decision region A( n ) , {x n 1 2 X n : n (x n 1 ) = 0}. For a given sequence (✏ n ) n of non-negative values such that lim n!1
✏ n = 0, we study the solution to:

n (✏ n ) ⌘ min n 2 n {P 1 ( n ) : s.t. P 0 ( n )  ✏ n }, 8n 1, (1)
where n ⌘ { n : X n ! ⇥} denotes the class of n-length detectors. Importantly, ( n (✏ n )) n 1 represents the optimum Type II error sequence that satisfies a sequence of fixed Type I error constraints.

The Neyman-Pearson lemma [START_REF] Neyman | On the problem of the most efficient tests of statistical hypotheses[END_REF] offers the optimal tradeoff between the two type of errors 1 . In this context, the determination of the (exponential) rate of convergence of the Type II error, which is known as the error exponent, has been a central problem in HT's analysis. Indeed, the error exponent is seen as an indicator of the complexity of the decision task (function of P 0 , P 1 and (✏ n ) n ) and has found numerous applications [START_REF] Marano | Algorithm and fundamental limits for unlabeled detection using types[END_REF], [START_REF] Wang | Signal amplitude estimation and detection from unlabeled binary quantized samples[END_REF]. For the important case when ✏ n = ✏ > 0 for all n, the celebrated Stein's lemma establishes that the error exponent of the Type II error is given by the KL divergence D(P kQ) ⌘ P x2X P (x) log P (x) Q(x) [START_REF] Kullback | On information and sufficiency[END_REF], [START_REF] Cover | Elements of information theory[END_REF].

Lemma 1 (Stein's lemma [START_REF] Chernoff | A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations[END_REF], [START_REF] Cover | Elements of information theory[END_REF]). For any fixed ✏ 2 (0, 1), lim n!1

1
n log( n (✏)) = D(P kQ). Importantly, the error exponent limit in Lemma 1 is independent of ✏ > 0. However, this limit changes when we impose a setting with a monotonic decreasing Type I error restrictions. In particular, Han et al. [START_REF] Han | Exponential-type error probabilities for multiterminal hypothesis testing[END_REF] studied the case when the Type I error sequence has an exponential decreasing behaviour. Nagakawa et al. [START_REF] Nakagawa | On the converse theorem in statistical hypothesis testing[END_REF] extended this analysis for a family of decreasing sequence of Type I error restrictions: Lemma 2. [START_REF] Nakagawa | On the converse theorem in statistical hypothesis testing[END_REF]Nakagawa] Let us assume that ✏ n  e rn for some r 2 (0, D(P kQ)), then lim n!1

1 n log( n (✏ n )) = D(P t ⇤ kQ), where P t ⇤ (x) ⌘ C t ⇤ P (x) 1 t ⇤ Q(x) t ⇤ 8x 2 X, and t ⇤
is the solution of D(P t ⇤ kP ) = r.

A direct implication of Lemma 2 is the following result:

Corollary 1. [START_REF] Nakagawa | On the converse theorem in statistical hypothesis testing[END_REF] Let us assume that (1/✏ n ) n is o(e rn ) for any r > 0, then lim n!1

1 n log( n (✏ n )) = D(P kQ). Importantly, Corollary 1 shows that the same error exponent of the Stein's lemma is obtained for these stringent family of problems -where (✏ n ) n tends to zero at a sub-exponential rate. In contrast, when the Type I error restriction tends to zero exponentially fast (Lemma 2), the error exponent is strictly smaller than D(P kQ).

A. Finite-Length Context and Contribution

In many practical problems, the statistician has access only to a finite number of observations. Consequently, it is critical to obtain non-asymptotic bounds for the probability of error n (✏ n ) for a finite n. Concerning the non-asymptotic analysis of this problem, the following result was derived by Strassen for the specific regime when ✏ n = ✏ > 0 for all n 1 [START_REF] Strassen | Asymptotic estimates in Shannon's information theory[END_REF]. Lemma 3. [START_REF] Strassen | Asymptotic estimates in Shannon's information theory[END_REF] Let us consider ✏ 2 (0, 1), then eventually with n, it follows that log( n (✏)) n = D(P kQ) + q

V (P kQ) n 1 (✏) + log n 2n + O 1 n , where V (P kQ) ⌘ X x2X P ({x})  log ✓ P ({x}) Q({x}) ◆ D(P kQ) 2 .
Lemma 3 shows that D(P kQ)

1 n log( n (✏)) is O ⇣ 1 p n ⌘
, which expresses the velocity of convergence of 1 n log( n (✏)) to its limit D(P kQ). Given the practical importance of this type of finite length results, it is very relevant to derive new results that extend Lemma 3 to our general problem in (1), as a function of P , Q, (✏ n ) n and n. In addition, it is critical that these bounds can be evaluated for its practical use. This last aspect is not achieved in Lemma 3, which from that perspective is an asymptotic (convergence) result.

The main contribution of this paper goes in this direction, where we derive new upper and lower bounds for the discrepancy between 1 n log( n (✏ n )) and its information limit D(P kQ) for any finite n 1 when (✏ n ) n tends to zero at a sub-exponential rate. These expressions can be evaluated and interpreted numerically in any context where we know the models (P and Q) and the parameters of the problem (✏ n and n). In addition, these new bounds stipulate the velocity at which the error exponent is achieved as the sample size tends to infinity. From this, we could assess how realistic the information limits (asymptotic results) are in practice when facing a problem with a finite number of observations. To conclude our analysis, we numerically compute and evaluate the expressions obtained by our result to show the derived bounds' tightness for some specific scenarios.

B. Related Work

In a Bayesian setting, Sason [START_REF] Sason | Moderate deviations analysis of binary hypothesis testing[END_REF] obtained an upper bound to the optimal Bayesian probability of error (non-asymptotic) by bounding the Type I and Type II errors simultaneously in such a way that they both decay to zero sub-exponentially with n. It is worth to mention that this work differs from the current setting in the sense that we are interested in bounding the discrepancy between 1 n log( n (✏ n )) and its information limit and how this analysis depends on the vanishing Type I error restrictions. In addition, we are interested in the velocity of convergence of 1 n log( n (✏ n )) to its information limit and the impact of considering stringent restriction on Type I errors (✏ n ) n . Complementing this paper, [START_REF] Espinosa | New results on testing against independence with rate-limited constraints[END_REF] studies a distributed (two-terminal) version of the BHT problem subject to communication (rates) constraints. Our results here do not derive from [START_REF] Espinosa | New results on testing against independence with rate-limited constraints[END_REF] since the setups are very different from each other, and different tools are used to address them. Finally, a similar analysis of the Type I error has been addressed by Bahadur [START_REF] Nikitin | Asymptotic efficiency of nonparametric tests[END_REF]. In contrast to this work's focus, this analysis considers a fixed restriction on the power of a test (1 Type II error) to determine the exponential rate of convergence of their sizes (Type I error) as n tends to infinity.

C. Notations and Organization

(b n ) n being o(a n ) indicates that lim sup n!1 (b n /a n ) = 0 and (b n ) n being O(a n ) indicates that lim sup n!1 |b n /a n |< 1. We say that (f (n)) n ⇡ (g(n)) n if there exists a constant C > 0 such that f (n) = Cg(n) eventually in n.
The rest of the paper is organized as follows: Section II presents the main result of this work. Numerical analysis and discussions are presented in Section III. The proof of is in Sect. IV.

II. MAIN RESULT

The main result of this letter extends Lemma 3 offering new non-asymptotic bounds for n (✏ n ) in (1) under subexponential Type I error restrictions. In particular, the next result provides upper and lower bounds for the discrepancy between 1 n log( n (✏ n )) and D(P kQ).

Theorem 1. Let us assume that P ⌧ Q and that (1/✏ n ) n is o(e rn ) for any r > 0. Then, eventually in n, it follows that:

1 n log( n (✏ n )) D(P kQ) C X (P, Q) r 2 ln(1/✏ n ) n 1 n log( n (✏ n ))  D(P kQ) + log ✓ 1 1 ✏ n n ◆ n + n
where C X (P, Q) ⌘ sup 1: This result establishes a non-asymptotic rate of convergence for the Type II error when we impose a vanishing condition on (✏ n ) n that is sub-exponential. Interestingly, the bounds for the discrepancy 1 n log( n (✏ n )) depend explicitly on the sequence (✏ n ) n .

2:

It is worth noting that the dependency on (✏ n ) n observed in our result is non-observed in the asymptotic limit in Corollary 1, which is D(P kQ) as long as (1/✏ n ) n is sub-exponential.

3: Adding on the previous point, the fact that the asymptotic error exponent is invariant from the simpler fixed Type I setup (in Lemma 1) to the more restrictive sub-exponential Type I error decay setting (in Corollary 1), it is however manifested in our non-asymptotic result in term of the rate of convergence to the limit D(P kQ). In particular, there is a concrete penalty

4:

The proof of the Theorem 1 has two parts: the constructive and unfeasibility arguments. Both arguments are constructed from concentration inequalities using the i.i.d. structure of the observations. For the constructive argument, we apply the bounded difference inequality [START_REF] Boucheron | Concentration inequalities: A nonasymptotic theory of independence[END_REF]. On the unfeasibility argument, we use (concentration) results from typical sequences [START_REF] Cover | Elements of information theory[END_REF] to construct a lower bound on the minimum probability of Type II error.

5:

If we impose a fixed value of ✏ n = ✏ 2 (0, 1), our result recovers the rate of convergence for the Type II error given by Lemma 3. However, we obtained explicit bounds.

III. PRACTICAL IMPLICATIONS OF THEOREM 1

In this section, we show how Theorem 1 may be adopted by a statistician to obtain bounds on n (✏ n ) when n is finite. The resulting bounds provide an interval of feasibility for n (✏ n ):

UB(✏ n ) ⌘ exp h n ⇣ D(P kQ) r 2 ln(1/✏ n ) n C X (P, Q) ⌘i , LB(✏ n ) ⌘ exp h n ⇣ D(P kQ) 1 n log (1 ✏ n n (✏ n ) ⌘ + n (✏ n ))
i .

The length of [LB(✏ n ), UB(✏ n )] indicates the precision of the result and, at the same time, the interval [LB(✏ n ), UB(✏ n )] can be used to measure how close n (✏ n ) is to e nD(P kQ) . Table I presents the length of [LB(✏ n ), UB(✏ n )] for three regimes of: ✏ n 2 {n 1 , n 0.1 , 1/log(n)}, and two models P , Q where D(P kQ) = 1 with |X|= 15. First, we observe that the length of [LB(✏ n ), UB(✏ n )] vanishes exponentially fast with the sample size. From this exponential decay, we observe that the centered value predicted by Theorem 1, i.e., the exponential behavior exp( nD(P kQ)), is a good approximation for n (✏ n ) provided that n is sufficiently large. This supports the idea that exp( nD(P kQ)) is a useful proxy for n (✏ n ) provided that a Critical Sample Size (CSS) is achieved (more details on this below). Table I also shows that the result's precision is affected by the velocity of convergence of the Type I error restriction (✏ n ) n , which is consistent with the statement and the analysis of our main result. In particular, for a faster speed of convergence of (✏ n ) n to zero (i.e., a stringer problem), the gap between the bounds is more prominent, which means that the bounds of Theorem 1 are expected to be less informative about n (✏ n ).

Regarding the implications of the above bounds to measure the gap between n (✏ n ) and e nD(P kQ) , we address the following question: given an arbitrary value of > 0 of the form 10 k with k 2 {1, . . . , 8}, and for two arbitrary models P and Q, we want to predict from Theorem 1 the minimum number of samples required to guarantee that n (✏ n ) 2 (e nD(P kQ) , e nD(P kQ) + ). The exponential decay of the length of [LB(✏ n ), UB(✏ n )], observed in Table I, implies that this should happen eventually with n very quickly. Indeed, we can derive an upper bound for this critical number of samples (CSS) from the expressions we have for LB(✏ n ) and UB(✏ n ). 2 Figures 1 and2 present the predicted CSS versus = 10 k for different scenarios of P , Q (in terms of D(P kQ)) and (✏ n ) n . We consider two scenarios for P and Q (low divergence D(P kQ) = 0.5 and high divergence D(P kQ) = 2.5) and we 2 The predicted CSS is the first n 1 such that max{UB(✏n) e nD(P kQ) , e nD(P kQ) LB(✏n)}  , which is finite for any > 0. explore (✏ n ) n 2 {n 1 , n 0.1 , 1/log(n), 0.1}. Figures 1 and2 show that even for really small precision = 10 8 the point at which n (✏ n ) can be well approximated by e nD(P kQ) requires at most 16 samples and 60 samples for high and low divergence cases, respectively, and the majority of (✏ n ) n . The dependency of these curves on the magnitude of D(P kQ) and (✏ n ) n is clearly expressed in these findings, which is consistent with our previous analyses.

Finally, to evaluate the tightness of our predictions, we simulate i.i.d. samples according to P and Q from which a precise empirical estimation of n (✏ n ) is derived. In particular, given P , Q and (✏ n ) n , we obtained empirical estimations of the error probabilities (Type I and Type II) from which we estimate n (✏ n ). For this purpose, 2.5 • 10 6 realizations of P and Q were used to have good estimations of these probabilities. Using the estimated values of n (✏ n ), we obtain the point where n (✏ n ) 2 (e nD (P kQ) , e nD(P kQ) + ) directly. values (the dashed lines) of the CSS. Consistent with our result's nature, our prediction of the CSS is more conservative than the true CSS estimated from simulations. Importantly, this discrepancy is not significant overall, expressing that our bounds are useful for this analysis and can be adopted in cases where it is impractical to estimate n (✏ n ) from data. Indeed, in this analysis, we face this issue, and it is very difficult to obtain accurate estimates of n (✏ n ) for high divergence regimes. Notice that n (✏ n ) is of order: O(e nD(P kQ) ) for which around e nD(P kQ) simulations (i.e., i.i.d. samples from P and Q) are needed. This becomes impractical even for n less than 30 when D(P kQ) is relatively large.

IV. PROOF OF THEOREM 1

We divide the proof of Theorem 1 in two parts.

1) Lower Bound Analysis: Under the assumption of Theorem 1, let us verify that

D(P kQ) ✓ 1 n log n (✏ n ) ◆  r 2 ln(1/✏ n ) n C X (P, Q).
Let us consider the corresponding optimal decision regions from the Neyman-Pearson Lemma parameterized in the following way: 8t > 0,

B n,t = ⇢ x n 1 2 X n : P n ({x n 1 }) Q n ({x n 1 }) > e nt . (2)
Considering the induced test n,t (•) : X n 7 ! {0, 1} such that 1 n,t ({0}) = B n,t . The Type I error probability is given by P n (B c n,t ). An upper bound for the Type II follows as:

Q n (B n,t )  e nt . (3)
Then, for any finite n > 0 and ✏ n > 0, finding an achievable Type II error exponent from this construction (and the bound in Eq.( 3)) reduces to solve the following problem:

t ⇤ n (✏ n ) , sup t {t : P n (B c n,t )  ✏ n }. (4)
It will be convenient to re-parameterize t with respect to the value D(P kQ). More precisely, let us define t , D(P kQ) ,

for any > 0. Then using the bounded difference inequality [START_REF] Boucheron | Concentration inequalities: A nonasymptotic theory of independence[END_REF], we obtain

P n B c n,t = P n x n 1 2 X n : D(P kQ) D(P kQ) !  exp ✓ n 2 2C X (P, Q) 2 ◆ , (5)
where D(P kQ) ,

1 n P n i=1 log ⇣ P ({xi}) Q({xi})
⌘ is the empirical divergence. Finally, from Eq. ( 4) a lower bound for t ⇤ n (✏ n ) can be determined from Eq. ( 5) by letting ˜ n (✏ n ) to be the solution of the following equality:

exp n ˜ n (✏ n ) 2 2C X (P, Q) 2 ! = ✏ n . (6)
Consequently, we have that t ⇤ n (✏ n ) t ˜ n (✏n) , D(P kQ)

r 2 log(1/✏ n ) n C X (P, Q). (7)
Finally, replacing the bound of ( 7) in ( 3) and taking logarithm we have that:

D(P kQ) ✓ 1 n log( n (✏ n )) ◆  r 2 ln(1/✏ n ) n C X (P, Q), (8)
which concludes this part.

Q n (B n ) (1 ✏ n )2 n(D(P kQ)+ ) . (10)
By construction, it is clear that there exists > 0 such that A c n, operates at Type I error ✏ n . In fact, we consider ⇤ n , sup{ :

P n (A c n, )  ✏ n }. (11)
Using the bounded difference inequality [START_REF] Boucheron | Concentration inequalities: A nonasymptotic theory of independence[END_REF], we get that

P n A c n, = P n x n 1 2 X n : D(P kQ) D(P kQ) !  exp ✓ n 2 2C X (P, Q) 2 ◆ . ( 12
)
Using the same argument from the lower bound analysis, we obtain a lower bound for ⇤ n given by

⇤ n n , r 2 log(1/✏ n ) n C X (P, Q). ( 13
)
3 Meaning that n(x n 1 ) = 0 if x n 1 2 Bn.

Finally, replacing n in Eq. ( 10) and taking logarithm, we have that for any set B n satisfying the assumptions of Lemma 4:

1 n log(Q n (B n ))  D(P kQ) + log ⇣ 1 1 ✏n n ⌘ n + n . (14)
Therefore, we can choose the optimum set which implies that

1 n log( n (✏ n ))  D(P kQ) + log ⇣ 1 1 ✏n n ⌘ n + n . ( 15
)
This concludes the proof.

  and Discussion of Theorem 1

  n )) on the velocity of convergence to zero of the discrepancy ( 1 n log n (✏ n ) D(P kQ)) in our result compared with what is obtained in Lemma 3.

Fig. 1 .

 1 Fig. 1. Critical number of samples (CSS) predicted by Th. 1 across different values of = 10 k . High divergence case with D(P kQ) = 2.5 and C X (P, Q) = 2.04.

Fig. 2 .

 2 Fig. 2. CSS predicted by Th. 1 across different values of = 10 k . Low divergence case with D(P kQ) = 0.5 and C X (P, Q) = 1.03. The dashed lines show an estimation of the exact CSS obtained from n(✏n) directly.

Figure 2

 2 Figure2contrasts our predictions and the true (estimated) values (the dashed lines) of the CSS. Consistent with our result's nature, our prediction of the CSS is more conservative than the true CSS estimated from simulations. Importantly, this discrepancy is not significant overall, expressing that our bounds are useful for this analysis and can be adopted in cases where it is impractical to estimate n (✏ n ) from data. Indeed, in this analysis, we face this issue, and it is very difficult to obtain accurate estimates of n (✏ n ) for high divergence regimes. Notice that n (✏ n ) is of order: O(e nD(P kQ) ) for which around e nD(P kQ) simulations (i.e., i.i.d. samples from P and Q) are needed. This becomes impractical even for n less than 30 when D(P kQ) is relatively large.

2 )

 2 Upper Bound Analysis: Let us consider the set for any > 0. We have the following result: Lemma 4. [10, Sect 11.8] For any set B n ✓ X n and its induced test n 3 such that operates at Type I error ✏ n (i.e. P n (B c n )  ✏ n ), then

  FUNCTION OF ✏n AND n FOR THE CASE WHEN D(P kQ) = 1.

					Number of observations n
	✏n	50	150	250	350	450	550	650	750
	1/log(n)	2.3587e-10	3.3962e-45	1.0595e-83	9.4592e-124	1.0229e-164	2.6103e-206	2.2862e-248	8.6970e-291
	1/n 0.1	7.8229e-17	8.1724e-57	9.1096e-99	1.3994e-141	6.4863e-185	1.3117e-228	1.4272e-272	9.5440e-317
	1/n	0.5571	3.7757e-25	7.4403e-56	2.7823e-89	2.3527e-124	1.4443e-160	1.2489e-197	2.3163e-235
					TABLE I
		MAGNITUDE OF UB(✏n) LB(✏n)

See[START_REF] Kay | A new proof of the neyman-pearson theorem using the eef and the vindication of sir r. fisher[END_REF] for a new proof based on properties of exponential density function families.

This work of S. Espinosa was funded by the National Agency for Research and Development (ANID)/ScholarshipProgram/DoctoradoNacional/2018-21180693.

This project has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 792464.

This article has been accepted for publication by IEEE Signal Processing Letters 2021 [1].


Malika Boudiaf
email: malik.boudiaf.1@etsmtl.net

Imtiaz Masud Ziko

Jérôme Rony

Dolz Jose

Pablo Piantanida

Ismail Ben Ayed

⇤ Éts

Montreal Ziko

Imtiaz Masud

Éts Montreal

Jose Dolz

Ismail Ben

Ayed Éts Montreal

Transductive Information Maximization For Few-Shot Learning

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Deep learning models have achieved unprecedented success, approaching human-level performances when trained on large-scale labeled data. However, the generalization of such models might be seriously challenged when dealing with new (unseen) classes, with only a few labeled instances per class. Humans, however, can learn new tasks rapidly from a handful of instances, by leveraging context and prior knowledge. The few-shot learning (FSL) paradigm [START_REF] Miller | Learning from one example through shared densities on transforms[END_REF][START_REF] Fei-Fei | One-shot learning of object categories[END_REF][START_REF] Vinyals | Matching networks for one shot learning[END_REF] attempts to bridge this gap, and has recently attracted substantial research interest, with a large body of very recent works, e.g., [START_REF] Hou | Cross attention network for few-shot classification[END_REF][START_REF] Guneet S Dhillon | A baseline for few-shot image classification[END_REF][START_REF] Rusu | Meta-learning with latent embedding optimization[END_REF][START_REF] Ye | Learning embedding adaptation for few-shot learning[END_REF][START_REF] Liu | Learning to propagate labels: Transductive propagation network for few-shot learning[END_REF][START_REF] Chen | A closer look at few-shot classification[END_REF][START_REF] Qiao | Transductive episodic-wise adaptive metric for few-shot learning[END_REF][START_REF] Kim | Edge-labeling graph neural network for few-shot learning[END_REF][START_REF] Sung | Learning to compare: Relation network for few-shot learning[END_REF][START_REF] Wertheimer | Few-shot learning with localization in realistic settings[END_REF][START_REF] Gidaris | Boosting few-shot visual learning with self-supervision[END_REF][START_REF] Snell | Prototypical networks for few-shot learning[END_REF][START_REF] Finn | Model-agnostic meta-learning for fast adaptation of deep networks[END_REF], among many others. In the few-shot setting, a model is first trained on labeled data with base classes. Then, model generalization is evaluated on few-shot tasks, composed of unlabeled samples from novel classes unseen during training (the query set), assuming only one or a few labeled samples (the support set) are given per novel class.

Most of the existing approaches within the FSL framework are based on the "learning to learn" paradigm or meta-learning [START_REF] Finn | Model-agnostic meta-learning for fast adaptation of deep networks[END_REF][START_REF] Snell | Prototypical networks for few-shot learning[END_REF][START_REF] Vinyals | Matching networks for one shot learning[END_REF][START_REF] Sung | Learning to compare: Relation network for few-shot learning[END_REF][START_REF] Lee | Meta-learning with differentiable convex optimization[END_REF], where the training set is viewed as a series of balanced tasks (or episodes), so as to simulate test-time scenario. Popular works include prototypical networks [START_REF] Snell | Prototypical networks for few-shot learning[END_REF], which describes each class with an embedding prototype and maximizes the log-probability of query samples via episodic training; matching network [START_REF] Vinyals | Matching networks for one shot learning[END_REF], which represents query predictions as linear combinations of support labels and employs episodic training along with memory architectures; MAML [START_REF] Finn | Model-agnostic meta-learning for fast adaptation of deep networks[END_REF], a meta-learner, which trains a model to make it "easy" to fine-tune; and the LSTM meta-learner in [START_REF] Ravi | Optimization as a model for few-shot learning[END_REF], which suggests optimization as a model for few-shot learning. A large body of meta-learning works followed-up lately, to only cite a few [START_REF] Rusu | Meta-learning with latent embedding optimization[END_REF][START_REF] Oreshkin | Tadam: Task dependent adaptive metric for improved few-shot learning[END_REF][START_REF] Mishra | simple neural attentive meta-learner[END_REF][START_REF] Sung | Learning to compare: Relation network for few-shot learning[END_REF][START_REF] Ye | Learning embedding adaptation for few-shot learning[END_REF].

Related work

Transductive inference: In a recent line of work, transductive inference has emerged as an appealing approach to tackling few-shot tasks [START_REF] Guneet S Dhillon | A baseline for few-shot image classification[END_REF][START_REF] Hou | Cross attention network for few-shot classification[END_REF][START_REF] Kim | Edge-labeling graph neural network for few-shot learning[END_REF][START_REF] Liu | Learning to propagate labels: Transductive propagation network for few-shot learning[END_REF][START_REF] Qiao | Transductive episodic-wise adaptive metric for few-shot learning[END_REF][START_REF] Nichol | On first-order meta-learning algorithms[END_REF][START_REF] Liu | Prototype rectification for few-shot learning[END_REF][START_REF] Imtiaz | Laplacian regularized few-shot learning[END_REF], showing performance improvements over inductive inference. In the transductive setting 3 , the model classifies the unlabeled query examples of a single few-shot task at once, instead of one sample at a time as in inductive methods. These recent experimental observations in few-shot learning are consistent with established facts in classical transductive inference [START_REF] Vladimir | An overview of statistical learning theory[END_REF][START_REF] Joachims | Transductive inference for text classification using support vector machines[END_REF][START_REF] Dengyong | Learning with local and global consistency[END_REF], which is well-known to outperform inductive methods on small training sets. While [START_REF] Nichol | On first-order meta-learning algorithms[END_REF] used information of unlabeled query samples via batch normalization, the authors of [START_REF] Liu | Learning to propagate labels: Transductive propagation network for few-shot learning[END_REF] were the first to model explicitly transductive inference in few-shot learning. Inspired by popular label-propagation concepts [START_REF] Dengyong | Learning with local and global consistency[END_REF], they built a meta-learning framework that learns to propagate labels from labeled to unlabeled instances via a graph. The meta-learning transductive method in [START_REF] Hou | Cross attention network for few-shot classification[END_REF] used attention mechanisms to propagate labels to unlabeled query samples. More closely related to our work, the recent transductive inference of Dhillion et al. [START_REF] Guneet S Dhillon | A baseline for few-shot image classification[END_REF] minimizes the entropy of the network softmax predictions at unlabeled query samples, reporting competitive fewshot performances, while using standard cross-entropy training on the base classes. The competitive performance of [START_REF] Guneet S Dhillon | A baseline for few-shot image classification[END_REF] is in line with several recent inductive baselines [START_REF] Chen | A closer look at few-shot classification[END_REF][START_REF] Wang | Simpleshot: Revisiting nearest-neighbor classification for few-shot learning[END_REF][START_REF] Tian | Rethinking few-shot image classification: a good embedding is all you need[END_REF], which reported that standard cross-entropy training for the base classes matches or exceeds the performances of more sophisticated meta-learning procedures. Also, the performance of [START_REF] Guneet S Dhillon | A baseline for few-shot image classification[END_REF] is in line with established results in the context of semi-supervised learning, where entropy minimization is widely used [START_REF] Grandvalet | Semi-supervised learning by entropy minimization[END_REF][START_REF] Miyato | Virtual adversarial training: a regularization method for supervised and semi-supervised learning[END_REF][START_REF] Berthelot | Mixmatch: A holistic approach to semi-supervised learning[END_REF]. It is worth noting that the inference runtimes of transductive methods are, typically, much higher than their inductive counterparts. For, instance, the authors of [START_REF] Guneet S Dhillon | A baseline for few-shot image classification[END_REF] fine-tune all the parameters of a deep network during inference, which is several orders of magnitude slower than inductive methods such as ProtoNet [START_REF] Snell | Prototypical networks for few-shot learning[END_REF]. Also, based on matrix inversion, the transductive inference in [START_REF] Liu | Learning to propagate labels: Transductive propagation network for few-shot learning[END_REF] has a complexity that is cubic in the number of query samples.

Info-max principle: While the semi-supervised and few-shot learning works in [START_REF] Grandvalet | Semi-supervised learning by entropy minimization[END_REF][START_REF] Guneet S Dhillon | A baseline for few-shot image classification[END_REF] build upon Barlow's principle of entropy minimization [START_REF] Barlow | Unsupervised learning[END_REF], our few-shot formulation is inspired by the general info-max principle enunciated by Linsker [START_REF] Linsker | Self-organization in a perceptual network[END_REF], which formally consists in maximizing the Mutual Information (MI) between the inputs and outputs of a system. In our case, the inputs are the query features and the outputs are their label predictions. The idea is also related to info-max in the context of clustering [START_REF] Krause | Discriminative clustering by regularized information maximization[END_REF][START_REF] Hu | Learning discrete representations via information maximizing self-augmented training[END_REF][START_REF] Jabi | Deep clustering: On the link between discriminative models and k-means[END_REF]. More generally, info-max principles, well-established in the field of communications, were recently used in several deep-learning problems, e.g., representation learning [START_REF] Hjelm | Learning deep representations by mutual information estimation and maximization[END_REF][START_REF] Van Den Oord | Representation learning with contrastive predictive coding[END_REF], metric learning [START_REF] Boudiaf | A unifying mutual information view of metric learning: cross-entropy vs. pairwise losses[END_REF] or domain adaptation [START_REF] Liang | Do we really need to access the source data? source hypothesis transfer for unsupervised domain adaptation[END_REF], among other problems.

Contributions

• We propose Transductive Information Maximization (TIM) for few-shot learning. Our method maximizes the MI between the query features and their label predictions for a few-shot task at inference, while minimizing the cross-entropy loss on the support set.

• We derive an alternating-direction solver for our loss, which substantially speeds up transductive inference over gradient-based optimization, while yielding competitive accuracy.

• Following standard transductive few-shot settings, our comprehensive evaluations show that TIM outperforms state-of-the-art methods substantially across various datasets and networks, while using a simple cross-entropy training on the base classes, without complex metalearning schemes. It consistently brings between 2% and 5% of improvement in accuracy over the best performing method, not only on all the well-established few-shot benchmarks but also on more challenging, recently introduced scenarios, with domain shifts and larger numbers of ways. Interestingly, our MI loss includes a label-marginal regularizer, which has a significant effect: it brings substantial improvements in accuracy, while facilitating optimization, reducing transductive runtimes by orders of magnitude.

Q composed of |Q| = N Q • K unlabeled (unseen)
examples from each of the K classes. With models trained on the base set, few-shot techniques use the labeled support sets to adapt to the tasks at hand, and are evaluated based on their performances on the unlabeled query sets.

Proposed formulation

We begin by introducing some basic notation and definitions before presenting our overall Transductive Information Maximization (TIM) loss and the different optimization strategies for tackling it. For a given few-shot task, with a support set S and a query set Q, let X denote the random variable associated with the raw features within S [ Q, and let Y 2 Y = {1, . . . , K} be the random variable associated with the labels. Let f : X ! Z ⇢ R d denote the encoder (i.e., feature-extractor) function of a deep neural network, where denotes the trainable parameters, and Z stands for the set of embedded features. The encoder is first trained from the base training set X base using the standard cross-entropy loss, without any meta training or specific sampling schemes. Then, for each specific few-shot task, we propose to minimize a mutual-information loss defined over the query samples.

Formally, we define a soft-classifier, parametrized by weight matrix W 2 R K⇥d , whose posterior distribution over labels given features 4 , p ik := P(Y = k|X = x i ; W, ), and marginal distribution over query labels, b p k = P(Y Q = k; W, ), are given by:

p ik / exp ⇣ ⌧ 2 kw k z i k 2 ⌘ , and b p k = 1 |Q| X i2Q p ik (1)
where W := [w 1 , . . . , w K ] denotes classifier weights,

z i = f (xi) kf (xi)k 2
the L2-normalized embedded features, and ⌧ is a temperature parameter. Now, for each single few-shot task, we introduce our empirical weighted mutual information between the query samples and their latent labels, which integrates two terms: The first is an empirical (Monte-Carlo) estimate of the conditional entropy of labels given the query raw features, denoted b

H(Y Q |X Q ), while the second is the empirical label-marginal entropy, b H(Y Q ).: b I ↵ (X Q ; Y Q ) := K X k=1 b p k log b p k | {z } b H(YQ): marginal entropy + ↵ 1 |Q| X i2Q K X k=1 p ik log(p ik ) | {z } b H(YQ|XQ): conditional entropy (2)
with ↵ a non-negative hyper-parameter. Notice that setting ↵ = 1 recovers the standard mutual information. Setting ↵ < 1 allows us to down-weight the conditional entropy term, whose gradients may dominate the marginal entropy's gradients as the predictions move towards the vertices of the simplex. The role of both terms in (2) will be discussed after introducing our overall transductive inference loss in the following, by embedding supervision from the task's support set.

We embed supervision information from support set S by integrating a standard cross-entropy loss CE with the information measure in Eq. ( 2), which enables us to formulate our Transductive Information Maximization (TIM) loss as follows:

min W • CE b I ↵ (X Q ; Y Q ) with CE := 1 |S| X i2S K X k=1 y ik log(p ik ), (3)
where {y ik } denotes the k th component of the one-hot encoded label y i associated to the i-th support sample. Non-negative hyper-parameters ↵ and will be fixed to ↵ = = 0.1 in all our experiments. It is worth to discuss in more details the role (importance) of the mutual information terms in (3):

• Conditional entropy b H(Y Q |X Q )
aims at minimizing the uncertainty of the posteriors at unlabeled query samples, thereby encouraging the model to output confident predictions 5 . This entropy loss is widely used in the context of semi-supervised learning (SSL) [START_REF] Grandvalet | Semi-supervised learning by entropy minimization[END_REF][START_REF] Miyato | Virtual adversarial training: a regularization method for supervised and semi-supervised learning[END_REF][START_REF] Berthelot | Mixmatch: A holistic approach to semi-supervised learning[END_REF], as it models effectively the cluster assumption: The classifier's boundaries should not occur at dense regions of the unlabeled features [START_REF] Grandvalet | Semi-supervised learning by entropy minimization[END_REF]. Recently, [START_REF] Guneet S Dhillon | A baseline for few-shot image classification[END_REF] introduced this term for few-shot learning, showing that entropy fine-tuning on query samples achieves competitive performances. In fact, if we remove the marginal entropy b H(Y Q ) in objective (3), our TIM objective reduces to the loss in [START_REF] Guneet S Dhillon | A baseline for few-shot image classification[END_REF]. The conditional entropy b H(Y Q |X Q ) is of paramount importance but its optimization requires special care, as its optima may easily lead to degenerate (non-suitable) solutions on the simplex vertices, mapping all samples to a single class. Such care may consist in using small learning rates and fine-tuning the whole network (which itself often contains several layers of regularization) as done in [START_REF] Guneet S Dhillon | A baseline for few-shot image classification[END_REF], both of which significantly slow down transductive inference.

• The label-marginal entropy regularizer b H(Y Q ) encourages the marginal distribution of labels to be uniform, thereby avoiding degenerate solutions obtained when solely minimizing conditional entropy. Hence, it is highly important as it removes the need for implicit regularization, as mentioned in the previous paragraph. In particular, high-accuracy results can be obtained even using higher learning rates and fine-tuning only a fraction of the network parameters (classifier weights W instead of the whole network), speeding up substantially transductive runtimes. As it will be observed from our experiments, this term brings substantial improvements in performances (e.g., up to 10% increase in accuracy over entropy fine-tuning on the standard few-shot benchmarks), while facilitating optimization, thereby reducing transductive runtimes by orders of magnitude.

Optimization

At this stage, we consider that the feature extractor has already been trained on base classes (using standard cross-entropy). We now propose two methods for minimizing our objective (3) for each test task. The first one is based on standard Gradient Descent (GD). The second is a novel way of optimizing mutual information, and is inspired by the Alternating Direction Method of Multipliers (ADMM). For both methods:

• The pre-trained feature extractor f is kept fixed. Only the weights W are optimized for each task. Such a choice is discussed in details in subsection 3.4. Overall, and interestingly, we found that fine-tuning only classifier weights W, while fixing feature-extractor parameters , yielded the best performances for our mutual-information loss.

• For each task, weights W are initialized as the class prototypes of the support set:

w (0) k = P i2S y ik z i P i2S y ik
Gradient descent (TIM-GD): A straightforward way to minimize our loss in Eq. ( 3) is to perform gradient descent over W, which we update using all the samples of the few-shot task (both support and query) at once (i.e., no mini-batch sampling). This gradient approach yields our overall best results, while being one order of magnitude faster than the transductive entropy-based fine-tuning in [START_REF] Guneet S Dhillon | A baseline for few-shot image classification[END_REF]. As will be shown later in our experiments, the method in [START_REF] Guneet S Dhillon | A baseline for few-shot image classification[END_REF] needs to fine-tune the whole network (i.e., to update both and W), which provides implicit regularization, avoiding the degenerate solutions of entropy minimization. However, TIM-GD (with W-updates only) still remains two orders of magnitude slower than inductive closed-form solutions [START_REF] Snell | Prototypical networks for few-shot learning[END_REF]. In the following, we present a more efficient solver for our problem.

Alternating direction method (TIM-ADM): We derive an Alternating Direction Method (ADM) for minimizing our objective in (3). Such scheme yields substantial speedups in transductive learning (one order of magnitude), while maintaining the high levels of accuracy of TIM-GD. To do so, we introduce auxiliary variables representing latent assignments of query samples, and minimize a mixed-variable objective by alternating two sub-steps, one optimizing w.r.t classifier's weights W, and the other w.r.t the auxiliary variables q.

Proposition 1. The objective in (3) can be approximately minimized via the following constrained formulation of the problem:

min W,q |S| X i2S K X k=1 y ik log(p ik ) | {z } CE + K X k=1 b q k log b q k | {z } ⇠ b H(YQ) ↵ |Q| X i2Q K X k=1 q ik log(p ik ) | {z } ⇠ b H(YQ|XQ) + 1 |Q| X i2Q K X k=1 q ik log q ik p ik | {z } Penalty ⌘ DKL(qkp) s.t K X k=1 q ik = 1, q ik 0, i 2 Q, k 2 {1, . . . , K}, (4)
where q = [q ik ] 2 R |Q|⇥K are auxiliary variables, p = [p ik ] 2 R |Q|⇥K and b q k = 1 |Q| P i2Q q ik .
Proof. It is straightforward to notice that, when equality constraints q ik = p ik are satisfied, the last term in objective ( 4), which can be viewed as a soft penalty for enforcing those equality constraints, vanishes. Objectives ( 3) and ( 4) then become equivalent.

Splitting the problem into sub-problems on W and q as in Eq. ( 4) is closely related to the general principle of ADMM (Alternating Direction Method of Multipliers) [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF], except that the KL divergence is not a typical penalty for imposing the equality constraints 6 . The main idea is to decompose the original problem into two easier sub-problems, one over W and the other over q, which can be alternately solved, each in closed-form. Interestingly, this KL penalty is important as it completely removes the need for dual iterations for the simplex constraints in (4), yielding closed-form solutions:

Proposition 2. ADM formulation in Proposition 1 can be approximately solved by alternating the following closed-form updates w.r.t auxiliary variables q and classifier weights W (t is the iteration index):

q (t+1) ik / ⇣ p (t) ik ⌘ 1+↵ X i2Q ⇣ p (t) ik ⌘ 1+↵ ! 1/2 (5)
w

(t+1) k 1 + ↵ X i2S ⇣ y ik z i + p (t) ik (w (t) k z i ) ⌘ + |S| |Q| X i2Q ⇣ q (t+1) ik z i + p (t) ik (w (t) k z i ) ⌘ 1 + ↵ X i2S y ik + |S| |Q| X i2Q q (t+1) ik (6)
Proof. A detailed proof is deferred to the supplementary material. Here, we summarize the main technical ingredients of the approximation. Keeping the auxiliary variables q fixed, we optimize a convex approximation of Eq. ( 4) w.r.t W. With W fixed, the objective is strictly convex w.r.t the auxiliary variables q whose updates come from a closed-form solution of the KKT (Karush-Kuhn-Tucker) conditions. Interestingly, the negative entropy of auxiliary variables, which appears in the penalty term, handles implicitly the simplex constraints, which removes the need for dual iterations to solve the KKT conditions.

Experiments

Hyperparameters: To keep our experiments as simple as possible, our hyperparameters are kept fixed across all the experiments and methods (TIM-GD and TIM-ADM). The conditional entropy weight ↵ and the cross-entropy weights in Objective (3) are both set to 0.1. The temperature parameter ⌧ in the classifier is set to 15. In our TIM-GD method, we use the ADAM optimizer with the recommended parameters [START_REF] Diederik | Adam: A method for stochastic optimization[END_REF], and run 1000 iterations for each task. For TIM-ADM, we run 150 iterations.

Base-training procedure: The feature extractors are trained following the same simple base-training procedure as in [START_REF] Imtiaz | Laplacian regularized few-shot learning[END_REF] and using standard networks (ResNet-18 and WRN28-10), for all the experiments. Specifically, they are trained using the standard cross-entropy loss on the base classes, with label smoothing. The label-smoothing parameter is set to 0.1. We emphasize that base training does not involve any meta-learning or episodic training strategy. The models are trained for 90 epochs, with the learning rate initialized to 0.1, and divided by 10 at epochs 45 and 66. Batch size is set to 256 for ResNet-18, and to 128 for WRN28-10. During training, all the images are resized to 84 ⇥ 84, and we used the same data augmentation procedure as in [START_REF] Imtiaz | Laplacian regularized few-shot learning[END_REF], which includes random cropping, color jitter and random horizontal flipping.

Datasets: We resort to 3 few-shot learning datasets to benchmark the proposed models. As standard few-shot benchmarks, we use the mini-Imagenet [START_REF] Vinyals | Matching networks for one shot learning[END_REF] dataset, with 100 classes split as in [START_REF] Ravi | Optimization as a model for few-shot learning[END_REF], the Caltech-UCSD Birds 200 [START_REF] Welinder | [END_REF] (CUB) dataset, with 200 classes, split following [START_REF] Chen | A closer look at few-shot classification[END_REF], and finally the larger tiered-Imagenet dataset, with 608 classes split as in [START_REF] Ren | Meta-learning for semi-supervised few-shot classification[END_REF].

Comparison to state-of-the-art

We first evaluate our methods TIM-GD and TIM-ADM on the widely adopted mini-ImageNet, tiered-ImageNet and CUB benchmark datasets, in the most common 1-shot 5-way and 5-shot 5-way scenarios, with 15 query shots for each class. Results are reported in Table 1, and are averaged over 10,000 episodes, following [START_REF] Wang | Simpleshot: Revisiting nearest-neighbor classification for few-shot learning[END_REF]. We can observe that both TIM-GD and TIM-ADM yield state-of-the-art performances, consistently across all standard datasets, scenarios and backbones, improving over both transductive and inductive methods, by significant margins.

Impact of domain-shift

Chen et al. [START_REF] Chen | A closer look at few-shot classification[END_REF] recently showed that the performance of most meta-learning methods may drop drastically when a domain-shift exists between the base training data and test data. Surprisingly, the simplest discriminative baseline exhibited the best performance in this case. Therefore, we evaluate our methods in this challenging scenario. To this end, we simulate a domain shift by training the feature encoder on mini-Imagenet while evaluating the methods on CUB, similarly to the setting introduced in [START_REF] Chen | A closer look at few-shot classification[END_REF]. TIM-GD and TIM-ADM beat previous methods by significant margins in the domain-shift scenario, consistently with our results in the standard few-shot benchmarks, thereby demonstrating an increased potential of applicability to real-world situations.

Pushing the meta-testing stage

Most few-shot papers only evaluate their method in the usual 5-way scenario. Nevertheless, [START_REF] Chen | A closer look at few-shot classification[END_REF] showed that meta-learning methods could be beaten by their discriminative baseline when more ways were introduced in each task. Therefore, we also provide results of our method in the more challenging 10-way and 20-way scenarios on mini-ImageNet. These results, which are presented in Table 3, show that TIM-GD outperforms other methods by significant margins, in both settings.

Ablation study

Influence of each term: We now assess the impact of each term7 in our loss in Eq. ( 3) on the final performance of our methods. The results are reported in Table 4. We observe that integrating the three terms in our loss consistently outperforms any other configuration. Interestingly, removing ResNet-18 51.3 ProtoNet [START_REF] Snell | Prototypical networks for few-shot learning[END_REF] ResNet-18 62.0 RelatNet [START_REF] Sung | Learning to compare: Relation network for few-shot learning[END_REF] ResNet-18 57.7 SimpleShot [START_REF] Wang | Simpleshot: Revisiting nearest-neighbor classification for few-shot learning[END_REF] ResNet-18 64.0 GNN [START_REF] Tseng | Cross-domain few-shot classification via learned feature-wise transformation[END_REF] ResNet-10 66.9 Neg-Cosine [START_REF] Liu | Negative margin matters: Understanding margin in few-shot classification[END_REF] ResNet-18 67.0 Baseline [START_REF] Chen | A closer look at few-shot classification[END_REF] ResNet-18 65.6 LaplacianShot [START_REF] Imtiaz | Laplacian regularized few-shot learning[END_REF] the label-marginal entropy, b H(Y Q ), reduces significantly the performances in both TIM-GD and TIM-ADM, particularly when only classifier weights W are updated and feature extractor is fixed. Such a behavior could be explained by the following fact: the conditional entropy term, b H(Y Q |X Q ), may yield degenerate solutions (assigning all query samples to a single class) on numerous tasks, when used alone. This emphasizes the importance of the label-marginal entropy term b H(Y Q ) in our loss [START_REF] Boudiaf | A unifying mutual information view of metric learning: cross-entropy vs. pairwise losses[END_REF], which acts as a powerful regularizer to prevent such trivial solutions.

Fine-tuning the whole network vs only the classifier weights: While our TIM-GD and TIM-ADM optimize w.r.t W and keep base-trained encoder f fixed at inference, the authors of [START_REF] Guneet S Dhillon | A baseline for few-shot image classification[END_REF] fine-tuned the whole network {W, } when performing their transductive entropy minimization. To assess both approaches, we add to Table 4 a variant of TIM-GD, in which we fine-tune the whole network {W, }, by using the same optimization procedure as in [START_REF] Guneet S Dhillon | A baseline for few-shot image classification[END_REF]. We found that, besides being much slower, fine-tuning the whole network for our objective in Eq. 3 degrades the performances, as also conveyed by the convergence plots in Figure 1. Interestingly, when fine-tuning the whole network {W, }, the absence of b

H(Y Q ) in the entropy-based loss CE + b H(Y Q |X Q )
does not cause the same drastic drop in performance as observed earlier when optimizing with respect to W only. We hypothesize that the network's intrinsic regularization (such as batch normalizations) and the use of small learning rates, as prescribed by [START_REF] Guneet S Dhillon | A baseline for few-shot image classification[END_REF], help the optimization process, preventing the predictions from approaching the vertices of the simplex, where entropy's gradients diverge.

Inference run-times

Transductive methods are generally slower at inference than their inductive counterparts, with runtimes that are, typically, several orders of magnitude larger. In Table 5, we measure the average Table 5: Inference run-time per few-shot task for a 5-shot 5-way task on mini-ImageNet with a WRN28-10 backbone.

Run-times

Method

Parameters Transductive Inference/task (s)

SimpleShot [46] {W} 7 9.0 ⇥ 10 3 TIM-ADM {W} 1.2 ⇥ 10 1 TIM-GD {W} 2.2 ⇥ 10 +0 Ent-min [7] { , W} 3
2.1 ⇥ 10 +1
adaptation time per few-shot task, defined as the time required by each method to build the final classifier, for a 5-shot 5-way task on mini-ImageNet using the WRN28-10 network. Table 5 conveys that our ADM optimization gains one order of magnitude in run-time over our gradient-based method, and more than two orders of magnitude in comparison to [START_REF] Guneet S Dhillon | A baseline for few-shot image classification[END_REF], which fine-tunes the whole network. Note that TIM-ADM still remains slower than the inductive baseline. Our methods were run on the same GTX 1080 Ti GPU, while the run-time of [START_REF] Guneet S Dhillon | A baseline for few-shot image classification[END_REF] is directly reported from the paper.

Conclusion and future work

Our TIM inference establishes new state-of-the-art results on the standard few-shot benchmarks, as well as in more challenging scenarios, with larger numbers of classes and domain shifts. We used feature extractors based on a simple base-class training with the standard cross-entropy loss, without resorting to the complex meta-training schemes that are often used and advocated in the recent few-shot literature. TIM is modular: it could be plugged on top of any feature extractor and base training, regardless of how the training was conducted. Therefore, while we do not claim that the very challenging few-shot problem is solved, we believe that our model-agnostic TIM inference should be used as a strong baseline for future few-shot learning research. In future work, we target on giving a more theoretical ground for our proposed mutual-information objective, and on exploring further generalizations of the objective, e.g., via embedding domain-knowledge priors. Specifically, one of our theoretical goals will be to connect TIM's objective to the classifier's empirical risk on the query set, showing that the former could be viewed as a surrogate for the latter.

Acknowledgements

This project has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 792464. This research was 9 797805.

supported by the National Science and Engineering Research Council of Canada (NSERC), via its Discovery Grant program.

Broader impact

Due to the simplicity and efficiency of our method, we lower the barrier of entry to few-shot learning.

In turn, we think that it will make a wider breadth of real-world applications tractable. The impact (positive or negative) on society is similar to that of any other few-shot method: being only a tool, its impact is entirely dependent on the final applications, and on the intentions of the people and institutions deploying it.

In our strive towards finding simple and efficient formulations -for instance, we stick to a standard cross-entropy, which not only eases implementation, but also avoid the huge memory consumption of more complex methods -we believe our method can enable and empower persons and communities that are unable to afford the costly resources and infrastructures required. This may help level the playing field with larger and better funded entities. For instance, to be adapted to a new task, our TIM-ADM method requires a little more than a recent smartphone computational power. This could spawn a lot of fresh and new applications on edge devices, closer to the end-users, in real-time.

1 A + 1 + ↵ |Q| X i2Q log 0 @ K X j=1 e 1 2 kzi wj k 2 1 A | {z } C:non-convex (12)
One can notice that objective [START_REF] Grandvalet | Semi-supervised learning by entropy minimization[END_REF] is not convex w.r.t w k . Actually, it can be split into convex and non-convex parts as in Eq. ( 12). Thus, we cannot simply set the gradients to 0 to get the optimal w k . The non-convex part can be linearized at current solution w

k as follows:

C(w k ) ⇡ C(w (t) k ) + @ C @w k (w (t) k ) T (w k w (t) k ) c = |S| X i2S p (t) ik (z i w (t) k ) T w k + 1 + ↵ |Q| X i2Q p (t) ik (z i w (t) k ) T w k (13)
Where c = stands for "equal, up to an additive constant". By adding this linear term to the convex part C, we can obtain a strictly convex objective in w k , whose gradients w.r.t w k read:

@(12) @w k ⇡ |S| [ X i2S y ik (z i w k ) + p (t) ik (z i w (t) k )] + 1 + ↵ |Q| [ X i2Q q ik (z i w k ) + p (t) ik (z i w (t) k )] (14)
Note that the approximation we do here is similar in spirit to concave-convex procedures, which are well known in optimization. Concave-convex techniques proceed as follows: for a function in the form of a sum of a concave term and a convex term, the concave part is replaced by its first-order approximation, while the convex part is kept as is. The difference here is that the part that we linearize in Eq. ( 12) is not concave. Setting the gradients above to 0 yields the optimal solution for the approximate objective.

Another solution to obtain a strictly convex objective would have been to discard the nonconvex part C. Very interestingly, in this case, one would recover w k updates that would very much resemble the prototype updates of the K-means clustering algorithm (slightly modified to take into account the fact that for support points in S have labels). Note that the link between regularized K-means and mutual information maximization has been extensively explored in [START_REF] Jabi | Deep clustering: On the link between discriminative models and k-means[END_REF]. Of course, in this case, the approximation is not as good as the first-order approximation above, and we found that omitting the non-convex part might decrease the performances significantly.

• q-update: With weights W fixed, the objective is convex w.r.t auxiliary variables q i (sum of linear and convex functions) and the simplex constraints are affine. Therefore, one can minimize this constrained convex problem for each q i by solving the Karush-Kuhn-Tucker (KKT) conditions 8 . The KKT conditions yield closed-form solutions for both primal variable q i and the dual variable (Lagrange multiplier) corresponding to simplex constraint P K j=1 q ij = 1. Interestingly, the negative entropy of auxiliary variables, i.e., P K k=1 q ik log q ik , which appears in the penalty term, handles implicitly non-negativity constraints q i 0. In fact, this negative entropy acts as a barrier function, restricting the domain of each q i to non-negative values, which avoids extra dual variables and Lagrangiandual inner iterations for constraints q i 0. As we will see, the closed-form solutions of the KKT conditions satisfy these non-negativity constraints, without explicitly imposing them. In addition to non-negativity, for each point i, we need to handle probability simplex constraints P K k=1 q ik = 1. Let i 2 R denote the Lagrangian multiplier corresponding to this constraint. The KKT conditions correspond to setting the following gradient of the Lagrangian function to zero, while enforcing the simplex constraints: @(4) @q ik = 1 + ↵ |Q| log p ik + 1

|Q|

(log b q k + 1) + 1

|Q|

(log q ik + 1) + i

= 1

|Q| ✓ log( q ik b q k p 1+↵ ik ) + 2 ◆ + i (16)
This yields:

q ik = p 1+↵ ik b q k e ( i |Q|+2) (17)
Applying simplex constraint P K j=1 q ij = 1 to (17), Lagrange multiplier i verifies:

e ( i |Q|+2) = 1 K X j=1 p 1+↵ ij b q j (18)
Hence, plugging [START_REF] Joachims | Transductive inference for text classification using support vector machines[END_REF] in ( 17) yields:

q ik = p 1+↵ ik b q k K X j=1 p 1+↵ ij b q j ( 19
)
Using the definition of b q k , we can decouple this equation:

b q k = 1 |Q| X i2Q q ik / X i2Q p 1+↵ ik b q k ( 20
)
which implies:

b q k / X i2Q p 1+↵ ik ! 1/2 (21)
Plugging this back in Eq. ( 19), we get:

q ik / p 1+↵ ik X i2Q p 1+↵ ik ! 1/2 (22)
Notice that q ik 0, hence the solution fulfils the positivity constraint of the original problem.

B TIM algorithms

In this section, we provide the pseudo-code for TIM's inference stage (both TIM-GD and TIM-ADM).

Algorithm 1: TIM-ADM Input : Pre-trained encoder f , Task {S, Q}, # iterations iter, Temperature ⌧ , Weights { , ↵}

z i f (xi) kf (xi)k 2 , i 2 S [ Q w k P i2S yikzi P i2S yik , k 2

8

 8

Figure 1 :

 1 Figure 1: Convergence plots for our methods on mini-ImageNet with a ResNet-18. Solid lines are averages, while shadows are 95% confidence intervals. Time is in logarithmic scale. Left: Evolution of the test accuracy during transductive inference. Right: Evolution of the mutual information between query features and predictions b I(X Q ; Y Q ), computed as in Eq. (2), with ↵ = 1.

  Assume we are given a labeled training set, X base := {x i , y i } Nbase i=1 , where x i denotes raw features of sample i and y i its associated one-hot encoded label. Such labeled set is often referred to as the meta-training or base dataset in the few-shot literature. Let Y base denote the set of classes for this base dataset. The few-shot scenario assumes that we are given a test dataset:X test := {x i , y i } Ntest i=1 ,with a completely new set of classes Y test such that Y base \ Y test = ;, from which we create randomly sampled few-shot tasks, each with a few labeled examples. Specifically, each K-way N S -shot task involves sampling N S labeled examples from each of K different classes, also chosen at random. Let S denote the set of these labeled examples, referred to as the support set with size |S| = N S • K. Furthermore, each task has a query set denoted by

	2 Transductive Information Maximization
	2.1 Few-shot setting

Table 1 :

 1 Comparison to the state-of-the-art methods on mini-ImageNet, tiered-Imagenet and CUB.

	The methods are sub-grouped into transductive and inductive methods, as well as by backbone
	architecture. Our results (gray-shaded) are averaged over 10,000 episodes. "-" signifies the result is
	unavailable.
				mini-ImageNet tiered-ImageNet	CUB
	Method	Transd.	Backbone	1-shot 5-shot 1-shot	5-shot	1-shot 5-shot
	MAML [9]		ResNet-18	49.6	65.7	-	-	68.4	83.5
	RelatNet [40]		ResNet-18	52.5	69.8	-	-	68.6	84.0
	MatchNet [45]		ResNet-18	52.9	68.9	-	-	73.5	84.5
	ProtoNet [38]		ResNet-18	54.2	73.4	-	-	73.0	86.6
	MTL [39]	7	ResNet-12	61.2	75.5	-	-	-	-
	vFSL [50]		ResNet-12	61.2	77.7	-	-	-	-
	Neg-cosine [26]		ResNet-18	62.3	80.9	-	-	72.7	89.4
	MetaOpt [22]		ResNet-12	62.6	78.6	66.0	81.6	-	-
	SimpleShot [46]		ResNet-18	62.9	80.0	68.9	84.6	68.9	84.0
	Distill [41]		ResNet-12	64.8	82.1	71.5	86.0	-	-
	RelatNet + T [14]		ResNet-12	52.4	65.4	-	-	-	-
	ProtoNet + T [14]		ResNet-12	55.2	71.1	-	-	-	-
	MatchNet+T [14]		ResNet-12	56.3	69.8	-	-	-	-
	TPN [28]		ResNet-12	59.5	75.7	-	-	-	-
	TEAM [34] Ent-min [7]	3	ResNet-18 ResNet-12	60.1 62.4	75.9 74.5	-68.4	-83.4	--	--
	CAN+T [14]		ResNet-12	67.2	80.6	73.2	84.9	-	-
	LaplacianShot [51]		ResNet-18	72.1	82.3	79.0	86.4	81.0	88.7
	TIM-ADM		ResNet-18	73.6	85.0	80.0	88.5	81.9	90.7
	TIM-GD		ResNet-18	73.9	85.0	79.9	88.5	82.2	90.8
	LEO [37]		WRN28-10	61.8	77.6	66.3	81.4	-	-
	SimpleShot [46]		WRN28-10	63.5	80.3	69.8	85.3	-	-
	MatchNet [45]	7	WRN28-10	64.0	76.3	-	-	-	-
	CC+rot+unlabeled [10]		WRN28-10	64.0	80.7	70.5	85.0	-	-
	FEAT [49]		WRN28-10	65.1	81.1	70.4	84.4	-	-
	AWGIM [12]		WRN28-10	63.1	78.4	67.7	82.8	-	-
	Ent-min [7]		WRN28-10	65.7	78.4	73.3	85.5	-	-
	SIB [15]		WRN28-10	70.0	79.2	-	-	-	-
	BD-CSPN [27]	3	WRN28-10	70.3	81.9	78.7	86.92	-	-
	LaplacianShot [51]		WRN28-10	74.9	84.1	80.2	87.6	-	-
	TIM-ADM		WRN28-10	77.5	87.2	82.0	89.7	-	-
	TIM-GD		WRN28-10	77.8	87.4	82.1	89.8	-	-

Table 2 :

 2 The results for the domain-shift setting mini-Imagenet ! CUB. The results obtained by our models (gray-shaded) are averaged over 10,000 episodes.

	Methods	Backbone	mini-ImageNet ! CUB 5-shot
	MatchNet [45]	ResNet-18	53.1
	MAML [9]

Table 3 :

 3 Results for increasing the number of classes on mini-ImageNet. The results obtained by our models (gray-shaded) are averaged over 10,000 episodes.

		ResNet-18	66.3
	TIM-ADM	ResNet-18	70.3
	TIM-GD	ResNet-18	71.0

Table 4 :

 4 Ablation study on the effect of each term in our loss in Eq. (3), when only the classifier weights are fine-tuned, i.e., updating only W, and when the whole network is fine-tuned, i.e., updating { , W}. The results are reported for ResNet-18 as backbone. The same term indexing as in Eq. (3) is used here: b H(Y

	mini-ImageNet tiered-ImageNet	CUB

Q ): Marginal entropy, b H(Y Q |X Q ): Conditional entropy, CE: Cross-entropy.

  Query predictions ŷi = arg max k p ik , i 2 Q Algorithm 2: TIM-GD Input : Pre-trained encoder f , Task {S, Q}, # iterations iter, Temperature ⌧ , Weights { , ↵}, Query predictions ŷi = arg max k p ik , i 2 Q

	p ik q ik q ik	pik P K l=1 pil p 1+↵ ik ( P i2Q p 1+↵ ik ) qik P K l=1 qil X	1/2 , i 2 Q
		1 + ↵
	w k end		1 + ↵	X i2S	y ik +	|S| |Q|	X i2Q	q ik
	Result: Learning rate
	z i w k for i p ik kf (xi)k 2 f (xi) P i2S yikzi , i 2 S [ Q P i2S yik , k 2 {1, . . . , K} 0 to iter do exp ⇣ ⌧ ⌘ 2 2 kw k z i k p ik pik P K l=1 pil w k w k r wk L TIM end
	Result:

{1, . . . , K} for i 0 to iter do p ik exp ⇣ ⌧ 2 kw k z i k 2 ⌘ , i 2 S [ Q i2S (y ik z i + p ik (w k z i )) + |S| |Q| X i2Q

(q ik z i + p ik (w k z i ))

Transductive few-shot inference is not to be confused with semi-supervised few-shot learning[START_REF] Ren | Meta-learning for semi-supervised few-shot classification[END_REF][START_REF] Li | Learning to self-train for semi-supervised few-shot classification[END_REF]. The latter uses extra unlabeled data during meta-training. Transductive inference has access to exactly the same training/testing data as its inductive counterpart.

In order to simplify our notations, we deliberately omit the dependence of posteriors pik on the network parameters ( , W). Also, pik takes the form of softmax predictions, but we omit the normalization constants.

The global minima of each pointwise entropy in the sum of b H(YQ|XQ) are one-hot vectors at the vertices of the simplex.

Typically, ADMM methods use multiplier-based quadratic penalties for enforcing the equality constraint.

The W and q updates of TIM-ADM associated to each configuration can be found in the supplementary material.

Note that strong duality holds since the objective is convex and the simplex constraints are affine. This means that the solutions of the (KKT) conditions minimize the objective.

A Proofs

Proof of Proposition 1

Proof. Let us start from the initial optimization problem:

We can reformulate problem (7) using the ADM approach, i.e., by introducing auxiliary variables q = [q ik ] 2 R |Q|⇥K and enforcing equality constraint q = p, with p = [p ik ] 2 R |Q|⇥K , in addition to pointwise simplex constraints:

We can solve constrained problem (8) with a penalty-based approach, which encourages auxiliary pointwise predictions q i = [q i1 , . . . , q iK ] to be close to our model's posteriors

To add a penalty encouraging equality constraints q i = p i , we use the Kullback-Leibler (KL) divergence, which is given by:

Thus, our constrained optimization problem becomes:

Proof of Proposition 2

Proof. Recall that we consider a softmax classifier over distances to weights W = {w 1 , . . . , w K }.

To simplify the notations, we will omit the dependence upon in what follows, and write

Without loss of generality, we use ⌧ = 1 in what follows. Plugging the expression of p ik into Eq. ( 4), and grouping terms together, we get:

Now, we can solve our problem approximately by alternating two sub-steps: one sub-step optimizes w.r.t classifier weights W while auxiliary variables q are fixed; another sub-step fixes W and update q.

• W-update: Omitting the terms that do not involve W, Eq. ( 11) reads:

C Summary figure

We hereby provide a summarizing figure of the training and inference stages used in TIM.

Figure 2: Outline of TIM framework (best viewed in color). First, the feature extractor is trained with the standard cross-entropy on the base classes. Then, it is kept fixed at inference and weights W are optimized for by minimizing the cross-entropy on the support set S, while maximizing the mutual information between features and predictions on the query set Q.

D Details of ADM ablation

In Table 6, we provide the W and q updates for each configuration of the TIM-ADM ablation study, whose results were presented in Table 4. The proof for each of these updates is very similar to the proof of Proposition 2 detailed in Appendix A. Therefore, we do not detail it here.

Table 6: The W and q-updates for each case of the ablation study. "-" refers to the updates in Proposition 2. "NA" refers to non-applicable.