Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper studies the utility-invariance trade-off problem and characterizes closed-form expressions for two types of trade-offs. This is an important problem since it's relevant to privacy, fairness and representation learning. 
main_review: This paper studies the utility-invariance trade-off problem and characterizes closed-form expressions for two types of trade-offs. This is an important problem since it's relevant to privacy, fairness and representation learning. The results are theoretically sound and the paper is mostly well-written.

However, there are a few aspects that the current version of the work is lacking, detailed below.

Comparison to [10]: The authors did not provide much comparison with the most closely related work [10]  (the only relevant part I found is line 96-98).  Both of these two papers work on very similar problem with only a few small differences in the choice of loss functions, and the results are similar from high level as well (and they even have nearly identical titles). While some comparison will be mentioned in this review, I think it's necessary to include a thorough comparison in the future version of this work.

Clarity: This paper is mostly well-written. However, there are some mathematical details that are not clearly explained. 

(1) In equation (10), the definition of the constrained function space $A_r$ involves an additional (tunable) parameter $\gamma$, whose role is not discussed in detail (apart from mentioning it as a trade-off parameter), nor is there any theoretical/empirical suggestion for how to choose the parameter. Furthermore, the main result (Theorem 4) holds regardless how $\gamma$ is chosen - which appears to be strange since $A_r$ itself depends on $\gamma$.  

(2) In Definition 1 & Definition 2, the trade-off objectives are stated as a linear combination of (a) prediction loss on y and (b) dependence between z and s. However, in the main theorem (Theorem 4), the part (a) is replaced with dependence between z and y. While the authors mentioned in line 213 and line 129-134 some explanations about this change, this not only causes confusion for the reader, but also (to some extent) hides a flaw in the reasoning about the design choice of loss, detailed below.

Choice of the loss function and Technical difficulty: As mentioned above, the authors replaced the target loss with the dependence (HSIC) loss. But this choice is poorly justified - while it was mentioned in Theorem 1 that the MSE loss does not guarantee statistical independence, this reasoning only applies to the sensitive feature ($s$) part, where one hopes to achieve independence with The same reasoning does apply to the target loss $y$ part, where the goal is to make accurate prediction, rather than strong dependence. 

Furthermore, the improvement over [10] mentioned in line 99-102, are mostly due to this change - the original formulation in eqn (1) appears to be much more difficult to deal with comparing to the setting in theorem 4, while theorem 4 bypasses this difficulty and only require simple eigenvector/eigenvalue analysis. The weaker characterization in [10] (only lower bounds are provided there) involves significantly more challenging analysis, for which I suspect that the authors would encounter similar challenge if they didn't made this simplification.

Experiments: The experiment section is very short and only toy dataset  (mixture of two Gaussians) is included. It is also unclear how the theory would impact the applications mentioned in the paper like domain adaptation and fairness.


limitations_and_societal_impact: -
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: This paper identifies and determines two tradeoffs between utility and dependence in learning invariant representations. The main contributions claimed by the authors are two folds: 1). closed-form solution for the global optima of the underlying optimization problem; 2). empirical estimates of the tradeoff terms that converge to the population counterpart in the large data limit. 

main_review: Overall, I find this paper a little bit hard to follow. I think the overall presentation would be significantly improved if the authors could justify the claims made in the paper. For example, to motivate the problem, the authors claimed between Line 133-134 that "As such, ARL is inherently incapable of attaining the trade-offs achievable by complete measures of dependence". I personally think this is an overstatement, since the conclusion of Theorem 1 only applies to the mean-squared error in the regression setting, and conclusion of this theorem completely fails as long as one uses either the variational form of Wasserstein or TV distances as the score function of the discriminator. Hence I felt it is inappropriate to say that ARL is inherently incapable of attaining the trade-offs. In fact, it's just a matter on the choice of your adversarial loss function and the hypothesis class of your adversarial.  

Perhaps my main concern is the lack of detailed comparisons with previous works and the overstatements of the contributions made in this work:
-   The authors mentioned in the related work that "In contrast to this body of work, our trade-off analysis is applicable to multi-dimensional discrete and/or continuous attributes where we find the exact optimal trade-offs." It seems to me that the conclusion in this paper only holds for continuous random vectors where the space of both S and Y are R. To see this, following the discussion between Line 164 to Line 170, the authors used Cov(\alpha(z), \beta(s)) where \alpha and \beta are in some RKHS. Per the original paper on HSIC [1], this criterion is for univariate continuous random variables, right?  

[1]. Kernel Methods for Measuring Independence, https://www.jmlr.org/papers/volume6/gretton05a/gretton05a.pdf

