# Faster Convergence in Deep-Predictive-Coding Networks to Learn Deeper
Representations

Isaac J. Sledge, _Member, IEEE_ , and José C. Príncipe, _Life Fellow, IEEE_
Isaac J. Sledge is the Senior Machine Learning Research Scientist and Dr.
Delores M. Etter Assistant Secretary of the Navy Emergent Engineer with the
Advanced Signal Processing and Automated Target Recognition Branch, Naval
Surface Warfare Center, Panama City, FL, USA (email: isaac.j.sledge@navy.mil).
He is the director of the Machine Intelligence Defense (MIND) lab at the US
Naval Sea Systems Command.José C. Príncipe is the Don D. and Ruth S. Eckis
Chair and the Distinguished Professor with both the Department of Electrical
and Computer Engineering and the Department of Biomedical Engineering,
University of Florida, Gainesville, FL, USA (email: principe@ufl.edu). He is
the director of the Computational NeuroEngineering Laboratory (CNEL) at the
University of Florida.The work of the authors was funded by grants
N00014-14-1-0542 (Marc Steinberg, ONR 35), N00014-19-WX-00636 (Marc Steinberg,
ONR 35), N00014-21-WX-01657 (Thomas McKenna, ONR 34), and N00014-21-WX-00476
(J. Tory Cobb, ONR 32) from the US Office of Naval Research. The first author
was also supported by in-house laboratory independent research (ILIR) grant
N00014-19-WX-00687 (Frank Crosby) from the US Office of Naval Research and a
Naval Innovation in Science and Engineering (NISE) grant from NAVSEA.

###### Abstract

Abstract—Deep-predictive-coding networks (DPCNs) are hierarchical, generative
models. They rely on feed-forward and feed-back connections to modulate latent
feature representations of stimuli in a dynamic and context-sensitive manner.
A crucial element of DPCNs is a forward-backward inference procedure to
uncover sparse, invariant features. However, this inference is a major
computational bottleneck. It severely limits the network depth due to learning
stagnation. Here, we prove why this bottleneck occurs. We then propose a new
forward-inference strategy based on accelerated proximal gradients. This
strategy has faster theoretical convergence guarantees than the one used for
DPCNs. It overcomes learning stagnation. We also demonstrate that it permits
constructing deep and wide predictive-coding networks. Such convolutional
networks implement receptive fields that capture well the entire classes of
objects on which the networks are trained. This improves the feature
representations compared with our lab’s previous non-convolutional and
convolutional DPCNs. It yields unsupervised object recognition that surpass
convolutional autoencoders and are on par with convolutional networks trained
in a supervised manner.

###### Index Terms:

Index Terms—Bio-inspired vision, predictive coding, unsupervised learning

## 1\. Introduction

Predictive coding is a promising theory for unsupervised sensory information
processing. Under this theory, a hierarchical, generative model [RaoRPN-
jour1999a, FristonK-jour2009a] of a dynamic environment is formed. This model
is consistently updated to infer possible states of the environment and
physical causes of the environmental stimuli. These causes, in turn, permit
reproducing the stimuli [SpratlingMW-jour2011a] (see Section 2).

Several predictive coders have been created and their biological plausibility
investigated [SrinivasanMV-jour1982a, RaoRPN-jour1999a, JeheeJFM-jour2006a,
FristonK-jour2008a]. None of these early contributions has been known to form
causes that are highly discriminative for complex stimuli, however. Our lab
thus developed multi-stage, deep-predictive-coding networks (DPCNs)
[ChalasaniR-conf2013a, PrincipeJC-jour2014a, ChalasaniR-jour2015a]. We showed
that DPCNs could form discriminative causes of temporal, spatial, and spatio-
temporal stimuli in certain cases. Alternate networks later followed [LotterW-
conf2017a, HanK-coll2018a].

DPCNs learn about an environment in an unsupervised manner. They can thus be
thought of as parameter-light, non-traditional autoencoders. DPCNs differ
substantially from autoencoders, though. The former contain feed-forward and
recurrent, feed-back connections, allowing information to be propagated
between stages to stabilize the internal representation. Another distinction
is that DPCNs do not have a corresponding decoder. They hence require a self-
organizing principle to be effective. That is, they must learn to extract
meaningful features, in the form of causes, that cluster the stimuli
effectively. This clustering objective is aided by imposing cause sparsity and
transformation invariance. Including these cause constraints make DPCNs
generalize well to novel stimuli. Lastly, DPCNs are composed of stages, not
layers. Each stage implements a recurrent state model. This permits DPCNs to
characterize the dynamics of temporal and spatio-temporal stimuli.

DPCNs exhibit promise for unsupervised object recognition in images and video.
Often, convolutional DPCNs like [ChalasaniR-jour2015a] learn sparse, invariant
features that are better for classification than those from convolutional
autoencoders. Such behavior arises from the interaction of feed-forward and
feed-back connections in the DPCNs. It also arises due to the implicit
supervision imposed from leveraging temporal information [BakerR-jour2014a].
Multiple presentations of the stimuli additionally facilitate the extraction
of spatial and temporal regularities [PerruchetP-jour2006a, AslinRN-
jour2012a], which we hypothesize permits high-level object analysis [BradyTF-
jour2007a], like object recognition. Sparsity contributes too [ZylberbergJ-
jour2011a, CarlsonNL-jour2012a], as it aids in generalization and can preempt
overfitting to specific stimuli.

Learning sufficiently robust features in a DPCN is quite computationally
intensive. A multi-stage optimization strategy, based on proximal gradients
[GulerO-jour1992b, BeckA-jour2009a], is typically used [ChalasaniR-conf2013a,
PrincipeJC-jour2014a, ChalasaniR-jour2015a] to conduct feed-forward and feed-
back inference of the causes. Both forms of inference are needed for cause
self-organization. Sub-quadratic function-value convergence rates are
theoretically guaranteed for this strategy [ChambolleA-jour2015a, AttouchH-
jour2016a]. Only sub-linear rates are often obtainable, however, due to severe
oscillations in the cost. That is, the search is not a pure descent strategy
in some cases. This has the dual effect of returning poor causes and doing so
slowly.

Due to these optimization difficulties, DPCNs are practically limited to two
stages. Two stages may be sufficient for characterizing certain stimuli.
However, it typically will not yield representations that handle objects in
complex environments. The networks exhibit poor stimuli-reconstruction
performance when extended beyond two stages due to being stymied by poor
convergence [SantanaE-jour2018a]. The deeper stages do not reach a stable
cause representation, which impacts the causes in preceding stages. Learning
essentially stagnates regardless of how many stimuli are presented. This, in
turn, prevents object recognition for many challenging environments. The
causes simply do not organize the stimuli well. Moreover, the causes are not
semantically rich enough to handle distractors. Even simple textural
backgrounds in visual stimuli can be sufficiently distracting enough to
confound the DPCNs. The causes are also sometimes unable to handle object
variability effectively. They cannot always resolve that objects from distinct
viewpoints are same, for instance.

Here, we develop a novel inference process that enables investigators to go
beyond the two-stage network limitation that is observed in practice for
DPCNs. This leads to what we refer to as accelerated DPCNs (ADPCNs). Both the
DPCNs and ADPCNs are unsupervised networks. They share the same underlying
architecture, with one exception: the ADPCNs extract convolutional features
(see Section 3). Both properties mean that ADPCNs are better suited for
discrimination than our lab’s original, non-convolutional DPCNs [ChalasaniR-
conf2013a, PrincipeJC-jour2014a]. The improved inference also makes ADPCNs
better than our lab’s convolutional-recurrent-predictive networks (CRPNs)
[ChalasaniR-jour2015a]. CRPNs similarly rely on slow proximal-gradient
inference.

More specifically, we replace the proximal gradient search in the original
DPCN with an accelerated version (see Section 3). The accelerated approach in
the ADPCN relies on a polynomial inertial sequence for updating the internal
feature representations. The inertial sequence has the effect of sufficiently
delaying the occurrence of cost oscillation. We prove this (see Appendix A).
Monotonically decreasing costs occur throughout almost all of the learning
process. We perform in-place restarts of the inference when it does not. The
ADPCNs therefore extract meaningful error signals that stabilize the sparse
causes early during training. ADPCNs also possesses a faster, sub-polynomial
rate of function-value convergence compared to the inference scheme used by
DPCNs (See Appendix A). ADPCNs hence exhibit improved empirical convergence
too over DPCNs. We are thus able to efficiently train both deep and wide
predictive-coding networks whose learning does not stall. The deep
convolutional layers of the ADPCN extract progressively richer,
transformation-invariant features for sparsely describing complex stimuli.
They aid in stimuli generalization. Wide convolutional layers better
approximate interactions between stimuli and causes than narrower ones. They
promote some measure of stimuli memorization without overfitting, which
permits recognizing perceptually similar objects from the same class. While
such behaviors can manifest in convolutional DPCNs, they do not due to the
aforementioned slow inference.

We show that the deeper and wider feature representations from the ADPCN are
far more robust than those obtainable for DPCNs. Even a single stage
difference between convolutional DPCNs and ADPCNs leads to a huge improvements
in discriminability. In particular, the later-stage causes in the ADPCNs have
receptive fields that embody the entirety of the objects being presented,
despite the lack of training labels (see Section 3). We observe this
phenomenon across a variety of benchmark datasets. It enables multi-class
object recognition under different scene conditions. The ADPCNs can handle
perspective changes, shape changes, illumination changes, and more. ADPCNs
thus form an approximate identity mapping that preserves perceptual
difference. Whole-object sensitivity also yields unsupervised classifiers that
are on par with supervised-trained convolutional and convolutional-recurrent
networks (see Appendix B). The ADPCNs have orders of magnitude fewer
parameters, though, than these other deep networks. ADPCNs, just like DPCNs,
are parameter-light, non-traditional autoencoders.

## 2\. Predictive Coding

The objective of predictive coding is to approximate external sensory stimuli
using generative, latent-variable models. Such models hierarchically encode
residual prediction errors. The prediction errors are the differences between
either the actual stimuli or a transformed version of it and the predicted
stimuli produced from the underlying latent variables. We refer to these
latent variables as causes. We also interchangeably refer to causes as
features.

By learning in this way, the internal representations of a predictive-coding
model are modified only for unexpected changes in the stimuli. This enables a
model to recall stimuli that it has encountered before. It also enables the
model to adapt to new stimuli without disrupting its internal representation
of the environment for previously observed stimuli.

We can characterize predictive coding in the following way for temporal and
spatio-temporal stimuli. Examples include audio and video, respectively. Both
DPCNs and ADPCNs are instances of this general framework.

  * Definition 1: Predictive Coding Model. Let $y_{t}\\!\in\\!\mathbb{R}^{p}$ represent a time-varying sensory stimulus at time $t$. The stimuli can be described by an underlying cause, $\kappa_{1,t}\\!\in\\!\mathbb{R}^{d_{1}}$, and a time-varying intermediate state,
$\gamma_{1,t}\\!\in\\!\mathbb{R}^{k_{1}}$, through a pair of
$\theta$-parameterized mapping functions,
$f_{1}:\mathbb{R}^{k_{1}}\\!\to\\!\mathbb{R}^{p}$, the cause-update function,
and
$g_{1}:\mathbb{R}^{k_{1}}\\!\times\\!\mathbb{R}^{d_{1}}\\!\to\\!\mathbb{R}^{k_{1}}$,
the state-transition function. These functions define a latent-variable model,

$y_{t}\\!=\\!f_{1}(\gamma_{1,t};\theta)\\!+\\!\epsilon_{1,t},\;\gamma_{1,t}\\!=\\!g_{1}(\gamma_{1,t-1},\kappa_{1,t};\theta)\\!+\\!\epsilon_{0,t}^{\prime}.$

Here, $\epsilon_{1,t}\\!\in\\!\mathbb{R}^{p}$ and
$\epsilon_{1,t}^{\prime}\\!\in\\!\mathbb{R}^{k_{1}}$ are noise terms that
represent the stochastic and model uncertainty, respectively, in
the predictions. This model can be extended to a multi-stage hierarchy by
cascading additional $\theta$-parameterized mapping functions,
$f_{i}:\mathbb{R}^{k_{i}}\\!\to\\!\mathbb{R}^{d_{i-1}}$ and
$g_{i}:\mathbb{R}^{k_{i}}\\!\times\\!\mathbb{R}^{d_{i}}\\!\to\\!\mathbb{R}^{k_{i}}$,
at each stage $i$ beyond the first,

$\kappa_{i-1,t}\\!=\\!f_{i}(\gamma_{i,t};\theta)\\!+\\!\epsilon_{i,t},\;\gamma_{i,t}\\!=\\!g_{i}(\gamma_{i,t-1},\kappa_{i,t};\theta)\\!+\\!\epsilon_{i,t}^{\prime}.$

Here, $\kappa_{i,t}\\!\in\\!\mathbb{R}^{d_{i}}$,
$\gamma_{i,t}\\!\in\\!\mathbb{R}^{k_{i}}$,
$\epsilon_{i,t}\\!\in\\!\mathbb{R}^{d_{i-1}}$ and
$\epsilon_{i,t}^{\prime}\\!\in\\!\mathbb{R}^{k_{i}}$.

Spatial stimuli, which include images, are a degenerate case of this
framework. They have no temporal component, so there is no modification of the
states as they are fed back. States are still extracted, though. Predictive
coding thus behaves similarly to sparse coding [HyvarinenA-jour2001a] in this
case. The main difference is that, for predictive coding, the states are
pooled and transformed to form causes. Sparse coding only has notions of
states. For DPCNs and ADPCNs, the causes are made invariant, which aids in
discrimination. Feature invariance does not naturally occur in many sparse
coding and hierarchical sparse coding models [BoutinV-jour2020a, BoutinV-
jour2021a].

For the above framework, both feed-forward, bottom-up and feed-back, top-down
processes are used to characterize observed stimuli. For the feed-forward
case, the observed stimuli are propagated through the model to extract
progressively abstract details. The stimuli are first converted to a series of
states that encode either spatial, temporal, or spatio-temporal relationships.
The type of relationship depends on the stimuli being considered. These states
are then made invariant to various transformations, thereby forming the hidden
causes. The causes are latent variables that describe the environment, as we
noted above.

The causes at lower stages of the model form the observations to the stages
above. Hidden causes therefore provide a link between the stages. The states,
in contrast, both connect the dynamics over time, to ignore temporal
discontinuities [StoneJV-jour2008a], and mediate the effects of the causes on
the stimuli [FristonK-jour2008a]. In the feed-back case, the model generates
top-down predictions such that the neural activity at one stage predicts the
activity at a lower stage. The predictions from a higher level are sent
through feed-back connections to be compared to the actual activity. This
yields a model uncertainty error that is forwarded to subsequent stages to
update the population activity and improve prediction. Such a top-down process
repeats until the bottom-up stimuli transformation process no longer imparts
any new information. That is, there are no unexpected changes in the stimuli
that the model cannot predict. Once this occurs, if the model is able to
synthesize the input stimuli accurately using the uncovered features, then it
means that it has previously seen a similar observation [SchendanHE-
jour2008a].

In short, a predictive-coding model has two processing pathways. Recurrent,
top-down connections carry predictions about activity to the lower model
levels. These predictions reflect past experience [FristonK-jour2008a]. They
form priors to disambiguate the incoming sensory inputs. Bottom-up connections
relay prediction errors to higher levels to update the physical causes. The
interaction of the feed-forward and feed-back connections [HosoyaT-jour2005a]
on the causes enables robust object analysis [AuksztulewiczR-jour2016a] from
the observed stimuli. A well-trained predictive-coding model should thus
distinguish between objects, despite learning about them in an unsupervised
way. This only occurs if the models preserve some notion of perceptual
difference.

Figure 1: An overview of the ADPCN architecture. For simplicity, the ADPCN is
presented for only one stage, but more stages are implicitly assumed for top-
down feed-back purposes. Note that the final stage of the DPCN has no output,
unlike in a standard autoencoder network. The goal of the ADPCN is to learn a
series of causes that explain the input stimuli, in this case, frames from a
video of a bird, and hence recreate them. Each stage in an ADPCN can be
roughly decomposed into two inference phases, one for updating the states and
the other for updating the causes. State and causal inference relies on intra-
stage feed-forward (black lines) and feed-back processes (gray lines), along
with intra-stage recurrent feed-back (blue lines). Much of the network is
devoted to feed-back processes to provide self supervision. Inter-stage feed-
back (red line) of higher-level states is used to update the lower-level
causes. For the inference process, we denote multiplication of a quantity on a
given path with a rounded square. Addition, subtraction, and multiplication of
quantities along multiple paths are denoted using circular gated symbols.
Pooling is denoted using a down arrow inside a rounded square. The function
blocks apply a sparsity operation to the quantities on the given path;
corresponding parameter values for these operations are offset from these
blocks. Function blocks offset from circular gates denote rectified, linear-
unit operations. Norm blocks offset from the circular gates denote squared-
norm operations. We omit showing the actual optimization process but note that
the feed-forward connections are largely devoted to computing gradients of the
two cost functions, $\nabla_{\gamma_{i,t}}\mathcal{L}_{1}$ and
$\nabla_{\kappa_{i,t}}\mathcal{L}_{2}$, that are used to update the states
$\gamma_{i,t}$ and causes $\kappa_{i,t}$. We also omit showing the update of
$\lambda_{i,t}$ along with the updates for the matrices $C_{i}$, $D_{i}$, and
$G_{i}$.

## 3\. Deep Predictive Coding

We propose an efficient architecture for the above hierarchical, latent-
variable model. This model is suitable for uncovering discriminative details
from the stimuli.

More specifically, we consider a faster, convolutional DPCN, the ADPCN. ADPCNs
can extract highly sparse, invariant features for either dynamic or static
stimuli (see Section 3.1). We then show how to effectively infer the ADPCN’s
latent variables using a fast proximal gradient scheme (see Section 3.2). This
optimization process permits effectively forming deep feature hierarchies that
preserve perceptual differences. It typically overcomes the learning
stagnation that we observed in DPCNs. Convergence properties are presented in
the online appendix (see Appendix A). In this appendix, we prove why
stagnation occurs in the DPCNs. We also quantify the convergence rate of the
DPCNs and ADPCNs to show that the latter, theoretically, converge more quickly
than the former. This justifies our new inference process, as do our empirical
results.

## 3.1 ADPCN Cost Functions

ADPCNs consist of two phases at each stage, which are outlined in fig. 1. The
first phase entails inferring the hidden states, which are a feature-based
representation used to describe the stimuli. States are formed at the first
phase via sparse coding in conjunction with a temporal-state-space model.
Stimuli are mapped to an over-complete dictionary of convolutional filters.
Subsequent ADPCN stages follow the same process, with the only change being
that the hidden causes assume the role of the observed stimuli.

We define state inference via a least-absolute-shrinkage-and-selection-
operator (LASSO) cost. We present this for the case of single-channel stimuli,
for the ease of readability. The extension to multiple channels is
straightforward.

  * Definition 2: State LASSO Cost. Let $\gamma_{i,t}\\!\in\\!\mathbb{R}^{k_{i}}$ be the hidden states at time $t$ and at model stage $i$. Let $C_{i}\\!\in\\!\mathbb{R}^{k_{i}\times k_{i}}$ be a hidden-state-transition matrix. Let $D_{i}^{\top}\\!\in\\!\mathbb{R}^{k_{i}\times k_{i-1}}$ be a Toeplitz-form matrix with $q_{i}\\!\in\\!\mathbb{N}_{+}$
