A representation-learning game for classes of prediction tasks
Authors: Neria Uzan
Nir Weinberger
Venue: ICLR 2024 poster (2024)
Keywords: representation learning
semi-supervised learning
dimensionality-reduction
regret
minimax solution
mixed strategies
multiplicative weights update
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We derive optimal representations for classes of prediction tasks. We establish the theoretically optimal randomized representation in the linear-MSE setting, and propose an iterative algorithm for optimal representation in the general setting.

Abstract: We propose a game-based formulation for learning dimensionality-reducing representations of feature vectors, when only a prior knowledge on future prediction tasks is available. In this game, the first player chooses a representation, and then the second player adversarially chooses a prediction task from a given class, representing the prior knowledge. The first player aims to minimize, and the second player to maximize, the regret: The minimal prediction loss using the representation, compared to the same loss using the original features. We consider the canonical setting in which the representation, the response to predict and the predictors are all linear functions, and the loss function is the mean squared error. We derive the theoretically optimal representation in pure strategies, which shows the effectiveness of the prior knowledge, and the optimal regret in mixed strategies, which shows the usefulness of randomizing the representation. For general representation, prediction and loss functions, we propose an efficient algorithm to optimize a randomized representation. The algorithm only requires the gradients of the loss function, and is based on incrementally adding a representation rule to a mixture of such rules.

Published as a conference paper at ICLR 2024
A REPRESENTATIIN-LEARNIII GAME FOR CLASSES OF PREDICTION TASKS
Neria Uzan
Nir Weinberger Technion Israel Institute of Technology ni rwei netechnion. i1
Technion Israel Institute of Technology neri neriauzanggmal 1. com
ABSTRACT
We propose a game-based formulation for learning dimensionality-reee -reduciig rep- resentations of feature vectors, when only a prior knowledge on future prediction tasks is available. In this game, the first player chooses representation, and then the second player adversarially chooses a prediction task from a given class, rep- resenting the prior knowledge. The first player aims to minimize, and the second player to maximize, the regret: The minimal prediction loss using the represen- tation, compared to the same loss using the original features. We consider the canonical setting in which the representation, the response to predict and the pre- dictors are all linear functions, and the loss function is the mean squared error. We derive the theoretically optimal representation in pure strategies, which shows the effectiveness of the prior knowledge, and the optimal regret in mixed strate- gies, which shows the usefulness of randomizing the representation. For general representation, prediction and loss functions, we propose an efficient algorithm optimize a randomized representation. The algorithm only requires the gradients of the loss function, and is based on incrementally adding a representation rule to a mixture of such rules.
INTRODUCTION
Commonly, data of unlabeled feature vectors { C X' is collected without a knowledge of the specific downstream prediction task it will be used for. When prediction task becomes of inter- est, labels y; E y are also collected, and learning algorithm is trained on {(Z,, y.)}. Modern sources, such as high-definition images or genomic sequences, have high dimensionality, and this necessitates diieersionality-redeeee reduction, either for better generalization (Goodfellow et al. 2016)) for storage/communicttion savings (Tsitsiklis) 1989 Nguyen et al., 2209:; Duchi et al. 2018). or for interpretability (Schapire and Freund) 2012). The goal is thus to find a now-dimensional represen- tation= = = R(x) E IR' that preserves the relevant part of the features, without a full knowledge of the downstream prediction task. In this paper, propose a theerttc framework for this goal, by assuming that the learner has prior knowledge on the class of downstream prediction tasks.
Unsupervised methods for dimensionality reduction, such as principal component analysis (PCA) (Pearson 1901 Jolliffe| 2005; Cunningham and Ghahramani 2013) Johnstone and Paul 2018). and
non-linear extensions such kernel PCA (Schölkopf al. 1998) and auto- ancodensoders (AE) (Kramer) 1991 Hinton and Salakhutdinov 2006 Lee et al.] [201]] Goodfellow et al. 2016), aim that the rep- resentation will maximally preserve the variation in ar, and thus ignore any prior knowledge on
future prediction tasks. This prior knowledge may indicate, e.g., that highly varying directions in the feature space are, fact, irrelevant for downstream prediction tasks. From the supervised learn- ing perspective, the information bottleneck (IB) principle (Tishby et al. 20000 Chechik et al.) 2003 Slonim et al. [006]] [Harremoës and Tishby 2007) was used to postulate that effccient supervised learning necessitates representations that are both low-complexity and relevant (Tishby and Za- slavsky 2015 Shwartz-Ziv and Tishby 2017 Shwartz-Ziv 2022 Achille and Soatto 2018a b) (see Appendix A). To corroborate this claim, Dubois al. (2020) proposed game-theoretic formulation (based on a notion of usable information, introduced by Xu et al. (2020)). in which Alice selects a prediction problem of y given æ, and then Bob selects the representation z. The pay-off is the min- imal risk possible using this representation. Dubois et al. (2020) showed that ideal generalization is obtained for representations that solve the resulting decodable 1B problem.

---

Published as a conference paper at ICLR 2024
In this paper, we assume the learner collected unlabeled feature vectors, and has prior knowledge that the downstream prediction problem belongs to a class F of response functions. We propose game different from that of Dubois et al. (2020): First, the representation player chooses rule R to obtain 2 = R(x=) E RR. Second, the response function player chooses y = f(x) where E F is possibly random. The payoff for (R, f) is the regret: The minimal prediction loss of y based on & compared to the minimal prediction loss based on X. The goal of the representation player (resp. response function player) is to minimize (resp. maximize) the payoff, and the output of this game is the saddle point representation. Compared to Dubois et al. (2020), the representation chosen based only on the class of response functions, rather than a specific one. The minimax regrel measures the worst-case regret (over functions in F) of learner that uses the saddle-poing representation. We derive the minimax representation both in pure strategies and in mixed strategies (Owen 2013). Mixed strategies use randomized representation rules, whose utilization is illustrated as follows: Assume that routinely collected images are required to be compressed. There are two compression (representation) methods. The first smoothens the images, and the second preserves their edges; exclusively using the first method would hinder any possibility of making predictions reliant on the image's edges. This is prevented by randomly alternating the use of both methods.
The class F manifests the prior knowledge on the downstream prediction tasks that will use the represented features, and may stem from domain specific considerations; imposed by privacy or fairness constraints; or emerge from transfer or continual learning settings; see Appendix B for an extended discussion. The resulting formulation encompasses an entire spectrum of possibilities: (1) Supervised learning: J = f.f is a singleton, and thus known to the learner. (2) Multitask learn- ing (Baxter 2000 Maurer et al. 2016 Tripuraneni al. 2020: 2021): F {.f.
is a finite set of functions. (3) Prior expert knowledge: F represents a continuous, yer restricted set of functions. For example, the response functions F may be more sensitive to certain features than others. (4) No supervision: F is the class of all possible response functions, which is essentially an unsupervised learning problem, since no valuable information known. We focus on the intermedi- ate regimes of partial supervision, in which the learner should (and can) optimize its representation to be jointly efficient for all tasks in F. In this respect, multitask learning (case 2) is a generalization of supervised learning, since the learner simulate the functions in F. Prior knowledge (case 3) is more similar to unsupervised learning, since the learner will not be able to efficiently do so.
Theoretical contribution We address the fundamental setting in which the representation. the re- sponse, and the prediction are all linear functions, under the mean squared error (MSE) loss (Section 3) The class is Fs = { 1} for a known symmetric matrix S. Combined with the covari- ance matrix of the features, they both determine the relevant directions of the function in the feature space, in contrast to just the features variability, as in standard unsupervised learning. We establish the optimal representation and regret in pure strategies, which shows the utility of the prior informa- tion, and in mixed strategies, which shows that randomizing the representation yields strictly lower regret. We prove that randomizing between merely e different representation rules suffices, where r +15 8" < d is a precisely characterized effective dimension.
Algorithmic contribution We develop an algorithm for optimizing mixed representations (Sec- tion for general repprsentttionn/esoonn/pppeee
and loss functions, based only on their gra- dients. Similarly to boosting (Schapire and Freund| 2012), the algorithm operates incrementally. At each iteration it finds the response function in Ff that is most poorly predicted by the current mixture of representation rules. An additional representation rule is added to the mixture, based on this function and the ones from previous iterations. The functions generated by the algorithm can be considered "self-defined signals", similarly to self-supervised learning (Oord et al., 2018 Shwartz-Ziv and LeCun 2023). To optimize the weights of the representation, the algorithm solves two-player game using the classic multiplicative weights update (MWU) algorithm (Freund and Schapire 1999) (a helluwtthe-rggularizeed leaderrreddeederreeeeeeee algorithm (Shalev-Shward 2012 Hazan 2016)).
Related work In Appendix A we discuss: The IB principle and compare the game of Dubois et al. 2020) with ours; The generalization error bounds of Maurer et al. (2016); Tripuraneni et al. (2020) for multi-task learning and learning-to-lee teamm,, and how our regret bound complements these results; The use of randomization in representation learning, similarly our mixed strategies solution; It- erative algorithms for solving minimax games, and specifically the incremental algorithm approach for learning mixture models (Schapire and Freund 2012) Tolstikhin et al. 2017). which we adopt.
2

---