-   A detailed comparison with a previous work is missing. In particular, this work makes the normality assumption of the joint distribution (Line 176 to 178) in the feature space and furthermore an independent assumption on the learned features (Eq. 10) in order to derive the tradeoff result. Similarly, [2] also makes the normal assumption but is free of the disentanglement assumption. In terms of technical results, it appears that the results in [2] (in the regression section) give similar bounds, i.e., the optimal representations are given by the top two eigenvectors of the kernel covariance matrix, and the authors also show that under the Gaussian assumption their lower bound becomes tight. I was wondering what's the difference between the results of this paper to that of [2]? Given the close relationship between these two works, the authors should make a clear cut comparison w.r.t. the bounds in [2]. So far such a comparison is completely missing. 

[2]. Fundamental Limits and Tradeoffs in Invariant Representation Learning, https://arxiv.org/abs/2012.10713

-   The authors claimed that their closed-form empirical estimators lend themselves to practical invariant representation learning algorithms. Where are the proposed invariant representation learning algorithms in the paper? It seems to me that the experiments are mainly used to verify the theoretical results in the paper. This is totally fine, but the claims made in the introduction does not reflect what's going on in the experiment section.  

Furthermore, there are several claims in the paper that are not justified and do not seem correct to me, including:
-   Line 33, the authors claim that "This independence condition is satisfied if and only if (iff), the representation z is independent of s". I don't think this is true. To see a simple counterexample, it's certainly possible that z is not independent of s while the predictor \hat{y} being independent of s -- simply making \hat{y} to be a constant function of s. 

-   Line 50-51, the authors claim that "Including all measurable functions in the hypothesis class of the encoder f(·) and target predic51 tor gY (·) ensures that the best possible trade-off is included within the feasible solution space." I was wondering why this is true? Presumably, even if one works with all the Borel-measurable functions, these functions are still determnistic mappings. Would this be sufficient to achieve all the feasible solutions? 

-   Line 192-193: could the authors further elaborate on why this statement is true? "Using, the representer theorem [45], it follows that f(x) = ΘE[kx(x1, x), · · · , kx(xn, x)]T, where Θ ∈ R r×n is a free parameter matrix."

===============================================================

I have read the authors' responses as well as other reviews. Please see my detailed comments below. Overall, I am not convinced by the response and I will adjust my rating from 4 to 3. 

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: This paper studies the tradeoffs between accurately predicting the target and being invariant with respect to a known sensitive attribute in representation learning. When the features are functions in a RKHS, the paper derives closed-form solutions to the tradeoff optimization program. Finite sample guarantees are also given.
main_review: The paper tries to establish theoretical foundations for invariant representation learning, which is an important direction. The proposed method improves over baseline ARL. However, there are several major weaknesses:

1. The objective of optimization isn't well motivated. Why should one use HSIC as the dependence measure instead of mutual information?
2. The feature model is very restrictive, i.e. orthogonal kernel functions (eq 10) and the theory doesn't seem to be able to generalize to more commonly used models like neural networks.
3. The tradeoffs D, L, F seem to only differ in hypotheses classes. I don't see how the distinctions are meaningful.
4. No experiments on realistic datasets to demonstrate the usefulness of the theory.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper identifies and determines two fundamental trade-offs between utility and semantic dependence induced by the statistical dependencies between the data and its corresponding target and semantic attributes. The authors derived closed form expressions for the global optima of the proposed optimization problems (for Tradeoff D, Tradeoff L and Tradeoff F among others), exposing the nature of the tradeoffs. Some convergence guarantees and experiments on synthetic data are also provided. 
main_review: Strengths:

+ Learning invariant representations and quantifying the tradeoffs between target and semantic attributes is an important topic in machine learning today in view of privacy protection and fairness. 

+ The authors' formulation of these issues in terms of the mathematical optimization problems in Section 3 is rather neat. The fact that the solutions can be obtained in closed form is also very nice. It provides neat insights.

Weaknesses:

- The experimental section is rather weak. I would have expected a more extensive set of experiments, possibly on real-life data to be done. Given the extensive theory that has been developed, it is surprising that the authors have not exploited the theory more on real-world (or at least larger synthetic) datasets to corroborate for example the tightness of the bounds in Theorem 6. This is a missed opportunity. It would have been nice to experiment with various kernels. The dependence on the parameter \tau is also not well explained. It seems like a hyperparameter that is important in real-life applications.  

Having said this, I must confess that I'm not an expert in this area of invariant representation learning.
limitations_and_societal_impact: This paper may have some impact in the study of fairness, privacy and other contemporary areas in machine learning.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes an MMD-style regularizer on the representation learned by a classifier in order to enforce invariance to a sensitive attribute. This is similar to existing work on invariant representation learning with an adversary, but using a measure of feature correlation which enforces more invariance than just the first-order statistics.
main_review: I think this paper is decent, but not quite at the point where it's ready for publication.

