Imbalanced Mixed Linear Regression

Summary

The paper proposes a novel method for estimating parameters in a mixture of linear regression (MLR) model. The authors argue that the maximum likelihood estimator (MLE) does not perform well under extreme imbalanced cases and propose a sequential estimation approach using robust regression methods. The paper presents empirical results to demonstrate the effectiveness of the proposed method.

Strengths

- The proposed method offers an interesting alternative to the MLE in MLR. - The method is intuitive, and the paper is well-organized.

Weaknesses

- Notations and Terminology: There are instances where the notations or terminologies used in the paper are not well-defined. For example: - The term "significantly imbalanced" needs clarification. - Line 98: What is the definition of $n_{\text{info}}$? - Line 190: How is median error defined? Is it the median of $F_{\text{latent}}$ over 50 repetitions? If so, how is $F_{\text{latent}}$ defined for the overspecified case? - Method: While the intuition behind the proposed method is clear, there are several details lacking motivation or explanation. For instance: - What is the intuition behind equation (2b) and the weight in Phase II? How do they differ from directly running a median regression using IRLS? - What happens if no refinement in equation (5) is used? How does the estimator perform? - The method seems to rely heavily on hyperparameters such as $\rho$, $w_{\text{th}}$, $\eta$, and $T_1$. However, in Section 4, Line 73, it is claimed that "Mix-IRLS" performs well with a fixed set of values for the tuning parameters. It would be helpful to understand why the method is robust to the choice of hyperparameters. - Experiments: More detailed descriptions of the experiments should be provided to make the results more convincing. - What is the definition of "median error"? How are the initial values chosen? What does "highly imbalanced proportions" mean in Line 83? - It is well-known that fitting mixtures becomes harder when the components are closer to each other. How similar are the different components in the experiments? What happends if the degree of similarity increases? Are these methods stil perform the same? - As mentioned previously, the lack of a clear definition for "median error" makes the results difficult to interpret. - Instead of reporting the extreme failure probabilities, it would be better to report the mean squared error (MSE) of the regression estimator. Additionally, the performance of different estimators could be compared using this metric. - Theory: - Providing a definition of "significantly imbalanced" would be helpful for understanding the paper. In the abstract, it is mentioned that the method works for imbalanced cases with a "significantly different" number of samples. However, in Remark 6.2, it is stated that Theorem 6.1 holds only for a sufficiently imbalanced mixture, and $p_2<1/2$ does not necessarily imply significant imbalance. - While theoretical results on the gap between the output of the proposed method and the true value under the population case is interesting, they are not useful in practice where we have a finite number of samples. It would be valuable to demonstrate 1) the consistency of the estimator and 2) the rate of convergence of the proposed method. - For cases where the number of components $K$ is unknown, the theoretical results in Appendix C only state that the algorithm stops under the given criteria, but they do not describe any properties of the estimator.

Questions

- The mixture model in (1), are the explanatory variables random or fixed? It looks like they are random based on the theory. Should be specified when the model is defined. - The definition of the mixing proportion is weird in the sense that it depends on the sample size $n$. Should it be $p_k=P(c_i^*=k)$ instead? - The statement that "Then the information limit .... is $n_{\text{info}}", can you please explain? Similarly for the statment that "A suitable value for $\rho$ depends on the ratio ...". - $P(\epsilon_t=t)=P(\epsilon_t=-t)$ does not mean anything for continuous random variables, should use CDF or pdf instead.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

Some limitations and possible future research directions are briefly mentioned in the paper.

Summary

This paper introduces a novel algorithm for mixed linear regression suitable for balanced and imbalanced mixture settings. It proves the proposed method holds for a sufficiently imbalanced mixture rather than a balanced one through a recovery guarantee on the theoretical front. Empirical results on synthetic data and real-world datasets highlight the superior performance of the proposed algorithm compared to conventional methods. The key contributions of this paper can be summarized as follows: + The paper presents an efficient and straightforward approach to addressing imbalanced mixed linear regression. + It proposes to find the dominant model, remove its associated samples from the observation set, and repeat the process to find the next dominant model. + It demonstrates the effectiveness through empirical results and theoretical analysis.

