Generalized Smooth Bilevel Optimization with Nonconvex Lower-Level

Thanks so much for your comments and suggestions. We response to your questions one by one as follows:

Q1: What is the meaning of stationary point in this context since the lower level problem is not assumed to be strongly convex?

A1: In our paper, we use the same definition of stationary point as in [1]. From [1], the stationary point of problem (1) is equivalent to that of the relaxed problem $\min_{(x,y)\in \mathbb{R}^d \times \mathbb{R}^q} f(x,y) s.t. \nabla_y g(x,y)=0$. When the lower-level of problem (1) is strongly convex, this stationary point is equivalent to the stationary point used in [2,3].

[1] Liu et al., Moreau envelope for nonconvex bi-level optimization: A single-loop and hessian-free solution strategy. arXiv preprint arXiv:2405.09927, 2024.

[2] Ghadimi, S. and Wang, M. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246, 2018.

[3] Ji, et al., Bilevel optimization: Convergence analysis and enhanced design. ICML, 4882–4892, 2021.

Q2: ... Is it easy to extend PNGBiO to the stochastic setting?

A2: Our PNBiO can be generalized to the stochastic setting. We have initially proved that our stochastic PNGBiO has a gradient complexity of $O(\epsilon^{-6})$. In the final version of our paper, we will add this conclusion. Meanwhile, we add some experimental results on our stochastic PNGBiO (S-PNGBiO) method. Specifically, we compare our S-PNBiO algorithm with other baselines including BO-REF, F^2SA, SLIP, BOME. In the experiment, we conduct the meta-learning task at CIFAR10 dataset, and use Resnet18 as task-shared model at the upper-level (UL) problem, and use a 2-layer neural network as task-specific model at the lower-level (LL) problem. Clearly, both UL and LL problems are non-convex. We run every method for 500 seconds (CPU time) with minibatch size 64 for both training and validation set. We set learning rates as 0.01 at F^2SA and BOME algorithms, and $\alpha=0.0001$, $\beta=0.01$ in SLIP and BO-REF. Our algorithm uses a vanishing step size, which is $\alpha_t=\beta_t=0.3/(k+1)^{0.5}$,$\eta=0.01$, the rest of the parameter settings are the same as in the paper, and the experimental results are shown in the following table (we have recorded the loss):

In the final version of our paper, we will add these experimental results.

Q3: Lines 205-208: The papers claims that the generalized smoothness assumption…, is there any example of such function in machine learning?

A3: 1) When $\rho=0$, our generalized smoothness condition degenerates to standard Lipschitz smoothness condition. 2) When $\rho\in(0,1]$, this smoothness condition depends on the current gradient. For example, the polynomial function $f(x)=|x|^\frac{2-\rho}{1-\rho}$, where $x\in\mathbb{R}$ and $\rho\in(0,1)$, satisfies this generalized smoothness condition. In this case, it does not apply when $\rho=1$.

Q4: Can the convergence result provided by the paper be translated in terms of convergence of the norm the hyper-gradient (equation (2) in the paper) when the inner function is strongly convex?

A4: When inner function is strongly convex, we have proved that our method has the same convergence rate $O(\frac{1}{T^{1/4}})$ based on the hyper-gradient metric as in [1], which shows our algorithm has the same rate of convergence under the generalized smooth condition as the standard smooth condition. In the final version, we will add these results.

[1] Liu et al., Moreau envelope for nonconvex bi-level optimization: A single-loop and hessian-free solution strategy. arXiv preprint arXiv:2405.09927, 2024.

Q5: Some questions of experimental designs.

A5: 1. In the experiments, the tuning parameters of all algorithms are selected to be optimal through the grid.

2. In the data cleaning experiment, the problem is based on unconstrained conditions, so here $R$ should be infinite, and here is a typo.

3. In the algorithms that require inner loops, we set 10 times.

Q6: The partial gradients are denoted with number in subscript while the partial Hessians are denoted with letter in subscript...

A6: In the paper, we have a different definition for the subscripts: 1 and 2 represent the derivatives with respect to the first and second parts, respectively. We will clarify this in the final version of our paper.

Q7: Questions about essay structure, mathematical writing and typos.

A7: Thanks so much for your suggestions. In the final version of our paper, we will correct these typos and mathematical writing, and will reorganize the section 5 of our paper, explaining the main results to make them clearer. Meanwhile, some theoretical results will be added.

Q1: The authors claim that the proposed algorithm solve the generalized-smooth bilevel optimization with nonconvex condition for both upper and lower level but only give an assumption that the lower-level objective function is weakly-convex. Did I miss something?

