Source-linked AI summary
Distributed optimization of deeply nested systems
Miguel Á. Carreira-Perpiñán, Weiran Wang
TL;DR
Training deeply nested systems is difficult because joint parameter estimation is nonconvex, hard to parallelize, and architecture selection is costly. The paper introduces MAC, which replaces nesting with an equivalent constrained problem optimized over parameters and auxiliary coordinates. MAC reuses single-layer algorithms, supports heterogeneous and distributed optimization, converges under stated assumptions, and often makes large progress within a few iterations.
Problem
Jointly training all layers and selecting an architecture in nested systems is a difficult nonconvex problem that is hard to parallelize and requires substantial expert effort.
Method
MAC replaces the deeply nested objective with an equivalent constrained formulation using auxiliary coordinates, then alternates optimization over parameters and coordinates.
Results
MAC achieves large error decreases in a few iterations, with parallel implementations attaining nearly linear speedup in the number of processors.
Takeaways & Limitations
MAC provides a general framework for parallel nested-system learning that can reuse existing single-layer algorithms and support heterogeneous architectures and architecture search.
Takeaways & Limitations
The quadratic-penalty implementation is simple and effective but is not intended to be particularly efficient; more efficient constrained and W- or Z-step methods remain future work.
Abstract
from arXiv · showhide
In science and engineering, intelligent processing of complex signals such as images, sound or language is often performed by a parameterized hierarchy of nonlinear processing layers, sometimes biologically inspired. Hierarchical systems (or, more generally, nested systems) offer a way to generate complex mappings using simple stages. Each layer performs a different operation and achieves an ever more sophisticated representation of the input, as, for example, in an deep artificial neural network, an object recognition cascade in computer vision or a speech front-end processing. Joint estimation of the parameters of all the layers and selection of an optimal architecture is widely considered to be a difficult numerical nonconvex optimization problem, difficult to parallelize for execution in a distributed computation environment, and requiring significant human expert effort, which leads to suboptimal systems in practice. We describe a general mathematical strategy to learn the parameters and, to some extent, the architecture of nested systems, called the method of auxiliary coordinates (MAC). This replaces the original problem involving a deeply nested function with a constrained problem involving a different function in an augmented space without nesting. The constrained problem may be solved with penalty-based methods using alternating optimization over the parameters and the auxiliary coordinates. MAC has provable convergence, is easy to implement reusing existing algorithms for single layers, can be parallelized trivially and massively, applies even when parameter derivatives are not available or not desirable, and is competitive with state-of-the-art nonlinear optimizers even in the serial computation setting, often providing reasonable models within a few iterations.
1 Introduction
Nested systems build complex mappings through hierarchies of nonlinear layers, but jointly training their parameters is difficult because function composition creates nonconvex objectives and limits scalable computation.
- Hierarchical architectures construct deeply nested mappings from inputs to outputs through successive processing layers.Examples include deep neural networks and processing systems for vision and speech.
- Jointly optimizing all layer parameters can achieve ideal task performance but is challenging because nesting produces inherently nonconvex functions.Traditional training commonly uses backpropagation to compute parameter gradients through the chain rule.
- MAC is introduced as a general optimization strategy that partly alleviates vanishing gradients, supports massive parallelization, and reuses algorithms for individual layers or units.The method is presented as a response to the computational and optimization challenges of deeply nested systems.
2 The method of auxiliary coordinates (MAC)
MAC replaces a deeply nested objective with an equivalent constrained formulation using auxiliary coordinates, then optimizes weights and coordinates through decoupled subproblems that support parallel and heterogeneous training.
- Formulation: MAC introduces auxiliary variables for hidden activations, yielding a constrained problem whose terms involve small parameter subsets and no nested functions.Eliminating the auxiliary coordinates recovers the original nested problem under general assumptions.
- Optimization: Quadratic-penalty optimization alternates W- and Z-steps while increasing µ, allowing the constrained formulation to approach the original nested objective.Under mild assumptions, the resulting solution path converges to a minimum of both constrained and original problems.
- Optimization: The W-step decomposes training into independent single-layer, single-unit problems that can reuse existing algorithms, while the Z-step coordinates the resulting updates.This decoupling creates large blocks of parallel computation and avoids backpropagated gradients over weights.
- Empirical behavior: MAC/QP reaches large error decreases in a few iterations, and its parallel implementation achieves nearly linear speedup with the number of processors.The reported comparisons are against stochastic gradient descent, conjugate gradients, and alternating optimization in the cited experiments.
- Heterogeneous architectures: MAC can accommodate heterogeneous architectures by assigning specialized layer algorithms, including k-means for RBF basis functions and least-squares training for remaining layers.The RBF autoencoder example introduces auxiliary coordinates only at the coding layer and reports a large error decrease in a few iterations.
- Model selection: MAC enables architecture search by separating layerwise model-selection tests, reducing M^K deep-net evaluations to M K single-layer tests per iteration.These tests can be parallelized and need not run at every iteration.
3 Related work
Prior work used auxiliary variables and activation updates for shallow or representation-focused problems, whereas MAC formulates general nested learning as an equivalent constrained optimization problem.
- The paper positions MAC as a general, provably equivalent constrained formulation for jointly optimizing parameters and auxiliary coordinates in nested systems.It can use quadratic penalties, augmented Lagrangians, or other constrained-optimization methods.
- Earlier approaches often optimized latent coordinates with mappings for dimensionality reduction, sometimes alternating over the mapping and coordinates.These methods include spline, neural-network, RBF, kernel, and Gaussian-process mappings.
- Some prior dimensionality-reduction formulations can produce biased nested mappings because they use a fixed penalty and are limited to shallow networks.The cited formulation is described as a truncated version of MAC's quadratic-penalty approach.
- MAC treats auxiliary coordinates as mathematical constructs for solving the nested optimization problem rather than as explicit targets for desirable hidden representations.The paper also distinguishes MAC by its support for heterogeneous architectures and architecture learning.
- MAC is similar in spirit to ADMM because both introduce variables that decouple terms, but MAC decouples functional nesting rather than splitting a shared objective variable.The distinction concerns what is being replaced by auxiliary variables.
4 Experiments
Experiments apply MAC to homogeneous and heterogeneous autoencoders, including architecture selection, and evaluate both optimization behavior and parallel speedups. Across settings, MAC uses alternating W- and Z-steps, reuses layer-specific solvers, and achieves rapid error decreases with simple parallelization.
- Experimental scope: MAC experiments cover deep sigmoidal autoencoders, heterogeneous RBF autoencoders, and joint architecture learning.The study also measures speedups from parallel MAC implementations in each setting.
- Optimization procedure: The W-step decomposes into independent single-layer, single-unit problems, while the Z-step separates across data points and uses nonlinear least-squares updates.Gauss-Newton is used for both steps; the Z-step usually requires 1–2 iterations.
- Homogeneous training: The deep sigmoidal autoencoder uses 256–300–100–20–100–300–256 units and over 200 000 weights on USPS digit images.Training uses 5 000 images for training and 5 000 for validation, with one preliminary gradient step applied to the random initialization.
- Homogeneous training: MAC/QP reaches a good network in a few iterations, whereas SGD and CG require many iterations to reduce the error.The parallel implementation also achieves a nearly linear speedup with processor count.
- Heterogeneous training: For the heterogeneous RBF autoencoder, MAC/QP combines k-means basis-function training with least-squares updates and reduces error substantially in a few iterations.The method introduces auxiliary coordinates only at the coding layer; the final latent manifolds improved, including loops that were folded initially.
- Architecture learning: Architecture learning searches 2 500 encoder–decoder configurations and selects a final (M1, M3) = (1 368, 150) model with 1.5 million weights.AIC first favors the much smaller (700, 150) architecture, producing a large objective decrease before later weight optimization and architecture changes.
5 Conclusion
MAC facilitates the design and estimation of nonconvex nested systems by jointly optimizing parameters, reusing existing algorithms, searching architectures, and enabling massively parallel computation while provably converging.
- MAC jointly optimizes parameters, searches automatically over architectures, reuses existing algorithms, and supports massively parallel computation.
- MAC can reduce runtime and human effort in practical design and estimation of nonconvex nested problems.
- MAC is presented as a possible complement or replacement for backpropagation-based algorithms in serial and parallel settings.
- MAC is particularly relevant to automatically tuning all stages of complex intelligent-processing systems in distributed cloud environments.
- The method leaves open questions about auxiliary-coordinate placement and the algorithms used for the W- and Z-steps.
A.1 Definitions
The nested formulation models a deep network as a composition of layer functions, while MAC introduces auxiliary hidden-unit coordinates and equality constraints to remove explicit nesting from the optimization representation.
- The nested objective trains a K-hidden-layer network by minimizing output loss over composed layer functions.
- Each layer applies a linear mapping followed by an elementwise squashing nonlinearity such as the sigmoid.
- MAC introduces one auxiliary variable per data point and hidden unit to represent intermediate activations.
- The feasible set consists of parameter-coordinate pairs whose auxiliary coordinates satisfy the forward-propagation constraints for every data point.
- Quadratic-penalty optimization minimizes the augmented objective for fixed µ while driving µ toward infinity.
A.2 Equivalence of the MAC and nested formulations
Under broad assumptions, the MAC-constrained and nested formulations have corresponding minimizers because the feasible set encodes forward propagation and recovers the nested objective.
- The equivalence theorem applies without requiring smooth functions, restricts neither the loss to least squares nor the nested problem to unconstrained settings.
- The nested and MAC-constrained problems have minimizers in a one-to-one correspondence.
- Forward propagation maps each parameter vector W to a unique auxiliary-coordinate vector g(W), with E1(W) = E(W, g(W)).
- Restricting the MAC objective to the feasible manifold Z = g(W) preserves the nested problem’s minimizers and maximizers.
A.3 KKT conditions
The KKT conditions of the MAC-constrained problem and the stationary conditions of the nested problem are equivalent, extending the correspondence beyond minimizers to all major solution types.
- The KKT equivalence is established under continuous first-derivative assumptions for the illustrated single-hidden-layer case, with analogous reasoning for deeper networks.
- The constrained problem’s auxiliary coordinates and multipliers can be substituted into its KKT equations to recover the nested stationary-point equations.
- Nested stationary points correspond one-to-one with KKT points of the MAC-constrained problem.
- Minimizers, maximizers, and saddle points correspond between the nested and MAC-constrained formulations.
B Convergence of the quadratic-penalty method for MAC
The quadratic-penalty method for MAC converges, under stated assumptions and increasingly accurate penalty minimization, to KKT or stationary points associated with the constrained and original nested problems. The analysis also identifies conditions and caveats governing this correspondence.
- General convergence theory: The general quadratic-penalty method converges to a stationary point, and with linearly independent constraint gradients, to a KKT point of the equality-constrained problem.The penalty parameters increase toward infinity while the approximate minimization tolerances decrease toward zero.
- MAC-specific convergence: MAC/QP iterates converge under mild assumptions to a KKT point of the constrained problem and thus to a stationary point, typically a minimizer, of the original nested problem.The result assumes a positive penalty sequence tending to infinity and approximate minimization errors tending to zero.
- MAC-specific conditions: For MAC, the constraint gradients are linearly independent at every point, establishing the regularity condition required by the general convergence theorem.The proof derives this by examining the gradients with respect to the auxiliary coordinates and showing all coefficients in a zero linear combination vanish.
- Limitations: Convergence may reach a pathological stationary point rather than a minimizer, and the quadratic-penalty function is not thereby established as an exact penalty function.The latter requires the opposite implication: every local constrained solution must be a local minimizer of the penalty objective.
- Stationarity correspondence: A stationary point of the quadratic-penalty function satisfying the auxiliary-coordinate constraints is also stationary for the nested problem, but the converse generally fails.The converse fails because a nested stationary point need not satisfy the auxiliary-coordinate stationarity equation.