Implicit Deep Learning

Laurent El Ghaoui; Fangda Gu; Bertrand Travacca; Armin Askari; Alicia Y. Tsai

Source-linked AI summary

Implicit Deep Learning

Laurent El Ghaoui, Fangda Gu, Bertrand Travacca, Armin Askari, Alicia Y. Tsai

arXiv:1908.06315v4Aug 17, 2019cs.LGmath.OCstat.ML

TL;DR

Implicit deep learning asks how to formulate and analyze prediction rules that are not restricted to recursive layer-by-layer networks. The paper develops fixed-point-based implicit models, conditions for well-posedness, analysis and training methods, and related architecture and sparsity tools. It reports linear-convergent fixed-point iterations with matrix-vector-product complexity comparable to a similarly sized forward pass, alongside an implicit-model regression RMSE of 0.56 versus 0.65 for a three-hidden-layer neural network.

Problem
Implicit models require well-posedness and robustness analysis because their equilibrium equations may have no or multiple solutions, while the framework seeks broader architectures and rigorous analyses.
Method
The paper represents prediction through a fixed-point equation for one hidden state, establishes well-posedness conditions, and develops robustness, composition, sparsity, and optimization methods.
Results
Fixed-point iteration has linear convergence with matrix-vector-product complexity comparable to a similar forward pass, and regression achieves RMSE 0.56 versus 0.65 for a three-hidden-layer neural network.
Takeaways & Limitations
Implicit models encompass most current neural-network architectures while allowing cycles and supporting robustness analysis, interpretability, sparsity, compression, and feature selection.
Takeaways & Limitations
The equilibrium equation may lack a solution or a unique solution, and the described adversarial bounds do not directly generate a maximum-impact feasible attack.

Abstract

from arXiv · show

Implicit deep learning prediction rules generalize the recursive rules of feedforward neural networks. Such rules are based on the solution of a fixed-point equation involving a single vector of hidden features, which is thus only implicitly defined. The implicit framework greatly simplifies the notation of deep learning, and opens up many new possibilities, in terms of novel architectures and algorithms, robustness analysis and design, interpretability, sparsity, and network architecture optimization.

1. Introduction.

Implicit models replace layer-by-layer recursion with a fixed-point equation for a single hidden state vector. This broader framework encompasses many neural-network architectures while supporting robustness, sparsity, interpretability, and feature-selection analyses.

Implicit prediction rules: Implicit prediction rules determine a hidden state x by solving a fixed-point equation rather than recursively passing through several layers.The state represents hidden features extracted from the input, but may be defined only implicitly because the equation lacks a closed-form solution.
Model representation: The framework separates linear operations from parameter-free nonlinear activation maps, with model parameters represented by matrices A, B, C, and D.Figure 1 presents this organization as a block diagram read from right to left.
Model scope: Implicit models include most current neural-network architectures as special cases while permitting cycles and greater parameter capacity for a fixed hidden-feature dimension.These properties make implicit models a wider class than standard deep networks.
Paper scope: The paper develops well-posedness conditions, neural-network representations, robustness analysis, and penalties for interpretability, sparsity, compression, and feature selection.Its outline also discusses composition of implicit models and robustness-oriented training penalties.

2. Well-Posedness and Composition.

The paper develops tractable conditions ensuring that implicit equilibrium equations have unique solutions, then analyzes how well-posed implicit models compose. These results support convex training constraints, comparable fixed-point computation, and broader architectures including cycles and attention-like multiplicative connections.

