Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the following problem: Given a labeled dataset, a parameter $K$, and $K$ model architectures, we want to partition the data into $K$ partitions and also learn all the parameters for each model corresponding to the partitions. To help understand the problem and compare their approach, I will discuss a simple baseline they use in their paper.

Given a labeled dataset, first run $k$-means++ using only the features (ignoring the labels) to form the $K$ partitions, then independently train a model for each of the partitions (now also using the labels). Note that in this approach, we have completely ignored the labels in the data-partitioning step. What this paper does is to instead also incorporate the labels and simultaneously learn the model parameters and the data-partitions.
strength_and_weaknesses: Strengths: Interesting paper which is overall well-written and studies a significant problem. Such algorithms can be useful when there is a large dataset, which was potentially generated from heterogeneous data-sources.

Weaknesses: 
Although the problem studied by the paper is interesting, the algorithm they provide (PRESTO) is a bit complicated. Some of the simpler baselines (like the k-means++ based approach) give performance which is pretty close to their approach. I am very skeptical if any practitioner would bother using their approach for the marginal improvement in utility compared to the simpler baselines. Also, can the authors comment on the time taken by their algorithm when compared to their baselines?

Although the paper provides a approximation bound (Theorem 4), I am skeptical if this is of any use in practice. More concretely, for some of the loss functions and the data-sets which the authors consider in the experiments, what is the value of this approximation factor?


clarity,_quality,_novelty_and_reproducibility: Clarity: The submission is clearly written and well-organized. I do have one qualm with the paper though. The algorithm discussed in the paper builds heavily on the some prior algorithms (Iyer et al, 2013 a;b, Durga et al. (2021)) but there is no intuition provided in the paper for either the majorization-minimization approach or the modular upper bound. It would be nice if you could add a paragraph or two briefly describing these things (appendix is also fine). I was not familiar with any of these works and it made it hard to follow the algorithm.

Quality: The submission is technically sound. All claims are well-supported with proofs and detailed experiments.

Novelty: I am not an expert in this area so I am not entirely sure about other related work. I have a question here, which I hope the authors can answer. Was the specific problem discussed in this paper studied by any other work? To additionally clarify, I was curious if even this baseline approach with $k$-means++ and learning a model for each partition was discussed in any prior work.

Reproducibility: Proofs are provided and also the code for experiments is available.

Typos/minor issues:

Page 2: “key rational” -> “key rationale”

Duplicate citations for the same paper: 

Soumyabrata Pal, Arya Mazumdar, Rajat Sen, and Avishek Ghosh. On learning mixture of linear regressions in the non-realizable setting. In International Conference on Machine Learning, pp. 17202–17220. PMLR, 2022a.
Soumyabrata Pal, Arya Mazumdar, Rajat Sen, and Avishek Ghosh. 

On learning mixture of linear regressions in the non-realizable setting. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 17202–17220. PMLR, 17–23 Jul 2022b. URL https://proceedings.mlr.press/ v162/pal22b.html.

Page 4, Section 2.3, K-Means Clustering: “turns out that $\theta_k = \mu_k$, and the cluster means and $\ell$…” -> “turns out that $\theta_k = \mu_k$, the cluster means, and $\ell$…”

Section 2.3 has repeated paragraph titles “Mixtures of SVMs and linear regressions” and “Mixture of Linear Regression”

Definition 1 on Page 5: “f is $\alpha$-submodular submodular”

Appendix A.1 (1) “..., then $T \subset I$” -> “..., then $S \in I$”
                        (2) “ If $S \subset I$ …” -> “If $S \in I$”

Theorem 2. $\underline{\ell}_{min}$ definition is a bit unclear. The underscript in min should be expanded and there should be a ] after $||\theta_k||^2$

(3) of Theorem 2: $\kappa_G(S) \leq \kappa_G^*$. Here, should $S$ be $\mathbb{S}$?

Just before equation (7): “optimal solution $\mathbb{S}^*$ Thus, the optimization (5) becomes” : Period missing between ‘$\mathbb{S}^*$’ and ‘Thus’

Algorithm 1 Line 2

Missing period at the end of Theorem 4.

summary_of_the_review: Overall interesting paper. I am currently leaning to accept but would be willing to increase my score after the author response.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a framework (called PRESTO) for simultaneously partitioning the data space and learning a separate model in each partition. The framework relies on solving an optimization problem with both discrete variables (data partitioning) and continuous parameters 
(model parameters) using a constrained optimization method.  
strength_and_weaknesses: Stength
 - An interesting problem formulation is presented.
 - Partitioning is obtained through explicit specification of the partitions without resorting to a clustering model.
 - Theoretical bounds are provided.
 - An approximate solution to the constrained optimization problem is proposed.

Weaknesses
  - Method presentation (section 3.2) and algorithm description are not clear, thus they are difficult to comprehend.
  - The method can not directly provide the partition assignments of new examples. Therefore an additional classification 
    model should be trained for the assignment task. 
  - Evaluation is insufficient: PRESTO is not compared to various methods belonging to the Mixture of Experts category.
  - Time complexity is not reported