filters structured as in [SulamJ-jour2018a]. The state-inference cost function
to be minimized, with respect to $\gamma_{i,t}$, $C_{i}$, and
$D_{i,q}^{\top}$, is given by

$\mathcal{L}_{1}(\gamma_{i,t},\kappa_{i,t},C_{i},D_{i}^{\top};\alpha_{i},\lambda_{i,t})=\frac{1}{2}\Bigg{(}\|\kappa_{i-1,t}\\!-\\!D_{i}^{\top}\gamma_{i,t}\|_{2}^{2}+\alpha_{i}\|\gamma_{i,t}\\!-\\!C_{i}\gamma_{i,t-1}\|_{1}+\sum_{k^{\prime}=1}^{k_{i}}[\lambda_{i,t}]_{k^{\prime}}|[\gamma_{i,t}]_{k^{\prime}}|\Bigg{)},$

where $\kappa_{0,t}\\!=\\!y_{t}$. The first term in this cost quantifies the
$L_{2}$ prediction error,
$\epsilon^{\prime}_{i,t}\\!=\\!\kappa_{i-1,t}\\!-\\!D_{i}^{\top}\gamma_{i,t}$,
at stage $i$. The aim is to ensure that the local reconstruction error between
stages is minimized. The second term constrains the next-state dynamics to be
described by the state-transition matrix. For static stimuli, indexed by $t$,
the state feed-back is replaced by
$\kappa_{i,t}\\!-\\!D_{i+1}^{\top}\gamma_{i+1,t}$. The strength of the
recurrent feed-back connection is driven by
$\alpha_{i}\\!\in\\!\mathbb{R}_{+}$. The transitions are $L_{1}$-sparse to
make the state-space representation consistent. Without such a norm penalty,
the innovations would not be sparse due to the feed-back. The final term
enforces $L_{1}$-sparsity of the states, with the amount controlled by
$\lambda_{i,t}\\!\in\\!\mathbb{R}_{+}^{k_{i}}$.

  * Proposition 1. Let $\gamma_{i,t}\\!\in\\!\mathbb{R}^{k_{i}}$ be the hidden states at time $t$ and at model stage $i$. Let $D_{i}^{\top}\\!\in\\!\mathbb{R}^{k_{i}\times k_{i-1}}$ be
a Toeplitz-form matrix of $q_{i}\\!\in\\!\mathbb{N}_{+}$ filters. The matrix-
vector multiplication $D_{i}^{\top}\gamma_{i,t}$ is functionally equivalent to
convolution for all stages $i$.

When projected back into the original visual space of the input, the
dictionaries define a series of receptive fields. The hidden states, at least
for the initial stages of the hierarchy thus act as basic feature detectors.
They often resemble the simple cells in the visual cortex [OlshausenBA-
jour1996a].

Ideally, we would prefer $L_{0}$-sparsity to the $L_{1}$ variant used in the
state-inference cost, as it does not impose shrinkage on the hidden-state
values. However, by sacrificing this property, we gain cost convexity, which
aids in efficient numerical optimization with provable convergence.

  * Proposition 2. Let $\gamma_{i,t}\\!\in\\!\mathbb{R}^{k_{i}}$ be the hidden states at time $t$ and at model stage $i$. Let $C_{i}\\!\in\\!\mathbb{R}^{k_{i}\times k_{i}}$ be a hidden-state-transition matrix. Let $D_{i}^{\top}\\!\in\\!\mathbb{R}^{k_{i}\times k_{i-1}}$ be a Toeplitz-form matrix with $q_{i}\\!\in\\!\mathbb{N}_{+}$ filters. Let $\alpha_{i},\lambda_{i,t}\\!\in\\!\mathbb{R}_{+}$.
The hidden-state cost function
$\mathcal{L}_{1}(\gamma_{i,t},\kappa_{i,t},C_{i},{D_{i}^{\top}};\alpha_{i},\lambda_{i,t})$
is convex for appropriate parameter values.

Note that the state LASSO may switch from convex to non-convex as the
variables are updated during inference. We may thus only recover local
minimizers, not global ones.

The state-based feature representations constructed by the first phase are not
guaranteed to be invariant to various transforms. Discrimination can be
impeded, as a result. The second ADPCN processing phase thus entails
explicitly imposing this behavior. Local translation invariance is attained by
leveraging the spatial relationships of the states in neighborhoods via the
max-pooling of states. Invariance to more complex transformations, like
rotation and spatial frequency, is made possible through the inference of
subsequent hidden causes.

Sparse cause inference is driven by a LASSO-based cost that captures non-
linear dependencies between components in the pooled states. We present this
cost for the case of a single convolutional layer, for the ease of
readability. We utilize multiple layers in our simulations.

  * Definition 3: Cause LASSO Cost. Let $\gamma_{i,t}\\!\in\\!\mathbb{R}^{k_{i}}$ be the hidden states and $\kappa_{i,t}\\!\in\\!\mathbb{R}^{d_{i}}$ be the bottom-up hidden causes at time $t$ and model stage $i$. Let $\kappa^{\prime}_{i,t}\\!\in\\!\mathbb{R}^{d_{i}}$ be the top-down-inferred causes. Let $C_{i}\\!\in\\!\mathbb{R}^{k\times k}$ be a hidden-
state-transition matrix. Let $D_{i}^{\top}\\!\in\\!\mathbb{R}^{k_{i}\times
k_{i-1}}$ be a Toeplitz-form matrix of $q_{i}\\!\in\\!\mathbb{N}_{+}$ filters.
Let $G_{i}\\!\in\\!\mathbb{R}^{d_{i}\times k_{i}}$ be an
invariant Toeplitz matrix. The hidden-cause cost to be minimized, with respect
to $\kappa_{i,t}$ and $G_{i}$, is given by

$\mathcal{L}_{2}(\gamma_{i,t},\kappa_{i,t},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t})=\frac{1}{2}\Bigg{(}\\!\Bigg{(}\sum_{j=1}^{n}\sum_{k^{\prime}=1}^{k_{i}}|[\lambda_{i,t}]_{k^{\prime}}\gamma_{i,t}^{j}|\Bigg{)}+\eta_{i}^{\prime}\|\kappa_{i,t}\\!-\\!\kappa^{\prime}_{i,t}\|_{2}^{2}+\lambda_{i}^{\prime}\|\kappa_{i,t}\|_{1}\\!\Bigg{)},$

where
$\lambda_{i,t,k^{\prime}}\\!=\\!\alpha_{i}^{\prime}(1\\!+\\!\textnormal{exp}(-[G_{i}^{\top}\kappa_{i,t}]_{k}))$,
$\alpha_{i}^{\prime}\\!\in\\!\mathbb{R}$. The first term in this cost models
the multiplicative inter-
action of the causes $\kappa_{i,t}$ with the max-pooled states
$\gamma_{i,t}^{j}$ through an invariant Toeplitz matrix $G_{i}$. This
characterizes the shape of the sparse prior on the states. That is, the
invariant matrix is adapted such that each component of the causes are
connected to element groups in the accumulated states that co-occur
frequently. Co-occurring components typically share common statistical
regularities, thereby yielding locally invariant representations [KarklinY-
jour2006a]. The second term specifies that the difference between the bottom-
up $\kappa_{i,t}$ and top-down inferred causes $\kappa^{\prime}_{i+1,t}$
should be small, with the term weight specified by
$\eta_{i}^{\prime}\\!\in\\!\mathbb{R}_{+}$. The final term imposes $L_{1}$
sparsity, with
the amount controlled by $\lambda_{i}^{\prime}\\!\in\\!\mathbb{R}_{+}$, to
prevent the intermediate representations from being dense.

The causes obtained by solving the above LASSO cost will behave somewhat like
complex cells in the visual cortex [ItoM-jour2004a]. Similar results are found
in temporally coherent networks [HurriJ-coll2003a], albeit without guaranteed
feature invariance.

As with the state-inference cost, we employ $L_{1}$ sparsity in the hidden-
cause cost for practical reasons, even though we would prefer $L_{0}$ sparsity
for its theoretical appeal.

  * Proposition 3. Let $\gamma_{i,t}\\!\in\\!\mathbb{R}^{k_{i}}$ be the hidden states and $\kappa_{i,t}\\!\in\\!\mathbb{R}^{d_{i}}$ be the hidden causes at time $t$ and model stage $i$. Let $C_{i}\\!\in\\!\mathbb{R}^{k_{i}\times k_{i}}$ be a hidden-state transition-matrix, $D_{i}^{\top}\\!\in\\!\mathbb{R}^{k_{i}\times k_{i-1}}_{+}$ be a Toeplitz-form matrix of filters,
and $G_{i}\\!\in\\!\mathbb{R}^{d_{i}\times k_{i}}$ be an invariant Toeplitz
matrix. Let
$\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime}\\!\in\\!\mathbb{R}_{+}$
and $\lambda_{i,t}\\!\in\\!\mathbb{R}_{+}^{k_{i}}$. The hidden-cause cost-
function
$\mathcal{L}_{2}(\gamma_{i,t},\kappa_{i,t},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t})$
is convex for appropriate parameter values.

Practically, we have found that traditional $L_{0}$ sparsity in the ADPCN
preempts learning. The causes are often too sparse to act as priors. Large
errors continuously accumulate, so the APDCNs are unable to reduce the
residual prediction errors. Approximating the $L_{0}$ term is often a better
option. We will explore it more in our future endeavors.

ADPCNs and the DPCNs our lab proposed [ChalasaniR-conf2013a, PrincipeJC-
jour2014a] have almost the same cost functions that we outline above. They
both build unsupervised representations of input stimuli [FoldiakP-jour1991a]
via a free-energy principle [FristonK-jour2006a]. The difference is that
ADPCNs implement convolution by way of the Toeplitz-form matrix of filters.
The original DPCNs relies on non-convolutional filters. The expressive power
of these DPCNs is thus quite poor for complex stimuli compared to the ADPCNs.
ADPCNs can take advantage of local spatial coherence in addition to temporal
coherence. They hence require fewer filters than DPCNs to extract meaningful
stimuli representations.

Defining states and causes as we have specified above has significant
advantages. ADPCNs are, for instance, incredibly parameter efficient compared
to standard recurrent-convolutional autoencoders. Few filters often are needed
to adequately synthesize an observed stimuli under varying conditions. This is
a byproduct of the explicit feature invariance imposed by the non-linear,
sparse cause inference. ADPCNs are also far more efficient and effective than
alternate DPCNs that have been proposed. For instance, the DPCN proposed by
Lotter et al. [LotterW-conf2017a] relies on convolutional, long shot-term
memories (LSTMs) to model spatio-temporal stimuli. LSTM cells can only store
and recall a single event through time, limiting their characterization of
complex temporal patterns. Many LSTM cells are needed for associative event
recall. They also require lengthy inference times. Behaviors like
memorization, associative recall, and others are possible with ADPCNs. ADPCNs
can be kernelized to realize non-linear, non-parametric state-space updates,
further increasing the ADPCNs’ expressive power without impacting inference
times. The DPCN proposed by Han et al. [HanK-coll2018a] relies on
convolutional layers with linear recurrent feedback, similar to our lab’s
recurrent-convolutional, winner-take-all networks [SantanaE-jour2018a].
However, the network in [HanK-coll2018a] lacks an unsupervised organization
mechanism.

## 3.2 ADPCN Inference

The propagation and transformation of observed stimuli in a ADPCN is more
involved than for standard network architectures. At any stage in the ADPCN,
the hidden, sparse states and unknown, sparse causes that minimize the two-
part LASSO cost must be inferred to create the feed-forward observations for
the next ADPCN stage.

Joint inference of the states and causes can be done in a manner similar to
block coordinate descent. That is, for a given mini-batch of stimuli, the
states can be updated by solving the corresponding LASSO cost while holding
the causes fixed. The causes can then be updated while holding the states
fixed. Altering either of these representations amounts to solving a
convolutional, $L_{1}$-sparse-coding problem. The presence of discontinuous,
$L_{1}$-based terms in the LASSO costs complicates the application of standard
optimization techniques, though.

Here, we consider a fast proximal-gradient-based approach for separating and
accounting for the smooth and non-smooth components of the LASSO costs. This
approach is motivated and analyzed in the appendix.

  * Definition 4: Feed-Forward, Bottom-Up State Inference. Let $\gamma_{i,t}\\!\in\\!\mathbb{R}^{k_{i}}$ be the hidden states and $\pi_{i,t}\\!\in\\!\mathbb{R}^{k_{i}}$ be the auxiliary hidden states at time $t$ and model stage $i$. These auxiliary hidden states will be combinations of
hidden states across different times. Let
$C_{i}\\!\in\\!\mathbb{R}^{k_{i}\times k_{i}}$ be a hidden-state-transition
matrix. As well, let
$D_{i}^{\top}\\!\in\\!\mathbb{R}^{k_{i}\times k_{i-1}}$ be a Toeplitz-form
matrix of $q_{i}\\!\in\\!\mathbb{N}_{+}$ filters. For an inertial sequence
$\beta_{m}\\!\in\\!\mathbb{R}_{+}$ and an adjust-
able step size $\tau_{i,t}^{m}\\!\in\\!\mathbb{R}_{+}$, the hidden-state
inference process, indexed by iteration $m$, is given by the following
expressions

$\gamma_{i,t+1}^{m}\\!=\\!\textnormal{\sc
prox}_{\\!\lambda_{i,t}}\\!\Bigg{(}\\!\pi_{i,t}^{m}\\!-\\!\lambda_{i,t}\tau^{m}_{i,t}\nabla_{\pi_{i,t}^{m}}\mathcal{L}_{1}(\pi_{i,t}^{m},\kappa_{i,t},C_{i},D_{i}^{\top};\alpha_{i},\lambda_{i,t})\\!\Bigg{)},\;\;\pi_{i,t}^{m+1}\\!=\\!\gamma_{i,t+1}^{m}\\!+\\!\beta_{m}(\gamma_{i,t+1}^{m}\\!-\\!\gamma_{i,t+1}^{m-1})$

with
$\mathcal{L}_{1}(\pi_{i,t}^{m},\kappa_{i,t},C_{i},D_{i}^{\top};\alpha_{i},\lambda_{i,t})\\!=\\!D_{i}^{\top}(\kappa_{i-1,t}\\!-\\!D_{i}\pi_{i,t}^{m})\\!+\\!\alpha_{i}\Omega_{i}(\pi_{i,t}^{m})$.
Here, use a Nesterov smoothing,
$\Omega_{i}(\pi_{i,t}^{m})\\!=\\!\textnormal{arg
max}_{\|\Omega_{i,t}\|_{\infty}\leq
1}\Omega_{i,t}^{\top}(\pi_{i,t}^{m}\\!-\\!C_{i}\pi_{i,t}^{m-1})$,
$\Omega_{i,t}\\!\in\\!\mathbb{R}^{k_{i}}$, to approximate the non-smooth state
transition. Small values for the hidden states are clamped via a soft
thresholding function implicit to the proximal operator, which leads to a
sparse solution. The states are then spatially max pooled over local
neighborhoods, using non-overlapping windows, to reduce their resolution,
$\gamma_{i,t+1}\\!=\\!\textnormal{\sc pool}(\gamma_{i,t+1})$.

  * Definition 5: Feed-Forward, Bottom-Up Cause Inference. Let $\gamma_{i,t}\\!\in\\!\mathbb{R}^{k_{i}}$ be the hidden states and
$\kappa_{i,t}\\!\in\\!\mathbb{R}^{d_{i}}$ be the hidden causes at time $t$ and
model stage $i$. Let $C_{i}\\!\in\\!\mathbb{R}^{k_{i}\times k_{i}}$ be a
hidden-state-transition matrix,
$D_{i}^{\top}\\!\\!\in\\!\mathbb{R}^{k_{i}\times k_{i-1}}$ be a Toeplitz-form
matrix of $q_{i}\\!\in\\!\mathbb{N}_{+}$ filters, and
$G_{i}\\!\in\\!\mathbb{R}^{d_{i}\times k_{i}}$ be an invariant Toeplitz
matrix. For an adjustable step size
$\tau^{\prime}_{i,t}{}^{\\!m}\\!\in\\!\mathbb{R}_{+}$ and inertial sequence
$\beta_{m}^{\prime}\\!\in\\!\mathbb{R}_{+}$, the hidden-cause inference
process, indexed by $m$, is given by the following expressions

$\kappa_{i,t+1}^{m}\\!=\\!\textnormal{\sc
prox}_{\\!\lambda_{i}^{\prime}}\\!\Bigg{(}\\!\pi^{\prime}_{i,t}{}^{\\!\\!\\!\\!m}\\!-\\!\lambda_{i}^{\prime}\tau^{\prime}_{i,t}{}^{\\!m}\nabla_{\pi^{\prime}_{i,t}{}^{\\!m}}\mathcal{L}_{2}(\gamma_{i,t+1},\pi^{\prime}_{i,t}{}^{\\!m},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t})\\!\Bigg{)},\;\;\pi^{\prime}_{i,t}{}^{\\!m+1}\\!=\\!\kappa_{i,t+1}^{m}\\!+\\!\beta^{\prime}_{m}(\kappa_{i,t+1}^{m}\\!-\\!\kappa_{i,t+1}^{m-1})$

with
$\nabla_{\pi^{\prime}_{i,t}{}^{\\!m}}\mathcal{L}_{2}(\gamma_{i,t+1},\pi^{\prime}_{i,t}{}^{\\!m},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t})\\!=\\!-\alpha_{i}^{\prime}G_{i}^{\top}\textnormal{exp}(-G_{i}\pi^{\prime}_{i,t}{}^{\\!m})|\gamma_{i,t+1}^{j}|\\!+\\!2\eta_{i}^{\prime}(\kappa_{i,t+1}^{m}\\!-\\!\kappa^{\prime}_{i+1,t})$.
Small
values for the hidden causes are clamped via an implicit soft thresholding
function, leading to a sparse solution.
The inferred causes are used to update the sparsity parameter
$\lambda_{i,t+1}\\!=\\!\alpha_{i}^{\prime}(1\\!+\\!\textnormal{exp}(-\textnormal{\sc
unpool}(G_{i}\kappa_{i,t+1})))$ via
spatial max unpooling.

In both cases, the step size is bounded by the Lipschitz constant of the LASSO
cost to be solved. The choice of the inertial sequence greatly affects the
convergence properties of the optimization.

  * Proposition 4. Let $\gamma_{i,t}\\!\in\\!\mathbb{R}^{k_{i}}$ be the hidden states and $\kappa_{i,t}\\!\in\\!\mathbb{R}^{d_{i}}$ be the hidden causes. The state iterates
$\\{\gamma_{i,t+1}^{m}\\}_{m=1}^{\infty}$ strongly converge to the global
solution of
$\mathcal{L}_{1}(\gamma_{i,t},\kappa_{i,t},C_{i},D_{i}^{\top};\alpha_{i},\lambda_{i,t})$
for the accelerated proximal gradient scheme. Likewise, the cause iterates
$\\{\kappa_{i,t+1}^{m}\\}_{m=1}^{\infty}$ for the accelerated proximal
gradient scheme strongly converge to the global solution of
$\mathcal{L}_{2}(\gamma_{i,t+1},\kappa_{i,t},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t})$
at a sub-polynomial rate. This occurs when using the inertial sequences
$\beta_{m},\beta^{\prime}_{m}\\!=\\!(k_{m}\\!-\\!1)/k_{m+1}$, where $k_{m}$
depends polynomially on $m$.

