Query Efficient Nonsmooth Stochastic Black-Box Bilevel Optimization with Bregman Distance

1.The strong convexity assumption has been extensively studied for BLO. The authors should lay importance on the difference of the used techniques for establishing complexity bound for black box BLO.

2.The stationarity measure $\|G^t\|$ lack explanation. It is important for the authors to justify that the used measure is equivalent to the compared methods.

• The practical applicability of bilevel optimization with both inner and outer levels as black-boxes was largely not motivated by the authors. While some specific bilevel problems can have partial black-box structure, many practical applications in machine learning (such as hyperparameter optimization, meta-learning, etc) involve inner-level variables that represent the parameters of deep neural networks. In such cases, using zeroth-order methods to solve the inner problem would be extremely slow and may not even converge.

• The choice to employ ZO techniques to solve both the inner and outer levels restricts the scalability of the approach, which may explain why the experimental validation was limited to small-scale toy tasks. Thus, the method’s suitability for real-world BO problems remains questionable, especially in deep learning context.

• The experiments are very limited with only two compared baselines (that are not particularly strong for these experiments). In fact, HOZOG [1] was introduced especially for hyperparameter optimization (where $x$ are the hyperparameters and $y$ is the parameters of possibly a deep neural network), in which it can be a strong baseline. However, the authors used it here in settings for which HOZOG is not the most adequate baseline, which I believe is unfair and undermines the validity of the results.

• The literature review on bilevel optimization is sparse and does not adequately cover recent, relevant works. For instance, PZOBO [2], another hessian-free ZO method, is neither discussed nor compared against, despite its direct relevance. The paper also lacks a discussion on extensions or limitations of the proposed approach in the broader context of BO, such as bilevel problems without lower-level singleton constraint. This would be essential to clarify where the proposed method fits within the current landscape of BO approaches and where it may fall short or require adaptation.

Other minor issues:

• The inner objective $g$ is smooth and this should be explicitly said after the problem definition, just like the authors did it for the outer objective function $f$.

• In the text, the authors keep mentioning that using ZO gradient for the inner level problem is not the most efficient thing, but their algorithm did exactly use that (equation 14).

References:

[1] Bin Gu, Guodong Liu, Yanfu Zhang, Xiang Geng, and Heng Huang. Optimizing large-scale hyperparameters via automated learning algorithm. arXiv preprint arXiv:2102.09026, 2021.

[2] On the convergence theory for hessian-free bilevel algorithms. D Sow, K Ji, Y Liang - Advances in Neural Information Processing Systems (NeurIPS), 2022.

1.The subproblem related to updates of $x$ may be difficult for some Bregman distance, especially when the structure of $h(x)$ is unknown or complex.

2.The theoretical convergence analysis of this method relies on several strong assumptions like strong convexity of the lower-level, which may not be met in most practical applications. This can consequently affect the actual performance of the algorithm.

3.Although Gaussian smoothing can approximate the gradient, the additional errors introduced at each iteration may accumulate. Although it can converge to a solution in expectation, it may still be far from the solution after multiple iterations due to a large variance.

The assumption of Lipschitz continuity in Assumption 2 appears inconsistent with strong convexity; further clarification is needed on why this assumption holds in the given setting.