Title: IMPROVED MUTUAL INFORMATION ESTIMATION

Abstract: We propose a new variational lower bound on the KL divergence and show that the Mutual Information (MI) can be estimated by maximizing this bound using a witness function on a hypothesis function class and an auxiliary scalar variable. If the function class is in a Reproducing Kernel Hilbert Space (RKHS), this leads to a jointly convex problem. We analyze the bound by deriving its dual formulation and show its connection to a likelihood ratio estimation problem. We show that the auxiliary variable introduced in our variational form plays the role of a Lagrange multiplier that enforces a normalization constraint on the likelihood ratio. By extending the function space to neural networks, we propose an efficient neural MI estimator, and validate its performance on synthetic examples, showing advantage over the existing baselines. We then demonstrate the strength of our estimator in large-scale self-supervised representation learning through MI maximization.

1. INTRODUCTION:

Mutual information (MI) is an ubiquitous measure of dependency between a pair of random variables, and is one of the corner stones of information theory. In machine learning, the information maximization principle for learning representation from unlabeled data through self-supervision (Bell & Sejnowski, 1995) motivated the development of many MI estimators and applications (Hjelm et al., 2019; Noroozi & Favaro, 2016; Kolesnikov et al., 2019; Doersch et al., 2015; van den Oord et al., 2018b; Hu et al., 2017) . The information bottleneck (Tishby et al., 1999; Kolchinsky et al., 2017) is another principle that triggered recent interest in mutual information estimation. MI is also used to understand the information flow in neural networks, in learning clusters (Krause et al., 2010) and in regularizing the training of Generative Adversarial Networks (GANs) (Chen et al., 2016) .

In many of those machine learning applications and other scientific fields, one has to estimate MI given samples from the joint distribution of high dimensional random variables. This is a challenging problem and many methods have been devised to address it. Since MI is defined as the Kullback-Leibler (KL) divergence between the joint distribution and the product of marginals, one can leverage non parametric estimators of f-divergences (Nguyen et al., 2008; Nowozin et al., 2016; Sriperumbudur et al., 2009) . Specifically of interest to us is the Donsker-Varadhan (DV) representation of the KL divergence (Donsker & Varadhan, 1976 ) that was used recently with neural networks estimators (Belghazi et al., 2018; Poole et al., 2019) . Other approaches to estimating the MI are through finding lower bounds using variational Bayesian methods (Alemi et al., 2016; 2017; Barber & Agakov, 2003; Blei et al., 2017) , as well as through geometric methods like binning (Kraskov et al., 2004) .

In this paper we propose a new estimator of MI that can be used in direct MI maximization or as a regularizer, thanks to its unbiased gradients. Our starting point is the DV lower bound of the KL divergence that we represent equivalently via a joint optimization that we call η-DV on a witness function f and an auxiliary variable η in Section 2. In Section 3, we show that when the witness function f is learned in a Reproducing Kernel Hilbert Space (RKHS) the η-DV problem is jointly convex in both f and η. The dual of this problem sheds the light on this estimator as a constrained ratio estimation where η plays the role of a Lagrange multiplier that ensures proper normalization of the likelihood ratio. We also show how the witness function can be estimated as a neural network akin to Belghazi et al. (2018) . We specify our estimator for MI in Section 4, and show how it compares to alternatives in the literature (Nguyen et al., 2008; Belghazi et al., 2018; Poole et al., 2019) . The experiments are presented in Section 5. On synthetic data, we validate our estimators by estimating MI on Gaussian variables and by regularizing GAN training as in Chen et al. (2016) . On real data, Lower Bounds on Estimators of

sup f 2H E P [f ] log(E Q ⇥ e f ⇤ )

< l a t e x i t s h a 1 _ b a s e 6 4 = " X P X n i x 3 n j 9 F 7 j Z T 7 T Z a 2 L u Q k t Q 8 = " > A A A C l 3 i c b V F d i x M x F M 2 M X 2 v 9 6 r p P o k K w C O u D Z W Y V 1 j c X R e l j C 3 Z 3 o R l L J r 0 z D Z v J D M k d s Y Q 8 + x v 9 E f 4 A 3 0 z b U e z u X g g c z j m X e + 9 J 3 i h p M U l + R v G N m 7 d u 3 9 m 7 2 7 t 3 / 8 H D R / 3 9 x 6 e 2 b o 2 A q a h V b c 5 z b k F J D V O U q O C 8 M c C r X M F Z f v F x r Z 9 9 A 2 N l r b / g q o G s 4 q W W h R Q c A z X v / 2 C t X g Q d 0 B V M a s o q j k v B l R t 5 7 5 h t G 8 8 U F M j c R s h z 9 8 n P / + G x 3 6 q z g h l Z L j F 7 T Z m q y 8 P r v J O / X v j q C t / 5 6 a s t Y H 7 e H y T D Z F P 0 K k g 7 M C B d j e f 9 3 2 x R i 7 Y C j U J x a 2 d p 0 m D m u E E p F P g e a y 0 0 X F z w E m Y B a l 6 B z d w m M E 9 f B m Z B i 9 q E p 5 F u 2 P 8 7 H K + s X V V 5 c K 7 X t 5 e 1 N X m d N m u x e J c 5 q Z s W Q Y v t o K J V F G u 6 T p 8 u p A G B a h U A F 0 a G X a l Y c s M F h j / Y m V I a 3 i y l + L 5 z i c s r 3 + u F r N L L y V w F p 0 f D 9 M 3 w a P J 2 c P K h S 2 2 P P C U v y C F J y T E 5 I S M y J l M i y K / o I H o W P Y + f x O / j z / F o a 4 2 j r u e A 7 F Q 8 + Q O C w N A E < / l a t e x i t > sup f 2H,⌘2R

E P [f ] e ⌘ E Q ⇥ e f ⇤ ⌘ + 1

< l a t e x i t s h a 1 _ b a s e 6 4 = " 8 5 u u c C 9 e v 3 3 w C a Z X x x Z g 8 2 E m y a g = " > A A A C t 3 i c b V F d i x M x F M 2 M X 2 t 1 t e q j L 8 E i C N o y s y u o o L A o w j 5 2 x e 4 u N O O Q S Z N O 2 E x m T O 6 I J e T 3 + J v 8 K b 6 Z a a d i d / d C 4 H D O u b m 5 J 0 W j p I U k + R 3 F N 2 7 e u n 1 n 7 + 7 g 3 v 3 9 B w + H j x 6 f 2 r o 1 j M 9 Y r W p z X l D L l d R 8 B h I U P 2 8 M p 1 W h + F l x 8 a n T z 3 5 w Y 2 W t v 8 K q 4 V l F l 1 o K y S g E K h / + I q 1 e B J 2 D E 0 R q U l E o G V X u 2 L / C h A P d c k X h v n j v i G 0 b T x Q X Q N y W / + z z f 3 j q N + p c E C O X J W R j z L + 5 c X e T v 8 5 / s v U H l / B 9 D x 6 v R + O X O N 0 w x A / y 4 S i Z J O v C V 0 H a g x H q a 5 o P / 5 B F z d q K a 2 C K W j t P k w Y y R w 1 I p r g f k N b y h r I L u u T z A D W t u M 3 c O l C P n w d m g U V t w t G A 1 + z / H Y 5 W 1 q 6 q I j i 7 R e x l r S O v 0 + Y t i L e Z k 7 p p g W u 2 G S R a h a H G 3 e / g h T S c g V o F Q J m R 4 a 2 Y l d R Q B u G P d q Y s D W 1 K y X 7 u b O K K y g + 6 r N L L y V w F p w e T 9 H B y c P J 6 d P S x T 2 0 P P U X P 0 A u U o j f o C B 2 j K Z o h F u 1 H h 9 H 7 6 E P 8 L s 5 j E Z c b a x z 1 P U / Q T s X f / w I Z D N t m < / l a t e x i t >

sup f 2H E P [f ] E Q e f + 1

< l a t e x i t s h a 1 _ b a s e 6 4 = " 2 X T 4 R 7 s z J l 4 N D v s M v N O 7 r S F t j X M = " > A A A C h n i c b V B N a x s x F N R u 0 s Z 1 0 s Z N j 7 2 I m E C h 1 O z m g / R o G g o 5 O h A n A W t r t P J b W 0 S r X a S 3 I U b o h x b 6 R 3 q L / E G p k w w I h p l 5 v K f J a y U t J s n v K N 7 a f v N 2 p / W u v b v 3 / s N + 5 + P B j a 0 a I 2 A o K l W Z u 5 x b U F L D E C U q u K s N 8 D J X c J v f X y z 8 2 w c w V l b 6 G u c 1 Z C W f a l l I w T F I 4 8 4 D a / Q k + I C u Y F K z k u N M c O U u v X f M N r V n C g q k z C 2 d P H c / / f g f H / i V P S q Y k d M Z Z t 9 e S 1 1 5 D 7 9 c 4 e l X m q 5 y z I 8 7 3 a S X L E F f k n R N u m S N w b j z l 0 0 q 0 Z S g U S h u 7 S h N a s w c N y i F A t 9 m j Y W a i 3 s + h V G g m p d g M 7 f s x 9 O j o E x o U Z n w N N K l + v + E 4 6 W 1 8 z I P y c X N 9 r m 3 E F / z R g 0 W 3 z M n d d 0 g a L F a V D S K Y k U X Z d O J N C B Q z Q P h w s h w K x U z b r j A U P n G l q n h 9 U y K x 4 2 f u L z 0 7 X b o K n 3 e z E t y c 9 x L T 3 r H V 6 f d / o 9 1 a y 3 y m R y S L y Q l 5 6 R P L s m A D I k g f 6 I 4 2 o 3 2 4 l b c i 8 / i 8 1 U 0 j t Y z n 8 g G 4 v 4 T W y P I j g = = < / l a t e x i t > f -MINE < l a t e x i t s h a 1 _ b a s e 6 4 = " b s q m P A I 4 S 5 Q P V u D y l j 9 c E U y N f g U = " > A A A C G 3 i c b V B N S 8 N A E N 3 U r x q / q h 6 9 B I v g x Z J U Q Y 9 F E f S g V L C t 0 I a y 2 W 7 a p b t J 3 J 1 I S 8 j v 8 C T o b / E m X j 3 4 U 7 y 5 b X O w r Q 8 G H u / N M D P P i z h T Y N v f R m 5 h c W l 5 J b 9 q r q 1 v b G 4 V t n f q K o w l o T U S 8 l A + e F h R z g J a we explore our estimator in deep MI maximization for learning representation from unlabeled data.

= " > A A A C H H i c b V D L S s N A F J 3 U V 4 2 v q k s 3 w S K 4 s S R V 0 G X x A b p Q K t g H t L F M p p N 2 6 G Q S Z m 6 k J e Q / X A n 6 L e 7 E r e C n u H P 6 W N j W A x c O 5 9 z L v f d 4 E W c K b P v b y C w s L i 2 v Z F f N t f W N z a 3 c 9 k 5 V h b E k t E J C H s q 6 h x X l T N A K M O C 0 H k m K A 4 / T m t e 7 G P q 1 J y o V C 8 U D D C L q B r g j m M 8 I B i 0 9 N o H 2 I b m s H t 3 e 3 F 2 l r V z e L t g j W P P E m Z A 8 m q D c y v 0 0 2 y G J A y q A c K x U w 7 E j c B M s g R F O U 7 M Z K x p h 0 s M d 2 t B U 4 I A q N x l d n V o H W m l b f i h 1 C b B G 6 t + J B A d K D Q J P d w Y Y u m r W G 4 r / e Y 0 Y / D M 3 Y S K K g Q o y X u T H 3 I L Q G k Z g t Z m k B P h A E 0 w k 0 7 d a p I s l J q C D m t r S k T j q M t K f + i T x g t Q 0 d V b O b D L z p F o s O M e F 4 v 1 J v n Q + S S 2 L 9 t A + O k Q O O k U l d I 3 K q I I I k u g Z v a I 3 4 8 V 4 N z 6 M z 3 F r x p j M 7 K I p G F + / b O C i G g = = < / l a t e x i t > ⌘-MINE < l a t e x i t s h a _ b a s e = " H S s l j v w H k B t D w H Z X S d R N Q c J K n k = " > A A A C I H i c b V D J S g N B E O x j X E b e h l M A h e D D N R G N Q B D o E c w C m R B O p W k S c C d I G O Z P P A n L d E o / J N z v L w S Q + K H i V V V P S S X K F t f x l L y y u r a + u Z j e z m v b O r r m X F h L B m U W S h C W f O o A s E D K C N H A b V I A v U A V W v d z y q Q i o f B E w j a P i E / A Z x S D R N F C C A N M T u / v H m S p p m z / Y Y i J x p i R H p i g z R + F b L Y h w C Z o E r V H T v C R k I l c i Y g z b q x g o i y H u A X d O A + q A a y f j y D r W S s t q h J X g N Z Y / T u R U F + p o e / p T p i V I / E / r x j + K R C C K E Q I W d S O h Y W h N Y r B a n E J D M V Q E o k d a r E s l Z a j D m t n S k T T q c j a Y + S T x / D S b V k k s k k o h z l C / n u e L V N L U M O S R H I Q I I U y S p k T J h p E + e y S t M M d + P D + J y L h n T m Q M y A + P F + R t o s = < / l a t e x i t > sup f n E pxy [f (x, y)] E pxpy h e f (x,y) i + 1 o < l a t e x i t s h a 1 _ b a s e 6 4 = " T 4 e h q f S A r 2 9 F n G r R t u T O a z 4 5 V j 8 = " > A A A C i X i c b V D R a h Q x F M 2 M V u t W 2 6 1 9 9 C W 4 C B V 1 m W m F F p + K R f C x g t s W N u O Q y W Z 2 Q z O Z k N y R H U I + t E / 9 D t + a 3 R n B b T 0 Q O J x z L j f 3 F F o K C 0 l y G 8 V P n m 4 9 e 7 7 9 Y r D z 8 t X u 3 n D / 9 a W t G 8 P 4 h N W y N t c F t V w K x S c g Q P J r b T i t C s m v i p v z l X / 1 m x s r a v U T W s 2 z i s 6 V K A W j E K R 8 2 J J G z Y L P w Z X e E d t o T y Q v g T h S U V g U h f v m c 6 d z t 2 x 9 5 0 z L w + X H 9 j 0 x Y r 6 A D O N P e D O 5 1 H n b J / k v 1 4 X 9 3 / Q H n H a U + H w 4 S s b J G v g x S X s y Q j 0 u 8 u E f M q t Z U 3 E F T F J r p 2 m i I X P U g G C S + w F p L N e U 3 d A 5 n w a q a M V t 5 t Y V e f w u K D N c 1 i Y 8 B X i t / j v h a G V t W x U h u b r G P v R W 4 v + 8 a Q P l a e a E 0 g 1 w x b p F Z S M x 1 H j V N 5 4 J w x n I N h D K j A h / x W x B D W U Q W t / Y M j d U L w