In this bottom-up inference process, there is an implicit assumption that the
top-down predictions of the causes are available. This, however, is not the
case for each iteration of a mini batch being propagated through the ADPCN. We
therefore consider an approximate, top-down prediction using the states from
the previous time instance and, starting from the first stage, perform bottom-
up inference using this prediction.

  * Definition 6: Feed-Back, Top-Down Cause Inference. At the beginning of every time step $t$, using the state-space model at each stage, the likely top-down causes, $\kappa^{\prime}_{i-1,t}\\!\in\\!\mathbb{R}^{d_{i-1}}$, are predicted using the previous
states $\gamma_{i,t}\\!\in\\!\mathbb{R}^{k_{i+1}}$ and the causes
$\kappa_{i,t}\\!\in\\!\mathbb{R}^{d_{i}}$. That is, for the filter dictionary
matrix, the following top-down
update is performed

$\kappa_{i-1,t}^{\prime}\\!=\\!D_{i}^{\top}\gamma_{i,t}^{\prime},\;\;\gamma_{i,t}^{\prime}\\!=\\!\textnormal{arg
min}_{\gamma_{i,t}}\Bigg{(}\\!\lambda_{i}^{\prime}\|\gamma_{i,t+1}\\!-\\!C_{i}\gamma_{i,t}\|_{1}\\!+\\!\alpha_{i}^{\prime}\|\gamma_{i,t}\|_{1}\Bigg{(}\\!1\\!+\\!\textnormal{exp}(-\textnormal{unpool}(G_{i}\kappa_{i,t}))\\!\Bigg{)}\\!\Bigg{)},$

except for the last stage, wherein
$\kappa^{\prime}_{i,t+1}\\!=\\!\kappa_{i,t}$. This minimization problem has an
algebraic expression for the
global solution:
$[\gamma_{i,t}^{\prime}]_{k}\\!=\\![C_{i}\gamma_{i,t-1}]_{k}$, whenever
$\alpha_{i}^{\prime}\lambda_{i,t,k}\\!<\\!\alpha_{i}$, and zero otherwise.

These top-down predictions serve an important role during inference, as they
transfer abstract knowledge from higher stages into lower ones. The overall
representation quality is thereby improved. The predictions also modulate the
representations due to state zeroing by the sparsity hyperparameter.

Alongside the state and cause inference is a learning process for fitting the
ADPCN parameters to the stimuli. Here, we consider gradient-descent training
without top-down information, which is performed once inference has stabilized
for a given mini batch. An overview of this procedure is presented in the
online appendix (see appendix A).

The inference procedure that we outline in the online appendix is different
than the one proposed in [ChalasaniR-conf2013a, PrincipeJC-jour2014a]. Our
lab’s original DPCN relies on proximal gradients with an extra-gradient rule
that is an almost-linear combination of previous state and cause iterates. The
ADPCNs leverage potentially non-linear iterate combinations. This has the
effect of taking larger steps along the error surface without diverging. In
essence, the DPCN inference process is overly conservative in its updates. It
also has issues that we outline in the online appendix (see Appendix A).

Another change is that multiple iterations of top-down feed-back are executed
in the ADPCNs. As the recurrent processes unfold in time, the APDCN is used
over and over to apply an increasing number of non-linear transformations to
the stimuli. This has the effect of simulating the propagation of the stimuli
through an increasingly deeper, feed-forward network but without the overhead
of adding and learning more network parameters [ChenY-coll2017a]. This
promotes the formation of more expressive states and causes that quickly
converge as the recurrent processes proceeds over time. It suggests that the
ADPCNs have a stable, self-organizing mechanism that minimizes surprise well
[FristonK-jour2010a]. Our lab’s DPCNs [ChalasaniR-conf2013a, PrincipeJC-
jour2014a] only consider a single feed-back iteration. A great many
hierarchical stages are needed to replicate the above behavior. However, a
lack of reasonable convergence prevents this from occurring. They hence do not
learn to preserve perceptual differences.

## 4\. Simulation Results

We now assess the capability of our inference strategy for unsupervised
ADPCNs. We focus on static visual stimuli (see section 3.1). We demonstrate
that ADPCNs uncover meaningful feature representations. They do so more
quickly than convolutional DPCNs that rely on a non-accelerated, proximal-
gradient update (see section 3.2). We show that the improved inference offered
by ADPCNs permits them to exceed the performance of deep unsupervised networks
and behave similarly to deep supervised networks.

## 4.1. Simulation Preliminaries

Data and Pre-processing. We rely on five datasets for our simulations. Two of
these, MNIST and FMNIST, contain single-channel, static visual stimuli. The
remaining three, CIFAR-10, CIFAR-100 and STL-10, contain multi-channel, static
visual stimuli. We whiten each dataset and zero their means. We use the
default training and test set definitions for each dataset.

Training and Inference Protocols. For learning the DPCN and ADPCN parameters,
we rely on ADAM-based gradient descent with mini batches [KingmaDP-conf2015a].
We set the initial learning rate to $\eta_{0}\\!=\\!\textnormal{0.001}$, which
helps prevent over-
shooting the global optimum. The learning rate is decreased by half every
epoch. We use exponential decay rates of 0.9 and 0.99 for the first- and
second-order gradient moments in ADAM, respectively, which are employed to
perform bias correction and adjust the per-parameter learning rates. An
epsilon additive factor of $\textnormal{10}^{-\textnormal{8}}$ is used to
preempt division by zero. We use an initial forgetting factor value of
$\theta_{0}\\!=\\!\textnormal{0.7}$. This factor is increased by a tenth every
thousand mini batches to stabilize convergence. We consider a mini-batch size
of 32 randomly selected samples to ensure good solution quality [HardtM-
conf2016a].

For DPCN and ADPCN inference, we primarily set the sparsity parameters to
$\lambda_{1},\lambda_{1}^{\prime}\\!=\\!\textnormal{0.2}$,
$\lambda_{2},\lambda_{2}^{\prime}\\!=\\!\textnormal{0.25}$, and
$\lambda_{3},\lambda_{3}^{\prime}\\!=\\!\textnormal{0.35}$. Such values permit
retaining much of the visual content in the first two stages while compressing
it more pronouncedly in the third. Some stimuli datasets have slightly altered
parameter values. Due to the static nature of the stimuli, we do not have
temporal state feed-back. We do, however, propagate the cause-state difference
between stages. This is a slight modification of the network diagram shown in
the previous section. We set the feed-back strengths, for most simulations, to
$\alpha_{1},\alpha_{2}\\!=\\!\textnormal{1}$ and
$\alpha_{3}\\!=\\!\textnormal{3}$. In fig. 1, these variables correspond to
the strength of the temporal, intra-layer feed-back, but here they are used
for non-temporal, inter-layer state feed-back. The stronger feed-back amount
in the third stage aids in suppressing noise without adversely impacting the
in earlier stages’ priors. We fix the causal sparsity constants to
$\alpha_{1}^{\prime},\alpha_{2}^{\prime},\alpha_{3}^{\prime}\\!=\\!\textnormal{1}$.
We terminate the accelerated and regular inference processes after 500 and
1000 iterations, respectively, per mini batch. A significantly lower number of
iterations is used in the former case, since the new inertial sequence
facilitates quick convergence.

Figure 2: A comparison of accelerated proximal gradient inference and learning
(left, blue) and proximal gradient inference and learning (right, red) the
MNIST dataset. The presented results are shown after training with mini
batches for two epochs. (a) Polar scatter plots of the orientation angles
versus spatial frequency for the first-stage causes. (b) Line plots of the
normalized center positions with included orientations for the first-stage
causes. For both (a) and (b), we fit Gabor filters to the first-stage causes;
locally optimal filter parameters were selected via a gradient-descent scheme.
The plots are color-coded according to the connection strength between the
invariant matrix and the observation matrix in the first network stage. Higher
connection strengths indicate subsets of dictionary elements from the
observation matrix that are most likely active when a column of the invariance
matrix is also active. If a DPCN has been trained well, then the filters
should have a small orientation-angle spread. Each plot represents a randomly
chosen column of the first-stage invariance matrix. (c)–(e) Back-projected
causes from the first, second, and third stages of the networks, respectively.
Each plot represents a randomly chosen cause. The back-projected causes can be
interpreted as receptive fields, with darker colors indicating a higher degree
of activation. For each stage, we assess the filter similarity and provide VAT
similarity plots. In these plots, low similarities are denoted using gray
while higher similarities are denoted using progressively more vivid shades of
either blue (accelerated proximal gradients) or red (proximal gradients). If a
DPCN has been trained well, then there should be few to no duplicate filters.
There, hence, should not be any conspicuous blocky structures along the main
diagonal of the VAT similarity plots. (f)–(g) Reconstructed instances from a
random batch at the first and third stage, respectively. For each stage, we
also assess the feature similarity between the original training samples and
the reconstructed versions and provide corresponding scatter plots. If a DPCN
reconstructs the input samples well, then there should be a strong linear
relationship between the features. Higher distributional spreads and shifts
away from the main diagonal indicate larger reconstruction errors. Figure 3: A
comparison of accelerated proximal gradient inference and learning (left,
blue) and proximal gradient inference and learning (right, red) the FMNIST
dataset. The presented results are shown after training with mini batches for
two epochs. See fig. 2 for descriptions of the plots.

## 4.2. Simulation Results and Discussions

Network Architecture. As we note in the previous section, our lab’s DPCNs are
non-convolutional. For our simulations, we consider the same Toeplitz-based
convolution as the ADPCNs. This is done to highlight that the improvement in
feature quality occurs due to the faster inference strategy.

We consider the same architecture for the convolutional DPCNs and ADPCNs. At
the first stage, we use 128 states with
$\textnormal{5}\\!\times\\!\textnormal{5}$ filters and 256 causes with
$\textnormal{5}\\!\times\\!\textnormal{5}$ filters. This yields an over-
complete reconstruction basis. At the second and third stages, we use 128
states and 256 states with $\textnormal{5}\\!\times\\!\textnormal{5}$ and
$\textnormal{5}\\!\times\\!\textnormal{5}$ filters, respectively. For these
two stages, we use 512 causes and 1024 causes with
$\textnormal{5}\\!\times\\!\textnormal{5}$ and
$\textnormal{5}\\!\times\\!\textnormal{5}$ filters, respectively. We perform
$\textnormal{2}\\!\times\\!\textnormal{2}$ max pooling between the states and
the causes at each stage.

Due to the choice of filter sizes, the ADPCNs will typically have a worse
reconstruction error but better recognition rate in the later stages. Using
larger filters in the early stages and smaller ones in the later stages
permits implementing traditional predictive-coding behaviors. That is, the
reconstruction error decreases deeper in the hierarchy, as parts of the
stimuli are explained away in an iterative manner.

Simulation Results. Simulation findings are presented in fig. 2 and fig. 3 for
the single-channel MNIST and FMNIST datasets, respectively. Findings for the
multi-channel CIFAR-10/100 and STL-10 datasets are, respectively, shown in
fig. 4 and fig. 5. The results in these figures were for after two epochs.

For these datasets, the ADPCNs are successful in quickly uncovering invariant
representations. Most of the columns in the invariance matrix group dictionary
elements that have very similar orientation and frequency while being
insensitive to translation (see fig. 2(a) to fig. 5(a)). Likewise, for each
active invariance-matrix column, a subset of the dictionary elements are
grouped by orientation and spatial position, which indicates invariance to
other properties like spatial frequency and center position (see fig. 2(b) to
fig. 5(b)). The convolutional DPCNs, in comparison, have representations that
are significantly altered by transformations other than translation. This
occurs because subsets of the dictionary elements are not grouped according to
various characteristics. Discrimination performance hence can suffer for
stimuli samples that are slightly altered.

Figure 4: A comparison of accelerated proximal gradient inference and learning
(left, blue) and proximal gradient inference and learning (right, red) the
CIFAR-10/100 datasets. The presented results are shown after training with
mini batches for two epochs. See fig. 2 for descriptions of the plots.

As well, the ADPCNs learn meaningful filters from the stimuli. The first two
stages of our ADPCNs have causal receptive fields that mimic the behavior of
simple and complex cells in the primate vision system (see fig. 2(c)–(d) to
fig. 5(c)–(d)). The fields for the first stage are predominantly divided into
two types: low-frequency and high-frequency, localized band-pass filters. The
former mainly encode regions of uniform intensity and color along with slowly
varying texture. The latter describe contours and hence sharp boundaries. Such
filters permit accurately reconstructing the input stimuli (see fig. 2(f)–fig.
5(f) and fig. B.1(a)–(e)). The second-stage receptive fields are non-linear
combinations of those in the first that are activated by more complicated
visual patterns, such as curves and junctions. A similar division of receptive
fields into two categories is often encountered in the second ADPCN stage.
More filters are activated by contours, however, than in the first stage. For
both stages, the filters are mostly unique, which is captured in the ordered
similarity plots (see fig. 2(c)–(d) to fig. 5(c)–(d)). Beyond two stages, the
ADPCN receptive fields encompass entire objects (see fig. 2(e) to fig. 5(e)).
They are, however, average representations, not highly specific ones, due to
the limited number of causes (see fig. 2(g) to fig. 5(g)). The backgrounds in
the visual stimuli are often suppressed at the third stage for CIFAR-10/100
and STL-10, which greatly enhance recognition performance (see fig.
B.1(c)–(e)). There are no backgrounds for MNIST and FMNIST, so recognition is
predominantly driven by the whole-object receptive fields in the third stage
see fig. B.1(a)–(b)). The ordered similarity plots indicate that none of the
third-stage filters appear to be duplicated for either dataset. This trend
also holds for the first- and second-stage receptive fields. This implies that
the ADPCNs emphasize the extraction of non-redundant features to form a
complete visual stimuli basis at each stage.

The filters learned by ADPCNs are not only sensitive to whole objects. They
also are attuned to stylistic changes of objects. As shown in fig. C.1, the
filter-derived cause features tend to segregate instances of objects that
visually differ. This occurs even within a given object class.

Convolutional DPCNs, in contrast, do not stabilize to viable receptive fields
at the same rate as the ADPCNs (see fig. 2(c)–(d) to fig. 5(c)–(d)). For
MNIST, the first-stage DPCN receptive fields have some localized band-pass
structure that is similar to Gabor filters. The overall spread of the fields
makes it difficult to accurately detect abrupt transitions and hence recreate
the input stimuli, though. The reconstructions thus are heavily distorted and
blurred (see fig. 2(f) and fig. B.1(a)). For FMNIST, the first-stage receptive
fields focus on low-frequency details, such as either constant grayscale
values or slow-changing grayscale gradients. They also focus onr higher-
frequency details, such as periodic texture. While some of the causes become
specialized band-pass-like filters, there are not enough to adequately
preserve sharp edges. The stimuli reconstructions are thus also distorted,
which removes much of the high-frequency content (see fig. 3(f) and fig.
B.1(b)). Similar results are encountered for CIFAR-10/100 and STL-10 (see fig.
4(f)–fig. 5(f) and fig. B.1(c)–(e)). For all of the datasets, the second-stage
receptive fields become even less organized than in the first stage. They are
mostly activated by blob-like visual patterns, which do not preserve enough
visual content for recreating a close resemblance of the input stimuli beyond
the first stage. The convolutional DPCNs are unable to learn relevant
representations in the third stage, as a consequence. The receptive fields for
this network stage are unique, by virtue of being essentially random. They
are, however, largely useless in extracting stimuli-specific details (see fig.
2(e) to fig. 5(e)). This further degrades the reconstruction quality to where
the inputs are unrecognizable (see fig. 2(g) to fig. 5(g)). Discrimination is
adversely impacted due to this severe lack of identifying characteristics (see
fig. B.1(a)–(e)). The filter redundancy also impacts learning good model
priors. There is typically not enough unique information to be back-propagated
to earlier stages to inform the choice of better receptive fields.

Figure 5: A comparison of accelerated proximal gradient inference and learning
(left, blue) and proximal gradient inference and learning (right, red) the
STL-10 dataset. The presented results are shown after training with mini
batches for two epochs. See fig. 2 for descriptions of the plots.

The causes formed by the ADPCNs and DPCNs specify invariant features that can
be employed for discrimination. In fig. B.2, we show that the stage-aggregated
ADPCN features yield high-performing unsupervised classifiers. They achieve
state-of-the-art unsupervised recognition rates for each dataset. These
recognition rates also are on par with deep networks trained in a supervised
fashion, despite having orders of magnitude fewer parameters. Although the
causal features from all stages have a positive net contribution, those from
the third stage contribute the most to recognition performance (see fig.
B.1(a)–(e)). The DPCNs exhibit poor performance, in comparison. Only the
first-stage features aid classification (see fig. B.1(a)–(e)). The remainder
largely worsen the recognition capabilities. For both the DPCNs and ADPCNs, we
rely on a seven-nearest neighbor classifier with an unsupervised-learned
metric distance [SenerO-coll2016a] to label the stimuli samples. As we
illustrate in fig. C.1, the causal features require non-linear decision
boundaries to distinguish between classes well. This occurs even in high-
dimensional spaces, as class overlap occurs. Such a property motivates the use
of nearest-neighbor classifiers.

Simulation Discussions. Our simulations indicate that ADPCNs were more
effective at uncovering highly discriminative feature representations of
visual stimuli than the original DPCN inference strategy. A trait that
contributes greatly to the ADPCNs’ success is its significantly improved
search rate.

As noted in the appendix, proximal-gradient-type schemes can undergo four
separate search phases, some of which have different local convergence rates.
In one of the phases, the constant-step regime, both the states and causes
undergo rapid improvements. However, in two phases, the local convergence rate
is slow whenever the largest eigenvalue of a certain recurrence matrix is less
than the current inertial-sequence magnitude. For linear inertial sequences,
like those found in the proximal-gradient-based DPCNs, this condition occurs
early during the optimization process. That is, for such sequences, the growth
is initially very rapid and follows a logarithmic rate. Within just a few
iterations, the sequence magnitude exceeds the eigenvalue, which preempts the
fast constant-step regime. The rate of convergence becomes worse than
sublinear. A large number of search steps is thus needed to move toward the
global solution. However, the search frequently terminates before this happens
due to reaching the maximum number of proximal-gradient iterations. The
search, alternatively, stops early due to a lack of progress across
consecutive iterations. In either case, the states and causes do not
adequately stabilize for a given mini batch. The poor state and cause
representations, naturally, are integrated into the filter dictionary matrices
and invariant matrices during the learning updates. This disrupts the priors
in the early hierarchy for future stimuli. The convergence is further stymied
by cost rippling. Proximal-gradient-based optimization does not behave like a
pure descent method in two out of the four phases. Such behavior is caused by
the eigenvalues of another recurrence matrix being a pair of complex
conjugates, which necessitates oscillating between the two. All of these
factors make it difficult to propagate meaningful bottom-up information
[MechelliA-jour2004a] beyond the first stage. The top-down details from higher
stages are hence ineffective at modifying the priors to disambiguate the
stimuli [BarM-jour2004a].

