Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose bring robustness to kernel weight regression (Eq. 1) through adversarial weight perturbation. The main difficulty lies in the tie between the weights and kernel, and therefore the need for the perturbation to be consistent with the kernel. The main idea here is to reparameterize the optimization in Eq. 1, to reach Eq. 3, where a doubly non-negative matrix is used to represent the weights. This reparameterization makes solving the inner maximization possible through a dual formulation. The authors studied the problem completely for two divergences and evaluated the method on various real/benchmark datasets.
main_review: I think the paper is in a good shape. Perhaps the only issue is why the authors perturbed only the response variable in the experimental results. What happens if the perturbation is applied on the features as well. More importantly, does the method resist such perturbations if they are adversarial, and not random? In addition, it would make more sense to evaluate the method based on some other datasets that exhibit larger natural distribution shift, i.e. through split of train/test according to a third variable (e.g. time in bank transactions, etc.) 
limitations_and_societal_impact: The section is not provided in the paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a novel way to address the problem of reweighting the empirical risk, which relies on a parameterization of the risk by a doubly non-negative weighting matrix.
The corresponding optimization problem is of "min-max" type, where the maximum is taken over some set of possible weights encoded by a divergence, here the log determinant and Bures-Wasserstein divergences.
The exploitation of dual techniques allows the problem to be tractable for both divergences, and experimental results emphasize on the efficiency of the approach in the context of perturbed training samples.
main_review: -Originality:
The problem tackled in this paper is well known, and the approach is novel.
Especially, the idea of treating the reweighting of the empirical risk in an adversarial manner is very original.
Related works are (up to my knowledge) adequately cited, and the contributions are clearly stated.

-Quality:
The submission is mathematically sound.
The difficulty brought in by the introduction of the max problem is adequately tackled using parametric duality, allowing for a practical computation of the gradient of the objective function and to first-order optimization methods.

Q1: The proposed models (NW, LLR) are somewhat simple with few parameters. Would the method be applicable with more complex models provided by e.g. kernel methods (representer theorem allowing a parameterization of the model by $n$ scalars, where $n$ is the number of training samples) ?

Q2: The problem tackled concerns empirical risk minimization without regularization, is there a reason for this choice, considering that one goal is to generalize better ?

The experimental section is furnished, and the code is available (matlab). Many aspects of the proposed approach are investigated, and the authors are honest about evaluating the strength of their method (especially about the hyperparameter $\rho$ induced by the size of the adversarial reweighting set, and the computational time).

Concerning the experimental baseline, I would have expected stronger baselines with a goal of being robust to the type of outliers introduced in the paper ($y \to \kappa y$ for some outlier level $\kappa$) such as kernel ridge regression (KRR) (the $\lambda$ parameter allowing for better generalization capabilities than plain empirical risk minimization), or models based on the minimization of the Huber loss instead of the square loss.
Especially, considering that the task at hand is conditional expectation estimation, a simple kernel ridge regression baseline (learned with regularization in RKHS norm) could bring more insights about the strength of the proposed approach.

-Clarity:
The submission is well-written and pleasant to read.

-Significance
The problem tackled is of prime interest, as the solution provided in the paper can help mitigating bias in the data, and achieve more fairness in machine learning algorithms.
The idea of introducing a min-max problem using a set of possible weights is fertile and could be adapted to algorithms other than the ones presented in the paper, thus leading to interesting potential future works built on the current submission.

-Overall strengh:
Original idea for reweighting the training risk, clever exploitation of dual techniques.
-Overall weakness:
Not very strong baselines for conditional expectation estimation.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper discusses how to "robustify" a sample weighting scheme by finding a re-weighting that is minimax optimal for a pre-defined uncertainty set. The authors give expressions for the optimal re-weighting scheme for two different distance metrics: log-determinant divergence and Bures-Wasserstein divergence. Authors show the optimal re-weighting can be calculated via gradient updates. Experimental validation is provided where the labels are perturbed.
main_review: In terms of the motivation of this work, I believe optimal re-weighting of kernel matrices so that they have additional robustness properties to adversarial perturbation is likely to have an impact in the nonparametric regression literature. Relatively speaking, this paper is written in a pretty approachable way, and the results are clearly stated. 

Some points that would help me understand the context of this paper and the results they produce are as follows:

