Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes an algorithm that solves bilevel optimization problem in an asynchronous distributed manner. The iteration complexity for the algorithm to obtain $\epsilon$-stationary point is upper bounded by $\mathcal{O}(\frac{1}{\epsilon^2})$. Empirical results show that under asynchronous setting, the proposed algorithm outperforms state-of-art distributed bilevel optimization algorithm. 
strength_and_weaknesses: Strength:
1. Strong empirical results with theoretical analysis

Weakness:
1. Redundant formulation compare to other bilevel paper, which makes it hard to read, especially when explaining how cutting plane works.
2. Insufficient references. There are works on asynchronous distributed optimization that are not included in this paper. For example, https://ieeexplore.ieee.org/ielaam/6884276/8350883/7903733-aam.pdf. There are also many works asynchronous federated learning, and probably needed to be included here.
3.  What is the value of $\tau$ in the experiment?
4. In the appendix, I don't quite follow the logic from eqn 57 to eqn 58. Can you please explain more?
5. I don't understand from optimization perspective, why this algorithm can outperform other algorithms in asynchronous setting. From Theorem 2, the larger $S$ is, then the less number of iterations is needed. For experiment, what if you run other synchronous algorithms (e.g. SDBO) in the same setting of ADBO, i.e. that the master problem will update its variable once it receives updates from $S$ workers. Will ADBO still outperform SDBO? 
clarity,_quality,_novelty_and_reproducibility: This paper is original and novel. However the written part needs to be improved.
summary_of_the_review: I think this paper is marginally below the acceptance threshold. Please see the weakness part for my reasoning. I think the authors need to revise the written to make the problem formulation/algorithm more neat and easier to follow.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Bilevel optimization problems, in which one optimization problem is nested within another, occur in multiple machine learning applications such as hyperparameter optimization. The paper considers a generic distributed bilevel optimization problem and proposes a novel asynchronous distributed algorithm. The proposed algorithm is guaranteed to converge to an \eps-stationary point in O(1\eps^2) iterations in a distributed setting. 
strength_and_weaknesses: Strengths:
+ The paper addresses a timely problem and provides a novel algorithm.
+ It’s interesting that the centralized version of the same algorithm also yields the optimal convergence rate in the centralized setting.

Weaknesses:
- The paper is a bit dense and I feel that the presentation could be improved significantly. Currently section 3 serves as a large unbroken block of equations, and readability would be improved if it were broken down further. For instance, divide the main algorithm into phases and describe the steps to estimate \phi(v) [Equations 5-9] and the steps to describe and generate the cutting planes separately. Even the paragraph on page 2 regarding the reformulation as a consensus problem feels out of place there - I would much rather see it at the beginning of section 3.

clarity,_quality,_novelty_and_reproducibility: The proposed approach is novel to the best of my knowledge and makes a useful contribution. As mentioned earlier, the paper is a bit dense and I found some of the math a bit hard to follow. Appendix A on the centralized version of the same algorithm is much cleaner and still retains most of the key ideas of the paper - a possible rewrite would be to focus on the centralized version first and then explain the differences in the distributed setting.

The paper includes experimental results in two settings - (i) data hyper-cleaning [classification with noisy labels] and (ii) regularization coefficient optimization on two specific datasets each. The paper would benefit from a discussion of why those specific datasets were chosen (for instance, do the results differ on CIFAR-10/100 instead of MNIST?). Also the paper does not provide enough details for easy reproducibility - making the code available would go a long way.

summary_of_the_review: Overall, the paper tackles an interesting problem and the proposed algorithm is novel and provides the first general framework for solving distributed bilevel optimization problems in an asynchronous setting. The empirical analysis, while limited, also shows promising results.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposed an asynchronous method for distributed bilevel optimization. The proposed method can tackle both nonconvex upper-level and lower-level objective functions. Convergence analysis has been provided.
strength_and_weaknesses: Strengths:
1. The proposed method is clearly explained and theoretically analyzed. 
2. Experiments have some promising results.

Weaknesses
1. The reason for asynchrony should be better explained, possibly with some real-world use cases. Actually, it has been observed that asynchrony may not be the best choice in distributed training, because it uses out-of-date (i.e., stale) gradients to update models. This staleness often results in degraded performance. Therefore, several state-of-the-art methods still use synchronous methods to achieve strong empirical performance, with some simple tricks such as large batch size, warmup, layerwise adaptive learning rates, and gradient compression (see reference [1-5] from below). I think this tradeoff between synchrony and asynchrony should be properly discussed.
2. Following the first point, the authors is encouraged to consider how to resolve the staleness issue due to asynchrony. This could further enhance this paper.
3. The experiments are conducted on two applications of bi-level optimization: hyper-cleaning and regularization coefficients optimization. I think bi-level optimization has received great attention these days mainly because of some emerging applications such as meta-learning, neural architecture search and etc. The authors are encouraged to consider these applications (e.g., meta-learning, neural architecture search) in the experiments.  

Reference:     
[1] Goyal, Priya, et al. "Accurate, large minibatch sgd: Training imagenet in 1 hour." arXiv preprint arXiv:1706.02677 (2017).   
[2] You, Yang, et al. "Large batch optimization for deep learning: Training bert in 76 minutes." arXiv preprint arXiv:1904.00962 (2019).   
[3] Huo, Zhouyuan, Bin Gu, and Heng Huang. "Large batch optimization for deep learning using new complete layer-wise adaptive rate scaling." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 9. 2021.    
[4] Liu, Rui, and Barzan Mozafari. "Communication-efficient Distributed Learning for Large Batch Optimization." International Conference on Machine Learning. PMLR, 2022.    
[5] Wang, Tong, et al. "Large Batch Optimization for Object Detection: Training COCO in 12 minutes." European Conference on Computer Vision. Springer, Cham, 2020.    
clarity,_quality,_novelty_and_reproducibility: Look good to me
summary_of_the_review: The paper proposed an interesting method. But I would appreciate it if the authors could address my above concerns.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposed an asynchronous algorithm for Distributed Bilevel Optimization (DBO) that theoretically achieves an $O(1/\epsilon^2)$ convergence rate and achieves good empirical performance. The main complaints from the reviewers are (1) poor writing in the main text and (2) outdated applications in the experiments. The authors have sufficiently addressed both concerns in their revision. I believe this is a solid paper, and the revision has improved significantly over the initial draft. For that reason, I would vote for acceptance of this paper, but I won't be upset if this paper undergoes another round of reviews at a future conference, because it is also reasonable that a significant revision must go through another round of peer review, as is common in journal reviewing process.
justification_for_why_not_higher_score: NA
justification_for_why_not_lower_score: NA
Decision: Accept: poster