Well-posedness conditions: BLIP activation maps are blockwise Lipschitz, encompassing componentwise maps such as ReLU, leaky ReLU, tanh, sigmoid, and softmax.CONE maps are the special case with scalar blocks and Lipschitz constant 1.
Well-posedness conditions: Well-posedness requires the equilibrium equation to have a unique solution for every right-hand side, which may fail for general implicit models.The paper illustrates that scalar fixed-point equations can have two or no solutions, motivating explicit constraints on A.
Well-posedness conditions: λpf(|A|) < 1 is sufficient for well-posedness with CONE activations, and the solution can be computed by fixed-point iteration with linear convergence.Each iteration is a matrix-vector product, so its complexity is comparable to a forward pass through a similarly sized network.
Tractable constraints and structure: The sufficient Perron-Frobenius condition is conservative, while the convex constraint ∥A∥∞ < 1 can replace it during training and rescale models without changing predictions.For ReLU, upper-triangular A is well-posed if and only if diag(A) < 1, even when the Perron-Frobenius condition fails.
Well-posedness conditions: For BLIP activations, a Perron-Frobenius condition based on blockwise induced norms likewise guarantees well-posedness and fixed-point solvability.The condition is numerically tractable through the matrix of blockwise induced norms and the Lipschitz constants.
Composition of implicit models: Block-triangular composition preserves well-posedness exactly when the diagonal subsystems are well-posed; cascade and parallel connections therefore inherit subsystem conditions.Multiplicative connections are Lipschitz under bounded activation maps, with applications to attention units using bounded maps such as tanh.

3. Implicit models of deep neural networks.

The paper represents feedforward, convolutional, residual, recurrent, and multiplicative neural-network components as implicit models. Strictly upper triangular structures make many such models well-posed and solvable by backward substitution, while activation and composition conditions extend the framework.

Well-posedness: Strictly upper triangular matrices A automatically ensure well-posedness and permit solving the equilibrium equation by backward substitution.For componentwise non-expansive maps, the corresponding absolute-value matrix also has zero eigenvalues.
Feedforward layers: Output activations, affine terms, and activations with φ(0) ≠ 0 can be incorporated by augmenting the state or input representation.Biases are handled by appending a constant 1 to the input, while shifting the activation and state handles nonzero φ(0).
Feedforward layers: A standard multilayer feedforward network becomes an implicit model whose triangular equilibrium is solved by backward block substitution, corresponding to a forward network pass.The construction uses a blockwise activation over hidden-layer states and applies to arbitrary layer matrices in this representation.
Convolutional layers and max-pooling: Convolutional layers are represented as Toeplitz-like linear maps, while max-pooling selects maximal values from specified image sub-areas and satisfies BLIP with l∞-Lipschitz constant 1.The max-pooling construction pads the activation output with zeroes to preserve input and output dimensions.
Residual, recurrent, and multiplicative networks: Residual, recurrent, multiplicative, and attention architectures can be expressed in the implicit framework using structured matrices and bounded or Lipschitz activation maps.Unrolled RNNs yield strictly upper block-triangular matrices, residual blocks combine linear operations with nonlinearities and skip additions, and bounded inputs control multiplicative units.
Robustness analysis: Robustness analysis of implicit models bounds states, outputs, and losses under unknown-but-bounded inputs, supporting diagnosis, adversarial-attack generation, and training constraints.The analysis assumes a blockwise Lipschitz activation map and informs penalties or constraints used during training.

4. Robustness.

The robustness analysis bounds state, output, and loss sensitivity to bounded input uncertainty, using well-posedness conditions and norm-based sensitivity constructions. For ReLU models, LP/SDP relaxations can further produce candidate adversarial attacks, while the bounds motivate robustness penalties.