v 7 J p 7 + z X l h 5 K y K v W F L x s O U U x w j 1 W B g 2 C N Q D L i O o L V n e F 1 U q 8 / M K m 4 7 9 3 D O G B t l / Q 9 3 u O U g L Y 6 J m 4 B G 0 F 0 e x f n W y 6 B g e N E 5 f j 0 F y v x S c f M W Q V r I r w I d g o 5 l K r c M b 9 b X Z + G L v O A C q J U 0 7 Y C a E d E A q e C x d l W q F h A 6 J D 0 W V O j R 1 y m 2 t H k J z E + 1 k 4 X 9 3 y p n w d 4 4 v 6 d i I i r 1 N h 1 d G d y o p q v J e Z / t W Y I v c t 2 x L 0 g B O b R 6 a J e K D D 4 O I k F d 7 l k F M R Y A 6 G S 6 1 s x H R B J K O j w Z r b 0 J Q k G n I 7 i b F Z n Y 8 8 n s Q i 1 Y s E + K x Q r 5 7 n S V Z p S B h 2 i I 5 R H N r p A J X S D y q i K K H p E z + g F v R p P x p v x b n x M W 5 e M d O Y A z c j 4 + g H K L 6 O i < / l a t e x i t > I(X; Y ) < l a t e x i t s h a 1 _ b a s e 6 4 = " w / V O + g O 9 w W t d R Q 8 X f P / V c 4 3 N s g Q = " > A A A C F H i c b V A 9 S w N B E J 2 L X / H 8 i l r a L A Y h N u E u C g o 2 Q R v t I p g P S Y 6 w t 9 k k a 3 b v j t 0 9 M R z 5 D 1 a C / h Y 7 s b X 3 p 9 i 5 S a 4 w i Q 8 G H u / N M D P P j z h T 2 n G + r c z S 8 s r q W n b d 3 t j c 2 t 7 J 7 e 7 V V B h L Q q s k 5 K F s + F h R z g J a 1 U x z 2 o g k x c L n t O 4 P r s Z + / Z F K x c L g T g 8 j 6 g n c C 1 i X E a y N V L s p N C 7 u j 9 u 5 v F N 0 J k C L x E 1 J H l J U 2 r m f V i c k s a C B J h w r 1 X S d S H s J l p o R T k d 2 K 1 Y 0 w m S A e 7 R p a I A F V V 4 y u X a E j o z S Q d 1 Q m g o 0 m q h / J x I s l B o K 3 3 Q K r P t q 3 h u L / 3 n N W H f P v Y Q F U a x p Q K a L u j F H O k T j 1 1 G H S U o 0 H x q C i W T m V k T 6 W G K i T U A z W 3 o S R 3 1 G n m Y + S X w x s m 2 T l T u f z C K p l Y r u S b F 0 e 5 o v X 6 a p Z e E A D q E A L p x B G a 6 h A l U g 8 A D P 8 A p v 1 o v 1 b n 1 Y n 9 P W j J X O 7 M M M r K 9 f S T q e R w = = < / l a t e x i t > sup f n E pxy [f (x, y)] log ⇣ E pxpy h e f (x,y) i⌘o < l a t e x i t s h a 1 _ b a s e 6 4 = " p i M v k Z g O m p l c m r v j R Q T l R 4 x 6 I + Q = " > A A A C l X i c b V F d i 9 Q w F E 3 r 1 z p + 7 K w + C O 5 L c B B G 0 K F d B X 0 R F r / w z R W c 3 Y V J L W n m t h M 2 T U O S y p S Q R 3 + k v 8 F f 4 J u Z a R + c X S + E H M 7 J y c 0 9 K Z T g x i b J r y i + d v 3 G z V t 7 t 0 d 3 7 t 6 7 v z 8 + e H B q m l Y z m L N G N P q 8 o A Y E l z C 3 3 A o 4 V x p o X Q g 4 K

E k + / k O W D W t r k J Y J a s w i T Z T N H N W W M w F + R F o D i r I L W s E i Q E l r M J n b x u X x 0 8 A s c d n o s K T F W / Z f h 6 O 1 M V 1 d h J O b i c x l b U P + T 1 u 0 t n y T O S 5 V a 0 G y v l H Z C m w b v M k e L 7 k G Z k U X A G W a h 7 d i t q K a M h t + Y K d L p a l a c b b e m c Q V t R + N Q l b p 5 W S u g t O j W f p y d v T 1 1 e T 4 3 Z D a H j p E T 9 A U p e g 1 O k a f 0 Q m a I 4 Z + R w f R 4 + g w f h S / j T / E n / q j c T R 4 H q K d i r / 8 B a N / z q Y = < / l a t e x i t > sup f,⌘ n E pxy [f (x, y)] E pxpy h e f (x,y) ⌘ i ⌘+1 o < l a t e x i t s h a 1 _ b a s e 6 4 = " u 5 F l k C y m Q + 6 X 5 O R R c J H b 8 2 Y I Z x U = " > A A A C 5 X i c b V F d i 9 Q w F E 3 r 1 z p + j f r o S 3 A Q V t w Z 2 l F Q 8 G V R B B 9 X c H Y X J r W k m b S N k 7 Y h u Z U p o T / B N / H V X + W D P 8 U 3 0 2 k f 7 O 5 e C J y c c 3 N u c p I o K Q w E w R / P v 3 b 9 x s 1 b B 7 c n d + 7 e u / 9 g + v D R q a l q z f i K V b L S 5 w k 1 X I q S r 0 C A 5 O d K c 1 o k k p 8 l 2 / e d f v a N a y O q 8 j M 0 i k c F z U q R C k b B U f H 0 N 6 n L j d M 5 2 P S I c K C t J a Z W L Z E 8 B W J J Q S F P E v

Figure 1 shows an overview of all the bounds and related MI estimators discussed in this paper.

2. LOWER BOUNDS ON KL DIVERGENCES AND MUTUAL INFORMATION:

Consider two probability distributions P and Q, where P is absolutely continuous w.r.t. Q. Let p and q be their respective densities defined on X ⊂ R d . Their KL divergence is defined as

KL(P, Q) = E x∼P log p(x) q(x) = p(x) log p(x) q(x) dx.

We are interested in the MI between two random variables X, Y where X is defined on X ⊂ R dx , and Y on Y ⊂ R dy . Let p xy be their joint densities and p x , p y the marginals of X and Y respectively. The MI is defined as follows: I(X; Y ) = KL(p xy , p x p y ),

(1) which is the KL divergence between the joint density and the product of marginals. Non-parametric estimation of MI from samples is an important problem in science and machine learning. In what follows, we review variational lower bounds on KL to enable such estimation.

Variational Characterization of KL divergence. Let H be any function space mapping X to R. The first variational characterization of the KL divergence goes back to Donsker & Varadhan (1976) :

EQUATION

where the equality holds if and only if (iif) f * = log(p/q) ∈ H . We refer to this bound as the DV bound.

The second variational representation was introduced in Nguyen et al. (2008) ; Nowozin et al. (2016) and derived through convex duality to be finally stated as follows:

EQUATION

with equality iif f * = log(p/q) ∈ H . We call this bound the f -div bound (as in f -divergence).

From Eq. 2 and Eq. 3 we see that the variational bounds are attempting to estimate the log-likelihood ratio f * = log(p/q), and the tightness of the bound depends on the representation power of H . In order to compare these two lower bounds, observe that log(t) ≤ t -1, t > 0. Therefore log E x∼Q e f (x) ≤ E x∼Q e f (x) -1 which means that for any function space H we have:

EQUATION

from which we conclude that the DV bound is tighter than the f -div bound. Now, given samples {x i , i = 1 . . . N, x i ∼ P}, {y i , i = 1 . . . N, y i ∼ Q}, estimating the KL divergence can be done by computing the variational bound from Monte-Carlo simulation. Specifically, for the DV bound we have the following estimator:

D H DV (P, Q) = sup 1 N N i=1 f (x i ) -log 1 N N i=1 e f (yi) : f ∈ H . (5)

Note that the Mutual Information Neural Estimator (MINE) (Belghazi et al., 2018) considered the above formulation with the hypothesis class H being a neural network. For the f -div bound we have similarly the following estimator:

EQUATION

for which Nguyen et al. (2008) introduced and studied a convex estimator with H being an RKHS.

While DV bound is tighter than the f -div bound, in order to learn the function f using stochastic gradient optimization, f -div is a better fit because the cost function is linear in the expectation, whereas in the DV bound we have a log non-linearity being applied to the expectation. This nonlinearity introduces biases in the mini-batch estimation of the cost function as noted in Belghazi et al. (2018) . In the following, we show how to alleviate this problem and remove the non-linearity at the price of an additional auxiliary variable that will enable better optimization for the DV bound.

An η-trick for the DV Bound. We start with the following elementary Lemma, that gives a variational characterization of the log. All proofs are given in the Appendix A. Lemma 1. Let x > 0, we have: log(x) = min η e -η x + η -1.

Using Lemma 1 we can now linearize the log in the DV bound.

Lemma 2 (η-Donsker-Varadhan). Let H be any function space mapping X to R:

EQUATION

We refer to this bound as η-DV bound.

Note that for η = 0 we recover the f -div bound. Using Lemma 2, we can now rewrite the estimator for the DV bound in Eq. 5 as follows:

EQUATION

enabling unbiased stochastic gradient optimization of the function f . We note that similar variational tricks of non-linearities have been devised for g(η) = √ η in Argyriou et al. (2008) ; Bach et al. (2011) .

3 η-DV BOUND, CONVEXITY, MMD RATIO ESTIMATES AND LAGRANGIANS

We established that the DV bound is tighter than the f -div and derived η-DV as an alternative to DV, enabling unbiased stochastic optimization. However, the role of η in improving the lower bound remains unclear. To highlight its role, we consider the η-DV bound from Eq. 7, and restrict the hypothesis function class to an RKHS, similarly to Nguyen et al. (2008) . Working in the dual, we can compare η-DV estimator to the f -div estimator and further understand this hierarchy of lower bounds. See Figure 2 for an illustration.

For simplicity, and without loss of generality, we let RKHS be a finite dimensional feature map, i.e., H = {f |f (x) = w, Φ(x) , Φ : X → R m , w ∈ R m }. Now for f ∈ H , the loss given in Eq. 8 for η-DV can be rewritten as follows:

EQUATION

)

Following Nguyen et al. (2008) , we consider the following regularized loss: L (w, η) = L(w, η) + Ω(w), and the corresponding sample-based formulation L (w, η) = L(w, η) + Ω(w), where Ω(w) is a convex regularizer, e.g., Ω(w) = λ 2 w 2 2 . The η-DV primal problem can now be defined as: η-DV-P : min w,η L(w, η) + Ω(w).

(11

) sup f 2H,⌘2R E P [f ] e ⌘ E Q ⇥ e f ⇤ ⌘ + 1

< l a t e x i t s h a 1 _ b a s e 6 4 = " 8 5 u u c C 9 e v 3 3 w C a Z X x x Z g 8 2 E m y a g = " In the following, we show that L (w, η) is jointly convex in (w, η) and derive its dual, which will shed light on the nature of the likelihood ratio estimate as well as the role of η.

> A A A C t 3 i c b V F d i x M x F M 2 M X 2 t 1 t e q j L 8 E i C N o y s y u o o L A o w j 5 2 x e 4 u N O O Q S Z N O 2 E x m T O 6 I J e T 3 + J v 8 K b 6 Z a a d i d / d C 4 H D O u b m 5 J 0 W j p I U k + R 3 F N 2 7 e u n 1 n 7 + 7 g 3 v 3 9 B w + H j x 6 f 2 r o 1 j M 9 Y r W p z X l D L l d R 8 B h I U P 2 8 M p 1 W h + F l x 8 a n T z 3 5 w Y 2 W t v 8 K q 4 V l F l 1 o K y S g E K h / + I q 1 e B J 2 D E 0 R q U l E o G V X u 2 L / C h A P d c k X h v n j v i G 0 b T x Q X Q N y W / + z z f 3 j q N + p c E C O X J W R j z L + 5 c X e T v 8 5 / s v U H l / B 9 D x 6 v R + O X O N 0 w x A / y 4 S i Z J O v C V 0 H a g x H q a 5 o P / 5 B F z d q K a 2 C K W j t P k w Y y R w 1 I p r g f k N b y h r I L u u T z A D W t u M 3 c O l C P n w d m g U V t w t G A 1 + z / H Y 5 W 1 q 6 q I j i 7 R e x l r S O v 0 + Y t i L e Z k 7 p p g W u 2 G S R a h a H G 3 e / g h T S c g V o F Q J m R 4 a 2 Y l d R Q B u G P d q Y s D W 1 K y X 7 u b O K K y g + 6 r N L L y V w F p w e T 9 H B y c P J 6 d P S x T 2 0 P P U X P 0 A u U o j f o C B 2 j K Z o h F u 1 H h 9 H 7 6 E P 8 L s 5 j E Z c b a x z 1 P U / Q T s X f / w I Z D N t m < / l a t e x i t > Dual in RKHS ⌘-DV < l a t e x i t s h a 1 _ b a s e 6 4 = " T P e O M O 5 H 8 T L q T u H Y u l U F g 9 K h S U s = " > A A A C J X i c b V B N S 8 N A E N 3 U r 1 q / o u L J S 7 A I X i y J C n o s 6 s G j g q 1 C E 8 p m O 2 m X 7 i Z h d y K W k B / j S d D f 4 k 0 E T / 4 O b 2 5 r D l Z 9 M P B 4 b 4 a Z e W E q u E b X f b c q M 7 N z 8 w v V x d r S 8 s r q m r 2 + 0 d Z J p h i 0 W C I S d R t S D Y L H 0 E K O A m 5 T B V S G A m 7 C 4 d n Y v 7 k D p X k S X + M o h U D S f s w j z i g a q W t v + a H M f U B a + A j 3 G E b 5 / n m 7 6 N p 1 t + F O 4 P w l X k n q p M R l 1 / 7 0 e w n L J M T I B N W 6 4 7 k p B j l V y J m A o u Z n G l L K h r Q P H U N j K k E H + e T 8 w t k 1 S s + J E m U q R m e i / p z I q d R 6 J E P T K S k O 9 G 9 v L P 7 n d T K M T o K c x 2 m G E L P v R V E m H E y c c R Z O j y t g K E a G U K a 4 u d V h A 6 o o Q 5 P Y 1 J a + o u m A s / u p T / J Q F r W a y c r 7 n c x f 0 j 5 o e I e N g 6 u j e v O 0 T K 1 K t s k O 2 S M e O S Z N c k E u S Y s w k p M H 8 k S e r U f r x X q 1 3 r 5 b K 1 Y 5 s 0 m m Y H 1 8 A b V N p e k = < / l a t e x i t > Primal f -div < l a t e x i t s h a 1 _ b a s e 6 4 = " d v S a g N O a d g t i v M I Q H a 7 X 9 H M 2 c Z I = " > A A A C I 3 i c b V B N S 8 N A E N 3 U r 1 q / q j 1 6 C R b B i y W p g h 6 L X j x W s B / Q l r L Z b t q l u 5 u w O y k N I b / F k 6 C / x Z t 4 8 e A P 8 e a 2 z c G 2 P h h 4 v D f D z D w v 5 E y D 4 3 x Z u Y 3 N r e 2 d / G 5 h b / / g 8 K h 4 f N L U Q a Q I b Z C A B 6 r t Y U 0 5 k 7 Q B D D h t h 4 p i 4 X H a 8 s b 3 M 7 8 1 o U q z Q D 5 B H N K e w E P J f E Y w G K l f L H U 9 k f h p F + g U P D + 5 H L B J 2 i + W n Y o z h 7 1 O 3 I y U U Y Z 6 v / j T H Q Q k E l Q C 4 V j r j u u E 0 E u w A k Y 4 T Q v d S N M Q k z E e 0 o 6 h E g u q e 8 n 8 + N Q + N 8 r A 9 g N l S o I 9 V / 9 O J F h o H Q v P d A o M I 7 3 q z c T / v E 4 E / m 0 v Y T K M g E q y W O R H 3 I b A n i V h D 5 i i B H h s C C a K m V t t M s I K E z B 5 L W 0 Z K h y O G J k u f Z J 4 I i 0 U T F b u a j L r p F m t u F e V 6 u N 1 u X a X p Z Z H p + g M X S A X 3 a A a e k B 1 1 E A E x e g Z v a I 3 6 8 V 6 t z 6 s z 0 V r z s p m S m g J 1 v c v e m + l T g = = < / l a t e x i t > sup f 2H E P [f ] E Q e f + 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " 2 X T 4 R 7 s z J l 4 N D v s M v N O 7 r S F t j X M = " > A A A C h n i c b V B N a x s x F N R u 0 s Z 1 0 s Z N j 7 2 I m E C h 1 O z m g / R o G g o 5 O h A n A W t r t P J b W 0 S r X a S 3 I U b o h x b 6 R 3 q L / E G p k w w I h p l 5 v K f J a y U t J s n v K N 7 a f v N 2 p / W u v b v 3 / s N + 5 + P B j a 0 a I 2 A o K l W Z u 5 x b U F L D E C U q u K s N 8 D J X c J v f X y z 8 2 w c w V l b 6 G u c 1 Z C W f a l l I w T F I 4 8 4 D a / Q k + I C u Y F K z k u N M c O U u v X f M N r V n C g q k z C 2 d P H c / / f g f H / i V P S q Y k d M Z Z t 9 e S 1 1 5 D 7 9 c 4 e l X m q 5 y z I 8 7 3 a S X L E F f k n R N u m S N w b j z l 0 0 q 0 Z S g U S h u 7 S h N a s w c N y i F A t 9 m j Y W a i 3 s + h V G g m p d g M 7 f s x 9 O j o E x o U Z n w N N K l + v + E 4 6 W 1 8 z I P y c X N 9 r m 3 E F / z R g 0 W 3 z M n d d 0 g a L F a V D S K Y k U X Z d O J N C B Q z Q P h w s h w K x U z b r j A U P n G l q n h 9 U y K x 4 2 f u L z 0 7 X b o K n 3 e z E t

