Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the optimization landscape of the H_inf control problem. It is shown that all Clarke stationary points are global minimal even though H_inf is nonconvex. Further, a  Goldstein subdifferential method is proposed and shown to stay in the nonconvex feasible set and eventually reach a global optimal solution.
strengths_and_weaknesses: H_inf control is an important robust control problem and is worth being studied, especially from the learning perspective. The optimization landscape results in this paper are significant. The Goldstein subdifferential method can guarantee the iterated control policies to stay in the nonconvex feasible set and eventually reach a global optimal solution. Further, the limitations of the Goldstein subdifferential method is discussed and implementable variants are proposed.

The major weakness of this paper is that no numerical evaluation is provided.
questions: Please add some numerical evaluation.
limitations: Yes
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers the problem of direct policy search in the optimal $\mathcal{H}_\infty$ control framework. $\mathcal{H}_\infty$ control is an important framework in the robust control literature, but the problem of finding the optimal controller is challenging because it is a constrained nonconvex nonsmooth optimization problem. In this paper, the authors first study the landscape of the optimization problem to show the existence of a unique global minimizing set and any Clarke stationary points are global minimum. Then, they show a direct policy search method, the Goldstein subdifferential method, can stay in the feasible set and find a global optimal state-feedback controller.
strengths_and_weaknesses: Strength: This paper makes a significant contribution to the interdisciplinary field of robust control and machine learning. Although similar results about the convergence of direct policy search exist in the literature of $\mathcal{H}_2$ control and mixed $\mathcal{H}_2/\mathcal{H}_\infty$ control, the authors discuss the difference between these settings clearly at the end of the Introduction. After reading the discussion, I believe the problem considered in this work is fundamental and challenging. This paper is also well-written and easy to follow in general.

Weakness: In Section 4.2, the authors mentioned that the minimum norm element of the Goldstein subdifferential $F^n$ can be difficult to evaluate in practice. However, the convergence result in Theorem 2 does not consider the potential error/noises when evaluating $F^n$ and perform the update. Further, Theorem 2 only provides an asymptotic convergence guarantee rather than a finite time error bound. Since the page limit is 9 pages, some contents in the appendix (e.g., the algorithm to evaluate $F^n$) can be moved into the main body.

In conclusion, I feel the strength of this work outweighs its weakness. This work is a very meaningful initial step towards more general convergence results.

questions: I encourage the authors to add a more detailed discussion about the future directions of this work. Despite a more general convergence bound, it will also be interesting to see if the linear time-invariant system and the time-invariant quadratic cost functions considered here can be generalized to more general dynamics/costs.
limitations: The authors discussed a limitation when practically implementing their algorithm in the last section, and proposed several potential solutions. I do not see any potential negative social impacts of this work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper establishes asymptotic convergence for Goldstein's method for H-infinity policy search. On the plus side, it does so with elegant topological and optimization-theoretic arguments. A negative, however, is that the rates are non-quantitative, and it is not clear how the complexity of implementing the optimization would depend on problem parameters.
strengths_and_weaknesses: I am torn about this paper; I thoroughly enjoyed reading it. I think it was excellently written, the proofs were clear and correct, and balanced concision with transparency perfectly. The fact that the results were purely qualitative made the paper easy and enjoyable to read. Were I asked to review this paper for an optimization or control journal, I would enthusiastically support acceptance. 

I think the weakness of this paper is that, the NeurIPS theory community comes out of the learning theory tradition, where one cares about finite sample/iteration rates that reflect how problem parameters reflect the complexity of solving a problem. For example, many of the main papers on policy search for H2 control stress polynomial dependence in dimension, norms / bounds on various problem parameters, and on desired accuracy. 