A1: Thanks for your comment. At the line 19 ( in introduction part) of our paper, we have pointed out that the upper-level problem belongs to the category of general non-convex problems.

Q2: Regarding the experiments, the authors did not conduct the comparison with BO-REP because it consumes a significant amount of memory. But in [1] a similar Hyper-representation task shows that BO-REP have a good ...

A2: Thanks for your comment. Our PNBiO can be generalized to the stochastic setting. We have initially proved that our stochastic PNGBiO has a gradient complexity of $O(\epsilon^{-6})$. In the final version of our paper, we will add this conclusion. Meanwhile, we have added some experimental results on stochastic version of our PNGBiO method. Specifically, we compare our stochastic PNBiO algorithm with other baselines including BO-REF, F^2SA, SLIP, BOME. In the experiment, we conduct the meta-learning task at CIFAR10 dataset, and use Resnet18 as task-shared model at the upper-level (UL) problem, and use a 2-layer neural network as task-specific model at the lower-level (LL) problem. Clearly, both UL and LL problems are non-convex. We run each method for 500 seconds (CPU time) with minibatch size 64 for both training and validation set. We set learning rates as 0.01 at F^2SA and BOME algorithms, and $\alpha=0.0001$, $\beta=0.01$ at SLIP and BO-REF. Our algorithm uses a vanishing step size, which is $\alpha_t=\beta_t=0.3/(k+1)^{0.5}$,$\eta=0.01$, the rest of the parameter settings are the same as in the paper, and the experimental results are shown in the following table (we have recorded the loss):

In the final version of our paper, we will add these experimental results.

Q3: About Theorem 5.10. Seems that the authors give some unusual settings for the stepsize α, β and η, with some complex form of the gradient norm in the iteration t and a variety of parameters instead of the commonly used constant stepsize in other works. Could the authors further explain that what do these parameters stand for and how can these settings make the gradient update stable and efficient as descripted in the end of Section 4?

A3: Thanks for your comment. In our paper, we set the step size as follows: $\alpha_t\in\left(0,\ \frac{||\frac{1}{c_t}\nabla_1\ f(x^t,y^t)||+||\nabla_1\ g(x^t,y^t)||}{4\left(K_1+2K_2+2K_3+\kappa\right)+C}\right)$, $\beta_t\in\left(0,\ \frac{||\frac{1}{c_t}\nabla_2\ f(x^t,y^t)||+||\nabla_2\ g(x^t,y^t)||}{4\left(K_4+2K_4+2K_6+\kappa\right)+C}\right)$, and $\eta_t\in\left(0,\ \frac{\min\{||\frac{1}{c_t}\nabla_1\ f(x^t,y^t)||+||\nabla_1\ g(x^t,y^t)||,||\frac{1}{c_t}\nabla_2\ f(x^t,y^t)||+||\nabla_2\ g(x^t,y^t)||\}}{\kappa_{g_2}\ \max\{4\left(K_1+2K_2+2K_3+\kappa\right),4\left(K_4+2K_4+2K_6+\kappa\right)\}+C}\right)$, where $C=8(1+\frac{1}{\eta_t\kappa_{g_2}})L_\theta^2(L_{gx,0}+L_{gx,1}M^\rho+\frac{2}{\gamma^2})$.

These step sizes are the bounds derived during the theoretical analysis process. It can be considered that during the experimental process, the selection of the step size not only depends on the parameters of the generalized smoothness of the objective function but also relies more on the gradient at the current iteration point. Due to the special structure of the algorithm, it can be viewed in the following form: $x^{t+1}=x^t-\alpha'_t\ \frac{||\frac{1}{c_t}\nabla_1\ f(x^t,y^t)||+||\nabla_1\ g(x^t,y^t)||}{||d_x^t||}d_x^t$, $y^{t+1}=y^t-\beta'_t\frac{||\frac{1}{c_t}\nabla_2\ f(x^t,y^t)||+||\nabla_2\ g(x^t,y^t)||}{||d_y^t||}d_y^t$, where $\alpha'_t\ \in(0,\frac{1}{4(K_1+2K_2+2K_3+\kappa)+C})$，$\beta'_t\ \in (0,\ \frac{1}{4(K_1+2K_2+2K_3+\kappa)+C})$. When $C$ is a constant, it can be regarded as a constant step size, but this depends on the boundedness of $M$.

