Venue: NeurIPS 2022 Conference

Reviews:

final_score: 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.
review_content: summary: This paper attempts to understand how masked autoencoder (MAE) works and investigates why the masking ratio of MAE is important. On top of the analysis, the paper proposes a uniformity-promoting MAE loss which additionally regularizes the loss by enforcing uniformity. In experiments, the uniformity-promoting MAE shows better performance than the original MAE on CIFAR-10 and ImageNet-100 datasets. 
strengths_and_weaknesses: - Strengths
	- Theoretical analysis of masked autoencoder gives somewhat new perspective and insight. 
	- Proposed uniformity-promoting MAE seems a reasonable loss design and works well on CIFAR-10 and ImageNet-100. 
- Weaknesses
	- The experiments are weak, so it is hard to convince the paper's main claim. As in table 1, the experiments are conducted on CIFAR-10 and ImageNet-100 which are not standard for evaluating self-supervised learning methods. It is necessary to conduct at least one comparison with MAE *on ImageNet-1k* as in the original MAE paper.  
	- The main formulation and analysis are based upon the MAE framework, so I wonder if the observations and knowledge can be transferred to other masked image modeling methods like BEiT [1], iBOT [2], and SimMIM [3], and so on. Discussion about the transferability of those methods and relationships among such masked image modeling methods will be interesting. 
	- It is hard to convince the claim in Figures 2 and 3(a) saying "the higher mask ratio will generate more similar views of intra-class samples." at line 241. Figure 2 seems to cherrypick samples. It is not guaranteed that the surviving patches have similar semantic meanings in natural image datasets like ImageNet. In figure 3, a smaller L2 distance at a higher mask ratio may come from the loss of variety and diversity of image patches. 


[1] Bao et al., Beit: Bert pre-training of image transformers, ICLR 2022
[2] Zhou et al., iBOT: Image BERT Pre-Training with Online Tokenizer, ICLR 2022
[3] Xie et al., SimMIM: A Simple Framework for Masked Image Modeling., CVPR 2022
questions:  - I wonder if the investigation and solution (U-MAE) can be transferred to other masked image modeling methods like BEiT [1], iBOT [2], SimMIM [3], and so on. Discussion about the transferability of those methods and relationships among such masked image modeling methods will be interesting. 

[1] Bao et al., Beit: Bert pre-training of image transformers, ICLR 2022
[2] Zhou et al., iBOT: Image BERT Pre-Training with Online Tokenizer, ICLR 2022
[3] Xie et al., SimMIM: A Simple Framework for Masked Image Modeling., CVPR 2022
limitations: the review will be updated in a couple of days.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper presents theoretical results of MAE, a recently popular approach for self-supervised visual representation learning. Two insights are provided: 1) MAE loss can be bounded by an implicit alignment loss, and switching to this loss appears to be helpful for MAE pre-training; 2) masking at a high ratio implicitly bridges different instances of the same class. Experiments are mainly done on small-scale datasets, CIFAR-10 and ImageNet-100.
strengths_and_weaknesses: (+) Analyzing and understanding state-of-the-art approaches, especially in self-supervised learning is of great significance.

(+) While I have not checked the math carefully, I find the insights discovered in the paper interesting, and it also appears to be quite well-supported by the experiments.

(-) The paper presents two results, one by treating MAE as implicit contrastive learning (Section 3), and one by building on a theory of generalization. While both are interesting, it is generally making the paper less focused (it could just be two separate works instead).

(-) I don't like the writing style of the paper, where the derivations appear in the main text. I would hope to see clean results, key equations, and detailed insights in the main paper, and leave the derivation part in the appendix.

(-) Figure 1 appears to be not so necessary, as MAE paper has already shown a similar trend on the standard, large-scale dataset ImageNet-1K. 

(-) Figure 2 is a bit artificial and less *convincing*. The visualization just shows a particular pair of examples. Many concerns can arise: what if the intra-class variation is so big that no shared, similar views can be found between two examples? what if the shared views are across two examples from *different* classes?