Convex Estimate in RKHS. In Lemma 3 we first establish the convexity of the η-DV loss function.

Lemma 3. L and L are jointly convex in w and η.

Lε (u, η) = L(u, η)+Ω(u)+εe -η . Our KL estimate is therefore given as D H DV (P, Q) = -L(w * , η * ), where (w * , η * ) = arg min (u,η) Lε (u, η).

η-DV Dual is a Constrained Likelihood Ratio Estimation. Another angle for estimating the KL divergence is through likelihood ratio estimation (Mohamed & Lakshminarayanan, 2016) . Given a ratio estimate r of p/q, the KL divergence can be computed as E Q r log(r), which can be easily estimated using samples from Q.

In Theorem 1, proven in Appendix A, we show that the dual problem (denoted D), corresponding to the primal minimization problem (denoted P) of η-DV, reduces to a constrained likelihood ratio estimation problem (denoted C). Theorem 1. Let Ω * (.) be the Fenchel conjugate of Ω(.). The η-DV bound restricted to an RKHS, amounts to the following regularized convex minimization: P = -(min w,η L(w, η) + Ω(w)), that has the following dual form:

D = min r>0 max η X r(y) log (r(y)) q(y)dy + (η -1) X r(y)q(y)dy -1 + Ω * (∆(r)) ,

where ∆(r) = X Φ(x)p(x)dx -X r(y)q(y)Φ(y)dy.

Noticing that η -1 plays the role of a Lagrangian multiplier, this is equivalent to the following likelihood ratio estimation problem:

C = min r>0 X r(y) log (r(y)) q(y)dy + Ω * X Φ(x)p(x)dx - X r(y)q(y)Φ(y)dy subject to: X r(y)q(y)dy = 1.

Therefore, we have P = D = C. Let (w * , η * ) be an optimizer of P . Let r * be an optimizer of D, then the KL estimate is given by:

D H DV (P, Q) = X r * (y) log (r * (y)) q(y)dy = L(w * , η * ).

The regularizer Ω(w) = λ 2 w 2 can now be given the following interpretation based on the results of Theorem 1. Recall the definition of the MMD (Gretton et al., 2012) between distributions using an RKHS: MMD Φ (P, Q) = E x∼P Φ(x) -E y∼Q Φ(y) . Replacing the Fenchel conjugate Ω * (.) by its expression in Theorem 1, we see that η-DV is equivalent to the following dual (η-DV-D)

EQUATION

) which can be written as a constrained ratio estimation problem (η-DV-C)

EQUATION

Hence, it is clear now that the η-DV optimization problem is equivalent to the constrained likelihood ratio estimation problem r given in Eq. 13, where the ratio is estimated using the MMD distance in the RKHS between rq and p. It is also easy to see that p/q is a feasible point and for the universal feature map MMD Φ (rq, p) = 0 iif r = p/q, therefore, for a universal kernel, p/q is optimal and we recover the KL divergence for r = p/q. When comparing η-DV-D from Eq. 12 and η-DV-C from Eq. 13, we see that η-1 plays the role of a Lagrangian that ensures that rq is indeed a normalized distribution. In practice, we solve the primal problem (P), while the dual problem (D) and its equivalent constrained form (C) explain why this formulation estimates the KL divergence and the role of η as a Lagrangian multiplier that enforces a normalization constraint. Let r * be the solution, then we have:

EQUATION

)

For comparison, the f -div bound, restricted to an RKHS, is equivalent to the following ratio estimation (follows from the proof of Theorem 1 by eliminating max on η, and setting η = 0), and is consistent with the results of Nguyen et al. (2008) (see Eq. 51 therein):

EQUATION

)

Let r * be the optimum, then the KL divergence can be estimated as follows Nguyen et al. (2008) :

EQUATION

)

Comparing D H DV (P, Q) and D H f (P, Q) we see that they both have a relative entropy term but the f -div bound does not impose the normalization constraint on the ratio, which biases the estimate. We end with the following remark: In Theorem 1, if we replace the loss L by its empirical counterpart L from Eq. 9, the equivalent Dual takes the following form:

min ri>0 1 N N i=1 r i log (r i ) + Ω * 1 N N i=1 Φ(x i ) - 1 N N i=1 r i Φ(y i ) , subject to: 1 N N i=1 r i = 1,

and the KL estimate is given by:

D H DV (P, Q) = 1 N N i=1 r * i log (r * i ) = -L(w * , η * ).

From RKHS to Neural Estimation. One shortcoming of the RKHS approach is that the method depends on the choice of feature map Φ. We propose to learn Φ as a deep neural network as in MINE (Belghazi et al., 2018) . Given samples x i from P, y i from Q, the KL estimation problem becomes:

EQUATION

which can be solved using BCD on (w, η, Φ). Note that if Φ(•) is known and fixed, then optimization problem in Eq. 17 becomes convex in η and w. We refer to this bound as η-DV-convex.

What Do Neural Estimators of KL or MI Learn? We conclude with the following observations:

1. Ratio estimation via Feature Matching. KL divergence estimation with variational bounds boils down to a ratio estimation using a form of MMD matching. 2. Choice of Feature/Architecture. The choice of the feature space or the architecture of the neural network introduces a bias in the ratio estimation; also observed in Tschannen et al. ( 2019). 3. Ratio Normalization. η-DV bound introduces a normalization constraint on the ratio, that ensures a better consistent estimate. 4. Impact of Regularizers. The choice of the regularizer dictates the choice of the metric. For instance, Ozair et al. (2019) used gradient penalties as a regularizer, and this corresponds to a ratio matching in the Sobolev discrepancy sense. Please see Appendix A.1 for more details.

4. η-DV MUTUAL INFORMATION ESTIMATION:

We now specify the KL estimators given in Section 3 for the MI estimation problem. Given a function space H defined on X × Y,

EQUATION

where ,y) . Equivalently, with the η-trick we have:

I H f -div (X; Y ) = sup f ∈H E pxy f (x, y) -E px E py e f (x

I H DV (X; Y ) = -inf f ∈H ,η e -η E pxpy e f (x,y) -E pxy f (x, y) + η -1. (19)

Now, given iid samples from marginals x i ∼ p x and ỹi ∼ p y , i = 1 . . . N , and samples from the joint (x i , y i ) ∼ p xy , i = 1 . . . N , we can estimate the MI as follows:

EQUATION

)

when H is an RKHS, η can be seen as a Lagrangian ensuring that the ratio estimation r(x, y) of pxy pxpy is normalized when integrated on p x p y , i.e., η is a Lagrangian associated with the constraint X ×Y r(x, y)p x (x)p y (y)dxdy = 1. In Table 1 we review other variational bounds for MI based on f -div, DV, and η-DV bounds (a-MINE from Poole et al. ( 2019) is discussed next). Improved Donsker-Varadhan for Mutual Information and a-DV Bound Discussion. In the following Lemma we show that for the particular case of MI estimation, the DV bound can be made tighter: Lemma 4. For any function g that maps X × Y to R + we have: ,y) ) where G (X × Y) is the entire space of functions defined on X × Y. For any function space H map X × Y to R we have: ,y) ).

MI Estimator Loss to minimize L Constraints (bound) DV-MINE log 1 N N i=1 e f (x i ,ỹ i ) -1 N N i=1 f (xi, yi) f is a DNN (DV) Unbiased 1 N N i=1 e f (x i , ỹi ) m -1 N N i=1 f (xi, yi) f is a DNN, m running DV-MINE avg. of 1 N N i=1 e f (x i ,ỹ i ) f-MINE 1 N N i=1 e f (x i ,ỹ i ) -1 N N i=1 f (xi, yi) -1 f is in RKHS (convex) (f -div) or f is a DNN a-MINE 1 N N i=1 e f (x i , ỹi ) a(ỹ i ) + log(a(ỹi)) -1 N N i=1 f (xi, yi) -1 a is a DNN, a > 0 (DV) f is a DNN InfoNCE 1 N N i=1 log 1 N N j=1 e f (x i ,ỹ j ) -f (xi, yi) f is a DNN (-) η-MINE e -η 1 N N i=1 e f (x i ,ỹ i ) -N i=1 f (xi, yi) + η -1 f is in RKHS (ours:η-DV) or f is a DNN; η ∈ R η-MINE-convex e -η 1 N N i=1 e w,Φ(x i ,ỹ i ) -N i=1 w, Φ(xi, yi) + η -1 Φ(•) is fixed (ours:η-DV) w ∈ R dim(Φ) , η ∈ R

