Synthetic Reduced Nearest Neighbor Model for Regression
Authors: Pooya Tavallali
Vahid Behzadan
Mukesh Singhal
Venue: ICLR 2022 Submitted (2022)
Keywords: Regression
Nearest Neighbor
Prototype Learning
Prototype Nearest Neighbor

Abstract: Nearest neighbor models are among the most established and accurate approaches to machine learning. In this paper, we investigate Synthetic Reduced Nearest Neighbor (SRNN) as a novel approach to regression tasks. Existing prototype nearest neighbor models are initialized by training a k-means model over each class. However, such initialization is only applicable to classification tasks. In this work, we propose a novel initialization and expectation maximization approach for enabling the application of SRNN to regression. The proposed initialization approach is based on applying the k-means algorithm on the target responses of samples to create various clusters of targets. This is proceeded by learning several centroids in the input space for each cluster found over the targets. Essentially, the initialization consists of finding target clusters and running k-means in the space of feature vectors for the corresponding target cluster. The optimization procedure consists of applying an expectation maximization approach similar to the k-means algorithm that optimizes the centroids in the input space. This algorithm is comprised of two steps: (1) The assignment step, where assignments of the samples to each centroid is found and the target response (i.e., prediction) of each centroid is determined; and (2) the update/centroid step, where each centroid is updated such that the loss function of the entire model is minimized. We will show that the centroid step operates over all samples via solving a weighted binary classification. However, the centroid step is NP-hard and no surrogate objective function exists for solving this problem. Therefore, a new surrogate is proposed to approximate the solution for the centroid step. Furthermore, we consider the consistency of the model, and show that the model is consistent under mild assumptions. The bias-variance relationship in this model is also discussed. We report the empirical evaluation of the proposed SRNN regression model in comparison to several state-of-the-art techniques.

Under review as a conference paper at ICLR 2022
SYNTHETIC REDUCED NEAREST NEIGHBOR MODEL FOR REGRESSION
Anonymous authors Paper under double-blind review
ABSTRACT
Nearest neighbor models are among the most established and accurate approaches to machine learning. In this paper, we investigate Synthetic Reduced Nearest Neighbor (SRNN) as a novel approach to regression tasks. Existing prototype nearest neighbor models are initialized by training a k-means model over each class. However, such initialization only applicable to classification tasks. In this work, we propose novel initialization and expectation maximization approach for enabling the application of SRNN to regression. The proposed initialization approach is based on applying the k-means algorithm the target responses of samples to create various clusters of targets. This is proceeded by learning several centroids in the input space for each cluster found over the targets. Essentially, the initialization consists of finding target clusters and running k-means in the space of feature vectors for the corresponding target cluster. The optimization procedure consists of applying an expectation maximization approach similar to the k-means algorithm that optimizes the centroids in the input space. This algorithm is com- prised of two steps: (1) The assignment step, where assignments of the samples to each centroid is found and the target response (i.e., prediction) of each centroid is determined; and (2) the update/centroid step, where each centroid is updated such that the loss function of the entire model minimized. We will show that the cen- troid step operates over all samples via solving weighted binary classification. However, the centroid step is NP-hard and no surrogate objective function exists for solving this problem. Therefore, new surrogate is proposed approximate the solution for the centroid step. Furthermore, we consider the consistency of the model, and show that the model is consistent under mild assumptions. The bias-variance relationship this model also discussed. We report the empiri- cal evaluation of the proposed SRNN regression model in comparison several state-of- of-th-rrtt techniques.
INTRODUCTION
One of the main topics of research in Machine Learning is the relation between the features and out- put responses(Haste Hastie et all (2099) Santosa & Symes/ (1986); Tibshirani (996);; Criminisi & Shotton (2013). Synthetic Reduced Nearest Neighbor (SRNN) models are shown to be an effective tool in determining the relationships between features of the inputs and the sub-clusters of each class in supervised learning tasks Tavallali et al. (2020b). However, existing prototype nearest neighbor models such SRNN are constrained to classification problems, and to the best of our knowledge, there remains a gap in extending these algorithms towards regression tasks. Such regression reduced nearest neighbor models may find extensive applications in epidemiological studies Tavallali et al. (2020a): Cisneros et al. (2021). medical studies Criminisi & Shotton (2013); Graf et al. (201 Ihla), and other applied regression tasks in general Tibshirani (1996). To address this gap in the state of the art, we propose novel algorithm for the optimization and construction of Regression Synthetic Reduced Nearest Neighbor (Reg-SRNN) models.
The proposed Reg-SRNN is capable of discovering various modalities of the input data, and relates those to the modalities of the output responses. The Reg-SRNN algorithm designed handle both single-re response and multi-response regression. The muuli--rsspone regression consists of learning the relation between input samples and several ground -trth output responses. Reg-SRNN partitions the input space into piecewise constant regions, where each region is represented by centroid and

---

Under review as a conference paper at ICLR 2022
its response. From this perspective, Reg-SRNN is similar to other piecewise constant models, such as Li & Martin (2017); Begon et all (2017); Bertsimas & Dumn (2017); 7): Tavallali et al. (2019; 2020c).. Reg-SRNN is capable of learning an accurate relation between each cluster of the data and its corresponding output responses. Therefore, Reg-SRNN can also provide enhanced interpretablity by reducing the information content of clusters into compressed representation manifested in their centroids.
The technical contributions of this paper include the proposal of novel initialization that by itself is competitive to other existing regression models. This is proceeded by an expectation maximization algorithm for directly minimizing the least squares eгror of the mode. The proposed optimization algorithm is provably convergent, and it is shown that it monotonically decreases the loss function. Therefore, the algorithm has a convergence guarantee on minimizing the loss function and achiev- ing local optimum.It is also worth mentioning that the algorithm does not cycle. The proposed optimization algorithm consists of two steps and inspired by K-means algorithm Lloyd (1982). One step is the assignment step and is composed of finding samples assignments and proper output response of the centroid. Second step is the update step where the centroid is optimized such that the loss function is decreased. The centroid step is affected by all the samples and we will show that this update step is a kind of NP-hard weighted binary classification problem. The update step is computed through surrogate objective function that is similar SVM. We establish that the algorithm is efficient because of its linear computational complexity. Finally, the model is evaluated on various datasets with various sizes and dimensionalities, the results of which demonstrate that Beg-SRRNIE is capable of competing and even over-matching similar regression models.
Accordingly, the main contributions of this paper are follows:
We propose novel algorithm for initialization of SRNN models to extend their application regression tasks.
We develop an optimization algorithm for regression SRNN models with guarantees on convergence.
Through experimental evaluation, we demonstrated the feasibility of our proposed regres- sion SRNN model in filling the gap between more complex models (such as random forests) and basic and interpretable models such linear regression and decision trees.
RELATED WORK
A regression task consists of learning the relation between samples of the input space and nu- merical output space. More specifically, regression is a supervised learning task of mapping inputs (independent variable X) to the output Y, which is continuous vector (Y IR... If the dimen- sionality of the output d 2 2, the task is known as multi-response regression. Regression has been the workhorse of numerous fields Tai (2021), and various regression models have been developed and expanded fundamentally over the recent decades Hastie et al. (2009). This expansion has been so rampant such that listing all such models and their relationships is a difficult task and out of the scope of this work. However, brief review of the recent models is presented in this paper. A common objective function for regression is to minimize the least squares error:
|| Y112
(1)
Where Y is the prediction. According to the Gauss-Markov theorem Gauss (823), the least squares eтror can be an unbiased linear model of minimum variance of the data under certain assumptions. Ordinary least squares may fail to properly predict outcomes if it is applied to settings where the Gauss-Markov assumptions are not held. Therefore, it is important to understand the assump- tions and occasionally apply the proper changes to the objective function of equation α to mod- ify the model (Tai (002)). Manifestations of such changes include imposing regulations or con- straints over the objective function. The literature on ordinary least squares estimation has exten- sively dealt with some of the well-known concerns that might violate the assumptions, such as Ridge Hoerl & Kennard (1970alb b). Lasso Tibshirani (1996). Elastic Net Zou & Hastie (2005), trees Quinlan (2014), forest Breiman (2001), boosting Bühlmann & Yu (2003) and others.
Common regression models include bagging, boosting, random forest Criminisi & Shotton (0013), oblique trees Murthy et al. (1994); Norouzi et al. (2015); Heath et al. 1993), and regression SVM
2