Strengths

+ The paper is well-organized and easy to follow. + The proposed method is efficient and simple. The central idea of simultaneously recovering the models while partitioning the samples into three classes based on their fit to the estimated model is indeed intriguing and adds value to the overall approach. + This approach seems promising for addressing mixed linear regression in both balanced and imbalanced mixture settings, as supported by the empirical results and theoretical analysis presented in the paper.

Weaknesses

+ My primary concern revolves around the motivation of this paper. While the title focuses on "imbalanced mixtures," the abstract and introduction cover a wide range of settings, such as small sample sizes, the presence of outliers, and an unknown number of models. While it is commendable that the authors aim to demonstrate the robustness of the proposed method, it would be preferable to emphasize one main topic to maintain clarity and focus. + Figure 1 visually illustrates the central idea of the proposed method, but further analysis or additional figure tools are required to explain why this method is particularly suitable for imbalanced settings. Providing in-depth insights into the algorithm's performance in such scenarios would enhance the paper's credibility. + In Figure 2, a comparison with conventional mixed linear regression methods is presented, but the selected methods mainly date back to before 2016, which might not reflect the state-of-the-art results. Including comparisons with more recent methods would bolster the paper's claims about the effectiveness of the proposed approach. Additionally, line charts, while showing the experiment trends, may not be sufficient to fully convey the experimental findings. Further detailed analysis and discussion of the results are necessary.

Questions

Please refer to the "Weaknesses" part.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

The authors should clarify the potential negative societal impact of their work.

Summary

In this paper, the authors take into account the problem of recovering a mixture of $K$ unknown linear regressions with imbalanced proportions, i.e. the numbers of samples for components in the mixture are substantially different. Rather than try to recover $K$ components at the same time as in previous work, they propose an algorithm named Mix-IRLS which finds these components sequentially using robust regression. This algorithm is theoretically shown to be able to recover the components with small sample size regardless of information about the true number of components $K$. Additionally, it is also demonstrated to be robust to noise and outliers. Finally, the authors empirically polish the performance of the Mix-IRLS algorithm on imbalanced mixtures by conducting simulation studies on both synthetic and real-word datasets.

Strengths

1. Originality: This is the first work to tackle the imbalance in the mixed linear regression. It provides a novel viewpoint of recovering mixture components sequentially rather than simultaneously as in the literature. 2. Quality: Results in this paper are empirically supported and some of them are theoretically grounded. The proposed method is technically sound and applicable for high-dimensional settings. 3. Clarity: The paper is well-written and easy to follow. Assumptions are discussed clearly. Proofs are presented neatly. 4. Significance: This work is important as it is the pioneer in solving the imbalanced problem of mixed linear regression.

Weaknesses

1. The population setting considered in Theorem 6.1 makes this result not practical as we do not have access to an infinite number of samples in practice. 2. Theoretical guarantee for the robustness to outliers and noise of the Mix-IRLS algorithm is missing. 3. There are some claims not associated with any proofs or references. A typical example is a claim in lines 98 & 99: 'No method can recover the models given fewer samples'.

Questions

1. In line 124, should the number of iterations $T_1$ vary with $k$? In particular, the number of samples of interest decreases after each round, which possibly affects the convergence of parameters. 2. In line 135, I think one of the conditions for S'k and $S_{k+1}$ not being disjoint is that the threshold $\omega_{th}$ is too high, not too low as claimed in the paper because the higher the $\omega_{th}$ is the more elements the set $S_{k+1}$ has. 3. Are there any theoretical guarantee that by following the procedures to find the true number of components $K*$, the output is the desired value? 4. What are the main challenges of showing Theorem 6.1 under the settings with the finite number of samples?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors already discussed the limitations of the proposed method in this work.

Summary