KL(p x,y , p x p y ) + E px log(E py g(x, y)) ≥ E px,y log(g(x, y)) Therefore: I(X; Y ) = sup f ∈G (X ×Y) E px,y f (x, y) -E py log(E px e f (x

I(X; Y ) ≥ I H a-DV (X; Y ) := sup f ∈H E px,y f (x, y) -E py log(E px e f (x

Using Jensen's inequality, we can easily derive the following hierarchy of lower bounds:

EQUATION

In Theorem 2, we apply the η-trick of Lemma 1 to I H a-DV (X; Y ), where we replace each log E px e f (x,y) using the variational form of log which leads to η(y). The interchangeability between minimization and expectation and going from scalar η for each y to a function η(.) needs some care and we prove it in the Appendix B.1, appealing to the interchangeability principle (Lemma 1 in Dai et al. (2016) ).

Theorem 2 (η-trick for Improved DV Bound). Let H be a space of bounded functions defined on X × Y we have:

I(X; Y ) ≥ -inf f ∈H ,η∈G(Y) E px.py e f (x,y)-η(y) + E py η(y) -1 -E px,y (f (x, y)),

where G (Y) is the entire space of functions defined on Y. Let H η be a function space subset of G (Y) we obtain:

I(X; Y ) ≥ I H a-DV (X; Y ) = sup f ∈H ,η(.)∈Hη E px,y f (x, y) -E px.py e f (x,y)-η(y) -E py η(y) + 1. (22)

Hence, we recover the lower bound given in Poole et al. (2019) (given in Table 1 ), that was derived through other variational principles. In the following, we make a few remarks about I H a-DV (X; Y ):

1. The I H a-DV (X; Y ) bound, as given in Poole et al. (2019) , can be also obtained by setting η(y) = log(a(y)), a(y) > 0. While this seems equivalent, the restriction of a to R + (η is in R) changes the landscape of the optimization problem and the interchangeability principle does not apply in a straightforward way. 2. Poole et al. (2019) refers to a(y) as a "critic" (as in the reinforcement learning literature). As shown in our analysis in Section 3, when we restrict H to an RKHS, η(y) plays a role of a Lagrangian multiplier or a dual potential in a ratio estimation problem. In this case it is enforcing multiple constraints X r(x, y)p(x)dx = 1 for each y, instead of imposing a single constraint X Y r(x, y)p(x)p(y)dxdy = 1 as in the I H η-DV (X; Y ) bound. 3. No Free Lunch: while I H a-DV (X; Y ) is tighter than our I H η-DV (X; Y ) bound, it comes at the price of estimating a function η(y) together with the witness function f . This triggers a higher computational cost and larger estimation errors. 4. We show in Appendix C how I H a-DV (X; Y ) can be extended to conditional MI estimation. 5. Generality: η-DV bound is applicable for general probability distributions P and Q:

KL(P, Q) ≥ D H η-DV (P, Q), while I H a-DV (X; Y ) only works for P = p xy and Q = p x p y .

Finally, in Algorithm 1 we outline the steps of η-MINE for MI estimation.

Algorithm 1 η-MINE (Stochastic BCD )

Inputs: X, Y dataset X ∈ R N ×dx , Y ∈ R N ×dy , such that (x i = X i,. , y i = Y i,.

) ∼ p xy Hyperparameters: α η , α θ (learning rates), n c (number of critic updates) Initialize η, θ parameter of the neural network f θ for i = 1 . . . Maxiter do for j = 1 . . . n c do Fetch a minibatch of size N (x i , y i ) ∼ p xy Fetch a minibatch of size N (x i , ỹi ) ∼ p x p y {ỹ i obtained by permuting rows of

Y } Evaluate L(f θ , η) = e -η 1 N N i=1 e f θ (xi,ỹi) -1 N N i=1 f θ (x i , y i ) + η -1 Stochastic Gradient step on θ: θ ← θ -α ∂ L(f θ ,η) ∂θ {We use ADAM} end for Update η: η ← η -α η ∂ L(f θ ,η) ∂η end for Output: f θ , η, ÎH η-DV (X, Y ) = 1 N N i=1 f θ (x i , y i ) -e -η 1 N N i=1 e f θ (xi,ỹi) -η + 1

5. EXPERIMENTS:

In this Section, we conduct a set of experiments using synthetic and real data on a number of applications to compare the proposed η-MINE MI estimator to the existing baselines.

MI estimation. We compared different MI estimators on three synthetically generated Gaussian datasets [5K training and 1K testing samples]. Each evaluated MI estimator was run 10 times and its average performance (together with the standard deviation) is shown in Fig. 3 .a. As can be seen, 2018) uses a 25-Gaussian dataset to show improvements on GAN Clustering by using MI objective for regularization. As in InfoGAN (Chen et al., 2016) , the conditional generator G is supplied with random codes c along with noise z, we maximize the mutual information between I(G(z, c), c) using η-MINE estimators. In Fig. 3 .b, we repeat this task and establish that η-MINE can recover all the modes within a fewer steps than DV-MINE (50K vs. 140K) and with a stable training.

j F E G E F d E M d s K t t X H X p L b p g a L Y = " > A A A C D H i c b V D L S s N A F J 3 U V 4 2 v q k s 3 w S K 4 s S R V 0 G X x A b p Q K t g H t L F M p p N 2 6 G Q S Z m 6 k J e Q X X L v V b 3 A n b v

K l B 4 O n N A E N X z X p D 8 T + v E Y N / 5 i Z M R D F Q Q c Z B f s w t C K 1 h B V a b S U q A D z T B R D L 9 q 0 W 6 W G I C u q i p l I 7 E U Z e R f m q a u h t n t o l 5 U i 0 W n O N C 8 f 4 k X z q f t J R F e 2 g f H S I H n a I S u k Z l V E E E S f S C X t G b 8 W y 8 G x / G 5 3 g 1 Y 0 x u d t E U j K 9 f X q + b d A = = < / l a t e x i t > Cond. GAN + ⌘-MINE < l a t e x i t s h a 1 _ b a s e 6 4 = " 7 M + v s C j m h m a x v 5 x D S 5 9 2 U F B e L J I = " > A A A C E H i c b V D L S g N B E J z 1 G e N r 1 a O X x S B 4 M e x G Q Y 9 B E f S g R D A P y I Y w O + k k Q 2 Y f z P S G h G V / w r N X / Q Z v 4 t U / 8 B P 8 C y e P g 0 k s a C i q u q m m v E h w h b b 9 b S w t r 6 y u r W c 2 s p t b 2 z u 7 5 t 5 + R Y W x Z F B m o Q h l z a M K B A + g j B w F 1 C I J 1 P c E V L 3 e 9 c i v 9 k E q H g Z P O I y g 4 d N O w N u c U d R S 0 z R d Q O o i D D A 5 v b 9 7 u E m b Z s 7 O 2 2 N Y i 8 S Z k h y Z o t Q 0 f 9 x W y G I f A m S C K l V 3 7 A g b C Z X I m Y A 0 6 8 Y K I s p 6 t A N 1 T Q P q g 2 o k 4 8 9 T 6 1 g r L a s d S j 0 B W m P 1 7 0 V C f a W G v q c 3 f Y p d N e + N x P + 8 e o z t y 0 b C g y h G C N g k q B 0 L C 0 N r V I P V 4 h I Y i q E m l E m u f 7 V Y l 0 r K U J c 1 k 9 K R N O p y N k i z W d 2 N M 9 / E I q k U 8 s 5 Z v v B 4 n i t e T V v K k E N y R E 6 I Q y 5 I k d y S E i k T R v

Self-supervised: Deep InfoMax (Hjelm et al., 2018) . In unsupervised or self-supervised learning, the objective is to build a model without relying on labeled data but using an auxiliary task to learn informative features that can be useful for various downstream tasks. In this experiment we evaluate the effectiveness of the proposed η-MINE estimator for unsupervised feature learning using the recently proposed Deep InfoMax method from Hjelm et al. (2018) . For feature representation we used an encoder similar to DCGAN (Radford et al., 2015) , shown in Fig. 4 .a and evaluated results on CIFAR10 and STL10 datasets (STL10 images were scaled down to match CIFAR10 resolution). Self-Supervised: Jigsaws with MI. The self-supervision Jigsaw pretext task (Noroozi & Favaro, 2016; Kolesnikov et al., 2019) aims at solving an image jigsaw puzzle by predicting the scrambling permutation π. From image X with x = {x 1 . . . x 9 } 3×3 jigsaw patches, and permutation y = π i : [1, 9] → [1, 9], scrambled patches x πi = {x πi(1) . . . x πi(9) } generate the puzzle. Each patch is passed through an encoder E, which needs to learn meaningful representations such that a classifier C J can solve the puzzle by predicting the scrambling order π i (Noroozi & Favaro, 2016) DV-MINE η-MINE CE top1 8.5 ± 1.3 11.0 ± 1.1 12.9 ± 0.3 top5 20.0 ± 2.5 24.1 ± 2.2 28.1 ± 0.6 top10 27.8 ± 3.1 32.7 ± 2.2 37.7 ± 0.6 ⇡ < l a t e x i t s h a 1 _ b a s e 6 4 = " s s r x X j 8 3 Q 3

b N + D 6 g c + n q q G i B z R k = " > A A A B 6 n i c b V A 9 S w N B E J 2 L X z F + R S 1 t F o N g F e 6 i o G X A x s I i o v m A 5 A h 7 m 7 l k y d 7 e s b s n h C M / w c Z C E V t / k Z 3 / x k 1 y h S Y + G H i 8 N 8 P M v C A R X B v X / X Y K a + s b m 1 v F 7 d L O 7 t 7 + Q f n w q K X j V D F s s l j E q h N Q j Y J L b B p u B H Y S h T Q K B L a D 8 c 3 M b z + h 0 j y W j 2 a S o B / R o e Q h Z 9 R Y 6 a G X 8 H 6 5 4 l b d O c g q 8 X J S g R y N f v m r N 4 h Z G q E 0 T F C t u 5 6 b G D + j y n A m c F r q p R o T y s Z 0 i F 1 L J Y 1 Q + 9 n 8 1 C k 5 s 8 q A h L G y J Q 2 Z q 7 8 n M h p p P Y k C 2 x l R M 9 L L 3 k z 8 z + u m J r z 2 M y 6 T 1 K B k i 0 V h K o i J y e x v M u A K m R E T S y h T 3 N 5 K 2 I g q y o x N p 2 R D 8 J Z f X i W t W t W 7 q N b u L y v 1 u z y O I p z A K Z y D B 1 d Q h 1 t o Q B M Y D O E Z X u H N E c 6 L 8 + 5 8 L F o L T j 5 z D H / g f P 4 A V A 2 N 2 w = = < / l a t e x i t > y < l a t e x i t s h a 1 _ b a s e 6 4 = " T v 2 v u d T N r 0 U M X u 1 G t j 8 i + e 1 t M F 0 = " > A A A B 6 H i c b V A 9 S w N B E J 2 L X z F + R S 1 t F o N g F e 6 i o G X A x s I i A R M D y R H 2 N n P J m r 2 9 Y 3 d P C E d + g Y 2 F I r b + J D v / j Z v k C k 1 8 M P B 4 b 4 a Z e U E i u D a u + + 0 U 1 t Y 3 N r e K 2 6 W d 3 b 3 9 g / L h U V v H q W L Y Y r G I V S e g G g W X 2 D L c C O w k C m k U C H w I x j c z / + E J l e a x v D e T B P 2 I D i U P O a P G S s 1 J v 1 x x q + 4 c Z J V 4 O a l A j k a / / N U b x C y N U B o m q N Z d z 0 2 M n 1 F l O B M 4 L f V S j Q l l Y z r E r q W S R q j 9 b H 7 o l J x Z Z U D C W N m S h s z V 3 x M Z j b S e R I H t j K g Z 6 W V v J v 7 n d V M T X v s Z l 0 l q U L L F o j A V x M R k 9 j U Z c I X M i I k l l C l u b y V s R B V l x m Z T s i F 4 y y + v k n a t 6 l 1 U a 8 3 L S v 0 u j 6 M I J 3 A K 5 + D B F d T h F h r Q A g Y I z / A K b 8 6 j 8 + K 8 O x + L 1 o K T z x z D H z i f P + w N j Q s = < / l a t e x i t > x⇡ < l a t e x i t s h a 1 _ b a s e 6 4 = " 4 L q x O 8 g R Z 3 U v k o 9 e e W D Q Z Q w i q J o = " > A A A B 7 n i c b V B N S w M x E J 2 t X 7 V + V T 1 6 C R b B U 9 m t g h 4 L X j x 4 q G A / o F 1 K N s 2 2 o U k 2 J F m x L P 0 R X j w o 4 t X f 4 8 1 / Y 9 r u Q V s f D D z e m 2 F m X q Q 4 M 9 b 3 v 7 3 C 2 v r G 5 l Z x u 7 S z u 7 d / U D 4 8 a p k k 1 Y Q 2 S c I T 3 Y m w o Z x J 2 r T M c t p R m m I R c d q O x j c z v / 1 I t W G J f L A T R U O B h 5 L F j G D r p P Z T P + s p N u 2 X K 3 7 V n w O t k i A n F c j R 6 J e / e o O E p I J K S z g 2 p h v 4 y o Y Z 1 p Y R T q e l X m q o w m S M h 7 T r q M S C m j C b n z t F Z 0 4 Z o D j R r q R F c / X 3 R I a F M R M R u U 6 B 7 c g s e z P x P 6 + b 2 v g 6 z J h U q a W S L B b F K U c 2 Q b P f 0 Y B p S i y f O I K J Z u 5 W R E Z Y Y 2 J d Q i U X Q r D 8 8 i p p 1 a r B R b V 2 f 1 m p 3 + V x F O E E T u E c A r i C O t x C A 5 p A Y A z P 8 A p v n v J e v H f v Y 9 F a 8 P K Z Y / g D 7 / M H r W 6 P 0 g = = < / l a t e x i t >

x < l a t e x i t s h a 1 _ b a s e 6 4 = " 7 Q K 3 0 v o i j p a N / s 9 A A P l 2 A H o w g g 8 

= " > A A A B 6 H i c b V A 9 S w N B E J 2 L X z F + R S 1 t F o N g F e 6 i o G X A x s I i A f M B y R H 2 N n P J m r 2 9 Y 3 d P D C G / w M Z C E V t / k p 3 / x k 1 y h S Y + G H i 8 N 8 P M v C A R X B v X / X Z y a + s b m 1 v 5 7 c L O 7 t 7 + Q f H w q K n j V D F s s F j E q h 1 Q j Y J L b B h u B L Y T h T Q K B L a C 0 c 3 M b z 2 i 0 j y W 9 2 a c o B / R g e Q h Z 9 R Y q f 7 U K 5 b c s j s H W S V e R k q Q o d Y r f n X 7 M U s j l I Y J q n X H c x P j T 6 g y n A m c F r q p x o S y E R 1 g x 1 J J I 9 T + Z H 7 o l J x Z p U / C W N m S h s z V 3 x M T G m k 9 j g L b G V E z 1 M v e T P z P 6 6 Q m v P Y n X C a p Q c k W i 8 J U E B O T 2 d e k z x U y I 8 a W U K a 4 v Z W w I V W U G Z t N w Y b g L b + 8 S p q V s n d R r t Q v S 9 W 7 L I 4 8 n M A p n I M H V 1 C F W 6 h B A x g g P M M r v D k P z o v z 7 n w s W n N O N n M M f + B 8 / g D q i Y 0 K < / l a t e x i t > E(x⇡) < l a t e x i t s h a 1 _ b a s e 6 4 = " B k a W k D b 1 M M Y g Y p 0 Y C H + p W d H y 8 E Q = " > A A A B 8 X i c b V B N S w M x E J 2 t X 7 V + V T 1 6 C R a h X s p u F f R Y E M G D h w r 2 A 9 u l Z N N s G 5 p k l y Q r l q X / w o s H R b z 6 b 7 z 5 b 0 z b P W j r g 4 H H e z P M z A t i z r R x 3 W 8 n t 7 K 6 t r 6 R 3 y x s b e / s 7 h X 3 D 5 o 6 S h S h D R L x S L U D r C l n k j Y M M 5 y 2 Y 0 W x C D h t B a O r q d 9 6 p E q z S N 6 b c U x 9 g Q e S h Y x g Y 6 W H 6 / J T L + 3 G b H L a K 5 b c i j s D W i Z e R k q Q o d 4 r f n X 7 E U k E l Y Z w r H X H c 2 P j p 1 g Z R j i d F L q J p j E m I z y g H U s l F l T 7 6 e z i C T q x S h + F k b I l D Z q p v y d S L L Q e i 8 B 2 C m y G e t G b i v 9 5 n c S E l 3 7 K Z J w Y K s l 8 U Z h w Z C I 0 f R / 1 m a L E 8 L E l m C h m b 0 V k i B U m x o Z U s C F 4 i y 8 v k 2 a 1 4 p 1 V q n f n p d p t F k c e j u A Y y u D B B d T g B u r Q A A I S n u E V 3 h z t v D j v

CE Loss:

< l a t e x i t s h a 1 _ b a s e 6 4 = " E P A A Y 6 0 j X N a 8 i w

4 k F 1 1 d v 9 k Q v q E = " > A A A B 7 n i c b V D L S g N B E O z 1 G e M r 6 t H L Y B A 8 h d 1 4 0 G M g C B 5 y i G A e k C x h d j K b D J n H M j M r h C U f 4 c W D I l 7 9 H m / + j Z N k D 5 p Y 0 F B U d d P d F S W c G e v 7 3 9 7 G 5 t b 2 z m 5 h r 7 h / c H h 0 X D o 5 b R u V a k J b R H G l u x E 2 l D N J W 5 Z Z T r u J p l h E n H a i S X 3 u d 5 6 o N k z J R z t N a C j w S L K Y E W y d 1 K n f o Y Y y Z l A q + x V / A b R O g p y U I U d z U P r q D x V J B Z W W c G x M L / A T G 2 Z Y W 0 Y 4 n R X 7 q a E J J h M 8 o j 1 H J R b U h N n i 3 B m 6 d M o Q x U q 7 k h Y t 1 N 8 T G R b G T E X k O g W 2 Y 7 P q z c X / v F 5 q 4 9 s w Y z J J L Z V k u S h O O b I K z X 9 H Q 6 Y p s X z q C C a a u V s R G W O N i X U J F V 0 I w e r L 6 6 R d r Q T X l e p D t V x r 5 H E U 4 B w u 4 A o C u I E a 3 E M T W k B g A s / w C m 9 e 4 r 1 4 7 9 7 H s n X D y 2 f O 4 A + 8 z x + N / 4 8 V < / l a t e x i t > ⇡ < l a t e x i t s h a 1 _ b a s e 6 4 = " K 3 N 4 r z N 6 Q k D G J C R J X 8 d O f I L / b v k = " > A A A B 8 n i c b V B N S 8 N A E N 3 4 W e t X 1 a O X x S J 4 K k k V 9 F j w 4 s F D B f s B S S i b z a Z d u t k N u x O h h P 4 M L x 4 U 8 e q v 8 e a / c d v m o K 0 P B h 7 v z T A z L 8 o E N + C 6 3 8 7 a + s b m 1 n Z l p 7 q 7 t 3 9 w W D s 6 7 h q V a 8 o 6 V A m l + x E x T H D J O s B B s H 6 m G U k j w X r R + H b m 9 5 6 Y N l z J R 5 h k L E z J U P K E U w J W 8 g P g I m Z F k P H p o F Z 3 G + 4 c e J V 4 J a m j E u 1 B 7 S u I F c 1 T J o E K Y o z v u R m E B d H A q W D T a p A b l h E 6 J k P m W y p J y k x Y z E + e 4 n O r x D h R 2 p Y E P F d / T x Q k N W a S R r Y z J T A y y 9 5 M / M / z c 0 h u w o L L L A c m 6 W J R k g s M C s / + x z H X j I K Y W E K o 5 v Z W T E d E E w o 2 p a o N w V t + e Z V

0 m w 3 v s t F 8 u K q 3 7 s s 4 K u g U n a E L 5 K F r 1 E J 3 q I 0 6 i C K F n t E r e n P A e X H e n Y 9 F 6 5 p T z p y g P 3 A + f w C 3 0 Z G R < / l a t e x i t > Encoder < l a t e x i t s h a 1 _ b a s e 6 4 = " 9 e q H l 8 R m g C D m 8 n + y

c Q 4 D Y f 8 r C 7 8 = " > A A A B 7 n i c b V B N S 8 N A E J 3 4 W e t X 1 a O X x S J 4 K k k 9 6 L E g g g c P F e w H t K F s N p N 2 6 W Y T d j d C C f 0 R X j w o 4 t X f 4 8 1 / 4 7 b N Q V s f D D z e m 2 F m X p A K r o 3 r f j t r 6 x u b W 9 u l n f L u 3 v 7 B Y e X o u K 2 T T D F s s U Q k q h t Q j Y J L b B l u B H Z T h T Q O B H a C 8 c 3 M 7 z y h 0 j y R j 2 a S o h / T o e Q R Z 9 R Y q X M r W R K i G l S q b s 2 d g 6 w S r y B V K N A c V L 7 6 Y c K y G K V h g m

r d 8 9 z U + D l V h j O B 0 3 I / 0 5 h S N q Z D 7 F k q a Y z a z + f n T s m 5 V U I S J c q W N G S u / p 7 I a a z 1 J A 5 s Z 0 z N S C 9 7 M / E / r 5 e Z 6 N r P u U w z g 5

I t F k W Z I C Y h s 9 9 J y B U y I y a W U K a 4 v Z W w E V W U G Z t Q 2 Y b g L b + 8 S t r 1 m n d Z q z / U q 4 3 7 I o 4 S n M I Z X I A H V 9 C A O 2 h C C x i M 4 R l e 4 c 1 J n R f n 3 f l Y t K 4 5 x c w J / I H z + Q N E l I + M < / l a t e x i t > Classifier < l a t e x i t s h a 1 _ b a s e 6 4 = " v I c v T g T g m z y 4 V 1 x r d w 1 p a N E k + X w = " > A A A B 8 X i c b V C 7 T s M w F L 0 p r 1 J e B U Y W i w q J q U r K A G O l L g w M R a I P 0 U a V 4 9 6 2 V h 0 n s h 2 k K u p f s D C A E C t / w 8 b f 4 L Q Z o O V I l o 7 P u d e + 9 w S x 4 N q 4 7 r d T 2 N j c 2 t 4 p 7 p b 2 9 g 8 O j 8 r H J 2 0 d J Y p h i 0 U i U t 2 A a h R c Y s t w I 7 A b K 6 R h I L A T T B u Z 3 3 l C p X k k H 8 w s R j + k Y 8 l H n F F j p c e G o F r b K 6 p B u e J W 3 Q X I O v F y U o E c z U H 5 q z + M W B K i N C

x 7 p e e 5 s f F T q g x n A u e l f q I x p m x K x 9 i z V N I Q t Z 8 u J p 6 T C 6 s M y S h S 9 k h D F u r v j p S G W s / C w F a G 1 E z 0 q p e J / 3 m 9

x I x u / J T L O D E o 2 f K j U S K I i U i 2 P h l y h c y I m S W U K W 5 n J W x C F W X G h l S y I X i r K 6 + T d q 3 q X V V r 9 7 V K / S 6 P o w h n c A 6 X 4 M E 1 1 O E W m t A C B h K e 4 R X e H O 2 8 O O / O x 7 K 0 4 O Q 9 p / A H z u c P q b K Q 7 w = = < / l a t e x i t > (a)

< l a t e x i t s h a 1 _ b a s e 6 4 = " k 1 e S H Q J 5 5 0 9

+ p R U / J n B X s E 7 Q p 8 0 = " > A A A B 6 n i c b V A 9 S w N B E J 2 L X z F + R S 1 t F o M Q m 3 A X B S 0 D N h Y W E c 0 H J E e Y 2 + w l S / b 2 j t 0 9 I Y T 8 B B s L R W z 9 R X b + G z f J F Z r 4 Y O D x 3 g w z 8 4 J E c G 1 c 9 9 v J r a 1 v b G 7 l t w s 7 u 3 v 7 B 8 X D o 6 a O U 0 V Z g 8 Y i V u 0 A N R N c s o b h R r B 2 o h h G g W C t Y H Q z 8 1 t P T G k e y 0 c z T p g f 4 U D y k F M 0 V n o o 4 3 m v W H I r 7 h x k l X g Z K U G G e q / 4 1 e 3 H N I 2 Y N F S g 1 h 3 P T Y w / Q W U 4 F W x a 6 K a a J U h H O G A d S y V G T P u T + a l T c m a V P g l j Z U s a M l d / T 0 w w 0 n o c B b Y z Q j P U y 9 5 M / M / r p C a 8 9 i d c J q l h k i 4 W h a k g J i a z v 0 m f K 0 a N G F u C V H F 7 K 6 F D V E i N T a d g Q / C W X 1 4 l z W r F u 6 h U 7 y 9 L t b s s j j y c w C m U w Y M r q M E t 1 K E B F A b w D K / w 5 g j n x X l 3 P h a t O S e b O Y Y / c D 5 / A I z 7 j V g = < / l a t e x i t > ⇡ < l a t e x i t s h a 1 _ b a s e 6 4 = " s s r x X j 8 3 Q 3 b N + D 6 g c + n q q G i B z R k = " > A A A B 6 n i c b V A 9 S w N B E J 2 L X z F + R S 1 t F o N g F e 6 i o G X A x s I i o v m A 5 A h 7 m 7 l k y d 7 e s b s n h C M / w c Z C E V t / k Z 3 / x k 1 y h S Y + G H i 8 N 8 P M v C A R X B v X / X Y K a + s b m 1 v F 7 d L O 7 t 7 + Q f n w q K X j V D F s s l j E q h N Q j Y J L b B p u B H Y S h T Q K B L a D 8 c 3 M b z + h 0 j y W j 2 a S o B / R o e Q h Z 9 R Y 6 a G X 8 H 6 5 4 l b d O c g q 8 X J S g R y N f v m r N 4 h Z G q E 0 T F C t u 5 6 b G D + j y n A m c F r q p R o T y s Z 0 i F 1 L J Y 1 Q + 9 n 8 1 C k 5 s 8 q A h L G y J Q 2 Z q 7 8 n M h p p P Y k C 2 x l R M 9 L L 3 k z 8 z + u m J r z 2 M y 6 T 1 K B k i 0 V h K o i J y e x v M u A K m R E T S y h T 3 N 5 K 2 I g q y o x N p 2 R D 8 J Z f X i W t W t W 7 q N b u L y v 1 u z y O I p z A K Z y D B 1 d Q h 1 t o Q B M Y D O E Z X u H N E c 6 L 8 + 5 8 L F o L T j 5 z D H / g f P 4 A V A 2 N 2 w = = < / l a t e x i t > y < l a t e x i t s h a 1 _ b a s e 6 4 = " T v 2 v u d T N r 0 U M X u 1 G t j 8 i + e 1 t M F 0 = " > A A A B 6 H i c b V A 9 S w N B E J 2 L X z F + R S 1 t F o N g F e 6 i o G X A x s I i A R M D y R H 2 N n P J m r 2 9 Y 3 d P C E d + g Y 2 F I r b + J D v / j Z v k C k 1 8 M P B 4 b 4 a Z e U E i u D a u + + 0 U 1 t Y 3 N r e K 2 6 W d 3 b 3 9 g / L h U V v H q W L Y Y r G I V S e g G g W X 2 D L c C O w k C m k U C H w I x j c z / + E J l e a x v D e T B P 2 I D i U P O a P G S s 1 J v 1 x x q + 4 c Z J V 4 O a l A j k a / / N U b x C y N U B o m q N Z d z 0 2 M n 1 F l O B M 4 L f V S j Q l l Y z r E r q W S R q j 9 b H 7 o l J x Z Z U D C W N m S h s z V 3 x M Z j b S e R I H t j K g Z 6 W V v J v 7 n d V M T X v s Z l 0 l q U L L F o j A V x M R k 9 j U Z c I X M i I k l l C l u b y V s R B V l x m Z T s i F 4 y y + v k n a t 6 l 1 U a 8 3 L S v 0 u j 6 M I J 3 A K 5 + D B F d T h F h r Q A g Y I z / A K b 8 6 j 8 + K 8 O x + L 1 o K T z x z D H z i f P + w N j Q s = < / l a t e x i t > x⇡ < l a t e x i t s h a 1 _ b a s e 6 4 = " 4 L q x O 8 g R Z 3 U v k o 9 e e W D Q Z Q w i q J o = " > A A A B 7 n i c b V B N S w M x E J 2 t X 7 V + V T 1 6 C R b B U 9 m t g h 4 L X j x 4 q G A / o F 1 K N s 2 2 o U k 2 J F m x L P 0 R X j w o 4 t X f 4 8 1 / Y 9 r u Q V s f D D z e m 2 F m X q Q 4 M 9 b 3 v 7 3 C 2 v r G 5 l Z x u 7 S z u 7 d / U D 4 8 a p k k 1 Y Q 2 S c I T 3 Y m w o Z x J 2 r T M c t p R m m I R c d q O x j c z v / 1 I t W G J f L A T R U O B h 5 L F j G D r p P Z T P + s p N u 2 X K 3 7 V n w O t k i A n F c j R 6 J e / e o O E p I J K S z g 2 p h v 4 y o Y Z 1 p Y R T q e l X m q o w m S M h 7 T r q M S C m j C b n z t F Z 0 4 Z o D j R r q R F c / X 3 R I a F M R M R u U 6 B 7 c g s e z P x P 6 + b 2 v g 6 z J h U q a W S L B b F K U c 2 Q b P f 0 Y B p S i y f O I K J Z u 5 W R E Z Y Y 2 J d Q i U X Q r D 8 8 i p p 1 a r B R b V 2 f 1 m p 3 + V x F O E E T u E c A r i C O t x C A 5 p A Y A z P 8 A p v n v J e v H f v Y 9 F a 8 P K Z Y / g D 7 / M H r W 6 P 0 g = = < / l a t e x i t > x < l a t e x i t s h a 1 _ b a s e 6 4 = " 7 Q K 3 0 v o i j p a N / s 9 A A P l 2 A H o w g g 8 = " > A A A B 6 H i c b V A 9 S w N B E J 2 L X z F + R S 1 t F o N g F e 6 i o G X A x s I i A f M B y R H 2 N n P J m r 2 9 Y 3 d P D C G / w M Z C E V t / k p 3 / x k 1 y h S Y + G H i 8 N 8 P M v C A R X B v X / X Z y a + s b m 1 v 5 7 c L O 7 t 7 + Q f H w q K n j V D F s s F j E q h 1 Q j Y J L b B h u B L Y T h T Q K B L a C 0 c 3 M b z 2 i 0 j y W 9 2 a c o B / R g e Q h Z 9 R Y q f 7 U K 5 b c s j s H W S V e R k q Q o d Y r f n X 7 M U s j l I Y J q n X H c x P j T 6 g y n A m c F r q p x o S y E R 1 g x 1 J J I 9 T + Z H 7 o l J x Z p U / C W N m S h s z V 3 x M T G m k 9 j g L b G V E z 1 M v e T P z P 6 6 Q m v P Y n X C a p Q c k W i 8 J U E B O T 2 d e k z x U y I 8 a W U K a 4 v Z W w I V W U G Z t N w Y b g L b + 8 S p q V s n d R r t Q v S 9 W 7 L I 4 8 n M A p n I M H V 1 C F W 6 h B A x g g P M M r v D k P z o v z 7 n w s W n N O N n M M f + B 8 / g D q i Y 0 K < / l a t e x i t > E(x⇡) < l a t e x i t s h a 1 _ b a s e 6 4 = " B k a W k D b 1 M M Y g Y p 0 Y C H + p W d H y 8 E Q = " > A A A B 8 X i c b V B N S w M x E J 2 t X 7 V + V T 1 6 C R a h X s p u F f R Y E M G D h w r 2 A 9 u l Z N N s G 5 p k l y Q r l q X / w o s H R b z 6 b 7 z 5 b 0 z b P W j r g 4 H H e z P M z A t i z r R x 3 W 8 n t 7 K 6 t r 6 R 3 y x s b e / s 7 h X 3 D 5 o 6 S h S h D R L x S L U D r C l n k j Y M M 5 y 2 Y 0 W x C D h t B a O r q d 9 6 p E q z S N 6 b c U x 9 g Q e S h Y x g Y 6 W H 6 / J T L + 3 G b H L a K 5 b c i j s D W i Z e R k q Q o d 4 r f n X 7 E U k E l Y Z w r H X H c 2 P j p 1 g Z R j i d F L q J p j E m I z y g H U s l F l T 7 6 e z i C T q x S h + F k b I l D Z q p v y d S L L Q e i 8 B 2 C m y G e t G b i v 9 5 n c S E l 3 7 K Z J w Y K s l 8 U Z h w Z C I 0 f R / 1 m a L E 8 L E l m C h m b 0 V k i B U m x o Z U s C F 4 i y 8 v k 2 a 1 4 p 1 V q n f n p d p t F k c e j u A Y y u D B B d T g B u r Q A A I S n u E V 3 h z t v D j v z s e 8 N e d k M 4 f w B 8 7 n D w Z r k I Y = < / l a t e x i t > Encoder < l a t e x i t s h a 1 _ b a s e 6 4 = " 9 e q H l 8 R m g C D m 8 n + y c Q 4 D Y f 8 r C 7 8 = " > A A A B 7 n i c b V B N S 8 N A E J 3 4 W e t X 1 a O X x S J 4 K k k 9 6 L E g g g c P F e w H t K F s N p N 2 6 W Y T d j d C C f 0 R X j w o 4 t X f 4 8 1 / 4 7 b N Q V s f D D z e m 2 F m X p A K r o 3 r f j t r 6 x u b W 9 u l n f L u 3 v 7 B Y e X o u K 2 T T D F s s U Q k q h t Q j Y J L b B l u B H Z T h T Q O B H a C 8 c 3 M 7 z y h 0 j y R j 2 a S o h / T o e Q R Z 9 R Y q X M r W R K i G l S q b s 2 d g 6 w S r y B V K N A c V L 7 6 Y c K y G K V h g m r d 8 9 z U + D l V h j O B 0 3 I / 0 5 h S N q Z D 7 F k q a Y z a z + f n T s m 5 V U I S J c q W N G S u / p 7 I a a z 1 J A 5 s Z 0 z N S C 9 7 M / E / r 5 e Z 6 N r P u U w z g 5 I t F k W Z I C Y h s 9 9 J y B U y I y a W U K a 4 v Z W w E V W U G Z t Q 2 Y b g L b + 8 S t r 1 m n d Z q z / U q 4 3 7 I o 4 S n M I Z X I A H V 9 C A O 2 h C C x i M 4 R l e 4 c 1 J n R f n 3 f l Y t K 4 5 x c w J / I H z + Q N E l I + M < / l a t e x i t >

MI Loss:

< l a t e x i t s h a 1 _ b a s e 6 4 = " 9 o x F y q I a S g U V Z M l 4 e i r y 9

I f O e m Q = " > A A A B 7 n i c b V B N S w M x E J 3 1 s 9 a v q k c v w S J 4 K r v 1 o M e C F 4 U K F e w H t E v J p t k 2 N J u E J C u U p T / C i w d F v P p 7 v P l v T N s 9 a O u D g c d 7 M 8 z M i x R n x v r + t 7 e 2 v r G 5 t V 3 Y K e 7 u 7 R 8 c l o 6 O W 0 a m m t A m k V z q T o Q N 5 U z Q p m W W 0 4 7 S F C c R p + 1 o f D P z 2 0 9 U G y b F o 5 0 o G i Z 4 K F j M C L Z O a t / f o b o 0 p l 8 q + x V / D r R K g p y U I U e j X / r q D S R J E y o s 4 d i Y b u A r G 2 Z Y W 0 Y 4 n R Z 7 q a E K k z E e 0 q 6 j A i f U h N n 8 3 C k 6 d 8 o A x V K 7 E h b N 1 d 8 T G U 6 M m S S R 6 0 y w H Z l l b y b + 5 3 V T G 1 + H G R M q t V S Q x a I 4 5 c h K N P s d D Z i m x P K J I 5 h o 5 m 5 F Z I Q 1 J t Y l V H Q h B M s v r 5 J W t R J c V q o P 1 X K t n s d R g F M 4 g w s I 4 A p q c A s N a A K B M T z D K 7

x 5 y n v x 3 r 2 P R e u a l 8 + c w B 9 4 n z + j h 4 8 j < / l a t e x i t > (b) < l a t e x i t s h a 1 _ b a s e 6 4 = " W O 9 T f 8 N t z 4 j 4 4 q e 7 P 1 n I 0

+ b O R J k = " > A A A B 6 n i c b V A 9 S w N B E J 2 L X z F + R S 1 t F o M Q m 3 A X B S 0 D N h Y W E c 0 H J E f Y 2 + w l S / b 2 j t 0 5 I Y T 8 B B s L R W z 9 R X b + G z f J F Z r 4 Y O D x 3 g w z 8 4 J E C o O u + + 3 k 1 t Y 3 N r f y 2 4 W d 3 b 3 9 g + L h U d P E q W a 8 w W I Z 6 3 Z A D Z d C 8 Q Y K l L y d a E 6 j Q P J W M L q Z + a 0 n r o 2 I 1 S O O E + 5 H d K B E K B h F K z 2 U g / N e s e R W 3 D n I K v E y U o I M 9 V 7 x q 9 u P W R p x h U x S Y z q e m 6 A / o R o F k 3 x a 6 K a G J 5 S N 6 I B 3 L F U 0 4 s a f z E + d k j O r 9 E k Y a 1 s K y V z 9 P T G h k T H j K L C d E c W h W f Z m 4 n 9 e J 8 X w 2 p 8 I l a T I F V s s C l N J M C a z v 0 l f a M 5 Q j i 2 h T A t 7 K 2 F D q i l D m 0 7 B h u A t v 7 x K m t W K d 1 G p 3 l + W a n d Z H H k 4 g V M o g w d X U I N b q E M D G A z g G V 7 h z Z H O i / P u f C x a c 0 4 2 c w x / 4 H z + A I 6 A j V k = < / l a t e x i t > x < l a t e x i t s h a 1 _ b a s e 6 4 = " 7 Q K 3 0 v o i j p a N / s 9 A A P l 2 A H o w g g 8 = " > A A A B 6 H i c b V A 9 S w N B E J 2 L X z F + R S 1 t F o N g F e 6 i o G X A x s I i A f M B y R H 2 N n P J m r 2 9 Y 3 d P D C G / w M Z C E V t / k p 3 / x k 1 y h S Y + G H i 8 N 8 P M v C A R X B v X / X Z y a + s b m 1 v 5 7 c L O 7 t 7 + Q f H w q K n j V D F s s F j E q h 1 Q j Y J L b B h u B L Y T h T Q K B L a C 0 c 3 M b z 2 i 0 j y W 9 2 a c o B / R g e Q h Z 9 R Y q f 7 U K 5 b c s j s H W S V e R k q Q o d Y r f n X 7 M U s j l I Y J q n X H c x P j T 6 g y n A m c F r q p x o S y E R 1 g x 1 J J I 9 T + Z H 7 o l J x Z p U / C W N m S h s z V 3 x M T G m k 9 j g L b G V E z 1 M v e T P z P 6 6 Q m v P Y n X C a p Q c k W i 8 J U E B O T 2 d e k z x U y I 8 a W U K a 4 v Z W w I V W U G Z t N w Y b g L b + 8 S p q V s n d R r t Q v S 9 W 7 L I 4 8 n M A p n I M H V 1 C F W 6 h B A x g g P M M r v D k P z o v z 7 n w s W n N O N n M M f + B 8 / g D q i Y 0 K < / l a t e x i t > CE Loss < l a t e x i t s h a 1 _ b a s e 6 4 = " E P A A Y 6 0 j X N a 8 i w 4 k F 1 1 d v 9 k Q v q E = " > A A A B 7 n i c b V D L S g N B E O z 1 G e M r 6 t H L Y B A 8 h d 1 4 0 G M g C B 5 y i G A e k C x h d j K b D J n H M j M r h C U f 4 c W D I l 7 9 H m / + j Z N k D 5 p Y 0 F B U d d P d F S W c G e v 7 3 9 7 G 5 t b 2 z m 5 h r 7 h / c H h 0 X D o 5 b R u V a k J b R H G l u x E 2 l D N J W 5 Z Z T r u J p l h E n H a i S X 3 u d 5 6 o N k z J R z t N a C j w S L K Y E W y d 1 K n f o Y Y y Z l A q + x V / A b R O g p y U I U d z U P r q D x V J B Z W W c G x M L / A T G 2 Z Y W 0 Y 4 n R X 7 q a E J J h M 8 o j 1 H J R b U h N n i 3 B m 6 d M o Q x U q 7 k h Y t 1 N 8 T G R b G T E X k O g W 2 Y 7 P q z c X / v F 5 q 4 9 s w Y z J J L Z V k u S h O O b I K z X 9 H Q 6 Y p s X z q C C a a u V s R G W O N i X U J F V 0 I w e r L 6 6 R d r Q T X l e p D t V x r 5 H E U 4 B w u 4 A o C u I E a 3 E M T W k B g A s / w C m 9 e 4 r 1 4 7 9 7 H s n X D y 2 f O 4 A + 8 z x + N / 4 8 V < / l a t e x i t > Encoder < l a t e x i t s h a 1 _ b a s e 6 4 = " 9 e q H l 8 R m g C D m 8 n + y c Q 4 D Y f 8 r C 7 8 = " > A A A B 7 n i c b V B N S 8 N A E J 3 4 W e t X 1 a O X x S J 4 K k k 9 6 L E g g g c P F e w H t K F s N p N 2 6 W Y T d j d C C f 0 R X j w o 4 t X f 4 8 1 / 4 7 b N Q V s f D D z e m 2 F m X p A K r o 3 r f j t r 6 x u b W 9 u l n f L u 3 v 7 B Y e X o u K 2 T T D F s s U Q k q h t Q j Y J L b B l u B H Z T h T Q O B H a C 8 c 3 M 7 z y h 0 j y R j 2 a S o h / T o e Q R Z 9 R Y q X M r W R K i G l S q b s 2 d g 6 w S r y B V K N A c V L 7 6 Y c K y G K V h g m r d 8 9 z U + D l V h j O B 0 3 I / 0 5 h S N q Z D 7 F k q a Y z a z + f n T s m 5 V U I S J c q W N G S u / p 7 I a a z 1 J A 5 s Z 0 z N S C 9 7 M / E / r 5 e Z 6 N r P u U w z g 5 I t F k W Z I C Y h s 9 9 J y B U y I y a W U K a 4 v Z W w E V W U G Z t Q 2 Y b g L b + 8 S t r 1 m n d Z q z / U q 4 3 7 I o 4 S n M I Z X I A H V 9 C A O 2 h C C x i M 4 R l e 4 c 1 J n R f n 3 f l Y t K 4 5 x c w J / I H z + Q N E l I + M < / l a t e x i t > Classifier < l a t e x i t s h a 1 _ b a s e 6 4 = " v I c v T g T g m z y 4 V 1 x r d w 1 p a N E k + X w = " > A A A B 8 X i c b V C 7 T s M w F L 0 p r 1 J e B U Y W i w q J q U r K A G O l L g w M R a I P 0 U a V 4 9 6 2 V h 0 n s h 2 k K u p f s D C A E C t / w 8 b f 4 L Q Z o O V I l o 7 P u d e + 9 w S x 4 N q 4 7 r d T 2 N j c 2 t 4 p 7 p b 2 9 g 8 O j 8 r H J 2 0 d J Y p h i 0 U i U t 2 A a h R c Y s t w I 7 A b K 6 R h I L A T T B u Z 3 3 l C p X k k H 8 w s R j + k Y 8 l H n F F j p c e G o F r b K 6 p B u e J W 3 Q X I O v F y U o E c z U H 5 q z + M W B K i N C

x 7 p e e 5 s f F T q g x n A u e l f q I x p m x K x 9 i z V N I Q t Z 8 u J p 6 T C 6 s M y S h S 9 k h D F u r v j p S G W s / C w F a G 1 E z 0 q p e J / 3 m 9

x I x u / J T L O D E o 2 f K j U S K I i U i 2 P h l y h c y I m S W U K W 5 n J W x C F W X G h l S y I X i r K 6 + T d q 3 q X V V r 9 7 V K / S 6 P o w h n c A 6 X 4 M E 1 1 O E W m t A C B h K e 4 R X e H O 2 8 O O / O x 7 K 0 4 O Q 9 p / A H z u c P q b K Q 7 w = = < / l a t e x i t > c < l a t e x i t s h a 1 _ b a s e 6 4 = " u q d E i J j n I X r R h y y N S n H H v 6 C 1 x l 0 = " > A A A B 6 H i c b V A 9 S w N B E J 2 L X z F + R S 1 t F o N g F e 6 i o G X A x s I i A R M D y R H 2 N n P J m r 2 9 Y 3 d P C E d + g Y 2 F I r b + J D v / j Z v k C k 1 8 M P B 4 b 4 a Z e U E i u D a u + + 0 U 1 t Y 3 N r e K 2 6 W d 3 b 3 9 g / L h U V v H q W L Y Y r G I V S e g G g W X 2 D L c C O w k C m k U C H w I x j c z / + E J l e a x v D e T B P 2 I D i U P O a P G S k 3 W L 1 f c q j s H W S V e T i q Q o 9 E v f / U G M U s j l I Y J q n X X c x P j Z 1 Q Z z g R O S 7 1 U Y 0 L Z m A 6 x a 6 m k E W o / m x 8 6 J W d W G Z A w V r a k I X P 1 9 0 R G I 6 0 n U W A 7 I 2 p G e t m b i f 9 5 3 d S E 1 3 7 G Z Z I a l G y x K E w F M T G Z f U 0 G X C E z Y m I J Z Y r b W w k b U U W Z s d m U b A j e 8 s u r p F 2 r e h f V W v O y U r / L 4 y j C C Z z C O X h w B X W 4 h Q a 0 g A H C M 7 z C m / P o v D j v z s e i t e D k M 8 f w B 8 7 n D 8 q 1 j P U = < / l a t e x i t > (c) < l a t e x i t s h a 1 _ b a s e 6 4 = " V u y l N Z 7 Q G r o G f M O w E D f e U E W 2 L R 4 = " > A A A B 6 n i c b V A 9 S w N B E J 2 L X z F + R S 1 t F o M Q m 3 A X B S 0 D N h Y W E c 0 H J E f Y 2 8 w l S / b 2 j t 0 9 I Y T 8 B B s L R W z 9 R X b + G z f J F Z r 4 Y O D x 3 g w z 8 4 J E c G 1 c 9 9 v J r a 1 v b G 7 l t w s 7 u 3 v 7 B 8 X D o 6 a O U 8 W w w W I R q 3 Z A N Q o u s W G 4 E d h O F N I o E N g K R j c z v / W E S v N Y P p p x g n 5 E B 5 K H n F F j p Y c y O + 8 V S 2 7 F n Y O s E i 8 j J c h Q 7 x W / u v 2 Y p R F K w w T V u u O 5 i f E n V B n O B E 4 L 3 V R j Q t m I D r B j q a Q R a n 8 y P 3 V K z q z S J 2 G s b E l D 5 u r v i Q m N t B 5 H g e 2 M q B n q Z W 8 m / u d 1 U h N e + x M u k 9 S g Z I t F Y S q I i c n s b 9 L n C p k R Y 0 s o U 9 z e S t i Q K s q M T a d g Q / C W X 1 4 l z W r F u 6 h U 7 y 9 L t b s s j j y c w C m U w Y M r q M E t 1 K E B D A b w D K / w 5 g j n x X l 3 P h a t O S e b O Y Y / c D 5 / A J A F j V o = < / l a t e x i t > E(x) < l a t e x i t s h a 1 _ b a s e 6 4 = " b M v 7 g N E 2 6 + 6 p Z E x K T 6 I u 4 v O x H Q 8 = " > A A A B 6 3 i c b V B N S w M x E J 2 t X 7 V + V T 1 6 C R a h X s p u F f R Y F M F j B V s L 7 V K y a b Y N T b J L k h X L 0 r / g x Y M i X v 1 D 3 v w 3 Z t s 9 a O u D g c d 7 M 8 z M C 2 L O t H H d b 6 e w s r q 2 v l H c L G 1 t 7 + z u l f c P 2 j p K F K E t E v F I d Q K s K W e S t g w z n H Z i R b E I O H 0 I x t e Z / / B I l W a R v D e T m P o C D y U L G c E m k 2 6 q T 6 f 9 c s W t u T O g Z e L l p A I 5 m v 3 y V 2 8 Q k U R Q a Q j H W n c 9 N z Z + i p V h h N N p q Z d o G m M y x k P a t V R i Q b W f z m 6 d o h O r D F A Y K V v S o J n 6 e y L F Q u u J C G y n w G a k F 7 1 M / M / r J i a 8 9 F M m 4 8 R Q S e a L w o Q j E 6 H s c T R g i h L D J 5 Z g o p i 9 F Z E R V p g Y G 0 / J h u A t v r x M 2 v W a d 1 a r 3 5 1 X G l d 5 H E U 4 g m O o g g c X 0 I B b a E I L C I z g G V 7 h z R H O i / P u f M x b C 0 4 + c w h / 4 H z + A D t G j b Q = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " 3 G Q W q p O 7 c Q A S 3 x P K V + I d s 7 + C o q 4 = " > A A A B 6 3 i c b V B N S 8 N A E J 3 4 W e t X 1 a O X x S J 4 K k k V 9 F j 0 4 r G C / Y A 2 l M 1 2 0 i 7 d 3 Y T d j V B C / 4 I X D 4 p 4 9 Q 9 5 8 9 + Y t D l o 6 4 O B x 3 s z z M w L Y s G N d d 1 v Z 2 1 9 Y 3 N r u 7 R T 3 t 3 b P z i s H B 2 3 T Z R o h i 0 W i U h 3 A 2 p Q c I U t y 6 3 A b q y R y k B g J 5 j c 5 X 7 n C b X h k X q 0 0 x h 9 S U e K h 5 x R m 0 t 9 F G J Q q b o 1 d w 6 y S r y C V K F A c 1 D 5 6 g 8 j l k h U l g l q T M 9 z Y + u n V F v O B M 7 K / c R g T N m E j r C X U U U l G j + d 3 z o j 5 5 k y J G G k s 1 K W z N X f E y m V x k x l k H V K a s d m 2 c v F / 7 x e Y s M b P + U q T i w q t l g U J o L Y i O S P k y H X y K y Y Z o Q y z b N b C R t T T Z n N 4 i l n I X j L L 6 + S d r 3 m X d b q D 1 f V x m 0 R R w l O 4 Q w u w I N r a M A 9 N K E F D M b w D K /

w 5 k j n x X l 3 P h a t a 0 4 x c w J / 4 H z + A A 6 0 j j 8 = < / l a t e x i t >

ImageNet class label:

< l a t e x i t s h a 1 _ b a s e 6 4 = " 5 6 1 / 2 6 6 8 U 0 

x z O E V Y Z / y Z J R N E t W S + 1 1 N 7 T b Y 0 U = " > A A A B / X i c b V C 7 S g N B F L 0 b X z G + 1 k d n M x g E q 7 A b C y 2 D N t p I B P O A Z A m z k x s z Z P b B z K w Q l + C v 2 F g o Y u t / 2 P k 3 z i Z b a O K B g c O 5 r z P H j w V X 2 n G + r c L S 8 s r q W n G 9 t L G 5 t b 1 j 7 + 4 1 V Z R I h g 0 W i U i 2 f a p Q 8 B A b m m u B 7 V g i D X y B L X 9 0 m d V b D y g V j 8 I 7 P Y 7 R C + h 9 y A e c U W 2 k n n 1 w b Q S 8 Q U 2 Y o E o R Q X 0 U P b v s V J w p y C J x c 1 K G H P W e / d X t R y w J M N T T N R 3 X i b W X U q k 5 E z g p d R O F M W U j c 6 p j a E g D V F 4 6 d T 8 h x 0 b p k 0 E k z Q u N j 0 z 9 P Z H S Q K l x 4 J v O g O q h m q 9 l 4 n + 1 T q I H 5 1 7 K w z j R G L L Z o U E i i I 5 I F g X p c 4 l M i 7 E h l E l u v B I 2 p J I y b Q I r m R D c + S 8 v k m a 1 4 p 5 W q r f V c u 0 i j 6 M I h 3 A E J + D C G d T g C u r Q A A a P 8 A y v 8 G Y 9 W S / W u / U x a y 1 Y + c w + / I H 1 + Q P b J p T V < / l

F S A N 5 U T r j u 8 l J h g T Z R j l M C n d p R o S Q o e k D x 1 L J R G g g 3 H 2 w Q Q f W 6 W H o 1 j Z k g Z n 6 u + J M R F a j 0 R o O w U x A z 3 v T c X / v E 5 q o v N g z G S S G p B 0 t i h K O T Y x n s a B e 0 w B N X x k C a G K 2 V s x H R B F q L G h l W w I / v z L i 6 R Z r f i n l e p N t V y 7 y O M o o k N 0 h E 6 Q j 8 5 Q D V 2 h O m o g i h 7 R M 3 p F b 8 6 T 8 + K 8 O x + z 1 o K T z + y j P 3 A + f w C Z n p b 6 < / l a t e x i t > Jigsaw permutation label < l a t e x i t s h a 1 _ b a s e 6 4 = " y U g p + 9 X Y X b F h b v R 6 3 C P C 2 L K E M l A = " > A A A C A X i c b V A 9 S w N B E N 2 L X z F + n d o I N o t B s A p 3 s d A y a C N W E c w H x C P s b e a S J b t 7 x + 6 e E k J s / C s 2 F o r Y + i / s / D d u L l d o 4 o O B x 3 s z z M w L E 8 6 0 8 b x v p 7 C 0 v L K 6 V l w v b W x u b e + 4 u 3 t N H a e K Q o P G P F b t k G j g T E L D M M O h n S g g I u T Q C o e X U 7 9 1 D 0 q z W N 6 a U Q K B I H 3 J I k a J s V L X P b h m f U 0 e c A J K p C Y T M S c h 8 K 5 b 9 i p e B r x I / J y U U Y 5 6 1 / 2 6 6 8 U 0 F S A N 5 U T r j u 8 l J h g T Z R j l M C n d p R o S Q o e k D x 1 L J R G g g 3 H 2 w Q Q f W 6 W H o 1 j Z k g Z n 6 u + J M R F a j 0 R o O w U x A z 3 v T c X / v E 5 q o v N g z G S S G p B 0 t i h K O T Y x n s a B e 0 w B N X x k C a G K 2 V s x H R B F q L G h l W w I / v z L i 6 R Z r f i n l e p N t V y 7 y O M o o k N 0 h E 6 Q j 8 5 Q D V 2 h O m o g i h 7 R M 3 p F b 8 6 T 8 + K 8 O x + z 1 o K T z + y j P 3 A + f w C Z n p b 6 < / l a t e x i t > f (E(x ⇡ ), y) < l a t e x i t s h a 1 _ b a s e 6 4 = " 6 Z o o b v E u x K 0 5 C a S O N F M R R b k o f m A = " > A A A B + H i c b V B N S 8 N A E J 3 4 W e t H o x 6 9 B I v Q g p S k C n o s i u C x g v 2 A N o T N d t M u 3 W z C 7 k a M o b / E i w d F v P p T v P l v 3 L Y 5 a O u D g c d 7 M 8 z M 8 2 N G p b L t b 2 N l d W 1 9 Y 7 O w V d z e 2 d 0 r m f s H b R k l A p M W j l g k u j 6 S h F F O W o o q R r q x I C j 0 G e n 4 4 + u p 3 3 k g Q t K I 3 6 s 0 J m 6 I h p w G F C O l J c 8 s B Z W b y q O X 9 W M 6 q Z 6 m V c 8 s 2 z V 7 B m u Z O D k p Q 4 6 m Z 3 7 1 B x F O Q s I V Z k j K n m P H y s 2 Q U B Q z M i n 2 E 0 l i h M d o S H q a c h Q S 6 W a z w y f W i V Y G V h A J X V x Z M / X 3 R I Z C K d P Q 1 5 0 h U i O 5 6 E 3 F / 7 x e o o J L N 6 M 8 T h T h e L 4 o S J i l I m u a g j W g g m D F U k 0 Q F l T f a u E R E g g r n V V R h + A s v r x M 2 v W a c 1 a r 3 5 2 X G 1 d 5 H A U 4 g m O o g A M X 0 I B b a E I L M C T w D K / w Z j w Z L 8 a 7 8 T F v X

6. CONCLUSION:

In this paper we introduced a new lower bound on the KL divergence and showed how it can be used to improve the estimation of mutual information using neural networks. Theoretically we proved that the dual of our η-DV formulation reduces to a constrained likelihood ratio estimation. In practice, the stability of η-MINE is due to its unbiased gradient. We tested our estimator η-MINE on synthetic data and applied it on various real-world tasks where MI can be used as a regularizer, or as an objective in self-supervised learning. We used η-MINE in unsupervised learning of representations through MI maximization and by solving Jigsaw puzzles. We leave for a future work the analysis and various possible applications of conditional mutual information neural estimators.

Supplementary Material for Improved Mutual Information Estimation:

The supplementary material is organized as follows:

• In Appendix A we layout proofs of Lemmas 1, 2 and 3. Those lemmas provide the η-DV formulation. We also give in this Appendix the proof of the main Theorem 1. This theorem gives the dual formulation of this variational bound in RKHS with Tikhonov Regularization and sheds the light on the ratio estimation interpretation of η-DV. • We give in Appendix A.1 the impact of other regularizers on the estimation of KL divergence in RKHS. • In Appendix B, we show that further improved bounds can be obtained for the particular case of mutual information leading to an improved Donsker-Varadhan. We show that by using the interchangeability principle, we can obtain an equivalent functional η-DV bound that is related to a-MINE introduced in Poole et al. ( 2016). • In Appendix C, we show how those improved variational bounds can be extended to conditional mutual information. • In Appendix D, we give more details on the experimental setup of self-supervised learning with the jigsaw task.

A TECHNICAL PROOFS:

Proof of Lemma:1. Let g(η) = e -η x + η -1. We have g (η) = -e -η x + 1 and g (η) = e -η x > 0.

Hence g is convex and admits a unique minimum. First order optimality gives us: g (η * ) = -e -η * x + 1 = 0, hence e -η * x = 1 and η * = log(x). Finally, we get

g(η * ) = e -log(x) x + log(x) -1 = e log( 1 x ) x + log(x) -1 = 1 + log(x) -1 = log(x).

Proof of Lemma 2. By Donsker-Varadhan representation we have:

D H DV (P, Q) = sup f ∈H E x∼P f (x) -log E x∼Q e f (x) = -inf f ∈H log E x∼Q e f (x) -E x∼P f (x) = -inf f ∈H {inf η e -η E x∼Q e f (x) + η -1} -E x∼P f (x) = -inf f ∈H ,η∈R {e -η E x∼Q e f (x) -E x∼P f (x) + η -1}.

Proof of Lemma 3. L is a sum of a linear function in w, η and Ω(w), that are both convex. We need to prove that f b (w, η) = e -η e w,b is jointly convex, since L can be written as a sum of f b and other convex functions:

∇ w f b (w, η) = e -η e w,b b, ∇ 2 w f b (w, η) = e -η e w,b b ⊗ b PSD (Positive Semi-Definite) ∂ 2 f b ∂w∂η = -e -η e w,b b, ∂ 2 f b ∂η 2 = e -η e w,b

. The Hessian of f b (w, η), Hf b , has the following form: Hence, f b is jointly convex in η and w, and so is L. Now adding the perturbation εe -η to the loss, we get w , η ) Hf b (w, η)(w , η ) = e -η e w,b ( w , bη ) 2 + εe -η > 0,

Hf b (w, η) = ∂ 2 L ∂w⊗∂w ∂ 2 L ∂w∂η ∂ 2 L ∂η∂w ∂ 2 L ∂η 2 = e -η e

for finite η and hence we have a strict convexity.

Proof of Theorem 1. Let's consider:

f (x) = w, Φ(x)

, and ϕ(t) = e t .

Recall that the Fenchel conjugate of f is f * (p) = sup x p, xf (x). It follows that ϕ * (t) = t log(t)t if t > 0, 0 for t = 0, and ∞ otherwise.

min w,η e -η E y∼Q ϕ ( w, Φ(y) ) -E x∼P w, Φ(x) + η -1 + Ω(w) = min w,η e -η X ϕ ( w, Φ(y) ) q(y)dy -w, X Φ(x)p(x)dx + η -1 + Ω(w) = min w,η,z e -η X ϕ (z(y)) q(y)dy -w, X Φ(x)p(x)dx + η -1 + Ω(w) s.t. z(y) = w, Φ(y) Introducing Lagrangian's α we have = min w,η,z max α e -η X ϕ (z(y)) q(y)dy -w, X Φ(x)p(x)dx + η -1 + Ω(w) - X α(y)( w, Φ(y) -z(y))dy = max α min w,η,z e -η X ϕ (z(y)) q(y)dy -w, X Φ(x)p(x)dx + η -1 + Ω(w) - X α(y)( w, Φ(y) -z(y))dy

using strong duality (convex function and lower semi-continuous) to swap min, max (Ekeland & Turnbull, 1983 )

= max α min η -max z - X (ϕ (z(y)) q(y)e -η + α(y)z(y))dy -max w w, X Φ(x)p(x)dx + X α(y)Φ(y)dy -Ω(w) -η + 1 = max α min η - X q(y)e -η max z -ϕ(z) - α(y) q(y)e -η z -Ω * X Φ(x)p(x)dx + X α(y)Φ(y)dy + η -1 = max α<0 min η - X q(y)e -η ϕ * (- α(y) q(y)e -η ) -Ω * X Φ(x)p(x)dx + X α(y)Φ(y)dy + η -1 = max α>0 min η - X q(y)e -η ϕ * ( α(y) q(y)e -η ) -Ω * X Φ(x)p(x)dx - X α(y)Φ(y)dy + η -1 = -min α>0 max η X q(y)e -η ϕ * ( α(y) q(y)e -η ) + Ω * X Φ(x)p(x)dx - X α(y)Φ(y)dy -η + 1

Hence, we have for α > 0, and finite η: X q(y)e -η ϕ * α(y) q(y)e -η dy = X q(y)e -η α(y) q(y)e -η log( α(y) q(y)e -η ) -α(y) q(y)e -η dy = X q(y)e -η α(y) q(y)e -η log( α(y) q(y)e -η ) -α(y) q(y)e -η dy = X [α(y) log α(y) q(y)e -ηα(y)]dy = X α(y) log α(y) q(y) dy + (η -1) α(y))dy.

Define r(y) = α(y) q(y) > 0

A.1 IMPACT OF REGULARIZERS ON KL ESTIMATION:

As discussed before, the choice of the regularizer Ω translates to a particular type of metric used in estimating the likelihood ratio: Ω(.) = .

2 2 translates in a ratio estimation in the MMD sense. Here, we consider other choices of regularization used in Fisher discriminant analysis (Harchaoui et al., 2008; Mroueh & Sercu, 2017) , specifically:

EQUATION

or gradient penalty regularizer (Gulrajani et al., 2017; Mroueh et al., 2018; 2019) :

EQUATION

)