Published as a conference paper at ICLR 2024
2 PROBLEM FORMULATION
C Specifically, the eigen- values of S $ are denoted as Amax = (1 Z ... Aa(S) Amin (S) and (S) denotes an eigenvector corresponding (S) such that V = =V(S) := (S), (S)). .... Da (a(S)) E Rdxd and S V(S)A(S)V (S) is an eigenvalue decomposition. Way := [wo,. ................................ ,yy E (2--(+))dd is the matrix comprised of the columns of W [Rd indexed by (3......j.. The probability law of random variable æ is denoted as L(x).
Notation conventions are mostly standard, and are detailed in Appendix
Let x E X' be a random feature vector, with probability law Ps := L(z). Let y y be a corre- sponding response drawn according to probability kemel y ~ f(- X = r), where for brevity, we will refer to f as the response function (which can be random). It is known that f E F for some given class F. Let 2 == R(x) E IK" be an r-dimensional representation of a where R: X' - R" is chosen from a class R of representation functions, and let Q: + y be a prediction rule from a class 2x, with the loss function loss: y x y - Rt. The pointwise regret of (R, f) is
regret( R, Pa)= = min E [loss(y, Q(((=)))
min TE [los((y, Q(x)))] qeQx
(1)
Qear
The minimax regret in mixed strategies is the regret of the worst response function in F to an optimal random representation, given by
regret (R. Pa) |
min max E [regret Pa)] L(R)EP(R) FEF
where P(R) is set of probability measures on the possible set of representations R. The minimax regret in pure strategies restricts P(R) to degenerated measures (deterministic), and so the expec- tation in (2) is removed. Our main goal is to determine the optimal representation strategy, either in pure R" E RR or mixed strategies L(R") E P(RR). To this end, we will also utilize the maximin version of (2). Specifically, let P(F) denote a set of probability measures supported on F, and
assume that for any R R. there exists measure in P(R) that puts all its mass on R. Then, the
minimax theorem (Owen 2013, Chapter 2.4) (iion 1958 implies that
max min E [regret(R. P=)] regret (i, |I.F)Pa L(F)EP(F) RER
(3)
The right-hand side of 33) is the maximin regret in mixed strategies, and the maximizing prob- ability law L(f*) is known as the least favorable prior. In general, mix Pa) S regret J (R.FF Pz). and the inequality can be strict. We focus on the representation aspect, and thus assumed that Pæ is known and that sufficient labeled data will be provided to the learner from the subsequent prediction task. We also note that, common in name-theory. the mixed min- imax regret is achieved for repeating representation games (Owen 2013), which fits the scenario in which routinely collected data is be represented. By contrast, the pure minimax regret guarantee is valid for a single representation, and thus more conservative from this aspect.
3 THE LINEAR SETTING UNDER MSE LOSS
In this section, we focus on linear classes and the MSE loss function. The response function class F is characterized by quadratic constraint specified by a matrix S $44. which represents the relative importance of each direction in the feature space in determining y.
Definition (The linear MSE setting). Assume that = R2, that y = R and a squared error loss function loss(11, V2) 1y2 32l2. Assume that E[x] = and let Σ. E[xxx" E ad be its invertible covariance matrix. The classes of representations, response functions, and predictors are all linear, that is: (1) The representation is R(x) R x for R E R Rd where d > r; (2) The response function is f E F C Rdd and y = ʃ x + n E R. where n E RR is a heteroscedastic noise that satisfies En x] = 0, and given some specified S sd $4 it holds that
JEFs= ( Rd: 1)
(4)
where ||f]|s:= ||--1 (f is the Mahalanobis norm; (3) The predictor is Q(2) = q 2 E IR for 9 E RT. Since the regret will depend on P, only via Eg, we will abbreviate the notation of the pure (resp. mixed) minimax regret regret (F E.z)) (resp. regret Ex))
3

---

Published as a conference paper at ICLR 2024
In Appendix E.1 we show that standard PCA can be similarly formulated, by assuming that F a singleton containing the noiseless identity function, so that y = a surely holds, and ă = Qz) E R Proposition 15 therein shows that the pure and mixed minimax representations are both R = Vir (F=)) and so randomization is unnecessary. We begin with the pure minimax regret.
Theorem 2. For the linear MSE setting (Definttoo))
regret pure (Fs Ex) Art1
(5)
A minimax representation malrix is
====1 Virr (E
(6)
and the worst case response function is
f= S2/2 Ur+1 Ur+1 ED -
(7)
The optimal representation thus whitens the feature vector and then projects it the top cigenvectors of the adjusted covariance matrix > syi/ which reflects the prior knowledge that E Fs. The proof in Appendix E.2 has the following outline: Plugging the optimal predictor into the regret results a quadratic form in E R determined by matrix which depends on the subspace spanned by the representation R. The worst-case f is the determined via the Rayleigh quotient theorem, and the optimal R is found via the Courant-Fischer variational characterization (see Appendix for summary of these results). We next consider the mixed minimax regret, which turns out to be more involved:
Theorem 3. For the linear MSE setting (Definition
D. let > = \x 51/2) for i E [d] and
A4+1 0, and let Et be any member of
x S (L - r) Net1
8
(8)
1=1
The minimax regret in mixed strategies is
l P-ン
mix (Fs Ex)
(9)
Σ
The covariance matrix of the least favorable prior of f is
Σg = V VTAV'V Σ A-T
(10)
where Ae == (Ai. O.., and (1/22
The probability law of the minimax representation: Let A (0,1)ex(*) be matrix whose
columns the members of the set A = (a E {0, 1) ||||= 8" rr (in some order). Let b (b1....,bb-) be such that
x-1 Σ
b. (8" r)
(11)
Then, there exists solution E [0, ()*) to Ap b with support size at most 8" +1. For j E [(*"), let I, = Li [ 0} be the indices the jth column of A. and let Vz, denote the columns of V whose index is in Iz. A minimax representation is R Σz 1/22, with probability Pj. for [(5))
The proof of Theorem 3 is also in Appendix E.2 and is substantially more complicated than for the pure regret. The reason is that directly maximizing over L(R) is challenging, and so we take a two-step indirect approach. The outline follows: First, we solve the maximin problem (3) and
4

---

Published as a conference paper at ICLR 2024
find the least favorable prior L(ff). Second, we propose probability law for the representation L(R), and show that its regret equals the maximin value, and thus also the minimax. With more detail, in the first step, we show that the regret only depends on L(f) via Eg = Elff J. and we explicitly construct L(f) that is supported on Fs and has this covariance matrix. This reduces the problem from optimizing L(f) to optimizing Sg whose solution (Lemma 17 results the least favorable Σj. and then the maximin value. In the second step, we construct representation that achieves the maximin regret. Concretely, we construct representation matrices that of the E principal components of E ///// where 8" > r. The defining property of E" 8 established in the maximin solution, is utilized to find proper weights on the (")) possible representations, which achieve the maximin solution, and thus also the minimax. The proof then uses Carathéodory's
theorem (see Appendix DD to establish that the optimal (py) is supported on at most l" + matrices,
much less than the potential support size of (c)) We next make a few comments:
1. Computing the mixed minimax probability: This requires solving A p b for probability vector p. This is a sinear-program feasibility problem, which is routinely solved (Bertsimas and Tsitsiklis 1997). For illustration, if = 1 then pj = 1 (e* 1)A7" x for j E [f*], and if - then Pj (X7))((} ) on the first l" standard basis vectors. Nonetheless, the dimension of p is (*) and thus increases fast as ((()))") which is infeasible for high dimensions. In this case, the algorithm of Section 4 can be used. As we empirically show it approximately achieves the optimal regret, with slightly more than e + 1 atoms (see henceforth..
The rank of E The rank of the covariance matrix of the least favorable prior an effective dimension, satisfying (see (9)
1- (r/1)
arginax (r( 1 >
(12)
By convention, {A,1 heeld is monotonic non-decreasing sequence, and so is the partial Cesàro mean v5()) == : E A;- For example, if X; = =i- i-a with a > 0 then vb({) ((()) So, if, e.g.. (b))= = f", then it is easily derived that L* = min aaaraarrr r, d, Hence, a 2 d-r is large enough and the decay rate of {A,) is fast enough then e < d. but otherwise l = d. As the decay rate of {}} becomes faster, the rank of y decreases from d to r + 1. Importantly, 8" 2 + + 1 always holds, and so the optimal mixed representation is not deterministic even if S / significant eigenvalues (which can be represented by a single matrix R E Rd* Hence. the mixed minimax regret is always strictly lower than the pure minimax regret. Thus, even when S = la and no valuable prior knowledge is known on the response function, the mixed minimax representation different from the standard PCA solution of top r eigenvectors of Σne.
has less than
3. Uniqueness of the optimal representation: Since one can always post-multiply R x by some invertible matrix, and then pre-multiply 2 = RT x by its inverse, the following holds: If R and Q not further restricted, then if R is minimax representation, and W(R) RR"x is an invertible matrix, then R. W (R) is also a minimax representation.
4. dimensooal features: Theorems 2 and 3 assume finite dimensional feature space. We show in Appendix [ that the results can be generalized to an infinite dimensional Hilbert space X, in the more restrictive setting that the noise n is statistically independent of æ..
Example 4. Assume S = Ta. and denote, for brevity, V = V(E.)) = [ui,...,, tal and A =
A(E.)) = Blag((A,..... >a)- The optimal minimax representation in pure strategies (Theorem 2 is
R -- 1-/ V1.- VA 1/ = VA_1/2 [ei....,e,) e,l [=|= = [>_ 1/2 UI
X- 1/2
(13)
which is comprised of the top r eigenvectors of Ee, scaled so that vi x has unit variance. By Comment 3 above, Var also an optimal minimax representation. The worst case response is = 1 (Ex) and, as expected, since R. uses the first principal directions
regret (F
>g
= A141-
(14)
The minimax regret in mixed strategies (Theorem
3 is different, and given by
8"
regret
(F En)
(15)
Σ A-1
5

---

Published as a conference paper at ICLR 2024
14 110
12
404
0.
0.4
1.5
2.5
2.5
3.5
Figure 1: Left: Pure and mixed minimax regret and l. for Example 4 for d = 50, 25, with A; of x i-a. Right: Pure and mixed minimax regret and e, for Example for d 50, r 25, with of x xi and s; x 2. The trend of L, is reversed for 2.
where lx is determined by the decay of the eigenvalues of En (see (8) The least favorable covariance matrix is given by (Theorem
b
V diaa (A ...... 1 00. -)
(16)
Intuitively, >ig equalizes the first e" cigenvalues of Ei 2ig (and nulls the other d - (*), to make the representation indifferent to these 8" directions. As evident from the regret. the "equalization" of the ith eigenvalue adds term of X to the denominator, and if X for the representation. This agrees with Comment which states that fast decay of {)e} reduces E. away from d. A derivation similar to [3) shows that the mixed minimax representation sets
small then is not chosen
R = 1/2 Vz,
-1/2 Ui........, A1y.
(17)
with probability Py. where I, = fd..,..... 2.. Thus, the optimal representation chooses a random subset of vectors from fui...., M2- J. See the left panel of Figure | for a numerical example.
Example 5. To demonstrate the effect of prior knowledge on the response function, we assume En = ..... o3) and S = diag(s1, ($1,..., sa), where of 2 ož 2 ... 2 of (but (ss)ie are not necessarily ordered). Letting f (a,). the class response functions Fs {f E Rd: ( I 1}. and so coordinates i E [d] with a large have large influence on the response. Let (i(z),.... i(4)) be a permutation of [d] so that byy) 81()) it the jth largest value of (o)s)) The pure minimax regret is (Theorem 2
regret (F Exee br $1,41*
(18)
The optimal representation is R [Ciny Gipz). Cigr) that is, uses the most influential coordi- nates, according to {si}, which may be different from the principal directions of Eg. For the minimax regret in mixed strategies, Theorem results
regret (F
Σx)
(19)
Σx= (8,
for t" E [d]]r] satisfying 8 and the covariance matrix of the least favorable prior is given by Σラ Σf 0, e
(20)
(5,
That is, the matrix is diagonal, and the kth term on the diagonal is (k, o 2 i, for some j E [e*] and >i (k: k) 0 otherwise. As in Example Mi equalizes the first l" eigenvalues of Ey (and nulls the other d - (*). However, it does so in a manner that chooses them according their influence on the response T The minimax representation mixed strategies is
(21) with probability py. Again, the first 0" coordinates used, and not just the top See the right panel of Figure for a numerical example. Naturally, in the non- -in--ia case, the minimax regret will also depend on the relative alignment between S and Σzz.
R" ory, -i,,11...,, Eig.

---

Published as a conference paper at ICLR 2024
4 AN ALGORITHM FOR GENERAL CLASSES AND LOSS FUNCTIONS
In this section, we propose an iterative algorithm for optimizing the representation in mixed strate- gies, i.e., solving (2) for general classes and loss functions. The algorithm will find finite mixture of representations, and so we let R R(5) R with probability p( for [m]] (this suffices for the linear MSE setting of Section 3 but possibly sub-optimal in general). The main idea is to incrementally add representations R to the mixture. Loosely speaking, the algorithm is initialized with a single representation rule R()) Then, the response function in F which is most poorly pre- dicted when æ is represented by (x)) is found. The added representation component R(2) aims to allow for accurate prediction of this function. At the next iteration, the function in F which is most poorly predicted by a mixed representation that randomly uses either R(() or R(2) is found, and R(3) is then optimized to reduce the regret for this function, and so on.
The actual algorithm is more complicated, since it also finds proper weights {p(r) je[m]] for the representation rules, and also randomizes the response player. Thus we set f = f() E F with probability o*) where E [m]. and nπ = mo + m for some mo 2 0. The resulting optimization problem then becomes
min ERRR) (97))
max
Σ
(b) 6l0) (eg) Pa),
(22)
jElm] (m[m
where {pb) ]e{[m] and (ol0) hie[m] are probability vectors. The ultimate goal of solving 22 is just to extract the optimal randomized representation R. given by (R())p()) p())))
Henceforth, the index k: E [m]] will denote the current number of representations. Initialization requires a representation (2(1) as well as set of functionn {f() Jiemo so that the final support size of f will be mo + m. Finding this initial representation and the set of functions based on the specific loss function and the set of representations/prdiicee
(see Appendix G for examples). The algorithm has two phases for each iteration. In the first phase, a new adversarial function added to the set of functions, as the worse function for the current random representation. In the second phase, a new representation atom is added the set of possible representations. This representation is determined based on the given set of functions. Concretely, at iteration k:
Phase 1 (Finding adversarial function): Given k representations (R()))E(R) with weights (p()) be(() the algorithm determines fl (moo as the worst function, by solving
regg- regret ((P(()) DSENN)
]SE(K): F Pa) max JEF
Σ (1)) ( Pa),
(23)
jE(R]
and (m)++)) is set to be the maximizer. This simplifies that the random representation R is kept fixed, and that previous functions (f())
22 in the sense that is replaced by k F is optimized as a pure strategy (the
[i ( are ignored).
Phase 2 (Adding representation atom): Given fixed { [Emoo++] and (RO) JEM new representation R(++1) is found as the most incrementally valuable representation atom, by solving
min regret ((a())), (f Pa) R
min min ΣΣ pli)) ,02)) regret (R(i), ((b) Pa)
(24)
R
(pir)) 3oli2)) J1 12
where ji E [k: + 1] and ja [ma + kt), the solution R(++1) is added to the representations, and the weights are updated to the optimal {p(ht}. Compared to (22). the response functions and first k representations are kept fixed, and only the weights (n(h)) ((02) } and R(++1) are optimized.
The procedure is described in Algorithm where, following the main loop, m = argmin reg, representation atoms are chosen and the output is {R(1), ((() Ligjm]]. Algorithm I relies on solvers for the Phase (23) and Phase (44) problems. In Appendix G we propose two algorithms for these problems, which are based on gradient steps for updating the adversarial response (assuming F is
7

---

Published as a conference paper at ICLR 2024
continuous class) and the new representation, and on the MWU algorithm (Freund and Schapire 1999) for updating the weights. In short, the Phase I algorithm updates the response function f projected gradient step of the expected loss, and then adjusts the predictors {Q to the updated response function f and the current representations {R()) JE(M) The Phase 2 algorithm only updates the new representation R(*+1) via projected gradient steps, while keeping {R0)) ]eem fixed. Given the representations (R()) je[M++1] and the functions {f(')
(mo ( a predictor Q is then fitted to each representation-fume function pair, which also determines the loss for this pair. The weights {pl) [ and ]oll) are updated towards the equilibrium of the two-player game determined by the loss of the predictors (Q(4.)) [je(k+ [ i),i via the MWU algorithm. In a multi-tast learning setting, in which the class F is finite, the Phase solver can be replaced by a performing simple maximization over the functions.
Algorithm Solver of (22): An iterative algorithm for learning mixed representations.
1: input Pæ. F.F, Q, r, mo
b Feature distribution, classes, dimensions and parameters > Initial representation and initial function (set)
2: input R()) { )e/mml
3: begin
4: for k to m do
5: phase 1: f(mo+h)) is set by a solver of 23 and:
Solved using Algorithm
2
rega f- regret (f (R(), p(0) p [E Pa))
(25)
6: phase 2: (()+1),, (Pk Je(++1 is set by a solver of (24g
()
b Solved using Algorithm
7: end for
8: set m = ar argminke[m] regı
9: return (R be(m=) and Pm. = {Pk [jejm]]
Since Algorithm aaims to solve a non convex-concave minimax game, deriving theoretical bounds on its convergence seems to be elusive at this point (see Appendix A for discussion). We next describe a few experiments with the algorithm (See Appendix for details).
Example 6. We validated Algorithm I in the linear MSE setting (Section B}, for which closed- form solution exists. We ran Algorithm on randomly drawn diagonal Vg, and computed the ratio between the regret obtained by the algorithm to the theoretical value. The left panel of Figure shows that the ratio is between 1.15 1.2 in a wide range of d values. Algorithm
| is also useful for this setting since finding an (e* + spsase solution to Ap- = b is computationally difficult when is very large (e.g., in the largest dimension of the experiment (c) = (35) = 628).
Our next example pertains logistic regression setting, under the cross-entropy loss function. Definition 7 (The linear cross-entropy setting). Assume that X' = Rdd that y = {+1) and that R[x:] = 0. Assume that the class of representation is linear Rdxr where d > r. Assume that a response function and a prediction rule determine the probability that y = via logistic regression modeling,
R(x) R for some R E R
fly =1 x) 1/[1 + exp(=f T))]. Assume the cross-entropy loss function, where given that the prediction that y 1 with probability results the loss loss(y. q) = ) + y) log q
1 (1 y) log(1 q). The set of predictor functions is 2
@ = {Q(2) = 1/[1 + exp( - =)}, q E RT). As for the lincar case, we assume that f E Fs for some 5 E 4. The regret is then given by the expected binary Kullback-Leibler (KL) divergence
regret(R, Pa)
min [DKL. ([L + exxp(=1 f x)] |I [1 exp( -pp--9TA R -)]- (26)
qERr
Example 8. We drawn empirical distributions of features from isotropic normal distribution, in the linear cross-entropy setting. We ran Algorithm I Juiin the closed-form regret gradients from Appendix H The right panel of Figure the reduced regret obtained by increasing the support size m of the random representation, and thus the efficttivneess of mixed representations.
The last example compares the optimized representation with that of PCA.
Example 9 (Comparison with PCA for multi-label classification). We constructed a dataset of im- ages, each containing 4 shapes randomly selected from dictionary of 6 shapes. The class J is
8

---

Published as a conference paper at ICLR 2024
130
Figure 2: Results of Algorithm Left: r 5, varying The ratio between the regret achieved by Algorithm and the theoretical regret in the linear MSE setting. Right: r 3, varying d. The regret achieved by Algorithm in the linear cross-entropy setting, various m.
Poan POR ues Age Lon
1.2
PCI
Adp act
Figure 3: Results on the dataset of images. Comparison between optimized minimax representation (simplified version of [lgorithm]] vs. PCA. Worst-case function in blue, and average-case function orange. Left: Cross entropy loss. Right: Accuracy.
finite and contains the t = 6 binary classification functions given by indicators for each shape. The representation linear and the predictor is based on logistic regression. In this setting, Algorithm can be simplified; See Appendix H.3] for details (specifically Definition 23 of the setting and Figure for an image example). We ran the simplified version of Algorithm
[ on dataset of 1000 images, and compared the cross-entropy loss and the accuracy of optimized representation to that of PCA on a fresh dataset of 1000 images. The results in Figure 3 show that the regret of PCA is much larger, not only for the worse-case function but also for the average-cas function. For example, using the representation obtained by the algorithm with r = 3 < is as good as PCA with at least r = 12.
5 CONCLUSION
We proposed a game-theoreti, formulation for learning feature representations when prior knowl- edge on the class of downstream prediction tasks is available. Interestingly, our formulation links between the problem of finding jointly efficient representations for multiple prediction tasks, and the problem finding saddle points of wat--ooovcoooncoccceee ing problem and is under active research (see Appendix [A). So, any advances in that domain can be translated to improve representation learning. Similarly to our problem, foundation models also adapt wide range of downstream prediction tasks, however, efficient learning is achieved therein without explicit prior knowledge on the class of downstream tasks, albeit using fine-tuning. is interesting incorporate minimax formulations into the training procedure of foundation models, or to explain them using similar game formulations.
games. The latter is a challeng-
For future research it would be interesting: (1) To generalize the class Fs [f:lsflss 1) used for linear functions to the class Fs, == E|| f()) 2 < for non non-linear functions, where {S, 1 now locally specified (somewhat similarly the regularization term used in contractive AE (ifal
et al. 2011) though for different reasons). (2) To efficiently learn S from previous experience, e.g., improving from one episode to another in meta- leea-learning setup (Hospedales al. 2021). (3) To evaluate the effectiveness of the learned representation in our formulation, an initialization for fur- ther optimization when labeled data collected. One may postulate that our learned representation may serve as universal initialization for such training.

---

Published as a conference paper at ICLR 2024
ETHICS STATEMENT
The research described this paper is foundational, and does not aim for any specific application. Nonetheless, the learned representation based on a prior assumption on the class of response func- tions, and the choice of this prior may have positive or negative impacts: For example, a risk of this choice of prior is that the represented features completely ignore a viable feature for making down- stream predictions. A benefit that can stem from choosing a proper prior is that the representation will null the effect of features that lead to unfair advantages for some partieular group in downstream predictions. Anyhow, the results presented in the paper are indifferent to such future utilization, and any usage of these results should take into account the aforementioned possible implications.
REPRODUCIBILITY STATEMENT
For the theoretical statements, full proofs appear in Appendices and F order to ease the reader, summary of the main mathematical results used appears in Appendix D For the experimental re- sults, a detailed description of the algorithm and experiments appears in Appendix HH This descrip- tion includes accurate description of the Phase and 2 solvers, initialization methods, explicit formulas for the gradients used, algorithm parameters, details on the generation of the dataset, and implementations details. The code for the experiments available at this link
ACKNOWLEDGMENTS
This research was partially supported by the Israel Science Foundation (ISF), grant no. 1782/22.
REFERENCES
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
John N. Tsitsiklis. Decentralized detection. 1989.
XuanLong Nguyen, Martin J. Wainwright, and Michael Jordan. On surrogate loss functions and f-divergences. The Annals of Statistics, 37(2):876 904, 2009, doi: 10.1214/08-A05595. URL
https::/ddi.orgg
1214/08 AO5595
John Duchi, Khashayar Khosravi, and Feng Ruan. Multiclass classification, information, divergence and surrogate risk. Annals of Statistics, 32466)33346-3275, 2018. ISSN 0090-5364. doi: 12.1214/
17-AOS1657.
Robert E. Schapire and Yoav Freund. Boosting: Foundations and Algorithms. The MIT Press, 2012. ISBN 0262017180.
Karl Pearson. On lines and planes of closest fit to systems of points in space. The London, Edin- burgh, and Dublin philosophical magazine and journal of science, 2(11):559-572, 1901.
Ian Jolliffe. Principal component analysis. Encyclopedia of statistics in behavioral science, 2005.
John P. Cunningham and Zoubin Ghahramani. Linear dimensionality reduction: Survey, insights, and generalizations. The Journal of Machine Learning Research, 16(1):2859-290) 2015.
lain M. Johnstone and Debashis Paul. PCA high dimensions: An orientation. Proceedings of the
IEEE, 106(8): 2018
Bernhard Schölkopf, Alexander Smola, and Klaus-Robert Müller. Nonlinear component analysis as kernel eigenvalue problem. Neural computation, (V5):1229-1111) 1998.
Mark A. Kramer. Nonlinear principal component analysis using autoassociative neural networks. AIChE journal, 37(2).233-243 1991.
Geoffrey E. Hinton and Ruslan R. Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 313(5786):504-507 2006.
10

---

Published as a conference paper at ICLR 2024
Honglak Lee, Roger Grosse, Rajesh Ranganath, and Andrew Y. Ng. Unsupervised learning of hierarchical representations with convolutional deep belief networks. Communications of the ACM, 14(10):55-033 2011. 2011.
Naftali Tishby, Fernando C. Pereira, and William Bialek. The information bottleneck method. arXiv preprint physicx/0004057, 2000.
Gal Chechik, Amir Globerson, Naftali Tishby, and Yair Weiss. Information bottleneck for Gaussian variables. Advances Neural Information Processing Systems, 16, 2003.
Noam Slonim, Nir Friedman, and Naftali Tishby. Multivariate information bottleneck. Neural computation, 18(8):1739-1788 2006.
Peter Harremoës and Naftali Tishby. The information bottleneck revisited or how to choose good distortion measure. In 2007 IEEE International Symposium on Information Theory, pages 566- 570. IEEE, 2007.
Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle. In 2015 ieee information theory workshop, pages 1-5. IEEE, 2015.
Ravid Shwartz-Ziv and Naftali Tishby, Opening the black box of deep neural networks via informa- tion. arXiv preprint
2017.
Ravid Shwartz-Ziv. 2022.
Information flow in deep neural networks. arXiv preprint arXiv:2202.06749,
Alessandro Achille and Stefano Soatto. Emergence of invariance and disentanglement in deep rep- resentations. The Journal of Machine Learning Research, 19(1):1947-198)) 2018a.
Alessandro Achille and Stefano Soatto. Information dropout: Learning optimal representations through noisy computation. IEEE transactions pattem analysis and machine intelligence, 40 (12):2897-2905, 2018b.
Yann Dubois, Douwe Kiela, David J. Schwab, and Ramakrishna Vedantam. Learning optimal repre- sentations with the decodable information bottleneck. Advances in Neural Information Processing Systems, 33: 8674-18690, 2020.
Yilun Xu, Shengjia Zhao, Jiaming Song, Russell Stewart, and Stefano Ermon. A theory of usable information under computational constraints. arXiv preprint arXiv:2002.10689, 2020.
Guillermo Owen. Game theory. Emerald Group Publishing, 2013.
Jonathan Baxter. A model inductive bias learning. Journal of artificial intelligence research, 12: 149-198, 2000.
Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. Journal of Machine Learning Research, 17(81):1-32, 2016.
Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory of transfer learning: The importance of task diversity. Advances in neural information processing systems, 33:7852-7862, 2020.
Nilesh Tripuraneni, Chi Jin, and Michael Jordan. Provable meta-learning of linear representations. In International Conference on Machine Learning, pages 10434-10443, PMLR, 2021.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. arXiv preprint arXiv: 00040037488.. 2018
Ravid Shwartz-Ziv and Yann LeCun. To compress or not to compress self- supervsee learning and information theory: A review. arXiv preprint MXXv:2204.00335 2023.
Yoav Freund and Robert E. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, (9(1-)):79-133 1999.
Shai Shalev- Shwart, Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 4(2):177-194 2012.
11

---

Published as a conference paper at ICLR 2024
Elad Hazan. Introduction to online convex optimization. Foundations and Trends@) in Optinization, 2(3-4):57-3325 2016.
Ilya O. Tolstikhin, Sylvain Gelly, Olivier Bousquet, Carl-Johann Simon-Gabriel, and Bernhard Schölkopf. Adagan: Boosting generative models. Advances neural information processing systems, 30, 2017.
Maurice Sion. On general minimax theorems. 1958.
Dimitris Bertsimas and John N. Tsitsiklis. Introduction to linear optimization, volume 6. Athena scientific Belmont, MA, 1997.
Salah Rifai, Pascal Vincent, Xavier Muller, Xavier Glorot, and Yoshua Bengio. Contractive auto- encoders: Explicit invariance during feature extraction. In Proceedings of the 28th international conference on international conference on machine learning, pages 833-840, 2011.
Timothy Hospedales, Antreas Antoniou, Paul Micaelli, and Amos Storkey, Meta-learning in neural networks: survey. IEEE transactions on pattern analysis and machine intelligence, 44(9); 2021.
M. Cover and A. Thomas. Elements of Information Theory. Wiley-Interscience, 2006. ISBN 0471241954.
Stephen Boyd, Stephen Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge uni- versity press, 2004.
Ohad Shamir, Sivan Sabato, and Naftali Tishby. Learning and generalization with the information bottleneck. T'heoretical Computer Science, 41 (29923)):2666-2222 2010.
Andrew M. Saxe, Yamini Bansal, Joel Dapello, Madhu Advani, Artemy Kolchinsky, Brendan D. Tracey, and David D. Cox. On the information bottleneck theory of deep learning. Journal of Statistical Mechanics: Theory and Experiment, 2019(12):124022) 2019.
Bernhard C. Geiger. On information plane analyses of neural network classifiers- review. IEEE Transactions Neural Networks and Learning Systems, 2021.
XuanLong Nguyen, Martin J. Wainwright, and Michael I. Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory, 36(11):5847-333 2010.
Ben Poole, Sherjil Ozair, Aäron van den Oord, Alexander A. Alemi, and George Tucker, On vari- ational lower bounds of mutual information. NeurIPS Workshop on Bayesian Deep Learning, 2018.
Tailin Wu, Ian Fischer, Isaac L. Chuang, and Max Tegmark. Learnability for the information bottle- neck. In Uncertainty in Artificial Intelligence, pages 1050-1060. PMLR, 2020.
David McAllester and Karl Stratos. Formal limitations the measurement of mutual information. In International Conference on Artificial Intelligence and Statistics, pages 875-884, PMLR, 2020.
Matthew Chalk, Olivier Marre, and Gasper Tkacik. Relevant sparse codes with variational informa- tion bottleneck. Advances in Neural Information Processing Systems, 29, 2016.
Alexander A Alemi, Ian Fischer, Joshua V Dillon, and Kevin Murphy. Deep variational information bottleneck. arXiv preprint arXiv:1612.00411 2016.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm. Mutual information neural estimation. In International conference on machine learning, pages 531-540. PMLR, 2018
Behrooz Razeghi, Flavio P. Calmon, Deniz Gunduz, and Slava Voloshynovskiy. Bottlenecks CLUB: Unifying information-theoree trade-offs among complexity, leakage, and utility. arXiv preprint arXiv:2207. 04895, 2022.
12

---

Published as a conference paper at ICLR 2024
Matías Vera, Pablo Piantanida, and Leonardo Rey Vega. The role of information complexity and randomization in representation learning. arXiv preprint arXiv: 2018.
Borja Rodriguez Galvez. The information bottleneck: Connections to other problems, learning and exploration of the curve, 2019.
Peter L. Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):443-482, 2002.
Martin J. Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
Karthik Sridharan and Sham M. Kakade. An information theoretic framework for multi-view learn- ing. 2008
Rana Ali Amjad and Bernhard C. Geiger. Learning representations for neural network-based clas- sification using the information bottleneck principle. IEEE trunsactions pullern analysis and machine intelligence, 42(9):2225-22)
2019.
Artemy Kolchinsky, Brendan D. Tracey, and David H. Wolpert. Nonlinear information bottleneck. Entropy, 21(12):1181, 2019.
D. Strouse and David Schwab. The information bottleneck and geometric clustering. Neural computation, 3 31(3):59-611, 2019.
Ankit Pensia, Varun Jog, and Po-Ling Loh. Extracting robust and accurate features via robust information bottleneck. JEEE Journal on Selected Areas in Information Theory, 1(1):311-144 2020.
Shahab Asoodeh and Flavio Calmon. Bottleneck problems: An information and estimation- thcoretic view. Entropy, 22(11): 2020.
Vudtiwat Ngampruetikorn and David J. Schwab. Perturbation theory for the information bottleneck.
Advances in Neural Information Processing Systems, 34:21008-21018, 2021.
Xi Yu, Shujian Yu, and José C Príncipe. Deep deterministic information bottleneck with matrix- based entropy functional. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3160-3164. IEEF, 2021.
Vudtiwat Ngampruetikorn and David J. Schwab. Information bottleneck theory of high-dimensional regression: Relevancy, efficiency and optimality. arXiv preprint urXiv:2208.03844 2022.
Deniz Gündüz, Zhijin Qin, Inaki Estella Aguerri, Harpreet S Dhillon, Zhaohui Yang, Aylin Yener, Kai Kit Wong, and Chan-Byoung Chae. Beyond transmitting bits: Context, semanties, and task- oriented communications. IEEE Journal Selected Areas in Communications, 41(1):5-41, 2022.
Vudtiwat Ngampruetikorn and David J. Schwab. Generalized information bottleneck for Gaussian variables. arXiv preprini arXiv:2303. 2023.
Vudtiwat Ngampruetikorn, William Bialek, and David Schwab. Information-bottteneee renormal- ization group for self-supervised representation learning. Bulletin of the American Physical Soci- ety, 65, 2020.
Andreas Argyriou, Theodoros Evgeniou, and Massimiliano Pontil. Multi-task feature learning. Ad- vances in neural information processing systems, 19, 2006.
Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint arXiv:2002.094 0944444 2020.
William B. Johnson. Extensions of Lipschitz mappings into a Hilbert space. Contemp. Math., 26: 189-206, 1984.
13

---

Published as a conference paper at ICLR 2024
Santosh S. Vempala. The random projection method, volume 63. American Mathematical Soc., 2005.
Michael W. Mahoney et al. Randomized algorithms for matrices and data. Foundations and Trends in Machine Learning, 3(2):123 224, 2011.
David P. Woodruff al. Sketching tool for numerical linear algebra. Foundations and Trends in l'heoreiical Computer Science, 10(1-2):1-157 2014.
Fan Yang, Sifan Liu, Edgar Dobriban, and David Woodruff. How to reduce dimension with PCA
and random projections? IEEE Transactions Information Theory, 67(12):1154-8189, 2021.
John F. Nash Jr. Equilibrium points in n-person games. Proceedings of the national academy of sciences, 36(1) 36(1))48-49) 1950.
Abraham Wald. Contributions to the theory of statistical estimation and testing hypotheses. The Annals of Mathematical Statistics, 10(4):299-326, 1939.
Larry Wasserman. All of statistics: A concise course in statistical inference, volume 26. Springer, 2004.
Yuhong Yang and Andrew Barron. Information-theorret determination of minimax rates of conver- gence. Annals of Statistics, pages 1564-1599, 1999.
Peter Grünwald and A. Philip Dawid. Game theory, maximum entropy, minimum discrepancy and robust bayesian decision theory. The Annals of Statistics, 32(4):1367-1433, 2004.
David Haussler and Manfred Opper. Mutual information, metric entropy and cumulative relative entropy risk. The Annals of Statistics, 25(6):2451-2492, 1997.
Farzan Farnia and David Tse. A minimax approach to supervised learning. Advances in Neural Information Processing Systems, 29, 2016.
Jorge Silva and Felipe Tobar. On the interplay between information loss and operation loss in repre- sentations for classification. In International Conference on Artificial Intelligence and Statistics, pages 4853 4871. PMLR, 2022.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 63111):1399144, 2020.
Antonia Creswell, Tom White, Vincent Dumoulin, Kai Arulkumaran, Biswa Sengupta, and Anil A. Bharath. Generative adversarial networks: An overview. IEEE signal processing magazine, 35 (1):53-65, 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1766.06883, 2017.
Aharon Ben-Tal, Laurent Ghaoui, and Arkadi Nemirovski. Robust optimization, volume 28.
Princeton university press, 2009.
Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training GANs. Advances in neural information processing systems, 29, 2016.
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algorithms for zero-sum games. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms,, pages 235-254. SIAM, 2011.
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable quences. Advances in Neural Information Processing Systems, 26, 2013.
James P. Bailey and Georgios Piliouras. Multiplicative weights update in zero-sum games. In Proceedings of the 2018 ACM Conference Economics and Computation, pages 321-338, 2018.
14

---

Published as a conference paper at ICLR 2024
Guodong Zhang, Yuanhao Wang, Laurent Lessard, and Roger B. Grosse. Near-optimal local con- vergence alternating gradient descent-ascent for minimax optimization. In International Con- ference Artificial Intelligence and Statistics, pages 7659-7679. PMLR, 2022.
Florian Schäfer and Anima Anandkumar. Competitive gradient descent. Advances in Neural Infor- mation Processing Systems, 32, 2019.
Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of GANs. Advances in neural information processing systems, 30, 2017.
Alistair Letcher, David Balduzzi, Sébastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. Differentiable game mechanics. The Journal of Machine Learning Research, 20(1):3032-077, 2019.
Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang, Si- mon Lacoste-Julien, and Ioannis Mitliagkas. Negative momentum for improved game dynamics. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1802-1811. PMLR, 2019.
Guodong Zhang and Yuanhao Wang- the suboptimality of negative momentum for minimax optimization. In International Conference Artificial Intelligence and Statistics, pages 2098- 2106. PMLR, 2021.
Max Welling, Richard Zemel, and Geoffrey F. Hinton. Self supervised boosting. Advances in neural information processing systems, 15, 2002.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- fion processing systems, 30, 2017.
Jacob Devlin, Ming- Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805. 2018.
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. arXiv preprint arXiv:0902.3433 2009.
Shai Dev-Da John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wort- man Vaughan. A theory of learning from different domains. Machine learning, 79:151-175, 2010.
Friedemann Zenke, Ben Poole, and Surya Ganguli. Continual learning through synaptic intelligence. In International conference on machine learning, pages 3987-3995. PMLR, 2017.
Cuong V Nguyen, Yingzhen Li, Thang D Bui, and Richard E Turner. Variational continual learning. arXiv preprint arXiv: 1010. 2017.
Gido M Van de Ven and Andreas S Tolias. Three scenarios for continual learning. arXiv preprint arXiv:1904.07733 2019.
Rahaf Aljundi, Klaas Kelchtermans, and Tinne Tuytelaars. Task-free continual learning, In Proceed- ings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11254 11263, 2019.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Roger A. Horn and Charles R. Johnson. Matrix analysis. Cambridge university press, 2012.
Dimitri Bertsekas, Angelia Nedic, and Asuman Ozdaglar. Convex analysis and optimization, vol- ume Athena Scientific, 2003.
Ky Fan. On a theorem of Weyl concerning eigenvalues linear transformations Proceedings of the National Academy Sciences, 35(1 1):622-6555 1949.
15

---

Published as a conference paper at ICLR 2024
The outline of the supplementary material is as follows. In Appendix A review additional related work. In Appendix [ we discuss in detail the origin of prior knowledge of classes of prediction problems. In Appendix [ we set notation conventions. In Appendix D we summarize a few mathematical results that are used in later proofs. In Appendix we show that PCA can be cast as a degenerate setting of our formulation, and provide the proofs of the main theorems in the paper (the linear MSE setting). In Appendix
F we generalize these results to an infinite dimensional Hilbert space. In Appendix G we provide two algorithms for solving the Phase and Phase problems in Algorithm|| I In Appendix H we provide details on the examples for the experiments with the iterative algorithm, and additional experiments.
A ADDITIONAL RELATED WORK
The information bottleneck principle The IB principle is prominent approach to feature rel- evance in the design of representations (Tishby et al. 2000) Chechik et al. [2003] Slonim et al.) 2006 Harremoës and Tishby 2007), and proposes to optimize the representation in order to maxi- mize its relevance to the response y. Letting [(z; y) and [(a;; denote the corresponding mutual information terms (Cover and Thomas, 2006). the IB principle aims to maximize the former while constraining the latter from above, and this is typically achieved via a Lagrangian formulation (Boyd et al. 2004). The resulting representation, however, is tailored to the joint distribution of (az, y), i.e., to a specific prediction task. In practice, this is achieved using a labeled dataset (generalization bounds were derived by /hhamir et al. (2010). As in our mixed representation approach, the use of randomized representation dictated by probability kernel f(- principle.
I) is inherent to the IB
A general observation made from exploring deep neural networks (DNNs) (Goodfellow et al. 2016) used for classification, is that practically good predictors in fact first learn an efficient representation of the features, and then just train simple predictor from to the response y f(x). This is claimed to be quantified by the IB where low mutual information [(x; 2) indicates an efficient rep- resentation, and high mutual information [(2; y) indicates that the representation allows for efficient prediction. This idea has been further developed using the IB principle, by hypothesizing that mod- ern prediction algorithms must intrinsically include learning an efficient representation (Tishby and Zaslavsky 2015 Shwartz- Ziv and Tishby 2017: Shwartz- Ziv 2022; Achille and Soatto 201 Sa b)
(this spurred a debate, see, e.g., (Saxe et al. 2019 Geiger 2021 )).
However, this approach is inadequate in our setting, since the prediction task is not completely spec- ified the learner, and in the IB formulation the optimal representation depends on the response variable (so that labeled data should be provided to the learner). In addition, as explained by Dubois jet al. (2020), while the resulting IB solution provides a fundamental limit for the problem, also suffers from multiple theoretical and practical issues. The first main issue is that the mutual infor- mation terms are inherently difficult to estimate from finite samples (Shamir et al., 2010: Nguyen et al. 2010 Poole et al. 2018; Wu et al. 2020 McAllester and Stratos 2020)). especially at high di- mensions, and thus require resorting to approximations, c.g., variational bounds (Chalk et al. 2016
Alemi al., 2016: Belg delghazi et al. 2018 Razeghi et 2022). The resulting generalization bounds (Shaiir et al. 2010 Vera et al." 2018) are still vacuous for modern settings (Rodriguez Galvez, 2019). The second main issue is that the IB formulation does not constrain the complexity of the representation and the prediction rule, which can be arbitrarily complex. These issues were ad- dressed by Dubois et al. (2020) using the notion of usable information, previously introduced by Xu et al. (020)): The standard mutual information yzz;y) can be described as the log-loss difference between a predictor for z which does not use or does use y (or vice-versa. since mutual infor- mation is symmetric). Usable information, or F-information 1z(= - y). restricts the predictor to a class FF which is computationally constrained. Several desirable properties were established in Xu et al. (2020) for the F-information, c.g., probably approximate correct (PAC) bounds via sodemmcchr--ommlexity based bounds (Bartlett and Mendelson 2002) (Wainwright) 2019 Chapter
5) (Shalev-Shwartz and Ben- BaviD 2014] Chapters 26-28).
Dubois et al. (2020) used the notion of F-information to define the decodable IB problem, with the goal of assessing the generalization capabilities of this IB problem, and shedding light on the necessity of efficient representation for generalization. To this end, a game was proposed. in which the data available to the learner are feature-response pairs (æ, y) (in notation y = f())). In
16

---

Published as a conference paper at ICLR 2024
the game proposed by Dubois et al. (2020). Alice chooses prediction problem f(-), i..., feature- response pair (x: y), and Bob chooses a representation & = R(x). For comparison, in this paper, assume that the learner is given features and a class F of prediction problems. We ask how to choose the representation R if it is only known that the response function Y = f(X) can be chosen adversarially from F. In our formulated game, the order of plays is thus different. First, the representation player chooses R. and then the adversarial function player chooses f E F. Beyond those works, the IB framework has drawn significant recent attention, and remarkable number of extensions and ramifications have been proposed (Sridharan and Kakade 2008,) Amjad and Geiger Kolchinsky et al.) [211 |Strouse and Schwab| 2019 Pensia al. |0200 Assodeh and Calmon Ngamprueti korn korn and Schwab) [2021] Yu et al., 2021; Ngampruetikorn and Schwab] [2022]
2019
2020
Gündüz et al. 2022; Razeghi et al. 2022; Ngampruetikorn and Schwab), 2023). An IB framework
for self-supervised learning was recently discussed in (Ngampruetikorn et al. 2020).
Multitask learning and learning-to-ccarn In the problem of multitask learning and learning-to
leamn (Baxter 2000 Argyriou al. 2006; Maurer al., 2016; Du et al., [020] Tripuraneni et al.) 2020 2021), the goal of the learner is to jointly learn multiple downstream prediction tasks. The underlying implicit assumption is that the tasks are similar in some way, specifically, that they share common low dimensional representation. In the notation of this paper, a class F = f2. ... Jt) of f prediction task is given, and a predictor from R: E + y is decomposed as (R(z)). where the representation = = R(x) E I' is common to all tasks. The learner is given a dataset for each of the tasks, and its goal is to learn the common representation, as well as the individual predictors in the multitask setting. In the learning- corninggto-leanyy to-leam setting, the learner will be presented with new
prediction tasks, and so only the representation is retained.
Maurer et al. (2016) assumed that the representation is chosen from a class R and the predictors from a class 2 (in our notation), and generalization bounds on the average excess risk for an empirical risk minimization (ERM) learning algorithm were derived, highlighting the different complexity mea- sures associated with the problem. In the context of sauming-to-learn, the bound in (Maurer et al.) 2016 Theorem 2) scales as O(1/VF) + 0(1/ /m). where m is the number of samples provided to the learner from the new task. In practice, it is often the case that leaming-to-learn is efficient even for small 4, which implies that this bound is loose. It was then improved by /Tripuraneni et al.) (2020). whose main statement is that a proper notion of task diversity is crucial for generalization. They then proposed an explicit notion of task diversity, controlled by a term v and obtained a bound of the form Ö C(R)+O(() nd
C(Q) m
(in our notation), where C(R) and C(2) are com-
plexity measures for the representation class and the prediction class, For comparison, in this paper we focus on finding the optimal representation, either theoretically (in the fundamental linear MSE setting) or algorithnically. rather than relying on generic ERM. To this end we side-step the gen- eralization error, and so the regret we define can be thought of as an approximation error. One direct consequence of this difference is that in our case task diversity (rich F) leads to large regret, whereas in (Tripuraneni et al., 2020) task diversity leads to low generalization bound. From this aspect, our results complement those of Tripuraneni al. (2020) to the non-realizable case (that is, when the prediction tasks cannot be decomposed as a composition f(x) = (R(())).
Randomization in representation learning Randomization is classically used in data represen- tation, most notably, utilizing the seminal Dohnson-LLndensteen generally, sketching algorithms (c.g., (Vempala) 2005 Mahoney et al., 2011 Woodruff et 2014 Yang et al. 2202)). Our use of randomization is different and is inspired by the classical Nash equi- librium (Nash Jr 1950). Rather than using single deterministic representation that was randomly chosen, we consider randomizing multiple representation rules, Such randomization is commonly used in the face of future uncertainty, which in our setting is the downstream prediction task.
Lemma Johnson| (1984) or more
Game-theoretic formulations in statistics and machine-learning The use of game-theoretic for- mulations in statistics, between a player choosing a prediction algorithm and an adversary choosing prediction problem (typically Nature), was established by Wald (1939) in his classical statistical decision theory (see, e.g., [Wasserman, 2004| Chapter 12)). It is a common approach both in classic statisties and learning theory (Yang and Barron 1999 Grünwald and Dawid 2004 Haussler and Opper 1997; Farnia and Tse, (016)) as well as in modern high-dimensional statistics (Wainwright) 2019). The effect of the representation (quantizer) on the consistency of learning algorithms when
17