Overall, I think the paper is presenting some interesting results and findings, but I don't think they are solid enough from the perspective of empirical justifications. I do hope my concerns can be addressed so that I am no longer on the fence for this paper. 
  
questions: - Clarification: how is $f_g$ obtained in the U-MAE loss? According to the theory it seems $f_g$ is a hypothetical function that inverts the decoder, but it is not clear how such a decoder can be trained empirically.
- Rebuttal request: I don't think Figure 3 is convincing enough. It just shows the L2 distances with intra-class examples and intra-instance views are decreasing as the mask ratio decreases. However, it is not clear what's the trend of the *overall* distances in the entire dataset, and what's the trend of the inter-class examples. I think it is more important to show the *relative* trend between intra-class and inter-class, rather than the *absolute* trend.
limitations: It's a theoretical paper, I do not find the paper addressing limitations and potential negative impact, which is fine to me.
review_title: null

final_score: 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.
review_content: summary: The paper aims to provide a theoretical underpinning to explain the success of masked autoencoders (MAEs) in computer vision, with a particular focus on the importance of the mask ratio. To this end, the authors establish a connection between MAE training and contrastive self-supervised learning objectives, and leverage graph theory to establish a generalization bound. Furthermore, based on their analysis the authors propose a regularizer and test its effectiveness empirically, observing benefits on multiple data sets.
strengths_and_weaknesses: I believe the search for a connection between contrastive self-supervised learning and reconstruction based approaches like MAEs is interesting and could turn out fruitful. The attempt to link the Siamese structure in contrastive SSL with the encoder-decoder architecture used in MAEs looks promising at first. However, I have doubts about different elements of the derivation of the alignment, as well as the presentation and the experiments.

The major issues I found are the following:
- It seems that then MAE encoder and decoder are incorretly defined in L93: Using the notation from the laper, the encoder $f$ maps $|m|$ image patches to $|m|$ tokens, which are then interleaved with $n - |m|$ mask tokens according to the locations of the masked patches and augmented with positional encodings. The resulting n tokens are then fed to the decoder $g$ which outputs $n$ patches. The authors then define $x_1$ corresponding to the stacked unmasked patches, and $x_2$ corresponding to the stacked masked masked patches. This means that $x_1$ and $x_2$ have different shapes unless the masking ratio is 0.5. As a consequence, the Lipschitz property cannot be applied as in L151 because $f(x_1, p_{x_1})$ and $f_g(x_2, p_{x_2})$ do not map into the same space. This would mean that the proof breaks down at this point. Interleaving $f$ and $f_g$ with the masked and unmasked tokens would bring them to comparable spaces, but considering the distance between the interleaved representations would not make much sense as this would amount to simply measuring the magnitude of the unmasked representation. I’m happy to change my assessment, but I don’t see how this can be fixed.
- Concepts from prior work are often unsufficiently explained, e.g. the derivation of the spectral graph theory based generalization bound and the related quantities (e.g. the authors talk about why the graph they consider is directed before it is clear what the relevance of the graph is). Notations are often defined after they are used for the first time, others are not introduced at all such as some quantities in Theorems 4.1 and 4.2.
- It is often unclear what the assumptions are and what is proven by theory. I believe a better way to structure the paper would be to clearly state the assumptions and then why they should be satisfied in practice (e.g. w.r.t. the Lipschitz assumption).


Minor weaknesses:
- L163 (and later) “regularizer” instead of “regular”
- The last parenthesis in (5) should be deleted.
- The choice of $f_g$ is important for the proposed regularization loss, but how it is chosen is only described in the appendix. It would be better to move the description to the main paper.

questions: - What is $\tilde x_2^-$ in equation (9)? How does the last term relate to uniformity as suggested by the terminology uniformity-promoting MAE? I could see how it relates to alignment.
- Why is (5) greater or equal the preceding expression? It seems it would be equal to the preceding expression.
- How are the graph weights define exactly? $M_1$ and $M_2$n are probability distributions if I read the definitions correctly, so the definition in (10) wouldn’t resolve to a scalar weight.
- What visualization technique is used to generate the plots in Figure 4? What data set are the results in Figure 5 obtained for?

