Adversarial Regression with Doubly Non-negative Weighting Matrices
Authors: Tam Le
Truyen Nguyen
Makoto Yamada
Jose Blanchet
Viet Anh Nguyen
Venue: NeurIPS 2021 Poster (2021)
Keywords: adversarial regression
kernel weighted regression
covariate perturbation
distributional robust
doubly non-negative matrices
Bures-Wasserstein
Log-determinant divergence
low-sample-size problem

Abstract: Many machine learning tasks that involve predicting an output response can be solved by training a weighted regression model. Unfortunately, the predictive power of this type of models may severely deteriorate under low sample sizes or under covariate perturbations. Reweighting the training samples has aroused as an effective mitigation strategy to these problems. In this paper, we propose a novel and coherent scheme for kernel-reweighted regression by reparametrizing the sample weights using a doubly non-negative matrix. When the weighting matrix is confined in an uncertainty set using either the log-determinant divergence or the Bures-Wasserstein distance, we show that the adversarially reweighted estimate can be solved efficiently using first-order methods. Numerical experiments show that our reweighting strategy delivers promising results on numerous datasets.

Adversarial Regression
with Doubly Non-negative Weighting Matrices
Tam Le"
Truyen Nguyen" University of Akron
Makoto Yamada Kyoto University and RIKEN AIP makoto, yamadarriken, jp
RIKEN AIP
tam. leQriken.
tnguyen@uakron.com edu
Jose Blanchet
Viet Anh Nguyen Stanford University and VinAI Research v. anhnv81@vinai. io
Stanford University
jose. blwnchet@staanooooooeoooo ord. edu
Abstract
Many machine learning tasks that involve predicting an output response can be solved by training a weighted regression model. Unfortunately, the predictive power of this type of models may severely deteriorate under low sample sizes under covariate perturbations. Reweighting the training samples has aroused as effective mitigation strategy to these problems. In this paper, we propose a novel and coherent scheme for kerneh-reweighted regression by reparametrizing the sample weights using doubly non-negative matrix. When the weighting matrix is confined an uncertainty set using either the log-determinant divergence or the Bures- Wasserstein distance, show that the adversarially reweighted estimate can be solved efficiently using first-order methods. Numerical experiments show that our reweighting strategy delivers promising results numerous datasets.
Introduction
We are interested in learning a parameter 3 that has competitive predictive performance on response variable Y. Given N training samples (2, R, D. in which (2,, 2.) are the contexts that possess explanatory power on Z. learning the parameter be posed weighted regression problem of the form
min Σ (2))(((322
(I)
In problem ( is weighting function that indicates the contribution of the sample-specific loss to the objective. By aligning the covariate (2, 2.) appropriately to the weighting term w(2)) and the loss term {(B, F,, D.), the generic formulation of problem ①1) can be adapted to many popular learning and estimation tasks in machine learning. For example, problem (I) encapsulates the family
of kernel smoothers, including the Nadaraya- Watson estimator [16] 22 39].
Example 1.1 (Nadaraya- Watson (NW) estimator for conditional expectation). Given the samples (2,. D.W we are interested in estimating the conditional expectation of Y given Z 20 for some covariate 2n Z. The NW estimator is the optimizer of problem (T) with {(B, y) || vll and
the weighting function w is given through a kernel K via (2,)) = K(20, 2,) The NW estimate of Z 20) admits closed form expression
ΣN K(20, 2:)0
3NW =
N K(20,
* equal contribution
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

The NW estimator utilizes a locally constant function to estimate the conditional expectation E|yiz zo]. Locally linear regression B 32 extends the NW estimator to reduce the noise produced by the linear component of target function 27 $3.21.
Example 1.2 (Locally linear regression (LLR)). For univariate output and z, the LLR minimizes the keinhe--eighhte loss with {[31, Bu] 2. y) (31 + B2 2 y)². The LLR estimate of E| 20] admits closed form expression
Aain=((7))) (? 12 -TPP)
BLLR =
[0]
with y = -V...... "..... E RR" W = diag (2 21),....
K 2n))
B and
1 (2) - z0)
T1
ğ =
1
(2n =0)
Intuitively, the NW and LLR estimators are special instances of the larger family of local polyno- mial estimators with order zero and one, respectively. Problem [I is also the building block for local learning algorithms [6. density ratio estimation [5] pp. 1521. risk minimization with covariate shift [17 $4). domain adaptation (36), geographically weighted regression
77. local interpretable
explanations 31. to name few.
In all of the aforementioned applications, prevailing trait is that the weight is given through kernel. To avoid any confusion in the terminologies, is instructive to revisit and distinguish the relevant definitions of kernels. The first family is the non-negative kernels, which are popularly employed in nonparametric statistics (37]
Definition 1.3 (Non-negatio negative kernel). A function K Z 2 > R is non-negative if K(z, 2') 2 0 for any 2, z' E 2.
In addition, there also exists family of positive definite kernll,, which forms the backbone of kernel machine learning 33).
Definition 1.4 (Positive definite kernel). A symmetric function K Z Z R is positive definite for any n E N and any choices of (2 (= E Z and (ai)i= E R, we have
ΣΣ a.a ((n,)(2))))) 20.
(2)
Moreover, is stricily positive definite if we have in addition that for mutually distinct (2)) E Z, the equality in (2) implies 01 =.. an
0.
Positive definite kernels are powerful tool to model geographical interactions (7]. to characterize the
covariance structure in Gaussian processes [29 $4], and to construct non-linear kernel methods [33] Interestingly, the two above- mentioned families of kernels have significant overlap. Examples of kernels that are both non-negative and strictly positive definite include the Gaussian kernel with bandwidth h >> 0 defined for any z, z' E Z as
K(2, z') = exp( - - ='112/12)
the Laplacian kernel, the Cauchy kernel, the Matérn kernel, the rational quadratic kernel, etc.
It is well-known that the non- parametric statistical estimator obtained by solving (I is sensitive to the corruptions of the training data (9] 21 28). Similar phenomenon is also observed in machine learning where the solution of the risk minimization problem (I) is not guaranteed to be robust or generalizable if the training sample size N is small. Reweighting, obtained by modifying w (2),, is arising as an
[ 2 12
14 19 23
43). The quality of the solution to (I) also deteriorates
attractive resolution to improve robustness and enhance the out-of-sample performance in the test At the same time, reweighting schemes have shown to produce many favorable
data [30 34
40
effects: reweighting can increase fairness [15 20 38 and can also effectively handle covariate shift
10 17

---

While reweighting has been successfully applied to the empirical risk minimization regime in which the weights are uniformly 1/N, reweighting the samples when the weighting function w is tied to a kernel is not trivial task. In fact, the kernel captures inherently the relative positions of the relevant covariates and any reweighting scheme should also reflect these relationship in global viewpoint. Another difficulty also arises due to the lack of convexity or concavity, which prohibits
the modifications of the kernel parameters. For example, the mapping h cxp( || 2 /h²) for the Gaussian kernel is neither convex nor concave if & * z'. Thus, is highly challenging to optimize over h in the bandwidth parameter space. Alternatively, modifying the covariates (2 will also result in reweighting effects. Nevertheless, optimizing over the covariates is intractable for sophisticated kernels such as the Matérn kernel.
Contributions. This paper relies fundamentally on an observation that the Gram matrix of non- negative, (strictly) positive definite kernel is a non-negative, positive (semi)definit (also known as doubly non-negative) matrix. It is thus natural to modify the weights by modifying the corresponding matrix parametrization in appropriate manner. Our contributions in this paper are two-fold:
We propose novel scheme for reweighting using a reparametrization of the sample weights doubly non-nege -egatiev matrix. The estimate is characterized as the solution to a min-max max optimization problem, in which the admissible values of the weights are obtained through a projection of an uncertainty set from the matrix space.
We report in-depth analysis on two reweighting approaches based on the construction of the matrix uncertainty set with the log-determinant divergence and the Exploiting strong duality, we show that the worst-case loss function and its gradient can be efficiently evaluated by solving the univariate dual problems. Consequently, the adversarially reweighted estimate can be found efficiently using first-order methods.
distance.
Organization of the paper. Section 2 introduces our generic framework reweighting using doubly non-negative matrices. Sections 3 and study two distinctive ways to customize reweighting framework using the log-determinant divergence and the Bures Wassersenn distance. Section 5 empirically illustrates that reweighting strategy delivers promising results in the conditional expectation task based on numerous real life datasets. We have released code for these proposed tool?3
Notations. The identity matrix is denoted by I. For any AE RPXP, Tr [A] denotes the trace A, A Z 0 means that all entries of A are nonnegative. Let Sh denote the vector space of p-by-p real and symmetric matrices. The set of positive (semi- (semi-)definite Jdefinite matrices is denoted by S (respectively, S For any A, B E IRPx,, we use (A, B) = Tr [A B) to denote the Frobenius inner product between and B, and ||l|| to denote the Euclidean norm of e E IRP.
2 A Reweighting Framework with Doubly Non-negative Matrices
We delineate in this section reweighting framework using doubly non-negative matrices. This framework relies on the following observation: we can reparametrize the weights in ( into a matrix Ω and the loss terms in (T into matrix (g), and the solution to the estimation problem ( can be equivalently characterized the minimizer of the problem
min (())).
(3)
Notice that there may exist multiple equivalent reparametrizattions of the form 3 However, in this paper, we focus on one specific parametrization where Ω the nominal matrix of weights
Koo noo
Nox Ωi
N+1
:
a
httppp///ggtaabbco/////at/aaaara Regressiin

---

with the elements being given by the weighting function w as Zox = 64w = w(2,) for i = 1,...,., NN,
and the valuud mapping V
((3) E =NN+1 satisfies
0
(13.21.01
2(3, NNNN)
((,,
0
V(3)=
Le (N,,
simple calculation reveals that the objective function of (3) equivalent to that of positive constant factor of 2. As a consequence, their solutions coincide.
① up to
Problem 3 is overparametrized reformulation of the weighted risk minimization problem ① Indeed, the objective function of problem (3) involves an inner product of two symmetric matrices, while problem ① can be potentially reformulated using an inner product of two vectors. While lifting the problem to the matrix space is not necessarily the most efficient approach, it endows us with more flexibility perturb the weights in a coherent manner. This flexibility comes from the following two observations: (i) there may exist multiple matrices that can be used as the nominal matrix f2 and one can potentially choose Ω to improve the quality of the estimator, (ii) the geometry of the space of positive (semi)definite matrices is richer than the space of vectors.
To proceed, we need to make the following assumption.
Assumption 2.1 (Regularity conditions). The following assumptions hold throughoud the paper.
(i) The function is nonnegative, and , y) is convex, continuously differentiable for any (x, v)- (ii) The nominal weighting matrix Ω is symmetric positive definite and nonnegative.
In this paper, we propose to find an estimate 3* that solves the following adversarially reweighted estimation problem
min
((3)
for some set (f)) of feasible weighting matrices. The estimate 3 thus minimizes the worst-case loss uniformly over all possible perturbations of the weight Ω E (Q)). In particular, we explore the construction of the uncertainty set (f)) that motivated by the Gram matrix obtained via some non negative and positive definite kernels. In this way, the weighting matrix capture more information on the pair-wis wise relation among training data. Hence, it is reasonable to consider the set (f2) of the form
(p) & { ( :220 ((2, sp].
(5)
By definition, any Ω E (S2) is symmetric, positive semidefinite matrix and all elements of Ω are nonnegative. A matrix with these properties is called doubly nonnegative. From a high level perspective, the set (f?) is defined as ball of radius centered at the nominal matrix Ω and this ball is prescribed by a pre-determined measure of dissimilarity s. Throughout this paper, we prescribe the uncertainty set (f2) using some divergence yp on the space of symmetric, positive semidefinite matrices S
Definition 2.2 (Divergence). For any N E N, y a divergence on the symmetric positive semidefinite matrix space N+1 if it is: (i) non-negative: (((21, 2 0 for all Q1, l22 E S and (ii) indiscernable: if (02, 12) = 0 then Q2 U2z-
we denote the adversarially reweighted loss function associated with Up ( by
(F) A max (2,
(EU,,.(0))
then 3 can be equivalently rewritten as
g* = arg min F (B).
(6)
3

---

A direct consequence is that the function F Fe,p is convex in 3 as long as the loss function satisfies the convex property of Assumption [ Hence, the estimate 3 can be found efficiently using convex optimization provided that the function gg and its gradient can be efficiently evaluated. Moreover,
because şp is divergence, ( {[]] Hence by setting p O, will recover the nominal estimate that solves ( In Section Faadd 4 we will subsequently specify two possible choices of op that lead to the desired efficiency computing F..o as well as its gradient. Further discussion on Assumption 2. is relegated to the appendix. We close this section by discussing the robustness effects of our weighting scheme + on the conditional expectation estimation problem.
Remark 2.3 (Connection distributionally robust optimization). Consider the conditional expec- tation estimation setting, in which E = zo] is the solution of the minimum mean square error estimation problem
B 2 =0] arg min IE 2 zo].
In this setting, our reweighting scheme coincides with the following distributionally robust optimization problem
min
Qy Z (B Eor1z- [18-118800 y)3},
max
with the nominal conditional distribution defined as Pyizz=o (dy) x Ei= K(zo, 2,)0g, The ambiguity set (( is a set of conditional probability measures of YIZ = 20 constructed specifically as
B(PY Qri2=00 : Qr1z=zo (dy) x Ein
30 E ( so that Sls = =Ω,0 = w(2,) iimt ((2))gg (dy)
Remark 2.3 reveals that our reweighting scheme recovers a specific robustification with distributional ambiguity. This robustification relies on using kernel density estimate construct the nominal conditional distribution, and the weights of the samples are induced by Up Hence, our scheme is applicable for the emerging stream of robustifying conditional decisions, see
25 26).
Remark 2.4 (Choice of the nominal matrix). The performance of the estimate may depend on the
specific choice of the nominal matrix Zt. However, in this paper, we do not study this dependence in details. When the weights (2,)) are given by kernel, it is advised to choose Q as the Gram matrix.
3 Adversarial Reweighting Scheme using the Log-Determinant Divergence
We here study the adversarially reweighting scheme when the is the log-determinant divergence. Definition 3.1 (Log-determinant divergence). For any positive integer E N, the log de-termeemnnn divergence from Q2 3 f2 + amounts to
D 02) A Tr [8125'] - log det (R,52 - p.
The divergence D is the special instance of the log-determinant a-divergence with a S Being divergence, DD is non-negative and it vanishes to zero if and only if Ω Z2g It is important to notice that the divergence D is only well-defined when both 22 and 22 are positive definite. Moreover, ID is non-symmetric and D(L,, & D( Ω4) in general. The divergence D is also tightly connected to the Kullback-Leibe divergence between two Gaussian distributions, and that D(2, P2) (L(N((,, P1) (0, P2)), where NO0 Ω) is normal distribution with mean 0 and covariance matrix Ω.
Suppose that Ô is invertible. Define the uncertainty set
Up ( = { e S +1 : 2 0, D(2 s sp..
For any positive definite matrix Ω. the function TD .2) is convex, thus the set (D, is also convex. For this section, examine the following optimal value function
max (Ω, (()),,
5

---

which corresponds to the worst-case reweighted loss using the divergence D. The maximization problem (7) constitutes nonlinear, convex semidefinite program. Leveraging a strong duality argument, the next theorem asserts that the complexity of evaluating (3) is equivalent to the complexity of solving a univariate convex optimization problem.
Theorem 3.2 (Primal representation). For any f2 E S and E (0,+ the function FD.P convex. Moreover, for any 3 such that V(3) + 0, let let ny be the unique solution of the convex univariate optimization problem
inf -I
PP - log det(I 7 1 -1o0
(8)
then (B) = (S2", V(8)), where Ω = -
Moreover, the sym-
metric matrix S2" unique and doubly nonnegative.
Notice that the condition (B) o O is not restrictive; if (33) 0. then Assumption 2. ()) implies that the incumbent solution incurs zero loss with {(B, 3. Vi for all In this case, B is optimal and reweighting will produce no effect whatsoever. Intuitively, the infimum problem (8) is the dual counterpart of the supremum problem (7). The objective function of (8) is convex in the dual variable 7, and thus problem g can be efficiently solved using a gradient descent algorithm.
The gradient of FD,, is also easy to compute, asserted in the following lemma.
Lemma 3.3 (Gradient of FD..). The function Fr.,p is continuously differentiable at B with
(3)D = Σ (3,,,,,
i=1
where O2 is defined as in Theorem
3.2
using the parametrization
100 Nio
MON SiN
Di
Ω*
:
[i
The proof of Lemma 3.3 exploits Danskin's theorem and the fact that Ω is unique in Theorem 3.2
Minimizing FD., now achievable by applying -ottc--r-thr-rtt first-order methods.
Sketch of Proof of Theorem 3.2 The difficulty in deriving the dual formulation (8) lies in the non-negativity constraint Ω 2 O. In fact, this constraint imposes (N 1)(N + 2)/2 individual component-wise wise constraints, and as such, simply dualizing problem 7 using Lagrangian multiplier will entail large number of auxiliary variables. To overcome this difficulty, we consider the relaxed set (Q2) & {Ω SN+1, D(Q, Q) s p}. By definition, we have (f.) S (D)), and ($)) omits the nonnegativity requirement Ω 2 0. The set VD.,( is also more amenable to optimization thanks to the following proposition.
Proposition 3.4 (Properties of (ğ)). For any â e SN and p 2 0, the set VD. is convex and compact. Moreover. the support function of VD, satisfies
Vo, (1)) (T) (2)
sup (1)
Tr [SZ]]]
inf 720
pp - ? log det(( -
>i 1T
for any symmetric matrix T E N+1
Moreover, need the following lemma which asserts some useful properties of the matrix V
Lemma 3.5 (Properties of (3)). For any B, the matrix ((3) is symmetric, nonnegative, and it has only two non-zero eigenvalues of value = ((B, 2.).
The proof of Theorem 3.2 proceeds by first constructing tight upper bound for (D)
(()V inf pp- log det(( 1 - - (() (10)
(D) max (e)
-

---

where the inequality in [00) follows from the fact that ( C (Q), and the equality follows
from Proposition 3.4 Notice that V(3) has one nonnegative eigenvalue by virtue of Lemma 3.5
and thus the constraint 752 > ((3) already implies the condition y > O. Next, we argue that the optimizer !?" of problem (0) be constructed from the optimizer y of the infimum problem via
22 0 [1 (x*) (
The last step involves proving that S2 a nonnegative matrix, and hence Q E LDD (1).. As consequence, the inequality (TO) holds equality, which leads to the postulated result. The proof relegated to the Appendix.
Adversarial Reweighting Scheme using the Bures- Wasserstiin Type Divergence
In this section, we explore the construction the set of possible weighting matrices using the Bures- Wasserstein distance on the space of positive semidefinite matrices.
Definition 4.1 (Bures-Warl Wasserstein divergence). For any positive integer E N. the Bures- Wasserstein divergence between f2 S.. and f22 S4P amounts to
W(2 02g A Tr [2 92 - (023 $1.
For any positive semidefinite matrices Qi and f22, the value W(L, is equal to the square of the type-2 Wasserstein distance between two Gaussian distributions (0, f2) and (O, [22) [33. As a consequence, W is divergence: it is non-negative and indiscernable. However, W is not proper distance because it may violate the triangle inequality. Compared to the divergence D studied in Section [ the divergence W has several advantages it symmetric and is well-defined for all positive semidefinite matrices. This divergence has also been of interest in quantum information, statistics, and the theory of optimal transport.
Given the nominal weighting matrix Ω define the set of possible weighting matrices using the Bures- Wasserstein divergence W as
Uw ( A (N E NN+1 :Ω 22200 0, W(2, Ω2) S p).
Corresoondingy,, the worst-case loss function is
Fw,p(3)
max DEU
(()).
(1I)
Theorem 4.2 (Primal representation). For any Ω E NN and p E (0, (00) the function Fw convex. Moreover, for any 3 such that V(3) + 0, let 7 be the unique solution of the convex univariate optimization problem
inf +I=V(8)
Tr + (1)))
(12)
Moreover the Thanks to the uniqueness of Q² and Danskin's 's theorem, the gradient of Fw, is now by-product of Theorem 4.2
then ((3) = (2* V(3)). where Ω* =
symmetric malrix Ω unique and doubly nonnegative.
Lemma 4.3 (Gradient of Fw. The function Fw.p is continuously differentiable at B with
N
V (BF
Σ Pig 2
1=1
where Qi is defined as Theorem 4.2 usinn the similar parametrization
A first-order minimization algorithm can be used to find the robust estimate with respect to the loss function Fw,p- Notice that problem [22 is one-dimensional, and either bisection search or gradient descent subroutine can be employed solve (12 efficiently.
7

---

Sketch of Proof of Theorem 4.2
The proof of Theorem 4.2 follows similar line of argument as
the proof of Theorem 3.2 Consider the relaxed set Vw, ( A {I2 E + W(2,, (2) S p}. By
definition, Vw,p( (22) omits the nonnegativity requirement 2 0 and thus L4w, (ft) S Vw. (1t.. The
advantage of considering ( arises from the fact that the support function of the set (St) admits simple form [24] Proposition A.4].
Proposition 4.4 (Properties of Vw ( For any Ω s and p 2 0, the set VW.)( is convex and compact. Moreover, the support function Vw.p (9t) satisfies
8 Vo (1) (T) A sup
Tr [2T] = inf 7 - Tr + -6)
(())
2>0 -->T
The upper bound for Fe can be constructed as
Fw.p(3) -
max nEV (ft)
(2, = inf -I>V(0)
7(p (0-
(13)
where the inequality in (13) follows from the fact that (w. ( S (W,, and the equality follows from Proposition [4.4 In the second step, we argue that the optimizer O2 of problem [33 can be constructed from the optimizer 7- of the infimum problem via
Ω = (>"))" V(3) V(
The last step involves proving that 52" is nonnegative matrix by exploiting Lemma 3.5 and hence Ω E LDD. Thus, inequality (13 is tight, leading to the desired result.
Numerical Experiments on Real Data
We evaluate our adversarial reweighting schemes on the conditional expectation estimation task. To this end, we use the proposed reweighted scheme on the NW estimator of Example I.] The robustification using the log-determinant divergence and the Bures- Wasserstein divergence are denoted by NW-LLggeet and NW-BuresW, respectively. We compare our NW robust estimates against four popular baselines for estimating the conditional expectation: (i) the standard NW estimate in Example [.] with Gaussian kernel, (ii) the LLR estimate in Example I l.2 with Gaussian kemne" (iii) the intercepted 31 of estimate (i.e., only the first dimension of RL denoted as LLR-I, and (iv) the NW-Metric 227 which utilizes the Mahalanobis distance in the Gaussian kernel.
Datasets. We use real-world datasets: (i) abalone (Abalone), (ii) bank-32fh (Bank), (iii) cpu (CPU), (iv) kin40k (KIN), (v) elevators (Elevators), (vi) pol (POL), (vii) pumadyn32nm (PUMA), and (viii) slice (Slice) from the Delve datasets, the UCI datasets, the KEEL datasets and datasets in Noh et al. (27]. Due to space limitation, we report results on the first 4 datasets and relegate the remaining results to the Appendix. Datasets characteristics can also be found in the supplementary material.
Setup. For each dataset, we randomly split 1200 samples for training, 50 samples for val- idation choose the bandwith h of the Gaussian kernel, and 800 samples for test, More specially, we choose the squared bandwidth h²2 for the Gaussian kernel from a predefined set {10- {10-2:144 2:1::1144 2 x 10-2:1:4 5 10-2:1:41 For a tractable estimation, we follow the approach in Brunds- don et al. (7] and Silverman 335 to restrict the relevant samples to N nearest neighbors of each test sample 2, with N E {10, 20, 30,50) 50}. The range of the radius p has 4 different values PE (0.01, 1, 10}. Finally, the prediction error is measured by the root mean square error (RMSE),
B, where n, is the test sample size (i.e., n2 =00) and B, the conditional expectation estimate at the test sample 2;. We repeat the above procedure 10 times to obtain the average RMSE. All our experiments are run on commodity hardware.
i.c., RMSE- V n4 E."
Ideal case: no sample perturbation. We first study how different estimators perform when there is no perturbation in the training data. In this experiment, we set the nearest neighbor size to N= 50, and our reweighted estimators are obtained with the uncertainty size of 0=0.1.
We omit results of LLR in Figures and 2 for a better visualization. See the Appendix for detailed results.
8

---

Abalone
Bank
CPU
KIN
0.14
0.12
0.1
0.08
Avergg
0.4
0.06
0.24
035
BMW BNNeBuursW LNWW-LoDDe
Figure Average RMSE for ideal case with no perturbation.
Figure shows the average RMSE across the datasets. The NW-Metric estimator outperforms the standard NW, which agrees with the empirical observation in Noh et al. [27]. More importantly, we observe that adversarial reweighting schemes perform competitively against the baselines several datasets.
When training samples are perturbed. We next evaluate the estimation performances when (0.2N, 0.4,,, 0.6.N, 0.8N, N) nearest samples from the N training neighbors of each test sample perturbed. We specifically generate perturbations only in the response dimension by shifting y ky. where k is sampled uniformly from [1.8, 2.2]. We set N = 50 and p 0.1 as the experiment for the ideal case (no sample perturbation).
Abalone
Bank
CPU
KIN
Average RMSE
3.5
0.13
20
1.1
0.11
10
0.8
0.09
0AN 0.4N 0.8N
0.8N
1.0N
0.2N
0.4N 0.8
0.8N 1.0N
0.2 0.4N
0.6N 0.8N
1.0N
0.2N 0.4N 0.6N 0.8N
1.0N
+ NW + LLRY NW-Mettic + NWW-BureW + NWWLLgget
Figure 2: RMSE for varying perturbation levels т. Results are averaged over 10 independent replications, each contains 800 test samples.
Figure 2 shows the average RMSE for with varying perturbation level т. The performance of all baseline approaches severely deteriorate, while both NW-LogDet and NW-BuresW can alleviate the effect of data perturbation. Our adversarial reweighting schemes consistently outperform all baselines in all datasets for the perturbed training data, across all perturbations
We then evaluate the effects of the uncertainty size p and the nearest neighbor size on NW-Log and NW-BuresW.
Abalone
Bank
CPU
KIN
0.125
Avarage
1.85
0.5
0.115
15
0.8
0.17
12
0.7
2.75
0.002
0.01
0.1
10
0.11
0.1
10
0.01
0.1
10
0.1
0.1
NWW-BuresW
+ NWW-LogDe
Figure Average RMSE as function of the ambiguity size p. Errors at p indicate the performance of the vanilla NW estimator.
Effects of the uncertainty size In this experiment, we set the nearest neighbor size to N = 50, the perturbation r = N. Figure 3 illlutrates the effects of the uncertainty size p for the adversarial reweighting schemes. Errors at O indicate the performance of the vanilla NW estimator. We observe that the adversarial reweighting schemes perform well some certain p and when that p is increased more, the performances decrease. The uncertainty size plays an important role for the adversarial reweighting schemes in applications. Tuning P may consequently improve the performances of the adversarial reweighting schemes.

---

Effects of the nearest neighbor size N. In this experiment, we set the uncertainty size to 0.1.
Figure|sshnn shows the effects of the nearest neigh- bor size N for the adversarial reweighting schemes under varying perturbation 7 in the KIN dataset. We observe that the performances of the adversarial reweighting schemes with N E {20, 30) perform better than those with NE {10, 50}. Note that when N is increased, the computational cost is also increased (see Equation | and Figure [ Similar the cases of the uncertainty size p. tuning N may also help to improve performances of the adversarial reweighting schemes.
Ver-LogDr
MWW BuresW
0.22
0.03
0.04
0.04
0.00
0.50
[-N-10
NNd0
Figure 4: Effects of the nearest neighbor size N.
Under varying shifting w.r.t In this ex- periment, we set the nearest neighbor size to N = 50. Diguutraillssstttes the performances of NW-LogDet under varying shifting w.r.t. k in
0/7
Average
the KIN dataset. For the left plots of the Figures [] we set the uncertainty size to p= 0,1 when varying the perturbation We observe that the adversarial reweighting schemes provide differ- ent degrees of mitigation for the perturbation under varying shifting w.r.t. K. For the right plots of the Figures we set the perturbation to T= 0.2.V when varying the uncertainty size We observe that the reweighting schemes under varying shifting w.r.t. K have the same behaviors in Figure when we consider the effects of the uncertainty size p (i..., when K E 2.28. Similar results for NW-BuresW W are reported in the supplementary material.
0.00
0:00
Pw (1.3 1.7) Se. (1.0, 22.7 de 3.2
Figure 5: Effects of perturbation intensity for NW-LogDet estimate. Left plot: different pertur- bation т, right plot: different uncertainty size p.
Time consumption. In Figure we illus- trate the time consumption for the adversar- ial reweighting schemes under varying neigh- bor size N and uncertainty size p in the KIN dataset. The adversarial reweighting schemes averagely take about 10 seconds for their estima- tion. When N and/or p increases, the computa- tion of the adversarial reweighting schemes take longer. This is intuitive because the dimension of the weight matrix Ω scales quadratically in the neighbor size N. Bigger uncertainty size p implies larger feasible set Upp. (kp..(()) longer computing time to evaluate Pepp and its gradient.
NWV-LogDet
Nilk NWK-BureWWW
107
2,00
p00 -1
20-10
Figure 6: Effects of N on computational time.
(Ω),, which leads to
Concluding Remarks. We introduce two novel schemes for sample reweighting using matrix reparametrization. These two invariants are particularly attractive when the original weights are given through kernel functions. Note that the adversarial reweighting with Bures- Bures-Wasserse Wasserstein distance W can be generalized to cases where the nominal weighting matrix Ω singular, unlike the reweighting with the log- deg-deeerminant divergence D.
Remark 5.1 (Invariant under permutation). Our results hold under any simultaneous row and column permulation of the nominal weighting matrix Ωt and the mapping V(B). To see this, let P be any (N + 1)- dimeesssial permutation matrix, and let 2tp & P.P and Vp(3) & PV Then (S'", V(3)),
max nEUL. (Stp)
(S2, Vp(8))
where S is calculated as in Theorem 3.2 x = DD and as Theorem for W. The proof relies on the fact that P P PPT = that both D and W are permutation invariant (in the sense that ((0,, 22g) xp( PP,, PQ)PP), and that the inner product also permutation invariant. Similar results hold for the gradient information, and hence the optimal solution of 3 is preserved under row and column permutations of Ω and V VB)).
10

---

Acknowledgements. Material in this paper is based upon work supported by the Air Force Office of Scientific Research under award number FA9550-20-1-0397, Support gratefully acknowl- edged from NSF grants 1915967, 1820942, 1838676, Simons Foundation grant (#31 1995), JSPS KAKENHI grant 20K 19873, and MEXT KAKENHI grants 20H04243, 21H04874. We thank the anonymous referees for their constructive feedbacks that helped improve and clarify this paper.
References
[1] David Alvarez-Melis and Tommi S Jaakkola. On the robustness of interpretability methods. arXiv preprini arXiv: 1806.08049 2018.
[2] Dario Amodei, Sundaram Ananthanarayanan, Rishita Anubhai, Jingliang Bai, Eric Battenberg, Carl Case, Jared Casper, Bryan Catanzaro, Qiang Cheng, and Guoliang Chen. Deep speech
2 End-to-end speech recognition in English and Mandarin. In Proceedings of The 33rd
International Conference on Machine Learning. volume 48, pages 183-182, 2016.
[3] Christopher G Atkeson, Andrew W Moore, and Stefan Schaal. Locally weighted learning. Lazy Learning, pages 1 11-73, 1997.
[4] Christian Berg, Jens Peter Reus Christensen, and Paul Ressel. Harmonic Analysis on Semigroups: Theory of Positive Definite and Related Functions. Springer, 1984.
[5] Alain Berlinet and Christine Thomas-Agnan, Reproducing Kernel Hilbert Space in Probability and Statistics. Kluwer Academic Publishers, 2004.
[6] Léon Bottou and Vladimir Vapnik. Local learning algorithms. Neural Computation, 4(6):888-
900, 1992.
[7] Chris Brunsdon, Stewart Fotheringham, and Martin Charlton. Geographically weighted re- gression. Journal of the Royal Statistical Society: Series D (The Statisticianm, 47(3):431-433, 1998.
[8] Zeineb Chebbi and Maher Moakher. Means of Hermitian positive-definite matrices based the log-determinant a-divergence function. Linear Algebra and its Applications, 436(7):1872 1889, 2012.
[9] Simon Du Yining Wang, Sivaraman Balakrishnan, Pradeep Ravikumar, and Aarti Singh. Robust nonparametric regression under Huber's e-contamination model. arXiv preprint arXiv:1805.10400 2018.
[10] John C Duchi, Tatsunori Hashimoto, and Hongseok Namkoong. Distributionally robust losses against mixture covariate shifts. Under review, 2019.
[11] Adrián Esteban-Pérez and Juan M Morales. Distributionally robust stochastic programs with side information based on trimmings. arXiv preprint arXiv:2009, /0592, 2020.
[12] Amirata Ghorbani, Abubakar Abid, and James Zou. Interpretation of neural networks is fragile.
In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3681-3688, Jul. 2019.
[13] C.R. Givens and R.M. Shortt. class of Wasserstein metrics for probability distributions. The Michigan Mathematical Journal, 31(2):231-244 1984.
[14] Moritz Hardt, Eric Price, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems, volume 29, pages 3315-3323, 2016.
[15] Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness without demographics in repeated loss minimization. In International Conference on Machine Learning, pages 1929-1938, 2018
[16] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning. Springer, 2009.
[17] Weihua Hu, Gang Niu, Issei Sato, and Masashi Sugiyama. Does distributionally robust super- vised learning give robust classifiers? P Proceedings of the 35th International Conference on Machine Learning, 2018.
[18] Rohit Kannan, Güzin Bayraksan, and James R Luedtke, Residuals-based distributionally robust optimization with covariate information. arXiv preprint arXh::2012.01088 2020.
11

---

[19] JooSeuk Kim and Clayton D. Scott. Robust kernel density estimation. The Journal of Machine Learning Research, 13:2529-2560 2012.
[20] Preethi Lahoti, Alex Beutel, Jilin Chen, Flavien Prost Kang Lee, Nithum Thain, Xuezhi Wang, and Ed Chi. Fairness without demographics through adversarially reweighted learning. In Advances in Neural Information Processing Systems, 2020.
[21] Haoyang Liu and Chao Gao. Density estimation with contaminated data: Minimax rates and theory of adaptation. arXiv preprint arXiv: 171.00880vv3. 2017.
[22] Elizbar A Nadaraya. On estimating regression. Theory of Probability Its Applications, 91):1411-42, 1964.
[23] Hongseok Namkoong and John C Duchi. Variance-based regularization with convex objectives. In Advances in Neural Information Processing Systems 30, pages 2971-2980, 2017.
[24] Viet Anh Nguyen, S. Shafieezadeh-Abale Bayesian and minimax mean square eπтоr estimation via Wasserstein distributionally robust optimization. arXiv preprint 1910::1110.1583 2019.
D. Kuhn, and P. Mohajerin Esfahani. Bridging
[25] Viet Anh Nguyen, Fan Zhang, Jose Blanchet, Erick Delage, and Yinyu Ye. Distributionally ro- bust local non- non-maraettric conditional estimation. In Advances in Neural Information Processing Systems 33, 2020.
[26] Viet Anh Nguyen, Fan Zhang, Jose Blanchet, Erick Delage, and Yinyu Ye. Robustifying conditional portfolio decisions via optimal transport. arXiv preprint arXiv:2103. 16451, 2021.
[27] Yung-Kyun Noh, Masashi Sugiyama, Kee-Eung Kim, Frank Park, and Daniel Lee. Generative local metric learning for kernel regression. In Advances in Neural Information Processing Systems, pages 1452-2462 2017.
[28] Pranav Rajpurkar, Robin Jia, and Perey Liang, Know what you don't 't know: Unanswerable ques- tions for squad. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguisttcss, pages 184.789.220 2018
[29] Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning). The MIT Press, 2005.
[30] Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. In International Conference on Machine Learning, pages 4334-4343.
PMLR, 2018
[31] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "Why should trust you?" Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1135-1144, 2016
[32] David Ruppert and Matthew Wand. Multivariate locally weighted least squares regression. The Annals of Statistics, pages 1346-1370, 1994.
[33] Bernhard Scholkopf and Alexander Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. Adaptive Computation and Machine Learning series, 2018.
[34] Jun Shu, Qi Xie, Lixuan Yi, Qian Zhao, Sanping Zhou, Zongben Xu, and Deyu Meng. Meta- weight-net: Learning an explicit mapping for sample weighting. In Advances in Neural Information Processing Systems, volume 32. pages 1917-1928, 2019.
[35] Bernard W Silverman. Density Estimation for Statistics and Data Analysis. CRC Press, 1986.
[36] Masashi Sugiyama, Shinichi Nakajima, Hisashi Kashima, Paul Von Buenau, and Motoaki Kawanabe. Direct importance estimation with model selection and its application to covariate shift adaptation. In Advances in Neural Information Processing Systems, volume pages
1433-1440 1440,, 2007.
[37] Alexandre B Tsybakov. Introduction to Nonparametrie Estimation. Springer, 2008
[38] Serena Wang, Wenshuo Guo, Harikrishna Narasimhan, Andrew Cotter, Maya Gupta, and Michael I Jordan. Robust optimization for faimesss with noisy protected groups. In Advances in Neural Information Processing Systems, 2020.
[39] Geoffrey S Watson. Smooth regression analysis. Sankhya: The Indian Journal of Statistics, Series A, pages 359-372, 1964.
12

---

[40] Yifan Wu, Tianshu Ren, and Lidan Mu. Importance reweighting using adversaaiillcoollaoratiy training. In NIPS 2016 Workshop. 2016.
[41] Muhammad Bilal Zafar, Isabel Valera, Manuel Rodriguez, Krishna Gummadi, and Adrian Weller. From parity to preference-based notions of fairness in classification. In Advances in Neural Information Processing Systems, volume 30, pages 229-239, 2017.
[42] Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representa- tions. In Proceedings of the 30th International Conference on Machine Learning, volume 28, pages 325-333, 2013.
[43] Chongjie Zhang and Julie A Shah. Fairness in multi-agent sequential decision-making. In Advances Neural Information Processing Systems, volume 27, pages 2636-2644, 2014.
[44] Jingzhao Zhang, Aditya Menon, Andreas Veit, Srinadh Bhojanapalli, Sanjiv Kumar, and Suvrit Sra. Coping with label shift via distributionally robust optimisation. arXiv preprint arXiv:2010. 12230, 2020.
13


Reviews:
[{"review_id": "vZZUyfpmuip", "reviewer": "Reviewer_rsLw", "summary": "$\\textbf{Summary and main contributions:}$\n\nThis paper aims to improve the performance of the weighted regression model in the scenario where data samples are under covariate perturbations. The main contributions are summarized below:\n\n(1) The authors propose to use doubly nonnegative matrices to reparameterize the sample weights in the kernel-reweighted regression model.\n\n(2) For the set of feasible weighting matrices, in the view of Log-Determinant divergence and Bures-Wasserstein type divergence, the authors theoretically show that the proposed kernel-reweighted regression model with doubly nonnegative weighting matrices is efficiently solvable.\n\n(3) Extensive experiment results on several datasets demonstrate its effectiveness under certain levels of sample perturbation.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "$\\textbf{Clarity and originality:}$ the paper is well written. The proposed kernel-reweighted regression model with doubly nonnegative weighting matrices is a novel contribution.\n\n$\\textbf{Significance:}$ when trained with perturbed samples, NW-LogDet is clearly effective and outperforms other methods under varying perturbation levels and uncertainty size. It has also been shown that the adversarially reweighted estimate is solvable with first-order methods.\n\n$\\textbf{Additional comments and suggestions:}$\n\n(1) The motivation to the use of Log-Determinant divergence and Bures-Wasserstein type divergence is not intuitive. It would be better if the authors add additional explanations regarding the insights of these two divergences.\n\n(2) One weakness of the proposed method is that it is less effective in the setting when there is no perturbation. As depicted in Figure 1, NW-metric appears like a more competitive method. In practice, it is likely that we do not have the knowledge of perturbation level, as a result, always adopting the proposed method may not be a good choice.\n\n(3) In figure 2, it would be better if the authors remove  LLR so that the performance gap between all other four methods would be more clear.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations of the proposed method are not adequately discussed in the paper. Besides, it would be better if the authors explain more detailed differences between the proposed method and [1].\n\n$\\textbf{References:}$\n\n[1] Yung-Kyun Noh, Masashi Sugiyama, Kee-Eung Kim, Frank Park, and Daniel D Lee. Generative local metric learning for kernel regression. In Advances in Neural Information Processing 417 Systems, pages 2452–2462, 2017.\n\n--------------------------------$\\textbf{Post-rebuttal}$--------------------------------\n\nThanks the authors for the detailed explanations.  I raise my score from 6 to 7 for the following two reasons:\n\n1. Most of my concerns are well addressed. Although for my second additional comment, I still hold the view that the proposed method might be less effective in the setting when there is no perturbation or slight perturbation. This may be viewed as a potential (and acceptable) weakness since in real-world scenarios, we may not have access to the perturbation level. \n\n2. I didn't observe any crucial weaknesses from other reviewers' feedback that convince me to change my attitude from acceptance to rejection.\n\nBest\n\nReviewer rsLw", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": ">6 hours"}, "extra_text": {}}, {"review_id": "k5aK-mc4wGN", "reviewer": "Reviewer_DQfm", "summary": "This paper focuses on reweighting the training samples in training a weighted regression model. To ameliorate the pessimism on the model's predictive power from low sample sizes or covariate perturbations, this paper proposes a new scheme for kernel-reweighted regression, i.e., adversarial reweighting scheme, to reparameterizing sample weights via a doubly non-negative matrix. Both theoretical and empirical analysis and results are provided.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Pros:\n\n1. This paper is well organized.\n2. Clear definition of the problem and related definition is provided, which allows an easy understand.\n3. The proposed adversarial reweighting framework is of significance for kernel-reweighted regression.\n4. Extensive experimental results and analysis on multiple real-world datasets are provided, which confirm the effectiveness and provide useful information about the proposed method.\n\nCons:\n\n1. It seems to be a little bit confused that \"While lifting the problem to the matrix space is not necessarily the most efficient approach, it endows us with more flexibility to perturb the weights in a coherent manner.\" (line 112 - 113). Could the author give a more intuitive explanation about why it needs to perturb the weights and why it is more flexible?\n2. It is a little bit unclear about why it needs to be formulated into a min-max optimization problem. Could the author give more discussion about the motivation in the earlier part of this paper?\n3. Lack of some intuitive explanation about how to address the potential problem results from low sample sizes or covariate perturbations. It may be better to add some discussion with the related properties in Sections. 3 or 4.\n\nMinor question:\n\n1. How to get the value of the perturbation intensity $\\kappa$? \n\n\n------Post-Rebuttal------\n\nThanks the authors for the detailed explanations.  After reading the author's response and other reviewers' comments, I think most of my concerns are well addressed. I decide to raise my score from 6 to 7.\n\nBest,\n\nReviewer DQfm", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no foreseeable negative societal impacts.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "S6BlbH1VzzQ", "reviewer": "Reviewer_rPg1", "summary": "The paper attempts an important problem of learning a regression model in the presence of adversarial perturbation. The paper formulates a general class of problems and proposes a solution for that. Finally, experimental results are also provided. \n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Overall, the paper seems to be technically good. The necessary technical analysis is provided. However, it could be simplified further to make it readable to a wider range of readers. For example, Eq. 1 and associated text lack enough clarity without a context which is more widely known. Introduction of z and parametrizing the weights with that can be a bottleneck for many readers. Description in simple words or simpler examples will improve the paper.  Similar comments hold for motivation of the problem and intuition of the method. A precise problem definition comes much later than too much technical nitty gritty. Otherwise, the technical quality is sound and significant. \n\nFormulation of reweighting in terms of non-negative matrices is interesting and could make it possible to derive analytical results which were otherwise difficult. This part of the paper is original. However, connecting to standard perturbation techniques such as differential privacy could make the paper more interesting to read and connect to the privacy community as well. \n\nQuality of the paper is limited to the technical analysis but can be adequate. The biggest drawback of the paper is lack of clarity which is discussed above. \n========================\nI thank author for their answer to my comment. I shall go with my previous score hope author will simplify the introduction as promised.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not discuss this aspect of the paper. However, I think they can connect their work to privacy as I suggested above and in turn can be connected to the privacy aspect of society and AI.", "review_text": "", "extra_scores": {"ethical_concerns": "I think there is no risk of ethical concerns in this paper. \n", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "NXRGAU-e9lZ", "reviewer": "Reviewer_sDqY", "summary": "This proposes a new method for kernel-reweighted regression by reparametrizing the sample weights using a doubly non-negative matrix. When the weighting matrix is confined in an uncertainty set using either the log-determinant divergence or the Bures Wasserstein distance (defined on psd matrices), it is shown that that the adversarially reweighted estimate can be solved efficiently using first-order methods. Some experiments are presented.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strengths\n---\n- Paper is well-written and easy to follow.\n- The reduction of the adversarial problem to a much simpler one-dimensional problem is appealing\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Weak points\n---\n- Work seems very incremental, and the contributions don't appear to be sufficient for publication at a conference like NeurIPS.\n\n- Experiments are not inclusive. All what the experiments seem to show is that LLR (local linear regression) is much worst than the other estimators (see Figure 1). For example, the experiments don't even show that NW-LogDet / NW-BuresW are any better than plane NW. So the question then is what is the advantage, theoretical or algorithmic, of the proposed estimators.\n\n- Missing statistical analysis of the resulting estimator.\n\n- There is a large body of work on distributional robust optimization out there. This work fits into that space, but unfortunately, the authors make no links.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "1ikR3K5gUTT", "reviewer": "Reviewer_cyV5", "summary": "This paper proposes a novel methodology for constructing robust estimates for kernel regression. This method works for methods that can be cast as locally-reweighted regression problems, such as the Nadaraya-Watson estimator and local polynomial regression in general. The methodology consists of viewing the traditional optimization objective as a vector inner product and then lifting to a matrix inner product. One can then define uncertainty sets (in the optimization sense) over which we would like to minimize the maximum of a matrix inner product using matrix divergences such as the log-determinant divergence and the Bures-Wasserstein distance. The paper then shows that it is possible to efficiently solve these problems.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Overall, I like this paper in a lot of ways. The new optimization problem is interesting in its own right. The fact that there are some matrix divergences for which the problem may be solved is also interesting, and it looks like some non-trivial effort goes into these proofs. The paper is also fairly clear and easy to read.\n\n\n------Post-Rebuttal------\n\nI've changed my mind about this paper. I've mostly changed my mind because (a) I don't believe any other reviewers have brought up any major concerns and (b) I feel that this is a fairly creative paper.\n\nI am disappointed that the authors seem unable to justify the proposed approach formally, but perhaps this was partly my error in communicating my concern. Let me try again. I tried to draw a diagram, and it didn't work with the markdown, so I'll try to describe it.\n\nThe essential idea is somewhat like a commutative diagram. Imagine a square, with the left top vertex A, right top vertex B, left bottom vertex A', and right bottom vertex B'. A is the original nonparametric regression problem (say, minimizing the MSE). B is the matrix version of the problem, which is essentially the same. B' is the robust matrix version of this problem proposed in this paper, and it is not directly related to the nonparametric regression problem A. A' is (if it exists) some robust type of nonparametric regression problem. It is related to A because it is the robust version, and it is related to B' because B' is the corresponding problem in the matrix space. Does A' exist? If so, what is it? The proposed solutions to B' should solve the (statistical) problem A'.\n\nI think we should be open to accepting this paper because it may lead to interesting connections (A, A') and (A', B'), and there's room to explore here. Most borderline papers do not present this upside. Sure it may be forgotten as a dead end in a year or two, but that's most NeurIPS papers anyways.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "On the other hand, I feel like there are some big unanswered questions. Why should we care about this particular formulation. Does this correspond to anything meaningful for a nonparametric regression problem? I know there are some short discussions on the particular divergences as related to normal random variables, but I don’t really understand what this is doing for my regression problem and why I should use it.\n\nOther issues that are more technical in nature get magnified by the fact that I don’t know what this robustification means for my regression problem. In Section 2, line 105, the discussion on the values of $\\hat{\\Omega}$ is somewhat limited. On a first read of the paper, I thought the unspecified entries were 0, which would make the matrix positive semi-definite and therefore incompatible with the log-determinant divergence robustness. On taking another look, it became clear that one can pick the other entries of the matrix so as to make it positive semi-definite. But, almost certainly this choice is not unique. So, again, what does it do to my nonparametric regression problem to choose different matrices $\\hat{\\Omega}$?\n\nA much more complete analysis of this problem would relate the proposed approaches to the regression problem. The rest of the paper is strong enough to be a clear accept if it had this as well. \n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes ways to robustify estimates for kernel-weighted regression. Most of the reviewers agree that the paper is technically sound and that it has the potential for interesting follow-up work, but there were concerns raised about the clarity and motivation, and absence of concrete connections between the robust reformulated problem and the original estimation problem. Having gone through the paper, I concur with the reviewers on the exposition issues pointed out, but agree that the paper should be accepted.

We strongly urge the authors to work on improving the exposition of the paper in the final version, and in particular:
- improve the motivation and description of the problem in the introduction
- and more importantly, have a discussion on the connections between the matrix re-parametrized robust problem (B' in Reviewer cyV5's comments) and the original estimation problem (A and A').

I thank the authors for engaging in an elaborate discussion with Reviewer cyV5. My reading is that there are two aspects that are unclear: (i) the choice of the uncertainty set and what it means for the original problem A, and (ii) if the resulting robust problem A' has connections to existing robustification schemes in the literature. I think the answer to the latter is "no", and it would be good to explicitly state this in the paper. One way to bring out of these nuances is by working out an end-to-end example (e.g. using the Nadaraya-Watson estimator), similar to what was presented in the rebuttal, but I leave it to authors to decide the best way to address the issues raised.

It's after much deliberation that we've decided to accept the paper. We've decided to give the author's the benefit of the doubt, and trust that they would bring out the same clarity in the paper as they did in the author response.
Decision: Accept (Poster)