An Adaptive Algorithm for Learning with Unknown Distribution Drift

Summary

The paper proposes an algorithm for environments with changing distributions without assuming a priori knowledge about the change in distributions. The proposed algorithm provides error bounds that decrease with the number of time steps.

Strengths

The idea of considering independent distributions with distribution shift is unexplored. The algorithm itself is a solid technical contribution, and the theoretical results are strong

Weaknesses

Numerical experiments are not included. Assumptions need further justification.

Questions

How strong is the assumption on the distributions? What scenarios satisfy such assumptions, are there any real examples? The reviewer believes that the problem formulation needs further explanation (e.g., what is to be learned at each instant of time). Numerical results could help to see the superiority of the presented method. The references are a bit old. There are more recent related works: “Minimax Classification under Concept Drift with Multidimensional Adaptation and Performance Guarantees.” “Adaptive online learning in dynamic environment.” “Random feature based online multi-kernel learning in environments with unknown dynamics.”

Rating

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

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

3 good

Limitations

Numerical experiments are not included.

Summary

This paper under considers the theoretical problem of determining the sliding window size for empirical risk minimization in the presence of unknown distribution changes. The proposed method aims to enable the learning of a classifier comparable to approaches that have prior knowledge of the distribution change magnitude.

Strengths

+ The paper's motivation is commendable, as it aims to tackle the challenge of non-stationary sequential learning, specifically with unknown distribution shifts. This is an important problem, and the proposed technique could potentially contribute to its advancement. + Although not evaluated extensively, the results appear reasonable. While I haven't reviewed the proofs in detail, they seem sound.

Weaknesses

- The paper relies on computability assumptions for key variables, such as the distribution discrepancy (e.g., $\|P^r_T - P^r_T\|_{\mathcal{F}}$) and the constants ($C_{\mathcal{F},1}$ and $C_{\mathcal{F},2}$). However, the paper lacks a discussion on when these assumptions hold, how solvable they are, or how accurately they can be estimated or upper bounded. In comparison to previous methods that estimate distribution shifts, it is unclear whether estimating these parameters would lead to a more practical algorithm. This aspect requires further analysis and discussion. - The authors claim that their proposed algorithm aims to provide a practical solution to handling unknown sequential distribution shifts without prior knowledge. However, the proposed algorithm introduces new parameters that are challenging to estimate or even tightly upper bound, such as the distribution discrepancy (assumption 2). While the new analysis techniques presented may contribute to addressing the problem, the overall contribution seems limited, as the proposed method essentially shifts the difficulty from estimating the distribution shift magnitude to estimating other parameters. - The paper lacks a thorough discussion on when Assumption 2 holds, especially in practical scenarios. This assumption is crucial, as the proposed method relies on estimating the distribution discrepancy and other constants that evolve the hypothesis class $\mathcal{F}$. Without addressing the practicality of these estimations, the proposed method's feasibility remains questionable. It would be beneficial to provide a detailed comparison of the estimation difficulty for the parameters required in the proposed method compared to previous works.

Questions

It is important to explicitly discuss the computability assumptions made in the paper and discuss when and how they hold. This discussion should include considerations of solvability, accurate estimation, or upper bounding of variables such as the distribution discrepancy and the constants. So it is suggested to provide an in-depth analysis of Assumption 2 and other computability assumptions on the constants mentioned above and its applicability in practical scenarios.

Rating

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

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

3 good

Limitations

Limitations are discussed in this work.

Summary

The author propose a general algorithm to learn a family of functions with respect to the current distribution at time T. This algorithm achieve a drifting-instance-dependent bound without any prior knowledge of the drift. Based on this, the author further analyze a tractable algorithm on binary classifier.

Strengths

1. The paper solves an open problem of drifting distribution with unknown prior. The proof technique is clear and solid. 2. It's further analysis on binary classification is inspiring.

Weaknesses