- I wish more interpretation was given to how to interpret these optimal re-weightings as compared to the original weighting matrix---right now they are simply stated as complicated mathematical expressions which are hard to parse. 
- Why is optimizing with respect to a ball (w.r.t the given divergence) of radius $\rho$ around the original weighting matrix the right notion of "robustifying" the estimator? For what sorts of data perturbations is the right notion of robustifying an estimator? I am not an expert in the field, and it might be standard to optimizing with respect to ball around the original matrix. However, it is not clear to me why. More context should be given as to what other notions of robustification have been studied in the literature, and why is the particular notion the authors choose to look at the right one. Indeed, it still remains unclear to me when one should choose to the log-determinant divergence vs. the Bures-Wasserstein divergence.
- With respect to the experiments, the particular scheme use to perturb the training samples seems non-standard to me, i.e., $y \to \kappa y$ where $\kappa$ is sampled uniformly between $1.8$ to $2.2$. What form of data corruption seen in practice does this correspond to? Some standard notions of data corruption include "error-in-variables regression" and the "Huber contamination model". The experiments don't seem to correspond closely to either.

I would be willing to increase my score if these points above were engaged with more meaningfully. In short, to what sorts of natural data corruption seen in practice does their re-weighing scheme provide robustness to, both theoretically and experimentally (details above).
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a method that minimizes the worst-case risk among a set of some generalized weighted empirical risks. The generalized weighted empirical risks are defined using doubly non-negative (i.e., non-negative, positive (semi-)definite) matrices that is close to the matrix corresponding to the original sample weights. The proposed method boils down to solving a mini-max problem involving the matrix, but surprisingly the gradient of the optimal objective of the inner maximization admits a closed-form solution, allowing first order optimization for the outer minimization. The paper also provides experiments using four benchmark datasets and shows the effectiveness of the proposed method.
main_review: # Summary of my review
The paper presents an interesting framework with an elegant solution. I have a few concerns about the motivation and the experiments, but the technical part of the work is insightful and the techniques used in the paper may have other important applications. I tend to vote for acceptance.


# Originality
The idea of the adversarial learning with doubly non-negative matrices seems new as far as I can see. The methods and the theoretical results also seem original. However, I am not an expert of this domain, and there may be some similar work that I am not aware of.


# Quality
The theoretical results and the derived methods presented in the paper are highly non-trivial to me. The results and proofs are quite technical, but the paper presents them very gently and clearly.
My concerns are
* Despite its mathematical elegance, it is hard for me to interpret the practical meaning of taking the adversarial matrix from doubly non-negative matrices. It would be nice if the authors could provide some intuitive explanations.
* In the experiments, the authors only consider the perturbation to the output variable of the training samples. It is possible to consider other kinds of perturbations?


# Clarity
The writing is overall very clear and easy to follow except for the technical details. The only think that was unclear to me was how to set \Omega_{i, j} when i \neq 0 and j \neq 0. I think the authors should explain this in the rebuttal.


# Significance
The technical contributions are significant. I personally would not be able to obtain such elegant results if I did not see this paper.
On the other hand, the practical contribution remains unclear. How does adversarially learning with doubly non-negative matrices help learn better in practice? Also, is it really helpful to do adversarial robust learning in the first place? [14] claims that distributionally robust learning may not lead to robust solutions. My intuition is that adversarially weighting samples gives heavy weights to samples with large loss, which ends up being sensitive to outliers. It may work in the opposite way to the intention of making the solution robust. Does the proposed framework not have this issue?


# Update after the authors' response and discussions
After reading the other reviewers' comments and the feedback from the authors rethinking about the value of the paper, I lowered my score from 7 to 6. In a few words, it is technically interesting, but I am not convinced about its usefulness in the ways the authors claim.
I appreciate the technical contribution of the paper, but I am not sure that the motivation explained by the author naturally leads to the problem formulation of the paper, or that the problem solved in the paper really "robustifies" the estimator. According to the discussions with the authors, it seems that the connection between the min-max optimization over the NN-matrices and the robustness remains an open question, which means that the method is a heuristic in terms of its statistical effectiveness. The only evidence of the practical usefulness is the experimental result. If the authors support the usefulness of the approach only by experiments, there should be much more extensive empirical studies. For these reasons, I do not strongly recommend accepting the paper.

limitations_and_societal_impact: The paper does not discuss the limitations or the societal impact. Perhaps, the authors should mention the scalability issue of the proposed method because it needs the inverse of a N-by-N matrix at every evaluation of the gradient.
review_title: null

Meta-review: The paper is technically sound, however its motivation and practical impact are unclear: the reasons why the contribution is one method of choice to go for small sample situations are not spelled out clearly enough. This makes the paper a bit subpar wrt the expectations for a paper at NeurIPS.

Decision: Accept (Poster)