The ADPCNs largely avoid these issues. After the constant-step regime, the
search switches to one of two potentially slower phases. However, the APDCNs’
inertial-sequence growth rate is rather muted, as opposed to that of the
DPCNs. The chance of exceeding the largest eigenvalue of the augmented,
auxiliary-variable recurrence matrix is low for the ADPCNs. The searches thus
can proceed unhindered toward the global solution. Moreover, since the
eigenvalue-magnitude threshold is often not reached, the largest eigenvalue of
the augmented, mapping recurrence matrix is real-valued, not complex. This
means that the accelerated proximal gradients behave like a descent method. It
thus will not experience localized cost rippling due to alternating between
conjugate pairs. Both properties promote rapid stabilization of the states and
causes, which expedite the formation of beneficial priors throughout much of
the early-stage network inference. These priors facilitate the construction of
transformation-insensitive feature abstractions in deeper network stages, due
to the bottom-up forwarding of stimuli-relevant signals. The recurrent, top-
down connections, in turn, suitably alter the representation sparsity.
Extraneous details that do not contribute greatly to the reconstruction
quality are hence ignored. This behavior biases in favor of valuable stimuli,
which is analogous to observed functionality in the frontal and parietal
cortices [SerencesJT-jour2008a]. The descending pathways also carry predictive
responses, in the form of templates of expected stimuli, that are matched to
the current and future mini batches to aid recognition [UllmanS-jour1995a].
That is, the templates convey contextual information for extracting task-
specific information, which makes recognition more reliable [PotterMC-
jour1975a, PalmerSE-jour1975a].

There are other traits that contribute to the success of the ADPCNs. For
instance, the ADPCN’s first-stage receptive fields are largely similar to that
of simple cells in the primary visual cortex. Simple cells often implement
Gabor-like filters with generic preferred stimuli that correspond to oriented
edges [HubelDH-jour1965a, HubelDH-jour1968a]. Such filters are useful within
the ADCPN. Relations between activations for specific spatial locations tend
to be distinctive between objects in visual stimuli. Activations are also
obtained, in a Gabor space, that facilitate the construction of naturally
sparse representations. These representations can then be hierarchically
extended, which is what we ultimately sought in the ADPCNs. Changes in object
location, scale, and orientation can be reliably detected, within this Gabor
space, thereby aiding in the creation of transformation-invariant features.
These features permit near-perfect stimuli reconstructions at the first stage.
The uniqueness of the band-pass filters is beneficial, as it permits the
ADPCNs to fixate on non-redundant stimuli characteristics. How these filters
arise and the rate at which they form are also important aspects that aid in
the ADPCNs’ success. They emerge due to feed-back from high-level visual
network areas, which quickly reduce activity in lower areas to simplify the
description of the stimuli to some of its most basic elements [MurraySO-
jour2004a]. In doing so, alternate explanations are suppressed, and only the
most dominant, fundamental causes of the stimuli remain [SpratlingMW-
jour2011a]. These causes are oriented luminance contours. This rapid
stabilization of filters is exactly functionality that we expect to encounter
in an efficient predictive coding process. It is hence well aligned with
contemporary neurophysiological theory [OlshausenBA-jour1997a].

The plots of center position and orientation angle versus center frequency for
the ADPCNs indicate that the learned Gabor filters form a meaningful
reconstruction basis for the visual stimuli. The entire center-position plane
is thoroughly filled. There hence are filter impulse responses everywhere in
space when a sufficient number of first-stage filters are learned. Likewise,
the Gabor orientation range is well covered, implying that the filters can
recognize edges at different angles. Taken together, both properties indicate
that these first-stage filters can reconstruct the stimuli well. Given the
similarities of the Gabor filters across the different stimuli datasets, it
would appear that the inferred basis can recreate any natural-image stimuli
well. The low reconstruction errors for the first stage of the APDCN
corroborate this claim. For the DPCNs, we also have that the center-position
plane is well covered. However, the filters have poor spatial frequency
bandwidths, so they are not activated much by contours. Only the most dominant
edges in the visual stimuli will be well preserved. These usually are the
object-background boundaries. Inter-object details are not retained. While the
first-stage DPCN filters also form a basis, it is a poor one for
reconstructing natural-image stimuli. Without a meaningful, stable basis, the
remainder of the network cannot build on it to reliably describe aspects of
the stimuli. The slow convergence of proximal gradients prevents this, as we
note above.

Beyond the first stage, the ADPCNs exhibit an increase in specificity,
abstraction, and invariance for deeper hierarchies [RiesenhuberM-jour1999a].
This behavior aligns well with the current understanding of the vision system
[TjanBS-jour2005a]. It also aids in the ADPCNs’ success. The second-stage
receptive fields, in the case of MNIST, become sensitive to curved sub-strokes
for the hand-written digits, which is similar to prestriate cortex
functionality [HedgeJ-jour2000a]. For FMNIST, they emphasize abrupt
transitions found in regions of the apparel and fashion accessories. This
mimics aspects of shape-pattern-selectivity behaviors found in the
extrastriate cortices [PasupathyA-jour1999a, PasupathyA-jour2002a]. For
STL-10, the receptive fields are often elongated Gabor-like filters, which can
be found in the prestriate cortex [LiuL-jour2016b]. All of these features
systematically focus on object-relevant visual details, thereby aiding
recognition. At the deepest stage, the receptive fields are entirely object
specific, which is functionality somewhat akin to the neurons in the primate
infero-temporal cortex [BruceC-jour1981a]. It is also related to memory
activity [MiyashitaY-jour1988a, YakovlevV-jour1998a]. The representations are
additionally translation and rotation insensitive, similar to inferotemporal
cortex neurons [RollsET-jour1992a, ToveeMJ-jour1994a, SalinasE-jour1997a], and
change little with respect to scale and spatial-frequency changes, similar to
neurons in the middle temporal area [RollsET-jour1985a, LiuL-jour2007a]. To
our knowledge, such invariant, whole-object sensitivity within a single stage
has not been witnessed in any existing predictive-coding model. Based on
contemporary theories [LiangH-jour2017a], we believe that the receptive-field
feed-back from the final stage contribute to the effective connectivity in the
earlier network stages [RamalingamN-jour2013a]. That is, the role of this
final stage is to disambiguate local image components. This is done by
creating a template that is fed back, which then selectively enhances object
components and suppresses interfering background components [EpshteinB-
jour2008a]. This biologically plausible behavior is crucial for achieving high
discrimination rates on CIFAR-10/100 and STL-10. For these datasets, the
objects of interest are scattered amongst distractors.

As we show in our simulation results, the third stage of the ADPCN contributes
more to recognition than the first two stages. Such a finding is well-aligned
with previous studies. Although simple objects can be discriminated based on
Gabor-like filters, complex objects require significant non-linearities
[ShiJV-jour2013a]. The later stages provide this functionality due to the
conversion from states to pooled, sparse causes. The processes of pooling and
sparsifying are highly non-linear. They additionally lead to the emergence of
complex-cell properties along with hence shift invariance [HubelDH-jour1962a]
and spatial phase invariance [LianY-jour2021a].

Including Toeplitz-based convolution with spatial pooling has a major impact
on performance. Spatial coherence behaviors that convolutional layers offer
are essential for describing inter-object relationships in complex visual
stimuli. Pooling introduces invariance. Our promising recognition results in
Appendix B are a testament to this. The corresponding cause embeddings are
too. They indicate that the ADPCNs self-organize the states and causes in an
object-sensitive way, despite the lack of supervision. DPCNs struggle to do
this, since they rely on non-convolutional filters [ChalasaniR-conf2013a,
PrincipeJC-jour2014a]. Their cause embeddings often group the stimuli in a
worse way than embeddings of the input stimuli. That is, their transformation
of the stimuli often destroys much of the visual content. Even the
convolutional extension to DPCNs struggle due to a lack of a good
reconstruction basis. This shows that convolution alone is not sufficient to
uncover good features. The networks must be paired with an efficient inference
process. Inference for the convolutional and non-convolutional DPCNs is based
on a slow, proximal-gradient-based approach. The later-stage cause embeddings
for these networks are thus quite poor, since the first- and second-stage
bases do not stabilize quickly to meaningful filters. It is likely that DPCNs
would benefit from a greedy, stage-wise training to initialize the networks in
a meaningful way. This may overcome the poor convergence, to some extent. Our
ADPCNs would likely benefit from it too. As well, the ADPCNs would probably
benefit from fixing the first-stage states and causes. As we have shown in our
simulations, these features do not change much across color-image datasets.
Effort could be better spent on learning more advanced features in the later
network stages.

Another benefit of including convolutional filters in the ADPCNs is that they
help encode perceptual stimuli similarity and differences. By this, we mean
that well-trained ADPCNs group related stimuli together and force unrelated
stimuli apart in the causal feature space. Such behavior is stems from
learning visual, appearance-based features at local and global object scales.
It also stems from iteratively sparsifying those features to selectively
remove redundant details. Inter-layer and intra-layer feed-back contribute
too. Other network architectures, like convolutional autoencoders, should also
be capable of accounting for perceptual differences. They, however, appear to
currently lack both appropriate losses and regularizers, along with
fundamental layer behaviors, to do this as effectively as ADPCNs.

## 5\. Conclusions

Here, we have revisited the problem of unsupervised predictive coding. We have
considered a hierarchical, generative network, the ADPCN, for reconstructing
observed stimuli. This network is composed of temporal sparse-coding models
with bi-directional connectivity. The interaction of the information passed by
top-down and bottom-up connections across the models permit the extraction of
invariant, increasingly abstract feature representations. Such representations
preserve perceptual differences.

Our contribution in this paper is a new means of inferring the underlying
components of the feature representations, which are the sparse states and
causes. Previously, a proximal-gradient-type approach has been used for this
purpose. Despite its promising theoretical guarantees, though, it exhibits
poor empirical performance. This practically limits the number of model stages
that can be considered in DPCNs. It also extensively curtails the quality of
the stimuli features that can be extracted. Here, we have considered a
parallelizable, vastly accelerated proximal-gradient strategy that overcomes
these issues. It allows us to go beyond the existing two-stage limitation,
facilitating the construction of arbitrary-staged DPCNs. Each stage leads to
increasingly enhanced performance for object analysis. The information from
higher stages is propagated to earlier ones to form more effective stimuli
priors for bottom-up processing. Most crucially, our optimization strategy
immensely streamlined inference. Often, only one or two presentations of the
stimuli are necessary to reach a stable filter dictionary and hence a
corresponding set of sparse states and sparse causes. Good object analysis
performance is hence observed. The previous optimization approach requires
many times more presentations before a stable set of filters is uncovered. The
resulting features are not nearly as discriminative as those from our proposed
strategy. We have mathematically proved that this stems from poor convergence-
rate properties of the original inertial sequence used in DPCNs.

We have applied ADPCNs to static-image datasets. For MNIST and FMNIST, the
ADPCNs learn initial-stage receptive fields that mimic aspects of the early
stages of the primate vision system. The later network stages implement
receptive fields that encompass entire objects. In the case of MNIST, the
back-projected filters become pseudo averages of the hand-written numerical
digits. Predominant writing styles are modeled well. For FMNIST, the back-
projected filters are the various types of clothing and personal articles.
General styles and some nuances are captured. To our knowledge, this is the
first time that such object-scale receptive fields have been learned for
predictive coding. This behavior helps yield unsupervised classifiers that
achieve state-of-the-art performance. Such classifiers also outperform
supervised-trained deep networks, which lends credence to the complicated
feature inference and invariance process that we employ. It also supports the
notion that the ADPCNs preserve perceptual differences. Similar results are
witnessed for natural-image datasets, such as CIFAR-10/100. The later-stage
receptive fields again encompass entire object categories. This yields
promising features that achieve generalization rates almost equivalent to that
of supervised-trained deep networks. This is despite our use of simple
nearest-neighbor classifiers. It is also despite the fact that our ADPCNs have
many times fewer convolutional filters than these other deep networks.

ADPCNs are readily applicable to spatio-temporal stimuli processing, much like
the original DPCNs. This is because the ADPCNs implement a recurrent state-
space model. For such modalities, like video, the ADPCN recognition
performance may be even better than for static stimuli, like images. This is
because top-down, feed-back connections impose temporal constraints on the
learning process. We will investigate this in our future work from the context
of solving time-varying problems. We will also demonstrate their superiority
compared to purely feed-forward convolutional-recurrent autoencoders. We will
show that the lack of a top-down pathway impedes learning meaningful
representations.

ADPCNs can also form the backbone of a general, unsupervised framework for
stimuli learning and high-level understanding. In our future work, we will
illustrate that architectural extensions of it are well suited for making
extrapolations about environment dynamics. This has implications for many
applications, including self-driving cars. In particular, we will show that
these modified ADPCNs learn temporal and perceptual cues that permit
predicting egocentric and allocentric events in the short-term future. For the
egocentric events, the ADPCNs understand well that a moving camera will cause
non-linear transformations of visual characteristics across video frames. The
ADPCNs thus can thus reliably predict, from a short history of video frames,
the appearance of non-mobile objects and their locations in subsequent frames.
This will be useful for estimating vehicle position and angle relative to
objects of interest, which can help refine steering control inputs for close-
quarters maneuvers. For the allocentric events, the ADPCNs understand well the
dynamics of mobile objects for either a fixed or moving camera. The ADPCNs can
hence similarly predict the appearance and location of those objects. This
will prove invaluable for gauging how pedestrians may react and hence avoid
collisions. We will show that both types of event predictions emerge due to
the ADPCNs learning at multiple time scales across different stages. Multi-
time-scale prediction is something that existing recurrent models struggle to
do well.

## References

## Appendix A

Below, we outline the ADPCN training and inference process.

1 Inputs: Initial dictionary matrix
$D_{i}^{\top}\\!\in\\!\mathbb{R}^{k_{i}\times k_{i-1}}_{+}$, state-transition
matrix $C_{i}\\!\in\\!\mathbb{R}^{k_{i}\times k_{i}}$, and invariant matrix
$G_{i}\\!\in\\!\mathbb{R}^{d_{i}\times k_{i}}$ for each network layer. A set
of time-varying, static stimuli $Y_{t}$, where $y_{t}\\!\in\\!Y_{t}$,
$y_{t}\\!\in\\!\mathbb{R}^{p}$. A set of initial states
$\gamma_{i,0}\\!\in\\!\mathbb{R}^{k_{i}}$ and causes
$\kappa_{i,0}\\!\in\\!\mathbb{R}^{d_{i}}$.

2

3 for  _$t\\!=\\!0,1,2,\ldots$_ do

4 Initialize the bottom-up cause for the first layer as
$\kappa_{0,t}\\!=\\!y_{t}$.

5 for  _$i\\!=\\!0,1,2,\ldots$_ do

6 For all layers but the last, the most likely top-down causes,
$\kappa^{\prime}_{i-1,t}\\!\in\\!\mathbb{R}^{d_{i-1}}$, are initialized at
each iteration using the next stage’s states
$\gamma_{i,t}\\!\in\\!\mathbb{R}^{k_{i+1}}$ and the causes
$\kappa_{i,t}\\!\in\\!\mathbb{R}^{d_{i+1}}$,
$\kappa_{i-1,t}^{\prime}\\!=\\!D_{i}^{\top}\gamma_{i,t}^{\prime},\;\;\gamma_{i,t}^{\prime}\\!=\\!\textnormal{arg
min}_{\gamma_{i,t}}\Bigg{(}\\!\lambda_{i}^{\prime}\|\gamma_{i,t+1}\\!-\\!C_{i}\gamma_{i,t}\|_{1}\\!+\\!\alpha_{i}^{\prime}\|\gamma_{i,t}\|_{1}\Bigg{(}\\!1\\!+\\!\textnormal{exp}(-\textnormal{\sc
unpool}(G_{i}\kappa_{i,t}))\\!\Bigg{)}\\!\Bigg{)}.\vspace{-0.15cm}$ This
minimization problem has an algebraic expression for the global solution:
$[\gamma_{i,t}^{\prime}]_{k}\\!=\\![C_{i,t}\gamma_{i,t-1}]_{k}$, whenever
$\alpha_{i}^{\prime}\lambda_{i,t,k}\\!<\\!\alpha_{i}$, and zero otherwise. For
the last layer, $\kappa^{\prime}_{i,t+1}\\!=\\!\kappa_{i,t}$.

7 for  _$i\\!=\\!0,1,2,\ldots$_ do

8 Let $\beta_{m}\\!\in\\!\mathbb{R}_{+}$ be an inertial sequence,
$\beta_{m}\\!=\\!(k_{m}\\!-\\!1)/k_{m+1}$, where
$k_{m}\\!=\\!1\\!+\\!(m^{r}\\!-\\!1)/d\,$ with $r\\!\in\\!\mathbb{R}_{1,+}$
and $d\\!\in\\!\mathbb{R}_{+}$. Given an adjustable step size
$\tau_{i,t}^{m}\\!\in\\!\mathbb{R}_{+}$, update the states using proximal-
gradient steps, indexed by $m$, until either convergence or a pre-set number
of iterations has been reached  $\gamma_{i,t+1}^{m}\\!=\\!\textnormal{\sc
prox}_{\\!\lambda_{i,t}}\\!\Bigg{(}\\!\pi_{i,t}^{m}\\!-\\!\lambda_{i,t}\tau^{m}_{i,t}(D_{i}^{\top}(\kappa_{i-1,t}\\!-\\!D_{i}\pi^{m}_{i,t})\\!+\\!\alpha_{i}\Omega_{i}(\pi^{m}_{i,t}))\\!\Bigg{)},\vspace{-0.2cm}$
where
$\pi_{i,t}^{m+1}\\!=\\!\gamma^{m}_{i,t+1}\\!+\\!\beta^{m}(\gamma^{m}_{i,t+1}\\!-\\!\gamma_{i,t+1}^{m-1})$.
The term $\Omega_{i}(\pi_{i,t}^{m})$ quantifies the contribution of the non-
smooth state transition. Use Nesterov smoothing, with
$\mu_{i}\\!\in\\!\mathbb{R}_{+}$, to approximate them,
$\Omega_{i}(\pi_{i,t})\\!=\\!\textnormal{arg
max}_{\|\Omega_{i,t}\|_{\infty}\leq
1}\Omega_{i,t}^{\top}(\pi_{i,t}^{m}\\!-\\!C_{i}\gamma_{i,t-1})\\!-\\!\mu_{i}\|\Omega_{i,t}\|^{2}_{2}/2$.
Max-pool the states using non-overlapping windows
$\gamma_{i,t+1}\\!=\\!\textnormal{\sc pool}(\gamma_{i,t+1})$.

9