Uncertainty sets: Input uncertainty is modeled through box and cardinality-constrained sets, with nominal inputs and componentwise uncertainty parameters.The analysis considers both unrestricted componentwise perturbations and perturbations limited to k changed components.
State bounds: Under CONE activations and λpf(|A|) < 1, the state deviation satisfies |x − x0| ≤ (I − |A|)^−1|B|σu.The bound is also characterized as the limit of a fixed-point iteration involving |A| and |B|σu.
State bounds: For BLIP activations, state bounds use the block-norm matrices N(A) and N(B), with invertibility of I − ΓN(A) guaranteed by the stated well-posedness condition.Γ is the diagonal matrix of blockwise Lipschitz constants, and the vector norm function η appears in the resulting bound.
Robustness-oriented training: The analysis motivates penalties based on ∥·∥∞ and ∥S∥∞ to constrain Lipschitz behavior and improve robustness during training.The norm penalty can apply to model matrices A, B, C, and D, while ∥S∥∞ is proposed from the refined sensitivity analysis.
Output bounds and sensitivity: Output bounds yield CONE and BLIP sensitivity matrices that visualize input-output properties and identify classes with higher sensitivity values.For a 10-class network, rows of the sensitivity matrix are represented as images; higher-sensitivity classes can focus an attack.
Adversarial attacks: For ReLU models, the box bounds do not directly generate attacks, whereas LP and SDP relaxations can provide upper bounds and candidate perturbed states and inputs.The SDP relaxation is convex and can retrieve an attack from an optimal input or a rank-one decomposition.

5. Sparsity and Model Compression.

Implicit models support several sparsity patterns that reduce computation, hidden-state dimension, or approximation error while preserving the fixed-point formulation.

Sparsity patterns: Element-wise sparsity in A, B, C, and D can speed up test-time computation, while rank sparsity uses low-rank model matrices.Appropriate penalties encourage both forms of sparsity during training.
Dimension reduction: Row sparsity of A reduces the fixed-point solve to the true hidden feature vector x1, and row sparsity of (A, B) reduces the state dimension to n1 < n.The reduced system avoids solving for state components that do not participate in the implicit feedback.
Dimension reduction: Column sparsity in A enables a closed-form expression for x2, producing a computational speedup.The state is decomposed into x1 and x2, with x2 determined directly from x1.
Dimension reduction: Column sparsity in (A⊤, C⊤)⊤ eliminates the need to compute x2 and reduces the state dimension to n1 < n.The prediction rule then depends only on the reduced state representation.
Dimension reduction: Row or column sparsity of A provides computational speedups, while zero corresponding rows of B or columns of C reduce prediction-rule dimensions.These effects follow from the structure of the implicit state equations.
Low-rank compression: A rank-k factorization A = LR⊤ changes the fixed-point equation from dimension n to dimension k and reduces per-iteration cost from O(n^2) to O(kn).The low-dimensional variable is z = R⊤x, and the stated savings apply when fixed-point iterations are used at test time.
Approximation error: Approximating A by A0 yields the state-error bound |x − x0| ≤ (I − (|A0 + E|))−1Ex0 when λpf(|A0 + E|) < 1.The bound assumes a CONE activation map and componentwise approximation error bounded by E.

6. Training Implicit Models.

Training implicit models combines loss minimization with equilibrium constraints and well-posedness conditions, using convex relaxations, gradient methods, and coordinate updates.

Training formulation: The training problem jointly learns A, B, C, D, and the state matrix X while enforcing X = φ(AX + BU) and well-posedness.The loss is convex in its prediction argument, and penalties can impose structure or sparsity.
Well-posedness: A practical formulation replaces the well-posedness requirement with the convex constraint ∥A∥∞≤κ for κ ∈ (0, 1).This constraint is used in the explicit training problem (6.4).
Regularization: Penalties can enforce upper-triangular structure, robustness, feature selection, and sparsity in the model matrices.Examples include norm constraints, sensitivity bounds, block norms, and element-wise l1 penalties.
Fenchel-divergence formulation: Fenchel-divergence reformulations replace the equilibrium equality with a divergence constraint or a relaxed penalty term.For many activation maps, the divergence is bi-convex, so fixing either argument makes the update convex.
Gradient methods: Projected gradient descent differentiates through the equilibrium equation, with gradients obtained by solving a matrix-valued fixed-point equation.Well-posedness guarantees a unique solution for the auxiliary gradient equation.
Coordinate methods: Block-coordinate descent alternates matrix updates with state updates, where the former can be convex and the latter can be solved by fixed-point iterations.Conditional-gradient updates can efficiently promote block sparsity by adding only a few nonzero elements per step.