1. The error bounded is only measured on windows that end at T. Instead, a better goal would be to select a window from t1 to t2. As an example of why this problem could be more relevant, there might be large drifts nearby T but early distributions are close to P_T. 2. The techniques used in this paper is not very novel. Specifically, although the authors claim they do not directly estimate the drift error, it is still drift detection only with tolerance towards estimation error. The doubling trick is intuitive and not surprising here. 3. As the authors admitted in our paper, this algorithm is very general and might be computationally intractable in more complicated cases. I think the author could discuss the benefit of their algorithm versus existing work on cases beyond binary classification. They may do this by showing either further proofs or empirical evidence. Currently, it is not immediate to me the value of an algorithm that ignores assumptions on the magnitude of the drifts.

Questions

Why is empirical estimate based on a window up to T better than empirical estimates based on any consecutive window? What's the value in getting rid of prior knowledge on drift magnitude in practice or in theory?

Rating

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

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

2 fair

Contribution

2 fair

Limitations

Sufficient.

Summary

This research paper presents a straightforward algorithm designed to facilitate adaptive learning of models in the presence of distribution drift. The algorithm is specifically designed to adapt to changing data patterns without requiring any prior knowledge of the drift. Moreover, the paper provides a proven bound that guarantees the learning error of the algorithm. Overall, the paper is well-written. The simplicity of the algorithm contributes to its comprehensibility, making the results easily understandable. Additionally, the inclusion of a detailed illustration showcasing the algorithm's effectiveness in handling binary classification with distribution drift serves as a strong validation of the proposed methodology. I think this is a breakthrough work for learning under non i.i.d data as it does not require prior knowledge of the potential drift. However, this could also be one of the limits of this paper. The algorithm proposed is to adaptively find r that can achieve the best trade-off between the statistical and drift error. Drift sometimes might represent an upcoming arrival of a new distribution. The proposed algorithm might get a competitive average accuracy compared to those algorithms that know the magnitude of drift in advance. However, I am not sure if this proposed algorithm will perform equivalent good if we test it on every sequential portion of the data as well. For example, a classifier of labeling every instance as 0 could also achieve an accuracy of 90% on the data where 90% of instances are 0 class. In this case, I get very limited information from its good results. Overall, I think the proposed methodology provides a new way of designing the learning algorithms under drift.

Strengths

Overall, I think the proposed methodology provides a new way of designing the learning algorithms under drift. I also agree that r would be an important factor during learning under drift. Therefore, adding this to the learning boundary, from my perspective, is a good start of conducting the following theoretical learning works that discuss the non-identically distributed problem. Theorem 1 could be a quite useful guidance for the following studies in this area.

Weaknesses

As I have mentioned in the summary, Theorem 1 only provides a very general bound. The r is considered as sequentially increased. However, I think the usage of Theorem 1 is very limited if we apply it to learning sequential data. As for the sequential data, there should be always new data coming and thus very possibly new distribution in the upcoming instances. It is less practical to design the r as monotonically increasing if you don't consider the magnitude of the drift. The Inequality in Algorithm 1 is always comparing P_t between it is at r_i and r_{i+1}. This means the i is only updated when the distribution drift is large enough among two consecutive i. However, this is not true. Therefore, this algorithm removes the assumption of knowing the magnitude of distribution drift in advance, but for me, it actually adds a hidden assumption that the magnitude of distribution drift should be enough big between at least one of two consecutive i in [1, T]. Let's think of the situation that the magnitude of distribution drift is incremental increasing by i. I am not sure if your algorithm can output the expected r in such a case. But for those algorithms that assume a known magnitude of drift in advance. They can complete this task. As is also mentioned in this paper that an adaptive algorithm with respect to the drift that uses distribution-dependent upper bounds

Questions

In Theorem 1, r is the output of Algorithm 1. What will be the limits if using other algorithms?

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

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

3 good

Limitations

Some of the limitations have been listed in section 7. As is discussed, satisfying Assumption 2 is challenging and authors already discuss possible solutions. From my perspective, the author claims their contributions as removing the prior knowledge of distribution drift. I appreciate their contribution. But as a reader, I am more curious if we do get some prior knowledge of the distribution drift, how can we use that knowledge to improve what you have presented in this work? I think this will provide more insights of this work.