10 Let $\beta^{\prime}_{m}\\!\in\\!\mathbb{R}_{+}$ be an inertial sequence,
$\beta^{\prime}_{m}\\!=\\!(k_{m}\\!-\\!1)/k_{m+1}$, where
$k_{m}\\!=\\!1\\!+\\!(m^{r}\\!-\\!1)/d\,$ with $r\\!\in\\!\mathbb{R}_{1,+}$,
$d\\!\in\\!\mathbb{R}_{+}$. Given an adjustable step size
$\tau^{\prime}_{i,t}{}^{\\!m}\\!\in\\!\mathbb{R}_{+}$, update the causes using
proximal-gradient steps until either convergence or a pre-set number of
iterations has been reached  $\kappa_{i,t+1}^{m}\\!=\\!\textnormal{\sc
prox}_{\\!\lambda_{i}^{\prime}}\\!\Bigg{(}\\!\pi^{\prime}_{i,t}{}^{\\!\\!\\!\\!m}\\!-\\!\lambda_{i}^{\prime}\tau^{\prime}_{i,t}{}^{\\!m}(2\eta_{i}^{\prime}(\kappa_{i,t+1}^{m}\\!-\\!\kappa^{\prime}_{i,t})\\!-\\!\alpha_{i}^{\prime}G_{i}^{\top}\textnormal{exp}(-G_{i}\pi^{\prime}_{i,t}{}^{\\!\\!\\!\\!m})|\gamma_{i,t+1}^{j}|)\\!\Bigg{)},\vspace{-0.2cm}$
where
$\pi^{\prime}_{i,t}{}^{\\!m+1}\\!=\\!\kappa_{i,t+1}^{m}\\!+\\!\beta^{\prime}_{m}(\kappa_{i,t+1}^{m}\\!-\\!\kappa_{i,t}^{m-1})$.
Update the sparsity parameter using spatial max unpooling after the causes
update has concluded,
$\lambda_{i,t+1}\\!=\\!\alpha_{i}^{\prime}(1\\!+\\!\textnormal{exp}(-\textnormal{\sc
unpool}(G_{i}\kappa_{i,t+1})))$.

11

12

13

14 for  _$i\\!=\\!0,1,2,\ldots$_ do

15 Update the filter dictionary matrix
$D_{i}^{\top}\\!\in\\!\mathbb{R}^{k_{i}\times k_{i-1}}_{+}$ and the state-
transition matrix $C_{i,t}\\!\in\\!\mathbb{R}^{k_{i}\times k_{i}}$
independently, until either convergence or a pre-set number of iterations has
been reached, via dual-estimation filtering, with steps indexed by $m$,
$D_{i}^{m+1}{}^{\top}\\!=\\!D_{i}^{m}{}^{\top}\\!+\\!\sigma_{t}\\!+\\!\psi_{i}^{m}\Bigg{(}\\!(\gamma_{i-1,t+1}\\!-\\!D_{i}^{m}{}^{\top}\gamma_{i,t+1})\gamma_{i,t+1}\\!+\\!\theta_{i}^{m}(D_{i}^{m}\\!-\\!D_{i}^{m-1})\\!\Bigg{)},\vspace{-0.175cm}$
$C_{i}^{m+1}\\!=\\!C_{i}^{m}\\!+\\!\sigma_{t}^{\prime}\\!+\\!\psi_{i}^{\prime}{}^{m}\Bigg{(}\\!\textnormal{\sc
sign}(\gamma_{i,t+1}\\!-\\!C_{i}^{m}\gamma_{i,t})\gamma_{i,t+1}^{\top}\\!+\\!\theta_{i}^{m}(C_{i}^{m}\\!-\\!C_{i}^{m-1})\\!\Bigg{)},\vspace{-0.2cm}$
where $\psi_{i}^{m},\psi_{i}^{\prime}{}^{m}\\!\in\\!\mathbb{R}_{+}$ are step
sizes, $\theta_{i}^{m}\\!\in\\!\mathbb{R}_{+}$ is a momentum coefficient, and
$\sigma_{t},\sigma_{t}^{\prime}\\!\in\\!\mathbb{R}$ is Gaussian transition
noise over the parameters. Normalize $D_{i}^{m+1}{}^{\top}$ to avoid returning
a trivial solution.

16 Update the causal invariance matrix $G_{i}\\!\in\\!\mathbb{R}^{d_{i}\times
k_{i}}$ via dual-estimation filtering, with steps indexed by $m$,
$G_{i}^{m+1}\\!=\\!G_{i}^{m}\\!+\\!\sigma_{t}^{\prime\prime}\\!+\\!\psi_{t}^{\prime\prime}{}^{\vspace{-0.01cm}m}\Bigg{(}\\!(\textnormal{exp}(-G_{i}^{m}\kappa_{i+1,t})|\gamma_{i,t+1}|)\kappa_{i,t+1}^{\top}\\!+\\!\theta_{i}^{m}(G_{i}^{m}\\!-\\!G_{i}^{m-1})\\!\Bigg{)},\vspace{-0.2cm}$
where $\psi_{t}^{\prime\prime}{}^{\vspace{-0.01cm}m}\\!\in\\!\mathbb{R}_{+}$
is a step size, $\theta_{i}^{m}\\!\in\\!\mathbb{R}_{+}$ is a momentum
coefficient, and $\sigma_{t}^{\prime\prime}\\!\in\\!\mathbb{R}$ is Gaussian-
distributed transition noise over the parameters. Normalize $G_{i}^{m+1}$ to
avoid returning a trivial solution.

17

18

Algorithm 1 Accelerated Deep Prediction Network (ADPCN) Training and Inference

The convergence of dual-estimation filtering is straightforward to
demonstrate. For the proximal-gradient inference process, it is much more
involved. We build up to it in what follows. We focus on the case where no
inference restarts are performed. This is done to theoretically show that the
speed-ups we obtain are due solely to the improved convergence rate offered by
the new extra-gradient update. The inclusion of multiple restarts serves to
delay the eventual inference slowdowns toward the end of inference. Restarts
should not improve the maximally achievable convergence rate.

We first prove a weak convergence result that facilitates demonstrating a much
stronger one when relying on properties of Cauchy sequences. We then quantify
the global convergence rate for our chosen inertial sequence. We then compare
the global convergence rate to a Nesterov-style inertial sequence that was
used in the original DPCN to illustrate the advantages of the former for
ADPCNs. Lastly, we outline local convergence properties of both inertial
sequences to explain the results presented for DPCNs and ADPCNs in the main
part of the paper. A high-level overview of both networks is presented in fig.
A.1.

|  DPCN |  |  ADPCN
---|---|---|---
Unsupervised |  Yes |  |  Yes
Small models |  Yes |  |  Yes
Convolutional |  No [ChalasaniR-conf2013a, PrincipeJC-jour2014a] / Yes [ChalasaniR-jour2015a] |  |  Yes
Inference Restarts |  No |  |  Yes
Feed-Forward Inference Conv. Rate |  $O(\zeta_{i}/m^{2})$ |  |  $O(r\zeta_{i}/(r\\!-\\!1)m^{r})$
Feed-Back Inference Converg. Rate |  $O(1)$ |  |  $O(1)$
Feed-Forward Infer. Comput. Complexity |  $O(k_{i}^{2})\\!+\\!O(d_{i}^{2})$ |  |  $O(k_{i}^{2})\\!+\\!O(d_{i}^{2})$
Parameter Learning Converg. Rate |  $O(1/m)$ |  |  $O(1/m)$
Parameter Learning Comput. Complexity |  $O(k_{i}^{2})\\!+\\!O(d_{i}^{2})$ |  |  $O(k_{i}^{2})\\!+\\!O(d_{i}^{2})$
Figure A.1: A quantitative comparison of DPCNs and ADPCNs. The main
distinction is that ADPCNs enjoy a much faster convergence rate for feed-
forward inference. This enables them to better describe stimuli and hence
extract useful details from them. Better feed-forward inference naturally
impacts feed-back parameter updating.

Toward this end, it is important to show that the distance between a given
iterate and the solution set for either inference cost can be bounded by the
norm of the residual. This is a local Lipschitzian error bound. The
Lipschitzian bound is satisfied whenever the norm of the residual is small.
The iterate must also be sufficiently close to the solution set for this bound
to be satisfied.

  * Proposition A.1. Let $\gamma_{i,t}\\!\in\\!\mathbb{R}^{k_{i}}$ be the hidden states and $\kappa_{i,t}\\!\in\\!\mathbb{R}^{d_{i}}$ be the hidden causes. Let $\pi_{i,t}\\!\in\\!\mathbb{R}^{k_{i}}$ be the auxiliary states and let $\pi^{\prime}_{i,t}\\!\in\\!\mathbb{R}^{d_{i}}$ be the auxiliary causes at layer $i$ and time $t$. Let $\omega_{1,i}\\!\in\\!\mathbb{R}$, that is assumed to
satisfy
$\omega_{1,i}\geq\mathcal{L}_{1}(\gamma_{i}^{*},\kappa_{i,t},C_{i},D_{i}^{\top};\alpha_{i},\lambda_{i})$.
As well, let $\omega_{2,i}\\!\in\\!\mathbb{R}$,
$\omega_{2,i}\geq\mathcal{L}_{2}(\gamma_{i,t},\kappa_{i}^{*},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t})$.
For
some $\omega_{1,i}$, there are
$\epsilon_{1,i},\epsilon_{1,i}^{\prime}\\!\in\\!\mathbb{R}_{+}$, such that,
for step size $\tau_{i,t}^{m}\\!\in\\!\mathbb{R}_{+}$

$\textnormal{dist}(\gamma_{i,t+1}^{m},\Gamma_{i}^{*})\leq\epsilon_{1,i}^{\prime}\Bigg{\|}\textnormal{\sc
prox}_{\\!1/\ell_{i,j}}\\!\Bigg{(}\\!\pi_{i,t}^{m}\\!-\\!\lambda_{i,t}\tau_{i,t}^{m}\nabla_{\pi_{i,t}^{m}}\mathcal{L}_{1}(\pi_{i,t}^{m},\kappa_{i,t},C_{i},D_{i}^{\top};\alpha_{i},\lambda_{i})\\!\Bigg{)}-\pi_{i,t}^{m}\Bigg{\|}$

whenever the following conditions, $\|\textnormal{\sc
prox}_{\\!\lambda_{i,t}}(\pi_{i,t}^{m}\\!-\\!\lambda_{i,t}\tau_{i,t}^{m}\nabla_{\pi_{i,t}}\mathcal{L}_{1}(\pi_{i,t}^{m},\kappa_{i,t},C_{i},D_{i}^{\top};\alpha_{i},\lambda_{i,t}))\\!-\\!\gamma_{i,t}^{m}\|<\epsilon_{1,i}$
and
$\omega_{1,i}\leq\mathcal{L}_{1}(\gamma_{i,t}^{m},\kappa_{i,t},C_{i},D_{i}^{\top};\alpha_{i},\lambda_{i})$,
are satisfied. Here, $\textnormal{dist}(\gamma_{i,t+1}^{m},\Gamma_{i}^{*})$
denotes the distance of a given iterate with the solution set. Likewise, for
some $\omega_{2,i}$, there are
$\epsilon_{2,i},\epsilon_{2,i}^{\prime}\\!\in\\!\mathbb{R}_{+}$, such that,
for step sizes $\tau^{\prime}_{i,t}{}^{\\!m}\\!\in\\!\mathbb{R}_{+}$,

$\textnormal{dist}(\kappa_{i,t}^{m},K_{i}^{*})\leq\epsilon_{2,i}^{\prime}\Bigg{\|}\textnormal{\sc
prox}_{\\!1/\ell^{\prime}_{i,j}}\\!\Bigg{(}\\!\pi^{\prime}_{i,t}{}^{\\!m}\\!-\\!\lambda_{i}^{\prime}\tau^{\prime}_{i,t}{}^{\\!m}\nabla_{\pi^{\prime}_{i,t}{}^{\\!m}}\mathcal{L}_{2}(\gamma_{i,t+1},\pi^{\prime}_{i,t}{}^{\\!m},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t})\\!\Bigg{)}-\pi^{\prime}_{i,t}{}^{\\!m}\Bigg{\|}$

whenever the following conditions $\|\textnormal{\sc
prox}_{\\!\lambda_{i}}(\pi^{\prime}_{i,t}{}^{\\!m}\\!-\\!\lambda_{i}^{\prime}\tau^{\prime}_{i,t}{}^{\\!m}\nabla_{\pi^{\prime}_{i,t}{}^{\\!m}}\mathcal{L}_{2}(\gamma_{i,t+1},\pi^{\prime}_{i,t}{}^{\\!m},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t}))\\!-\\!\kappa_{i,t}^{m}\|<\epsilon_{2,i}$
and
$\omega_{2,i}\leq\mathcal{L}_{2}(\gamma_{i,t+1},\pi^{\prime}_{i,t}{}^{\\!m},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t})$
are satisfied. Here, $\Gamma_{i}^{*}$, with
$\gamma_{i}^{*}\\!\in\\!\Gamma_{i}^{*}$,
$\gamma_{i}^{*}\\!\in\\!\mathbb{R}^{k_{i}}$, denotes the sol-
ution set for the state-inference cost function. As well, $K_{i}^{*}$, with
$\kappa_{i}^{*}\\!\in\\!K_{i}^{*}$,
$\kappa_{i}^{*}\\!\in\\!\mathbb{R}^{d_{i}}$, denotes the solution set for
the cause-inference cost function. Both
$\ell_{i,j},\ell_{i,j}^{\prime}\\!\in\\!\mathbb{R}_{+}$ denote Lipschitz
constants of the state and cause costs.

  * Proof: In what follows, for ease of presentation, we ignore the variables of the inference cost that remain fixed across inference iterations. Let the $L_{1}$-sparsity term in the state-inference cost be re-written in an equivalent manner as $\sum_{k^{\prime}=1}^{k_{i}}[\lambda_{i,t}]_{k^{\prime}}\xi_{i,t}$, with the constraint $|[\gamma_{i,t}]_{k^{\prime}}|\\!-\\!\xi_{i,t}\\!\leq\\!0$, $\xi_{i,t}\\!\in\\!\mathbb{R}^{k_{i}}$ [TsengP-jour2009a]. There exists some $\omega_{i}\\!\in\\![0,\infty)^{k_{i}}$ such that

$(\textnormal{\sc
prox}_{\\!1/\ell_{i,j}}(\pi_{i,t}^{m}\\!-\\!\lambda_{i,t}\tau_{i,t}^{m}\nabla_{\pi_{i,t}^{m}}\mathcal{L}_{1}(\pi_{i,t}^{m}))-\gamma_{i,t}^{m})+(\nabla_{\pi_{i,t}^{m}}\mathcal{L}_{1}(\pi_{i,t}^{m})-\omega_{i})=0,$

where $(\textnormal{\sc
prox}_{\\!1/\ell_{i,j}}(\pi_{i,t}^{m}\\!-\\!\lambda_{i,t}\tau_{i,t}^{m}\nabla_{\pi_{i,t}^{m}}\mathcal{L}_{1}(\pi_{i,t}^{m}))\\!=\\!\xi_{i,t}$.
Here, we assume that the choice of $\pi_{i,t}^{m}$ is such that the
inequality conditions are satisfied for
$\epsilon_{1,i},\epsilon_{1,i}^{\prime}\\!\in\\!\mathbb{R}_{+}$. As well,
there exists some optimal $\pi_{i}^{*}\\!\in\\!\Gamma_{i}^{*}$,
$\pi_{i}^{*}\\!\in\\!\mathbb{R}_{+}^{k_{i}}$, and a corresponding
$\omega^{*}_{i}\\!\in\\![0,\infty)^{k_{i}}$ such that
$\nabla_{\pi_{i}^{*}}\mathcal{L}_{1}(\pi_{i}^{*})-\omega^{*}_{i}\\!=\\!0$,
where $\pi_{i}^{*}\\!=\\!\xi_{i,t}$. We also have that, for
$\sigma\\!\in\\!\mathbb{R}_{+}$,
$2\sigma\|\pi_{i,t}^{m}\\!-\\!\pi_{i}^{*}\|^{2}\\!\leq\\!\langle\pi_{i,t}^{m}\\!-\\!\pi_{i}^{*},\,\nabla_{\pi_{i,t}^{m}}\mathcal{L}_{1}(\pi_{i,t}^{m})\\!-\\!\nabla_{\pi_{i}^{*}}\mathcal{L}_{1}(\pi_{i}^{*})\rangle$.
Hence, for some $\omega_{1,i}^{\prime}\\!\in\\!\mathbb{R}$ that depends on
$\omega_{1,i}\\!\in\\!\mathbb{R}$,
we have

$2\sigma\|\pi_{i,t}^{m}\\!-\\!\pi_{i}^{*}\|\leq(\omega_{1,i}^{\prime}\\!+\\!((\omega_{1,i}^{\prime})^{2}\\!+\\!4\omega_{1,i}^{\prime})^{1/2})\|\pi_{i,t}^{m}\\!-\\!\textnormal{\sc
prox}_{\\!1/\ell_{i,j}}(\pi_{i,t}^{m}\\!-\\!\lambda_{i,t}\tau_{i,t}^{m}\nabla_{\pi_{i,t}^{m}}\mathcal{L}_{1}(\pi_{i,t}^{m}))\|/2.$

When combined with
$\|(\pi_{i,t}^{m},\omega_{i,t})\\!-\\!(\pi_{i}^{*},\omega^{*}_{i})\|\\!\leq\\!\delta_{i}(\|\pi_{i,t}^{m}\\!-\\!\pi_{i}^{*}\|\\!+\\!\|\pi_{i,t}^{m}\\!-\\!\textnormal{\sc
prox}_{\\!\lambda_{i,t}}(\pi_{i,t}^{m}\\!-\\!\lambda_{i,t}\tau_{i,t}^{m}\nabla_{\pi_{i,t}}\mathcal{L}_{1}(\pi_{i,t}^{m}))\|)$
for $\delta_{i}\\!\in\\!\mathbb{R}_{+}$, we get that
$\textnormal{min}_{\pi^{*}\in\Gamma_{i}^{*}}\|\pi_{i,t}^{m}\\!-\\!\pi^{*}\|\\!\leq\\!\epsilon_{1,i}^{\prime}\|\pi_{i,t}^{m}\\!-\\!\pi_{i}^{*}\|$.

A similar argument to what is above can be used for the
causes.$\;\;\footnotesize\blacksquare$

As Luo and Tseng [LuoZQ-jour1992a] have shown, such locally held bounds are
useful for analyzing the rate of convergence of iterative algorithms for
constrained, smooth optimization. The bounds can be used to very weakly
demonstrate that the sequence of functional iterates will eventually reach the
global functional solution, albeit independent of strong inertial-sequence
properties. Analogous bounds have been derived by Pang [PangJS-jour1987a] for
strongly convex problems. Here, we do not impose the condition of strong
convexity for the inference costs, which makes these results applicable to a
broader set of functionals, much like the ones that we employ.

Tseng and Yun [TsengP-jour2009a] later extended this bound for constrained,
non-smooth optimization. However, this was done in the context of gradient
descent, not proximal gradients.

To provide a more general convergence result, we need to consider specific
inertial sequences and incorporate them into the analysis. Toward this end, we
first bound the squared residual between the primary iterates, the states
$\gamma_{i,t}$ and the causes $\kappa_{i,t}$, and their corresponding
auxiliary iterates $\pi_{i,t}$ and $\pi_{i,t}^{\prime}$.

  * Proposition A.2. Let $\gamma_{i,t}\\!\in\\!\mathbb{R}^{k_{i}}$ be the hidden states and $\kappa_{i,t}\\!\in\\!\mathbb{R}^{d_{i}}$ be the hidden causes. Let $\pi_{i,t}\\!\in\\!\mathbb{R}^{k_{i}}$ be the auxiliary states at layer $i$ and time $t$. Assume that the state update, for a positive step size $\tau_{i,t}^{m}\\!\in\\!\mathbb{R}_{+}$, is given by
the relation $\gamma_{i,t+1}^{m}\\!=\\!\textnormal{\sc
prox}_{\\!\lambda_{i,t}}(\pi_{i,t}^{m}\\!-\\!\lambda_{i,t}\tau_{i,t}^{m}\nabla_{\pi_{i,t}^{m}}\mathcal{L}_{1}(\pi_{i,t}^{m},\kappa_{i,t},C_{i},D_{i}^{\top};\alpha_{i},\lambda_{i,t}))$,
with the auxiliary state update
$\pi_{i,t}^{m+1}\\!=\\!\gamma_{i,t+1}^{m}\\!+\\!\beta_{m}(\gamma_{i,t+1}^{m}\\!-\\!\gamma_{i,t+1}^{m-1})$.
Likewise, assume that the cause update, for a positive step size
$\tau^{\prime}_{i,t}{}^{\\!m}\\!\in\\!\mathbb{R}_{+}$, is
given by the relation $\kappa_{i,t+1}^{m}\\!=\\!\textnormal{\sc
prox}_{\\!\lambda_{i}}(\pi^{\prime}_{i,t}{}^{\\!m}\\!-\\!\lambda_{i}^{\prime}\tau^{\prime}_{i,t}{}^{\\!m}\nabla_{\pi^{\prime}_{i,t}{}^{\\!m}}\mathcal{L}_{2}(\gamma_{i,t+1},\pi^{\prime}_{i,t}{}^{\\!m},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t}))$,
with the auxiliary
cause relation
$\pi^{\prime}_{i,t}{}^{\\!m+1}\\!=\\!\kappa_{i,t+1}^{m}\\!+\\!\beta^{\prime}_{m}(\kappa_{i,t+1}^{m}\\!-\\!\kappa_{i,t+1}^{m})$.
In both cases, let
$\beta_{m},\beta^{\prime}_{m}\\!=\\!(k_{m}\\!-\\!1)/k_{m+1}$, with elements
$k_{m}\\!=\\!1\\!+\\!(m^{r}\\!-\\!1)/d$ with $r\\!\in\\!\mathbb{R}_{1,+}$,
$d\\!\in\\!\mathbb{R}_{+}$. There are some
$\epsilon_{1,i},\epsilon_{2,i}\\!\in\\!\mathbb{R}_{+}$ such that