It is easy to see that when we restrict f to H , η-DV-Fisher has the same objective as in Eq. 11 with Ω(w) = λ 2 w, (C(P, Q))w , where

C(P, Q) = E P+Q 2 Φ(x) ⊗ Φ(x) is a covariance matrix.

Similarly, η-DV-Sobolev corresponds to Eq. 11 with Ω(w) = λ 2 w, (D(P, Q))w , where

D(P, Q) = E (P+Q)/2 d j=1 ∂ j Φ(x) ⊗ ∂ j Φ(x) is a Gramian of derivatives. The convex conjugate Ω * (w) is therefore 1 2λ w, (C † (P, Q))

w and 1 2λ w, (D † (P, Q))w , for η-DV-Fisher and η-DV-Sobolev respectively (where † denotes the pseudo-inverse). Harchaoui et al. (2008) that the Fisher discrepancy is F 2 Φ (P, Q) = δ P,Q , C(P, Q) † δ P,Q , and from Mroueh et al. (2018; 2019) the Sobolev discrepancy is S 2 Φ (P, Q) = δ P,Q , D(P, Q) † δ P,Q . Now replacing Ω * by its expression in Theorem 1 we see that the choice of the regularizer dictates the discrepancy used for the ratio estimation: η-DV-Fisher : min r>0 X r(y) log (r(y)) q(y)dy + 1 2λ F 2 Φ (rq, p), subject to: E px,y f (x, y) -E py log(E px e f (x,y ))

