Hoo Optimality Criteria for LMS and Backpropagation

NeurIPS 1993

TL;DR

This paper provides a theoretical justification for the robustness of the widely used LMS and backpropagation algorithms by showing they are "H-infinity optimal" estimators. This means they minimize the worst-case prediction error, explaining their excellent performance in the face of noisy or uncertain data, unlike some other methods.

What Problem Does This Paper Address?

Adaptive algorithms like the Least Mean Squares (LMS) algorithm and backpropagation are incredibly popular in signal processing and machine learning, respectively. They are known for their robustness, meaning they perform well even when the data is noisy or the underlying model is not perfectly known. However, this robustness has largely been an observed phenomenon rather than a theoretically proven property. Traditional analyses often focus on minimizing the average squared error (H2 norm), which doesn't fully capture worst-case performance. This paper aims to provide a theoretical framework, using the H-infinity norm, to explain and quantify this observed robustness for both linear (LMS) and nonlinear (backpropagation) adaptive systems.

Methods

The core of the paper's methodology lies in framing the estimation problem within the context of H-infinity optimal control theory.

  • H-infinity Norm: The authors introduce the H-infinity norm as a measure of performance. This norm quantifies the maximum energy gain from disturbances (noise, modeling errors) to the prediction error. Minimizing this norm means minimizing the worst-case impact of these disturbances.
  • Transfer Operator: They define a "transfer operator" that maps the unknown parameters and disturbances to the prediction errors. The H-infinity norm is then applied to this operator.
  • Linear Case (LMS): For linear models, they show that the LMS algorithm, under certain conditions on the learning rate and input excitation, achieves an H-infinity norm of 1. This means the energy of the prediction error is guaranteed to be no larger than the energy of the disturbances.
  • Nonlinear Case (Backpropagation): For nonlinear models, they extend the analysis to show that backpropagation is locally H-infinity optimal. This means that when the current estimate is close to the true value and disturbances are small, backpropagation exhibits H-infinity optimal behavior. This is achieved by using a local linearization of the nonlinear function and applying the H-infinity framework.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses simulated scenarios to illustrate its points, rather than specific datasets.

Key Insights and Ideas

  • LMS and Backpropagation are Robust by Design: The H-infinity optimality provides a fundamental theoretical reason why these algorithms are so robust. They are not just empirically good; they are mathematically designed to handle worst-case scenarios.
  • Minimizing Worst-Case Error, Not Just Average Error: The H-infinity framework shifts the focus from minimizing the average squared error (H2) to minimizing the maximum possible error amplification from disturbances. This is crucial for real-world applications where data quality can vary significantly.
  • LMS Achieves a "Perfect" H-infinity Norm: The result that LMS achieves an H-infinity norm of 1 is particularly striking. It implies that the algorithm perfectly balances the energy of the prediction error with the energy of the disturbances, never amplifying them.
  • Local Optimality for Nonlinear Systems: While backpropagation isn't globally H-infinity optimal for all nonlinear systems, its local optimality is still a significant finding. It explains its good performance in regions where the nonlinearities are well-behaved and the estimates are near the true values.
  • Learning Rate Matters: The paper explicitly derives bounds on the learning rate (µ) for both LMS and backpropagation, reinforcing the well-known practical observation that excessively large learning rates can degrade performance.

Key Results

  • Theorem 1: The LMS algorithm is H-infinity optimal for linear models, achieving a minimum H-infinity norm of 1, provided the input is sufficiently exciting and the learning rate is within a specific range.
  • Theorem 2: The backpropagation algorithm is an approximation to a theoretically derived H-infinity optimal algorithm for nonlinear models.
  • Theorem 3: Backpropagation is locally H-infinity optimal for nonlinear models. This means that for sufficiently close estimates and small disturbances, the ratio of prediction error energy to disturbance energy is bounded by 1 + ε, where ε can be arbitrarily small.
  • Corollaries: In the absence of disturbances, both LMS and backpropagation are shown to converge to the true solution, with convergence speed related to the learning rate.

Limitations and Future Work

  • General Solution for Nonlinear Systems: The paper acknowledges that a general solution for H-infinity optimal estimation for arbitrary nonlinear functions is still an open problem.
  • Local vs. Global Optimality: The H-infinity optimality for backpropagation is shown to be local. The paper notes that backpropagation can get stuck in local minima, which is consistent with the H-infinity ratio becoming arbitrarily large in such cases.
  • "Exciting" Inputs: The theoretical results for both LMS and backpropagation rely on the input signals being "persistently exciting." While this is a standard assumption in adaptive filtering, its practical implications and how to ensure it are not deeply explored.
  • Future Work: The authors suggest that the H-infinity optimality results can lead to convergence proofs for LMS and backpropagation in the absence of disturbances. They also hint at exploring how larger learning rates might increase resistance to local minima, though this is not pursued due to space constraints. The paper also mentions that the LMS algorithm is a "central solution" and has connections to maximum entropy and risk-sensitive optimal solutions, suggesting avenues for further research.

Summary updated

BibTeX
@inproceedings{1993hoo,
  title = {{Hoo Optimality Criteria for LMS and Backpropagation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1993},
}
Figure