Optimal Learners for Realizable Regression: PAC Learning and Online Learning

Summary

This paper studies the statistical complexity of realizable regression in the PAC learning and online learning setups. The main results are the following combinatorial conditions that characterize the PAC and online learnability: - PAC learnability by (worst-case) ERM learner is equivalent to having a finite $\gamma$-graph dimension for all $\gamma \in (0, 1)$. - PAC learnability is equivalent to the finiteness of $\gamma$-one-inclusion graph dimension for all $\gamma \in (0, 1)$. - The minimax cumulative loss in online learning is characterized (up to a constant factor) by the online dimension. The combinatorial dimensions are above are newly introduced in the paper. The authors also conjectured that the DS dimension in the literature also characterizes PAC learnability. In addition, the paper provides several other examples that shed light on the landscape between learnability, uniform convergence, and other complexity measures of the hypothesis class (Figure 1).

Strengths

This paper studies a fundamental problem in learning theory, which has, surprisingly, been left open for several decades. The results are strong and comprehensive, and the authors did a great job in introducing the prior results and presenting the high-level roadmaps behind the technical proofs.

Weaknesses

My only complaint is on the short conclusion and a lack of discussion on future directions (apart from the obvious one of proving Conjecture 1).

Questions

Regarding Conjecture 1: - Could you elaborate on the obstacle that prevents the approach of [BCD+22] to be applied towards the regression setting? - Are there any evidence/heuristic arguments that support the conjecture? Are there interesting assumptions under which finite $\gamma$-DS dimension implies learnability?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and 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

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

This is a theory paper and its limitations lie in the assumptions on which the validity of the results rely, including the realizability assumption and the focus on PAC and online learning. This has been formally stated in the paper, and also explicitly mentioned in the title and abstract.

Summary

This paper develops optimal learners and characterizes learnability with new combinatorial dimensions for realizable regression (where the best predictor has zero regret) in PAC and online learning, significantly depicting the landscape of learnability in PAC/online learning. For PAC learning, they show that: - the PAC learnability in the realizable regression by a worst-case ERM iff the gamma graph dimension is finite - learnability in the realizable regression is fully characterized by a finite gamma One-Inclusion dimension - finite gamma-DS dimension is a necessary condition for PAC learnability in the realizable regression For online learning, they devise a new combinatorial dimension, namely online dimension that is built up on the scaled Littlestone dimension. They show that the online dimension characterizes the minimax instance optimal cumulative loss up to a constant factor and design an optimal online learner.

Strengths

- Significant results that complete the landscape of learnability of PAC/online learning in realizability regression

Weaknesses

- None that I know (note that this problem area is not my research domain)

Questions

N/A

Rating

9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and 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

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The paper might need to discuss the limitations of the results and analysis.

Summary

This paper introduce some dimensions that characterize PAC learnability for realizable regression. The authors introduce $\gamma-$ Graph dimenion which is necessary and sufficient for PAC learnability by ERM, and $\gamma-$OIG dimension which is necessary and sufficient for PAC learnability. $\gamma-$DS dimension is introduced which is necessary and conjectured to be sufficient. There are also results for online learning.

Strengths

PAC learnability for realizable regression is characterized by an appropriate dimension. This seems to be an important open problem that is resolved.

Weaknesses

The various dimensions are hard to understand. It would be nice to see examples. For instance, lines 188-192 were not particularly helpful to understand Definition 5, since I am not sure what it means for $\mathcal{H}$ to contain a cube. Do you mean there is a hypercube of a certain size embedded in every function in $\mathcal{H}$?

Questions

Line 263, is there some typo? maybe you dont mean $\forall i$.

Rating

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

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central 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

None

Summary

This work analyzes the realizable regression and connects it with several notions of dimensions. They care about the online learning and the PAC learning. They first show that the $\gamma$-OIG dimension characterizes the PAC learning and that PAC learning requires finite $\gamma$-DS. Finally, they show that for the online regression, the authors find a dimension that characterize it. They show that this dimension is an upper bound over the cumulative loss and it is a lower bound up to some constant.

Strengths

The paper provides complexity results for regression in online learning and PAC learning. In binary classification, we have a better understanding of the complexity and how different dimensions connect. In the regression setting, we do not know a lot and this paper provides a very good understanding and nice results. The paper is well written and explains the previous work well.

Weaknesses

Not a weakness, but can the authors explain why is there a requirement for bounded labels? What happens if the labels are not bounded?

Questions

The question in the weaknesses section.

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

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

no limitations.

Summary

This paper provides combinatorial dimensions that characterize realizable regression in both batch as well as online settings. Moreover, it provides minimax optimal learner up to polylog factor in the batch setting and minimax optimal learner in the online setting.

Strengths

1. The paper is well-written, easy to follow, and solves an important open problem of characterizing realizable learnability for real-valued function classes. 2. The paper uses classical ideas such as Median Boosting algorithm, sample compression schemes as well as some recent developments in PAC learning theory such as partial concept classes, OIG based dimensions, etc. Overall, the paper is technically sound and is definitely an important technical contribution to the field. 3. In online setting, the paper introduces a novel idea of summing scales along each branch of the tree and defining dimension as the sum of scales. This is a novel and useful technical tool as it provides a new way of defining dimensions that are not parametrized by a scale even though some form of scale is inherent to the problem setting.

Weaknesses

Although the paper does provide a combinatorial characterization of realizable regression, I am not sure if the OIG-based dimension is very insightful. Theoretically, it is a useful abstraction as it has a finite-character property and thus the learnability of the problem can, at least technically, be determined using finitely many domain points and functions in function classes. However, the practical utility of such dimension is questionable. Can be computed for natural classes such a linear classes, Lipschitz classes, and so forth? Computing upper bounds is generally difficult even for classical dimensions like VC and fat-shattering, but the lower bounds of these dimensions are typically easy to compute for some natural classes because of simplicity of their shattering conditions. Is it also the case for this OIG based dimension?

Questions

I assume that fat-shattering dimension upper bounds the OIG based dimension proposed here. Is there a combinatorial proof of this fact? Also, is there a general property of the class that guarantees that the finiteness of OIG based dimension and fat-shattering dimension co-incide?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and 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

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

N/A