Learning Stability Certificates from Data

• Certificate functions unify Lyapunov, barrier, and contraction methods by proving desired system properties, and strong converse results link certificates to properties that hold.They can also be used for controller synthesis.Source: §1 · pp. 1–2
• Existing certificate-synthesis tools often require closed-form dynamics, restrictive function classes, or costly computation, limiting their use with complex robotic systems.These constraints include SOS optimization and SMT solvers.Source: §1 · p. 2
• Prior trajectory-based learning enforces certificate conditions on samples and can generalize empirically, but lacks a deeper theoretical account of when and why it works.Source: §1 · p. 2
• Violation regions for a learned contraction metric on the damped Van der Pol oscillator appear to shrink as the number of trajectories increases, motivating questions about data needs and consistency.Source: §1 · p. 2, Figure 1 · p. 2
• The paper proves learning consistency with a fast ˜O(k/n) generalization-error rate, converts error bounds into bounds on violating-region volume, and demonstrates efficient learning and adaptive-control use.Here, k is the effective number of parameters, and generalization error is the probability that a learned certificate fails on a new trajectory.Source: §1 · p. 2

• Giesl et al. fit a dynamics model before constructing a Lyapunov function by interpolation, with L∞ convergence rates tied to dense state-space coverage.Source: §2 · p. 3
• This work instead analyzes generalization directly for Lyapunov functions learned by enforcing derivative conditions on training data.Related approaches include learning Lyapunov functions for linear or piecewise affine systems, learning regions of attraction, and jointly learning models and certificates; some lack formal generalization guarantees or require true dynamics.Source: §2 · p. 3
• Softening Lie-derivative constraints can enable first-order gradient optimization, and the paper's generalization analysis can be adapted to soft constraints.Source: §2 · p. 3
• Barrier-function studies learn or use control barrier functions for safety, sometimes extending validity beyond training data with Lipschitz arguments.Source: §2 · p. 3
• Prior contraction-learning work either holds the metric fixed or jointly learns a model and control contraction metric, while generalization for joint model-and-metric learning remains future work.Source: §2 · pp. 3–4
• Random convex programming bounds violation probability by O(d/n) for sampled constraints, and this paper generalizes that style of bound beyond convex programs, with less sharp constants.The experiments use the random-convex-programming bound for numerical generalization bounds when the problem is convex.Source: §2 · p. 4

3.1 Problem Statement

• The problem setting assumes a fully observed state, unknown continuous dynamics, random initial conditions, and access to their trajectories; experiments estimate time derivatives numerically.Source: §3.1 · p. 4
• The framework chooses a differentiable function V to satisfy a known condition h along trajectories, and supports multiple certificate conditions and extensions to higher-order or time derivatives.The optimization uses a positive margin to promote generalization beyond sampled data, and the paper bounds violation probability over new trajectories.Source: §3.1 · pp. 4–5

3.1.1 Lyapunov stability analysis

• For Lyapunov learning, the certificate condition combines the derivative of V along the dynamics with a class K function of V, yielding local asymptotic stability when the stated Lyapunov properties hold.Source: §3.1.1 · p. 5

3.1.2 Contraction metrics

• For contraction metrics, the framework expresses contraction through a differential Lyapunov function and enforces its condition using sampled perturbed trajectories and their numerical differences.The variational dynamics of the perturbation match the local linearization of the system.Source: §3.1.2 · p. 5

4 Generalization Error Results

• The analysis assumes trajectories remain in a compact set and certificate functions and their gradients are uniformly bounded there.Contracting systems satisfy the stated trajectory-stability assumption.Source: §4 · p. 6
• Feasible certificates achieve zero empirical risk with margin γ, enabling statistical learning bounds on violations for unseen trajectories.The analysis bounds Rademacher complexity to control generalization error.Source: §4 · p. 6

4.1 Lipschitz parametric function classes

• For Lipschitz parametric classes, the generalization error scales as ˜O(k/n), while exploiting SOS matrix structure sharpens the bound to ˜O(d/n).The SOS representation has k = d(d + 1)/2 parameters, but a matrix-structure estimate improves on the generic parametric bound.Source: §4.1 · pp. 6–7

4.2 Reproducing kernel Hilbert space function classes

• For the non-parametric RKHS class, Theorem 4.4 provides a generalization bound under boundedness and Lipschitz assumptions on the feature function and its derivative.The class is dense in its associated RKHS as Bα grows.Source: §4.2 · p. 7

Assumptions