limitations: It is unclear whether the approach really captures the mechanism underlying the success of MAE. At least I’m not convinced that the potentially incorrect derivations give additional insights on top of the intuitions e.g. about masking ratios given in the original MAE paper.
review_title: null

final_score: 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.
review_content: summary: The authors propose a new theoretical understanding of Masked Autoencoders (MAE). From the theoretical perspective, this paper is interesting and novel. I agree with their contributions as stated in the paper.

1. They prove that MAE loss is upper bounded by an implicit alignment loss and develop a new understanding of how MAE bridges the samples in the same class. Based on their analysis, they propose a new U-MAE loss.

2. They establish a guarantee for the downstream performance of MAE with practical assumptions and compare the training process of contrastive learning and MAE.

3. They verify that their U-MAE loss can significantly improve the performance of MAE on two datasets CIFAR-10 and ImaegNet-100. 

 As a very early attempt, this paper provides theoretical contributions for the MAE study. Both the "How to Understand Masked Autoencoders" paper and this paper provide insights for the theoretical research for the MAE community.
strengths_and_weaknesses: Strengths

MAE looks like a very straightforward model. But how to extract the mathematical essence of the simple model is very challenging. This paper contributes a novel understanding of MAE, and provides the experiments.   In particular, the authors propose a new theoretical understanding of why the choice of mask ratio is so important for MAE from a graph perspective. This is very insightful and inspiring.

Writing is clear and easy to follow.


Weaknesses -- some suggestions and minor issues.

1. The mathematical formulations can be improved. 

For example, Line 95 [k] and Line 105 [.] will make the readers confused about the brackets. 

In Line 100, the tilde can be replaced as $\in$, as D_u is defined as a set, not a distribution.

In Eq. (1), x_1 is defined as a vector, so it is better to use bold to denote the vector.

2. More implementation details. 
It is very interesting to see more training details, including how many GPUs, and how many hours for training. 

3. More explanation on experimental results.

For example, in Figure 4 (2), U-MAE loss obtained better visualizations. There are two clusters (grey and red) that are separated from other clusters. Why are they so distinctive from the others?  What are the 10 random classes?  What classes are the grey and red clusters presenting? What are the natures of these two classes in the original data domain?  Further analysis can give us more motivation.
questions: Suggestions can be found in the above.
limitations: Training MAE from scratch is very resource-consuming. But for future work, it is still better to do experiments on the large-scale datasets, like ImageNet-1K used in the MAE paper.
review_title: null

Meta-review: metareview: The authors aim to shed some light on the recent success of masked autoencoders (MAEs) by theoretically analyzing the MAE loss and the role of high masking ratios. In particular, the authors show that, under some assumptions, the MAE loss can be upper-bounded by an implicit alignment loss. The authors argue that this connection to contrastive self-supervised learning is critical and allows one to formally characterize the effect of different masking ratios and establishing a generalization bound. Then, the authors propose a regularizer based on the analysis and empirically evaluate its effectiveness.

The reviewers appreciated the timeliness and significance of this work. The insights brought forward seem relevant and important enough to the larger community focused on the theoretical underpinnings of MAEs. Two main weaknesses were identified: (1) Does this potentially very loose upper-bound actually allow one to make the conclusions in this work? After all, the models in practice might not satisfy the stated assumptions. In fact, the transformer architecture itself might be the driving force behind the success. (2) The empirical validation is not ideal -- given that the authors didn't reproduce the original results on ImageNet-1k it's unclear whether the proposed regularizer improves the results on top of the non-regularized MAE.

After the discussion phase the ratings remained borderline and two reviewers were still not fully convinced. I personally feel that both (1) and (2) were partially addressed during the discussion. Having in mind that providing definite results in this setting is incredibly challenging, I find that this work is a valuable contribution to the community of researchers trying to improve the understanding of the underlying mechanisms of self-supervised learning.
confidence: Less certain
Decision: Accept