Abstract
We present a framework for performing regression between two Hilbert spaces. We accomplish this via Kirszbraun's extension theorem—apparently the first application of this technique to supervised learning—and analyze its statistical and computational aspects. We begin by formulating the correspondence problem in terms of quadratically constrained quadratic program (QCQP) regression. Then we describe a procedure for smoothing the training data, which amounts to regularizing hypothesis complexity via its Lipschitz constant. The Lipschitz constant is tuned via a Structural Risk Minimization (SRM) procedure, based on the covering-number risk bounds we derive. We apply our technique to learn a transformation between two robotic manipulators with different embodiments, and report promising results.
Introduction
In classical regression, the objective is typically to estimate a scalar value. However, many modern machine learning tasks involve vector-valued regression, where the goal is to map inputs to a multi-dimensional output space. The standard approach to this problem is to "decouple" the dimensions, treating each output coordinate as an independent scalar task. This simplification is problematic as it fails to capture the inherent geometric relationships and dependencies between output components.
While the problem can be framed as a Quadratically Constrained Quadratic Program (QCQP) to preserve these dependencies, standard solvers—such as interior-point methods—are computationally prohibitive. These methods often scale poorly, struggling with datasets beyond a few hundred points. This paper introduces a mathematically principled framework that utilizes Kirszbraun’s extension theorem to perform efficient, non-parametric regression between Hilbert spaces while maintaining geometric sensitivity.
Methodology
The proposed framework decomposes the regression task into two distinct algorithmic stages: smoothing and extension.
1. Smoothing (Training and Regularization)
To prevent overfitting and ensure generalization, the training labels are first perturbed to satisfy a user-specified Lipschitz smoothness constraint while minimizing distortion. This denoising step ensures that the learned function remains stable and does not exhibit extreme fluctuations between nearby points. In this context, the Lipschitz constant serves as a powerful regularizer. By controlling this constant, we manage the trade-off between fitting the training data and maintaining a simple hypothesis, a process guided by Structural Risk Minimization (SRM).
2. Extension (Prediction)
To predict a label for a new, unseen test point, we employ an approximate version of Kirszbraun’s extension theorem. This theorem provides a powerful guarantee: any $L$-Lipschitz function defined on a subset of a Hilbert space can be extended to the entire space without increasing the Lipschitz constant. This allows the model to generalize from the smoothed training set to the entire input domain while preserving the geometric properties of the Hilbert space.
The Multiplicative Weight Update (MWU) Solver
The primary computational contribution of this work is the development of a specialized Multiplicative Weight Update (MWU) scheme. Standard QCQP solvers are $O(N^3)$ or worse, making them impractical for large-scale learning. Our MWU approach reduces the complex QCQP to a series of "Laplace’s problems"—solving systems of linear equations. This iterative method provides a quadratic runtime improvement, shifting the computational bottleneck and allowing the framework to scale to much larger datasets.
Experimental Evaluation
Benchmarks and Scalability
The framework was evaluated using synthetic non-linear transformations, including $f(x) = x^3$ and $f(x) = \sin(x)$, with training sets ranging from 20 to 1,000 points. The MWU-based algorithm was compared directly against Matlab’s standard interior-point (IntPt) solver.
The results demonstrated a massive speedup. For a dataset of 200 points, the MWU method completed the smoothing process in approximately 1.6 seconds. In contrast, the interior-point solver required over 766 seconds. Furthermore, the IntPt solver failed to complete tasks within a 12-hour window for datasets exceeding 200 points, whereas the MWU method successfully processed 1,000 points in under a minute.
Accuracy and Generalization
Beyond speed, the MWU method exhibited superior numerical stability. As the data size increased, the standard IntPt solver frequently failed to solve the optimization problem correctly, leading to "heavy outliers" in the output. The MWU method produced more accurate smoothing and extensions, resulting in significantly lower average squared error on test sets. This confirms that the MWU approach is not only faster but also more robust for high-dimensional regression tasks.
Conclusion
This paper demonstrates that Kirszbraun’s extension theorem, combined with a novel MWU solver, provides a scalable and theoretically sound basis for vector-valued regression. By treating the Lipschitz constant as a regularization parameter, we can effectively manage the complexity of the learned hypothesis.
While the current framework is restricted to Hilbert spaces—as Kirszbraun’s theorem does not generally hold for Banach spaces—it shows great promise for applications requiring geometric consistency, such as learning transformations between robotic manipulators with different embodiments. Future work will focus on optimizing the MWU oracle for specific data structures and exploring applications in higher-dimensional real-world datasets.
Summary updated