$\|\pi_{i,t}^{m}\\!-\\!\gamma_{i,t+1}^{m}\|^{2}\geq\frac{\tau_{i,t}^{m}}{\epsilon_{1,i}}\Bigg{(}\\!\mathcal{L}_{1}(\gamma_{i,t+1}^{m},\kappa_{i,t},C_{i},D_{i}^{\top};\alpha_{i},\lambda_{i,t})\\!-\\!\mathcal{L}_{1}(\gamma_{i}^{*},\kappa_{i,t},C_{i},D_{i}^{\top};\alpha_{i},\lambda_{i,t})\\!\Bigg{)}$
$\|\pi^{\prime}_{i,t}{}^{\\!m}\\!-\\!\kappa_{i,t+1}^{m}\|^{2}\geq\frac{\tau^{\prime}_{i,t}{}^{\\!m}}{\epsilon_{2,i}}\Bigg{(}\\!\mathcal{L}_{2}(\gamma_{i,t+1},\kappa_{i,t+1}^{m},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t})\\!-\\!\mathcal{L}_{2}(\gamma_{i,t+1},\kappa_{i}^{*},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t})\\!\Bigg{)}$

where $\gamma_{i}^{*}\\!\in\\!\Gamma_{i}^{*}$,
$\gamma_{i}^{*}\\!\in\\!\mathbb{R}_{+}^{k_{i}}$, is a solution of the state-
inference cost and $\kappa_{i}^{*}\\!\in\\!K_{i}^{*}$,
$\kappa_{i}^{*}\\!\in\\!\mathbb{R}_{+}^{d_{i}}$, is a solution of the
cause-inference cost.

  * Proof: We focus on the case of the hidden states; that for the hidden causes has only slight differences. In what follows, for ease of presentation, we ignore the variables of the inference cost that remain fixed across inference iterations. We have, for $m$ being sufficiently large, that

$\displaystyle\mathcal{L}_{1}(\gamma_{i,t+1}^{m})\\!-\\!\mathcal{L}_{1}(\gamma_{i}^{*})$
$\displaystyle\leq
2\|\gamma_{i,t+1}^{m+1}\\!-\\!\pi_{i,t}^{m+1}\|^{2}/\tau_{i,t}^{m}\\!+\\!\textnormal{dist}(\gamma_{i,t+1}^{m+1},\Gamma_{i}^{*})\|\gamma_{i,t+1}^{m+1}\\!-\\!\pi_{i,t}^{m+1}\|/\tau_{i,t}^{m}\vspace{0.05cm}$
$\displaystyle\leq\xi_{1,i}^{-1}(4\epsilon_{1,i}^{\prime\prime}\\!+\\!\xi_{1,i})\|\gamma_{i,t+1}^{m+1}\\!-\\!\pi_{i,t}^{m+1}\|^{2}/2\tau_{i,t}^{m}$

where $\epsilon_{1,i}^{\prime\prime}\\!\in\\!\mathbb{R}_{+}$ and
$\xi_{1,i}\\!\in\\!\mathbb{R}_{+}$. There exists some
$\epsilon_{1,i}\\!\geq\\!\xi_{1,i}^{-1}(4\epsilon_{1,i}^{\prime\prime}\\!+\\!\xi_{1,i})/2$,
which must naturally be positive, such that the proposition is true. Here, the
second inequality follows from proposition A.1,

$\textnormal{dist}(\gamma_{i,t+1}^{m},\Gamma_{i}^{*})\leq\epsilon_{1,i}^{\prime\prime}\|\textnormal{\sc
prox}_{\\!\tau_{i,t}^{m}}(\gamma_{i,t+1}^{m}\\!-\\!\lambda_{i,t}\tau_{i,t}^{m}\nabla_{\gamma_{i,t+1}^{m}}\mathcal{L}_{1}(\gamma_{i,t+1}^{m})\\!-\\!\gamma_{i,t+1}^{m}\|/\ell_{i,t}\tau_{i,t}^{m},$

This arises from the non-decreasing nature of the proximal-norm function and
the Cauchy-Schwarz inequality, which implies that dividing by
$\ell_{i,t}\tau_{i,t}^{m}$ leads to a non-increasing function. The iterate-
solution distance can thus be further bounded from above as
$\textnormal{dist}(\gamma_{i,t+1}^{m},\Gamma_{i}^{*})\\!\leq\\!2\epsilon_{1,i}^{\prime\prime}\xi_{1,i}\|\gamma_{i,t+1}^{m}\\!-\\!\pi_{i,t}^{m}\|$.
Since the relationship holds for arbitrary $m$ sufficiently large, it can be
increased by one iteration.

A similar argument to what is above can be used for the
causes.$\;\;\footnotesize\blacksquare$

We now can bound the functional-value difference between an arbitrary
iterates, $\gamma_{i,t}$ and $\kappa_{i,t}$, and optimal solutions,
$\gamma_{i}^{*}\\!\in\\!\Gamma_{i}^{*}$ and
$\kappa_{i}^{*}\\!\in\\!K_{i}^{*}$. Note that, due to convexity of the two
inference costs, every solution is guaranteed to be a
globally optimal one. From this result, we will be able to obtain convergence
of the function values and iterates.

  * Proposition A.3. Let $\gamma_{i,t}\\!\in\\!\mathbb{R}^{k_{i}}$ be the hidden states and $\kappa_{i,t}\\!\in\\!\mathbb{R}^{d_{i}}$ be the hidden causes. Let the inertial
sequences used, respectively, for the state-inference and cause-inference
costs be $\beta_{m},\beta^{\prime}_{m}\\!=\\!(k_{m}\\!-\\!1)/k_{m+1}$, where
$k_{m}\\!=\\!1\\!+\\!(m^{r}\\!-\\!1)/d$ with $r\\!\in\\!\mathbb{R}_{1,+}$,
$d\\!\in\\!\mathbb{R}_{+}$. We have that

$\sum_{m=1}^{\infty}k_{m+1}^{2}\Bigg{(}\\!\mathcal{L}_{1}(\gamma_{i,t+1}^{m},\kappa_{i,t},C_{i},D_{i}^{\top};\alpha_{i},\lambda_{i,t})\\!-\\!\mathcal{L}_{1}(\gamma_{i}^{*},\kappa_{i,t},C_{i},D_{i}^{\top};\alpha_{i},\lambda_{i,t})\\!\Bigg{)}$
$\sum_{m=1}^{\infty}k_{m+1}^{2}\Bigg{(}\\!\mathcal{L}_{2}(\gamma_{i,t+1},\kappa_{i,t+1}^{m},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t})\\!-\\!\mathcal{L}_{2}(\gamma_{i,t+1},\kappa_{i}^{*},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t})\\!\Bigg{)}$

are convergent. Here, $\gamma_{i}^{*}\\!\in\\!\Gamma_{i}^{*}$,
$\gamma_{i}^{*}\\!\in\\!\mathbb{R}{k_{i}}$, is a solution of the state-
inference cost and $\kappa_{i}^{*}\\!\in\\!K_{i}^{*}$,
$\kappa_{i}^{*}\\!\in\\!\mathbb{R}^{d_{i}}$, is a
solution of the cause-inference cost. We have assumed, here, that the state
update, for a positive step size
$\tau_{i,t}^{m}\\!\in\\!\mathbb{R}_{+}$, was given by the relation
$\gamma_{i,t+1}^{m}\\!=\\!\textnormal{\sc
prox}_{\\!\lambda_{i,t}}(\pi_{i,t}^{m}\\!-\\!\lambda_{i,t}\tau_{i,t}^{m}\nabla_{\pi_{i,t}^{m}}\mathcal{L}_{1}(\pi_{i,t}^{m},\kappa_{i,t},C_{i},D_{i}^{\top};\alpha_{i},\lambda_{i,t}))$,
with the
auxiliary update
$\pi_{i,t}^{m+1}\\!=\\!\gamma_{i,t+1}^{m}\\!+\\!\beta_{m}(\gamma_{i,t+1}^{m}\\!-\\!\gamma_{i,t+1}^{m-1})$.
As well, the cause update, for a positive step size
$\tau_{i,t}^{\prime}\\!\in\\!\mathbb{R}_{+}$,
was $\kappa_{i,t+1}^{m}\\!=\\!\textnormal{\sc
prox}_{\\!\lambda_{i}}(\pi^{\prime}_{i,t}{}^{\\!m}\\!-\\!\lambda_{i}^{\prime}\tau^{\prime}_{i,t}{}^{\\!m}\nabla_{\pi^{\prime}_{i,t}{}^{\\!m}}\mathcal{L}_{2}(\gamma_{i,t+1},\pi^{\prime}_{i,t}{}^{\\!m},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t}))$,
with the auxiliary cause update
$\pi^{\prime}_{i,t}{}^{\\!m+1}\\!=\\!\kappa_{i,t+1}^{m}\\!+\\!\beta^{\prime}_{m}(\kappa_{i,t+1}^{m}\\!-\\!\kappa_{i,t+1}^{m})$.

  * Proof: For ease of presentation, we ignore the variables of the inference cost that remain fixed across inference iterations. It can be shown that, for some $\xi_{1,i}\\!\in\\!\mathbb{R}_{+}$,

$\displaystyle\mathcal{L}_{1}(\gamma_{i,t+1}^{m+1})$
$\displaystyle\leq\mathcal{L}_{1}(\gamma_{i,t+1}^{\prime}{\\!\\!\\!\\!\\!\\!}^{m}\hskip
7.53996pt)\\!-\\!\|\gamma_{i,t+1}^{\prime}{\\!\\!\\!\\!\\!\\!}^{m}\hskip
7.53996pt-\gamma_{i,t+1}^{m+1}\|^{2}/2\tau_{i,t}^{m}+\|\gamma_{i,t+1}^{\prime}{\\!\\!\\!\\!\\!\\!}^{m}\hskip
7.53996pt\\!-\pi_{i,t}^{m+1}\|^{2}/2\tau_{i,t}^{m}-(1\\!-\\!\xi_{i,t})\|\gamma_{i,t+1}^{m+1}\\!-\\!\pi_{i,t}^{m+1}\|^{2}/\tau_{i,t}^{m}\vspace{0.05cm}$
$\displaystyle\leq(1\\!-\\!\beta_{m+1}^{-1})\mathcal{L}_{1}(\gamma_{i,t}^{m})+\beta_{m+1}\mathcal{L}_{1}(\gamma_{i}^{*})+\beta_{m+1}^{-2}\|\beta_{m}\gamma_{i,t+1}^{m+1}\\!-\\!(\beta_{m+1}\\!-\\!1)\gamma_{i,t+1}^{m}\\!-\\!\gamma_{i}^{*}\|^{2}/2\tau_{i,t}^{m}\vspace{0.05cm}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;+\beta_{m+1}^{-2}\|\beta_{m}\gamma_{i,t+1}^{m}\\!-\\!(\beta_{m}\\!-\\!1)\gamma_{i,t+1}^{m-1}\\!-\\!\gamma_{i}^{*}\|^{2}/2\tau_{i,t}^{m}-(1\\!-\\!\xi_{i,t})\|\gamma_{i,t+1}^{m+1}\\!-\\!\pi_{i,t}^{m+1}\|^{2}/\tau_{i,t}^{m}$

where $\gamma_{i,t+1}^{\prime}{\\!\\!\\!\\!\\!\\!}^{m}\hskip
7.53996pt\\!=\\!\beta_{m+1}^{-1}\gamma_{i}^{*}\\!+\\!(1\\!-\\!\beta_{m+!}^{-1})\gamma_{i,t}^{m}$.
Multiplying both sides by $k_{m+1}^{2}$ and re-arranging terms yields

$\displaystyle
k_{m+1}^{2}(\mathcal{L}_{1}(\gamma_{i,t+1}^{k})\\!-\\!\mathcal{L}_{1}(\gamma_{i}^{*}))\\!-\\!k_{m+1}^{2}(\mathcal{L}_{1}(\gamma_{i,t+1}^{m+1})\\!-\\!\mathcal{L}_{1}(\gamma_{i}^{*}))\vspace{0.05cm}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\geq(k_{m}^{2}\\!-\\!k_{m+1}^{2}\\!-\\!k_{m+1})(\mathcal{L}_{1}(\gamma_{i,t+1}^{m})\\!-\\!\mathcal{L}_{1}(\gamma_{i}^{*}))+k_{m+1}^{2}(1\\!-\\!\xi_{i,t})\|\gamma_{i,t+1}^{m}\\!-\\!\pi_{i,t}^{m}\|^{2}/2\tau_{i,t}^{m}\vspace{0.05cm}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;-\|k_{m+1}\gamma_{i,t+1}^{m+1}\\!-\\!(k_{m+1}\\!-\\!1)\gamma_{i,t+1}^{m}\\!-\\!\gamma_{i}^{*}\|^{2}/\tau_{i,t}^{m}-\|k_{m}\gamma_{i,t+1}^{m}\\!-\\!(k_{m}\\!-\\!1)\gamma_{i,t+1}^{m-1}\\!-\\!\gamma_{i}^{*}\|^{2}/\tau_{i,t}^{m}.$

The result derived in proposition A.2 can be applied to show that
$k_{m+1}^{2}(1\\!-\\!\xi_{i,t})\|\gamma_{i,t+1}^{m}\\!-\\!\pi_{i,t}^{m}\|^{2}/2\tau_{i,t}^{m}$
is bounded above by
$k_{m+1}^{2}(1\\!-\\!\xi_{i,t})(\mathcal{L}_{1}(\gamma_{i,t+1}^{m+1})\\!-\\!\mathcal{L}_{1}(\gamma_{i}^{*}))/4\epsilon_{1,i}$.
Continuing from above, we have that

$\displaystyle(2k_{m}^{2}\\!-\\!k_{m+1}^{2}\\!-\\!k_{m+1})(\mathcal{L}_{1}(\gamma_{i,t+1}^{m})\\!-\\!\mathcal{L}_{1}(\gamma_{i}^{*}))-(k_{m}^{2}\\!-\\!k_{m+1})(\gamma_{i,t+1}^{m+1})\\!-\\!\mathcal{L}_{1}(\gamma_{i}^{*}))\vspace{0.05cm}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\geq(k_{m}^{2}\\!-\\!k_{m+1}^{2}\\!-\\!k_{m+1})(\mathcal{L}_{1}(\gamma_{i,t+1}^{m})\\!-\\!\mathcal{L}_{1}(\gamma_{i}^{*}))+k_{m+1}^{2}(1\\!-\\!\xi_{i,t})\|\gamma_{i,t+1}^{m}\\!-\\!\pi_{i,t}^{m}\|^{2}/2\tau_{i,t}^{m}\vspace{0.05cm}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;+k_{m+1}^{2}(1\\!-\\!\xi_{i,t})\|\gamma_{i,t+1}^{m+1}\\!-\\!\pi_{i,t}^{m+1}\|^{2}/4\tau_{i,t}^{m}.\hskip
190.63338pt\phantom{.}$

From this, we can see that
$(2k_{m}^{2}\\!-\\!k_{m+1}^{2}\\!-\\!k_{m+1})(\mathcal{L}_{1}(\gamma_{i,t+1}^{m})\\!-\\!\mathcal{L}_{1}(\gamma_{i}^{*}))\\!+\\!k_{m+1}^{2}(1\\!-\\!\xi_{i,t})\|\gamma_{i,t+1}^{m}\\!-\\!\pi_{i,t}^{m}\|^{2}/2\tau_{i,t}^{m}$
is
a non-increasing sequence for $m$. It is bounded below. This implies
convergence of the sequence in $m$ and hence for $m\\!+\\!1$. This takes care
of the two terms on the left and the first two terms on the right-hand side.
This leaves the final term on the right-hand side,
$k_{m+1}^{2}(1\\!-\\!\xi_{i,t})\|\gamma_{i,t+1}^{m+1}\\!-\\!\pi_{i,t}^{m+1}\|^{2}/4\tau_{i,t}^{m}$,
which is also is convergent in $m$. Applying proposition A.2 to this final
term on the right-hand side proves the proposition for the hidden states.

A similar argument to what is above can be used for the
causes.$\;\;\footnotesize\blacksquare$

Based on properties of the inertial series $\\{\beta_{m}\\}_{m=1}^{\infty}$
and $\\{\beta_{m}^{\prime}\\}_{m=1}^{\infty}$, particularly that the inverse
of the inertial subcomponents $\sum_{m=1}^{\infty}k_{m}^{-1}$ is convergent,
we immediately obtain that the state $\\{\gamma_{i,t}^{m}\\}_{m=1}^{\infty}$
and cause $\\{\kappa_{i,t}^{m}\\}_{m=1}^{\infty}$ iterates are Cauchy. The
state and cause iterates are thus bounded. The Bolzano-Weierstrass theorem
implies convergence of iterate subsequences for complete spaces, which applies
to our case. The iterates themselves are also strongly convergent to global
solutions. Convergence of proximal-gradient-type schemes is not new. It,
however, needed to be verified for our accelerated case.

