- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The computational cost of formally verifying neural Lyapunov functions is investigated. Rather than addressing how a Lyapunov function is learned, the work focuses on the subsequent formal verification step. The considered verifiers use branch-and-bound over axis-aligned boxes together with different bounding methods. The authors state that verification cost can be separated into a frontier component, which depends on the geometry close to the maximal certifiable level, and a bulk component, which is characterized through a so-called certified radius. The analysis is demonstrated on systems with two to six continuous state variables.
Critical strengths
-
Deriving the computational cost of formal verification is a relevant research direction.
-
The distinction between a frontier cost and a bulk cost is somewhat interesting.
-
The experiments demonstrate the difference between per-clause and conjunction-aware verification.
-
According to the experiments, useful predictions of the cost for the investigated certificates are obtained.
Critical weaknesses
-
The relevance of the contribution to machine learning and, consequently, to ICLR is not obvious. The paper itself states that what makes a learned Lyapunov certificate trustworthy is the formal check that follows training, which is the topic studied in this paper. Thus, the main contribution seems much closer to formal verification and computational geometry than to machine learning and probably better fits to conferences such as Computer Aided Verification (CAV).
-
All results are tied to a particular class of verification algorithms. The paper demonstrates that a different verification strategy can substantially alter the picture and the derived computational complexity is unfavorable as the number of continuous state variables increases. However, if this scaling is mainly a property of the selected algorithm and its axis-aligned representation, the natural conclusion appears to be that this verification approach should be replaced by algorithms that scale better with state dimension. In that case, the presented complexity characterization may become much less relevant once another verification algorithm is used.
-
A complexity result for the underlying certification problem itself would be substantially more relevnt. A lower bound that applies independently of a particular verifier or set representation would remain relevant when verification algorithms improve. In contrast, characterizing the cost of a specific branch-and-bound architecture risks characterizing a limitation of current implementations rather than a fundamental difficulty of certification.
-
Other set representations are extensively used in verification and reachability analysis, including polytopes, zonotopes, and constrained zonotopes. Such representations can capture correlations between state variables that axis-aligned boxes cannot. The manuscript does not establish how its conclusions change when such representations are used. Consequently, it is difficult to determine which part of the reported dimensional dependence is inherent to the problem and which part results from the selected representation and subdivision scheme.
-
Also, reachability analysis is largely absent from the discussion. This is surprising because the objective is ultimately to establish properties of the trajectories of a dynamical system. The paper should discuss how the proposed complexity analysis relates to reachability-based verification and under which circumstances neural Lyapunov verification is expected to be computationally preferable.
-
The system class is somewhat restrictive. The theoretical setting assumes discrete-time dynamics. However, many technical systems are naturally modeled by differential equations. It is unclear whether the proposed frontier and bulk analysis can be transferred to continuous-time systems.
-
The paper is rather difficult to read. Several substantial mathematical ideas are introduced in quick succession, while relatively little intuition and reader guidance are provided before the detailed results. Also, the language can be improved.
Questions for authors
-
Which of the complexity results are properties of the certification problem itself, and which are properties of the particular branch-and-bound verification algorithms considered in the paper?
-
Could a lower bound be obtained for the underlying problem of certifying the Lyapunov region rather than for a particular class of box-based verifiers?
-
How would the complexity change if the verifier used a different set representation?
-
How does the proposed analysis compare with reachability analysis? Why is this alternative not mentioned, and how would its computational complexity compare with the presented approach?
-
Could the analysis be extended to continuous-time dynamics described by differential equations?
-
What is the machine-learning-specific scientific question addressed by the paper?
-
How should the scaling results be interpreted if future verification algorithms no longer rely on the analyzed subdivision scheme? Is there a part of the theory that the authors expect to remain unchanged under fundamentally different verification methods?