On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation

1. Prop 3.1. How to get Prop. 3.1 from Thm. E.3? How does the additional ${\rm Span}(\,...\,, \nabla_y f(x,y^*))$ appear?
2. Thm. 3.2. Can we derive the explicit form of $\nabla \psi(x)$? Or we can only define it implicitly as the limit of $\nabla \psi_{\sigma}(x)$ when ${\sigma \rightarrow 0^+}$?
3. Appendix E.6. Proof of Thm. 3.6. After "Then, since we have Assumption 1, we get", why we have $2 (g(x,y_{\sigma}^*) - g(x,z_p^*)) \ge \mu \Vert y_{\sigma}^* - z_p^* \Vert^2$. It seems like the QG condition in Karimi et al. (2016), but it seems like this reference only shows that it can be implied by the PL condition in the unconstrained case. But how we can get this in the constrained case?
4. Proof of Thm. E.3 in Appendix. Why we always have $\Omega(\delta) v = \nabla^2_{\theta w} f(w,\theta^\ast) {\rm d}w$? What if $\nabla_{\theta w}^2 f(w,\theta^\ast)$ is zero, then the RHS is also zero?
5. Appendix B.2. Can the authors explain more about the necessity of using the Moreau envelope? What is the benefit of using the Moreau smoothing? What will happen if it is not used? Sorry, I don't fully understand the technical challenge 1. Why it fails if one simply estimate the value of $(\lambda^*,\nu^*,y^*)$ for a given $x$ and plug into the expression of $\nabla \psi_{\sigma}(x)$ in Thm. 3.2?

• Assumption 1: Was this assumption considered in previous work? Moreover, the quantifiers are unclear: "satisfies (4) for all $y$ that satisfies... with some positive $\mu,\delta,\sigma_0$". Do you mean that there exist $\mu,\delta,\sigma_0$ so that $y$ satisfies... implies (4)? This should be properly revised.
• Assumption 3 vs. 4: It is assumed that $f,g\to\infty$ as $\|y\|\to\infty$, but then that $\|y\|\leq O(1)$. Why aren't these in contradiction to one another?
• Assumptions 5-8: As previously mentioned, can the authors elaborate on these assumptions? They are not well-enough motivated. Statements such as "Assumption 6 helps ensure that the active set does not change when ... is perturbed slightly" seems to suggest the desired consequence is almost assumed in the first place. Also, in particular, is Assumption 7.1 standard? It seems strong, and I am not aware of such an assumption in previous works (I may be wrong, though would like the authors to clarify).
• High-level remark: I am not sure whether the authors decision do defer the entire algorithmic aspect of the paper to the appendix is preferable. Of course I acknowledge the strict page quota, and this may be inevitable in a lengthy work such as this, but it seems unsatisfactory that the only result mentioned in the main text is Theorem 3.6, which remains rather un-motivated without the algorithmic contribution. This becomes most clear in the conclusion, when the authors mention that their algorithm is simple, general, useful etc., though the reader did not encounter it at all in the main text. For the author's consideration.

minor comments:

• 1st paragraph after (P): "continuously differentiable and smooth" - are these synonymous?
• "since this issue is fundamental" - this phrasing is unclear, I suggest explaining what this means (possibly informally).
• Throughout the paper only \citet is used, while \citep is more adequate whenever the work is not part of the sentence.
• Theorem 1.1 (Informal): the phrase "at least one sufficiently regular solution path exists" is unclear at this point. What is even a solution path (not previously mentioned or defined)?
• mean squared smoothness condition mentioned without definition or ref. For example, the authors can add "(as formally defined in Section ...)".
• typo: to appendix = to the appendix.
• Assumption 2 involves a norm, which only later on (in the notation paragraph) is explained to be the operator norm. This should be clarified beforehand.
• The normal cone is mentioned without definition, I suggest adding a brief reminder (even in a footnote, for example).