In this paper the authors study the problem of mixed linear regression, where instead of a single linear regression model, the response variable comes from a finite mixture of them. The authors propose an algorithm for estimating the regression coefficients, especially in the imbalanced case where the mixing proportions can be very different from each other. The algorithm is efficient and scalable to high dimensions, does not require knowledge of the number of components, and is robust to noise and outliers. The algorithm is tested on both synthetic and real data sets, outperforming several existing methods. Theoretical aspects of the algorithm are also analyzed on the population level in a two-component model.

Strengths

1. The paper presents a conceptually simple algorithm. Although the idea of sequentially fitting each component is not new, the incorporation of robust statistics leads to an efficient and scalable algorithm that outperforms several other standard algorithms for mixed linear regression on both synthetic and real data. 2. The authors show that the algorithm does not require the knowledge of the number of components, which is a very favorable property for learning mixture models, along with robustness to noise and outliers. 3. The algorithm handles sufficiently imbalanced mixtures, extending existing literature which is mostly for balanced or sufficiently balanced cases. It also gives comparable and more robust estimation even in the perfectly balanced case. 4. Although the algorithm requires several hyper parameters, the authors show that tuning of the parameters does not lead to major improvement so the algorithm is essentially tuning free. 5. The theoretical results give a justification of the algorithm on the population level, especially in the sufficiently imbalanced case.

Weaknesses

1. The design of the algorithm seems to rely heavily on the imbalanced mixing proportion assumption to be able to filter out each component, yet it gives competitive or even improved performance in the perfectly balanced case. Some intuition or explanation would be helpful since the balanced case is not covered by the theoretical results. 2. The theoretical results investigate only the infinite data setting. The paper could be strengthened with a finite sample analysis.

Questions

1. If I understand correctly, the noise distribution is assumed to be the same across all the components. Does the algorithm apply in the case when the noise distribution is different for each component? Or is there any major modification needed? 2. Let's say we have a two-component model with perfectly balanced weights (p1=p2=1/2). In an intuitive sense, how would the algorithm proceed in this case? I guess the initial step would end up with something like a line right in the middle of the two components, and wonder how the algorithm would correct for this.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Theoretical analysis of the algorithm could be strengthened, but the empirical success is already very compelling.

Summary

This paper proposes a new method, Mix-IRLS, for mixed linear regression, in which data are drawn from a mixure of linear models whose coefficients we wish to estimate. The method is especially motivated by the failure of existing methods in the case of imbalanced mixtures (i.e., when some components are much rarer than others). After presenting the new method, the paper presents experimental results on simulated and real data, illustrating the improved robustness of Mix-IRLS over existing methods. Finally, the paper proves that, in a particular two-component, infinite-sample example, a slight variant of Mix-IRLS is able to recover both of the true regression coefficients (even without knowing the number of components a priori).

Strengths

The MLR problem is clearly presented and the proposed Mix-IRLS approach is well-motivated. The simulations clearly illustrate the basic strengths of Mix-IRLS (robustness to imbalance, contamination, and unknown K) over existing methods. The application to the music perception dataset of Cohen [13] is compelling and well-explained.

Weaknesses

1) The introduction doesn't mention any applications motivating the MLR problem. The only real-world example is the music perception dataset of Cohen [13] in Section 5. I would find the paper more compelling if it were clear to the reader why this problem is useful to study. It would be especially compelling if there were real-world examples where class imbalance was a limiting issue for existing methods (the music example appears fairly balanced, although it is hard to tell from the plot). 2) Some of the assumptions in Theorem 6.1 seem arbitrary and unnecessary. Specifically, the assumption X ~ N(0, I_d) is very strong, and the resulting in the theorem doesn't illustrate how the distribution of X impacts the recovery guarantee. Based on existing theory for linear regression, I would expect a much milder assumption, such as a lower bound on the smallest eigenvalue of the covariance matrix of X, to suffice. Also, as far as I can tell, excluding X_i with ||X_i||^2 < R is done only to simplify the analysis and shouldn't really affect the recovery guarantee (indeed, as far as I can tell, the guarantee in Theorem 6.1 only improves as R -> infinity). These assumptions make Theorem 6.1 feel more like an "example" than a "theorem", and encourage the authors to work towards a more general formulation of Theorem 6.1. Overall, on initial reading, I lean weakly towards rejection because the real-world significance of the work is not very clear and the theoretical results seem unpolished. But I could change my score if either of these points is improved substantially.