We are now able to prove the main convergence result of the paper.

  * Proposition 4. Let $\gamma_{i,t}\\!\in\\!\mathbb{R}^{k_{i}}$ be the hidden states and $\kappa_{i,t}\\!\in\\!\mathbb{R}^{d_{i}}$ be the hidden causes. The state iterates
$\\{\gamma_{i,t+1}^{m}\\}_{m=1}^{\infty}$ strongly converge to the global
solution of
$\mathcal{L}_{1}(\gamma_{i,t},\kappa_{i,t},C_{i},D_{i}^{\top};\alpha_{i},\lambda_{i,t})$
for the accelerated proximal gradient scheme. Likewise, the cause iterates
$\\{\kappa_{i,t+1}^{m}\\}_{m=1}^{\infty}$ for the accelerated proximal
gradient scheme strongly converge to the global solution of
$\mathcal{L}_{2}(\gamma_{i,t+1},\kappa_{i,t},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t})$
at a sub-polynomial rate. This occurs when using the inertial sequences
$\beta_{m},\beta^{\prime}_{m}\\!=\\!(k_{m}\\!-\\!1)/k_{m+1}$, where $k_{m}$
depends polynomially on $m$.

  * Proof: Strong convergence of the states $\\{\gamma_{i,t+1}^{m}\\}_{m=1}^{\infty}$ and causes $\\{\kappa_{i,t+1}^{m}\\}_{m=1}^{\infty}$ to the optimal solutions
$\gamma_{i}^{*}\\!\in\\!\Gamma_{i}^{*}$ and $\kappa_{i}^{*}\\!\in\\!K_{i}^{*}$
can be obtained from an extension of proposition A.3. For the convergence
rate, we note that there is some $\zeta_{i}\\!\in\\!\mathbb{R}_{+}$ such that
$\zeta_{i}m^{-r}\\!\geq\\!\|\gamma_{i,t+1}^{m-1}\\!-\\!\gamma_{i,t}^{m}\|$.
For $m^{\prime}\\!>\\!1$, we have that
$\|\gamma_{i,t+1}^{m+m^{\prime}}\\!-\\!\gamma_{i,t}^{m}\|$ is bounded
above by
$\sum_{j=m+1}^{m+m^{\prime}}\|\gamma_{i,t}^{j}\\!-\\!\gamma_{i,t}^{j-1}\|\\!\leq\\!\zeta_{i}\sum_{j=m+1}^{m+m^{\prime}}m^{-r}$.
As $m^{\prime}\\!\to\\!\infty$,
$\|\gamma_{i,t+1}^{m}\\!-\\!\gamma_{i}^{*}\|\\!\leq\\!\zeta_{i}r/m^{r}(r\\!-\\!1)$,
which
implies a sub-$r$-polynomial rate of convergence for the state iterate
sequence.

A similar result holds for the cause iterates.$\;\;\footnotesize\blacksquare$

The choice of the inertial sequence greatly affects convergence properties.
The classical sequence proposed by Nesterov, for instance, yields iterates
$\\{\gamma_{i,t+1}^{m}\\}_{m=1}^{\infty}$ and
$\\{\kappa_{i,t+1}^{m}\\}_{m=1}^{\infty}$ that only weakly converge to global
solutions $\gamma_{i}^{*}\\!\in\\!\Gamma_{i}^{*}$ and
$\kappa_{i}^{*}\\!\in\\!K_{i}^{*}$, which stems from the fact that
$\sum_{m=1}^{\infty}k_{m}^{-1}$, with
$k_{m+1}\\!=\\!(1\\!+\\!(1\\!+\\!4k_{m}^{2})^{1/2})/2$, is divergent. In
finite-dimensional Euclidean spaces, this is not a shortcoming, since it
implies convergence component-wise and thus is equivalent to strong
convergence.

The original DPCN relied on a Nesterov-style sequence, so we analyze its
convergence.

  * Proposition A.4. Let the inertial sequences used, respectively, for the state-inference and cause-inference costs be $\beta_{m},\beta^{\prime}_{m}\\!=\\!(k_{m}\\!-\\!1)/k_{m+1}$, where $k_{m+1}\\!=\\!(1\\!+\\!(1\\!+\\!4k_{m}^{2})^{1/2})/2$. We have that

$\sum_{m=1}^{\infty}k_{m}^{2}\Bigg{(}\\!\mathcal{L}_{1}(\gamma_{i,t+1}^{m},\kappa_{i,t},C_{i},D_{i}^{\top};\alpha_{i},\lambda_{i,t})-\mathcal{L}_{1}(\gamma_{i}^{*},\kappa_{i,t},C_{i},D_{i}^{\top};\alpha_{i},\lambda_{i,t})+\frac{1}{2\tau_{i,t}^{m}}\|\gamma_{i,t+1}^{m}\\!-\\!\gamma_{i,t+1}^{m-1}\|^{2}\\!\Bigg{)}$
$\sum_{m=1}^{\infty}k_{m}^{2}\Bigg{(}\\!\mathcal{L}_{2}(\gamma_{i,t+1},\kappa_{i,t+1}^{m},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t})\,-\,\mathcal{L}_{2}(\gamma_{i,t+1},\kappa_{i}^{*},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t})\,+\,\frac{1}{2\tau^{\prime}_{i,t}{}^{\\!m}}\|\kappa_{i,t+1}^{m}-\kappa_{i,t+1}^{m-1}\|^{2}\\!\Bigg{)}$

are convergent. Here, $\gamma_{i}^{*}\\!\in\\!\Gamma_{i}^{*}$,
$\gamma_{i}^{*}\\!\in\\!\mathbb{R}^{k_{i}}$, is a solution of the state-
inference cost and $\kappa_{i}^{*}\\!\in\\!K_{i}^{*}$,
$\kappa_{i}^{*}\\!\in\\!\mathbb{R}^{d_{i}}$, is a
solution of the cause-inference cost. We have assumed, here, that the state
update, for a positive step size
$\tau_{i,t}^{m}\\!\in\\!\mathbb{R}_{+}$, was given by the relation
$\gamma_{i,t+1}^{m}\\!=\\!\textnormal{\sc
prox}_{\\!\lambda_{i,t}}(\pi_{i,t}^{m}\\!-\\!\lambda_{i,t}\tau_{i,t}^{m}\nabla_{\pi_{i,t}^{m}}\mathcal{L}_{1}(\pi_{i,t}^{m},\kappa_{i,t},C_{i},D_{i}^{\top};\alpha_{i},\lambda_{i,t}))$,
with the
auxiliary update
$\pi_{i,t}^{m+1}\\!=\\!\gamma_{i,t+1}^{m}\\!+\\!\beta_{m}(\gamma_{i,t+1}^{m}\\!-\\!\gamma_{i,t+1}^{m-1})$.
As well, the cause update, for a positive step size
$\tau_{i,t}^{\prime}\\!\in\\!\mathbb{R}_{+}$,
was $\kappa_{i,t+1}^{m}\\!=\\!\textnormal{\sc
prox}_{\\!\lambda_{i}}(\pi^{\prime}_{i,t}{}^{\\!m}\\!-\\!\lambda_{i}^{\prime}\tau^{\prime}_{i,t}{}^{\\!m}\nabla_{\pi^{\prime}_{i,t}{}^{\\!m}}\mathcal{L}_{2}(\gamma_{i,t+1},\pi^{\prime}_{i,t}{}^{\\!m},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t}))$,
with the auxiliary cause update
$\pi^{\prime}_{i,t}{}^{\\!m+1}\\!=\\!\kappa_{i,t+1}^{m}\\!+\\!\beta^{\prime}_{m}(\kappa_{i,t+1}^{m}\\!-\\!\kappa_{i,t+1}^{m})$.

  * Proof: For ease of presentation, we ignore the variables of the inference cost that remain fixed across inference iterations. It can be shown that

$\begin{array}[]{l}\\!\\!\\!\\!\\!\\!\\!\\!\\!\mathcal{L}_{1}(\gamma_{i,t+1}^{m})-\mathcal{L}_{1}(\gamma_{i}^{*})+\beta_{m}^{2}\|\gamma_{i,t+1}^{m}\\!-\\!\gamma_{i,t+1}^{m-1}\|^{2}/2\tau_{i,t}^{m}\vspace{0.05cm}\\\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\geq\mathcal{L}_{1}(\gamma_{i,t+1}^{m+1})-\mathcal{L}_{1}(\gamma_{i}^{*})+\|\gamma_{i,t+1}^{m}\\!-\\!\gamma_{i,t+1}^{m+1}\|^{2}/2\tau_{i,t}^{m+1}.\end{array}$

Multiplying both sides by $k_{m+1}^{2}$, performing an addition by zero, and
re-arranging terms yields

$\displaystyle
k_{m+1}^{3}(\mathcal{L}_{1}(\gamma_{i,t+1}^{m})\\!-\\!\mathcal{L}_{1}(\gamma_{i}^{*}))+k_{m+1}^{3}\|\gamma_{i,t+1}^{m}\\!-\\!\gamma_{i,t+1}^{m-1}\|^{2}/2\tau_{i,t}^{m}\vspace{0.05cm}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\leq(k_{m+1}^{3}\\!+\\!k_{m}^{3}\\!-\\!k_{m}^{3})(\mathcal{L}_{1}(\gamma_{i,t+1}^{m})\\!-\\!\mathcal{L}_{1}(\gamma_{i}^{*}))-k_{m+1}(k_{m}\\!-\\!1)^{2}\|\gamma_{i,t+1}^{m}\\!-\\!\gamma_{i,t+1}^{m-1}\|^{2}/2\tau_{i,t}^{m}\vspace{0.05cm}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\leq
k_{m}^{3}(\mathcal{L}_{1}(\gamma_{i,t+1}^{m})\\!-\\!\mathcal{L}_{1}(\gamma_{i}^{*}))+k^{\prime}(\mathcal{L}_{1}(\gamma_{i,t+1}^{m})\\!-\\!\mathcal{L}_{1}(\gamma_{i}^{*}))-(k_{m}^{2}(2\\!-\\!k^{\prime})\\!+\\!k_{m}(2k^{\prime}\\!-\\!1)\\!-\\!k^{\prime})/2\tau_{i,j}^{m}\vspace{0.05cm}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;+k_{m}^{3}\|\gamma_{i,t+1}^{m}\\!-\\!\gamma_{i,t+1}^{m-1}\|^{2}/2\tau_{i,t}^{m}.$

The last inequality follows because $\sum_{m=1}^{\infty}k_{m}^{-1}$ is
divergent. In this case, there exists some $0\\!<\\!k^{\prime}\\!<\\!2$ such
that $k_{m+1}\\!-\\!k_{m}\\!\leq\\!k^{\prime}$ for all $m\\!>\\!m^{\prime}$,
$m^{\prime}\\!>\\!0$. We therefore have that

$\displaystyle
k^{\prime}(k_{m}^{2}\\!+\\!k_{m}\\!+\\!1)(\mathcal{L}_{1}(\gamma_{i,t+1}^{m})\\!-\\!\mathcal{L}_{1}(\gamma_{i}^{*}))\vspace{0.05cm}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\geq
k_{m+1}^{3}(\mathcal{L}_{1}(\gamma_{i,t+1}^{m+1})\\!-\\!\mathcal{L}_{1}(\gamma_{i}^{*})+\|\gamma_{i,t+1}^{m+1}\\!-\\!\gamma_{i,t+1}^{m}\|^{2}/2\tau_{i,t}^{m+1})+k_{m}^{3}(\mathcal{L}_{1}(\gamma_{i,t+1}^{m})\\!-\\!\mathcal{L}_{1}(\gamma_{i}^{*})\vspace{0.05cm}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;+\|\gamma_{i,t+1}^{m}\\!-\\!\gamma_{i,t+1}^{m-1}\|^{2}/2\tau_{i,t}^{m}).$

Re-organizing terms allows us to demonstrate that
$\sum_{m=1}^{\infty}\|\gamma_{i,t+1}^{m}\\!-\\!\gamma_{i,t+1}^{m-1}\|^{2}/2\tau_{i,t}^{m}$
is convergent via a Cauchy test. This implies that
$\sum_{m=1}^{\infty}k_{m}^{2}(\mathcal{L}_{1}(\gamma_{i,t+1}^{m})\\!-\\!\mathcal{L}_{1}(\gamma_{i}^{*})\\!+\\!\|\gamma_{i,t+1}^{m}\\!-\\!\gamma_{i,t+1}^{m-1}|^{2}/2\tau_{i,t}^{m})$
is also convergent.

A similar argument to what is above can be used for the
causes.$\;\;\footnotesize\blacksquare$

The rate of convergence, though, is limited when choosing a Nesterov-style
inertial sequence, both locally and globally. In the global case, we have that

  * Proposition A.5. Let $\gamma_{i,t}\\!\in\\!\mathbb{R}^{k_{i}}$ be the hidden states and $\kappa_{i,t}\\!\in\\!\mathbb{R}^{d_{i}}$ be the hidden causes. The state iterates
$\\{\gamma_{i,t+1}^{m}\\}_{m=1}^{\infty}$ strongly converge to the global
solution of
$\mathcal{L}_{1}(\gamma_{i,t},\kappa_{i,t},C_{i},D_{i}^{\top};\alpha_{i},\lambda_{i,t})$
for the accelerated proximal gradient scheme. Likewise, the cause iterates
$\\{\kappa_{i,t+1}^{m}\\}_{m=1}^{\infty}$ for the accelerated proximal
gradient scheme strongly converge to the global solution of
$\mathcal{L}_{2}(\gamma_{i,t+1},\kappa_{i,t},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t})$
at a sub-quadratic rate. This occurs when using the inertial sequences
$\beta_{m},\beta^{\prime}_{m}\\!=\\!(k_{m}\\!-\\!1)/k_{m+1}$, where
$k_{m+1}\\!=\\!(1\\!+\\!(1\\!+\\!4k_{m}^{2})^{1/2})/2$.

  * Proof: Strong convergence of the states $\\{\gamma_{i,t+1}^{m}\\}_{m=1}^{\infty}$ and causes $\\{\kappa_{i,t+1}^{m}\\}_{m=1}^{\infty}$ to the optimal solutions
$\gamma_{i}^{*}\\!\in\\!\Gamma_{i}^{*}$ and $\kappa_{i}^{*}\\!\in\\!K_{i}^{*}$
can be obtained from an extension of proposition A.4. For the convergence
rate, we note that there is some $\zeta_{i}\\!\in\\!\mathbb{R}_{+}$ such that
$\zeta_{i}m^{-3/2}\\!\geq\\!\|\gamma_{i,t+1}^{m-1}\\!-\\!\gamma_{i,t}^{m}\|$.
For $m^{\prime}\\!>\\!1$, we have that
$\|\gamma_{i,t+1}^{m+m^{\prime}}\\!-\\!\gamma_{i,t}^{m}\|$ is bounded
above by
$\sum_{j=m+1}^{m+m^{\prime}}\|\gamma_{i,t}^{j}\\!-\\!\gamma_{i,t}^{j-1}\|\\!\leq\\!\zeta_{i}\sum_{j=m+1}^{m+m^{\prime}}m^{-3}$.
As $m^{\prime}\\!\to\\!\infty$,
$\|\gamma_{i,t+1}^{m}\\!-\\!\gamma_{i}^{*}\|\\!\leq\\!\zeta_{i}/2m^{2}$, which
implies a
sub-quadratic rate of convergence for the state iterate sequences.

A similar argument to what is above demonstrates the convergence rate for the
cause iterate sequences.$\;\;\footnotesize\blacksquare$

From this proposition, we see that a polynomial extra-gradient step permits
making either equal or larger adjustments, on average, per iteration than the
Nesterov step. It is, in essence, artificially adapting the step size without
causing divergence. The ADPCN iterates thus often reach a given loss magnitude
more quickly than those for the DPCN.

This potentially improved step size offered by a polynomial inertial sequence
has a major impact on ADPCN performance. A feed-forward, bottom-up inference
problem is solved to propagate a batch of stimuli through the network and
convert it into states and causes. This problem has to be solved at every
stage, which we do using the method of proximal gradients. If a subpar
solution is returned for the bottom-up inference, then it impacts the quality
of the parameter updates. This, in turn, affects the network response for the
next batch of stimuli. A great many presentations of the stimuli may be needed
to counteract this issue. There is a chance that the corresponding network
parameters learned using a linear extra-gradient step may never approach the
same performance as those for our polynomial-based step.

Note that a feed-back, top-down inference problem must also be solved at every
stage to back-propagate the causes to earlier layers. However, top-down
inference has a global best solution that can be obtained directly without
relying on non-iterative processes. This is why we listed it as having a
constant-time convergence rate in fig. A.1.

To better understand why the convergence is better with a polynomial inertial
sequence, it is helpful to re-cast the proximal gradient updates in a way that
permits understanding local convergence behaviors using spectral analysis. We
do this first for the state-inference process.

  * Proposition A.6. The state update $\gamma_{i,t+1}^{m}\\!=\\!\textnormal{\sc prox}_{\\!\lambda_{i,t}}(\pi_{i,t}^{m}\\!-\\!\lambda_{i,t}\tau_{i,t}^{m}\nabla_{\pi_{i,t}}\mathcal{L}_{1}(\pi_{i,t},\kappa_{i,t},C_{i},D_{i}^{\top};\alpha_{i},\lambda_{i,t}))$,
with
$\pi_{i,t}^{m+1}\\!=\\!\gamma_{i,t}^{m}\\!+\\!\beta_{m}(\gamma_{i,t}^{m}\\!-\\!\gamma_{i,t}^{m-1})$,
is equivalent to $\gamma_{i,t+1}^{m}\\!=\\!\textnormal{\sc
shrink}(w_{i,t}^{m};\lambda_{i,t}/\ell_{i,t})$, for the auxiliary variable

$w_{i,t}^{m}\\!=\\!\Bigg{(}\\!I_{k_{i}\times
k_{i}}\\!-\\!\ell_{i,t}^{-1}D_{i}^{\top}D_{i}\\!\Bigg{)}\pi_{i,t}^{m}\\!+\\!\ell_{i,t}^{-1}D_{i}^{\top}\kappa_{i-1,t}\\!+\\!\alpha_{i}\ell_{i,t}^{-1}\textnormal{\sc
proj}_{\infty}\Bigg{(}\\!(\pi_{i,t}^{m}\\!-\\!C_{i}\gamma_{i,t-1})/\mu_{i}\\!\Bigg{)},$

where $I_{k_{i}\times k_{i}}\\!\in\\!\mathbb{R}_{+}^{k_{i}\times k_{i}}$ is
the identity matrix, $0_{1\times 2k_{i}}\\!\in\\!\mathbb{R}^{2k_{i}}$ is a row
vector of zeros and $1_{k_{i}+1\times 1}\\!\in\\!\mathbb{R}^{k_{i}+1}_{+}$ is
a
column vector of ones. This is equivalent to the matrix recurrence
$(w^{m+1}_{i,t},w^{m}_{i,t},1)^{\top}\\!\\!=\\!S_{i,t}^{m}(w^{m}_{i,t},w^{m-1}_{i,t},1)^{\top}$.
More specifically,

