Answer to c)

Our main goal here is to propose a principled framework for learning representations based on partial knowledge of downstream prediction tasks. We aimed for analytical exploration of its fundamental properties, and thus focused on analysis of the linear-MSE setting, specifically Theorem 3. We believe that this provides a strong evidence for the validity of the framework. The proof of this result is rather convoluted (see our answer to d) below), and thus is also a main contribution of the paper. Algorithm 1 was developed to show that the framework is viable beyond the linear case, even in general cases (loss function, representation rules). Following this approach, we have focused the paper on the core of the framework and basic settings, rather than on practical baselines. Going beyond basic settings inherently requires some domain-knowledge, e.g., determining the class of functions $\{\cal F\}$, and we believe that this deserves a separate inquiry. We hope that this would be achieved in future research, both by us, and by experts in various domains. We note, however, that the incremental algorithmic approach we take follows a widely acceptable solution in various ML problems, as we discuss in depth on page 2 (“Algorithmic contribution”), and in Appendix B, pages 18-19 (“Game-theoretic formulations in statistics and machine-learning” and “Incremental learning of mixture models”).

Answer to d)

The main part of the analysis in the linear case is the proof of Theorem 3 (which is rather long, about 7 pages). Its goal is to find the optimal solution for the representation in mixed strategies. The main technical difficulty is that solving the mixed minimax problem directly, that is, solving

$\min\_{\boldsymbol{R}}\max_{f\in{{\mathcal F}_{S}}} \mathbb{E}\left[\mathsf{regret}(\boldsymbol{R},f \mid \Sigma\_{\boldsymbol{x}})\right]$

is intractable. However, the minimax theorem from game theory implies that its value equals the maximin problem, that is, to $\max_{\boldsymbol{f}}\min_{\boldsymbol{R}}\mathbb{E}\left[\mathsf{regret}(\boldsymbol{R},f\mid\Sigma_{\boldsymbol{x}})\right]$ where now the function can be random too. This problem is still not trivial, but we managed to solve it. This resulted $\boldsymbol{f}^{\*}$, the function part of the saddle-point $(\boldsymbol{R}^{\*},\boldsymbol{f}^{\*})$, which solves both the minimax and maximim problems. We then exploited the maximin solution as a certificate to find the optimal representation $\boldsymbol{R}^{\*}$, because the minimax value is never smaller than the maxinim value. Thus, if one finds a random representation for which

$\max_{f\in{\cal {\cal F}_{S}}}\mathbb{E}\left[\mathsf{regret}(\boldsymbol{R},f\mid\Sigma\_{\boldsymbol{x}})\right]$

equals the maxinim value, this guarantees that this random representation is the sought $\boldsymbol{R}^{\*}$. We find this by first making an educated guess regarding a simple structure that $\boldsymbol{R}^{\*}$ should posses. We then optimized over this structure, and shown it is reduced to solving an equation $Ap=b$. We proved that any solution to this equation leads to a representation whose regret is no larger than the maximin value, and is thus $\boldsymbol{R}^{\*}$, the saddle-point representation. To complete the proof, we show that a solution to $Ap=b$ must exist, and that the support of this solution is at most $\ell^{*}+1$. This leads to an optimal random representation $\boldsymbol{R}^{\*}$ that is drastically simpler than a general probability distribution over $\mathbb{R}^{d\times r}$, and reinforces the effectiveness of the approach.

Answer to e)

As follows from our answer to d), the obtained solution $(\boldsymbol{f}^{\*},\boldsymbol{R}^{\*})$ is exactly the equilibrium of the game. If both sides agree to use this solution, no side can improve its payoff by a one-sided change of his/her strategy.

Answer to f)

As we have answered to point c), we focused this paper on the general approach, theoretical guarantees on fundamental settings, and a general algorithm. However, even though it is just a basic setting, in Example 9 we compare our method to PCA and show a significant improvement. PCA is also clearly not the state-of-the-art, but it is a classic and principled method that enables initial comparisons, and evidence of the potential of the method.