---

Under review as a conference paper at ICLR 2022
Drucker al. (1997). In the context of regression trees, various approaches of inducing a tree presented in the literature. Most decision tree induction methods are concentrated on the splitting criterion used at the growing phase of the tree Ikonomovska al. (201 1b: Levatić et all (2014). Ap- plication of decision tree algorithms to multi- multi-response regression has been previously considered in the literature Breiman et al. (1984); De' Ath (2002). In Breiman et all (1984); Quinlan (1986),
thors consider training a decision tree for each individual output response. However, such approach constructs large model specially if the number of output responses are high. Another approach pro- posed in De' Ath (2002) consists of constructing a single decision tree for all the output responses. In other words, the model predicts all the output values simultaneously through a single decision tree. However, model for all the outputs might not be sufficient Kocev et al. (2099) because they train model for single response rather than the true problem which is a multi-response regression. Au- thors in Kocev et all (2009) have explored two approaches to the multi-response regression problem by comparing learning a model for each output separately (i.c., multiple regression trees), and learn- ing one model for all outputs simultancously (i.c.. single multi-target regression tree). In order to improve predictive performance, Kocev et al (2013) has also considered two ensemble learn- ing techniques, namely, bagging [Breiman (1996); Liang et all (201 and random forests Breiman (2001) for regression trees and multi-target regression trees. The results showed that multi-target regression trees created more accurate and compact models.
related topic to the problem of this paper is nearest neighbor regression. Nearest neighbor re- well-established methods in the literature of ordinary univariate
gression and local estimators location estimators (Benedetti (1977): ; Stone (177);: Tukey et al. (1977). However, per our ex- tensive search, there remains gap prototype nearest neighbor approaches to regression. The only work that considered similar model and optimization to SRNN was Huang (2017). However, the proposed algorithm does not have guarantee of convergence or achieving some sort of optimum solution.
3 PROPOSED METHOD
3.1 PRELIMINARIES
Assume a dataset consisting of tuples (I; Ui) where 2, and i represent input features, output responses and index number. Each tuple represent data 2; and its corresponding output response y:- Here, I2 E RDD and yi E Rd. The Regression Synthetic Reduced Nearest Neighbor (Reg. SRNN) consists of K tuples of synthetically produced centroids/protooypes (cj, where e, úJ and j represent the centroid's 's point in the input space, output prediction and index. At the inference time, the Reg. SRNN operates like a nearest neighbor model where the centroids are used as the samples. The problem of training Reg. SRNN is as follows:
Σ ll 11;11 F1
min ((
(2)
s.t j argmin
d(x; - -(ÿ)
where d(.) is a distance metric. Through this paper we use 1-2 norm as the distance metric:
d(x; (j) = /
121l2
Essentially the prediction of the model consists of the output prediction of closest centroid to the input sample. Officially, define Reg. SRNN follows:
K
NN(x) Σ 11 E R2)
Where, N.)..) represents nearest neighbor function of the K centroids. I(.) is an indicator func- tion that produces if the input x is in the region of Ry. R, represents the region where the closest centroid to the points in that region eg.
3

---

Under review as a conference paper at ICLR 2022
3.2 INITIALIZATION
Numerical optimization algorithms require initialization (cite num opt). In this paper, we propose novel initialization for the regression SRNN. Previous work on the initialization of SRNN models consisted of learning K-means model for each class of the data. For example, in case of M classes and centroids, K. centroids are learned for each class as initialization of the SRNN Kusner al. .y (014);; Wang et all (2016) Zhong et all (2017); Tavallali et all (2020b). However, such approach is not applicable to the regression. This initialization also have close ties with naive Bayes and density estimation Silverman (2018). Here, we expand this initialization to the case of Reg. SRNN.
Intuitively, the output responses can consist of several modalities. In other words, is possible that the output responses are generated from several distributions. The clusters of such distributions can be approximated by running a K-means over the output space (M centroids). Assume that S represents the set of samples assigned to each output cluster. Next step consists of learning K.N. [S...
centroids over the imput features of the Sm for all M clusters. In other words, we learn centroids over the input features of each output cluster relative to the population of that cluster. The found centroids at the second step are used as initialization for the Reg. SRNN. At this step, új is found using the following formula:
ú mean(y, E S,)
(5)
where Sy represents the set of samples that assigned to jth centroid. Sy essentially consists of samples where jth centroid is the closest centroid to them. mean(.) represents the average of its input set. Note that Sj- E Rj.
3.3 CONSISTENCY
Here we discuss the consistency of the Reg. SRNN. We show that Reg. SRNN is a nonparametric and consistent under mild assumptions for continuous features. Assume an independent identically distributed (iid) dataset where it is being generated from f(x). f(x) represents the true function for relation between the inputs and outputs. Also assume that ((x) is piecewise constant function. Over a set of N observations, consistency of nonparametric estimator fx( (such as Reg. SRNN) is shown using the following formula Parzen (1962):
Pr( Tim N [ (N(()) f(x)) (x)))
(6)
The proof of consistency of Reg. SRNN is similar to proof of consistency for regression trees Breiman et al. (984) and density estimators in Ram & Gray 201
Theorem (Consistency of Reg. SRNN). The estimator defined in equation 4 satisfies equation equation 6
Proof. Assume B and d1 denote the collection of all sets f C X and fixed positive integer, respec- tively. Assume that describes the sets that are the solution to a system of d, inequalities 6 x I c where b E IRd and E R. Every region in the Reg. SRNN in formula equation 4 can be seen solution of a system of d1 inequalities of the form bT x < c where b is -ot-one-vector (only one element of b is 1 and the rest are 0). Therefore, Beg.SRNN C. B.
Assume random point Xn from function on X, (n Z 1). FN represents the empirical function learned by Reg. SRNN over X,, For 2 1, < n S N, and defined on set t C X by
Σ yn T(X, E t) mean(y, RR) -0 N
1
[.fx(oyde
Fx(t)=
where y/, fxx) and f(z) is the estimator presented in equation 4 Using a general version of Glivenko-Cantelli theorem Vapnik & Chervonenkis (2015)
Pr( lim sup) J. [(x)dol = 0) =
(8)
N N-
4

---

Under review as a conference paper at ICLR 2022
By replacing equation equation 7 in equation g have
J. fr(())d 1. [x)ddol N N
Pr( lim supl
then:
Pr( lim sup - [((N(E)) ( f(z)|dr 20) =1
(10)
Further, by assuming that the region of t leans toward 0 as N + 0o (Pr( lim J. dr = 0) 1). N
Rest of the steps will follow similar to theorem in Ram & Gray (201 and we get
[ - f(x))) de = 0) =
Pr( lim N-
(11)
Please note that the steps similarly done in Ram & Gray 2011 except the step of equation which is different.
K The consistency shows that as the number of samples go to infinity and [SIī SRNN is consistent. This is provable thanks the assumption that the true function that relates the inputs to the outputs is a piecewise constant function. This essentially means that the SRNN itself is consistent also for classification tasks.
O, then the Reg.
3.4 THE EXPECTATION MAXIMIZATION OF REG. SRNN
The problem equation represents the training problem of Reg. SRNN. SRNN generally is known as prototype nearest neighbor in other papers of literature and centroids are also called prototypes. Problem squation@rresmmlle K-means[Llod (1982) problem except that the loss function is | l/ll. The expectation maximization in this paper follows same approach as to K-means algorithm and the approach in Tavallali et al. (2000)). The optimization consists of two steps, assignment step and the update step.
3.4.1 ASSIGNMENT STEP
The assignment step consists of calculating assignment of the samples to each centroid and finding the optimum output prediction of each centroid. The problem of this step is as follows:
min (
Σ lly. 1i "1².
(12)
S.t
J argmin
d(z; - (G))-
(0
Note that problem equation 12 only tends optimize over úi for j 1...K. Using sets Sj, problem equation| 12 can be simplified to:
min (
Σ Σ
11 1l.
(13)
The problem equation can be separated (1((2))))
each centroid and its corresponding This be done since the regions are distinct and samples can not be shared among the regions. The prediction for each region is the label of jth centroid ûU (the centroid that represents the region). As result, the problem of optimizing label for each region is
min 35
Σ (1(())D)))))
11
13
(14)
whose minimum is presented in formula equation of response of samples in the Ry.
5 In other words, the optimum of ú is the mean
As result, in the assignment step, the Sj and ù have to be calculated for all the samples.
5

---

Under review as a conference paper at ICLR 2022
3.4.2 UPDATE STEP
The update step consists of updating the position of centroids such that the objective function in equation is minimized Llovd (1982). At this step the output prediction of the centroids are kept constant. The update step affected by all the samples in the dataset because by changing the position of centroid, the assignments of the samples can get changed and as result the prediction for each train sample gets changed. Further will be shown that finding optimum of the problem in this step is NP-hard. Therefore, the centroid problem is approximated through a novel surrogate objective function.
Each centroid is optimized individually Tavallali et all (2020b). The optimization problem for t centroid consists of moving the kt centroid such that the samples' assignment are changed in favor The centroid problem is
of decreasing the objective function equation 2
min Ck
Σ My
29'
(15)
S.t
J argmin
d(x; -c)-
Of
Note that the optimization is only ck- We rewrite the problem equation over the assignment of a sample to hdth centroid or to the rest of centroids. For simplicity we introduce the notation Tij d(æ; c)) The problem
N
Σ llu: - ux Urss: - rri) + 11y Ds; Uru - rrs)).
min 6
(16)
s.t
= argmin
d(z; - cG)-
( j
In problem equation I6 U() is step function where it outputs 1 if the input is larger than 0 and otherwise it will produce Note that the input arguments of the step functions are negative of each other. This means sample has to either get assigned to the ttth centroid or the rest of centroids. The sample can not get assigned to both terms equation The assignment 7th sample to each term will produce continuous error. This essentially means that the problem equation [6 is a weighted binary classification problem. The problem equation [6 encourage the sample to get assigned the side that produces lower error. For simplicity the set of samples that produce lower error if assigned to the C centroid and Sz, represents the set of other samples. let t; abs(llv: 0z 2
introduce the sets Se and S The Se, represents
11ys Ø5; (|²) where abs(.) returns the absolute value
of its input. The problem of equation [6 is equivalent to
min Σ
4U(ry; rix) +
Σ
4U(ra regt)
(17)
The problem D a NP-hard problem Nguven & Sanner 2013). Therefore, inspired by the SVM, we approximate the solution to problem equation 17 using the following surrogate objective function
problem[Neuven
(n) argmin
Σ trikk
Σ 2.
trrelllprag rrk)
(18)
R.ES.
where μ penalty coefficient. Intuitively, the surrogate objective function encourages the t centroid to stay close to samples of S. while staying away from samples of Sz. is increased from 0 to and along this path, the (1) that produces the smallest error for equation [7] is selected. This surrogate is a modified version surrogate objective function in Tavallali et all (2020h). The acts similar to slack variables in a SVM problem. The objective function of problem equation [T8] is a continuous function; thus, a local optimum of the problem can found using gradient-based algorithms.
3.5 RELATION TO EM ALGORITHM
The proposed algorithm is originally inspired by the EM algorithm used for K-means. The assign- ment step consists of finding the samples assigned each centroid and finding the optimal output

---

Under review as a conference paper at ICLR 2022
prediction of each centroid. The assignment of samples is the same as calculating the prior probabil- ities in an EM algorithm. Finding optimum output prediction of each centroid can also be considered part of maximization step.
In the update step, the centroids have to be updated. At this step, the outcome of assigning each sample to each centroid is evaluated (lvv: أاا -= =i 1, N). This evaluation is equivalent
to calculating the posterior probabilities. Then the centroid problem is approximated using these outcomes which is the maximization step.
3.6 RELATION OF SURROGATE TO SVM
The problem of finding the best centroid that closer to samples of S. than any other centroid can be cast feasibility problem.
find
CN:
s.t Tik < Top
Y(a, V:) E Se Tak Top Y(z, y:) E S4,
(19)
However, this feasibility problem is NP-hard since the the second set of constraints are concave Sahni (1974). These constraints make the problem different from similar SVM problems where the constraints are convex and global solution can be found in efficient time.
3.7 PROPERTIES OF THE ALGORITHM
computational complexity Optimizing the centroid problem takes O(ND) since it uses a gradi- based algorithm for solving the surrogate objective. All the K centroids have to optimized at each iteration. Therefore, the computational complexity of the algorithm is ((aNDK) where a is the number of iterations.
Convergence The convergence to a local optimum is similar to that of the K-means algorithm Lloyd ( Tavallali all (2020b). At each iteration, the error decreases and the objective func- tion is bounded by 0 from bellow. Further, the different combination of assignment of the samples the centroids is finite. Therefore, the algorithm stops after finite number of iterations.
EXPERIMENTAL RESULTS
In this section, the experimental results are presented to demonstrate the merits of proposed pro- posed algorithm. Various datasets are downloaded and used for evaluation from UCI repository Dheeru & Karra Taniskidou (011)). We partitioned the datasets using the following setups: 1- the dataset contained separate test set, the dataset was used provided in the repository. In case cross-validation was needed (for specific models) and validation set was not provided then the we partitioned the trainset to 80% train and 20% validation sets. 2- if the test set was provided partitioned the dataset to 80% train and 20% test set. For models that needed validationset, we di- vided the trainset 80% train and 20% validation set. 3- if all sets were provided by the repository, then the sets were used as provided. The setup for Reg. SRNN is as follows: at the initialization phase, used K for the output clusters for slice localization data and for the of datasets K was used for the output clusters. The number of input centroids used for each output cluster were proportional the population of each cluster. The centroid problem was optimized using batch stochastic gradient descent. We used various setups for each dataset to achieve the smallest possible train error.
Various models are used for comparison with Reg. SRNN. The basis of comparison is based on the number of base models used in each model. All the models comparable to the Reg. SRNN can be seen kind of ensemble model that consists of several base models. In case of forest and boosting, each tree base model. For prototype models such as Reg. SRNN and K-means, each centroid is base model. For Radial Basis Function (RBF) models, each RBF is considered as a base model. We also compared our model with linear regression and Ridge regression. The two models presented with straight lines. Figures [ and 2 present performance of each model
7

---

Under review as a conference paper at ICLR 2022
110
dlice Inckitalion dats
110
DPU
Aifel
0.30
030
0.50
030
293
30
49)
606
30
30
1301
0330
26
MI2
MIZ
20
20
15
0.51
20
10
030
40400 modida
40400 mooduts
42.000 mroduts
Figure Horizontal axis represents the number of base models(e.g. centroids, RBFs, trees and etc.). The vertical axis represents the mean squared error. The first and second row curves show the train errors and test errors, respectively. Reg. SRNN is compared with similar models.
over various datasets based on mean squared error versus number of base models. Reg. SRNN was compared with Random Forest (RF), K-means, Regression Boosting (reghoost), bagging, Radial Basis Function+ linear regression (RBF+lin-reg), linear regression (lin-reg), and ridge regression (ridgeCV), For the RE, each tree was trained using 70% of the trainset and 0.7 of features were randomly selected and used at the split nodes. For the K-means, K-means model with desired number of centroids were trained over trainset and the assignment step of Reg. SRNN was applied the model. For the regboost, we used trees of depth 3. For bagging, similar setup to RF was used except that no feature randomization is applied. RBF+lin-reg consists of first training RBFs (same number RBFs as the centroids other models) and the training linear regression over the outputs of RBFs. The width of RBFs were selected by cross- coss-validation. The penalty coefficient of ridgeCV was selected by cross-vais vross-validttion.
As can be observed from figures 1 and 2 the SRNN-Rey was able to achieve better comparable train and test errors to other models.
5 LIMITATIONS:
The model presented in this paper is new in the sense that it has never been proposed previously. However, since its nature is a nearest neighbor model we expect that the model presents some limi- tations similar to those of a nearest neighbor model. Similar nearest neighbor for regression that might have high test error in high dimensional datasets Hastie et al. (2009). Therefore, we suspect that the performance of Reg-SRNN might deteriorate with higher dimensional dataset. However, in our experiments, we noticed that the Reg-SRNN performed very well in slice localization data which is a high dimensional dataset (384 features).
6 CONCLUSION
In this paper, as per our search, we have proposed the first regression synthetic reduced nearest neighbor. The consistency of the algorithm was proved and its properties were explored. We showed that the algorithm is computationally efficient and can converge to local optimum in the sense than no move can improve the model any further. The approach is essentially the same type of EM algorithm used for K-means and it is extended for the case of regression synthetic reduced nearest neighbor. The update step was an NP-hard weighted binary classification problem. The optimum of such problems are typically approximated using surrogate objective function, such as hinge loss in SVM for 0-1 binary classification problem. Therefore, we approximated the solution to the update step through novel surrogate objective function. Further, we analyzed the relation of the update
8

---

Under review as a conference paper at ICLR 2022
train error
test eπrоr
1030
1030
278.00 PXdd55
118.00 moddds
Figure 2: Horizontal axis represents the number of base models(e.g., centroids, RBFs, trees and etc.). The vertical axis represents the mean squared error. Reg. SRNN is compared with similar models.
step with SVM. Experimentally, we showed that the Reg. SRNN performs better or competitive to other similar models in the literature such as ensembles and centroid based models.
7
REPRODUCIBILITY
The experiment codes (currently attached supplementary materials) will be published on Github repository to facilitate reproduction and extension our results. Furthermore, the datasets used in experiments are publicly available via the UCI repository.
REFERENCES
Jean-Michel Begon, Arnaud Joly, and Pierre Geurts. Globally induced forest: prepruning com- pression scheme. In International Conference on Machine Learning, pp. 420-428, 2017.
Jacqueline K Benedetti. On the nonparametric estimation of regression functions. Journal of the Royal Statistical Society: Series B (Methodological), 341
Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Leariing 106(7):1039- 1082, 2017.
Leo Breiman. Bagging predictors. Machine learning, 24(2):123-140, 1996.
Leo Breiman. Random forests. Machine learning, 45(1):5-32,
Lco Breiman, Jerome H. Friedman, A. Olshen, and Charles Stone. Classification and Re- gression Trees. Wadsworth, Belmont, Calif., 1984.
Peter Bühlmann and Bin Yu. Boosting with the loss: regression and classification. Journal of the American Statistical Association, 98(462):324-333) 2003.
Ricardo Cisneros, Hamed Gharibi, Marcela R Entwistle, Pooya Tavallali, Mukesh Singhal, and Donald Schweizer. Nitrogen dioxide and asthma emergency department visits in california, usa during cold season (november february) of 2005 to 2015: A time-stratified case-crossover analysis. Science of The Total Environment, 754:142089, 2021.
Antonio Criminisi and Jamie Shotton. Decision Forests for Computer Vision and Medical Image Analysis. Advances in Computer Vision and Pattern Recognition. Springer- Verlag, 2013.
Glenn De' Ath. Multivariate regression trees: new technique for modeling species-environnen relationships. Ecology, 83(4): 2002.
Dua Dheeru and Efi Karra Taniskidou. http://archive.. ics. uei eduuml
UCI machine learning repository, 2017.
URL
Harris Drucker, Chris JC Burges, Linda Kaufman, Alex Smola, Vladimir Vapnik, et al. Support vec- regression machines. Advances neural information processing systems, 9:155-161, 1997.

---

Under review as a conference paper at ICLR 2022
Carl Friedrich Gauss. Theoria combinationis observationum erroribus minimis obnoxiae, volume 2.
H. Dieterich, 1823.
Franz Graf, Hans-Peter Kriegel, Sebastian Pölsterl, Matthias Schubert, and Alexander Cavallaro. Position prediction et volume seans. In Proceedings of the 28th International Conference on Machine Learning (ICML) Workshop on Learning for Global Challenges, Bellevue, Washington, WA, 201
Franz Graf, Hans-Peter Kriegel, Matthias Schubert, Sebastian Pölsterl, and Alexander Cavallaro. 2d image registration et images using radial image descriptors. In International Conference on Medical Image Computing and Compuler-Assistel Intervention, pp. 607-614. Springer, 201 1b.
Trevor Hastie, Robert Tibshirani, and Jerome H. Friedman. The elements of statistical learning: data mining, inference, and prediction. New York, NY: Springer, second edition, 2009.
David Heath, Simon Kasif, and Steven Salzberg. Induction of oblique decision trees. In IJCAI, volume 1993, pp. 1002-1007, 1993.
Arthur E Hoerl and Robert W Kennard. Ridge regression: Biased estimation for nonorthogonal problems. Technometrics, 12(1):55-61 67, 1970a.
Arthur E Hoerl and Robert W Kennard. Ridge regression: applications to nonorthogonal problems. probbell Technometrics, 12(1))69-82, 1970b.
Hanwen Huang. Regression in heterogeneous problems. Statistica Sinica, pp. 71-88, 2017.
Elena Ikonomovska, João Gama, and Saão Džeroski. Incremental multi-target model trees for data streams. In Proceedings of the 201 ACM symposium on applied computing, pp. 988-993. ACM, 2011.
Dragi Kocev, Sašo Džeroski, Matt White, Graeme Newell, and Peter Griffioen. Using single-and multi-target regression trees and ensembles to model compound index of vegetation condition. Ecological Modelling, 220(8):1 159-1 1168, 2009.
Dragi Kocev, Celine Vens, Jan Struyf, and Saão Džeroski. Tree ensembles for predicting structured outputs. Pattern Recognition, 46(3):817-833, 2013.
Matt Kusner, Kusner,Stephen Tyree, Kilian Weinberger, and Kunal Agrawal. Stochastic neighbor compres- sion. In International Conference on Machine Learning, pp. 622-630, 2014.
Jurica Levatić, Michelangelo Ceci, Dragi Kocev, and Sašo Džeroski. Semi-supervised learning for malti-ta In International Workshop New Frontiers in Mining Complex Patterns, pp. 3-18. Springer, 2014.
Alexander Hanbo Li and Andrew Martin. Forest-type regression with general losses and robust forest. In International Conference on Machine Learning, pp. 2091-2100, 2017.
Guohua Liang, Xingquan Zhu, and Chengqi Zhang. An empirical study of bagging predictors for different learning algorithms. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 25, 2011.
Stuart Lloyd. Least squares quantization pem. IEEE transactions on information theory, 28(2): 129-137, 1982.
Sreerama Murthy, Simon Kasif, and Steven Salzberg. system for induction of oblique decision trees. Journal of artificial intelligence research, 2:1-32, 1994.
Tan Nguyen and Scott Sanner. Algorithms for direct 0-1 loss optimization in binary classification. In Interontional Conference on Machine Learning, pp. 1085-1093, 2013.
Mohammad Norouzi, Maxwell D Collins, David J Fleet, and Pushmeet Kohli. Co2 forest: Improved random forest by continuous optimization of oblique splits. arXiv preprint arXiv: 1XXv:1506.06755, 2015.
10

---

Under review as a conference paper at ICLR 2022
Emanuel Parzen. On estimation of probability density function and mode. The annals of mathe- matical statistics, 33(3):1065-1076, 1962.
J. Ross Quinlan. Induction of decision trees. Machine learning, 1(1):81-106, 1986.
J Ross Quinlan. C4. 5: programs for machine learning. Elsevier, 2014.
Parikshit Ram and Alexander G Gray. Density estimation trees. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 627-635. ACM, 2011.
Sartaj Sahni. Computationally related problems. SIAM Journal computing. 3(4):262-277) 1974.
Fadil Santosa and William W Symes. Linear inversion of band-limited reflection seismograms. SIAM Journal on Scientific and Statistical Computing, 7(4):1307-1330, 1986.
Bernard W Silverman, Density estimation for statistics and data analysis. Routledge, 2018.
Mervyn Stone. Cross-validator. choice and assessment of statistical predictions. Journal of the Royal Statistical Sociery: Series B (Methodological), 36(2))))))))))))1)) 36(2):111-33) 1974.
Yunpeng Tai. A survey of regression algorithms and connections with deep learning. arXiv preprint arXiv:2104. 12647, 2021.
Pooya Tavallali, Mehran Yazdi, and Mohammad Reza Khosravi. Robust cascaded skin detector based on adaboost. Multimedia Tools and Applications, 78(2):2599 2620, 2019.
Pooya Tavallali, Hamed Gharibi, Mukesh Singhal, Donald Schweizer, and Ricardo Cisneros. A multi-pollutant model: a method suitable for studying complex relationships environmental epidemiology. Air Quality, Atmosphere Health, 13:645-6575 2020a.
Pooya Tavallali, Peyman Tavallali, Mohammad Reza Khosravi, and Mukesh Singhal. Interpretable synthetic reduced nearest neighbor: An expectation maximization approach. In 2020 IEEE Inter- national Conference on Image Processing (ICIP), pp. 1921-1925. IEEE, 2020b.
Pooya Tavallali, Mehran Yazdi, and Mohammad Khosravi. A systematic training procedure for viola-jones face detector in heterogeneous computing architecture. Journal of Grid Computing, pp. 1-16, 2020c.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-22) 1996.
John W Tukey al. Exploratory data analysis, volume 2. Reading, Mass., 1977.
Vladimir N Vapnik and Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity, pp. 11-30. Springer, 2015.
Wenlin Wang, Changyou Chen, Wenlin Chen, Piyush Rai, and Lawrence Carin. Deep metric learn- ing with data summarization. Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 777-794. Springer, 2016.
Kai Zhong, Ruiqi Guo, Sanjiv Kumar, Bowei Yan, David Simcha, and Inderjit Dhillon. Fast classi- fication with binary prototypes. In Artificial Intelligence and Statistics, pp- 1255-1263, 2017.
Hui Zou and Trevor Hastie. Regularization and variable selection via the elastic net. Journal of the royal statistical society: series B (statistical methodology). 67(2):301-322 2005.
11


