Interior Point Implementations of Alternating Minimization Training

Michael D. Lemmon, Peter T. SzymanskiNeurIPS 1994

This paper, originally presented at NIPS (now NeurIPS) in 1994, bridges the gap between classical optimization theory and neural network training. It demonstrates how to adapt high-performance "Interior Point" (IP) methods—usually reserved for linear programming—to speed up the training of Radial Basis Function (RBF) networks.

By reframing Alternating Minimization (AM) training as a "perturbed" linear programming problem, the authors successfully apply IP methods. This yields a training algorithm with a guaranteed sublinear convergence rate of $O(\sqrt{n}L)$, ensuring that training time scales efficiently even as network size increases.

The Challenge of Alternating Minimization

Training RBF networks and "mixtures of experts" often relies on Alternating Minimization (AM), a process closely related to the Expectation-Maximization (EM) algorithm. In AM, optimization flip-flops between adjusting the network's weights and tuning the "gating" parameters that decide which part of the network handles which input.

While AM is popular, it often lacks rigorous convergence rate guarantees that scale well with problem size. The authors noticed that one half of the AM cycle (the Q-update) is essentially a Linear Programming (LP) problem. They set out to answer a pivotal question: Can we use the highly efficient "path-following" algorithms from the world of Interior Point optimization to make neural network training faster and more predictable?

A Modified Interior Point Approach

The authors propose a modified small-step primal Interior Point algorithm that breaks the problem into two distinct legs:

  1. The Q-update (Linear Programming): This step optimizes the gating neuron's weights. Because this is a standard LP problem, it can be solved by following a "central path"—a theoretical track that leads directly to the optimal solution while staying safely away from the constraint boundaries of the feasible region.
  2. The $\Theta$-update (Quadratic Programming): This step optimizes the regressor weights.

The Core Innovation: Normally, one might try to solve the $\Theta$-update perfectly in every iteration. However, doing so "rotates" the cost vector so sharply that it knocks the algorithm off its central path, destroying the efficiency of the Interior Point method.

To fix this, the authors introduce a convex combination for the $\Theta$-update. Instead of jumping directly to the new minimum, they take a calculated, less aggressive step. This ensures the solution stays within the "region of quadratic convergence," preserving the sublinear scaling of the original IP method. Viewing the $\Theta$-update as a perturbation of an underlying Linear Program allows the use of powerful stability results from optimization theory.

Experimental Setup

The algorithm was evaluated on a synthetic time-series prediction task. The target was a complex signal generated by the sum of four sine waves: $y(t) = \sin(\pi t) - \sin(2\pi t) + \sin(3\pi t) - \sin(\pi t/2)$.

Using a training set of 100 samples, the researchers tested the algorithm on networks ranging from 4 to 20 agent neurons. This resulted in LP problem sizes ($n$) ranging from 404 to 2020 variables.

Key Results and Performance

The empirical results closely matched the theoretical guarantees, demonstrating both speed and computational efficiency.

Convergence and Computational Complexity
  • Theoretical and Empirical Convergence: The paper provides formal proofs that their "damped" $\Theta$-update guarantees the algorithm stays on the central path. In simulations, the algorithm converged in $O(\sqrt{n}L)$ iterations, exactly as predicted by the sublinear scaling theory. If you quadruple the size of your network, the number of iterations required only doubles.
  • Computational Efficiency: While theory suggested a complexity of $O(n^{3.5}L)$ floating-point operations (FLOPS), the authors found that using sparse matrix techniques reduced this to $O(n^2L)$ in practice. This makes the algorithm's complexity comparable to a matrix multiplication rather than a more expensive matrix inversion.
  • Accuracy: The resulting networks achieved mean square errors on the order of $10^{-3}$, proving that the efficiency gains did not compromise model quality.

Limitations and Future Work

While the authors proved that each "leg" of the minimization converges, they noted that the simultaneous convergence of both steps was still being finalized using contraction mapping and nonlinear stability analysis.

Furthermore, this paper focuses on a "small-step" algorithm. The authors suggest that "large-step" IP methods might offer even greater performance gains if the same stability could be maintained. Finally, extending this "Perturbed LP" framework beyond RBF and linear regressor networks to other types of EM-trained architectures remains an open challenge for future research.

Summary updated

BibTeX
@inproceedings{lemmon1994interior,
  author = {Michael D. Lemmon and Peter T. Szymanski},
  title = {{Interior Point Implementations of Alternating Minimization Training}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1994},
}
Figure