Let δ:

P,Q = E P Φ(x) -E Q Φ(y). Recall from

where G (X × Y) is the entire space of functions defined on X × Y. We conclude therefore that KL(p x,y , p x p y ) + E px log(E py g(x, y)) ≥ E px E p y|x log(g(x, y)) = E px,y log(g(x, y)).

B.1 η-TRICK AND INTERCHANGEABILITY PRINCIPLE FOR IMPROVED DV:

We just showed that an improved Donsker-Varadhan representation of Mutual Information can be be derived as follows:

I(X; Y ) = sup f ∈G (X ×Y)

E px,y f (x, y) -E py log(E px e f (x,y )).

We show in this section that, by using interchangeability principle, we can replace the "log" non linearity preceding the expectation with an "functional" η-trick.

We start first by stating the interchangeability principle between expectation and minimum operations: Lemma 7 (Interchangeability Principle see Lemma 1 in (Dai et al., 2016) ). Let ξ be a random variable on Ξ and assume for any ξ ∈ Ξ, the function g(., ξ) : R → (-∞, +∞) is a proper and lower semi-continuous convex function. Then E ξ min u∈R g(u, ξ) = min u(.)∈G (Ξ) E ξ g(u(ξ), ξ).

Applying the interchangeability principle and the variational representation of log we obtain the following Theorem: Theorem 3 (Theorem 2 restated: η-trick for improved DV Bound). Let H be a space of bounded functions defined on X × Y, we have:

I(X; Y ) ≥ - inf f ∈H ,η∈G(Y)

E px.py e f (x,y)-η(y) + E py η(y) -1 -E px,y (f (x, y)),

where G (Y) is the entire space of functions defined on Y. Let H η be a function space subset of G (Y), we obtain:

I(X; Y ) ≥ I H a-DV (X; Y ) = sup f ∈H ,η(.)∈Hη

E px,y f (x, y) -E px.py e f (x,y)-η(y) -E py η(y) + 1.

Proof. We know from Lemma 6 that for any function space H I(X; Y ) ≥inf

f ∈H E py log(E px e f (x,y) ) -E px,y (f (x, y)).

(25)

Applying the η-trick for each log in the expectation:

E py log(E px e f (x,y) ) = E py min η∈R e -η E px e f (x,y) + η -1.

We assume here that the function space f is bounded. Before applying the interchangeability Lemma 7, let us verify that all assumptions hold for g(η, y) = e -η E px e f (x,y) + η -1.

Convex. g(., y) is convex. Considering derivatives wrt to η: g (η, y) = -e -η E px (e f (x,y) ) + 1, and g (η, y) = e -η E px (e f (x,y) ) > 0.

Proper Function. g(η, .) is a proper function, since f is bounded (-M ≤ f (x, y) ≤ M ):

g(0, y) = E px e f (x,y) -1 ≤ e M -1 < ∞. and g(η, y) > -∞, ∀η, since g(η, y) ≥ g(η * , y) = log(E px e f (x,y) ) ≥ -M, ∀η.

Lower semi-continuity. g(η, .) is lower semi-continuous since it is continuous (sum of continuous functions).

Now back to Eq. 26, we are ready to apply the interchangeability principle given in Lemma 7: E py e -η(y) E px e f (x,y) + η(y) -1 .

E