Reviews:
[{"review_id": "zQw3347AMH5", "reviewer": "Reviewer_j59H", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "[COMMENTS AFTER REBUTTAL]\n\nI have read the rebuttals from authors and reviews from other reviewers. However, I still think that this submission is below the standard I expect for an ICLR paper. Thanks.\n\n[END COMMENTS AFTER REBUTTAL]\n\n\n1. Strengths\n\nAs stated in Section 5, \"The model presented in this paper is new in the sense that it has never been proposed previously.\". In my opinion, the main contribution of this submission is to adapt Synthetic Reduced Nearest Neighbor (SRNN) for regression tasks, while the main contributions claimed in the last part of Section 1 only correspond to some necessary adaptions. SRNN is a traditional method proposed for classification task in 1972 [*], it is reasonable to adapt it for regression task.\n \n[*] Geoffrey W. Gates: The reduced nearest neighbor rule (Corresp.). IEEE Trans. Inf. Theory 18(3): 431-433 (1972)\n\n2. Weaknesses\n\n(1) Motivation: \n\nThe original SRNN is proposed mainly for decreasing memory and computation requirements with a possible drop in performance. However, this submission doesn’t mention such motivation or authors have other more reasonable explanations?\n\n\n(2) Technical details & Experiments: \n\n(a) In experiments, it is shown that the proposed Reg. SRNN achieves superior performance against compared baselines. However, as I mentioned above, SRNN aims at decreasing memory and computation requirements with a possible drop in performance.\n\n(b) The main experimental results are shown in Fig.1&Fig.2. However, in my opinion, it is weird to compare the performance w.r.t. the number of base models (e.g., centroids, RBFs, trees and etc.). For the proposed Reg. SRNN, the number of centroids is just a hyperparameter to be set, and the same to other baselines.\n\n(c) Authors can add the standard kNN model for regression task as a baseline.\n\n(d) Authors analyze the convergence in Subsection 3.7, it is better to illustrate the convergence curve in experiments.\n\n\n(3) Presentation quality: \n\n(a) The related work should pay more attention on SRNN model rather than some general regression techniques. Besides, this submission is very related to (Tavallali et al., 2020b), so authors can also discuss more about the method in this literature.\n\n(b) The citation style is incorrect.  \n\n(c) Section 5 can be merged into Section 6 or Section 1.\n\n(d) What's the difference between Fig.1 and Fig.2. Just different benchmark data sets? If so, they should be merged too.\n\n", "summary_of_the_paper": "The main contributions of this submission is to adapt Synthetic Reduced Nearest Neighbor (SRNN)  for regression tasks. Technical details and comparative studies are provided accordingly.", "summary_of_the_review": "From my perspective, the motivation is unclear, the experiments are weird and incomplete, and the presentation quality is poor. In summary, I think that this submission is below the standard I expect for an ICLR paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "gs3Q0fb-ZC", "reviewer": "Reviewer_rWNi", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "[COMMENTS AFTER REBUTTAL] \n\nI thank the authors for the rebuttal, I carefully took a look at it, as well as at the reviews of the other reviewers. However, I'm still convinced that it is not strong enough to get accepted in this conference \n\n[END COMMENTS AFTER REBUTTAL]\n\n\n\nStrengths:\n- the topic is relevant for ICLR\n- the idea is simple but potentially interesting\n- authors provide also a proof of consistency\n\nWeakness:\n\nW1. I’ve found the structure of the paper not completely clear. In particular I don’t completely understand the order of the subsections in Sect 3: for example, what section 3.2 refers to? Why putting “consistency” before the algorithm and not in the section “Properties of the algorithm” (last subsection)? In Section 3.1 I would also add the description of the SRNN for classification: the proposed approach is an extension of it, thus it would be beneficial to summarize it.\n\n\nW2. The section 2 “Related Work” contains a general introduction to the regression problem. I think this is too general, and not relevant for the paper. On the other hand, it does not contain the description of works which are more strictly related to the presented method, such as the general nearest neighbour strategies and especially the method in Huang (2017): these have been only cited at the end of the section. In particular I think it is fundamental to define the differences between the proposed approach and that of Huang (2017) – authors only reported a general sentence (“However, the proposed algorithm does not have guarantee of convergence or achieving some sort of optimum solution.”), without describing the algorithm and the idea. Finally, I suggest authors to clearly discuss the differences with the work of Tavallali et al 2020b, which has been cited in many different places inside the manuscript.\n\n\nW3. The authors use a K-means like strategy. Many methods in the literature used such generalized strategies, I think authors should at least acknowledge some of them. Moreover, it is clear from  such methods that the initialization is always an issue. How did authors solve it? With the procedure described in Section 3.2? If so, how did they initialize the k-means inside it? How many repetitions? Which is the impact of this procedure (also empirically)? \nPlease see also the discussion in:\n\nP Fränti, S Sieranoja: How much can k-means be improved by using better initialization and repeats? Pattern Recognition, 2019\n\n\n\nW4. How did author face the problem of determining the number of centroids K? How relevant is this choice? I suggest the authors to at least discuss this crucial issue\n\n\nW5. I think the experimental part can be largely improved. Here are some comments: \n1. Many important details are missing. For example: \n- Details on datasets: number and (at least) names of the datasets, characteristics in terms of number of features, number of objects, dimensions of training and testing sets (if any) and so on\n- Details on protocols: evaluation metric, details on Cross Val (e.g. how many repetitions of 80%/20%?)\n- Details on the proposed approach: initialization, number of iterations, different options investigated, impact on the performances and so on. For example,  authors used K=4 for one dataset and K=2 for the others: what if we change this value? How critical is this choice?\n- What is the meaning of “We used various setups for each dataset to achieve the smallest possible\ntrain error.”? Which setups? Is this behaviour fair? Please add a justification\n\n\n2. For what concerns the chosen competitors: instead of using these general methods, I suggest the authors to add a comparison with some of the original NN regression methods and with the method of Huang, which represents the most similar approach in the literature.\n\n3. Why authors consider the different clusters in their approach as “base models” (like trees in forests?)\n\n4. Plots reproduced in fig 1 are very difficult to read. Even zooming the pdf their presentation remains obscure (e.g. the colors of the different competitors are too similar)\n\n5. Comments on the results are missing: there is only one very general sentence (“As can be observed from figures 1, and 2, the SRNN-Reg was able to achieve better or comparable train and test errors to other models.”). Example of aspects which can be discussed are:\n+ how does the method work in the different datasets? Any relation with the different characteristics?\n+ which are the best competitors?\n+ why in some plots we only have 6 or 7 lines?\n+ why in some plots we have horizontal lines?\n\n", "summary_of_the_paper": "The paper presents a novel regression model based on Nearest Neighbor. In particular authors adapt the synthetic reduced NN model used for classification to the regression case. The main intuition is to simplify the regression problem by finding clusters of inputs and targets. Authors presents some theoretical properties of the method as well as few experimental results. ", "summary_of_the_review": "Potentially interesting paper with some problems in the presentation and in the experiments.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "RJp4QfPGaVf", "reviewer": "Reviewer_HzHJ", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This paper proposed a new initialization and EM approach to extend the synthetic reduced nearest neighbor model for regression problems. They have provided theoretical analysis to show the consistency of the proposed method under mild assumptions. Their experimental results show that the proposed method can achieve better or comparable results than existing methods. \n\nThe following are my concerns of this paper:\n(1) The novelty and contribution of this paper seem limited. The motivation of this paper is to extend the previous method SRNN for regression problems.  The proposed initialization and EM approach seem straightforward based on existing studies.  \n(2) Some important information is missing in the experiment part. “Various setups for each dataset to achieve the smallest possible train error” is kind of vague. Will the K value in the initialization step have a large influence on the final results?\n(3) In Figure 1, what is the difference between SRNN and SRNN0? Figure 1 ‘Slice localization data’ also shows that RF almost has the same curve as bagging. Is there any reason behind this behavior? How are the hyper-parameters tunned for the competing approaches? It mentioned that regboost used trees of depth 3. It would be better also to show the hyper-parameter tunning of the competing approaches. \n\nMinor:\nThe writing can be further improved.\na local optimum.It --> a local optimum. It\nSecond step --> The second step\nhot-one-vector --> one-hot vector \nequation (18) relu --> ReLU if it means the Rectified Linear Unit function. ", "summary_of_the_paper": "This paper proposed a new method to extend the synthetic reduced nearest neighbor model for regression problems. The idea of the proposed method is based on an initialization approach of creating clusters based on the target variable and an EM approach for minimizing the loss function of the proposed Reg. SRNN model. This paper provides an analysis of the consistency of the proposed method. The experiments results compared the proposed methods with several existing approaches. ", "summary_of_the_review": "Please refer to my main review. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "FZvNfGSl1Qd", "reviewer": "Reviewer_c48u", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The description of the results is far from optimal. The problem is the notation, insufficient explanation of main steps, misleading terminology and probably also the correctness:\n\n1) Update step (Section 3.4.2). The problem formulation (15) is clear, however, I didn't get trough the derivation of the approximate problem (18) which is actually used to fined the prototype. More specifically, I don't see the equivalence between the problem (16) and (17). Moreover I think the problems are not equivalent in general. Consider a simple example with two examples and two prototypes in 1D:\n- two examples: $x_1=-1,y_1=-1, x_2=1,y_2=1$\n- the second prototype $c_2=1, \\hat{y}_2-1$\n- output of the first prototype $\\hat{y}_1$\n\nThen, the minimization (16) w.r.t. $c_1$ is attained for $c_1$ such that $r_{12} < 2$. The minimization of (17) w.r.t. $c_1$ is attend for $c_1$ such that $r_{12} > 2$. Besides, the transition from (17) to (18) needs some justification.\n\n2) The consistency theorem. It is difficult to go through the proof and to understand it.\n- \"Assume a random point $X_n$ from function $f$ on $X$...\" What is a random point from a function?\n- What is the meaning of $R_t$ where $t$ is a subset of $X$ ?\n- What is a difference between $f(x)$, $\\hat{f}(x)$ and $\\hat{f}_N(x)$ ?\n\n3) Relation to EM algorithm (section 3.5). I find denoting the proposed optimization algorithm as the expectation-maximization approach misleading. The proposed approach and the EM algorithm are instance of block-coordinate descend like, K-means and many other methods. I do not see any other similarity worth mentioning or which would help to elucidate the problem.\n\n-----\nThe experiments are not reproducible and poorly described. First, it is not clear which UCI datasets were used and what are the main characteristics of the data (#examples, #dimensions, #outputs). Second, the competing methods are not referenced. Third, there is no discussion of the results at all.\n\n----\nMinor issues and typos:\n- The notation of the proposed method is no consistent: \"Reg-SRNN\" and \"Reg. SRNN\"\n- The equations are referenced by a number without brackets .\n- Equ (15): $\\hat{y}^*_j$ -> $\\hat{y}_{j^*_i}$\n- Equ (16) and (17): $\\min_{c_j}$ -> $\\min_{c_k}$\n- pp 6: \"...sets $S_c$ ...\" -> $S_{c_k}$\n", "summary_of_the_paper": "The paper proposes a novel algorithm for learning prototype based nearest neighbor regression model. The algorithm minimizes an average of the quadratic loss on training examples w.r.t. the prototype centers and the prototype outputs by a block coordinate descent. The main contribution is the optimization algorithm finding the prototypes.", "summary_of_the_review": "The paper is in a preliminary state. The explanation of the method is insufficient. The description of experiments lack important information.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: An algorithm for learning prototype based nearest neighbor regression model is presented. This algorithm minimizes an MSE on training examples w.r.t. the prototype centers and the prototype outputs by a block coordinate descent. The main contribution is the optimization algorithm finding the prototypes.
Major concerns in the reviews include missing mathematical rigor, poor description of the experiments, and unclear novelty. From my own reading I would like to add that the main theoretical contribution (Theorem 1) makes assumptions that are beyond any reasonable constraint, in particular as we know for more than 40 years, that such kind of assumptions are superfluous for many, many other algorithms.

In summary, a clear reject.
Decision: Reject