Inv-PnCO: Invariant Predict-and-Combinatorial Optimization under Distribution Shifts

Writing Issue: The writing of this paper requires meticulous revision and further improvement. The primary contribution lies in the theoretical analysis; however, I found numerous errors in the notation and proofs, which hindered my understanding of the theoretical guarantees provided by this work. For instance, in Section B.2, it should be "$R(q(\mathbf{y}|\mathbf{x}))$" rather than "$R(q(\mathbf{y}|\mathbf{x})$", yet the authors overlooked such an obvious error. Many similar issues exist, as detailed in Questions.

Citation Issue: I find the citation format in this paper rather unusual. Although this is not a criterion for evaluating the quality of the paper, I still recommend that the authors use \citep{} for citations in LaTeX, rather than \citet{}. The \citet{} command is used when the cited reference needs to be incorporated as part of the sentence.

Experiment Issue: In the experimental section, this work only compares with ERM, which does not convincingly validate the effectiveness of their framework.

• Regarding Novelty: One of my main concerns is the novelty of the proposed method, as the objective function in Eq. (7) appears similar to Eq. (10) in Federici et al., 2021, developed for supervised learning. Although the problem setting differs, the main challenges and how the previous work’s ideas are extended to the setting studied in this paper are not clearly discussed. A more detailed comparison with Federici et al., 2022 would enhance clarity.

• Regarding the Condition in Theorem 1: It is not entirely clear whether the condition $I_{e',q}(x; y \vert y) = I_{e, q}(x; y \vert y)$ in Theorem 1 is achievable. As discussed in line 292 and in the proof, this condition is satisfied when $D_{\text{KL}}(p(z \vert x) \Vert q(z \vert y))$ is minimized. However, in Eq. (7), we are optimizing a regularized version, which might make the condition in Theorem 1 challenging to satisfy. Is the conclusion in Theorem 1 still valid under these circumstances?

• Experiments: I appreciate the authors' efforts in conducting extensive experiments to validate the proposed methods. However, some aspects of the presentation remain unclear:

  • The standard deviations are missing in the tables. For instance, in the Warcraft shortest path task, the performance of SPO under "OOD: ERM" and "OOD: Inv-PnCO" is quite close. It’s unclear whether the advantage of Inv-PnCO over ERM is statistically significant. Including error bars in the results and performing a statistical test would improve clarity.
  • In Figure 3(c), it is interesting to observe that the performance of the proposed method decreases with 5 environments compared to 4 environments, which seems contrary to the remark in lines 319-322. Additional explanation of this phenomenon would be helpful.

• Clarity on Notation: Several important notations are omitted in the main paper, making it difficult to follow. For example, it would be clearer to include the definition of $I_{e,q}(x; z \vert y)$ in Theorem 1 and $\mathcal{L}$ in Theorem 2 directly in the main text.

• The proposed approach is not computationally efficient and therefore may not scale well to typical real-world problems.
• Missing comparison with and discussion of related work on using mutual information based regularization for adversarial robustness [1,2,3].
• The approach depends on a strong assumption about existence of invariant factors whose decision remains invariant across environments.

Minor:

• Citations should be correctly bracketed

[1] Zhu, Sicheng, Xiao Zhang, and David Evans. "Learning adversarially robust representations via worst-case mutual information maximization." International Conference on Machine Learning. PMLR, 2020.

[2] Wang, Tianhao, Yuheng Zhang, and Ruoxi Jia. "Improving robustness to model inversion attacks via mutual information regularization." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 13. 2021.

[3] Zhou, Dawei, et al. "Improving adversarial robustness via mutual information estimation." International Conference on Machine Learning. PMLR, 2022.

As the abstract suggests, since the CO problems has been introduced for a long time, how is Inv-PnCO compared to other previous methods? This paper compares with vanilla ERM only (Table 3, 4, 5), which is a strong drawback. There has been other papers for CO with distribution shift. For example, [1] proposed to use meta learning for better distribution generalization. This paper does not compare to enough SOTA methods.

[1] UNSUPERVISED LEARNING FOR COMBINATORIAL OPTIMIZATION NEEDS META LEARNING. ICLR 2023.

I personally found the paper difficult to follow, mainly due to the writing structure. I would have liked to have seen a more explicit motivation for the impact of this line of work in the introduction / first sections (e.g. concrete real world cases of distribution shift failure for learning to solve COs). However, I am not familiar with this exact research topic, so this could be owing to this.

I am not completely convinced by the impact of the proposed methodology, (this is harder to assess due to the way the paper is written as stated above). For example, in the Grid-world example using a ResNet, how does the method compare to just training the ResNet with simple data augmentations for added visual robustness ? The data sets are all toy, and no standard distribution shift baselines are included as reference.

Note: The paper is not completely anonnymized (link to code contains name of an author), and hence does not follow the 2024 guidelines.