Using this equivalent form, we have: E py e -η(y) E px e f (x,y) + η(y) -1 -E px,y (f (x, y)

= inf f ∈H ,η∈G(Y)

E px.py e f (x,y)-η(y) + E py η(y) -1 -E px,y (f (x, y).

It follows that:

I(X; Y ) ≥ - inf f ∈H ,η∈G(Y)

E px.py e f (x,y)-η(y) + E py η(y) -1 -E px,y (f (x, y)

= sup f ∈H ,η∈G(Y)

E px,y f (x, y) -E px.py e f (x,y)-η(y) -E py η(y) + 1.

Consider now a function space H η from Y → R we have:

I(X; Y ) ≥ sup f ∈H ,η∈Hη

E px,y f (x, y) -E px.py e f (x,y)-η(y) -E py η(y) + 1,

The MI lower bound is looser than regular η-MINE, since we have two lower bounds passing from all function spaces G (X × Y) on to H , then going from G (Y) to H η .

No free lunch: tighter bound but we need to estimate a function η(x) which makes bigger estimation errors. To get a good estimate of η(x), to obtain its optimal value log(E py e f (x,y) ), we need for each x many samples from p y (which means many epochs of cycling through the same data in random order). The η-trick with only a scalar variable is better computationally, since it enjoys convexity and has better optimization properties. But as it is clear from this discussion, η function of a modality is good for conditional MI estimation which we will discuss next.

C CONDITIONAL MUTUAL INFORMATION:

To illustrate the power of improved Donsker-Varadhan and its variational representation with the ηtrick and interchangeability principle, we show how to extend this to Conditional Mutual Information estimation.

We have a (X, Y ) pair of random variables that may depend on another variable Z. This conditional dependence is of high importance in all applications of joint embedding or in the information bottleneck principle, etc. 

Now using the η-trick for each z, followed by the interchangeability principle, we have the final variational form:

I(X; Y |Z) = sup f ∈F ,η

E z∼pz E p x,y|z f (x, y, z) -E z∼pz e -η(z) E p x|z p y|z e f (x,y,z) + η(z) -1 .

(28)

D JIGSAW SELF-SUPERVISION AND MUTUAL INFORMATION:

Jigsaw Task Preprocessing For Jigsaw self-supervision task, the encoder needs to learn features from images randomly cropped and tiled into 3×3 jigsaw puzzles. In order to avoid shortcuts based on matching edges of patches or picking up on color aberration as discussed in Noroozi & Favaro (2016) , images are resized to 292×292, randomly cropped into 255×255 and jigsawed into 3×3 or 85×85 per patch wherein a 64×64 patch is randomly cropped, avoiding potentially easy edge matching. 255×255 crops are randomly assigned to gray scales with a probability of 2 ⁄3 prior to patch extraction. Each patch RGB channel is normalized to zero mean, unit variance. At test time, the 255×255 crops are obtained from images center crops.

ImageNet 10% For the Jigsaw experiments, we decided to subsample ImageNet to 10% within each class for both training and validation sets (128K training and 5K validation images). The reason is that running on all of ImageNet 1.3 Million images was not practical for reasonable training turnaround on our infrastructure given what we had to train one set of encoder models from the pretext task and one set of classifier models for the target task. Even though we only train classifiers for the target task (as explained later in this section), we still need to forward input features through the Encoder which can still be computationally costly despite only backpropagating through the classifier. This 10% subset of ImageNet was proposed by (Kolesnikov et al., 2019) and can be used for faster training turnaround while still being larger than the Tiny ImageNet dataset (200 classes, 500 training, 50 vaildation, 50 test images per class) often used in publications.

:



Figures and Tables:

A w a c P k S S Y u F x 2 v D 6 F y O / 8 U S l Y m F w D 8 O I u g J 3 A + Y z g k F L r t 8 C O o D k 6 O b 6 9 j J t F 4 p 2 y R 7 D m i d O R o o o Q 7V d + G l 1 Q h I L G g D h W K m m Y 0 f g J l g C I 5 y m Z i t W N M K k j 7 u 0 q W m A B V V u M j 4 6 t Q 6 0 0 r H 8 U O o K w B q r f y c S L J Q a C k 9 3 C g w 9 N e u N x P + 8 Z g z + m Z u w I I q B B m S y y I + 5 B a E 1 S s D q M E k J 8 K E m m E i m b 7 V I D 0 t M Q O c 0 t a U r c d R j Z D D 1 S e K J 1 D R 1 V s 5 s M v O k X i4 5 x 6 X y 3 U m x c p 6 l l k d 7 a B 8 d I g e d o g q 6Q l V U Q w Q 9 o m f 0 i t 6 M F + P d + D A + J 6 0 5 I 5 v Z R V M w v n 4 B 7 K K h 3 A = = < / l a t e x i t > a-MINE < l a t e x i t s h a 1 _ b a s e 6 4 = " b h N K C s R f M 7 h 8 6 p L o Z U E 5 P f 2 K c i c = " > A A A C G 3 i c b V B N S 8 N A E N 3 U r x q / q h 6 9 B I v g x Z J U Q Y 9 F E f S g V L C t 0 I a y 2 W 7 a p Z t N 3 J 1 I S 8 j v 8 C T o b / E m X j 3 4 U 7 y 5 b X O w r Q 8 G H u / N M D P P i z h T Y N v f R m 5 h c W l 5 J b 9 q r q 1 v b G 4 V t n f q K o w l o T U S 8 l A + e F h R z g S t A Q N O H y J J c e B x 2 v D 6 F y O / 8 U S l Y q G 4 h 2 F E 3 Q B 3 B f M Z w a A l F 7 e A D i A 5 u r m + v U z b h a J d s s e w 5 o m T k S L K U G 0 X f l q d k M Q B F U A 4 V q r p 2 B G 4 C Z b A C K e p 2 Yo V j T D p 4 y 5 t a i p w Q J W b j I 9 O r Q O t d C w / l L o E W G P 1 7 0 S C A 6 W G g a c 7 A w w 9 N e u N x P + 8 Z g z + m Z s w E c V A B Z k s 8 m N u Q W i N E r A 6 T F I C f K g J J p L p W y 3 S w x I T 0 D l N b e l K H P U Y G U x 9 k n h B a p o 6 K 2 c 2 m X l S L 5 e c 4 1 L 5 7 q R Y O c 9 S y 6 M 9 t I 8 O k Y N O U Q V d o S q q I Y I e 0 T N 6 R W / G i / F u f B i f k 9 a c k c 3 s o i k Y X 7 / k D 6 H X < / l a t e x i t > DV-MINE < l a t e x i t s h a 1 _ b a s e 6 4 = " p P 9 B k z E N L 7 S T d 7 u 0 e A 7 p K x 1 T 2 r 0

R b b l z i i s o P B q G r 9 G E z j 8 n l 0 T g 9 H h / 9 + D w 6 + 9 q 3 t o 3 e o L f o E K X o B J 2 h 7 + g C T R B D d 9 F W t B v t x T t x G p / G X 7 p o H P U z B 2 g D 8 f k 9 3 t L I e g = = < / l a t e x i t > KL(P, Q) < l a t e x i t s h a 1 _ b a s e 6 4 = " k d V i k z K R T h G C W x a M T F w T w t n m g d M = " > A A A C I H i c b Z D L S g M x F I Y z X m u 9 j b p 0 E y x C B S k z V d B l 0 Y 2 g i x b s B d p S M m n a h m Y u J G e k Z Z i t D + L a r T 6 D O 3 G p b + B b m G l H s K 0 / B D 7 + c w 7 n 5 H c C w R V Y 1 q e x t L y y u r a e 2 c h u b m 3

y 7 e b / S z H 6 A N b + Q 3 2 y n I a l p J X n J G b a D y 8 U / S y m X Q w b r S O 2 J a 5 Y m A 0 h J H a m p X R e E + + t y p 3 K 0 7 3 y u L c r p + 3 j 0 j m l c r m 7 3 A R D T V V p j u O t Y q 7 w Y H f H e 9 y Q 8 u 3 O / D J c T n 4 0 k y S 7 a F r 4 J 0 A B M 0 1

Figure 1: Overview of the paper. Top row shows several KL divergence lower bounds for two probability distributions P and Q. By substituting P = pxy, Q = pxpy, and defining f as a neural network, we obtain corresponding MI estimators. η-DV and η-MINE are the proposed bound and its derived estimator. Further details are provided in the text.

Figure 2: Comparison of dual formations of η-DV and f -div in RKHS.Here r is an estimator for density ratio p/q and MMDΦ(P, Q) = E x∼P Φ(x) -E y∼Q Φ(y) . As can be seen, both duals have a relative entropy term, but the f -div bound does not impose the normalization constraint on the ratio, which biases the estimate, while η-DV uses η as the Lagrangian multiplier to impose the constraint E Q [r] = 1 and ensure density normalization.

Conditional GAN + ⌘ MINECond. GAN + DV-MINE < l a t e x i t s h a 1 _ b a s e 6 4 = " j s

0 H P 8 G / c P p Y 2 N Y D F w 7 n 3 M u 5 H C / i T I F t f x u Z h c W l 5 Z X s q r m 2 v r G 5 l d v e q a o w l o R W S M h D W f e w o p w J W g E G n N Y j S X H g c V r z e h d D v / Z E p W K h e I B B R N 0 A d w T z G c G g p c c m 0 D 4 k l 9 W j 2 5 u 7 q 7 S V y 9 s F e w R r n j g T k k c T l F u 5 n 2 Y 7 J H F A B R C O l W o 4 d g R u g i U w w m l q N m N F I 0 x 6 u E M b m g o c U O U m o 6 9 T 6 0 A r b c s P p R 4 B 1 k j 9 e 5 H g Q

r k h b y S N + P Z e D c + j M / J 6 p I x v T k g M z C + f g H E b J y 1 < / l a t e x i t >

Figure 3: Performance of different MI estimators on synthetic Gaussian datasets. Top: MI estimation. Data was sampled from 2-, 10-and 20-dimensional Gaussian distributions with randomly generated means and covariance matrices. As we increase the data complexity, the difference between estimators decreases, although we observed that η-MINE (or its convex extension) on average performed better than the baseline methods, converging to the true MI [red line] faster. Bottom: MI for GAN regularization. Top row: unconditional GAN baseline fails at capturing all 25 modes in the Gaussian mixture. Middle row: MI-regularized conditional GAN using DV-MINE (Belghazi et al., 2018) converges after 140K steps of the generator. We found this estimator to be sensitive to the hyper-parameters and unstable during training. Bottom row: MI-regularized conditional GAN using η-MINE; the model converges in 50K steps of the generator.

Figure 4: (a) Encoder architecture and classification accuracy (top1) on CIFAR-10 dataset for different pretrained encoders. Each number represents test accuracy of the system trained by maximizing MI between features from layers pointed by the corresponding arrows. Interestingly, the highest accuracy was obtained by pre-training encoder composed of just the first two convolutional layers (see (b) and (c) for details of this process). (b) Model pre-training by maximizing MI between features from different layers [additionally transformed by a neural net, aimed at constructing witness function f (•)]. (c) After pre-training, we fix encoder and attach a trainable linear layer to perform traditional supervised training on the same or different datasets. Table 2: Classification accuracy (top1) results on CI-FAR10 (C10) and STL10 (S10) for unsupervised pretraining task with DV-MINE and η-MINE using encoder in Fig. 4.b. For reference we also list results for supervised (CE) training using full encoder in Fig. 4.a. η-MINE-based pre-training achieves overall better results when evaluated on same or different data, even outperforming the supervised model on S10.

z s e 8 N e d k M 4 f w B 8 7 n D w Z r k I Y = < / l a t e x i t >

a t e x i t > Jigsaw permutation label < l a t e x i t s h a 1 _ b a s e 6 4 = " y Ug p + 9 X Y X b F h b v R 6 3 C P C 2 L K E M l A = " > A A A C A X i c b V A 9 S w N B E N 2 L X z F + n d o I N o t B s A p 3 s d A y a C N W E c w H x C P s b e a S J b t 7 x + 6 e E k J s / C s 2 F o r Y + i / s / D d u L l d o 4 o O B x 3 s z z M w L E 8 6 0 8 b x v p 7 C 0 v L K 6 V l w v b W x u b e + 4 u 3 t N H a e K Q o P G P F b t k G j g T E L D M M O h n S g g I u T Q C o e X U 7 9 1 D 0 q z W N 6 a U Q K B I H 3 J I k a J s VL X P b h m f U 0 e c A J K p C Y T M S c h 8 K 5 b 9 i p e B r x I / J y U U Y

Figure 5: (a) Jigsaw CE training. (b) Jigsaw MI training. (c) ImageNet Classification CE training.

w,b b ⊗ b -e -η e w,b b -e -η e w,b b e -η e w,b Let us prove that for all (w, η): (w , η ) Hf b (w, η)(w , η ) ≥ 0, ∀(w , η ). We have: (w , η ) Hf b (w, η)(w , η ) = e -η e w,b ( w , b ) 2 -2η e -η e w,b w , b + η 2 e -η e w,b = e -η e w,b ( w , b ) 2 -2η w , b + η 2 = e -η e w,b ( w , bη ) 2 ≥ 0.

MUTUAL INFORMATION: a-MINE FORMULATION FROM INTERCHANGEABILITY PRINCIPLEWe start by the classical result of Donsker and Varadhan: Lemma 5(Donsker-Varadhan). For any Distribution P and any distribution Q and any non-negative function g for which E x∼P log g(x) is finite, we have:KL(P, Q) + log(E x∼Q g(x)) ≥ E x∼P log(g(x)).This gives us a representation of KL divergence:KL(P, Q) = sup g>0 E x∼P log(g(x))log(E x∼Q g(x)) = sup f E x∼P f (x)log(E x∼Q e f (x) ).The following Lemma shows that a finer application of the Donsker-Varadhan Lemma gives an improved variational representation of MI : Lemma 6. Let g > 0 KL(p x,y , p x p y ) + E px log(E py g(x, y)) ≥ E px,y log(g(x, y)).Hence, we getI(X; Y ) = sup g>0 E px,y log(g(x, y)) -E px log(E py g(x, y)) = sup f ∈G (X ×Y)E px,y f (x, y) -E px log(E py e f (x,y ))= supf ∈G (X ×Y)

py log(E px e f (x,y) ) = E py min η∈R e -η E px e f (x,y) + η -1

py log(E px e f (x,y) ) -E px,y f (x, y)

Given

Table content: <table/>

(see Fig. 5.a). While this standard formulation relies on a CE-based classification of the permutation, we propose here to use MI Jigsaw, where we train the encoder E to maximize I(E(x πi ); π i ) by using MI estimators DV-provides an upper-bound for supervised performance for E from the Jigsaw task. Despite CE being better than η-MINE and DV-MINE, η-MINE does a respectable job at learning a useful representation space for the target task, better than DV-MINE. More details about the Jigsaw experiments setup can be found in Appendix D.

Table content: <table><tr><td>and η-MINE, as seen in Fig. 5.b. A patch preprocessing similar to Kolesnikov et al. (2019) avoids</td></tr><tr><td>shortcuts based on color aberration, patch edge matching, etc. (Noroozi &amp; Favaro, 2016); for details</td></tr><tr><td>of our implementation, see Appendix D. All our models are built on a 10% subset of ImageNet (128K</td></tr><tr><td>train., 5K val., 1K classes) as proposed by Kolesnikov et al. (2019). This is a larger set than Tiny</td></tr><tr><td>ImageNet (200 classes) used in many publications. E is a ResNet50 for all our experiments. In our</td></tr><tr><td>ImageNet target classification task, E from CE and MI Jigsaw trainings are frozen (at 200 epochs)</td></tr></table>

ImageNet

Table content: <table><tr><td>(10% subset) classification ac-</td></tr><tr><td>curacy results (in %). DV-MINE and η-MINE are</td></tr><tr><td>using fixed Encoder from MI training. CE is for</td></tr><tr><td>using a CE Jigsaw Encoder. Numbers reported</td></tr><tr><td>are average and standard deviations over 8 models</td></tr><tr><td>from different initialization seeds.</td></tr></table>

KL(p x,y , p x p y ) + E px log(E py g(x, y)) = E pxy log( p xy p x p y ) + E px log(E py g(x, y)) = E px E p y|x log( p y|x p y ) + log(E py g(x, y)) = E px KL(p y|x , p y ) + log(E py g(x, y)) . Now applying Donsker-Varadhan Lemma, we have: KL(p y|x , p y ) + log(E py g(x, y)) ≥ E p y|x log(g(x, y)).

Table content: <table><tr><td>Proof.</td></tr></table>

I(X; Y |Z) = KL(p xyz , p x|z p y|z p(z)), meaning that conditioned on Z, how much X and Y are dependent. |Z) = E z∼pz KL(p x,y|z ||p x|z p y|z ). Now applying Donsker-Varadhan Lemma, we have for all z and for any function f KL(p x,y|z ||p x|z p y|z ) + log E p x|z p y|z f (x, y, z) ≥ E p x,y|z log(f (x, y, z)). Now marginalizing on Z, we get E z∼pz KL(p x,y|z ||p x|z p y|z ) + E z∼pz log E p x|z p y|z f (x, y, z) ≥ E z∼pz E p x,y|z log(f (x, y, z)).

Table content: <table><tr><td>Therefore we have:</td></tr><tr><td>I(X; Y Hence,</td></tr></table>

Peer review (iclr2020):
This paper develops variations on the Donsker-Varadhan (DV) lower bound on KL divergence which yields a lower bound on mutual information as a special case. The paper is primarily theoretical with an emphasis on the case where the witness function f is drawn from an RKHS (a support vector machine). They discuss, and present experimental results where the feature map of the RKHS is computed by a neural network, although the theoretical results largely do not apply to optimization of the neural network. I have two complaints. First, the authors ignore fundamental limitations on the measurement of mutual information from finite samples. See *Fundamental Limitations on the Measurement of Mutual Information* by McAllester and Stratos. This paper makes the intuitively obvious observation that I(X,Y) <= H(X) and one cannot give meaningful lower bound on H(X) larger than about 2 log N when drawing only N samples --- the best test one can use is the birthday paradox and a non-repetitive sample only guarantees that the entropy is larger than about 2 log N. This is obvious for discrete distributions but holds also for continuous distributions --- from a finite sample one cannot even tell if the distribution is continuous or discrete. So meaningful lower bounds for *high dimensional data* are simply not possible for feasible samples. Given this fact, the emphasis needs to be on experimental results. The experimental results in this paper are extremely weak. They should be compared to those in *Learning Representations by Maximizing Mutual Information Across Views* by Philip Bachman, R Devon Hjelm, William Buchwalter Response to the author response: This was written earlier but there was a mishap when I attempted to submit it and it was not actually submitted until comments were no longer available to the authors so I am putting this in the review. Bounding the ratio of the densities already bounds the mutual information. In order for the actual mutual information to be large (hundreds of bits) the log density ratios must actually be extreme. We do believe, presumably, that mutual information in video data can be hundreds of bits. So I am still not convinced that lower bounds on large quantities of mutual information are meaningful. Also, your bound, like the DV bound, involves an empirical estimator of an expectation . The true expectation of an exponential seems likely to be dominated by rare extremes of f(x) which contribute exponentially to the expectation. I see no reason to believe that the empirical estimate is meaningful in a real application such as vision. Regarding the experiments, I do not have much interest in experiments on synthetic Gaussians. The most meaningful experiments for me are the pre-training results for CIFAR. But you seem to be comparing yourself to your own implementations of (weak?) baselines rather than performance numbers reported by, for example, Hjelm et al. or van den Oord et al. (CPC).