$\begin{pmatrix}w^{m+1}_{i,t}\vspace{0.05cm}\\\ w^{m}_{i,t}\vspace{0.05cm}\\\
1\end{pmatrix}=\underbrace{\begin{pmatrix}W_{i,t}^{m}&\ell_{i,t}^{-1}D_{i}^{\top}\kappa_{i-1,t}\\!+\\!(I_{k_{i}\times
k_{i}}\\!-\\!\ell_{i,t}^{-1}D_{i}^{\top}D_{i})z_{i,t}^{m}\\!+\\!\alpha_{i}\ell_{i,t}^{-1}f_{i,t}^{m}\vspace{0.05cm}\\\
0_{1\times 2k_{i}}&1_{k_{i}+1\times 1}\\\
\end{pmatrix}}_{S_{i,t}^{m}}\\!\begin{pmatrix}w^{m}_{i,t}\vspace{0.05cm}\\\
w^{m-1}_{i,t}\vspace{0.05cm}\\\ 1\end{pmatrix}\vspace{-0.1cm}$

where
$z_{i,t}^{m}\\!=\\!-(1\\!+\\!\beta_{m})\lambda_{i,t}s_{i,t}^{m}/\ell_{i,t}\\!+\\!\beta_{m}\lambda_{i,t}s_{i,t}^{m-1}/\ell_{i,t}$,
with $s_{i,t}^{m}\\!=\\!\textnormal{\sc sign}(\textnormal{\sc
shrink}(w^{m}_{i,t};\lambda_{i,t}/\ell_{i,t}))$. The term $f_{i,t}^{m}$
accounts for the Nesterov-smoothed component,
$f_{i,t}^{m}\\!=\\!\textnormal{\sc
proj}_{\infty}(((H_{i,t}^{m})^{2}w_{i,t}^{m}\\!-\\!\lambda_{i,t}^{m}\ell_{i,t}^{-1}s_{i,t}^{m}\\!-\\!C_{i}\gamma_{i,t-1})/\mu_{i})$,
which is given by projecting the $L_{1}$-sparse state-transition component
onto an $L_{\infty}$ ball. The matrix
$W_{i,t}^{m}\\!\in\\!\mathbb{R}^{2k_{i}\times 2k_{i}}$ is

$W_{i,t}^{m}=\begin{pmatrix}(1\\!+\\!\beta_{m})(I_{k_{i}\times
k_{i}}\\!-\\!\ell_{i,t}^{-1}D_{i}^{\top}D_{i})(H_{i,t}^{m})^{2}&-\beta_{m+1}(I_{k_{i}\times
k_{i}}\\!-\\!\ell_{i,t}^{-1}D_{i}^{\top}D_{i})(H_{i,t}^{m})^{2}\vspace{0.05cm}\\\
I_{k_{i}\times k_{i}}&0_{k_{i}\times k_{i}}\end{pmatrix}.$

Here, $\ell_{i,t}\\!\in\\!\mathbb{R}_{0,+}$ is the Lipschitz constant of the
state-inference cost at a given layer $i$ and for the current batch $t$. The
flag matrix $H_{i,t}^{m}\\!=\\!\textnormal{\sc diag}(\textnormal{\sc
sign}(\textnormal{\sc shrink}(w^{m}_{i,t};\lambda_{i,t}/\ell_{i,t})))$ is
diagonal and relies on a sparse shrinkage process
for the auxiliary variable.

  * Proof: The underlying update for accelerated proximal gradients can be re-written as

$\displaystyle\gamma_{i,t+1}^{m}$ $\displaystyle=\textnormal{arg
min}_{\pi}(\|\pi\\!-\\!(\pi_{i,t}^{m}\\!-\\!\ell_{i,t}^{-1}\nabla_{\pi_{i,t}^{m}}\mathcal{L}_{1}^{\prime}(\pi_{i,t}^{m}))\|^{2}/2\ell_{i,t}\\!+\\!\lambda_{i,t}\|\pi\|_{1})\vspace{0.05cm}$
$\displaystyle=\textnormal{\sc shrink}((I_{k_{i}\times
k_{i}}\\!-\\!\ell_{i,t}^{-1}D_{i}^{\top}D_{i})\pi_{i,t}^{m}\\!+\\!\ell_{i,t}^{-1}D_{i}^{\top}\kappa_{i-1,t}\\!+\\!\alpha_{i}\ell_{i,t}^{-1}\textnormal{\sc
proj}_{\infty}((\pi_{i,t}^{m}\\!-\\!C_{i}\gamma_{i,t-1})/\mu_{i});\lambda_{i,t}/\ell_{i,t})$

where $\mathcal{L}_{1}^{\prime}(\pi_{i,t}^{m})$ represents the state-inference
cost but without the $L_{1}$-sparsity constraint on the states. Here, we have
used a Nesterov smoothing approach, with $\mu_{i}\\!\in\\!\mathbb{R}_{+}$, to
deal with the $L_{1}$-sparse state-transition update,
$\textnormal{arg max}_{\|\Omega_{i,t}\|_{\infty}\leq
1}\Omega_{i,t}^{\top}(\pi_{i,t}^{m}\\!-\\!C_{i}\gamma_{i,t-1})\\!-\\!\mu_{i}\|\Omega_{i,t}\|^{2}_{2}/2\\!=\\!\textnormal{\sc
proj}_{\infty}((\pi_{i,t}^{m}\\!-\\!C_{i}\gamma_{i,t-1})/\mu_{i})$. This
projection onto an $L_{\infty}$-ball has the closed-form solution

$\textnormal{\sc
proj}_{\infty}((\pi_{i,t}^{m}\\!-\\!C_{i}\gamma_{i,t-1})/\mu_{i}=\begin{cases}1,&(\pi_{i,t}^{m}\\!-\\!C_{i}\gamma_{i,t-1})/\mu_{i}\\!>\\!1\vspace{0.05cm}\\\
(\pi_{i,t}^{m}\\!-\\!C_{i}\gamma_{i,t-1})/\mu_{i},&-1\\!\leq\\!(\pi_{i,t}^{m}\\!-\\!C_{i}\gamma_{i,t-1})/\mu_{i}\\!\leq\\!1\vspace{0.05cm}\\\
-1,&(\pi_{i,t}^{m}\\!-\\!C_{i}\gamma_{i,t-1})/\mu_{i}\\!<\\!-1\end{cases}.$

We replace the states by the auxiliary variable $w_{i,t}^{m}$ and note that
$\gamma_{i,t+1}^{m}=\textnormal{\sc
shrink}(w_{i,t}^{m};\lambda_{i,t}/\ell_{i,t})$, where

$\textnormal{\sc shrink}(w_{i,t}^{m};\lambda_{i,t}/\ell_{i,t})=\textnormal{\sc
diag}(\textnormal{\sc sign}(\textnormal{\sc
shrink}(w_{i,t}^{m};\lambda_{i,t}/\ell_{i,t})))^{2}w_{i,t}^{m}\\!-\\!\lambda_{i,t}\textnormal{\sc
sign}(\textnormal{\sc
shrink}(w_{i,t}^{m};\lambda_{i,t}/\ell_{i,t}))/\ell_{i,t},$ $\textnormal{\sc
sign}(\textnormal{\sc
shrink}(w_{i,t}^{m};\lambda_{i,t}/\ell_{i,t}))=\begin{cases}1,&w_{i,t}^{m}\\!>\\!\lambda_{i,t}/\ell_{i,t}\vspace{0.05cm}\\\
0,&-\lambda_{i,t}/\ell_{i,t}\\!\leq\\!w_{i,t}^{m}\\!\leq\\!\lambda_{i,t}/\ell_{i,t}\vspace{0.05cm}\\\
-1,&w_{i,t}^{m}\\!<\\!-\lambda_{i,t}/\ell_{i,t}\end{cases}.$

We can systematically re-write the auxiliary-variable update as

$\displaystyle w_{i,t}^{m+1}$ $\displaystyle=(I_{k_{i}\times
k_{i}}\\!-\\!\ell_{i,t}^{-1}D_{i}^{\top}D_{i})(\gamma_{i,t+1}^{m}\\!+\\!\beta_{m}(\gamma_{i,t+1}^{m}\\!-\\!\gamma_{i,t+1}^{m-1}))+\ell_{i,t}^{-1}D_{i}^{\top}\kappa_{i-1,t}+\alpha_{i}\ell_{i,t}^{-1}\textnormal{\sc
proj}_{\infty}((\gamma_{i,t+1}^{m}\\!-\\!C_{i}\gamma_{i,t})/\mu_{i})\vspace{0.05cm}$
$\displaystyle=(I_{k_{i}\times
k_{i}}\\!-\\!\ell_{i,t}^{-1}D_{i}^{\top}D_{i})((1\\!+\\!\beta_{m})(H_{i,t}^{m-1})^{2}w_{i,t}^{m}\\!-\\!\lambda_{i,t}\textnormal{\sc
sign}(\textnormal{\sc
shrink}(w_{i,t}^{m-1};\lambda_{i,t}/\ell_{i,t}))/\ell_{i,t})\vspace{0.05cm}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;-(I_{k_{i}\times
k_{i}}\\!-\\!\ell_{i,t}^{-1}D_{i}^{\top}D_{i})(\beta_{m-1}(H_{i,t}^{m})^{2}w_{i,t}^{m}\\!+\\!\lambda_{i,t}\textnormal{\sc
sign}(\textnormal{\sc
shrink}(w_{i,t}^{m-1};\lambda_{i,t}/\ell_{i,t}))/\ell_{i,t})\vspace{0.05cm}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;-\ell_{i,t}^{-1}D_{i}^{\top}\kappa_{i-1,t}+\alpha_{i}\ell_{i,t}^{-1}\textnormal{\sc
proj}_{\infty}((\gamma_{i,t+1}^{m}\\!-\\!C_{i}\gamma_{i,t})/\mu_{i})\vspace{0.05cm}$
$\displaystyle=(1\\!+\\!\beta_{m})(I_{k_{i}\times
k_{i}}\\!-\\!\ell_{i,t}^{-1}D_{i}^{\top}D_{i})(H_{i,t}^{m})^{2}w_{i,t}^{m}-\beta_{m}(I_{k_{i}\times
k_{i}}\\!-\\!\ell_{i,t}^{-1}D_{i}^{\top}D_{i})(H_{i,t}^{m-1})^{2}w_{i,t}^{m-1}-\ell_{i,t}^{-1}D_{i}^{\top}\kappa_{i-1,t}\vspace{0.05cm}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;+(I_{k_{i}\times
k_{i}}\\!-\\!\ell_{i,t}^{-1}D_{i}^{\top}D_{i})((-\lambda_{i,t}\\!-\\!\lambda_{i,t}\beta_{m})\textnormal{\sc
sign}(\textnormal{\sc
shrink}(w_{i,t}^{m-1};\lambda_{i,t}/\ell_{i,t}))/\ell_{i,t}\vspace{0.05cm}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;+\lambda_{i,t}\beta_{m})\textnormal{\sc
sign}(\textnormal{\sc
shrink}(w_{i,t}^{m-1};\lambda_{i,t}/\ell_{i,t}))/\ell_{i,t})+\alpha_{i}\ell_{i,t}^{-1}\textnormal{\sc
proj}_{\infty}((\gamma_{i,t+1}^{m}\\!-\\!C_{i}\gamma_{i,t})/\mu_{i}).$

The matrix recurrence follows from this update.$\;\;\footnotesize\blacksquare$

We now characterize the cause inference in a similar manner.

  * Proposition A.7. The cause update $\kappa_{i,t+1}^{m}\\!=\\!\textnormal{\sc prox}_{\\!\lambda_{i}}(\pi^{\prime}_{i,t}{}^{\\!m}\\!-\\!\lambda_{i}^{\prime}\tau^{\prime}_{i,t}{}^{\\!m}\nabla_{\pi^{\prime}_{i,t}{}^{\\!m}}\mathcal{L}_{2}(\gamma_{i,t+1},\pi^{\prime}_{i,t}{}^{\\!m},G_{i};\alpha_{i}^{\prime},\lambda_{i}^{\prime},\eta_{i}^{\prime},\lambda_{i,t}))$,
with
$\pi^{\prime}_{i,t}{}^{\\!m+1}\\!=\\!\kappa_{i,t+1}^{m}\\!+\\!\beta^{\prime}_{m}(\kappa_{i,t+1}^{m}\\!-\\!\kappa_{i,t+1}^{m})$,
is equivalent to $\kappa_{i,t+1}^{m}\\!=\\!\textnormal{\sc
shrink}(v_{i,t}^{m};\lambda_{i}^{\prime}/\ell^{\prime}_{i,t})$, for the
auxiliary
variable

$v_{i,t}^{m}\\!=\\!\Bigg{(}\\!I_{d_{i}\times
d_{i}}\\!-\\!1/\ell^{\prime}_{i,t}\\!\Bigg{)}\pi_{i,t}^{\prime}{}^{\\!\\!\\!\\!m}\\!+\\!2\eta_{i}^{\prime}I_{d_{i}\times
d_{i}}\kappa_{i,t}^{\prime}/\ell_{i,t}^{\prime}\\!-\\!\alpha_{i}^{\prime}/\ell_{i,t}^{\prime}\Bigg{(}\\!G_{i}^{\top}\textnormal{exp}(-G_{i}\pi_{i,t}^{\prime}{}^{\\!\\!\\!\\!m})|\gamma_{i,t+1}^{j}|\\!\Bigg{)},$

where $I_{d_{i}\times d_{i}}\\!\in\\!\mathbb{R}_{+}^{d_{i}\times d_{i}}$ is
the identity matrix, $0_{1\times 2d_{i}}\\!\in\\!\mathbb{R}^{2d_{i}}$ is a row
vector of zeros and $1_{d_{i}+1\times 1}\\!\in\\!\mathbb{R}^{d_{i}+1}_{+}$ is
a
column vector of ones. This is equivalent to the matrix recurrence
$(v^{m+1}_{i,t},v^{m}_{i,t},1)^{\top}\\!\\!=\\!T_{i,t}^{m}(v^{m}_{i,t},v^{m-1}_{i,t},1)^{\top}$.
More
specifically,

$\begin{pmatrix}v^{m+1}_{i,t}\vspace{0.05cm}\\\ v^{m}_{i,t}\vspace{0.05cm}\\\
1\end{pmatrix}=\underbrace{\begin{pmatrix}V_{i,t}^{m}&2\eta_{i}^{\prime}I_{d_{i}\times
d_{i}}\kappa_{i,t}^{\prime}/\ell_{i,t}^{\prime}\\!+\\!(I_{d_{i}\times
d_{i}}\\!-\\!1/\ell_{i,t}^{\prime})z_{i,t}^{\prime}{}^{\\!\\!\\!\\!m}\\!-\\!\alpha_{i}^{\prime}g_{i,t}^{m}/\ell_{i,t}^{\prime}\vspace{0.05cm}\\\
0_{1\times 2d_{i}}&1_{d_{i}+1\times 1}\\\
\end{pmatrix}}_{T_{i,t}^{m}}\\!\begin{pmatrix}v^{m}_{i,t}\vspace{0.05cm}\\\
v^{m-1}_{i,t}\vspace{0.05cm}\\\ 1\end{pmatrix}\vspace{-0.1cm}$

where
$z_{i,t}^{m}\\!=\\!-(1\\!+\\!\beta_{m}^{\prime})\lambda_{i}^{\prime}q_{i,t}^{m}/\ell_{i,t}^{\prime}\\!+\\!\beta_{m}^{\prime}\lambda_{i}^{\prime}q_{i,t}^{m-1}/\ell_{i,t}^{\prime}$,
with $q_{i,t}^{m}\\!=\\!\textnormal{\sc sign}(\textnormal{\sc
shrink}(v^{m}_{i,t};\lambda_{i}^{\prime}/\ell_{i,t}^{\prime}))$. The term
$g_{i,t}^{m}$
accounts for the invariant-matrix component,
$g_{i,t}^{m}\\!=\\!G_{i}^{\top}\textnormal{exp}(-G_{i}v_{i,t}^{\prime}{}^{\\!\\!\\!\\!m})|\gamma_{i,t+1}^{j}|$.
The matrix $V_{i,t}^{m}\\!\in\\!\mathbb{R}^{2d_{i}\times 2d_{i}}$ is

$V_{i,t}^{m}=\begin{pmatrix}(1\\!+\\!\beta_{m}^{\prime})(I_{d_{i}\times
d_{i}}\\!-\\!1/\ell_{i,t}^{\prime})(M_{i,t}^{m})^{2}&-\beta_{m+1}^{\prime}(I_{d_{i}\times
d_{i}}\\!-\\!1/\ell_{i,t}^{\prime})(M_{i,t}^{m})^{2}\vspace{0.05cm}\\\
I_{d_{i}\times d_{i}}&0_{d_{i}\times d_{i}}\end{pmatrix}.$

Here, $\ell_{i,t}^{\prime}\\!\in\\!\mathbb{R}_{0,+}$ is the Lipschitz constant
of the state-inference cost at a given layer $i$ and for the current batch
$t$. The flag matrix $M_{i,t}^{m}\\!=\\!\textnormal{\sc diag}(\textnormal{\sc
sign}(\textnormal{\sc
shrink}(v^{m}_{i,t};\lambda_{i}^{\prime}/\ell_{i,t}^{\prime})))$ is diagonal
and relies on a sparse shrinkage process
for the auxiliary variable.

We now list spectral properties of the iteration sub-matrices
$W_{i,t}^{m}\\!\in\\!\mathbb{R}^{k_{i}+1\times k_{i}+1}$ and
$V_{i,t}^{m}\\!\in\\!\mathbb{R}^{d_{i}+1\times d_{i}+1}$. The
validity of these claims follows from extensions of work on the alternating
direction method of multipliers [BoleyD-jour2013a].

  * Lemma A.1. Suppose that the flag matrices across consecutive iterations $m$ of the hidden state and cause updates respectively satisfy $H_{i,t}^{m-1}\\!=\\!H_{i,t}^{m}\\!=\\!H_{i,t}^{m+1}$ and $M_{i,t}^{m-1}\\!=\\!M_{i,t}^{m}\\!=\\!M_{i,t}^{m+1}$. The iteration matrices $W_{i,t}^{m}$ and $V_{i,t}^{m}$ are different at each step and satisfy:

    * (i) $\|W_{i,t}^{m}\|_{2}\\!\leq\\!1$ and $\|V_{i,t}^{m}\|_{2}\\!\leq\\!1$. Also, $\|(I_{k_{i}\times k_{i}}\\!-\\!\ell_{i,t}^{-1}D_{i}^{\top}D_{i})H_{i,t}^{m}\|_{2}\\!\leq\\!1$ and $\|(I_{d_{i}\times d_{i}}\\!-\\!1/\ell_{i,t}^{\prime})M_{i,t}^{m}\|_{2}\\!\leq\\!1$.

    * (ii) For any $0\\!<\\!\beta_{m},\beta_{m}^{\prime}\\!\leq\\!1$, the eigenvalues of $W_{i,t}^{m}$ and $V_{i,t}^{m}$ lie in a closed circle in the real-complex plane that is centered at $(0,\frac{1}{2})$ and that has a radius of $\frac{1}{2}$. If either of these iteration matrices has eigenvalues with absolute values of $\rho(W_{i,t}^{m})\\!=\\!1$ and $\rho(V_{i,t}^{m})\\!=\\!1$, then there must be no imaginary component. If the step
sizes are such that $\beta_{m},\beta_{m}^{\prime}\\!<\\!1$ and if