---

Published as a conference paper at ICLR 2024
surrogate convex loss function replaces the loss function of interest studied in (guuyen al.) |009| Duchi et al., 2018; Grünwald and Dawid 2004) (for binary and multiclass classification, re- spectively). A relation between information loss and minimal error probability was recently derived by Silva and Tobar 2022).
Iterative algorithms for the solution of minimax games have drawn much attention in the last few years due to their importance in optimizing generative adversarial networks (GANs) (Goodfellow al. 2020 Creswell al. 2018), adversarial training (Madry al. (017), and robust optimization (Ben- Tal et al. 2009). The notion of convergence is rather delicate, even for the basic convex- concave two-r setting (Salimans et al., 2016). While the value output by the MWU algorithm (Freund and Schapire 1999). or improved versions (Daskalakis et al.) 2011 Rakhlin and Sricharan,
2013) converges a no-regret solution, the actual strategies used by the players are, in fact, repelled away from the equilibrium point to the boundary of the probability simplex (Bailey and Piliouras, 2018). For general games, the gradient descent ascent (GDA) natural and practical choice, yet despite recent advances, its theory is still partial (Zhang et al. 2022). Various other algorithms have
been proposed, e.g., (Schäfer and Anandkumar
2019 Mescheder et al. 2017: Letcher et al. 2019
Gidel et al. 2019 Zhang and Wang 2021).
Incremental learning of mixture models Our proposed Algorithm I operates iteratively, and each main iteration adds a representation rule as new component to the existing mixture of rep- resentation rules. More broadly, the efficiency of algorithms that follow this idea is based on two principles: (i) A powerful model can be obtained from mixture of few weak models; (ii) Mix- ture models can be efficiently learned by a gradual addition of components to the mixture, the new component aims to address the most challenging problem instance. As a classic example, this idea is instantiated by the boosting method (Schapire and Freund, 2012) for classification, and was adapted for generative models by Tolstikhin et al. (2017) for GANs. In boosting, the final classifier is a mixture of simpler classifiers. Large weights are put on data points which are wrongly classified with the current mixture of classifiers, and the new component (classifier) is trained to cope with these samples. In GANs, the generated distribution is a mixture is of generative models. Large weights are put on examples which are easily discerned by the discriminator of the true and gen- crated distributions, and the new component (generative distribution) optimizes the GAN objective on this weighted data. In our setting, the final representation a mixture of representation rules. Weights are put on adversarial functions that cannot be accurately predicted with the current repre- sentation matrices. The new representation component aims to allow for accurate prediction of these functions. Overall, the common intuitive idea is very natural: The learning algorithm sees what is most lacking in the current mixture, and adds a new component that directly aims to minimize this shortage. We refer the reader to (Tolstikhin et al. 2017) for more in-depth exposition of this idea. As mentioned by Tolstikhin et al. (2017), this idea dates back to the use of boosting for density estimation (Welling et al. 2202)..
Unsupervised pretraining From a broader perspective, our method is essentially an unsupervised pretraining method, similar to the methods which currently enable the recent success in natural language processing. Our model is much simplified compared transformer architecture (Vaswani et al., 2017), but the unsupervised training aspect used for prediction tasks (Devlin et al. 2018) is common, and our results may shed light on these methods. For example, putting more weight on some words compared to others during training phase that uses the masked-token prediction objective.
B CLASSES OF RESPONSE FUNCTIONS
Our approach to optimal representation is based on the assumption that a class F of downstream prediction tasks is known. This assumption may represent prior knowledge or constraints on the response function, and can stem from various considerations. To begin, it might be hypothesized that some features are less relevant than others. As a simple intuitive example, the outer pixels in images are typically less relevant to the classification of photographed objects, regardless of their variability (which may stem from other effects, such lighting conditions). Similarly, non-coding regions of the genotype are irrelevant for predicting phenotype. The prior knowledge may encode softer variations in relevance. Moreover, such prior assumption may be imposed on the learned
18