clarity,_quality,_novelty_and_reproducibility: The paper proposes an interesting formulation and includes approximation results. 
However, it lacks in terms of clarity, especially in what concerns the 'outline of the PRESTO algorithm' (section 3.2) and the corresponding pseudocode (Algorithm 1).
In what concerns reproducibility, the authors provide the code of PRESTO along with details on the used datasets. 
summary_of_the_review: The paper proposes a framework (called PRESTO) for simultaneously partitioning the data space and learning a separate model in each partition. The framework relies on solving an optimization problem with both discrete variables (data partitioning) and continuous parameters (model parameters) using a constrained optimization method.

The idea is interesting and supported by theoretical results. 

However, there are several concerns regarding the manuscript:
1) I think that PRESTO resembles with the Mixture of Experts (MoE) family of methods. Nevertheless, the paper does not include any reference and comparison with MoE.
2) The authors compare only with the typical (trivial) case where partitioning is first obtained using clustering and then a separate model is trained on each partition. Even in this case, the results in Table 1 do not indicate any particular accuracy improvement.
4) The time complexity of the method should be specified and compared to the methods in Table 1. It should be noted that the method must run for various values of K in order for the best number of partitions to be determined through cross-validation.
5) I do not think that the method could be an efficient alternative for k-means of Bergman clustering as mentioned in section 2.3.
6) If mixture of SVMs is a special case, why not implementing PRESTO with SVMs as classifiers and compare with the original mixture of SVMs method?
7) In my opinion PRESTO does not perform mixture modeling. Mixture models are statistical models, PRESTO is a domain decomposition approach.
8) The intuition behind the a_G hyperparameter should be provided.
9) Does PRESTO algorithm converge? What is the role of the 'Iterations' parameter in Algorithm 1.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: When the observed data comes from a population that consists of several subpopulations, it is useful to model each subpopulation separately. Hence, the paper proposes a method that simultaneously learns a partition of the dataset so that each subset of the data comes from the same distribution. The model parameters and the partitions are learned simultaneouly, which is formulated as an optimization problem. One major contribution of the paper is to design a numerical algorithm. 
strength_and_weaknesses: **Strengths**
The paper is well written and can be easily followed. 

**Weakness**
1. One major concern of the reviewer is that the difference of the proposed method and mixture of linear regression is not highlighted.
- In Section 2.3, the authors mentioned that mixture of linear regression is a special case of theirs. If so, then why you get different results for these two methods in Table 1. 
- Can the authors please clatify what's the difference between the proposed approach and the general EM algorithm used in fitting mixture of regression models.

2. Numerical algorithm. An MM algorithm is proposed to minimize $G(\mathbb{S})$. The success of MM algorithm depends heavily on the majorization function, which the reviewer believe shoudl be $m_{\hat{\mathbb{S}}}^{G}[\mathbb{S}]$. However, the reviewer don't think $m_{\hat{\mathbb{S}}}^{G}[\mathbb{S}]$ majorizes $G(\mathbb{S})$ since the equality does not hold when $\mathbb{S}=\hat{\mathbb{S}}$. Can the author please clarify?

3. Experiment result. 
- Are the differences of different approaches in Table 1 significant?
- The k-means approaches does not use any information about label $y$ but still performs as good as the proposed method, can the authors give some justificaitons on why this is the case?


**Minor issues**

1. The definitions of monotonity and $\alpha$-submodular need to be double checked. The current version is not correct since the $f$ does not appear anywhere in the definition.
2. The definition of relizable and non-relizable is not clear.
3. The number of paritions is the same as the number of classes in the dataset, what happens if the number of partitions is overspecified or under specified?

clarity,_quality,_novelty_and_reproducibility: The paper is well written in general. The idea is novel though there are some claims need to be better explained or justified. The experiments seem to be reproducible based on the description in the paper.



summary_of_the_review: One major concern of the reviewer is that the difference of the proposed method and mixture of linear regression.  The paper is marginally below the acceptance threshold before the reviewer's comments are clarified.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper introduces a novel data partitioning problem, where the goal is to partition a dataset into k groups so as to minimize a joint objective function that measures the loss of the best model on each group, and has a regularization term. This framework nominally contains many other well-studied problems, like clustering, mixtures of support vector machines and mixtures of linear regression. The main theoretical contribution is an algorithm which they show, for large enough values of the regularizing coefficient, achieves a bounded approximation ratio. This is achieved by connecting it to submodular optimization with bounded curvature subject to a matroid constraint. However the reviewers found the empirical results to be unconvincing. 
justification_for_why_not_higher_score: The empirical results are not very compelling. The algorithm is quite complicated and it achieves only modest improvements over much simpler baselines. The theoretical results do not tell a clean story, since the assumptions are quite strong and the approximation guarantees are quite large.
Decision: Reject