In summary, our main contributions are a general framework, an analytic solution in basic setting (linear-MSE) and its proof, and a “meta-algorithm” which shows the viability of the method in the general cases. Hopefully, applications will be explored in depth in the future. In light of the above clarification, we would appreciate if you could re-evaluate our contributions, and finally thank you for your effort in reviewing the paper.

Response to the weakness

As we mention in Remark 1 on page 5, the direct solution of $Ap=b$ is infeasible in high dimensions, since it requires solving a linear program with very large dimension ${\ell^{\*} \choose r}=\Theta((\ell^{*})^{r})$. In the paper, we mentioned that this can be circumvented by using our general algorithm to solve the linear case. This approach is indeed effective, as shown in Example 6 on page 8. However, we actually developed a computationally effective algorithm to directly solve $Ap=b$, which allows to use the closed-form solution, but haven't included this algorithm in the paper in order not to burden the reader. It is reminiscent of the ``basis pursuit'' algorithm, and operates as follows: Recall that $A$ has $\ell^{\*}$ rows and ${\ell^{\*} \choose r}$ columns. Theory guarantees $Ap=b$ has a solution $p$ that has less than $\ell^{\*}+1$ non-zero entries. Thus, the algorithm needs to find the support of this solution, that is, $\ell^{\*}+1$ column indices out of the possible ${\ell^{\*} \choose r}$ columns of $A$ with non-zero weights. This can be done iteratively. First, we begin with an initial guess of $\ell^{\*}+1$ columns. It could be arbitrary, but as a general rule-of-thumb it is better to choose columns with $\ell^{\*}-r$ ones on the larger eigenvalues (and zeros for other columns). Let us denote the sub-matrix of $A$ comprised from these $\ell^{\*}+1$ columns by $A_{1}$, and the vector $p$ reduced to these indices by $p_{1}$. Then, a solution to $A_{1}p_{1}=b$ is sought that only uses this support. Specifically, since an exact solution perhaps cannot be found, we instead solve $\min_{p_{1}}\||A_{1}p_{1}-b\||\_{1}$, which is a linear program. Let the solution be $p_{1}^{\*}$. Then, the error is given by $e_{1}=A_{1}p_{1}^{\*}-b$. If $e_{1}=0$ then this means that we have found a solution to $Ap=b$ with a support of at most $\ell^{\*}+1$, as theory predicts. Otherwise, the error $e_{1}$ is rounded towards a column of $A$. Specifically, we find the $\ell^{\*}-r$ coordinates of $e_{1}$ with maximal value, and choose a column of $A$ with ones on these columns (and zero otherwise). This new column is added to $A_{1}$ to create $A_{2}$. Next, we similarly solve $\min_{p_{2}}\||A_{2}p_{2}-b\||\_{1}$ and obtain error $e_{2}$. If $e_{2}=0$ that this means we have solved $Ap=b$ with $\ell^{\*}+2$ columns, which is sub-optimal, but still rather effective. We continue to more such iterations, adding columns to $A_{i}$ as necessary, one column at a time, until $e_{i}=0$. If the number of iterations is not too large, then this only requires solving linear programs of dimensions much smaller than ${\ell^{\*} \choose r}$. As an example, in case $d=100$, $r=20$, and the eigenvalues are $\lambda_{i}\propto1/\sqrt{i}$ it turns out that $\ell^{\*}=61$. While ${\ell^{\*} \choose r}={61 \choose 20}=6\cdot10^{15}$ is huge, this method finds a solution with $120\approx2\ell^{\*}$ columns, and thus feasible, and also rather effective.

Response to the questions