Q4: Specifically, in section 5 ... these lemmas in the convergence analysis? Also, which lemmas are main novel ones? The description is .....

A4: Thanks for your suggestion. These new lemmas are crucial to our theoretical contributions, and we believe they will provide new insights for research in related fields. In the final version, we will provide a more detailed description of these lemma. We admit that the current description may be too dense. We will reorganize this section, adding more explanations to make it easier for readers to comprehend our arguments and conclusions.

Q1: This paper studied the generalized smooth bilevel optimization relying on the generalized smoothness introduced in [1]. The proposed PNGBiO method could apply the generalized smooth bilevel optimization with generalized smoothness introduced in [2] ?

A1: Thanks for your comment. We study generalized smooth bilevel optimization based on generalized smoothness introduced in [1] based on the following points:

1. The framework of [1] is more compatible with our theoretical foundations and methodology, and facilitates the integration and extension of existing results.

2. The scope of our paper is limited, and focusing on the framework of [1] helps to explore a specific problem in depth and avoid an overly broad scope.

3. We recognize the importance of exploring different broad definitions of smoothness including [2], which will be of interest for future research.

Q2: In the experiments, how to choose the proximal parameter $\gamma$ and penalty parameter $c_t$ in the proposed PNGBiO algorithm?

A2: Thanks for your comment. In the experiments, we set $c_t=\frac{10}{(k+1)^{0.25}}$ , $\gamma=0.1$.

Q3: From Figure 1 in the paper, the proposed PNGBiO method solves the approximated problem (1). In the convergence analysis, the convergence measure used in the paper is reasonable?

A3: Thanks for your comment. The metric in the article is reasonable, as our problem uses two approximations to the original problem, in the metric in this article, we have effectively carved the deviations generated during both approximations to get back to the original problem. Since the lower problem is not (strongly) convex, we could not use the traditional hyper-gradient for the carving, but instead used the residual function for the metric.

Q4: In the convergence analysis, the term $M=\max_{\mu\ \in[0,1]}\|\nabla_1 g(x,\theta_{\mu})\|$ is bounded ?

A4: Thanks for your comment. As you said, in the convergence analysis, $M$ has a bounded gradient paradigm for every fixed $x$. Since our iteration can be terminated in a finite number of times, for $M$ it can take the maximum value within $t$ values. Moreover, $M$ is bounded when the Lipschitz smoothness condition is satisfied for $x$ in the lower function.

Q1: Using the same parameter $M$ to denote two different terms in the convergence analysis (at lines 240 and 266) could indeed be a typo or an oversight in notation.

A1: Thanks for your comment. There is a typo. We will correct it in the final version of our paper.

Q2: Since the normalized gradient plays a crucial role, could you provide a more detailed explanation of its purpose and necessity?

A2: Thanks for your insightful comment. Inspired by the paper [1], the generalized smoothing condition implies that the smoothness is unbounded, i.e., it depends on the gradient information at a certain point. During the iteration process, too large changes may produce too large or too small gradients, making the algorithm unstable and inefficient. Normalization can effectively solve these problems, making it more robust and faster convergence. Thus, in our algorithm, we use the normalized gradient descent iteration.

[1] Chen, Z., Zhou, Y., Liang, Y., and Lu, Z. Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization. In International Conference on Machine Learning, pp. 5396–5427. PMLR, 2023.

Q3: In the PNGBiO algorithm, how to choose the parameters $\gamma$ and $c_t$ in the experiments?

A3: Thanks for your comment. In the experiments, we set $c_t=\frac{10}{(k+1)^{0.25}}$ , $\gamma=0.1$.

Q4: This paper studied the nonconvex bilevel optimization with the generalized smoothness introduced in (Chen et al. 2023 ). Why not consider the nonconvex bilevel optimization with the generalized smoothness in (Li et al., 2023) ?

A4: Thanks for your comment. We chose to study the generalized smoothness nonconvex bilayer optimization proposed in (Chen et al. 2023) based on the following points:

1. The framework of (Chen et al. 2023) is more compatible with our theoretical foundations and methodology, and facilitates the integration and extension of existing results.

2. The scope of our paper is limited, and focusing on the framework of (Chen et al. 2023) helps to explore a specific problem in depth and avoid an overly broad scope.

3. We recognize the importance of exploring different broad definitions of smoothness including (Li et al., 2023), which will be of interest for future research.

Q5: In Table1, the first $g(\cdot,\cdot)$ should be $f(\cdot,\cdot)$.

A5: You are right, we will correct this typo in the final version of our paper.