7. Numerical experiments.

Numerical experiments demonstrate that implicit models can fit nonlinear regression functions and are evaluated against neural networks on synthetic classification datasets.

Regression: The regression experiment used 200 noisy inputs sampled uniformly between −5 and 5 and an implicit model of order n = 75.The well-posedness constraint was ∥A∥∞≤0.5, and the output noise had standard deviation approximately 0.57.
Regression: 0.56 RMSE was achieved after updating (C, D), compared with 0.65 RMSE for a tuned three-hidden-layer neural network.The implicit model first reached 1.77 RMSE after updating (A, B), then improved after linear regression on (C, D).
Regression: The regression comparison is presented as evidence that implicit models can fit nonlinear functions.Figure 9 compares the implicit prediction y(u) with f(u).
Overall comparison: The experiments report that implicit models have the potential to match or exceed neural-network performance across synthetic and real datasets.The comparison aligns the number of implicit hidden features with the neural-network architecture for fairness.
Classification setup: Synthetic classification datasets were generated from either a neural network or an implicit model, with both model classes fitted to each dataset.Inputs have dimension p = 5 and outputs have dimension q = 2; each dataset uses 20 training and test points.

0.76. The curves are generated from 5 the different runs with the lines marked as mean and region marked as the standard deviation

Figure 12 compares performance on a synthetic dataset generated from an implicit model, reporting an average best accuracy of 0.85 for the implicit method.

The figure compares the implicit method with neural networks on a synthetic dataset generated from an implicit model.
0.85 average best accuracy is reported for the implicit method.
The comparison concerns performance across methods evaluated on data generated from an implicit model.

0.74. The curves are generated from 5 different runs with the lines marked as mean and region marked as the standard deviation over the runs.

Across synthetic and image classification experiments, implicit models match or outperform reference neural networks. On MNIST and GTSRB, their average best accuracy is higher than the neural-network baselines.

Implicit models outperform neural networks in both synthetic experiments, potentially reflecting greater modeling capacity at similar parameter size.The paper reports this explanation as a possible reason for the observed advantage.
On MNIST, the implicit model matches the reference neural network’s accuracy during training.The reference is a 784-60-40-10 three-layer feedforward network, while the implicit model uses n = 100.
0.976 average best accuracy: implicit models versus 0.972 for neural networks on MNIST.The curves summarize 5 runs, with means shown as lines and standard deviations as regions.
0.874 average best accuracy: implicit models versus 0.859 for neural networks on GTSRB.The curves summarize 5 runs, with means shown as lines and standard deviations as regions.
Implicit models match and can outperform classical neural networks on the reported image-classification experiments.This conclusion is stated for the GTSRB experiment and is consistent with the MNIST comparison.

7.3. Adversarial attack.

The paper uses sensitivity matrices and optimization-based formulations to analyze and generate adversarial attacks. These approaches support input-independent feature selection, visually subtle failures, and both dense and sparse attacks.

Attack via the sensitivity matrix: Sensitivity matrices identify input features with higher output impact and can guide adversarial attacks on MNIST and CIFAR-10 models.Brighter sensitivity values indicate features whose perturbation has higher impact on the output.
Attack via the sensitivity matrix: Unlike gradient-based attacks, sensitivity-matrix attacks do not require an input sample and use model-level feature sensitivities.The gradient is described as a local, input-dependent version of the sensitivity matrix.
Attack via the sensitivity matrix: The sensitivity-matrix procedure can generate sparse attacks by perturbing selected high-sensitivity features.Figure 16 includes dense attacks with small perturbations and sparse attacks with randomly perturbed pixels.
Input-specific attacks: LP relaxation finds perturbed images that maximize discrepancy between perturbed and nominal hidden states for individual inputs.The resulting images can appear visually similar to clean images while causing incorrect predictions.
Input-specific attacks: Adding a cardinality constraint enables sparse attacks, and both sparse and non-sparse perturbations cause incorrect predictions in the reported examples.Figure 18 contrasts non-sparse attacks on the left with sparse attacks on the right.