1. Title: What do you mean by "first-order stochastic approximation"?
2. Page 2: The third paragraph states that there are results under the uniform PL condition, which seemed to imply that there is a method for the PL condition, but the next paragraph claims that there is no algorithm finding the stationary point under the PL condition. Could you clarify this?
3. Page 2: In the fourth paragraph, how about making the term "landscape" more specific? It was not clear to me here, although it becomes clearer later.
4. Page 3: How about adding "small-error" in front of the "proximal EB"?
5. Page 3: It is implied that Assumption 1 guarantees the local Lipschitz continuity of solution sets (Assumption 5), but it seems that it is not explicitly stated (with proof) anywhere.
6. Page 3: PL and proximal EB conditions are almost identical, and you only assume the proximal EB within the neighborhood of solutions. Then, how were you able to get an improved rate over existing rate for the PL condition? Most of the explanations of the algorithm are deferred to the appendix, and it was not clear for what reason that the proposed algorithm is more efficient even with weaker condition. Could you comment on this?
7. Page 7: How does Assumption 6 help the active set to not change much?
8. Page 7: I was not able to follow Proposition 3.1 and its corresponding explanation. Could you help me better understand the context?
9. Page 9: Can Theorem 3.6 be proven with Assumption 5 rather than Assumption 1?

A couple of typos:

• Section 3.3. first line: “via finite differentation” —> “via finite differentiation”
• Section 3.3. “we can apply mean-value theorem” —> “we can apply the mean value theorem”
• If you check, on both page 3 (below Assumption 1) and page 8, you use the sentence “the crux of assumption 1 is the guaranteed (Lipschitz) continuity of solution sets”
• Page 8: “With a more standard assumption on the uniqueness of the lower-level solution and the invertability ” —> “invertibility” ?

Page 1/2

• You first introduce formuation (P) then you introduce formulation P_con which to me is exactly equivalent to P, isn’t it ? If it is, I would not relabel it but simply emphasize the equivalence between P and this formulation. There are already many formulations. If some of those are exactly equivalent (like I suspect it is the case for P and Pcon, I would not introduce additional notations)
• Finally you introduce a relaxation of the constraint in P_pen. intuitively, we understand that for sigma small enough, this relaxation should recover P_con and this is what you formalize by introducing appropriate conditions. So far, this is clear. What I find less clear is the sentence “Although finding the solution of (Ppen) is a more familiar task than solving (P) ”. For small \sigma, from Theorem 1.1., there must be some conservation of difficulty (at least for some \sigma). It would be helpful to have some more intuition on that (one or two sentences). I.e. it seems miraculous to end up with a formulation that suddenly becomes so much easier so solve.

Page 2

• In the formulation P_{pen}, I don’t really understand how you can know the value of min_z g(x, z) while you don’t have any explicit solution for min_y g(x, y). This should be commented

Page 3

• The result of Theorem 1 is clearly interesting but it could be expected that a smaller value of sigma would enforce more weight on the penalty and hence ultimately recover the solution to (1)
• You should define the notion of epsilon-stationnary point. In particular What is the meaning of epsilon in regard to sigma. When you introduce the notion of epsilon-solution you seem to replace the sigma in psi_sigma by the epsillon, but then the two appear simultaneously when discussing the oracle complexity
• You use the terms “complexity” and “oracle complexity” before clearly defining them. Are you talking about the number of iterations/steps? If yes, this should appear somewhere. The notion of “oracle complexity” is also used in a number of different settings. What are the oracles you are referring to ? What function classes are you considering. This is not self contained (at least on page 3). I can see you clarify this in the statement of Theorem 1.2. but it should appear earlier. In fact I’m wondering if you should not put Theorem 1.2 before Theorem 1.1. Also, is your oracle only given by the noisy/stochastic gradient or do you also assume access to the value of the function? The information that appear in section 3.4. should appear way earlier.
• What do you mean by the sentence “Assumption 1 holds only in a neighborhood of the lower-level solution ” ? do you mean that Theorem 1.1. only requires Assumption 1 to hold in a neighborhood of y^* ? Then you should clarify this in the statement of Theorem 1.

Page 4

• You mention the mean-squared smoothness condition before defining it. Either include it in the main part of the paper or remove the second part of the Theorem. The sentence “fully single-loop manner” is also unclear so I would be in favor of removing the second part of the Theorem (at least from the main body of the paper)

Page 5

• Why not use V for the value function and Y for the solution set ?
• In section 3, we don’t really understand what you are doing
• I think you can spare some space by removing the definition of Lipschitz continuity from the main body of the paper (this is a relatively well known concept and it would free some space for some other (perhaps more crucial) explanations — see my other comments)

Page 6

