Introduction
In the fields of control systems and robotics, non-parametric modeling frameworks like Nonlinear Set Membership (NSM) are increasingly favored for learning complex system dynamics from data. Unlike probabilistic methods, NSM provides deterministic bounds on unknown functions by assuming Lipschitz continuity. This assumption requires a Lipschitz constant ($L^*$), which represents the maximum rate of change of the function. However, determining the exact $L^*$ is notoriously difficult, leading practitioners to use conservative, "loose" upper bounds ($L \gg L^*$). This paper investigates the mathematical and geometric consequences of this common practice.
The Geometric Metamorphosis of NSM
The NSM regressor typically calculates predictions by averaging a "ceiling" and a "floor" function derived from training data. Geometrically, these functions are defined by Additively Weighted Voronoi Diagrams (AVDs). As the estimated Lipschitz constant $L$ increases, these complex AVDs undergo a transformation.
As shown in Figure 1, when $L$ is small (e.g., $L=2$), the prediction surface is relatively smooth. However, as $L$ increases to 16, the surface morphs into flat, constant "plateaus." These plateaus correspond exactly to the cells of a standard Voronoi partition, which characterizes a 1-Nearest Neighbor (1-NN) regressor. This visual evidence confirms that loose Lipschitz bounds inadvertently force a sophisticated NSM model to behave like a simple 1-NN model, which is prone to overfitting and high variance.
Convergence Properties
The authors provide a formal theoretical proof (Theorem 1) demonstrating that the NSM regressor converges to the 1-NN regressor in the $L_2$ functional norm as $L \to \infty$. This means the global average error between the two models vanishes.
Figure 2 illustrates this convergence using a synthetic 2D dataset. While the global trend shows a clear decrease in error, the authors note that convergence is not uniform. Specifically, the $L_\infty$ norm (maximum point-wise error) does not necessarily converge because of the sharp, discontinuous transitions at the boundaries of the Voronoi cells. Furthermore, while the error decrease is strictly monotonic in 1D, higher dimensions may exhibit local fluctuations even as the global error trends toward zero.
Practical Implications and Future Work
This discovery has significant implications for real-time control and optimization:
- Computational Efficiency: Evaluating NSM models is traditionally computationally expensive ($O(N)$ query time). However, the link to nearest-neighbor structures suggests that approximate nearest-neighbor algorithms could reduce query time to $O(\log N)$, making NSM more viable for high-frequency tasks.
- Optimization Challenges: The discontinuous "plateaus" resulting from loose bounds can hinder gradient-based optimizers used in frameworks like Model Predictive Control (MPC). The authors suggest exploring smooth surrogate models to mitigate this.
In conclusion, while overestimating the Lipschitz constant is a common safety measure, it fundamentally changes the nature of the NSM model. Understanding this convergence allows for better-informed model selection and potential algorithmic optimizations in robust non-parametric regression.
Summary updated