8. Prior Work.

Prior work connects implicit learning to equilibrium models, lifted training formulations, and robustness analyses for neural networks. The paper positions its framework within these lines while emphasizing broader implicit representations and attack-quality analysis.

Implicit learning: Deep Equilibrium Models demonstrate an entirely implicit framework for sequence modeling.The paper identifies this work as a recent example of successful implicit deep learning.
Related architectures: Related approaches incorporate logical structures, model predictive control, quadratic-programming activations, or stochastic optimization into differentiable learning systems.These examples span semidefinite programming, reinforcement learning, implicit layers, and end-to-end learning.
Lifted models: Lifted training keeps the implicit state vector as a variable because the state generally lacks a closed-form expression and parameter gradients are challenging to compute.This produces a higher-dimensional formulation of the training problem.
Robustness: The paper formalizes robustness analysis through implicit prediction rules because many deep-learning architectures can be represented in that form.The stated motivation is the vulnerability of deep models and the ineffectiveness of some proposed defenses.
Robustness formulations: The paper’s SDP formulation parallels prior work and can be tightened by adding propagated input-uncertainty constraints.The comparison concerns how uncertainty constraints are handled at each neural-network layer.

9. Concluding Remarks.

Implicit models are connected to systems and control representations, enabling a perspective in which deep networks can operate inside dynamical-system loops. The paper also identifies non-unique representations as an open issue.

Cousins of implicit models: Implicit models separate linear operations from parameter-free nonlinear maps, yielding a block-diagram representation related to systems and control theory.The paper compares this representation with state-space and linear-fractional representations.
Cousins of implicit models: The framework connects deep networks with LTI and uncertain systems through representations involving dynamic linear operations and nonlinear maps.Figure 19 identifies LTI systems and uncertain systems as cousins of implicit models.
Future perspectives: Combining deep networks with dynamical systems could support feedback compositions and rigorous stability-margin analysis using LMIs or IQCs.The passage presents this as a prospect for future unified theory.
Open problem: A single prediction rule can have multiple implicit-model representations, including alternatives produced by diagonal scaling of model matrices.The paper suggests studying minimal representations based on hidden-state dimension n.

where

The paper develops existence, uniqueness, stability, and gradient-computation results for implicit models defined by equilibrium equations. It also gives practical procedures for training, mini-batch gradients, and constrained parameter updates.

Well-posedness: Under λpf(|A|) < 1, Picard iterates converge to a solution of x = φ(Ax + b), and decay of Mk establishes uniqueness.The proof uses invertibility of I − |A|, convergence of the associated series, and continuity of φ.
Well-posedness: Well-posedness of a block matrix is equivalent to well-posedness of its diagonal blocks when φ acts componentwise.The proof solves the second block first, then the first, and establishes the converse by varying b1 and b2.
Stability bounds: Theorems bound perturbation and iteration errors using non-expansivity, Lipschitz constants, and a nonnegative matrix whose spectral radius is below one.The resulting bounds follow from inequalities involving |A|, |A|^N, and M := diag(γ)N(A).
Gradient computation: Implicit differentiation yields gradients for A, B, C, and D through the unique matrix solution G = Φ(AG + I), computable by fixed-point recursion.The implementation avoids explicitly forming G and instead computes ∇zL through matrix-vector iterations.
Gradient computation: The gradient derivation provides a closed-form evaluation for all model parameters and extends efficiently to mini-batches for componentwise activation maps.The mini-batch formulation uses a suitable nonnegative matrix, norm vectors, and activation-derivative matrices.
Constrained updates: Projection onto the l∞ matrix-norm ball decomposes across rows and can be solved using parallel vectorized bisection over dual variables.Each row subproblem is handled through the dual, with rowwise dual variables collected into a vector interval.