---

Published as a conference paper at ICLR 2024
function, e.g., it may be assumed that the response function respects the privacy of some features, or only weakly depends on features which provide an unfair advantage. In domain adaptation (Mansour et al. 2009), one may solve the prediction problem for feature distribution Pa obtaining optimal response function f1- Then, after a change of input distribution to Qz, the response function learned for this feature distribution
may be assumed to belong functions which are "compatible" with fi. For example, if P& and Qz are supported on different subsets of IR the learned response function (z) and f2(x) may be assumed to satisfy some type of continuity assumptions. Similar assumptions may hold for the more general setting of transfer learning (Ben-Davin et al. 2010).
Furthermore, such assumptions may hold in a continual learning setting (Zenke et al. [011] 7 Nguyen
et al. 2017. Van de Ven and Tolias 2019 Aljundi et al.] (019), in which a sequence of response functions is learned one task at a time. Assuming that catastruphic forgetting forgetttinn
is aimed to be avoided,
then starting from the second task, the choice of representation may assume that the learned response function is accurate for all previously learned tasks.
C NOTATION CONVENTIONS
For integer d, [d] == 2 d]. For p 2 1, |||||;:= 1< is the l,p norm of I E Rd. The Frobenius norm of the matrix A is denoted by ||A||== VTr(AT A The non- negative (resp. positive) definite cone of symmetric matrices is given by 8 (resp. $4+). For a given positive-definit matrix S E S the Mahalanobis norm of x E Rd is given by | |S-1//x||2= (x (x S-1x///2/ where .11/2 is the symmetric square root of S. The matrix W == (w....., wr] E R.dxr is comprised from the column vectors (w; kejre C Rd. For real symmetric matrix S E 8d, A5) is the ith largest eigenvalue, so that (S) = A (S) 2 A2( 2 Aa(S) = Amin (S), and in accordance, (s(S) denote an eigenvector corresponding to As(S) (these are unique if there are no two equal eigenvalues, and otherwise arbitrarily chosen, while satisfying orthogonality u.- By
v)) dey). Similarly, A(S) == diag(A (S). (s)) ....,,,..... As(S) and V(S)= :- (UI, 02 (S), (a),""),a((S)) (S)]. so that S ((S)A(S)V (S) is an eigenvalue decomposition. For 2 Vej = [Ui,.... Uj] E R(--++)xd is the matrix comprised of the columns indexed by {i, (1. The vector e Rd is the ith standard basis vector, that is, eq 10....0. 0, O,...
terms d-i terms Random quantities (scalars, vectors, matrices, etc.) are denoted by boldface letters. For example, E Rd is random vector that takes values E IRd and R E Rdxr is random matrix. The probability law of random element x is denoted by L(x:.. The probability of the event in some given probability space is denoted by P[[]] (typically understood from context). The expectation operator is denoted by [E].]. The indicator function is denoted by [[+,, and the Kronecker delta is denoted by 6, := ii = 5}. We do not make distinction between minimum and infimum (or maximum and supremum) as arbitrarily accurate approximation is sufficient for the description of the results in this paper. The binary KI. divergence between P2 (0, 1) is denoted as
(pI ll P2) = pı log
Pl + (1 p1) log p2
1 - p1
(27)
P2
D USEFUL MATHEMATICAL RESULTS
In this section we provide several simplified versions of mathematical results that are used in the proofs. The following well-known result is about the optimal low-rank approximation of a given matrix:
Theorem 10 (Eckart-Young-Mine Young-Mirsky (Wainwright 2019 Example 8.1) 4.1.4)). For symmetric matrix S E Sa
(Vershynin 2018
Section
||S 5Spp
min 3'e8ttrak(S""
||S S'1lF
(28)
where
S2
Σ (.(S) o4 (S) (S) (E(K]
(29)
(more generally, this is true for any unitarily invariant norm).
19

---

Published as a conference paper at ICLR 2024
We next review simplified version of variational characterizations of eigenvalues of symmetric matrices:
Theorem 11 (Rayleigh quotient (Horn and Johnson 2012 Theorem 4.2.2)). For symmetric matrix
e S
T
Sx
( max z#0 |
(30)
Theorem 12 (Courant- Fisher variational characterization (Horn and Johnson, 4.2.6)). For symmetric matrix E 84, k E [d], and subspace T of li
2012
Theorem
x: SS
x Sa
(k)
min T-kim(T)=k 2TT 1
max
T:dim (T k+1 ZET
max
min 2012
|
(31)
Theorem 13 (Fan's 's variational characterization (Horn and Johnson a symmetric matrix E Sd and l E [d]
Corollary 4.3.39.)) For
A1(5) + Ax(S))= UEROXE
min
Tr SU]
(32)
U==
and
) Aa(S)
max
TrU TUT.
(33)
We will use the following celebrated result from convex analysis.
Theorem (Carathéodory's theorem (Bertsekas et 2003 Prop. 1.3.1)). Let A Rd be non-
empty. Then, any point in the convex hull of A can be written as convex combination of at most + points from
E
THE LINEAR MSE SETTING: ADDITIONS AND PROOFS
E. THE STANDARD PRINCIPAL COMPONENT SETTING
In order to highlight the formulation proposed in this paper, we show, starting point, that the well known PCA solution of representing æ E IRd with the top r eigenvectors of covariance matrix of x can be obtained F= } and so y = x with probability In addition, the predictor class Q is a linear function from the representation dimension back to the features dimension d.
specific case of the regret formulation. In this setting, we take
Proposition 15. Consider the linear MSE setting, with the difference that the response is Rd the loss function is the squared Euclidean norm loss( yı, y2) lly1 - y2ll and the predictor with probability 1. Then,
Q(=) Q z E RR. for Q Rexd Assume F = [Ta} so that
regret pure (F Ex)) regret (F Ex) = Σ x((2.))
(34)
1=++1
and an optimal representation is R = V1.r (Ex)).
The result of Proposition 15 verifies that the minimax and maximin formulations indeed generalize the standard PCA formulation. The proof is standard and follows from the Eckart- Eckart-Young Coung-Mirsky theorem, which determines the best rank r approximation the Frobenius norm.
Proof of Proposition 15
Since F (Ia} is singleton, there is no distinction between pure and mixed minimax regret. It holds that
regret(R: Rt f) = E || QT x x
(35)
where A = TTR R E Rdxd is a rank matrix. For any A E Rddd
[|| - Ax [2]
[ T - x Ax - x A x + T A Ax]
(36)
= Tr Ex -Li,
AT + A ATA
(37)
|| E1/2 2
(38)
F
20

---

Published as a conference paper at ICLR 2024
-112 B
(39)
where B == >//² A. By the classic Eckart- Eckart-Young-Mil Young-Mirsky theorem (Wainwright 2019 Example 8.1)
/eershynin 2018 Section 4.1.4) (see Appendix D). the best rank r approximation the Frobenius norm is obtained by setting
B X( 1.
000 = Σ Vie(Zn)) U22y
(40)
1=1
where 8j (;(( U/ (xn) is the ith eigenvector of Ene (or Ex)) Then, the optimal A is
A'
v (Ex) Eg 1/11/21110 u
(r Eg 1/2
(41)
= since v1 is also an eigenvector of Σx 1/2 Letting = ((R)E(A)VT(B) and Q U(Q) (Q) be the singular value decomposition of R and Q, respectively, it holds that
RT = V(Q) (Q) (R)UT(B)
(42)
Setting V(Q)= V(R) I, and (Q) E(R) E Rdxr to have r ones on the diagonal (and all other entries are zero), as well as (Q) = (R) to be an orthogonal matrix whose first r columns are (e)r) results that Q R_T = A", as required.
E.2 PROOFS OF PURE AND MIXED MINIMAX REPRESENTATIONS
Before the proof of Theorem 2 we state a simple and useful lemma, which provides the pointwise value of the regret and the optimal linear predictor for given representation and response. Lemma 16. Consider the representation 2 = R x E TR. It then holds that
regret(R, R, Pa) = min TE ( x + - q =)
(43)
qER"
E
E n mI] + J (En E. R) ER
(44)
Proof. The orthogonality principle states that
E [(f must hold for the optimal linear estimator. Using = RRT x and taking expectations leads to the ordinary leaat-s (OLS) solution
q 2) =0
(45)
(t.s (
S22 -
(46)
assuming that R R. is invertible (which indeed assume as if this is not the case, the represen- tation can be reduced to a dimension lower than r in a lossless manner). The resulting regret of is thus given by
regret(RA R, Px)
( x + n ====²
(47)
(0)
E (f x + +n) (f x + n- - T222)
(48)
E [ x
2 - -s x
n) S
(49)
[B|n
x1 + TTaff E |o RR
(50)
E
Φ]] + Exf - Tr [ Miel
(51)
E
B|n
+ f Σxf - 9 R Enf
(52)
E
Ein
x|] + T (Eg Eg R(R E.R)
(53)
where (a) follows from the orthogonality principle in 45 (b) follows from the tower property of conditional expectation and since E[an] from (46).
= Exx E
x = 0, and (c) follows by substituting 4ts
21

---

Published as a conference paper at ICLR 2024
We may now prove Theorem 2
Proof of Theorem of
2 For any given f, the optimal predictor based on E R achieves average loss
[ + -9- ==x)² = E [B|n² [=]
regret R = Ta. fl Pa)) = min E
(54)
vER"
(obtained by setting f = La in Lemma 16 so that =x). Hence, the resulting regret of R over an adversarial choice of f E Fs is
max regret (,, f) max E ||5 x + --==
E|inn a]]
feAs
fef
(a)
max SEFs
l EE Rq RTT Ex) ,
(55)
(51/22 - Rg Ex R ER
f
max fA1i1S
(56)
21/2 S1/2 -//2 H 2 12-- R² 21 S1/2)
(57)
A
11/251//
[a -1- 11//2 R Σ R) - R 1 ///2/1/22
(58)
( A
51/2211/
[1 R(R R) - /1/2/1/2
(59)
A (l4 R(R R) - R Eu
SEL
La ReR R2) R2)-
(60)
where (a) follows from Lemma 16 (b) follows by letting f= == S- and recalling that any
f F must satisfy 2 1, (c) follows from the Rayleigh quotient theorem (Horn and Johnson
2012 Theorem 4.2.2) (see Appendix D). (d) follows by letting Rt = Σ R. and (e) follows since Ia R(R it)- is an orthogonal projection (idempotent and symmetric matrix) of rank d
Now, to find the minimizer of max regret J) over R. we note that
A1 Laa - R(R R /
(Ia- R(R R) RR
(
max T (Io- R(R R. R EE (Ia- R R) u
(61)
w:||u||a=1
(b)
max
u T T /2 1/2 sI
(62)
w:||a||2=1, R u=0
u TI /
min S:dim(S)=d
max =11 wES
(63)
Ar+1 Σ1 11/2
(64)
where (a) follows again from the Rayleigh quotient theorem (Horn and Johnson 2012 Theorem 4.2.2), (b) follows since Ia R(R R) RT is an orthogonal projection matrix, and so we may write u = u + Uj so that [|u: |12+||u]122 1 and Āt u = O; Hence replacing u with w only increases the value of the maximum, (c) follows by setting S to be a r dimensional subspace of IRd, and (d) follows by the Courant-Fischer variational characterization (Homn and Johnson 2012 Theorem 4.2.6) (see Appendix D). The lower bound in (c) can be achieved by setting the columns of R E TR to be the top eigenvectors (v: Sx )e(r))
) This leads to the minimax representation R. From 660) the worst case f is the top eigenvector of
Ta- - (()( Rt) (ft))") >1 2//2551/2
(Ta î. (()))))-)))(0))))
(65)
This is a symmetric matrix, whose top eigenvector is the (r + 1)th eigenvector 2T-1 (EV 1/2 SEL/2
22

---

Published as a conference paper at ICLR 2024
We next prove Theorem 3
Proof of T'Thorem 3 We follow the proof strategy mentioned after the statement of the theorem.
We assume that n 0 with probability 1, since, as for the pure minimax regret, this unavoidable additive term of E E = to the loss does not affect the regret.
The minimax problem direct computation: As in the derivations leading to 600) the minimax regret in 2 is given by
regret mix (Fs mn)
min max E [regret(RR] f [x)] L(R)EP(R) fETs
(66)
min max E FT (5L/2 - ( Rg 1aRR--1p 'R' E f
(67)
((R) f. F
min max
fT E La R(R R)
R
S112f
(68)
1 (R))P((R) f-11f1351
min A1 (51/221/2 Ia R(R R)
R R
m g2/2)
(69)
L(E ())E(()
where R E1 R. Determining the optimal distribution of the representation directly from this expression seems to be intractable. We thus next solve the maximin problem, and then return to the maximin problem (69). set specific random representation, and show that it achieves the maximin value. This, in turn, establishes the optimality of this choice.
The maximin problem: Let arbitrary L(f) be given. Then, taking the expectation of the regret over the random choice of f. for any given It E R,
(a)
20 51/2 En R)-- R Σn 51/2) 88 "]]
E [regret(B, Rt f)
Tr
(70)
Tr [S S S Eg R(R Ry
R Σg 11/2) Eg]
(71)
Tr $1//2 _ s1/2 - 5// _ R
R S1/51/ $51/21
(72)
Th
| ///5111111 /2 Iaa R
R
Σ 2
(73)
[11 R it) -1 Ri Σ! 1/2 /1/25//3 /
Tr
(74)
(4) Tr [1- R(R R) R
R(R
R)
RR
(75)
Tr W /
min WeR -e w=
(76)
Σ /
(77)
= Σ A
(78)
1=++1
where (a) follows from Lemma 16 and setting j = S-1/2 (b) follows by setting 5, = E
E J. (c) follows by setting R = 1-2 R. (d) follows since I - R(R - Rt is an orthogo- nal projection (idempotent and symmetric matrix) of rank d - r, (e) follows since any orthogonal projection can be written as WWT where W (d-rr is orthogonal matrix W W Id-rs
(ff) follows from Fan's 's variational characterization (an [949)Honm and Johnson 2012 Corollary
4.3.39.) (see Appendix D). Equality in (e) can be achieved by letting R be the top r eigenvectors of
1/ 51/25) 33//55 1/2
23

---

Published as a conference paper at ICLR 2024
The next step of the derivation is to maximize the expected regret the probability law of f (or f). Evidently, [[regret([R, f)] Limr+1 5 only depends on the random function f via Σy. The covariance matrix Σn is constrained as follows. Recall that f is supported be its covariance matrix. Then, it
on Fs {ʃ E IR: || - 1} (see (4), and let 2ig H[ f |
must hold that Tr(S-1Egt S 1. Then, it also holds that
1 2 Tr = Tr
E[S- ff f f
(79)
E
(80)
E f f
(81)
Tr {
(82)
where E = 5-1/22 Conversely, given any covariance matrix Eg E 84 such that Tr[E,] S there exists random vector f supported on Fs such that
E[ff 5'
(83)
We show this by an explicit construction. Let Egg V be the eigenvalue decomposition of Σy, and, for brevity, denote by \Ι >xEE)) the diagonal elements of Åy. Let {q:hie be set of independent and identically (IID) distributed random variables, so that q, is Rademacher, that is Plq. Plq. -1] 1/2. Define the random vector
= (9 (ai. (ai.Vi, . Ad Vda
(84)
The constraint Tr[Ey] implies that Σ < 1 and | Ei= Ā with probability 1. Then, letting f = Vig also holds that | = ول with probability 1, and furthermore,
E ff [
- gg VJ = Vy = Eg
(85)
Consequently, letting f S1/2 assures that || || | 1 and E[S S as was required to obtain. Therefore, instead of maximizing over probability laws on P(Fs), we may equivalently maximize over E E $ such that Tr(ī,] S i.e. to solve
regret (Fs En)
max Ty
Σ X /
(86)
The optimization problem in 86 is solved in Lemma 17 and is provided after this proof. Setting = ,1/ S1/2 in Lemma 17 and letting A; = , S1/2), the solution is given by
--
(87)
Σ
where et E [d]]r] satisfies
8 --
-
(88)
A+++1
i=1
Lemma 17 also directly implies that optimal Σ y is given as in 10 The value in (8 is exactly regret (Fs Σx) claimed by the theorem, and we next show it is indeed achievable by a properly
constructed random representation.
The minimax problem- - a solution via the maximin certificate: Given the value of the regret game in mixed strategies found in (87p. may also find minimax representation in mixed strategies. To this end, we return to the minimax expression in (69). and propose a random representation which achieves the maximin value in (87). Note that for any given R, the matrix Ia- - R( R) R. an orthogonal projection, that is, symmetric matrix whose eigenvalues all either 0 or and it has
24

---

Published as a conference paper at ICLR 2024
most r eigenvaluus equal to zero. We denote its eigenvalue decomposition by La- R(R ( R) UNUT. Then, any probability law on R induces probability law on U and 52 (and vice-versa). To find the mixed minimax representation, we propose setting U (EE//EE probability 1, that is, to be deterministie,, and thus only randomize Ω. With this choice, and by denoting, for brevity, A A(E2/² SEL A(S S1/2), the value of the objective function in (69) is given by
= V with
\
///2>1// /2V [2 ..
V 21/2/1112
A [ V -
(89)
[2] A). A (E
(90)
Now, the distribution of Ω is equivalent to a distribution on its diagonal, which is supported on the finite set A := {a E 10 ||lll d - r}. Our goal is thus to find a probability law on a, supported on A, which solves
min max A1 (E [ A) = min max E[a.]>r L(a) TE[d]
(91)
((0)) iE|d]
where X; /2 are the diagonal elements of A. Consider E", the optimal dimension of the maximin problem, which satisfies (88). We then set ag++1 = ... a, = to hold with probability 1, and so it remains determine the probability law of on A = {a E {0, 132" ||a|1/2 -r}. Clearly, reducing ||a/]] only reduces the objective function
(a1.-. ..... ag-). supported
max A.]. and so we may fact assume that ā is supported on A := { {0, 13" ||ā||== 1
e r.. a finite subset of cardinality (,)). Suppose that we find probability law L(a) supported
on A such that
1/A bi:
E[a.] (e" r).
(92)
Σ i= 1/A:
for all i E [e*]. Then, since E[a,] 1 for i [d][[**]
max Bla;}>; max <E|d!
Ae ... dd
(93)
2i=1 X
8
max
(94)
Ei=1 A
(95)
where (+) follows from the condition on E" in the right inequality of (88). This proves that such probability law achieves the minimax regret in mixed strategies. This last term is regret Ex) claimed by the theorem. remains to construct L(a) which satisfies (92.. To this end, note that the set
C : {c 1j" ||c|| = C" -r]
(66)
is convex and compact, and A is the set of its extreme points (C is the convex hull of A). Letting b= (by....,bu) be. T as denoted in (92). it holds that b, > 0 and H" is a non-decreasing sequence. Using the condition on l in the left inequality of (88 then holds that
1/4e-
b S ... ..... by. (6--7)
1.
(97)
Σ 1/A.
Hence, 5 E C. By Carathéodory's 's theorem Bertsekas al. 2003
Prop. 1.3.1) (see Appendix D
any point inside convex compact set in IR. can be written h + extreme points. Thus, there exists {pa)aEA such that Pa E [0, 1] and E Pa = 1 so that
convex combination of at most
1 == T, and moreover the support of Pa has cardinality at most (* Let 7 {0, 13 x
be such that its jth column is given by the jth member of A (in arbitrary order). Let E [0, 1
25

---

Published as a conference paper at ICLR 2024
be vector whose jth element corresponds to the jth member of A. Then, p is the solution to Ap = b, and as claimed above, such a solution with at most 6 + 1 nonzero entries always exists. Setting a = (7. 1...,)) with probability Pa then assures that (92) holds, as was required to be d-E- terms
proved.
Given the above, we observe that setting At as the theorem induces a distribution on Q for which the random entries of its diagonal satisfy (2)) and thus achieve regret (Fs Ex).
We next turn to complete the proof of Theorem by solving the optimization problem in (86) Assume that E 84+ a strictly positive covariance matrix Σ 0, and consider the optimization problem
00-
max Ei EBM
Σ XEEEE))
2m++1
subject to Tr[E,]] 2
(98)
for some r E [d-1]. Note that the objective function refers to the maximization of the d - minimal eigenvalues of E1/2,,E1/2 1//
Lemma 17. Let
0g E X.
(99)
The optimal value of 98 is v"
max(d]Mr) 0g and E E arggma de iff
--
--
<
(100)
Xe- (E)
Xx++(EE)
An optimal solution is
Ae- (Σ) 0, 0.....) .V()))
((E) diag
(101)
(E)
(1)
E1/2 let E, = UGA be its eigenvalue decomposition, and, for brevity, denote X; = {xEE)) Then, the trace operation appearing in the constraint of (98 can be written as
Proof. Let Eg E1/2 E2/2
Trpłyl = Tr Σ 112 1/2
(102)
Tr
Σ
1-1/2 y イイ
(103)
Tr
E-1/2
E-1/2
(104)
(1z. 3 --)))))) Aa
(105)
(106)
where T. = vT) (that is, the ith column of U and c, == J.. ' (which satisfies Ca > 0). Thus, the optimization problem in 98) over En is equivalent to optimization problem over
(Ni, us heeee given by
Σ A
max
i=++1
26

---

Published as a conference paper at ICLR 2024
d
subject to
Σ
CAAi 1
i=1
Cj 0; -'
0. ijj òig
A 2 A 2 Ao
20
(107)
To solve the optimization problem [107. let fix feasible {ūeJield' that (cheld are fixed too. This results the problem
d
((T.)) (1c)) (Aehie i=++1
A
subject to 1=1
s1 1
2 2 Na 20
(108)
The objective function of (108) linear in (Aehe and constraint set is a convex bounded polytope. So the solution to (108) must be obtained on the boundary of the constraint set. Clearly, the optimal value satisfies e,, ((c)) 2 0, and thus the solution (7, he(d must be obtained when the
constraint Σ c24y < 1 is satisfied with equality. Indeed, if this is not the case then one may scale all A₂ by constant larger than 1, and obtain larger value of the objective, while still satisfying the constraint.
To find the optimal solution (108) we consider feasible points for which e : max E [d]:A; >> 0) fixed. Let {> Jeea be the optimal solution of (108). under the additional constraint that A 0. We next prove that X contradiction that there exists j [e] that X > X O. There are two cases consider, to wit, whether - < + 1 and so only Aÿ appears in the objective of (108), or, otherwise, j - 1 12 + 1 and then Āÿ-1 + } appears in the objective of (108). Assuming the first case, let X Xje; and consider the optimization problem
det1
Xe must hold. To this end, assume by
max R A
subject to 2 1 Åÿcş a;
d 2 2₂ >0. 0.
(109)
is easy to verify that the optimum of this problem 23-1 =}; cc- Thus, if X,
then one can replace this pair with x
\द so that the value of the constraint
E Tsc; remains the same, and thus .A. 83 1 X In2 objective function value of (108) is smaller; contradiction. Therefore, it must hold for the first
a feasible point, while the
case that X Xy. For the second case, in a similar fashion, let now X + X Xjcy and consider the optimization problem
max R, + 2q-i A 1.15
subject to 2 11-19--1 + Åoo==a, =a
8 2, >0.
(110)
The solution for this optimization problem one of the two extreme points of the feasible interval for Xy- Since X; >> O was assumed it therefore must hold that رニ = X7. and hence also X; = Xj Thus, \j-1 X leads to contradiction. From the above, we deduce that the optimal solution of 1088 under the additional constraint that X
Xu is
1
X
(111)
Σ
27

---

Published as a conference paper at ICLR 2024
1t11 X 0,
(112)
and that the optimal value value of (108) is
Since l E [d]]pr] can be arbitrarily chosen, we deduce that the
Eiz
" ((c)))
max (rr
(113)
Ei= G
For any given l E [d]rr) we may now optimize over ( which from 113 is equivalent to minimizing Eí C₁ holds that
min fuu i=1
min fa B
12 E
-u:
(114)
i=
min
TT
2
(115)
fara x5=b,
a min DERIXE;UTÜ=L.
Tt
Σ -
(116)
Tr T
min
(117)
DERIXCUTT
Ū=
(b)
Σ
(118)
where in (a) t Bddt whose i columns are {ū, hield and U 1 It. and in (b) have used Fan (7949)ss 's variational characterization (Horn and Johnson 2012 Corollary 4.3.39.) (see Appendix D). Substituting back to (113) results that
max (E(d][r] Ei=1 X.
max a₂- rE(MMp]
(119)
Let us denote that maximizer index by e Then, Fan's characterization is achieved by setting U = V (so that the f columns of Ú are the e eigenvectors (E), corresponding to the t" largest eigenvalues of E), so that
E
V diag
1.,,,,,,,.., VT. (120)
(x)
8" terms
and then
= Σ 1 1/////111"" 1-1/2 1/2
(121)
8"
VA VV- -AA1//2TV diag 1,0, ,..T....00 -0
(122)
V diag
Ae- (2) 0, No.23.00... 0.....0)
VT
(123)
(1)
as claimed in 101).
To complete the proof, remains characterize t" which belongs the set possible indices max- imizing {ar { Since l maximizes at it must be local maximizer, that is, it must hold that those in (100). remains to show that any e E [d].[r which satisfies (100) has the same value, and thus any local maxima is global maxima. We will show this by proving that the sequence {ael unimodal, as follows. Let A 0++1 a, be the discrete derivative of {ar hee(d, and consider the sequence (Achee [r]- We show that as l increases from r to d, {Ac)re(dN() is only changing its sign at most once. To this end, we first note that
ag--1 S ag. +1++1- By simple algebra, these conditions are equivalent
A 1+1-r
l-r
Σ Ac(T)
(l r) Xerr(E)
(124)
81 ΣE
E
Σ i= X
A(
A(E)
28

---

Published as a conference paper at ICLR 2024
Since the denominator of (24) is strictly positive, it suffices prove that the sequence comprised of the numerator of 124), to wit (<c)xe(d[N)) with
8
E = Σ (x(2) (e- de+1 (2)
(125)
only changing its sign at most once. Indeed, this claim is true because Gr Ei=1 X,(2) because {Se)eE(dMM is monotonic non-increasing sequence,
0 and
1
Se - S - (C-r+
20.
(126)
(e+2(E) Ae+1
Therefore, {<e [r) has most single sign change (its has a positive value at é and is monotonically non-increasing with up l d), and so is {Ar) The single sign change property of the finite difference {Ar] is equivalent the fact that ld is unimodal. Thus, any local maximizer of ag is also global maximizer.
F THE HILBERT SPACE MSE SETTING
In this section, we show that the regret expressions in Section 3 can be easily generalized to an infinite dimensional Hilbert space, for responses with noise that is statistically independent of the features. We still assume the MSE loss function () = IR and loss(y1, U2) = (y1 )2))),, and that the predictor is linear function. However, be functions in a Hilbert space. As will be evident, the resulting regret is not very different from the finite-dimensional case. Formally, this is defined as follows:
allow the the representation and response function to
Definition 18 (The Hilbert space MSE setting). Assume that æ Pa is supported on compact
subset C RRd, and L2 (Pz) be the Hilbert space of functions from IR such that E [x)) = Sx (x) dPa < co, with the inner product,
(f.g) = S f(x)g(()) dPx
dP'
(127)
for f.g E L2(Px). Let { be orthonormal basis for L2(Pa).
A representation is comprised of a set of functions (Wi)eE)r) C T.2( (Pa) 1/: X + R, so that
R [R()) (v) (z)) R'}.
(128)
Let {Ai)ee be a positive monotonic non-increasing sequence for which \ 4 0 as j - oc, and let FF be the set of functions from X' - R such that given f' E F, the response is given by
y f(z) +n
(129)
where
2 f E F(a) = f(x) f(x)= = Σ (z); (fShSeN E &2(),, j=1
(130)
where n is homoscedastic noise that is statistically independent of æ and satisfies E[n] 0. Infinite- dinnnt--dmmesioonll ellipsoids such as F(),) naturally arise in reproducing kernel Hilbert spaces (RKHS) (Wainwright 2019, Chapter 12) (Shalev-Shwartz and Ben-David 2014 Chapter 16), in which { is the eigenvalues of the kernel. In this case, the set /(A.) [:: If 1} where ||-1| the norm of the RKHS For example, could be the first-order Sobolev space of functions with finite first derivative energy.
Let the set of predictor functions be the set of linear functions from Rdd + R, that
Q = (Q(x)= - - Σ ge vx(x), E
(131)
We denote the pure (resp. mixed) minimax regret as regret pure (R, F(2,) regret (R, F(x,} Pa)). We begin with pure strategies.
Pa) (resp.
29

---

Published as a conference paper at ICLR 2024
Theorem 19. For the Hilbert space MSE setting (Definition 18
regret (R., F1,, Pa) Ar+1-
(132)
A minimax representation is
(= = (.)
(133)
and the worst response function is f V 9.+1-
We now turn to the minimax representation in mixed strategies. Theorem 20, For the Hilbert space MSE setting (Definition 78
regr (R. Pw) 8- -
(134)
Σ 1
where is defined as 8 of Theorem 3 (with the replacement d + N4). Let (by). be an IID
sequence of Rademacher random vartables, Pbb; 1] Plb, = -1] 1/2. Then, least
favorable prior f
bi 0.
1sise.
(135)
124+1
and a law of minimax representation choose
(²)x) (dz, (x)}
(136)
with probability P5 [(")),, defined as in Theorem
Discussion Despite having countably infinite possible number of representations, the optimal rep- resentation only utilizes finite set of orthogonal functions, as determined by the radius of F(s:). and 20 is obtained by reducing the infinite dimensional problem to a d-
The proof of Theorems and dimensional problem via an approximation argument, then showing the the finite dimensional case similar to the problem of Section 3 and then taking limit d 1 20.
F.1 PROOFS
Let us denote the d-dimensional slice of F(a,) by
F 0 for all 2 1
(137)
Further, us consider the restricted representation class, in which the representation functions (t,(t) belong to the span of the first d basis functions, that is
R (d) == (R(x)) R: = (x) span( (orheta) for all i e [r]].
(138)
The following proposition implies that the regret in the difenite-iimensional Hilbert space obtained as the limit of Enite-dimensione regrets, as the one characterized in Section 3
Proposition 21. It holds that
regret pure (R, F. F(2,3 Pa) lim regret
pure (R(d), (((d)
Pa))
(139)
dtoo
and
regretmix (Riimmi(R,,, F(,,) Pa)
lim regret
((),F(())
x(d) (Ay) Pa).
(140)
Proof. Let {cg JeN be the coefficients of the orthogonal expansion of t/,, [r], that is, v. =
Σj= Cypj. With slight abuse of notation, we also let c; == (C11. ...) (N). We use sandwich argument. On one hand,
regret (R, F(,)) Pa) min max regret R, f) RER feF(x,)
(141)
30

---

Published as a conference paper at ICLR 2024
min max regret(R,, f)
(142)
RER feF
(A))
min RER
max regret(
(143)
SET (Ag)
regret
pure
(R (
x(d)
{Ag}
Px);
(144)
where (+) follows from the following reasoning: For any (R E R F(d)
(2/))
2
2 ΣΣ (c))
regret(R,
min DER
Σ (z) +n
E [n
(145)
06
min E qER"
Σ (50 /=1
Σ
4 kCyoy
(146)
j=1 i=1
d
h
min
GiCij
Cif
(147)
GE
1=d+1
where here (a) follows since the noise n is independent of æ, and since, similarly to the finite- dimensional case (Section 3 the prediction loss based on the features x is E(n"), for any given / E F, (b) follows from Parseval's 's identity and the orthonormality of {6h (en),en. So,
min max regret(R.) f) RER fEFld) (Ay)
= min
max (aghelr)es fEF
min 9ER"
PaCij
+
Σ
(148)
j=1
j=d+1
Evidently, since - (,,))² 2 0, an optimal representation may satisfy that cij 0 for all j 2 d + 1. Thus, the optimal representation belongs to (d)).
On the other hand,
rere (R, F(1,) Pa) = min max regret(R, f) RER (Ef(A,)
(149)
< min
max regret(R,, [R,
(150)
REROO fe3()))
min RER
max regret R, f) + Adt1 (EF(d) (Ag)
(151)
pure (d)) Fld) [4y}
regret
Pa) + >d411
(152)
where (+) follows from the following reasoning: For any (R E (()) f F(1)))
2
regret(R, = min E
(z) +n
Σ (c)
Ein²
(153)
qeRr
j=1 i=1
2
min
fJ Σ Reiig
(154)
yER"
j=1
j=d+1
(6)
d
min 9ER"
fj - Σ GiCij
+ Aat1,
(155)
1=1
1=1
31

---

Published as a conference paper at ICLR 2024
where (a) follows similarly to the analysis made in the previous step, and (b) follows since for any f E [(2)) it holds that
f3 S aot1
06 f S
Σ j=d+1
f Aa+1
Σ j=d+1 >3
Ad+1-
(156)
>3
Combining (144) and (152) and using Ad+1 + completes the proof for the pure minimax regret.
The proof for the mixed minimax is analogous and thus is omitted.
We also use the following simple and technical lemma. Lemma 22. For R E R(d) and f F
regret(R, f
ff (Le R ( f.
(157)
where R E B'xd is the matrix of coefficients of the orthogonal expansion of i e [r). so that R(i,j) Cij.
Us = Σj= Cig3 for
Proof. It holds that
27
regret(RR Rt f) = min
Σ (2) +n Σe0
q
Σ
(2)
n
(158)
GER"
i=1
j=1
r
min E
fj Σ giCij
(159)
QER"
min geR"
Sj
CiCij
(160)
i=1
d
min QER"
13 25$
BiCij +
Ci Cigj
(161)
J=1
12=1
min qER"
f 29 Rf + RRR,T. q
(162)
= f - R (RR (RR J,
(163)
where the last equality is obtained by the minimizer q" )
Proof of Theorems 79 and 20 By Proposition] 21 we may first consider the finite dimensional case, and then take the limit d 0o. By Lemma 22 in the d-dimensional case (for both the representation and the response function), the regret is formally as in the linear setting under the MSE of Theorem 2. by setting therein Σn La. and S diag(A),.... Xa) (c.f. Lemma 16). The claim of the
Theorem 19 then follows by taking d t oo and noting that A4+1 1 0. The proof of Theorem 20 is analogous and thus omitted.
G ITERATIVE ALGORITTMS FOR THE PHASE AND PHASE 2 PROBLEMS
In this section, describe our proposed algorithms for solving the Phase and Phase 2 problems of Algorithm [ Those algorithms are general, and only require providing gradients the regret function ( and an initial representation and set of adversarial functions. These are individually determined for each setting. See Appendix H for the way these are determined in Examples 6 and
Note that any f (d)) may he uniquely identified with d-dimensional vector f Rd. With slight abuse of notation we do not distinguish between the two.
32

---

Published as a conference paper at ICLR 2024
G.1 PHASE 1: FINDING A NEW ADVERSARIAL FUNCTION
We propose an algorithm to solve the Phase problem (23) which based on an iterative algorithm. We denote the function's value at the 7th iteration by J(0) The proposed Algorithm 2 operates as follows. At initialization, the function ((1) E F is arbitrarily initialized (say at random), and then the optimal predictor Q is found for each of the & possible representations R(), j E [Ae]. Then, the algorithm iteratively repeats the following steps, starting with 2: (1) Updating the function from 1()-1) [(t) based a gradient step of
Σ pd JE(R]
loss( (U (R (1())))))))
(164)
that is. the weighted loss function of the previous iteration function, which is then followed by projection to the feasible class of functions F, denoted as II)(() (2) Finding the optimal predictor Q(1) for the current function fit) and the given representations {RQ) Je(K), and computing the respective loss for each representation,
σ = E [loss((e)) Q())
(165)
This loop iterates for T iterations, or until convergence.
Algorithm A procedure for finding a new function via the solution of (23
1:
procedure PIASE SOLVER(( R(6), .p)) )E(N), F, 2,d,
2: begin
3: initialize f
b Number of iterations parameters Step size parameter
4: initialize 17/
5: initialize f(1) E
Function initialization, e-g., random
6: for j to k do
7: set Qti) + argmingeg (1))((())())) Q(R((=))) (()))
8: end for
9: for 2 T do
10:
update 112) f(t-1) + EjEn (
P(-1) V (1-s(((-)))(x)) (R()))
gradient update of the function
11:
project f()) = II, (f(-11())))
> Projection on the class F
j = to k: do
13:
set Q() +- argmin E. (oo (m), Q(R((())))
Update of predictors
set L - [foss(f())z)) (z)) Q (RG) (z)))] Compute loss of each representation
15:
end for end for
17:
return J(T) and the regret Eee(y p(o). I
18:
end procedure
Design choices and possible variants of the basic algorithm At initialization have chosen simple random initialization for J(1). but it may also be initialized based on some prior knowledge of the adversarial function. For the update of the predictors, the optimal predictor, which can be achieved in practice by running another iterative algorithm such as stochastic gradient descent (SGD) until convergence. If this too computationally expensive, the number of gradient steps may be limited. The update of the function is done via projected SGD with constant step size 7f.. yet it is also possible to modify the step size with the iteration, e-g., the common choice // / Vl at step (Hazan 2016). Accelerated algorithms, e.g., moment-based, may also be deployed.
have specified full computation of
Convergence analysis theoretical analysis of the convergence properties the algorithm ap- pears to be challenging. Evidently, this is minimax game between the response player and player cooperating with the representation player, which optimizes the prediction rule order to mini- mize the loss. This is, however, not concave-convex game. As deseribed in Appendix A| even concave-convex games are not well understood at this point. We thus opt to validate this algorithm numerically.
33

---

Published as a conference paper at ICLR 2024
Running-time complexity analysis Algorithm2 for fixed number of iterations Ty, accepts k representations, and makes kTy updates. Each update is comprised from a gradient step of for the adversarial function (cost C1), and optimization of the predictor (cost C2). So the total computation complexity is k (C1 + C2). The most expensive part is the optimization of the predictor C2. and this can be significantly reduced by running few gradients steps of the predictor instead of full optimization. If we take 9 gradient steps then C2 is replaced by Cig and the total computational cost kg + 1)
G.2 PHASE FINDING A NEW REPRESENTATION
We propose iterative algorithm solve the Phase 2 problem (4 and thus finding a new repre- sentation (((++1), To this end, we first note that the objective function in (24) can be separated into a part that depends on existing representations and a part that depends on the new one, specifically,
Σ
plii) ob5). E l f(2) Q(i (RUI)
ji
JoE +m)
Σ
p(++1) .(12). E [(oss( (x), Q(++ (1(
te +m]
Σ
Σ
pli). obie). ((rd)))
Elkk
joE Emo
Σ
plltt) olib). . (lss((((i)()))) ((ttlab)
(166)
[
where
( = ((a) (x), ((i (a)))))
(167)
and the predictors (Q jej Maliiiiaaeee Ja Em can be optimized independently of the new representa-
tion R(++1), We propose an iterative algorithm for this problem, and denote the new representation at the tth iteration of the algorithm by R((+t) The algorithm's 's input is set of mo + k adver-
sarial functions {f() [i][mo+k)- and the current set of representations { }5E(K)- Based on these, the algorithm may find the optimal predictor for f(ia) based on the representation R(1)), and thus compute the loss
(. = min E. ( QEQ
Q(R())
(168)
for ji E [k)] and j2 E [mo + k). In addition, the new representation is arbitrarily initialized (say, at random) as R (K++1) and the predictors [0/btt 1 are initialized as the optimal predictors for f(az given the representation R(A)") The algorithm keeps track of weights for the represen- tations (including the new one), which are initialized uniformly, i.c., p()) सो for ji E [k + I] (including a weight for the new representation). The algorithm also keeps track of weights for the (Ja)
for j2 E [mg + k). Then, the m algorithm iteratively repeats the following steps, starting with t = 2: (1) Updating the new represen-
functions, which also initialized uniformly (1)
tation from R.(+1) to (t)
((K+1) based on a gradient step of the objective function (44 as a function of
(t-1)
R(++1), Based on the decomposition in (166) the term of the objective which depends on (((+1) is
(k+1) P(t-1)
Σ
(jz)
E foss(plizs (x)) Q(++1 (1((++()))))
(169)
+2E[mo++]]
that is, the loss function of the previous iteration new representation, weighted according to the current function weights ((2)) Since the multiplicative factor P(t-1)
(k+1) is common to all terms, is removed from the gradient computation (this aids in the choice of the gradient step). This gradient step is then possibly followed by normalization or projection, which we denote by the operator TT(-). For example, in the linear case, it make sense to normalize ((++1) have unity norm (in
34

---

Published as a conference paper at ICLR 2024
some matrix norm of choice). After updating the new representation (1++1) optimal predictors are found for each function, the loss is computed
I (6)
(k+1) min E [oss( Q(R(()
(170)
QEQ
for all ja [mg + ki,, and the optimal predictor is updated (Q()) (1)++ [2 based on this
solution. (2) Given the current new representation R( the loss matrix
(L()) (1 ((e()))22emmo)
(171)
is constructed where for ji E [k] it holds that (1.J22) 1( for all t (i.e., the loss of previous ((t)
representations and functions is kept fixed). This is considered to be the loss matrix of two-player zero-sum game between the representation player and the function player, where the representation player has k + possible strategies and the function player has mo
strategies. The weights (P()) Ui1 [h and {0()) [io[mm++i] are then updated according to the MWU rule. Specifically, for an inverse temperature parameter 3 (or a regularization parameter), the update is given by
(1) Pit-1) BL
( P(t)
(172)
EjE(h) P(t-1) BLL
for the representation weights and, analogously, by
( (1) = (1-1) 8 8--60
U
(173)
EjeN (t-1) 8-L5)
for the function weights (as the function player aims to maximize the loss). This can be consid- ered regularized gradient step on the probability simplex, or more accurately, follow-the- regularized-leader (Hazan 2016). The main reasoning of this algorithm is that at each iteration the weights (g()) (e(k+))))))) and (o(m)))(()))))))) are updated towards the solution of the two-player
zero-sum game with payoff matrix {- U1- J2)) ( (iisemm In turn, based only on the func- tion weights
[mj]-- +kj- the new representation is updated to ((++1), which then changes the pay-off matrix at the next iteration. It is well known that the MWU solved two-player zero-sum
game (Freund and Schapire 1999), in which the representation player can choose the weights and the function player choose the function.
This loop iterates for Tspp iterations, and then the optimal weights are given by the average over the last Tagg iterations (Freund and Schapire 1999), i.e.,
Top
p
1
Σ
P(t)
(i)
(174)
TaNg
T=
T Tog
and
T rpp
00)
Σ
(3)
(175)
Tang
(0)
t=Tasp
Tog+1
In the last TR Toop iterations, only the representation R(*++)) and the predictors are updated. The algorithm then outputs (2(k+11 as the new representation and the weights {p )
Design choices and possible variants of the basic algorithm At initialization, have cho- sen simple random initialization for B (((+))) but may also be initialized based on some prior knowledge of the desired new representation. The initial predictors [Q(k ) (ie((mo+M)) will then
be initialized as the optimal predictors for (k+1) and {f(iz)) jee We have initialized the
35

---

Published as a conference paper at ICLR 2024
Algorithm A procedure for finding a new representation R( via the solution of (24
1: procedure PHASE
(REER(((R))))) {f(h)) jselmo R,F, 2, r,
2: begin
3: initialize Tn. Tsup, Tavg
D Number of iterations parameters Step size parameter Inverse temperature parameter Function initialization, e-g., random
4: initialize 7)
5: initialize 3 E (0,1)
6:
initialize f()) E F
7: initialize P(1) t 0 for j E [k] and P(1)
(g)
(k+1)
A uniform weight initialization for the
representations
8: initialize (12) - mo+k for ju E [k]]
A uniform weight initialization for the functions
(1)
9:
for ji 1 to k do
for j2 to my + do
11:
set Q(i t argmingeo E [loss(((>>(a)) ((R)))))))))))))))
Q(R()(=))))
Optimal predictors for existing representations and input functions set [(1:5)) minqe E [loss( (oos(f(Uz)((2) (x)), Q(i (R()) (x))) The minimal loss
13: end for
end for
15:
for J2 =1 to mg + k do
Arbitrarily, e.g., at random set (0) (+++1,))) + argminges E (foss(f(z)(()) ((R(++)()))) for j2 E [mo + k] Optimal predictors for new representation and input functions end for for t to Ta do update
initialize (((+1)
17:
19:
A gradient update of the new representation
R(++11 R.((+11) (1-1/2) (c-1) + 7n
(22)
na E
loss( (os)(f())(zz) 1(++1 (R((t) (z)))
(R
(c-1)
(t-1)
(176)
21:
(k++1) project (i()) for = 1 do
II (R
(t-1/2)
b Standardization based the class R
22:
set Q(+++.52) +- argmingee E ((x)(() (K+1)
(((((((())))
23:
Update of predictors for the new representation
(k+1,22) + E (oss(()(()) ((), (1(++1))
24:
((())
Compute loss
25:
end for
L (2) ((i for j1 E [k] and ju [mo +
(1)
27:
ift T then
1):866))
28:
( update (()
for j E [k] Σjem (1-11--000 8865
>. A MWU
(2)
(6)
(i--1) 260
29:
update (0) +
o/3) Σ Ejelmo-n) (i- 1-16)
for j E [mo + k]
> A MWU
30:
else = then
31:
update (()) (t) Tave Et Tap
(i)
Σ Tap
(10 for j [k] T ((t)
b Optimal weights by averaging last Tang iterations
update (5) + Tavg -
( for [mg + (t)
b Optimal weights by averaging last Tang iterations
else
34:
update P() + (i)
(i)
P(t-1) for j E [k]
D No update for the last T Tsoo iterations
35:
update (
+ (1)
for [mo k) No update for the last T T stop iterations
(t) (t-1))
36:
end
(k+1) and (i) return ((2)
37:
(n)
38: end for
39:
end procedure
36

---

Published as a conference paper at ICLR 2024
Table 1: Hardware details
CPU
RAM
GPU
Intel i9 13900k 64GB
RTX 3090 Ti
representation and function weights uniformly. A possibly improved initialization for the function weights is to put more mass on the more recent functions, that is, for large values of j2, or to use the minimax strategy of the function player in the two-player zero-sum game with payoff matrix (- " Jiee E Jel (that is, a game which does not include the new representation). As in the Phase 1 algorithm, the gradient update of the new representation can be replaced by more sophisticated algorithm, the computation of the optimal predictors can replaced with (multiple) update steps, and the step size may also be adjusted. For the MWU update, use the proposed scaling proposed by Freund and Schapire (1999)
B
(177)
clum
for some constant It is well known that using the last iteration of MWU algorithm may fail (Bailey and Piliouras 2018), while averaging the weights value of all iterations provides the optimal value of a two-player zero-sum games (Freund and Schapire 1999). For improved accuracy, we compute the average weights over the last Twgg iterations (thus disregarding the initial iterations). We then halt the weights update and let the function and predictor update rum for T Tsup iterations in order to improve the convergence of R(*-1). Finally, the scheduling of the steps may be more complex, c.g., is possible that running multiple gradient steps follows by multiple MWU steps may improve the result.
Running-ting complexity analysis Algorithm is more complicated than Algorithm 2 but the computational complexity analysis is similar. It runs for TR iterations and the total cost is roughly on the order of k gC1 (taking g gradient steps for the predictor optimization: k2 the number of representations, and is controlled by the learner; C2 is determined by the computer, and should be large enough to assure quality results).
H DETAILS FOR THE EXAMPLES OF ALGORITHM I AND ADDITIONAL EXPERIMENTS
As mentioned, the solvers of the Phase 1 and Phase 2 problems of Algorithm Trequire the gradients of the regret (T) as inputs, as well as initial representation and set of adversarial functions. We next provide these details for the examples in Section 4 The code for the experiments was written in Python 3.6 6 and available at this link The optimization of hyperparameters was done using the Optuna library. The hardware used is standard and detailed appear in Table
H.1 DETAILS FOR EXAMPLE 6 THE LINEAR MSE SETTING
In this setting, the expectation over the feature distribution can be carried out analytically, and the regret is given by
regret Ex) (x)) = -E (f 21
(178)
ff Σnf 24 T E
(179)
The regret only depends the feature distribution Pa via Σg. For each run of the algorithm, the variance matrix En was chosen to be diagonal with elements drawn from a log-normal distribution, with parameters (0, 0o), and $ Ta-
Regret gradients
The gradient of the regret w.r.t. the function f is given by
v,B (1T R x) = 2ʃ Σn - 2g R En
(180)
37

---

Published as a conference paper at ICLR 2024
Table 2: Parameters for linear MSE setting example
Parameter
3,
B
1/r
Value
0.94
0.653
0.713
0.944
Parameter
TR
Ty
T
Tsop
Value
100
until convergence
10
80
and the projection on Fs
ITx(f) lifss
Ilfls> 1 ( Ilflls< 1
(181)
However, we may choose to normalize by Ihf even if Ilfllss 1 since in this case the regret is always larger if ff is replaced by l (in other words, the worst case function is obtained on the boundary of Fs). The gradient w.r.. the predictor is given by
V xf'-"""" 2 = 2- E R+ 24
R Eg
(182)
Finally, to derive the gradient w.r.t. R, let denote =- R2........ ... R.! Rdxr where R₁ Rd is the ith column (i E [r]), and = (gi, 42..... qr). Then, R x Lie(d] qilt æ and the loss function is
27
E (5 x: q TR (Tm)) m)²
E
1Tx: Σ
qar T Ri
(183)
iE(d)
= Exf 29 R. E + q R R Eq.
(184)
The gradient of the regret w.r.t. R2 is then given by
Vn E (1 x - q R x) =) = 2B [s] TT x - a1 TR. RTT22 xx) qu
(185)
= -224 ( Em 1 En)
(186)
hence, more succinetly, the gradient w.r.t. R is
V [<= Ef R
(187)
We remark that in the algorithm these gradients are multiplied by weights. We omit this term when- ever the weight is common to all terms order keep the effective step size constant.
Initialization Algorithm requires an initial representation R()) and an initial set of functions {f())sE(mo) In the MSE setting, each function f TRdd is also single column of representation matrix R E Rdxr_ A plausible initialization matrix R{1)_ E pdxr is therefore the worst r functions.
These, in turn, can be found by running Algorithm I obtain m r functions, by setting 1. A proper initialization for this run is simply an all-zero representation R(1) 0 [ The resulting
output is then ( Jeet which can be placed as the columns of R(1) This initialization is then used for Algorithm
The algorithm parameters used for Example are shown in Table The parameters were optimally tuned for do 1.
Algorithm parameters
Additional results The learning curve for rumning Algorithm T for Example shown in Figure which shows the improvement in regret in each iteration, for which an additional matrix is added the set of representations. It can be seen that mixing roughly 10 matrices suffice get close the
38

---

Published as a conference paper at ICLR 2024
35
30
2.5
2.0
1.5
1.0
#iteration
Figure The learning curve for Algorithm D in the linear MSE setting: d 20, 33
AcuuRic 9200
4.5
10
20
40
50
55
Figure 5: The ratio between the regret achieved by Algorithm [ and the theoretical regret in the linear MSE setting. Left: 20, a = 1, varying r. Right: r = 5, d = 20, varying do-
minimal regret attained by the algorithm, compared to the potential number of (+) (20) 1140 representation matrices determined by A.
Additional results of the accuracy of the Algorithm in the linear MSE setting are displayed in Figure 5 The left panel of Figure shows that the algorithm output is accurate for small values of r. but deteriorates as r increases. This is because when r increases then so is E" and so is the required number of matrices in the support of the representation rule (denoted by ma). Since the algorithm gradually adds representation matrices to the support, an inaccurate convergence at an early iteration significantly affects later iterations. One possible way to remedy this to run each iteration multiple times. and choose the best one, before moving on to the next one. Another reason that given large number of matrices in the support (large m), it becomes increasingly difficult for the the MWU to accurately converge. Since the iterations of the MWU do not converge to the equilibrium point, but rather their average (see discussion in Appendix A) this can only be remedied by allowing more iterations for convergence (in advance) for large values of m. The right panel of Figure 5 shows that the algorithm output is accurate for wide range of the condition number of the covariance matrix. This condition number is determined by the choice of do. where low values typically result covariance matrices with condition number that is close to 1, while high values will typically result large condition number. The right panel shows that while the hyperparameters tuned for dn 1, the result is fairly accurate for a wide range of on values, up to ap Ry 5. Since for Z (N, 1) (standard normal) it holds that IP[ Z 2] 95%, the typical condition number of a covariance matrix drawn with do 5 is roughly range.
d 200
4.85 10a, which a fairly large
201
39

---

Published as a conference paper at ICLR 2024
H.2
DETAILS FOR EXAMPLE
8 THE LINEAR CROSS-ENTROPY SETTING
In this setting,
regret(R,, Pw) | min E DKL ([1 + exp(-f x)1 exp(-q x)] ")) (188) PER"
and the expectation over the feature distribution typically cannot be carried out analytically. We thus tested Algorithm I on empirical distributions of samples drawn from a high-dimensional normal 1000 feature vectors were drawn from an isotropic
distribution. Specifically, for each run, normal distribution of dimension d 15. The expectations of the regret and the corresponding gradients were then computed with respect to (w.r.t)) the resulting empirical distributions.
Regret gradients
We use the facts that
DKL P2) = log Pi P2)
(189)
0p1
p2(1 P1)
and
0 DKI l1
- P1
(190)
0p2
p2(1 p2)
For brevity, let next denote
P1 + exp( (x
(191)
and
1
P2 1 + expl - R x))
(192)
We next repeatedly use the chain rule for differentiation. First,
1
exp(- [T)) x))
VIP = V
P1 ([) P1).
(193)
1
[1 + [xpe exp(pppp0 fapp--faar xx))
and
expl R x) R
vgp2 V,
R x) = P2(1 P2) RTx x.- (194)
+ exp( qq R
[1+ expe
So, assuming that Ps is such that the order of differentiation and expectation may be interchanged (this can be guaranteed using dominated/monotone convergence theorems), the gradient of the regret w.r.t. f is
V rregret( f Pa) E
DKI || p2) x V sp
(195)
Opi
(PI(1 - (12))
E
log
P1 - P1)
(196)
p2(1 p1)
exp(-ft TTx)
E
(fT --- R.T. )æ
x
(197)
[1 exp(p =T)]
exp( (op--fTen TT)
E
x T (f - Rq)æ
(198)
[xpe (x x)}² [=)²
Next, under similar assumptions, the gradient of the regret w.r.t the predictor is
a Opz
V regret((R, P&)
E
DKL (p1 ll p2) V V9p2
(199)
1
TF
R
(200)
11 (ppp--9-- TTRRR
1 cxp( (ap(-ff- ff xx)
40

---

Published as a conference paper at ICLR 2024
Table 3: Parameters for linear cross entropy setting example
Parameter
Bg
Value 0.9
0.9
10-3
10-1
Parameter
Tn
T3
Tavg
T Tsoo
Value
100
1000
25
50
Finally, as for the MSE case, to derive the gradient w.r.t R. we denote R = [RI, R2...., Rr. E
Raxr where R; E Ied is the ith column (i [r]), and q (q), :2.92.-.0 .2. :r)) Then, R
Eiela R.R, x and
P2 1 1 exp(- Evela Re x))
(201)
Then, the gradient of P2 w.r.t. RS is then given by
V VR P2(1 - P2) 9:
(202)
hence, more succinctly, the gradient w.r.t. is
V RD2 p2(1 - -22) xq
(203)
Hence,
Fregret(RR Pa) = E
DKI. 11) x V RR22
(204)
0pp
IE
[P2 p1)
xqq"
(205)
1
1
E [ exp(-y' RTw)
xz
(206)
+ exp(- fTx)
Initialization Here the initialization is similar to the linear MSE setting, except that since column of the representation cannot ideally capture even a single adversarial funetion, the initialization
algorithm only searches for single adversarial function (m = 1). This single function is then used to produce (()) as the initialization of Algorithm
Algorithm parameters The algorithm parameters used for Example g are shown Table 3
H.3 DETAILS FOR EXAMPLE D. AN EXPERIMENT WITH A MULTI-LABEL CLASSIFICATION OF IMAGES AND COMPARISON TO PCA
We next present the setting of Example g which shows that large reduction in the representation dimension can be obtained if the function known belong finite class.
Definition 23 (The multi-label classification setting). Assume that X' V where d 625, and x represents an image. The distribution Pz is such that æ contains shapes selected from dictionary of 6 shapes in different locations, chosen with uniform probability; see Figure The output a binary classification y = {+1} of the image. Assume that the class of representation is linear R(x)= R for some R E R == ddxr where d > The response function belongs to a class of 6 different functions F = [ff1.... ). where f; X' - y indicates whether the ith shape appears in the image not. Assume the cross-entropy loss function, where given that the prediction
that y 1 with probability results the loss loss(y, q) = - (1 + 2) log q 1 (1 - y) log(1 (1- q).
The set of predictor functions is Q (2(2) 1/(1 + exp( -q" =)}, Rr). }. and the regret is then given by the expected binary Kullback- Leibler (KI.) divergence as in Definition 7
Simplifying Algorithm 1 In the the multi-label classification setting of Definition 23 Algorithm Caan be simplified as follows. First, since the number of response functions in the class F is finite, the Phase 1 problem (22) in Algorithm algorithm is simple, since the adversarial function can
41

---

Published as a conference paper at ICLR 2024
stengle:
X
Figure 6: An image in the dataset for the multi-label classification setting (Definition 23
be found by a simple maximization over the functions. Then, the phase step simply finds for each function f(iz) in F, j2 [6]. the best appresentation-prediiee (R Q().))) using gradient descent, where R(i)) X + R" is a linear representation =, and Q is logistic regression. This results is a payoff matrix of R6x6 Then, the resulting game can be numerically solved as a linear program, thus obtaining the probability that each representation should be played. The resulting loss of this minimax rule Rs is the loss of our representation. This representation is then compared with standard PCA representation, which uses the projections on the first principle directions of R = V1.r(22rr as the representation (without randomization). The results of the experiment are shown in Figure B in the paper.
H.4 AN EXPERIMENT WITH A NN ARCHITECTURE
In the analysis and the experiments above we have considered basic linear functions. As mentioned, since the operation of Algorithm[]on onlly depends on the gradients of the loss function, can be easily generalized to representations, response functions and predictors for which such gradients (or sub- gradients) can be provided. In this section, we exemplify this idea with simple NN architecture. For Rd we let the rectifier linear unit (ReLU) be denoted as (z)+-
Definition 24 (The NN setting). Assume the same setting as in Definitions and 7 except that the class of representation, response and predictors are NN with hidden layers of sizes hns ba,hy, hy N4, respectively, instead of linear functions. Specifically: (1) The representation is
R(x) = R.T ( ())x))+))
(207)
for some (Ro, R..... R₂) E R = (RaxhR x TRARKkR RRRxhR x RRax() where d > r. (2) The response is determined by
((x) -o To_ (..((RI((
(208)
where (Fo, Fi...., fe) e F [Rdxhs Rhyxk, ... B x R (3) The predictor is deter- mined by for some
q(2) qe (... (QT (00z))+))
(209)
where (Qn, .i.....q.). E E := [ x x R xhy
Ra, xhy x Rha}.
Regret gradients Gradients were computed using PyTocch with standard gradients computation using backpropagation for an SGD optimizer.
Initialization The initialization algorithm is similar to the initialization algorithm used in the lin- ear cross-entropy setting.
Algorithm parameters
The algorithm parameters used for the example are shown in Table 4
Results For a single hidden layer, Figure 7 shows the reduction of the regret with the iteration for the cross-entropy loss.
42

---

Published as a conference paper at ICLR 2024
Table 4: Parameters for the NN cross-entropy setting.
Parameter
c
ha
hf
hg
Value
1
d
d
d
Parameter
3r
3y
14g
Value
0.9
0.9
10-3
10-1
10
Parameter
T
Ty
TQ
Tavg
T stop
Value
100
1000
100
10
80
0.55
0.02
0.55
32
11
4tcrabinn
Figure 7: The regret achieved by Algorithm in the NN cross-entropy setting as function of the iteration m.
43


Reviews:
[{"review_id": "3iejW4g1ly", "reviewer": "Reviewer_crzZ", "summary": "The paper considers the online prediction problem of predicting features for learning functions. First, the paper focuses on the problem of online linear regression with reduced dimensionality. Then, it considers more general settings, including mixed representations or/and logistic regression. Finally some preliminary experimental results are shown.", "questions": "Is it possible to extend the first result (linear regression) to kernelized classifiers? If not, can you explain why?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem is well-motivated and suited for the conference. The problem formulations are reasonable. Although the first problem might look somewhat elementary, the theoretical results are solid.", "weaknesses": "So far the current results only focus on simple cases where the classifiers are linear. Ideally, some attempts to cope with nonlinear classifiers or nonlinear feature mapping would be appreciated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pnMLCcEVmD", "reviewer": "Reviewer_HEJP", "summary": "The authors propose a new game theoretic framework for learning low-dimensional representations $z= R(x) \\in \\mathbb{R}^r$ of unlabelled data $\\\\{\\vec{x}_i\\\\} \\subset \\mathbb{R}^d$ (where $r \\ll d$) in such a way that the learned representation would be useful for a variety of downstream learning tasks (specified by a class $\\mathcal{F}$ of response functions).\n\nThe contributions are both theoretical (optimal linear representations for linear response etc) and practical/algorithmic (more general representations and response functions). This paper uses a different form of game than the one used by (Dubois et al 2020).\n1. In (Dubois et al 2020), Player 1 chooses the learning task (input distribution, response function) and the score function. Then Player 2 (knowing the above) trains a representation for the input data. Finally, Player 1 evaluates the representation, using the chosen score function on an ERM classifier trained using the representation given by Player 2 (with IID data ~ (input distribution, response function)).\n\n2. In this paper the game is a 2PZS game with: (i) Player 1 (representation player) chooses the representation mapping $R \\in \\mathcal{R}$ (ii) Player 2 chooses the response function $f \\in \\mathcal{F}$, where the data distribution ($P_{\\mathbf{x}}$), loss function ($\\mathsf{loss}$), and the class of prediction rules ($\\mathcal{Q}$) are fixed. The payoff is given by\n$$\\mathsf{Payoff}(R,f) = \\mathsf{Regret}(R, f | P_{\\mathbf{x}}, \\mathsf{loss}, \\mathcal{Q}) = \\min_{Q \\in \\mathcal{Q} \\text{ on } \\mathbb{R}^r} \\mathbb{E}[\\mathsf{loss}(f(\\mathbf{x}),Q(R(\\mathbf{x})) )] - \\min_{Q \\in \\mathcal{Q} \\text{ on } \\mathbb{R}^d} \\mathbb{E}[\\mathsf{loss}(f(\\mathbf{x}),Q(\\mathbf{x}) )]$$\n\nThe game in this paper interchanges the order of the players (in a still useful way) and also abstracts the evaluation of the representation in order to make use of the 2PZS/saddle-point framework.\n\nThey then consider the minimax and maximin regret in terms of mixed strategies, which are equal due to the minimax theorem. The former is given by $$\\min_{\\mathcal{D}^{\\mathrm{rep}} \\in \\text{distributions on } \\mathcal{R}} \\max_{f \\in \\mathcal{F}} \\mathbb{E}_{R \\sim \\mathcal{D}^{\\mathrm{rep}}} \\mathsf{Regret}(R,f)$$ \n\nwhereas the latter is given by\n$$\\max_{\\mathcal{D}^{\\mathrm{fn}} \\in \\text{distributions on } \\mathcal{F}} \\min_{R \\in \\mathcal{R}} \\mathbb{E}_{f \\sim \\mathcal{D}^{\\mathrm{fn}}} \\mathsf{Regret}(R,f)$$ \n\nwith the goal of characterizing the optimal minimax (= maximin) regret as well as the optimal $\\mathcal{D}^{\\mathrm{fn}}$ (parametrized) and as well as the optimal $\\mathcal{D}^{\\mathrm{rep}}$ (parametrized) that lead to the optimal regret. They are able to do this in the linear MSE case. In the general case, they propose an algorithm to find distributions (mixtures) over finitely many functions and representations, with no theoretical guarantees.\n\nThey also consider the minimax regret in pure strategies, given by\n$$\\min_{R \\in \\mathcal{R}} \\max_{f \\in \\mathcal{F}} \\mathsf{Regret}(R,f)$$ \nwith the goal of finding an optimal saddle point representation $(R^\\ast, f^\\ast)$ in the linear MSE case.\n\nThe results in the paper are as follows:\n\n**The linear MSE setting:** Where the data $\\mathbf{x}$ is non-degenerate with zero-mean and covariance $\\Sigma_{\\mathbf{x}}$, the representations are linear ($R(\\mathbf{x}) = R^\\top \\mathbf{x}$ for $R \\in \\mathbb{R}^{d \\times r}$), the response functions are linear (response class is $\\mathcal{F}_S$, consisting of functions of the form $f(\\mathbf{x}) = f^\\top \\mathbf{x} + \\varepsilon$, where $\\varepsilon$ is heteroskedastic, mean-zero, noise, and the coefficient vector $f \\in \\mathbb{R}^d$ lies in the ellipsoid given by a positive definite matrix $S$), the loss function is mean squared error (MSE), and the prediction functions are also linear ($Q(\\mathbf{x}) = q^\\top \\mathbf{x}$).\n\n* Here they characterize the minimax pure regret, as well as the optimal saddle point pair $(R^\\ast, f^\\ast)$ giving the minimax regret w.r.t pure strategies (Theorem 2). Interestingly, the optimal representation involves _whitening_ the input vector and then projecting the result on the _top-$r$ eigenvectors_ of the $S$-adjusted version of the data covariance $\\Sigma_{\\mathbf{x}}$.\n* They also characterize the minimax/maximin mixed regret, as well as the optimal mixed strategies $(\\mathcal{D}^{\\mathrm{fn}}, \\mathcal{D}^{\\mathrm{rep}})$ leading to this regret (Theorem 3).\n\nThe characterization results also generalize to infinite dimensional feature spaces $\\mathcal{X}$ (rather than $\\mathbb{R}^d$) with some more assumptions (independent noise). This is only done in Appendix F.\n\n**General case**: Here they do implicitly assume some finite dimensional, differentiable, representation for the representations and response functions such that the saddle point problem giving minimax regret can be approximately-solved using an iterative procedure (proposed). The algorithm is motivated by the application of some theoretically-applicable concepts (for saddle point problems) --- iteratively adding to (and hopefully improving) the sets of representations and the response functions alternately,  using projected gradient descent on the regret w.r.t one (keeping the other set fixed), and then adjusting the weights assigned to the various representations and functions in the currently explored set using MWU (as in Freund and Schapire's adaptive game playing framework). However, there are understandably no theoretical guarantees, since the saddle-point problem involved is not convex-concave in general.", "questions": "None", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "* The game-theoretic framework proposed by the paper is very interesting and is novel (in terms of application to representation learning) to the best of my knowledge.\n* The results in the linear MSE case are very precise and complete. They give the intuitive expected results when the response class is $\\mathcal{F}_S, S=\\\\{I_d\\\\}$ = unit-norm linear functions (Example 5) and when the response class is $\\mathcal{F} = \\\\{I_d\\\\}$ = identity function (Appendix E). \n* The linear MSE results also seem to have some interesting consequences (depending on the structure and correlations of $S^{-1}$ and $\\Sigma_{\\mathbf{x}}^{-1}$) in general (interpreting the entries as some form of feature importance/correlation weights in the input data and in the prediction task respectively), which are very novel to the best of my knowledge, and could well be exploited in other works.\n* The representation learning algorithm for the general case is a substantial contribution which is well-motivated using existing theoretical frameworks, even in the understandable absence of theoretical guarantees.\n* The examples in the main paper are very useful in conveying the gist of the ideas.\n* The experiments, while limited, are well-thought-out (validating the general algorithm in the linear MSE case, comparison with standard PCA etc).", "weaknesses": "* The experiments are very limited given the scope of the paper (\"learning good representations for general prediction tasks\", as it may said-to-be). The experiments do not compare to any state-of-the-art practical methods for learning representations at all, especially when applying the representations to different tasks (which I feel is important given the lack of theoretical guarantees for the general case algorithm). However, this paper may be viewed as introducing a _novel framework_ for representation learning/evaluation that links it to saddle-point-game theory (in a way that prior works do not) and hence make it possible for any advances in solving hard saddle-point-games to lead to better approaches for learning representations.\n* The meat of the paper is mostly in what is effectively the supplementary material (after the references). The authors have albeit put substantial effort in trying to condense the ideas involved in the proofs as well as illustrate using good examples in the main section. However, it seems to be a losing battle, and any useful perusal of this paper must involve substantial parts of the supplementary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5hdRJrJyuw", "reviewer": "Reviewer_yB5J", "summary": "They propose a game-based methodology to learn the classical machine learning problem of dimensionaity-reducing representations of feature vectors. On the machine learning they consider the linear setting and use the mean square error loss function. On the game theoretic side, they used mixed and pure strategies.", "questions": "The goal of RL is the minimize regret, while the goal of this seems to be to minimize MSE loss. There are some results relating to regret, but how does this relate to the MSE that results in applying this method? \n\nAlso for Theorem 3, does this assume there are only finitely many possible feature vectors (or does it just assume that the dimension of the feature vectors is finite). Just to check my understanding, I assume the dimension of the covariance matrix matches the dimension of the feature vectors learned correct?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "They propose an interesting way to study a very classical problem. The paper is well-written, and clear", "weaknesses": "The computation can be complex such as in solving Ap = b for the probability p in the mixed minmax strategy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0wTk5tdWqH", "reviewer": "Reviewer_eNwZ", "summary": "The submission proposed a two-person game to solve the representation learning problem. It targets on a given class of tasks. A theoretical justification was made for the linear setting. A series of discussions were provided following the proposed algorithm for the general setting.", "questions": "d) The analysis for the linear case seems to be adapted from the game theory. Could you please clarify the technical contribution, if any, in the analysis?\ne) Is it possible to show the game will reach some situation, such as an equilibrium? Representations from the equilibrium may represent a negotiated outcome from both players.\nf) Although Examples 6 -- 9 help us to understand the nature of Algorithm 1, one still cannot know Algorithm 1's applicability. Would it be better to compare Algorithm 1 with baselines to show the representations output from Algorithm 1 are better than the existing methods?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "a) The submission proposed a game to solve the representation learning for a given class of tasks. The formulation is practical as one can control the relevant tasks.\nb) The submission provided theoretical justifications for the linear setting to characterize the learned representations and the performance bounds (Theorems 2 and 3).", "weaknesses": "c) An algorithm is proposed to learn the representation for the general case. However, the evidence, from the theoretical or the practical perspective, is insufficient to determine the applicability of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)