Summary
This paper analyzes the impact on sample complexity of encoding invariances into kernel functions in the context of kernel ridge regression. A kernel function is invariant to the actions of a group if its output does not change when its inputs are acted on by members of the group. The paper shows that for finite groups, the sample efficiency is effectively multiplied by the size of the group. For groups of positive dimension, it shows the sample efficiency is improved by (1) reducing the effective dimension of the input manifold, and (2) reducing the volume of the manifold.
Strengths
- Significance: This paper analyzes how invariance improves sample complexity for kernel ridge regression in a much more general setting than prior work. For example, it allows the input space to be any compact manifold, and the invariance to be represented by any smooth compact Lie group (prior work, for example [5], had assumed the input manifold was a sphere and that the invariance was to a finite group).
- Quality: Although I have not checked the proofs, the quality of the work appears high. The generalization bound in Theorem 3.1 is proved to be minimax optimal in Theorem 3.3, an interesting/important result.
- Clarity: The paper is generally well written and clear. See “Weaknesses” section for places for improvement.
- Originality: It seems the approach of using differential geometry to analyze these generalization bounds is original, and that the authors developed some tools of independent interest in this area.
Overall, I believe this paper makes an important theoretical contribution to a problem space that has been of significant interest to the machine learning community: namely, how to make models invariant to certain input transformation (either via data augmentation, or by changing model architecture), and understanding how encoding these invariances impacts the models’ generalization performance and sample complexity.
Weaknesses
Perhaps the greatest weakness of this paper is at times seeming too “mathy” (https://arxiv.org/pdf/1807.03341.pdf), without sufficient grounding in concrete examples or empirical results. For example:
- It would have been useful to go over more examples of invariances whose groups have positive dimension, and understand more concretely how these invariances affect the generalization bound.
- It could be useful, for equations (5) and (7), to give examples of how this quantity changes for different finite vs. infinite (positive dimension) groups. One example I had in mind, for $x \in R^2$, was rotational invariance, where the rotations could be in a finite group (e.g., rotate by multiples of $\alpha$ degrees, for any $\alpha$ that evenly divides 360) or an infinite group (e.g., rotate by $\beta$ degrees for any real-value $\beta \in [0, 360)$). How would these situations compare, in terms of equations (5) and (7), as the value of $\alpha$ approaches 0?
- It would have been helpful to understand which of the examples given would not have been possible to analyze with prior results.
- It would have been useful to run experiments (even toy/synthetic experiments if necessary) to demonstrate that the bounds from the paper are actually predictive of model performance.
NIT: $\omega_d$ is defined in Theorem 3.4, but used in prior theorems.
Questions
See 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.
Limitations
Perhaps a broader discussion of limitations would be useful.
- What deep learning scenarios would the results from this paper apply to or not apply to?
- What important open problems remain to be solved?
- How empirically predictive are these theoretical results, in different settings? In what cases would these results definitely not be empirically predictive?