In this paper, the rates are purely asymptotic. Moreover, the algorithm requires the computation of a minimal norm element Goldstein differential, which may potentially be computationally prohibitive, especially if it requires sampling arbitrarily adversarial non-convex functions. Therefore, it is unclear to me whether even a single step of the proposed algorithm can be implemented efficiency (say, where the number of samples is poly(d,e,log(1/delta)). I did appreciate the authors discussion of the various implementation choices, and that level of specificity may be appropriate for other communities. But I think that for NeurIPS the author must convince the reader that the algorithm can be implemented efficiently in the sense that it can be performed in number of iterations / sampling calls which are polynomial in relevant problem parameters.

Similarly, the final guarantee in Theorem 2 is asymptotic, not giving a sense of rates.

EDIT: The authors have addressed the majority of my concerns, and I am increasing my score to a 7.
questions: 1. Can the authors remark on the computational complexity of the sampling methods referred to in [49,13], and well as the zero-th order methods [9,10,31]? Do the authors conjecture that these methods could be implemented with samples scaling polynomially in relevant parameters?

2. Is there a way to bound the minimal separation between K_0 and K, Delta_0, in terms of a more natural problem quantity?

3. Can the argument of Theorem 2 be modified to given quantitative bounds for finite iterations?
limitations: As noted, the guarantees are non-quantitative and hence I am not sure if this is a good fit for NeurIPS. 

However, I can be convinced! - if the authors can show precedent for similarly qualitative optimization papers (or if my fellow reviewers can), then I will be inclined to increase my score because I did enjoy this paper. 

EDIT: After reviewing the author changes, most of my concerns regarding the computational infeasibility of finding approximate Goldstein differentials have been allayed. I am raising my review to a 7. I am tempted to give the paper an 8, but I am still concerned that the Delta_0 quantity is a little mysterious, and may hide nasty problem-dependent factors. Still the authors  should be proud of their excellent submission, I hope to see this in the program.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors study direct policy optimization for finding the minimal $\mathcal{H}_\infty$-norm stabilizing controller. They prove various analytic properties about the landscape of policy optimization such that a Goldstein subdifferential method converges in function value to the global minimum. While the Goldstein subdifferential method can be difficult to implement, they also discuss various sampling based strategies for finding the minimum norm subdifferential.
strengths_and_weaknesses: **Strengths:**
- The paper is written very clearly and concisely. 
- The result is elegant. 
- The proofs are clean and read quite nicely.

**Weaknesses:**

- The main result is asymptotic (Theorem 2 does not give any rates of convergence). 

- It is acknowledged that computing the minimum norm subdifferential is challenging (see e.g. Line 317), but the sampling algorithms to address this are discussed mainly in the appendix. The authors present several implementation schemes, but it is not clear as a reader which one to prefer. 

- An end to end statement combining Theorem 2 and any one of the sampling schemes to give a result on a practical algorithm is not clearly stated in the paper (although can possibly be inferred from the discussion in Appendix C). 

- The algorithms listed in the appendix (Algorithm 1,2,3,4) all require function evaluations of the form $J(K)$, which involves computing the $\mathcal{H}_\infty$-norm of the system in feedback with a given $K$. Without access to the system dynamics $(A, B)$ (which is the whole point of studying policy search methods otherwise the $K^*$ can be computed via an SDP as noted in Lines 124-126), it is not clear how one computes $J(K)$, even with access to a simulator.

- There are no experiments showing the effectiveness of the proposed algorithms.

**Recommendation:**

In light of these weaknesses, I am not sure about the immediate impact/relevance of this paper beyond a small niche in the NeurIPS community. Nevertheless, it is a nice result from a mathematical point of view which in my opinion warrants an accept. The one caveat is that I am not that familiar with the nonsmooth optimization literature. Hence, while the results appear novel to me, if a reviewer who is more knowledgable in this area disagrees, then I would reconsider my recommendation based on said reviewer's arguments.

**EDIT:** After reviewing the author's responses and draft, I raised my score from 6 to 7. 
questions: - As a point of clarification, is there a unique minimum $K^*$ for problem (6), or are there possibly many global minima? 

- Can the authors discuss the barriers to removing the $Q$ positive definite assumption and replacing it with a more standard $(A, Q^{1/2})$ is observable assumption?

- For the proof of Theorem 1, I am curious why the first case assuming $J’(K^{\dagger}, d) > 0$ is necessary. What is insufficient with the following argument: suppose $K^{\dagger}$ is a Clarke stationary point, but $K^{\dagger}$ is not a global minimum and hence $J(K^{\dagger}) > J^*$. In this case, Lemma 3 guarantees the existence of $d \neq 0$ such that $J’(K^{\dagger}, d) < 0$. However, by the subdifferential regularity of $J$ (Proposition 2), we know that $J’(K^{\dagger}, d) \geq 0$ for all $d$, hence a contradiction. 

- Theorem 2: consider stating that $\delta^n = \frac{c \Delta_0}{n+1}$ for some $c \in (0, 1)$ instead of setting $c = 0.99$. The proof still goes through, but this would allow you to underestimate $\Delta_0$.

- Theorem 2: how do you compute (or estimate) $\Delta_0$? 

- Theorem 2: Does $K^n \rightarrow K_\infty$ with $K_\infty \in \mathcal{K}$? The theorem is a statement about the function values, but is it possible for the $K^n$’s to not converge? This is related to my question about uniqueness of $K^*$. 

- Theorem 2: Can one obtain a rate of convergence on $J(K^n) \rightarrow J^*$?

limitations: Some limitations are already discussed in weaknesses. 

Also, the authors point out that their work only applies to the full state observation case, with partial observability needing future work. This is not an issue for me, as I see the partial observability case as follow up work.
review_title: null

Meta-review: metareview: The paper analyses direct policy search as an algorithm in H_inf control synthesis specifically for the problem of minimizing the H_inf closed-loop norm and show that it can achieve global optima. The authors observe that this is a constrained nonconvex nonsmooth optimization problem and by studying the landscape the landscape establish the existence of a unique global minimizing set and any Clarke stationary points are global minimum. They further propose using the Goldstein subdifferential method and show it can stay in the feasible set and find a global optimal state-feedback controller.

Overall the reviewers strongly appreciated the contribution and clarity of the paper. Some reviewers raised the concern of asymptotic vs non aymptotic results but were eventually satisfied by the author response, which highlighted bounds for delta, epsilon stationary points and the subtlety of delta, epsilon stationary points not being close to the global minima. There was unanimous agreement between reviewers that the paper would be a strong contribution to the conference and hence I recommend acceptance. 
confidence: Certain
Decision: Accept