• The global results assume incremental stability: distances between any two trajectories are bounded by β of their initial distance and time.The section describes this assumption as stronger than Lyapunov stability and implied by contraction.Source: §5 · p. 8

Lyapunov functions

• For ξ ∈ ˜X, V(ϕt(ξ)) is bounded by uξ(t), with decay terms depending on the incremental-stability rate β.For β(s, t) ≤ M e^-αts with α > λ, hβ(t) = e^-λt; for β(s, t) ≤ Ms/(t + 1), hβ(t) = t2e^-λt.Source: §5 · p. 8
• For uniformly sampled trajectories, ν(Xb) ≤ O(k/n), yielding n ≥ Ω(k · ζ^-2p) to bound the Lyapunov violation-ball radius by ζ under the stated assumptions.The sample requirement has exponential dependence on dimension p without additional structure.Source: §5 · p. 8
• The authors say incremental stability simplifies the proof relative to Liu et al. and makes the constants explicit.Source: §5 · p. 9

Metric learning

• Under Theorem 5.2’s assumptions, the learned metric contracts at rate (1 − η)λ throughout ˜S(rb).The theorem assumes a full-dimensional X, p ≥ 2, and a system contracting in M⋆ at rate λ > 0.Source: §5 · p. 9

Experimental setup

• The experiments use neural-network Lyapunov functions and SOS-based convex metric learning, with generalization error estimated on test sets and upper confidence bounds computed using the Chernoff inequality.The quadruped experiment learns a discrete-time Lyapunov function from recovery trajectories after random impulse forces, using a hand-tuned PD controller.Source: §6 · pp. 9–10

Damped pendulum

• The pendulum Lyapunov function learned from 1000 trajectories supports adaptive regulation as disturbance strength increases tenfold, while the system without adaptation is driven far from the origin.The experiment varies κ over {1, 6, 10}; Figure 2 also shows level sets and trajectory rollouts for set invariance.Source: §6 · p. 9, Figure 2 · p. 10

Stable standing for quadrupeds

• With n = 50000, the Minitaur median generalization UCB is 1.11% on a test set and 1.99% with a 10% holdout validation set.The learned discrete-time Lyapunov function is evaluated over 30 trials; the plotted percentiles are 10th, 50th, and 90th.Source: §6 · p. 10, Figure 2 · p. 10

6-dimensional gradient system

• With n = 4000, median generalization UCBs are 5.85% for test-set differential Lyapunov constraints, 8.02% for validation, and 5.35% for contraction at .99λ.As sample count increases, differential-constraint error probability decreases and the learned metric becomes a true metric at the reduced rate with high probability.Source: Figure 2 · p. 10, 6-dimensional gradient system · p. 11

7 Conclusion

• The conclusion reports that certificate functions can be efficiently learned from data and identifies noisy observations, process noise, joint dynamics-and-certificate learning, and lower bounds as future questions.The stated extension to uncertain environments specifically concerns noisy state observations and process noise in the dynamics.Source: §7 · p. 11

A.1 Metric learning algorithm

• Metric learning samples nearby trajectory pairs, computes their flows and differences, then optimizes differential contraction constraints; convex parameterizations can enforce global positive definiteness.The algorithm may also use nonconvex neural-network parameterizations with soft constraints, or enforce positive definiteness along trajectories rather than globally.Source: §A.1 · p. 14

A.2 Pendulum

• The pendulum experiment’s test-set generalization UCB percentiles are 0.459%, 0.459%, and 1.163%; grid violations are higher because the grid includes states outside the sampled flows.Across 30 trials, the grid-violation percentiles are 0.168%, 1.548%, and 3.696%.Source: §A.2 · p. 15

Then the adaptive control law

• The adaptive law relies on nominal pendulum stability and learns to cancel the disturbance; the proof concludes that the state and its derivative converge to zero.The appendix identifies the law as a special case of speed-gradient algorithms and establishes boundedness before applying Barbalat’s Lemma.Source: §A.2 · p. 15, Then the adaptive control law · p. 16

A.3 Minitaur

• For Minitaur recovery, the discrete-time Lyapunov condition includes slack γ = 0.025, which is needed for convergence to a ball rather than zero.The controller returns joint angles and velocities to the standing position with a small bias of about 0.2 in ℓ2-norm.Source: §A.3 · p. 16

A.4 6-dimensional gradient system

• The 6D gradient-flow metric uses degree-two monomials, global positive-definiteness constraints, and 25 differential Lyapunov constraints per trajectory; test-set and validation bounds are reported.The test set has 1000 points, and each plotted point averages 25 independent training-set draws.Source: §A.4 · p. 17