Questions

1) In addition to each component of c^* being sufficiently large, I think identifiability also requires all of the \beta's to be distinct (consistent with the 1/||\Delta|| terms in Eq. (10)). Perhaps this should also be mentioned in the context of identifiability, around Line 94. 2) Lines 97-99, "the minimal number of observations n required to recover $\beta^*$ in the absence of noise is $n_{info} = d/min(p)$." What is the justification for this sentence, and what assumptions does it require? Is it somehow obvious? Can the authors prove it or provide a reference? 3) Lines 101-102, "Even in the simplified setting... the problem is NP-hard without further assumptions." How is the present work able to get around this? Does it make further assumptions? (If so, which ones?) Does it guarantee only approximate recovery? Or something else? 4) I was confused by the corruption added in the second simulation (corresponding to the left panel of Figure 3). It seems to me that the corrupted samples \tilde{y}_i are a special case of an MLS component, with \beta = 0 and a different noise scale. As far as I understand, Mix-IRLS does not know noise level \sigma, so it cannot distinguish which is the "real" data and which is the "corruption". So, it seems like Mix-IRLS is arbitrarily selecting one of the two possible MLS models, and is ignoring the other. Is this task well-specified? 5) What is the goal of applying Mix-IRLS to the Kaggle regression benchmark datasets (health insurance, red wine, WHO life expectancy, and fish market)? As far as I could tell, the purpose of Mix-IRLS is parameter (\beta) estimation, but it's not clear to me what parameters are being estimated in these examples, or how these results could be interpreted. 6) In the Problem Setup (Section 2), the distribution of explanatory variables Xs is not discussed. This is fine, since a precise statistical model is not needed (except in Theorem 6.1), but I feel like I am lacking some intuition for the problem because of this. Sometimes (e.g., Figure 1), their distribution seems to differ for each MLR component, whereas elsewhere (e.g., Theorem 6.1) their distribution is the same. Intuitively, the former (different distributions) setting seems potentially much easier than the latter (same distributions) setting, since the components will be more separated. Is there a particular way the authors suggest thinking about the distribution of Xs? I also have a similar question regarding the distributions of \epsilons -- is it important that the noise distributions be similar across components?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Section 7 discusses some limitations of their theoretical results, but perhaps this could be more extensive (see point 2 under "Weaknesses" above).

Measuring clustering performance in the CO2 experiment

Thanks to the authors for adding the new CO2 experiment. I think having such a concrete application significantly strengthens the paper and I intend to raise my score due to this addition. However, I'm unsure whether the intersection score used to measure performance in this experiment is appropriate. Specifically, for imbalanced mixtures, the intersection between the labels found by each method and the true labels is not a very informative metric, as it places little weight on rare classes (much as accuracy is not an informative measure for imbalanced classification). On this dataset, a method could conceivably have 92% intersection score without ever identifying the rare (diesel and ethanol) classes, and, from the reported results, it's unclear which, if any, of the methods actually recover these rare classes. So, I suggest instead reporting class-wise performance measures (e.g., recall) separately for each class. The overall intersection score might still be appropriate for selecting the best permutation of the classes, though. If it turns out that MixIRLS is better able to recover the rare classes, then I think the results are especially impressive and could be better highlighted by a more informative metric. On the other hand, if it turns out that the stronger performance of MixIRLS is mostly due to better distinguishing the two prevalent (regular/premium gasoline) classes, then the conclusion is still positive, but some more careful interpretation/discussion of the results might be in order (e.g., perhaps this is better explained in terms of robustness than in terms of class imbalance).