Memory Savings by Sharing One Source: Insights into Subsetsum Approximation

1. Determining the optimal binary mask and subset sum may result in higher computational overhead, which may outweigh the memory savings.
2. Although the research touches on certain practical issues (such as redundancy in sparse models), more examination of failure scenarios and edge cases could improve the work.

• While I understand at a high level the theoretical motivations of the paper, and that strong lottery tickets themselves do not require training per-se, finding the masks for SLTs amounts to optimizing/training the masks which could be expensive at high model widths for which SLTs work. It's not obvious this method would be practical in practice even for inference at SLT widths, and it's most importantly not clear to be that the memory savings would be worth the extra computational costs. There are no discussions on even theoretical computational costs and if these could ever not be the bottleneck in an MoE or ensemble rather than memory.
• No empirical evidence, which I believe is necessary given the non-theoretical motivations and claims of the authors that the theoretical results are validated in experiments.
• Only memory savings results are the theoretical results in Figure 2 that appear to assume a straightforward reduction in memory proportional to the number of shared models.
• Multi subset sum approximations can also be expensive, and in the author's experiments, they do not discuss the computational requirements of this part of their methodology. In Algorithm 1 it appears the approximation is O(2^n).
• I found the motivation and claims on contributions towards making MoEs/ensembles more memory efficient unconvincing given the author's theoretical findings and lack of experimental validation. Although I understand these are timely and appealing motivations in themselves, the author's proposed theoretical claims have little to do with memory efficiency of ensembles and MoEs in practice. These are very dependent on hardware and implementation, especially "memory footprint", which is much more about intermediate representations than just the number of weights of the models in practice.
• The authors appear to conflate "memory footprint" and the number of weights in a model (i.e. size of a persisted model). While obviously the number of model weights do play a factor in the memory footprint of a model, it's usually a minor one compared to other factors more specific to the architecture and implementation of that architecture. It's fairly difficult to motivate methods that reduce the number of weights of a model alone as memory footprint and computational complexity are significant bottlenecks, while storage is not typically a bottleneck in contemporary compute settings/applications.
• There is a wide body of literature in deep learning related to the idea of having a base model with different sparse masks might be used to learn different representation has been proposed and explored in many settings already in numerous papers unreferenced, notably "Piggyback: Adapting a Single Network to Multiple Tasks by Learning to Mask Weights", Mallya et al., ECCV 2017, and "Many Task Learning With Task Routing", Strezoski et al. ICCV 2019. While I do not claim the author's method is not novel (I believe it is) if there are claims it would be better in practice than these previous approaches, these need to be empirically validated compared to such baselines and papers that are similar mentioned and differentiated from. If there are claims the proposed method would be theoretically better than these, perhaps that should also be demonstrated. At a minimum some of this literature should be in the related work also.
• I personally found the paper hard to understand and follow, often assuming notation or concepts without defining them or the context. For example, in the second paragraph, without great knowledge of the theoretical work in SLTs the reader would be completely lost on what a "width requirement" is or why we are interested in it here. Or on notation, simply even $\epsilon$ and $\delta$ in Theorem 3.1, 3.2 respectively, we seem to be required to assume what these are until much later in the paper.

The text should be more readable if some prelimiary knowledge is given.

1. This work is based on a problematic concept of SLT, which has many potential problem itself (e.g., long searching time, fail to improve accuracy if trained on the subnetworks, etc.). Therefore, the design and solution is not convincing.

2. This paper claims the memory reduction by using SLT. However, the experiments are not quite sufficiently showing such claim. It is not clear how memory is reduced. Also SLT can reduce memory is already proved in Otsuka et al., 2024, therefore making the contribution of this paper limited.

3. The experiments are not thorough. The author of the paper only conduct very limited experiments, with only two figures. Besides, the figures are also showing limited information. There are no quantitative data or analysis.

4. The paper has some minor writing issues. The writing is not consistent and the elaborations are sometimes confusing. For example, in line 738-739 in appendix, the reference of the section is missing with question marks.