A.4.1 Randomized convex programs

• The randomized convex-program procedure samples constraints from a distribution, solves the sampled optimization problem, and chooses ε numerically so the failure bound β(ε) equals δ.For n ≥ d, the appendix derives a Chernoff-based upper bound on ε’s scaling with n and δ.Source: §A.4.1 · pp. 17–18

Experimental setup

• The experiment parameterizes the metric with degree-four monomials and tests 50 differential Lyapunov constraints per trajectory at rate λ = 3/4.Initial conditions are drawn uniformly from a ball of radius 2.Source: §A.5 · p. 18

Training-sample variation

• As the number of training samples increases, the damped Van der Pol violation set decreases in size and is pushed toward the sampled-region boundary.The experiment tests the metric condition on a uniform grid of 9 × 10^4 points.Source: §A.5 · p. 18

Contraction-rate variation

• Figure 3 plots the violation set as a function of η; as η decreases to zero, the set decreases in size and is pushed to the boundary of the sampled region.Source: §A.5 · p. 18

Proof estimate

• Dudley’s inequality is introduced as an estimate for Rn(V).The excerpt does not state the estimate’s form or a resulting bound.Source: B Proofs for Section 4 · p. 18

Figure 3

• Figure 3 concerns the violation set for contraction-metric learning in the damped Van der Pol system.Its caption describes the set as a function of tested rate ηλ, with 0 < η < 1.Source: Figure 3 · p. 19
• The figure’s horizontal comparison is across tested contraction rates ηλ, rather than across different systems.The caption identifies the system as damped VDP.Source: Figure 3 · p. 19

B.1 Proof of Theorem 4.2

• Theorem 4.2’s proof bounds the parameter-to-function-class Lipschitz constant and uses a volume comparison bound for the metric entropy of a unit ball in R^k.The proof then invokes Lemma 4.1.Source: §B.1 · p. 19

B.2 Proof of Theorem 4.3

• Theorem 4.3’s proof bounds metric entropy for a matrix ball using the smaller of a volume-comparison bound and a dual Sudakov bound.The proof integrates this estimate and invokes Lemma 4.1.Source: §B.2 · p. 19
• The matrix-ball entropy argument yields a bound involving d, n, and log d.The displayed bound is given in the proof as d n log d.Source: §B.2 · p. 19

B.3 Proof of Theorem 4.4

• The approximation proof combines Rademacher-complexity bounds, symmetrization, contraction, and McDiarmid’s inequality to control function and derivative errors.It then applies Lemma 4.1 to the independently sampled finite-dimensional class.Source: §B.3 · pp. 21–22

C Proofs for Section 5

• The Section 5 proof preliminaries define uniform measure on compact sets and provide bounds for balls in the product of a state space and a sphere.The product-space measure is uniform on X combined with Haar measure on the sphere.Source: C Proofs for Section 5 · pp. 24–25
• For a linear time-varying system, every unit direction at time t is a positive scalar multiple of the flow of some initial unit vector.The proof uses the invertibility of the state-transition matrix.Source: C Proofs for Section 5 · p. 25

C.1 Proof of Theorem 5.1

• Theorem 5.1’s proof relates points reached from the considered initial set to nearby good initial conditions, then applies a comparison lemma to establish its bounds.The argument uses continuity when taking the limit as the neighborhood radius approaches its boundary.Source: §C.1 · pp. 25–26

C.2 Proof of Theorem 5.2

• A contracting system induces contraction of its prolongated tangent-bundle dynamics in a block-diagonal metric, yielding contraction on compact subsets of the Euclidean tangent bundle.The proof uses a differential Lyapunov function and chooses a sufficiently small metric parameter to obtain contraction.Source: §C.2 · pp. 26–27
• The tangent-bundle metric construction is limited to Euclidean space because its block-diagonal metric is not invariant under coordinate changes between manifold charts.The authors identify canonical tangent-bundle metrics as possible generalizations.Source: §C.2 · p. 27

D Known dynamics

• With known dynamics, Proposition D.1 bounds contraction over the reachable set when the bad initial-state set has uniform measure at most ε and the stated regularity and size conditions hold.The proposition gives a contraction rate λ/α for α > 1 under its displayed inequality.Source: D Known dynamics · p. 29
• The known-dynamics proof compares metric conditions along trajectories from good and nearby initial states, using Lipschitz bounds to control their difference.The resulting rate condition depends on the metric, its derivative, and dynamics regularity bounds.Source: D Known dynamics · pp. 29–30