There's quite a bit of overclaiming in the earlier writing when compared to the actual contribution presented. For example, the title of the work mentions the "tradeoffs and limitations" in invariant representation learning, and the earlier sections prepare the reader for some sort of new insight. However, upon a full read through, it is apparent that the tradeoffs and limitations to which the title refers is just the existing discussion on the "bottleneck principle" of Tishby et al, and the inherent tension between expressivity and invariance of a set of features when the label and sensitive attribute are correlated. This Pareto frontier is well-discussed in the literature (off the top of my head, see: "The cost of fairness in binary classification", "Costs and Benefits of Wasserstein Fair Regression" [which is concurrent with this submission, but further demonstrates that this perspective is not unique], in addition to all the works cited by this paper [8, 9, 10]).

Instead, the contribution of this paper (and what I believe the writing should more clearly focus on) is an MMD-like regularization penalty which under appropriate conditions correctly captures higher-order non-linear dependence between the learned features and the sensitive attribute in question. Theorem 1, while making an interesting observation about the limitations of adversarially invariant representation learning, is not the first time this has been pointed out (the authors acknowledge this). Furthermore, this is not an inherent fault of adversarial representation learning as claimed; rather, it is inherent to losses which are evaluated pointwise, such as MSE (the example used in the theorem statement). If, for example, we were to introduce a "critic" to regularize the distribution divergences (for example, to estimate mutual information or Wasserstein divergence), then adversarial representation learning would be able to identify higher-order dependencies. This is partially acknowledged, but much later (line 277), and it should be made clear earlier.

Ultimately, **I think the theoretical results for the proposed penalty term are valuable; I just think that there is too much focus on everything else, which is not newly presented in this work.** I should also note that I'm not very familiar with existing MMD-like divergence penalties for feature invariance. This general idea is being used in a lot of places: I've seen many such regularizers proposed, particularly recently, for OOD generalization [e.g., "Causally-motivated Shortcut Removal Using Auxiliary Labels", "An Information-theoretic Approach to Distribution Shifts", there are many more but I'm just picking a few to demonstrate that I'm not making this up]. As such, the overall novelty of this penalty term is questionable to me---it is possible that I'm just unaware of the previous literature.

Beyond these issues, the earlier notation of this work is very problematic:
* Are **x**, **y**, **z**, **s** fixed (after drawing the training distribution) or not? They are initially presented as random, but then the discussion of the label tradeoff treats the **x, y, s** as fixed (such that we can define the ideal **z** for each observation). And then **z** is presented as both fixed (chosen to be ideal for the particular training observation) *and* random (assumed to have a distribution with bounded second moment)?
* As far as I can tell, in the space of arbitrary measurable square-integrable functions f, shouldn't the label tradeoff be exactly equivalent to the data tradeoff? If **z** is assumed to have bounded second moment, then wouldn't the function f defined as f(**x**) = **z** satisfy square integrability? In which case, there always exists a function which achieves the "ideal" representation, regardless of the data distribution... I think the difference between the two in the experiments is actually the result of the "function tradeoff" idea, where such an f is undiscoverable.
* In the proof of Theorem 1, the distributional expectation of the loss is equated with the empirical loss over the training set. How does this make sense? The statement itself is trivial but it was surprisingly difficult to fully understand due to the notation.

Of course it's possible I'm misunderstanding all of these points, but I would argue that this is due to extremely inconsistent notation. I did not check the proofs in great detail because my functional analysis is not very strong, but these notational issues worry me.

I'm also unclear on why learning the "label-tradeoff" representation is at all meaningful? It requires access to the true label and sensitive feature, so of course it's useless in practice. I guess instead it's intended to show the gap between "label-tradeoff" and "data-tradeoff", but as I mentioned above I think this is actually an issue of estimation (finding the correct featurizer *f*) rather than one of approximation. In other words, I believe the "L -> D" gap as presented by the paper is actually a "D -> F" gap, and that the "L -> D" gap does not exist. If the authors disagree, it would go a long way to clean up the notation here.


--------------
**Update after rebuttal**

The authors have clarified some of my confusion, but I still feel that the emphasis of this work is too much on existing material and the material which is new is unclear and confusing, to the point that it requires significant revision. I am maintaining my score.
limitations_and_societal_impact: Sure
review_title: null

Meta-review: This paper analyzes various tradeoffs in invariant representation learning. During review, several concerns have been raised including missing comparisons with closely related work, clarity and exposition, and some misunderstandings at a conceptual level. These concerns were not adequately addressed during the discussion phase. In the end, there was a consensus amongst the reviewers that this paper is not ready for publication in its current form.
Decision: Reject