• The regret and the MSE (or more generally, the loss) are tightly related. For example, in the linear-MSE setting, the regret is the MSE of the proposed solution, minus the noise variance. The variance of the noise represents an inevitable loss that cannot be reduced by any representation. It is thus subtracted from the MSE in order to focus on the part of the MSE that can be reduced by optimization of the representation.
• In Theorem 3, the feature vector is $\boldsymbol{x}\in\mathbb{R}^{d}$ with $d<\infty$ and its covariance matrix is $\Sigma_{\boldsymbol{x}}\in\mathbb{R}^{d\times d}$, so it is a finite-dimensional continues vector, which takes infinite possible values. A pure representation of $\boldsymbol{x}$ is a matrix $R\in\mathbb{R}^{d\times r}$ so that the representation is $\boldsymbol{z}=R^{\top}\boldsymbol{x}\in\mathbb{R}^{r}$, which is also a continues vector. A mixed representation allows to choose the matrix $R$ randomly. In Theorem 3, we show that this randomization may be supported on a finite set of matrices $\\{R_{1},R_{2},\ldots,R_{\ell^{*}+1}\\}$ so that the representation is $\boldsymbol{z}=R_{j}^{\top}\boldsymbol{x}$ with probability $p_{j}$. The theorem provides the optimal choice of set of matrices and the probabilities $\\{p_{j}\\}$.

We hope that this clarifies your questions, and will be happy to take further ones. We thank you for your effort in evaluating the paper and the positive assessment.

Our answers to the mentioned weaknesses are as follows:

• Indeed, our main goal in this paper was to introduce this framework and explore its basic principles. We consider our proposed algorithm as a meta-algorithm, which demonstrates that the proposed approach is not limited to the linear setting, and agree that it requires extensive experimentation in applications. We have some ideas for such applications in mind, for example, using prior knowledge on region of interest in computer vision, or using prior knowledge on non-coding DNA in genomics. However, this requires domain-knowledge in determining the class of functions ${\cal F}$, and various other details. This will divert the paper to these applications, rather than to the broad scope of representation learning. We hope that extensive experimentation would be achieved in future research, both by us, and by experts in various domains.

• Our approach in writing the paper was to first present the general framework and its importance; second, explore it theoretically in basic linear settings; and third, propose an efficient algorithmic for the general case, which cannot be covered by theoretical analysis. We believed that all these components are vital, and thus deferred the technical aspects to the appendix, leaving them to in-depth readers. We understand that this comes at a cost, and we will re-inspect the paper from this aspect. We would be happy to take any suggestions for improvement (e.g., what important points are missing in the body of the paper), and will incorporate them into an updated version.

Thank you for a careful reading of the paper, a detailed summary, and a positive assessment.

• Response to the weakness: Our proposed Algorithm 1 is applicable to any differential representation, not just linear. This algorithm alternates between optimizing an adversarial function (phase 1) and a new representation rule (phase 2). We have not focused on this in the body of the paper, but the optimization of the new representation rule in phase 2 is discussed in Appendix G.2 in detail. Algorithm 3 proposed there for the phase 2 optimization of the representation is based on computing gradients of the loss with respect to the representation rule (line 20). Therefore, the algorithm is applicable as long as these gradients can be computed (sub-gradients may also suffice). In Appendix H.4 we conducted a preliminary experiment with a one hidden-layer NN architecture, and showed the improvement of the regret. In future research we plan to explore our algorithm for non-linear representations in depth.

• Response to the question: Yes, extension to representations that are based on infinite-dimensional features is possible. In Appendix F, we provide one possible such extension, to a Hilbert space setting (this is mentioned on page 5, in the remark before Example 4). In this setting, the original feature vector $x\in\mathbb{R}^{d}$ is mapped to a vector $R(x)=(\psi_{1}(x),\ldots,\psi_{r}(x))^{\top}\in\mathbb{R}^{r}$ where $\\{\psi_{i}(x)\\}$ are non-linear feature-maps, taken from a Hilbert space of such maps. Our theoretical results on pure and mixed representations are generalized to this setting in Theorems 19 and 20. One can also consider the opposite setting – a linear representation followed by a non-linear (kernelized) predictor. Generalizing the theoretical results to this case is interesting, but appears to be challenging. This is because it requires obtaining a closed-form expression for $\mathsf{regret}(R,f\mid P_{\boldsymbol{x}})$, as was obtained for the linear case in Lemma 16, Appendix E.2. In turn, this requires understanding how the non-linear feature map affects a linear representation $z=Rx$, which is difficult in general. In future research, it would be interesting to furnish conditions that allow to analyze such cases too. By the way, referring to the weakness above, this setting is another case in which the representation is non-linear.

Thank you for your effort in evaluating the paper and the positive assessment.