• I would be in favor of a couple of additional explanatory sentences in Examples 1 and 2. E.g. just clarify the definition of S(x), i.e. S = {-1,1} except at 0 where it is the whole [-1,1] interval, or recall the definitions of S and psi
• The whole introduction in section 3 is confusing. It is not really clear what you are trying to do do until the last sentences. I.e. we understand you want to show examples in which \nabla \psi(x) \neq \lim_{\sigma\rightarrow 0} \nabla \psi_{\sigma}(x). But it is not completely clear why, especially given that you seem to already have introduced in assumption 1, a condition that ensures that \nabla \psi_{\sigma} can be made arbitrarily close to \nabla \psi.
• Under example 2, when you mention the continuity of the solution set. Do you mean continuity with respect to x ?
• Before introducing examples 1 and 2, I would add a sentence insisting on the fact that in both examples, the non existence of $\nabla \psi$ comes from the discontinuity in $\psi$. Also I known you don’t have much space but it would help to have a plot of the solution sets for both examples (or perhaps briefly mention the solution sets for both cases ? This would help clarify the fact that the set is )

Page 7

• Although technically correct, the term “kernel” in the setence “the kernel space of the Hessian …” before Theorem 3.2. can be confusing especially in ML related papers. I would use nullspace instead of kernel space.
• The central part of section 3, i.e. the part that connects this section to Theorem 1.1. is Theorem 3.2. This theorem should appear way earlier or at least you should clearly explain that you derive the conditions appearing in Theorem 1.1. I would rewrite section 3 as follows. Start by clearly indicating that you will derive conditions for the second relation in Theorem 1.1. to hold (i.e. the fact that \nabla \psi_{\sigma}(x) is a O(\sigma) approximation of \nabla \psi)
• I would rewrite section 3.1. by giving more intuition on how you derive assumption 6. Just a couple sentences of explanation. (I think readability of the paper would benefit from for example, removing the definition of Lipschitz continuity and replacing it with a more elaborate explanation of the derivation of assumption 6)
• I would remove Proposition 3.1 or I would make it simpler. The proposition is not clear and neither is its connection to the rest of the paper or its explanation (i.e. Geometrically speaking, perturbations in … ).

Page 8

• I would simplify section 3.3.

Q1. What is the relationship between the $\epsilon$-stationary point of $\psi_{\sigma}(x)$ and the $\epsilon$-KKT solution of the constrained single-level problem $P_{\mathrm{con}}$? Theorem E.5 establishes a one-directional relation. Is the converse of Theorem E.5 also valid? Note that in Theorem E.5, the $\epsilon$-KKT solution of $P_{\mathrm{con}}$ should be a pair $(x, y)$.

Q2. Could the requirement of boundedness for $\max_{x\in\mathcal{X},y\in\mathcal{Y}} |f(x,y)|=O(1)$ be relaxed or made less restrictive?

Minor Comments:

(1)On page 3, Theorem 1: It would be beneficial to clarify the meaning of $y^*(\sigma)$.

(2)On page 4, Assumption 3: Is it redundant to consider the coercivity of both $f(x,y)$ and $g(x,y)$ as $|y|\rightarrow\infty$, given that $\mathcal{Y}$ is bounded according to Assumption 4?

(3)On page 7, Definition 7: Does $\lambda_{\mathcal{I}}$ implicitely depend on $y$ in Equation (8)? What is the domain of $\mathcal{L}_{\mathcal{I}}$?

(4)On page 7, Equation (9): There is a period missing at the end of Equation (9).

(5)On page 9, Assumption 8: Does Assumption 8 implicitly assume that the active set does not change?

(6)On page 17, Equation (13): There is a period missing at the end of Equation (13).

(7)On page 18: check the definition of $g_{xy}^{k,m}$ and $g_{xz}^{k,m}$.

(8)On page 19, C.1, Definition of $\Delta_k^z$: “$\rho g(x, \cdot)$” should be “$\rho g(x_k, \cdot)$”.

(9)On page 22, Equation (21): “$D_v \ell^*(x)$” should be “$D_v \ell^*(w)$”.

(10)On page 27, Proof of Theorem 3.6, Line 8 from below: Should $\sigma C_f$ be replaced with $2\sigma C_f$?

(11)On page 27, Proof of Theorem 3.6, Line 4 from below: $\mu_g$ should be replaced with $\mu$.

(12)On page 30, Proof of Theorem E.5: It appears that in the last step of the proof, $g(x,y) - g^*(x)$ is bounded by $O(\sigma^2)$. Would this observation be useful for improving the convergence rate?

(13)On page 30, Equation (28): There is a period missing at the end of Equation (28).