# Sequential Stochastic Control (Single or Multi-Agent) Problems Nearly Admit
Change of Measures with Independent Measurements

Ian Hogeboom-Burr  Serdar Yüksel The authors are with the Dept. of Mathematics
and Statistics, Queen’s University, Kingston K7L 3N6, ON, Canada,
<EMAIL_ADDRESS>
###### Abstract

Change of measures has been an effective method in stochastic control and
analysis; in continuous-time control this follows Girsanov’s theorem applied
to both fully observed and partially observed models, in decentralized
stochastic control (or stochastic dynamic team theory) this is known as
Witsenhausen’s static reduction, and in discrete-time classical stochastic
control Borkar has considered this method for partially observed Markov
Decision processes (POMDPs) generalizing Fleming and Pardoux’s approach in
continuous-time. This method allows for equivalent optimal stochastic control
or filtering in a new probability space where the measurements form an
independent exogenous process in both discrete-time and continuous-time and
the Radon-Nikodym derivative (between the true measure and the reference
measure formed via the independent measurement process) is pushed to the cost
or dynamics. However, for this to be applicable, an absolute continuity
condition is necessary. This raises the following question: can we perturb any
discrete-time sequential stochastic control problem by adding some arbitrarily
small additive (e.g. Gaussian or otherwise) noise to the measurements to make
the system measurements absolutely continuous, so that a change-of-measure (or
static reduction) can be applicable with arbitrarily small error in the
optimal cost? That is, are all sequential stochastic (single-agent or
decentralized multi-agent) problems $\epsilon$-away from being static
reducible as far as optimal cost is concerned, for any $\epsilon>0$? We show
that this is possible when the cost function is bounded and continuous in
controllers’ actions and the action spaces are convex. We also note that the
solution and the cost obtained for the perturbed system is realizable (under a
randomized policy) for the original model.

##  1 Introduction

Reformulation of stochastic dynamic control and filtering problems via a
change of measure has proven to be very effective for existence,
approximations, filtering, and dynamic programming methods under a variety of
contexts. In discrete-time, such a formulation leads to an equivalent system
under which measurements are exogenous independent variables. For continuous-
time stochastic control, this method has been very popular since the analysis
in [4], to avoid stringent conditions on control policies to satisfy the
existence of strong solutions to controlled stochastic differential equations
(see also [14, 15]), which allows the control to be a function of an
independent Brownian innovations process. This was utilized by Fleming and
Pardoux [18], who introduced wide-sense admissible control policies for
classical partially observed stochastic control problems (POMDPs), where first
the measures were reduced to an exogenous Brownian process and a control
policy was defined to be wide-sense admissible if the control and (exogenous)
measurements were independent from future increments of the measurement
process (see also [7], where this was utilized further without separating
estimation and control in POMDPs). Borkar [10], [11] obtained existence
results in average cost POMDPs via generalizing Fleming and Pardoux’s notion
to discrete-time POMDPs, where, once again, first the measurements were made
independent and then the control and measurements form a wide-sense admissible
process if they are independent from future measurements. In non-linear
filtering theory such methods have found applications via the Kushner-
Kallianpur-Striebel formula [30].

In decentralized stochastic control this method has allowed for rather mild
existence and dynamic programming results [42, 41, 44, 23] and approximation
results [36]. We also refer the reader to [12] for relations with classical
continuous-time stochastic control where the relation with Girsanov’s
classical measure transformation [22], [4] is recognized.

The common thread for the above change of measure arguments is an absolute
continuity condition involving a family of conditional probabilities on the
measurement variables (given the past history or state realizations) with
respect to a common reference measure.

For many applications, this is not applicable a priori. In particular, if the
measurements are deterministically related to the history of actions and
states, such a condition does not apply.

In this paper, we focus on the sequential discrete-time (possibly
decentralized) setup and answer the following question: Can we perturb any
discrete-time sequential (single-agent or decentralized multi-agent)
stochastic control problem by adding some arbitrarily small additive (e.g.
Gaussian or otherwise) noise to the measurements to make the measurement
kernels absolutely continuous with respect to a fixed reference measure, so
that a change-of-measure (also known as a static reduction) can be made with
arbitrarily small error in the optimal cost? That is, are all sequential
stochastic problems $\epsilon$-away from being static reducible as far as
optimal cost is concerned, for any $\epsilon>0$? We show that this is possible
when the cost function is bounded and continuous in agents’ actions and the
action spaces are convex.

We note that such a result is not direct and is in fact surprising given the
general lack of continuity in the space of information structures under weak
convergence (which is indeed the notion considered in our positive result when
we will, under weak convergence, approach a dirac delta measure by a sequence
of Gaussian measures with decreasing variances): [43, Section 3.1.1] shows
that the optimal cost in partially observable stochastic control is not weakly
continuous (though upper semi-continuous) on the space of measurement channels
in general, and in fact this negative result also applies to setwise
perturbations of measurement channels [43, Section 3.2.1] even when the costs
considered are bounded continuous and all spaces considered are compact (see
also [27, Section 4]). To obtain our positive result in this paper, we will
consider a cautious construction where Lusin’s theorem will be utilized twice,
first to approximate functions and second to approximate stochastic kernels
with their continuous and weakly continuous counterparts, respectively.

We finally note that there exist two lines of relevant studies on this general
subject in the stochastic control literature in both discrete-time and
continuous-time, for classical fully observed or partially observed systems
and often under stringent conditions. One line of work [25, 2, 3, 24, 29, 32,
33] studies small-noise limits of stochastic systems (more commonly in the
fully observed setup) where large-deviations theoretic results are obtained,
which often apriori require stringent regularity or smoothness properties on
system (or measurement) dynamics to facilitate such analysis. While our
results do not give rates of convergence, our results do not require even
continuity of the kernels in the state or actions.

A second line of research involves vanishing perturbation or vanishing
viscosity solutions. For fully observed or partially observed controlled
diffusions (or deterministic optimal control) non-degenerate diffusions
facilitate powerful stochastic analysis methods (such as convexification,
compactification, closedness under weak convergence etc.), and therefore it is
a natural question to see what happens when one perturbs an original
degenerate system with additive noise, leading to a vanishing viscosity
solution [19, 30, 20] for the limit as the noise vanishes (see e.g. [1,
Chapter 7] for non-degenerate partially observed diffusion problems where
relations with viscosity solutions are emphasized). Related studies, under
strong regularity conditions or specific models, include [19], [13] and [6].
Our paper is different in two directions: (i) For such methods often one needs
tightness and closedness (under weak topology) conditions on the sets of
strategic measures to extract a converging subsequence as the perturbation
coefficient vanishes; this is often too much to ask for decentralized
stochastic control (see e.g. [41, Theorem 5.5]) since conditional independence
properties are not closed under weak convergence [44, Theorem 2.7]. (ii) Even
when the information structure is classical (i.e., information is expanding
with perfect recall), which is the case in fully observed or partially
observed single-agent setups, weak continuity of the transition kernel is
needed for the closedness of strategic measures under weak convergence [37].

In our paper, these conditions may not be applicable and are not needed.

##  2 Sequential Stochastic Control: Witsenhausen’s Intrinsic Model

In the following, we present the general (possibly decentralized) discrete-
time setup, as well as some further characterizations as laid out by
Witsenhausen, termed as the Intrinsic Model [39]. In this model, any action
applied at any given time is regarded as applied by an individual decision
maker (DM), who acts only once. One advantage of this model, in addition to
its generality, is that the definitions regarding information structures can
be compactly described.

Suppose that in a stochastic control system considered below, there is a pre-
defined order in which the decision makers act. Such systems are called
sequential stochastic control systems or sequential teams. In the context of a
sequential team, the Intrinsic Model has three components:

  * •

A collection of measurable spaces $\\{(\Omega,{\cal F}),(\mathbb{U}^{i},{\cal
U}^{i}),(\mathbb{Y}^{i},{\cal Y}^{i}),i\in{\cal N}\\}$, with ${\cal
N}:=\\{1,2,\cdots,N\\}$, specifying the system’s distinguishable events, and
the control and measurement spaces. Here $N=|{\cal N}|$ is the number of
control actions taken, and each of these actions is taken by an individual
(different) DM (hence, even a DM with perfect recall can be regarded as a
separate decision maker every time it acts). The pair $(\Omega,{\cal F})$ is a
measurable space (on which an underlying probability may be defined). The pair
$(\mathbb{U}^{i},{\cal U}^{i})$ denotes the measurable space from which the
action, $u^{i}$, of decision maker $i$ is selected. The pair
$(\mathbb{Y}^{i},{\cal Y}^{i})$ denotes the measurable observation/measurement
space for DM$i$.

  * •

A measurement constraint which establishes the connection between the
observation variables and the system’s distinguishable events. The
$\mathbb{Y}^{i}$-valued observation variables are given by
$y^{i}=\eta^{i}(\omega,{\bf u}^{[1,i-1]})$, ${\bf u}^{[1,i-1]}=\\{u^{k},k\leq
i-1\\}$, $\eta^{i}$ measurable functions and $u^{k}$ denotes the action of
DM$k$. Hence, the information variable $y^{i}$ induces a $\sigma$-field,
$\sigma({\cal I}^{i})$ over $\Omega\times\prod_{k=1}^{i-1}\mathbb{U}^{k}$

  * •

A design constraint which restricts the set of admissible $N$-tuple control
laws $\underline{\gamma}=\\{\gamma^{1},\gamma^{2},\dots,\gamma^{N}\\}$, also
called designs or policies, to the set of all measurable control functions, so
that $u^{i}=\gamma^{i}(y^{i})$, with $y^{i}=\eta^{i}(\omega,{\bf
u}^{[1,i-1]})$, and $\gamma^{i},\eta^{i}$ measurable functions. Let
$\Gamma^{i}$ denote the set of all admissible policies for DM$i$ and let
${\bf\Gamma}=\prod_{k}\Gamma^{k}$. In our setup, we will also allow for
randomized policies, with independent randomizations, for each DM.

We also introduce a fourth ingredient:

  * •

A probability measure $P$ defined on $(\Omega,{\cal F})$ which describes the
measures on the random events in the model.

Under the setup for this paper, we will assume
$\mathbb{Y}^{i}\subset\mathbb{R}^{k_{i}}$, for some $k_{i}\in\mathbb{Z}_{\geq
1}$, for every $i\in\mathcal{N}$, and we will require admissible policies be
defined from $\mathbb{R}^{k_{i}}$ to $\mathbb{U}^{i}$. All spaces are assumed
to be Borel.

We note that the intrinsic model of Witsenhausen as defined in [39] provides a
set-theoretic characterization of information fields; however, for standard
Borel spaces, the model above is equivalent to that of Witsenhausen’s. We will
utilize this functional representation in our analysis to follow. We also note
that Witsenhausen has shown that the intrinsic model can be written as a
special case of an equivalent model (also due to Witsenhausen [40]), which has
a similar structure as the one above (with functional descriptions on the
measurement variables) with only some slight differences.

Under this intrinsic model, (the information structure of) a sequential
stochastic control (or team) problem is dynamic if the information available
to at least one DM is affected by the action of at least one other DM. A
decentralized problem is static if the information available at every decision
maker is only affected by exogenous disturbances (Nature)
$\omega_{0}\in\Omega_{0}$; that is no decision maker can affect the
information for another decision maker.

Information structures can also be classified as classical, quasi-classical or
nonclassical. An Information Structure (IS) $\\{y^{i},1\leq i\leq N\\}$ is
classical if $y^{i}$ contains all of the information available to DM$k$ for
$k<i$. An IS is quasi-classical or partially nested, if whenever $u^{k}$, for
some $k<i$, affects $y^{i}$ through the measurement function $\eta^{i}$,
$y^{i}$ contains $y^{k}$ (that is $\sigma(y^{k})\subset\sigma(y^{i})$). An IS
which is not partially nested is nonclassical.

Classical stochastic control problems (where a single controller acts
repeatedly over time with increasing information), i.e., those that are
usually known as MDPs (Markov Decision Processes) or POMDPs (Partially
Observed Markov Decision Processes), are easily seen to fit in this general
formulation: these are classical according to the classification presented
above.

Now, consider the team policy

$\underline{\gamma}=\\{\gamma^{1},\cdots,\gamma^{N}\\}$

and let a cost function be defined as:

$\displaystyle J(\underline{\gamma})=E^{\underline{\gamma}}[c(\omega_{0},{\bf
u})]=E[c(\omega_{0},\gamma^{1}(y^{1}),\cdots,\gamma^{N}(y^{N}))],$ (1)

for some non-negative measurable loss (or cost) function
$c:\Omega_{0}\times\prod_{k}\mathbb{U}^{k}\to\mathbb{R}_{+}$. Here, we have
the notation ${\bf u}=\\{u^{t},t\in{\cal N}\\}$, and $\omega_{0}$ may be
viewed as the cost function relevant exogenous variable contained in $\omega$.

######  Definition 1.

For a given sequential stochastic team problem with a given information
structure, $\\{J;\Gamma^{i},i\in{\cal N}\\}$, a policy (strategy) $N$-tuple
${\underline{\gamma}}^{*}:=({\gamma^{1}}^{*},\ldots,{\gamma^{N}}^{*})\in{\bf\Gamma}$
is an optimal team policy if

$J({\underline{\gamma}}^{*})=\inf_{{{\underline{\gamma}}}\in{{\bf\Gamma}}}J({{\underline{\gamma}}})=:J^{*}.$
(2)

The expected cost achieved by this strategy, $J^{*}$, is the optimal cost.

In the following, we will denote by bold letters the ensemble of random
variables across the DMs; that is ${\bf y}=\\{y^{i},i=1,\cdots,N\\}$ and ${\bf
u}=\\{u^{i},i=1,\cdots,N\\}$.

###  2.1 Static Reduction of Stochastic Dynamic Problems via Change of
Measures

Following Witsenhausen [40, Eqn (4.2)], as reviewed in [42, Section 3.7], we
say that two information structures are equivalent if: (i) The policy spaces
are equivalent/isomorphic in the sense that policies under one information
structure are realizable under the other information structure, (ii) the costs
achieved under equivalent policies are identical almost surely, and (iii) if
there are constraints in the admissible policies, the isomorphism among the
policy spaces preserves the constraint conditions.

A large class of sequential stochastic control or team problems admit an
equivalent information structure which is static. This is called the static
reduction of a dynamic team problem.

For the results to be presented, under a static reduction, we will have
individual measurement variables be independent of each other as well as
$\omega_{0}$. Witsenhausen refers to such an information structure as
independent static in [40, Section 2.4(e)]. This is not possible in general
for every sequential problem which admits a static reduction, for example
quasi-classical team problems with linear models [26] do not admit such a
further reduction, since the measurements are partially nested.

Consider (a static or a dynamic) team setting according to the intrinsic model
where each DM$i$ measures $y^{i}$ We will, for every $1\leq n\leq N$, view the
relation

$\displaystyle
P(dy^{n}|\omega_{0},y^{1},y^{2},\cdots,y^{n-1},u^{1},u^{2},\cdots,u^{n-1}),$
(3)

as a (controlled) stochastic kernel (to be defined later), and through
standard stochastic realization results (see [21, Lemma 1.2] or [9, Lemma
3.1]), we can represent this kernel in a functional form through

$\displaystyle
y^{n}=g_{n}(\omega_{0},\nu,y^{1},y^{2},\cdots,y^{n-1},u^{1},u^{2},\cdots,u^{n-1})$
(4)

for some independent $[0,1]$-valued $\nu$ and measurable $g_{n}$.

This team admits an independent-measurements reduction provided that the
following absolute continuity condition holds: For every $t\in{\cal N}$, there
exists a reference probability measure $Q_{t}$ and a function $f_{t}$ such
that for all Borel $S$:

$\displaystyle P(y^{t}\in
S|\omega_{0},u^{1},u^{2},\cdots,u^{t-1},y^{1},y^{2},\cdots,y^{t-1})$
$\displaystyle\quad\quad=\int_{S}f_{t}(y^{t},\omega_{0},u^{1},u^{2},\cdots,u^{t-1},y^{1},y^{2},\cdots,y^{t-1})Q_{t}(dy^{t}),$
(5)

We can then write (since the action of each DM is determined by the
measurement variables under a given policy)

$\displaystyle P(d\omega_{0},d{\bf y},d{\bf u})$
$\displaystyle=P(d\omega_{0})\prod_{t=1}^{N}\bigg{(}f_{t}(y^{t},\omega_{0},u^{1},u^{2},\cdots,u^{t-1},y^{1},y^{2},\cdots,y^{t-1})Q_{t}(dy^{t})1_{\\{\gamma^{t}(y^{t})\in
du^{t}\\}}\bigg{)}.$

The cost function $J(\underline{\gamma})$ can then be written as

$\displaystyle J(\underline{\gamma})$ $\displaystyle=\int
P(d\omega_{0})\prod_{t=1}^{N}(f_{t}(y^{t},\omega_{0},u^{1},u^{2},\cdots,u^{t-1},y^{1},y^{2},\cdots,y^{t-1})Q_{t}(dy^{t}))c(\omega_{0},{\bf
u})$ (6)

with $u^{k}=\gamma^{k}(y^{k})$ for $1\leq k\leq N$, and where now the
measurement variables can be regarded as independent from each other, and also
from $\omega_{0}$, and by incorporating the $\\{f_{t}\\}$ terms into $c$, we
can obtain an equivalent static team problem. Hence, the essential step is to
appropriately adjust the probability space and the cost function.

######  Remark 2.1 (Change of Measure Formula).

Denote the joint probability measure on
$(\omega_{0},u^{1},\dots,u^{N},y^{1},\dots,y^{N})$ by $P$, and the probability
measure of $\omega_{0}$ by $\mathbb{P}^{0}$. If the preceding absolute
continuity condition (2.1) holds, then (under any admissible policy profile
$\gamma^{1},\cdots,\gamma^{N}$) there exists a joint reference probability
measure ${\mathbb{Q}}$ on $(\omega_{0},u^{1},\dots,u^{N},y^{1},\dots,y^{N})$
such that the probability measure $P$ is absolutely continuous with respect to
${\mathbb{Q}}$ ($P\ll{\mathbb{Q}}$), so that for every Borel set $A$ in
$(\Omega_{0}\times\prod_{i=1}^{N}(\mathbb{U}^{i}\times\mathbb{Y}^{i}))$

$\displaystyle
P(A)=\int_{A}\frac{dP}{d{\mathbb{Q}}}\mathbb{Q}(d\omega_{0},du^{1},\dots,du^{N},dy^{1},\dots,dy^{N}),$
(7)

where the reference probability measure

$\displaystyle\mathbb{Q}(d\omega_{0},du^{1},\dots,du^{N},dy^{1},\dots,dy^{N}):=\mathbb{P}^{0}(d\omega_{0})\prod_{i=1}^{N}Q^{i}(dy^{i})1_{\\{\gamma^{i}(y^{i})\in
du^{i}\\}},$ (8)

leads to a Radon-Nikodym derivative:

$\displaystyle\frac{dP}{d\mathbb{Q}}(\omega_{0},u^{1},\dots,u^{1},y^{1}\dots,y^{N})=\prod_{i=1}^{N}f^{i}(y^{i},\omega_{0},u^{1},\dots,u^{i-1},y^{1},\dots,y^{i-1}).$
(9)

The new cost function may now explicitly depend on the measurement values,
such that

$\displaystyle c_{s}(\omega_{0},{\bf y},{\bf u})=c(\omega_{0},{\bf
u})\prod_{i=1}^{N}f_{i}(y^{i},\omega_{0},u^{1},u^{2},\cdots,u^{i-1},y^{1},y^{2},\cdots,y^{i-1}).$
(10)

Here we can reformulate even a static team to one which is, clearly still
static, but now with independent measurements which are also independent from
the cost relevant exogenous variable $\omega_{0}$.

As a common example, consider the additive noise measurement model, for some
$f$,

$y^{1}=f(x)+w,$

with $w$ a noise variable which admits a probability density function $\eta$
(not necessarily positive everywhere). Then, for any Borel $B$

$P(y^{1}\in
B|x)=\int\eta(y^{1}-f(x))dy^{1}=\int\frac{\eta(y^{1}-f(x))}{\kappa(y^{1})}\kappa(y^{1})dy^{1}$

for any $\kappa$ which is a probability density function that is positive
everywhere (such as the Gaussian). Thus, the measurement variable can be
assumed to be $y^{1}\sim\int_{\cdot}\kappa(y)dy$ which is independent of $x$
and has a measure that admits a probability density function $\kappa$. Note
that here one or both of $\eta$ and $\kappa$ can be Gaussian as an important
special case.

This fact will be used for the main results of this paper. Since adding
Gaussian noise to each DM’s measurement will ensure the model satisfies the
absolute continuity condition (4), if we can show that the optimal expected
cost under a setup where each DM receives a measurement corrupted by an
additive Gaussian noise channel (with zero mean) converges to the expected
cost under the DMs’ original channels as the variance of the noise goes to
zero, then (4) can be satisfied while only altering the optimal expected cost
by an arbitrarily small amount.

##  3 Sequential stochastic control problems are nearly static reducible

###  3.1 Assumptions and supporting results

Recall from (3) and the preceding discussion that in a dynamic team setup the
probability measure on the measurements ${\bf y}$ is not fixed as opposed to
the static case. Let, for all $n\in{\cal N}$,

$h_{n}=\\{\omega_{0},y^{1},u^{1},\cdots,y^{n-1},u^{n-1},y^{n},u^{n}\\},$

and $p^{n}(dy^{n}|h_{n-1}):=P(dy^{n}|h_{n-1})$ be the transition kernel
characterizing the measurements of DM $n$ according to the intrinsic model. We
note that this may be obtained by the relation:

$\displaystyle
p^{n}(y^{n}\in\cdot|\,\omega_{0},y^{1},u^{1},\cdots,y^{n-1},u^{n-1})$
$\displaystyle\,:=P\bigg{(}\eta^{n}(\omega,{\bf
u}^{[1,n-1]})\in\cdot\bigg{|}\,\omega_{0},y^{1},u^{1},\cdots,y^{n-1},u^{n-1}\bigg{)}$
(11)

We will allow for an agent’s measurements through their channel $p^{i}$ to be
garbled by an additive Gaussian noise channel $\tau^{i}_{m}$, which provides
the DM with measurement $z^{i}=y^{i}+q^{i}_{m}$, where
$q^{i}_{m}\in\mathbb{R}^{k_{i}}$ is a vector of independent identically
distributed $\mathbb{R}$-valued Gaussian noise with mean $0$ and variance
$1/m$. This is the measurement that the DM then uses when selecting their
action $u^{i}=\gamma^{i}(z^{i})$ and becomes the measurement that can affect
future DMs’ measurements through their channels $p^{i+1},\dots,p^{N}$. We
denote the DM channels under the garbled setup by
$p^{1}\tau^{1}_{m},\dots,p^{N}\tau^{N}_{m}$. We denote the team-optimal cost
(i.e. the expected cost achieved under optimal selection of DM policies) under
this setup with $J^{*}(P,p^{1}\tau^{1}_{m},\dots,p^{N}\tau^{N}_{m})$, and the
team-optimal cost under the original setup with $J^{*}(P,p^{1},\dots,p^{N})$.

We now introduce the following assumptions (where only A1 and A2 will be
needed for our main result):

  * (A1)

The cost function $c$ is continuous and bounded.

  * (A2)

Each DM$i$’s action space $\mathbb{U}^{i}$ is a convex subsets of
$\mathbb{R}^{n_{i}}$, for some $n_{i}\in\mathbb{Z}_{\geq 1}$.

  * (A3)

Each DM$i$’s measurement channel given in (11) is weakly continuous in the
following sense: if
$(z^{1}_{m},u^{1}_{m},\dots,z^{i-1}_{m},u^{i-1}_{m})\rightarrow(z^{1},u^{1},\dots,z^{i-1},u^{i-1})$,
then

$p^{i}(y^{i}\in\cdot|\omega_{0},z^{1}_{m},u^{1}_{m},\dots,z^{i-1}_{m},u^{i-1}_{m})\rightarrow
p^{i}(y^{i}\in\cdot|\omega_{0},z^{1},u^{1},\dots,z^{i-1},u^{i-1})$

weakly for all $\omega_{0}\in\Omega_{0}$.

For example, through the stochastic realization functional form (4) with
$y^{n}=g_{n}(\omega_{0},\nu,z^{1},z^{2},\cdots,z^{n-1},u^{1},u^{2},\cdots,u^{n-1})$
for some independent $\nu$ and measurable $g_{n}$, we have that if

$g_{n}(\omega_{0},\nu,\cdot):(z^{1},u^{1},\dots,z^{n-1},u^{n-1})\mapsto y^{n}$

is continuous, then the kernel would satisfy A3.

We will show that under assumption A1 and A2

$\lim_{m\rightarrow\infty}J^{*}(P,p^{1}\tau^{1}_{m},\dots,p^{N}\tau^{N}_{m})=J^{*}(P,p^{1},\dots,p^{N}).$

From this, it follows that any sequential dynamic team problem is
$\epsilon$-away in optimal cost from being static reducible.

First, a result will be stated and proved under the additional assumption A3,
in Theorem 5. Then, this result will be relaxed to include measurement
channels that do not necessarily satisfy A3 in Theorem 6, which is the main
theorem of our paper.

The proof will first use Lusin’s theorem to construct continuous policies for
each DM that approximate their equilibrium policies on a set of
$1-\epsilon_{i}$, for any $\epsilon_{i}>0$. Then, it will be shown using a
generalized dominated convergence theorem that the garbled information
structure converges weakly to the ungarbled information structure. These steps
will then be combined to prove the desired statement. The relaxation in
Theorem 6 will use Lusin’s theorem an additional time to show that each
agent’s channel can be approximated by a channel that satisfies A3 on a set of
measure $1-\beta_{i}$, for any $\beta_{i}>0$.

Our approach is related to perturbing information structures under the weak
convergence topology. This problem was studied in [43] with negative results
presented showing that the optimal cost is not in general weakly continuous on
the space of channels. In the following, however, by restricting the nature of
allowable perturbations, we will establish a positive result on continuity.

First we will require an extension of the forward direction to Blackwell’s
ordering of information structures [8] to sequential dynamic teams in standard
Borel spaces (see also [42, Theorem 4.3.3]).

######  Lemma 2.

For sequential dynamic team problems, if each agent’s information under a set
of measurement channels $(p^{1},\dots,p^{N})$ is a garbling of their
information under another set of measurement channels
$(\tilde{p}_{1},\dots,\tilde{p}_{N})$ then the team-optimal cost cannot be
strictly lower under $(p^{1},\dots,p^{N})$ than under
$(\tilde{p}_{1},\dots,\tilde{p}_{N})$.

By garblings, we mean that each agent’s measurements under
$(p^{1},\dots,p^{N})$ are such that
$y^{i}_{p^{i}}=g^{i}(y^{i}_{\tilde{p}_{i}},\nu_{i})$ for some measurable
$g^{i}$ and independent noise $\nu_{i}$, for all $i\in\mathcal{N}$, where
$y^{i}_{\tilde{p}_{i}}$ is the measurement under the original channel
$\tilde{p}_{i}$.

###### Proof.

of Lemma 2 We observe that any outcome for a sequential stochastic problem
achievable under $(p^{1},\dots,p^{N})$ is also achievable under
$(\tilde{p}_{1},\dots,\tilde{p}_{N})$, since outcomes are determined by
policies, which are measurable functions from measurements to actions, and the
measurements under $(p^{1},\dots,p^{N})$ can be simulated using the
measurements from $(\tilde{p}_{1},\dots,\tilde{p}_{N})$ and the independent
noise variables $\nu_{i}$, and thus the resulting expected outcomes can also
be achieved under $(\tilde{p}_{1},\dots,\tilde{p}_{N})$. For instance, if
$\gamma^{1,*},\dots,\gamma^{N,*}$ form a $\delta$-optimal policy (i.e. are
within $\delta>0$ of minimizing the expected cost) under channels
$({p^{1}},\dots,p^{n})$, then this team policy under the channels
$(\tilde{p}^{1},\dots,\tilde{p}^{N})$ can be simulated by selecting actions
using the (randomized) policies
$u^{i}=\gamma^{i,*}(g^{i}(y^{i}_{\tilde{p}^{i}},\nu_{i}))$, for all
$i\in\mathcal{N}$, achieving the same expected cost. $\diamond$

We now recall Lusin’s theorem, which will be used throughout the proof of the
main theorems.

######  Theorem 3.

[16, Theorem 7.5.2][Lusin’s Theorem] Let $(\mathbb{X},T)$ be any topological
space and $\mu$ a finite, closed regular Borel measure on $\mathbb{X}$. Let
$(\mathbb{S},d)$ be a separable metric space and let $f$ be a Borel-measurable
function from $\mathbb{X}$ into $\mathbb{S}$. Then for any $\epsilon>0$ there
is a closed set $F\subset\mathbb{X}$ such that $\mu(\mathbb{X}\setminus
F)<\epsilon$ and the restriction of $f$ to $F$ is continuous.

Finally we recall Tietze’s extension theorem, which will be used in
conjunction with Lusin’s theorem in the proofs. This will be used to construct
a continuous extension of the continuous function defined on $F$ in Theorem 3
to $\mathbb{X}$. Note that we consider a general space setup in the following;
this is needed as we will study stochastic kernels as probability measure-
valued maps.

######  Theorem 4.

[17, Theorem 4.1][Dugundji] Let $\mathbb{X}$ be an arbitrary metric space, $A$
a closed subset of $\mathbb{X}$, $L$ a locally convex linear space, and
$f:A\rightarrow L$ a continuous map. Then there exists a continuous function
$f_{C}:\mathbb{X}\rightarrow L$ such that $f_{C}(a)=f(a)\>\forall a\in A$.
Furthermore, the image of $f_{C}$ satisfies $f_{C}(\mathbb{X})\subset$
$[$convex hull of $f(A)]$.

###  3.2 Weakly Continuous Measurement Kernels

Now we present the main result of this section, which will be further
generalized in the main result of our paper, Theorem 6, to be presented in the
next section.

######  Theorem 5.

Assume assumptions A1, A2, and A3 hold. For any $\epsilon>0$, any sequential
dynamic team problem is $\epsilon$-away in optimal cost from being static
reducible.

###### Proof.

Step 1. Let
$p^{i}(y^{i}\in\cdot|\omega_{0},y^{1},u^{1},\dots,y^{i-1},u^{i-1})$ denote
each respective DM’s measurement channel for $i\in\mathcal{N}$. Let
$\tau^{1}_{m},\dots,\tau^{N}_{m}$ be independent additive Gaussian noise
channels with variance $1/m$ and mean $0$ for each DM. We will use $y^{i}$ to
denote the measurement by agent $i$ through channel $p^{i}$, and $z^{i}$ to
denote the corrupted measurement of $y^{i}$ through additive Gaussian noise
channel $\tau^{i}_{m}$.

Let $\bar{\gamma}^{*}=(\gamma^{1,*},\dots,\gamma^{N,*})$ be a $\delta$-team-
optimal policy (where $\delta>0$ is arbitrary) given cost function $c$ _when
the Gaussian noise channels are not used_. I.e. $\bar{\gamma}^{*}$ is a policy
that achieves a cost of $J^{*}(P,p^{1},\dots,p^{N})+\delta$, or lower. Let
$\mu$ denote the joint probability measure on
$\Omega_{0}\times\mathbb{Y}^{1}\times\dots\mathbb{Y}^{N}$ when the DMs use
channels $p^{1},\dots,p^{n}$, and $\nu_{m}$ denote the measure on
$(\Omega_{0}\times\mathbb{Y}^{1}\times\mathbb{R}^{k_{1}}\times\dots\mathbb{Y}^{N}\times\mathbb{R}^{k_{N}})$
when the DMs use channels $p^{1}\tau^{1}_{m},\dots,p^{N}\tau^{N}_{m}$.

We will now apply Lusin’s theorem (Theorem 3) for each decision maker to allow
for the restriction of each DM’s policy $\gamma^{i,*}$ to be continuous on a
subset of $\mathbb{Y}^{i}$ of arbitrarily large marginal measure under policy
$\bar{\gamma}^{*}$.

There is now the question of whether changing the policy affects the marginal
on the measurements. This will be handled via a total probability argument:
For each decision maker, we will fix all prior DM’s policies as their personal
policy from the $\delta$-team-optimal strategy $\bar{\gamma}^{*}$, while all
future DMs’ policies can be left as arbitrary measurable functions. We require
all prior DMs’ policies to be fixed in order to fix the measure on DM$i$’s
measurement space $\mathbb{Y}^{i}$, since DM$i$’s measurement may depend on
previous DMs’ actions (and thus policies). Future DMs’ policies are irrelevant
to the application of Lusin’s theorem, as the theorem guarantees that the
marginal on the subset of $\mathbb{Y}^{i}$ where $\gamma^{i,*}$ is not
continuous is small, which is unaffected by future DMs’ measures on their
measurement spaces.

For the first DM, by Lusin’s theorem, there exists a set $A^{1}$ such that
$\gamma^{1,*}$ is continuous on $(\mathbb{Y}^{1}\setminus A^{1})$ and

$\int_{\Omega_{0}\times
A^{1}\times\mathbb{Y}^{2}\times\dots\times\mathbb{Y}^{N}}P(d\omega_{0})p^{1}(dy^{1}|\omega_{0})p^{2}(dy^{2}|\omega_{0},y^{1},f^{1}(y^{1}))\dots{\\\
}p^{N}(dy^{N}|\omega_{0},y^{1},f^{1}(y^{1}),\dots,y^{N-1},f^{N-1}(y^{N-1}))<\epsilon_{1},$
(12)

for any measurable $f^{1},\dots,f^{N-1}$.

For the second DM, for $\epsilon_{2}>0$, given fixed policy $\gamma^{1,*}$ for
DM 1, there exists a set $A^{2}$ such that $\gamma^{2,*}$ is continuous on
$(\mathbb{Y}^{2}\setminus A^{2})$ and

$\int_{\Omega_{0}\times\mathbb{Y}^{1}\times
A^{2}\times\mathbb{Y}^{3}\times\dots\times\mathbb{Y}^{N}}P(d\omega_{0})p^{1}(dy^{1}|\omega_{0})p^{2}(dy^{2}|\omega_{0},y^{1},\gamma^{1,*}(y^{1}))\dots{\\\
}p^{N}(dy^{N}|\omega_{0},y^{1},\gamma^{1,*}(y^{1}),y^{2},f^{2}(y^{2}),\dots,y^{N-1},f^{N-1}(y^{N-1}))<\epsilon_{2},$
(13)

for any measurable $f^{2},\dots,f^{N-1}$.

Continuing in this way, for the $N$th DM, for $\epsilon_{N}>0$, given fixed
$\gamma^{1,*},\dots,\gamma^{N-1,*}$, there exists a set $A^{N}$ such that
$\gamma^{N,*}$ is continuous on $(\mathbb{Y}^{N}\setminus A^{N})$ and

$\int_{\Omega_{0}\times\mathbb{Y}^{1}\times\dots\times\mathbb{Y}^{N-1}\times
A^{N}}P(d\omega_{0})p^{1}(dy^{1}|\omega_{0})p^{2}(dy^{2}|\omega_{0},y^{1},\gamma^{1,*}(y^{1}))\dots{\\\
}p^{N}(dy^{N}|\omega_{0},y^{1},\gamma^{1,*}(y^{1}),\dots,y^{N-1},\gamma^{N-1,*}(y^{N-1}))<\epsilon_{N}.$
(14)

Furthermore, following Tietze’s extension theorem, Theorem 4, it follows that
there exist continuous policies $\gamma^{1}_{C},\dots,\gamma^{N}_{C}$, such
that $\gamma^{i}_{C}(x)=\gamma^{i,*}(x),\>\forall x\in(\mathbb{Y}^{i}\setminus
A^{i})$ for each $i\in\\{1,\cdots,N\\}$.

Step 2. Define the following terms:

$h_{i}:=(\omega_{0},y^{1},\gamma^{1,*}(y^{1}),\dots,y^{i-1},\gamma^{i-1,*}(y^{i-1})),$
where $h_{1}=(\omega_{0}).$

$r_{i}:=(\omega_{0},z^{1},\gamma^{1,*}(z^{1}),\dots,z^{i-1},\gamma^{i-1,*}(z^{i-1})),$
where $r_{1}=(\omega_{0}).$

We now note the following, for any fixed $y^{1},\omega_{0}$:

$\displaystyle\lim_{m\rightarrow\infty}\int\tau^{1}_{m}(dz^{1}|y^{1})p^{2}(dy^{2}|r_{2})\dots
p^{N}(dy^{N}|r_{N})\tau^{N}_{m}(dz^{N}|y^{N})c(\omega_{0},\gamma^{1}_{C}(z^{1}),\dots,\gamma^{N}_{C}(z^{N}))$
$\displaystyle=\lim_{m\rightarrow\infty}\int\tau^{1}_{m}(dz^{1}|y^{1})p^{2}(dy^{2}|r_{2})\dots
p^{N}(dy^{N}|r_{N})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\times\int\tau^{N}_{m}(dz^{N}|y^{N})c(\omega_{0},\gamma^{1}_{C}(z^{1}),\dots,\gamma^{N}_{C}(z^{N}))$

Letting
$G^{N}_{m}(y^{N},z^{N-1},\dots,z^{1}):=\int\tau^{N}_{m}(dz^{N}|y^{N})c(\omega_{0},\gamma^{1}_{C}(z^{1}),\dots,\gamma^{N}_{C}(z^{N}))$
(recalling that $\omega_{0}$ is fixed), we can observe that $G^{N}_{m}$ is a
sequence of real-valued and bounded functions, and that if
$(y^{N}_{m},z^{N-1}_{m},\dots,z^{1}_{m})\rightarrow(y^{N},z^{N-1},\dots,z^{1})$,
then

$G^{N}_{m}(y^{N}_{m},z^{N-1}_{m},\dots,z^{1}_{m})\rightarrow
c(\omega_{0},\gamma^{1}_{C}(z^{1}),\dots,\gamma^{N-1}_{C}(z^{N-1}),\gamma^{N}_{C}(y^{N})),$

i.e. $G^{N}_{m}$ continuously converges (as it is defined in [38]) to

$G^{N}(y^{N},z^{N-1},\dots,z^{1}):=c(\omega_{0},\gamma^{1}_{C}(z^{1}),\dots,\gamma^{N-1}_{C}(z^{N-1}),\gamma^{N}_{C}(y^{N})).$

The important aspect is that the measurement $z^{N}$ is now replaced by
$y^{N}$ in the cost function. This follows from the fact that
$\tau^{N}_{m}(\cdot|y^{N})$ converges weakly to the dirac-delta measure at
$y^{N}$ (see e.g. [28, Example 12.21] for a related argument) and that the
DMs’ policies are continuous and the cost function is continuous and bounded.
Continuing, we have:

$\displaystyle\lim_{m\rightarrow\infty}\int\tau^{1}_{m}(dz^{1}|y^{1})p^{2}(dy^{2}|r_{2})\dots
p^{N}(dy^{N}|r_{N})\tau^{N}_{m}(dz^{N}|y^{N})c(\omega_{0},\gamma^{1}_{C}(z^{1}),\dots,\gamma^{N}_{C}(z^{N}))$
$\displaystyle=\lim_{m\rightarrow\infty}\int\tau^{1}_{m}(dz^{1}|y^{1})p^{2}(dy^{2}|r_{2})\dots\tau^{N-1}_{m}(dz^{N-1}|y^{N-1})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\times\int
p^{N}(dy^{N}|r_{N})G^{N}_{m}(y^{N},z^{N-1},\dots,z^{1}).$

Let $H^{N}_{m}(z^{N-1},\dots,z^{1}):=\int
p^{N}(dy^{N}|r_{N})G^{N}_{m}(y^{N},z^{N-1},\dots,z^{1})$. We can observe that,
since $G^{N}_{m}$ is a sequence of real-valued and bounded functions,
$H^{N}_{m}$ is also such a sequence. Furthermore, if
$(z^{N-1}_{m},\dots,z^{1}_{m})\rightarrow(z^{N-1},\dots,z^{1})$, then
$H^{N}_{m}(z^{N-1}_{m},\dots,z^{1}_{m})$ continuously converges to
$H^{N}(z^{N-1},\dots,z^{1}):=\int
p^{N}(dy^{N}|r_{N})G^{N}(y^{N},z^{N-1},\dots,z^{1})$ by the weak continuity
assumption on the channel $p^{N}$ and the continuity of $c$ (and thus
$G^{N}_{m}$).

Continuing in this way, for decreasing $i$, we iteratively define $G^{i}_{m}$
for $i\in\\{1,\dots,N-1\\}$ as

$G^{i}_{m}(y^{i},z^{i-1},\dots,z^{1}):=\int\tau^{i}_{m}(dz^{i}|y^{i})H^{i-1}_{m}(z^{i-1},\dots,z^{1})$

and $H^{i}_{m}$ for $i\in\\{1,\dots,N-1\\}$ as

$H^{i}_{m}(z^{i-1},\dots,z^{1}):=\int
p^{i}(dy^{i}|r_{i})G^{i}_{m}(y^{i}_{m},z^{i}_{m},\dots,z^{1}_{m}).$

We note that each of these functions are real-valued and bounded, and will
continuously converge. In particular,

$\displaystyle G^{i}_{m}(y^{i},z^{i-1},\dots,z^{1})$
$\displaystyle\rightarrow\int\left(\prod_{j=i}^{N-1}p^{j}(dy^{j}|h_{j})\right)c(\omega_{0},\gamma^{1}_{C}(z^{1}),\dots,\gamma^{i-1}_{C}(z^{i-1}),\gamma^{i}_{C}(y^{i}),\dots,\gamma^{N}_{C}(y^{N})),$

and each $H^{i}_{m}$ will converge to $\int
p^{i}(dy^{i}|r_{i})G^{i}(y^{i},z^{i-1},\dots,z^{1})$.

Thus, eventually we arrive at:

$\displaystyle\lim_{m\rightarrow\infty}\int\tau^{1}_{m}(dz^{1}|y^{1})p^{2}(dy^{2}|r_{2})\dots
p^{N}(dy^{N}|r_{N})\tau^{N}_{m}(dz^{N}|y^{N})c(\omega_{0},\gamma^{1}_{C}(z^{1}),\dots,\gamma^{N}_{C}(z^{N}))$
$\displaystyle=\lim_{m\rightarrow\infty}\int\tau^{1}_{m}(dz^{1}|y^{1})H^{2}_{m}(z^{1}),$

where $H^{2}_{m}$ is a continuously converging sequence of continuous and
bounded real-valued functions.

Thus, since $\tau^{1}_{m}(\cdot|y^{1})$ converges weakly to the dirac-delta
measure at $y^{1}$, applying the Generalized Dominated Convergence Theorem
([38, Theorem 3.5] or [31, Theorem 3.5]), we have that:

$\displaystyle\lim_{m\rightarrow\infty}\int\tau^{1}_{m}(dz^{1}|y^{1})H^{2}_{m}(z^{1})$
$\displaystyle=H^{2}(y^{1})$ $\displaystyle=\int
p^{2}(dy^{2}|h_{2})p^{3}(dy^{3}|h_{3})\dots
p^{N}(dy^{N}|h_{N})c(x,\gamma^{1}_{C}(y^{1}),\dots,\gamma^{N}_{C}(y^{N})).$

Step 3. Now, we can complete the proof:

$\displaystyle\lim_{m\rightarrow\infty}E^{P,p^{1},\dots,p^{N}}_{\tau^{1}_{N},\dots,\tau^{N}_{N}}[c(\omega_{0},\gamma^{1}_{C},\dots,\gamma^{N}_{C})]$
$\displaystyle=\lim_{m\rightarrow\infty}\int
c(\omega_{0},\gamma^{1}_{C}(z^{1}),\dots,\gamma^{N}_{C}(z^{N}))$
$\displaystyle\qquad\qquad\qquad\qquad\times
P(d\omega_{0})p^{1}(dy^{1}|r_{1})\tau^{1}_{m}(dz^{1}|y^{1})\dots
p^{N}(dy^{N}|r_{N})\tau^{N}_{m}(dz^{N}|y^{N})$
$\displaystyle=\lim_{m\rightarrow\infty}\int
P(d\omega_{0})p^{1}(dy^{1}|\omega_{0})\int
c(\omega_{0},\gamma^{1}_{C}(z^{1}),\dots,\gamma^{N}_{C}(z^{N}))\tau^{1}_{m}(dz^{1}|y^{1})$
$\displaystyle\qquad\qquad\qquad\qquad\times
p^{2}(dy^{2}|r_{2})\tau^{2}_{m}(dz^{2}|y^{2})\dots
p^{N}(dy^{N}|r_{N})\tau^{N}_{m}(dz^{N}|y^{N})$ $\displaystyle=\int
c(\omega_{0},\gamma^{1}_{C}(y^{1}),\dots,\gamma^{N}_{C}(y^{N}))P(d\omega_{0})p^{1}(dy^{1}|h_{1})p^{2}(dy^{2}|h_{2})\dots
p^{N}(dy^{N}|h_{N}),$

where the final equality holds by the convergence result from Step 2.
Furthermore, we have that:

$\displaystyle\mu(\Omega_{0}\times(\mathbb{Y}^{1}\setminus
A_{1})\times\dots\times(\mathbb{Y}^{N}\setminus A_{N}))$ $\displaystyle\geq
1-\sum_{i=1}^{N}\mu_{\mathbb{Y}^{i}}(A_{i})$
$\displaystyle=1-\sum_{i=1}^{N}\epsilon_{i}.$

Letting $M:=\|c\|_{\infty}\in\mathbb{R}_{+}$, we have that:

$\displaystyle\int_{\Omega_{0}\times\mathbb{Y}^{1}\times\dots\times\mathbb{Y}^{N}}c(\omega_{0},\gamma^{1}_{C}(y^{1}),\dots,\gamma^{N}_{C}(y^{N}))P(d\omega_{0})p^{1}(dy^{1}|h_{1})p^{2}(dy^{2}|h_{2})\dots
p^{N}(dy^{N}|h_{N})$
$\displaystyle\leq\bigg{(}\int_{\Omega_{0}\times(\mathbb{Y}^{1}\setminus
A_{1})\times\dots\times(\mathbb{Y}^{N}\setminus
A_{N})}c(\omega_{0},\gamma^{1,*}(y^{1}),\dots,\gamma^{n,*}(y^{N}))$
$\displaystyle\qquad\qquad\qquad\qquad\times
P(d\omega_{0})p^{1}(dy^{1}|h_{1})p^{2}(dy^{2}|h_{2})\dots
p^{N}(dy^{N}|h_{N})\bigg{)}+M\sum_{i=1}^{N}\epsilon_{i}$
$\displaystyle\leq\bigg{(}\int_{\Omega_{0}\times\mathbb{Y}^{1}\times\dots\times\mathbb{Y}^{N}}c(\omega_{0},\gamma^{1,*}(y^{1}),\dots,\gamma^{n,*}(y^{N}))$
$\displaystyle\qquad\qquad\qquad\qquad\times
P(d\omega_{0})p^{1}(dy^{1}|h_{1})p^{2}(dy^{2}|h_{2})\dots
p^{N}(dy^{N}|h_{N})\bigg{)}+2M\sum_{i=1}^{N}\epsilon_{i}$ $\displaystyle\leq
J^{*}(P,p^{1},\dots,p^{N})+2M\sum_{i=1}^{N}\epsilon_{i}+\delta.$

The above holds since on $(\mathbb{Y}^{i}\setminus A_{i})$, $\gamma^{i}_{C}$
is equivalent to $\gamma^{i,*}$.

Since each $\epsilon_{i}>0$ and $\delta$ are arbitrary, we have that:

$\lim_{m\rightarrow\infty}E^{P,p^{1},\dots,p^{N}}_{\tau^{1}_{m},\dots,\tau^{N}_{m}}[c(\omega_{0},\gamma^{1}_{C},\dots,\gamma^{N}_{C})]\leq
J^{*}(P,p^{1},\dots,p^{N}).$

Since we know that, for any $m$,
$J^{*}(P,p^{1}\tau^{1}_{m},\dots,p^{N}\tau^{N}_{m})\leq
E^{P,p^{1}\tau^{1}_{m},\dots,p^{N}\tau^{N}_{m}}[c(x,\gamma^{1}_{C},\dots,\gamma^{N}_{C})]$
by definition (since $(\gamma^{1}_{C},\dots,\gamma^{N}_{C})$ are not
necessarily optimal policies for these measurement channels), it follows that:

$\lim_{m\rightarrow\infty}J^{*}(P,p^{1}\tau^{1}_{m},\dots,p^{N}\tau^{N}_{m})\leq
J^{*}(P,p^{1},\dots,p^{N})$.

Applying Lemma 2, we know that for every $m\in\mathbb{Z}$,

$J^{*}(P,p^{1}\tau^{1}_{m},\dots,p^{N}\tau^{N}_{m})\geq
J^{*}(P,p^{1},\dots,p^{N}).$

Thus we get
$\lim_{m\rightarrow\infty}J^{*}(P,p^{1}\tau^{1}_{m},\dots,p^{N}\tau^{N}_{m})=J^{*}(P,p^{1},\dots,p^{N})$.
This completes the proof. $\diamond$

###  3.3 Sequential Stochastic Control Problems are Nearly Static Reducible

In this section, we show that the weak continuity assumption on the channels
(A3) can be omitted using an extra approximation step. This is the main result
of the paper.

######  Theorem 6.

Assume Assumptions A1 and A2 hold. For any $\epsilon>0$, any sequential
dynamic team problem is $\epsilon$-away in optimal cost from being static
reducible.

We note that the theorem proof is also constructive: the solution and the cost
obtained for the perturbed system is realizable (under a randomized policy)
for the original model.

Proof program. The proof is essentially the same as the one for the Theorem 5,
except from the addition of a new step, Step 2, to be presented below.

Figure 1 displays the general proof program. Here $J^{\bar{\gamma}}(\cdot)$
denotes the expected cost when the policies are given specified by
$\bar{\gamma}$. (1) holds because a continuous collection
$\gamma^{1}_{C},\dots,\gamma^{N}_{C}$ can not achieve a cost better than the
optimal cost under channels $p^{1}\tau^{1}_{m},\dots,p^{N}\tau^{N}_{m}$, for
any $m$. (2) holds by applying Step 2 below, where $\beta>0$ is the
(arbitrarily small) error term caused by approximating the channels with
weakly continuous kernels. (3) holds by Step 1 below, because
$\gamma^{1}_{C},\dots,\gamma^{N}_{C}$ approximate the $\delta$-optimal
policies $\gamma^{1,*},\dots,\gamma^{N,*}$, except for on a set of small
measure, resulting in an arbitrarily small error term $\epsilon>0$. After
being defined, $\gamma^{1}_{C},\dots,\gamma^{N}_{C}$ are fixed throughout the
proof, and in Step 2, the application of Lusin’s theorem to approximate the DM
channels uses these fixed continuous policies, as they affect the measures on
the DM action spaces. The terms in (4) are related by Lemma 2, with the
relationship being $J^{*}(P,p^{1}\tau^{1}_{m},\dots,p^{N}\tau^{N}_{m})\geq
J^{*}(P,p^{1},\dots,p^{N})$.

Fig. 1: Proof Program: Arguments of the proof of Theorem 6

We now present the details of the proof.

###### Proof.

(of Theorem 6)

Step 1. Exactly as in the proof of Theorem 5, we use Lusin’s theorem to
construct sets $(\mathbb{Y}^{1}\setminus A^{1}),\dots,(\mathbb{Y}^{N}\setminus
A^{N})$ on which $\gamma^{1,*},\dots,\gamma^{N,*}$ are respectively
continuous, and we use Tietze’s extension theorem to approximate
$\bar{\gamma}^{*}$ with $\gamma^{1}_{C},\dots,\gamma^{N}_{C}$. We will fix
this continuous collection of functions in the following.

Step 2. We now apply Lusin’s theorem again, however this time we apply it to
each agent’s channel to approximate each channel with a weakly continuous
kernel.

Note that a stochastic kernel (as a regular conditional probability) is
defined with the following property: for every
$(\omega_{0},y^{1},u^{1},\dots,y^{i-1},u^{i-1})$,
$p^{i}(y^{i}\in\cdot|\omega_{0},y^{1},u^{1},\dots,y^{i-1},u^{i-1})$ is
$\mathcal{P}(\mathbb{Y}^{i})$-valued and for every Borel set
$B\subset\mathbb{Y}^{i}$, $p^{i}(y^{i}\in
B|\cdot):\omega_{0},y^{1},u^{1},\dots,y^{i-1},u^{i-1}\to\mathbb{R}$ is Borel-
measurable.

Following [5, Proposition 7.26], the above property is equivalent to the the
kernel $p^{i}(y^{i}\in\cdot|\omega_{0},y^{1},u^{1},\dots,y^{i-1},u^{i-1})$
being a Borel-measurable map from
$\Omega_{0}\times\mathbb{Y}^{1}\times\mathbb{U}^{1}\times\dots\times\mathbb{Y}^{i-1}\times\mathbb{U}^{i-1}$
to $\mathcal{P}(\mathbb{Y}^{i})$ (which is endowed by the weak convergence
topology).

Because $\mathbb{Y}^{i}$ is standard Borel, $\mathcal{P}(\mathbb{Y}^{i})$ is a
separable metric space, and can be defined by viewing the space of probability
measures $\mathcal{P}(\mathbb{Y}^{i})$ as a convex subset of a locally convex
space [34, Chapter 3] of signed measures defined on ${\cal
B}(\mathbb{Y}^{i})$, where we define the locally convex space of signed
measures with the following notion of convergence: We say that
$\nu_{n}\rightarrow\nu$ if $\int f(y^{i})\nu_{n}(dy^{i})\rightarrow\int
f(y^{i})\nu(dy^{i})$ for every continuous and bounded function
$f:\mathbb{Y}^{i}\to\mathbb{R}$.

Thus, Theorems 3 and 4 apply with the continuous extension being probability
measure-valued (by Theorem 4).

Therefore for any $\beta_{i}>0$, for fixed
$\gamma^{1}_{C},\dots,\gamma^{i-1}_{C}$, and $p^{1},\dots,p^{i-1}$, there
exists a channel $p^{i}_{C}$ that satisfies A3, in the sense that if
$(\omega_{m},y^{1}_{m},u^{1}_{m},\dots,y^{i-1}_{m},u^{i-1}_{m})\rightarrow(\omega_{0},y^{1},u^{1},\dots,y^{i-1},u^{i-1})$,
then
$p^{i}_{C}(y^{i}\in\cdot|\omega_{m},y^{1}_{m},u^{1}_{m},\dots,y^{i-1}_{m},u^{i-1}_{m})\rightarrow
p^{i}_{C}(y^{i}\in\cdot|\omega_{0},y^{1},u^{1},\dots,y^{i-1},u^{i-1})$ weakly.
We emphasize here that the DM policies are fixed as the continuous policies
developed in Step 1; these policies, in conjunction with fixing the previous
DMs’ channels, determine the joint probability distribution on
$\Omega_{0}\times\mathbb{Y}^{1}\times\mathbb{U}^{1}\times\dots\times\mathbb{Y}^{i-1}\times\mathbb{U}^{i-1}$.
Furthermore,
$p^{i}_{C}(\cdot|\omega_{0},y^{1},u^{1},\dots,y^{i-1},u^{i-1})=p^{i}(\cdot|\omega_{0},y^{1},u^{1},\dots,y^{i-1},u^{i-1})$
on a set of measure $1-\beta_{i}$ on
$\Omega_{0}\times\mathbb{Y}^{1}\times\mathbb{U}^{1}\times\dots\times\mathbb{Y}^{i-1}\times\mathbb{U}^{i-1}$.
Let $D^{i}$ denote this set of measure $1-\beta_{i}$, and use $D^{i}_{j}$ to
denote the projection of the set $D^{i}$ on its $j$th component.

Let
$E:=(\cap_{j=1}^{N}D^{j}_{1}\times\cap_{j=2}^{N}D^{j}_{2}\times\mathbb{R}^{k_{1}}\times\cap_{j=2}^{N}D^{j}_{3}\times\dots\cap_{j=N-1}^{N}D^{j}_{2N-1}\times
D^{N}_{2N}\times\mathbb{R}^{k_{N}}\times D^{N}_{2N+1})$. I.e.,
$E\subset(\Omega_{0}\times\mathbb{Y}^{1}\times\mathbb{R}^{k_{1}}\times\mathbb{U}^{1}\times\dots\mathbb{Y}^{N}\times\mathbb{R}^{k_{N}}\times\mathbb{U}^{N})$,
where $p^{i}=p^{i}_{C}$ on $E$, for every $i\in\mathcal{N}$, and $E$ is
constructed using the intersections of the spaces of arbitrarily large measure
on which the channels are weakly continuous. Let $E^{c}$ denote the complement
of $E$ in
$(\Omega_{0}\times\mathbb{Y}^{1}\times\mathbb{R}^{k_{1}}\times\mathbb{U}^{1}\times\dots\mathbb{Y}^{N}\times\mathbb{R}^{k_{N}}\times\mathbb{U}^{N})$.
Let $M:=\|c\|_{\infty}\in\mathbb{R}_{+}$. Now, applying the fact that the
marginal measure on each $D^{i}$ is known, we note that, given fixed
$\gamma^{1}_{C},\dots,\gamma^{N}_{C}$, for any $m\in\mathbb{Z}_{\geq 1}$:

$\displaystyle\int_{E^{c}}c(\omega_{0},u^{1},\dots,u^{N})P(d\omega_{0})p^{1}(dy^{1}|r_{1})\tau^{1}_{m}(dz^{1}|y^{1})\gamma^{1}_{C}(du^{1}|z^{1})\dots$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad
p^{N}(dy^{N}|r_{N})\tau^{N}_{m}(dz^{N}|y^{N})\gamma^{N}_{C}(du^{N}|z^{N})$
$\displaystyle\leq
M\int_{E^{c}}P(d\omega_{0})p^{1}(dy^{1}|r_{1})\tau^{1}_{m}(dz^{1}|y^{1})\gamma^{1}_{C}(du^{1}|z^{1})\dots$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad
p^{N}(dy^{N}|r_{N})\tau^{N}_{m}(dz^{N}|y^{N})\gamma^{N}_{C}(du^{N}|z^{N})$
$\displaystyle\leq M\sum_{i=1}^{N}\beta_{i}.$

Step 3. Assume that $p^{1},\dots,p^{N}$ satisfy A3; this step follows
identically to Step 2 from Theorem 5. Once again, the conclusion is that, for
any $\omega_{0}$ and $y^{1}$:

$\displaystyle\lim_{m\rightarrow\infty}\int\tau^{1}_{m}(dz^{1}|y^{1})p^{2}(dy^{2}|r_{2})\tau^{2}_{m}(dz^{2}|y^{2})\dots$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad
p^{N}(dy^{N}|r_{N})\tau^{N}_{m}(dz^{N}|y^{N})c(\omega_{0},\gamma^{1}_{C}(z^{1}),\dots,\gamma^{N}_{C}(z^{N}))$
$\displaystyle=\int p^{2}(dy^{2}|h_{2})p^{3}(dy^{3}|h_{3})\dots
p^{N}(dy^{N}|h_{N})c(x,\gamma^{1}_{C}(y^{1}),\dots,\gamma^{N}_{C}(y^{N})).$

Step 4. Now, we can show the main result. We have that:

$\displaystyle\lim_{m\rightarrow\infty}E^{P,p^{1}\tau^{1}_{m},\dots,p^{N}\tau^{N}_{m}}[c(\omega_{0},\gamma^{1}_{C},\dots,\gamma^{N}_{C})]$
$\displaystyle=\lim_{m\rightarrow\infty}\int
c(\omega_{0},\gamma^{1}_{C}(z^{1}),\dots,\gamma^{N}_{C}(z^{N}))$
$\displaystyle\qquad\qquad\qquad\times
P(d\omega_{0})p^{1}(dy^{1}|r_{1})\tau^{1}_{m}(dz^{1}|y^{1})\dots
p^{N}(dy^{N}|r_{N})\tau^{N}_{m}(dz^{N}|y^{N})$
$\displaystyle=\lim_{m\rightarrow\infty}\int c(\omega_{0},u^{1},\dots,u^{N})$
$\displaystyle\quad\times
P(d\omega_{0})p^{1}(dy^{1}|r_{1})\tau^{1}_{m}(dz^{1}|y^{1})\gamma^{1}_{C}(du^{1}|z^{1})\dots
p^{N}(dy^{N}|r_{N})\tau^{N}_{m}(dz^{N}|y^{N})\gamma^{N}_{C}(du^{N}|z^{N})$
$\displaystyle\leq\bigg{(}\lim_{m\rightarrow\infty}\int_{E}c(\omega_{0},u^{1},\dots,u^{N})P(d\omega_{0})p^{1}(dy^{1}|r_{1})\tau^{1}_{m}(dz^{1}|y^{1})\gamma^{1}_{C}(du^{1}|z^{1})\dots$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad
p^{N}(dy^{N}|r_{N})\tau^{N}_{m}(dz^{N}|y^{N})\gamma^{N}_{C}(du^{N}|z^{N})\bigg{)}+M\sum_{i=1}^{N}\beta_{i}$
$\displaystyle=\bigg{(}\int_{E}c(\omega_{0},u^{1},\dots,u^{N})P(d\omega_{0})p^{1}(dy^{1}|h_{1})\gamma^{1}_{C}(du^{1}|y^{1})p^{2}(dy^{2}|h_{2})\dots$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad
p^{N}(dy^{N}|h_{N})\gamma^{N}_{C}(du^{N}|y^{N})\bigg{)}+M\sum_{i=1}^{N}\beta_{i}$
$\displaystyle\leq\bigg{(}\int
c(\omega_{0},u^{1},\dots,u^{N})P(d\omega_{0})p^{1}(dy^{1}|h_{1})\gamma^{1}_{C}(du^{1}|y^{1})p^{2}(dy^{2}|h_{2})\dots$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad
p^{N}(dy^{N}|h_{N})\gamma^{N}_{C}(du^{N}|y^{N})\bigg{)}+2M\sum_{i=1}^{N}\beta_{i}$
$\displaystyle=\int
c(\omega_{0},\gamma^{1}_{C}(y^{1}),\dots,\gamma^{N}_{C}(y^{N}))P(d\omega_{0})p^{1}(dy^{1}|h_{1})p^{2}(dy^{2}|h_{2})\dots
p^{N}(dy^{N}|h_{N})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+2M\sum_{i=1}^{N}\beta_{i}$
$\displaystyle\leq\int
c(\omega_{0},\gamma^{1,*}(y^{1}),\dots,\gamma^{N,*}(y^{N}))P(d\omega_{0})p^{1}(dy^{1}|h_{1})p^{2}(dy^{2}|h_{2})\dots
p^{N}(dy^{N}|h_{N})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+2M\sum_{i=1}^{N}\epsilon_{i}+2M\sum_{i=1}^{N}\beta_{i}$
$\displaystyle=J^{*}(P,p^{1},\dots,p^{N})+\delta+2M(\sum_{i=1}^{N}\epsilon_{i}+\sum_{i=1}^{N}\beta_{i}).$

The first several steps follow using Step 2, applying the fact that, if
$(z^{1},u^{1},y^{2},z^{2},u^{2},\dots,y^{N},z^{N},u^{N})\in E$, then, given
$\gamma^{1}_{C},\dots,\gamma^{N}_{C}$, each $p^{i}=p^{i}_{C}$ on $E$, and each
$p^{i}_{C}$ satisfies A3. Furthermore, the measure of the complement of $E$ is
uniformly small for every $m$. We also use a similar argument as to Theorem 5
to swap the continuous policies with $\bar{\gamma}^{*}$ for the final
inequality.

Since each $\epsilon_{i}>0$, $\beta_{i}>0$, and $\delta$ are arbitrary, and
$\gamma^{1}_{C},\dots,\gamma^{N}_{C}$ are not necessarily optimal policies
under $p^{1}\tau^{1}_{m},\dots,p^{N}\tau^{N}_{m}$, we have that:

$\lim_{m\rightarrow\infty}J^{*}(P,p^{1}\tau^{1}_{m},\dots,p^{N}\tau^{N}_{m})\leq
J^{*}(P,p^{1},\dots,p^{N}).$

Applying Lemma 2, we know that for every $m\in\mathbb{Z}$,

$J^{*}(P,p^{1}\tau^{1}_{m},\dots,p^{N}\tau^{N}_{m})\geq
J^{*}(P,p^{1},\dots,p^{N}).$

Thus we get
$\lim_{m\rightarrow\infty}J^{*}(P,p^{1}\tau^{1}_{m},\dots,p^{N}\tau^{N}_{m})=J^{*}(P,p^{1},\dots,p^{N})$.
This completes the proof. $\diamond$

##  4 Discussion and Conclusion

In this paper, we presented results showing that all discrete-time sequential
stochastic control (single-agent or multi-agent) problems with continuous and
bounded cost functions and convex action spaces are $\epsilon$-away (in
optimal cost) from being static reducible.

The static reduction method has been used in many results to show existence of
team-optimal solutions, such as [23], [44], [41], [35]. Furthermore, [36] uses
the static reduction method to develop results showing that finite models can
be used to approximate general team problems with arbitrarily small error in
cost. Thus, the results presented here show that these previous existence and
approximation results extend (with arbitrarily small error) to all team
problems with continuous and bounded cost functions and convex action spaces.

Continuous-time generalizations as well as filtering theoretic applications of
our result will be interesting given the importance of non-degeneracy in
facilitating mathematical analysis in the theory of non-linear filtering (see
[25, 33, 24, 2, 3] for related, often large-deviations theoretic, studies) in
addition to establishing related results for fully observed or partially
observed controlled diffusions (see e.g. [1, Chapter 7] where challenges
involving non-degenerate diffusions and relations with viscosity solutions are
emphasized). Related studies, under strong regularity conditions or specific
models, include [13] and [6]).

## References

  * [1] A. Arapostathis, V. S. Borkar, and M. K. Ghosh, Ergodic control of diffusion processes, vol. 143, Cambridge University Press, 2012.
  * [2] J. S. Baras, A. Bensoussan, and M. R. James, Dynamic observers as asymptotic limits of recursive filters: Special cases, SIAM Journal on Applied Mathematics, 48 (1988), pp. 1147–1158.
  * [3] J. S. Baras and P. S. Krishnaprasad, Dynamic observers as asymptotic limits of recursive filters, in 1982 21st IEEE Conference on Decision and Control, IEEE, 1982, pp. 1126–1127.
  * [4] V. E. Beneš, Existence of optimal stochastic control laws, SIAM Journal on Control, 9 (1971), pp. 446–472.
  * [5] D. P. Bertsekas and S. E. Shreve, Stochastic optimal control: The discrete time case, Academic Press New York, 1978.
  * [6] S. Bianchini and A. Bressan, Vanishing viscosity solutions of nonlinear hyperbolic systems, Annals of mathematics, (2005), pp. 223–342.
  * [7] J.-M. Bismut, Partially observed diffusions and their control, SIAM Journal on Control and Optimization, 20 (1982), pp. 302–309.
  * [8] D. Blackwell, The comparison of experiments, in Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, (1951), pp. 93–102.
  * [9] V. S. Borkar, White-noise representations in stochastic realization theory, SIAM J. on Control and Optimization, 31 (1993), pp. 1093–1102.
  * [10] V. S. Borkar, Average cost dynamic programming equations for controlled Markov chains with partial observations, SIAM J. Control Optim., 39 (2000), pp. 673–681.
  * [11] , Dynamic programming for ergodic control of Markov chains under partial observations: A correction, SIAM J. Control Optim., 45 (2007), pp. 2299–2304.
  * [12] C. D. Charalambous, Decentralized optimality conditions of stochastic differential decision problems via Girsanov’s measure transformation, Mathematics of Control, Signals, and Systems, 28 (2016), pp. 1–55.
  * [13] G. Ciampa and F. Rossi, Vanishing viscosity in mean-field optimal control, arXiv preprint arXiv:2111.13015, (2021).
  * [14] M. H. A Davis and P. Varaiya, Information states for linear stochastic systems, Journal of Mathematical Analysis and Applications, 37 (1972), pp. 384–402.
  * [15] , Dynamic programming conditions for partially observable stochastic systems, SIAM Journal on Control, 11 (1973), pp. 226–261.
  * [16] R. M. Dudley, Real Analysis and Probability, Cambridge University Press, Cambridge, 2nd ed., 2002.
  * [17] J. Dugundji, An extension of tietze’s theorem, Pacific Journal of Mathematics, 1 (1951), pp. 353–367.
  * [18] W.H. Fleming and E. Pardoux, Optimal control for partially observed diffusions, SIAM J. Control Optim., 20 (1982), pp. 261–285.
  * [19] W. H. Fleming and R. W. Rishel, Deterministic and stochastic optimal control, vol. 1, Springer, 2012.
  * [20] W. H. Fleming and H. M. Soner, Controlled Markov processes and viscosity solutions, vol. 25, Springer Science & Business Media, 2006.
  * [21] I. I. Gihman and A. V. Skorohod, Controlled stochastic processes, Springer Science & Business Media, 2012.
  * [22] I. V. Girsanov, On transforming a certain class of stochastic processes by absolutely continuous substitution of measures, Theory of Probability & Its Applications, 5 (1960), pp. 285–301.
  * [23] A. Gupta, S. Yüksel, T. Başar, and C. Langbort, On the existence of optimal policies for a class of static and sequential dynamic teams, SIAM Journal on Control and Optimization, 53 (2015), pp. 1681–1712.
  * [24] A. J. Heunis, Non-linear filtering of rare events with large signal-to-noise ratio, Journal of applied probability, 24 (1987), pp. 929–948.
  * [25] O. Hijab, Asymptotic bayesian estimation of a first order equation with small diffusion, The Annals of Probability, 12 (1984), pp. 890–902.
  * [26] Y. C. Ho and K. C. Chu, Team decision theory and information structures in optimal control problems - part I, IEEE Transactions on Automatic Control, 17 (1972), pp. 15–22.
  * [27] I. Hogeboom-Burr and S. Yüksel, Continuity properties of value functions in information structures for zero-sum and general games and stochastic teams, arXiv preprint arXiv:2109.11035, (2021).
  * [28] J. Hunter and B. Nachtergaele, Applied Analysis, World Scientific, Singapore, 2005.
  * [29] M. R. James, J. S. Baras, and R. E. Elliott, Risk-sensitive control and dynamic games for partially observed discrete-time nonlinear systems, IEEE transactions on automatic control, 39 (1994), pp. 780–792.
  * [30] H. J. Kushner, A partial history of the early development of continuous-time nonlinear stochastic systems theory, Automatica, 50 (2014), pp. 303–334.
  * [31] H.J. Langen, Convergence of dynamic programming models, Math. Oper. Res., 6 (1981), pp. 493–512.
  * [32] P. Dai Pra, L. Meneghini, and W. J. Runggaldier, Connections between stochastic control and dynamic games, Mathematics of Control, Signals and Systems, 9 (1996), pp. 303–326.
  * [33] A. S. Reddy, A. Budhiraja, and A. Apte, Some large deviations asymptotics in small noise filtering problems, arXiv preprint arXiv:2106.05512, (2021).
  * [34] W. Rudin, Functional analysis, mcgraw-hill, New York, (1991).
  * [35] N. Saldi and S. Yüksel, Geometry of information structures, strategic measures and associated control topologie, arXiv, (2020), pp. arXiv–2010.07377.
  * [36] N. Saldi, S. Yüksel, and T. Linder, Finite model approximations and asymptotic optimality of quantized policies in decentralized stochastic control, IEEE Transactions on Automatic Control, 62 (2017), pp. 2360 – 2373\.
  * [37] M. Schäl, Conditions for optimality in dynamic programming and for the limit of n-stage optimal policies to be optimal, Z. Wahrscheinlichkeitsth, 32 (1975), pp. 179–296.
  * [38] R. Serfozo, Convergence of lebesgue integrals with varying measures, Sankhyā: The Indian Journal of Statistics, Series A, (1982), pp. 380–402.
  * [39] H. S. Witsenhausen, The intrinsic model for discrete stochastic control: Some open problems, Lecture Notes in Econ. and Math. Syst., Springer-Verlag, 107 (1975), pp. 322–335.
  * [40] , Equivalent stochastic control problems, Math. Control, Signals and Systems, 1 (1988), pp. 3–11.
  * [41] S. Yüksel, A universal dynamic program and refined existence results for decentralized stochastic control, SIAM Journal on Control and Optimization, 58 (2020), pp. 2711–2739.
  * [42] S. Yüksel and T. Başar, Stochastic Networked Control Systems: Stabilization and Optimization under Information Constraints, Springer, New York, 2013.
  * [43] S. Yüksel and T. Linder, Optimization and convergence of observation channels in stochastic control, SIAM J. on Control and Optimization, 50 (2012), pp. 864–887.
  * [44] S. Yüksel and N. Saldi, Convex analysis in decentralized stochastic control, strategic measures and optimal solutions, SIAM J. on Control and Optimization, 55 (2017), pp. 1–28.


# Saddlepoints in Unsupervised Least Squares

Samuel Gerber

###### Abstract

This paper sheds light on the risk landscape of unsupervised least squares in
the context of deep auto–encoding neural nets. We formally establish an
equivalence between unsupervised least squares and principal manifolds. This
link provides insight into the risk landscape of auto–encoding under the mean
squared error, in particular all non-trivial critical points are saddlepoints.
Finding saddlepoints is in itself difficult, overcomplete auto–encoding poses
the additional challenge that the saddlepoints are degenerate. Within this
context we discuss regularization of auto–encoders, in particular bottleneck,
denoising and contraction auto–encoding and propose a new optimization
strategy that can be framed as particular form of contractive regularization.

##  1 Introduction

This papers examines the risk landscape of unsupervised least squares.
Unsupervised least squares aims to find a reconstruction map $r$ that
minimizes the discrepancy of the output to it’s own input , i.e., minimizing
$\lVert r(x)-x\rVert^{2}$. In the neural network literature this is referred
to as auto–encoding. Without any restrictions on $r$ the identity mapping is
an optimal, albeit uninformative, solution. An informative solution should
provide a salient summary of the data. To find informative solutions,
auto–encoding is typically formulated as a concatenation of an encoder map
$\lambda$ and a decoder map $g$ with $r=g\circ\lambda$ with restrictions on
$\lambda$ or $g$ to avoid learning the identity function. Several
regularization methods exist to enforce such restrictions. For example, the
bottleneck auto–encoder forces the map $\lambda$ to be of lower dimension than
the input through adding a bottleneck layer. While such regularization avoid
learning the identity map, they do not address the general problem of
overfitting in unsupervised least squares.

For networks with linear activations, (Kawaguchi, 2016) show that for auto-
encoding all minima are globally optimal and the solutions correpsonds to the
maximal principal subspace. This paper provides an analogous characterization
of the critical points of the risk function for deep auto-encoders in the non-
linear case. In particular all critical points, besides minima with zero risk,
are saddle points. Zero risk solutions defy the purpose of autencoders, i.e.
finding a more compact representation that characterizes the input data. In
the linear case solution with zero risk are identity functions. Zero In the
non-linear case zero risk solutions include, besides the identity, space
filling manifolds. This highlights an important distinction between the linear
and non-linear case. In the linear case it is sufficent to restrict the
dimensionality of the principal subspace, for example through the use of a
bottleneck layer. For non-linear auto-encoders additional regularization of
the encoding and decoding functions is required, otherwise the optimzation
will tend towards space-filling solutions.

We establish a tight connection between unsupervised least squares and the
more restrictive notion of a principal manifold. This connection illuminates
the risk landscape of unsupervised leas squares, which in turn informs the
behaviour of auto–encoding under various forms of regularization. Hastie and
Stuetzle (1989) formally defined principal curves as curves that pass through
the middle of a distribution and showed that principal curves are critical
points of the mean squared reconstruction error. This indicates a tight
connection to unsupervised least squares. Principal manifolds enforce that the
reconstruction function constitutes an orthogonal projection, while
unsupervised least squares permit arbitrary reconstruction functions. To
establish the equivalence between principal manifolds and unsupervised least
squares we show that the critical points of the mean squared error risk for
arbitrary reconstruction functions, and thus the critical points of
auto–encoders under squared error loss, are principal manifolds. The
connection of unsupervised least squares to principal manifolds illuminates
the shape of the auto–encoder risk landscape. In particular Duchamp and
Stuetzle (1996) showed that principal curves are saddlepoints of the mean
squared error, this observation also holds for auto–encoding. Duchamp and
Stuetzle (1996) and Gerber and Whitaker (2013) demonstrate that the
saddlepoint nature of the risk landscape leads to overfitting and renders
traditional cross-validation techniques infeasible for tuning of
regularization parameters.

This difficulty persists for auto–encoders as Figure 1 illustrates in the case
of bottleneck auto–encoding. The bottleneck layer enforces a hard constraint
on the dimensionality of the reconstruction function, while the network
architecture implicitly regularizes the complexity of the reconstruction
function. However, due to the saddlepoint nature of the risk landscape the
risk on test data keeps decreasing with increasing network complexity. Thus,
cross-validation will fail to suggest an appropriate network complexity. In
the limit, with infinite training data and no restriction on the complexity of
the reconstruction function a space filling curve, with zero reconstruction
error, is an optimal fit. These global minima, space-filling manifolds or the
identity function, of the auto–encoding risk are not desirable solutions and
do not provide an adequate summary representation of the data.

|  |
---|---|---
|  |
(a) | (b) | (c)
Figure 1: Bottleneck auto–encoding enforces a hard dimensionality constrain
through a bottleneck neural network layer. The images show (top row) the
minima found after 20,000 iterations and (bottom row) the root mean square
error on training (green solid line) and test data (purple dashed line) using
network architectures with hidden layers of (a)
50–100–200–100–50–1–50–100-200–100–50, (b) 50–100–50–1–50–100–50, (c)
200–1–200 units. Depending on the network architecture, auto–encoding does (a)
overfit, (b) fit well or (c) underfit. The relatively small reach of the
spiral example requires a fairly deep network to achieve an accurate fit.
However, the test error does not suggest that the fit in (b) is adequate and
suggests to use the most powerful network. In all cases the one-dimensional
parametrization of the auto–encoder jumps across the spiral arms.

The hard dimensionality constraint in bottleneck auto–encoders avoids fitting
the identity function. However, the hard constraint requires careful
initialization to find an adequate parametrization. As an alternative to the
bottleneck layer several regularization schemes, such as denoising (Vincent et
al., 2008) and contractive auto–encoding(Alain and Bengio, 2014), for
controlling the dimensionality of the reconstruction function have been
proposed. These regularization methods provide a soft constraints on
dimensionality and solve or circumvent the issue of inadequate
parametrization. The soft dimensionality constraints do not alleviate the
challenge of tuning the regularization or selecting an appropriate network
architecture. Figure 2 shows that for a fixed contractive penalty the test
error for different network architecture either selects an architecture that
severely overfits or tends towards the identity mapping.

|  |
---|---|---
|  |
(a) | (b) | (c)
Figure 2: Effect of network architecture in combination with contractive
regularization penalty. The image show the (top row) minima found after 20,000
iterations and (bottom row) the root mean square error on training (green
solid line) and test data (purple dashed line) using a fixed penalty of 0.02
and network architectures with hidden layers of (a) 50–100–200–200–100–50, (b)
50–100–100–50, (c) 200–200 units. The gray lines show a polar grid on the
input space and the black lines show the deformation of the polar grid after
mapping it through the auto–encoder. The gray line shows the spiral the data
is sample from with noise. The black lines shows the spiral after mapping it
through the auto–encoder.

Fixing the network architecture while adjusting the regularization does not
solve the issue as Figure 3 illustrates. A very flexible network that permits
severe overfitting leads to the smallest test error. If the network
architecture is restrictive enough the test error decreases with decreasing
penalty weight and the solution tends towards the identity mapping.

|  |
---|---|---
|  |
(a) | (b) | (c)
Figure 3: Effect of regularization penalty for fixed network architecture. The
image show the (top row) minima found after 20,000 iterations and (bottom row)
the root mean square error on training (green solid line) and test data
(purple dashed line) using a network architecture with hidden layers of
50–50–50–50 units and regularization weights (a) 0.04 (b) 0.02 and (c) 0.005.
The gray lines show a polar grid on the input space and the black lines show
the deformation of the polar grid after mapping it through the auto–encoder.

In practice the structure in the data is typically not know and it would be
difficult to select an appropriate network architecture. Thus, a method that
imposes a dimensionality constraint without reliance on the implicit
regularization of the network architecture is desirable. We contend that the
difficulties in regularization of auto–encoders are due to the saddlepoint
structure of the unsupervised least squares risk.

The critical points of the unsupervised least squares risk are principal
manifolds and provide an arguably reasonable summary representation of the
data. However, except for the uninformative identity solution and space
filling manifolds the critical points are saddlepoints. Figures Figures 1, 2
and 3 illustrate that the saddlepoint nature of the critical points renders
cross–validation useless, since it is possible to move away from a critical
point without increasing the risk on test data. Furthermore steepest decent
methods will typically not even move towards desirable solutions. In the
principal manifold setting, Gerber and Whitaker (2013) propose a solution to
the saddlepoint challenge based on minimizing a different risk. The novel risk
has the property that principal manifolds are now minima instead of
saddlepoints. We show that this risk, derived from geometrical considerations,
is a particular application of a more general approach based on minimizing the
norm of the Gradient of the risk. We apply this Gradient–Norm minimization  to
auto–encoders, which results in a formulation that bears a close resemblance
to contractive auto–encoding (Alain and Bengio, 2014).

##  2 The Unsupervised Least Squares Risk

This section shows that the critical points of the unsupervised least squares
risk are principal manifolds and investigates the properties of those critical
points in detail. Section 2.1 revisits the definition of a principal curves
and manifolds and Section 2.2 establishes the connection of the unsupervised
least squares risk to principal manifolds by examination of the first
variation of the unsupervised least squares risk.

###  2.1 Connection to Principal Manifolds

Let $X$ be a random variable with a smooth density $p$ such that the support
$\Omega=\\{x:p(x)>0\\}$ is a compact, connected region with smooth boundary.
Denote by $E$ the expectation operator, i.e.,
$E\left[f(X)\right]=\int_{\Omega}f(x)p(x)dx$.

Recall the formal definition of principal curves.

######  Definition 2.1 (Principal Curve (Hastie and Stuetzle, 1989)).

Let $g:\Lambda\to\mathbf{R}^{n}$, $\Lambda\subset\mathbf{R}$ and
$\lambda_{g}:\Omega\to\Lambda$ with projection index
$\lambda_{g}(x)=\max_{z}\\{s:\lVert y-g(x)\rVert=\inf_{\tilde{z}}\lVert
y-g(\tilde{s})\rVert\\}$. The principal curves of $Y$ are the set
$\mathcal{G}$ of smooth functions $g$ that fulfill the self consistency
property $E[Y|\lambda_{g}(X)=z]=g(z)$.

Hastie and Stuetzle (1989) showed that principal curves are critical points of
the risk $d(g,X)^{2}=\frac{1}{2}E[\lVert g(\lambda_{g}(X))-X\rVert^{2}]$. The
principal curve risk is closely related to the unsupervised learning risk, but
imposes restriction on the form of the decoder $\lambda$, i.e., the encoder
$\lambda$ is forced to be the projection index given $g$

The typical approach to estimate principal curves optimizes over $g$ and
solver the non–linear problem of finding $\lambda_{g}$. To circumvent the
non–linear optimization problem of computing $\lambda_{g}$ Gerber et al.
(2009) proposed a new formulation that switches the optimization over the
encoder $\lambda$ while fixing $g_{\lambda}(z)\equiv E[X|\lambda(X)=z]$ to be
the conditional expectation given $\lambda$. This yields the risk
$d(\lambda,X)^{2}=\frac{1}{2}E\left[\left\lVert
g_{\lambda}(\lambda(X))-X\right\rVert^{2}\right]$. Again closely related to
the unsupervised least squares risk but with restrictions imposed on the form
of the decoder $g$.

For future reference we term the three different formulations as:

  1. 1.

Principal manifold risk (pm–risk): $d(g,X)^{2}$ with $\lambda_{g}$ constrained
to be orthogonal to $g$

  2. 2.

Conditional expectation manifold risk (cem–risk): $d(\lambda,X)^{2}$ with
$g_{\lambda}$ constrained to the conditional expectation given $\lambda$.

  3. 3.

Unsupervised least squares risk (uls–risk): $d(g,\lambda,X)^{2}$ with $g$ and
$\lambda$ unconstrained.

Duchamp and Stuetzle (1996) showed that principal curves are saddlepoints of
the pm–risk $d(g,X)^{2}$ and Gerber and Whitaker (2013) showed that critical
points of the cem–risk are weak principal curves. Weak principal curves are,
as the name implies, a slightly weaker version of principal curves:

######  Definition 2.2 (Weak Principal Curves (Gerber and Whitaker, 2013)).

Let $g:\Lambda\to\mathbf{R}^{n}$ and $\lambda:\Omega\to\Lambda$. The weak
principal curves of $Y$ are the set $\mathcal{G}_{w}$ of functions $g$ that
fulfill the self consistency property $E[Y|\lambda(Y)=s]=g(s)$ with $\lambda$
satisfying
$\left<y-g(\lambda(y)),\left.\frac{d}{ds}g(s)\right|_{s=\lambda(y)}\right>=0\,\forall
y\in\Omega$.

For principal curves which have no ambiguity points, i.e. all $x\in\Omega$
have a unique closest point on the curve, the definition is equivalent to
principal curves.

###  2.2 Critical Points are Principal Manifolds

To establish the connection of the unsupervised least squares risk

$d(g,\lambda,X)^{2}=\frac{1}{2}E\left[\lVert
g\left(\lambda(X)\right)-X\rVert^{2}\right]$

to principal manifolds, we show that the critical points of
$d(g,\lambda,X)^{2}$ are weak principal manifolds.

For the pm–risk the optimization is over decoder $g$ only the encoder
$\lambda$ is defined in terms of $g$. Vice versa, for the cem–risk the
optimization is over the encoder $\lambda$ only and the decoder $g$ is defined
in terms of $\lambda$. The following theorem establishes that the critical
points for the uls–risk which includes optimization over both $g$ and
$\lambda$ are weak principal manifolds.

######  Theorem 2.1.

The critical points of the unsupervised leasts squares risk
$d(g,\lambda,X)^{2}=\frac{1}{2}E\left[\lVert
g\left(\lambda(X)\right)-X\rVert^{2}\right]$ are weak principal curves.

###### Proof.

The Gâteaux derivative (or first variation) of $d(\lambda,g,X)^{2}$ with
respect to $\lambda$ is

$\frac{d}{d\epsilon}d(\lambda+\epsilon\tau,g,X)^{2}=E\left[\left(g\left(\lambda(X)-X\right)\right)\nabla_{g}\left(\lambda(X)\right)\tau(X)\right]$
(1)

and with respect to $g$

$\frac{d}{d\epsilon}d(\lambda,g+\epsilon h,X)^{2}=E\left[\langle
g\left(\lambda(X)\right)-X,h\left(\lambda(X)\right)\rangle\right]\,.$ (2)

At a critical point these have to be pointwise zero for any $\tau$ (variation
of $\lambda$) and $h$ (variation of $g$), respectively. This yields the
conditions
$\left(g\left(\lambda(X)-X\right)\right)\nabla_{g}\left(\lambda(X)\right)=0$
from equation (1) and $g(z)=E[X|\\{x:\lambda(x)=z\\}]$ for any $z$ in the
image of $\lambda$ from equation (2). This establishes that critical points of
the uls–risk are weak principal manifolds. ∎

The critical points contain uninteresting minimal solutions with zero
reconstruction residual, i.e., space filling manifolds and the identity
mapping. Critical points of the pm–risk and cem–risk are saddlepoints, since
the uls–risk is more flexible, i.e., is a superset of both the pm–risk and the
cem-risk, the critical points of the uls–risk are saddlepoints as well.

The uls–risk poses additional challenges. If $\lambda$ is permitted to be
injective, i.e., no dimensionality constraints, then the condition that
$g(z)=E[X|\\{x:\lambda(x)=z\\}]$ can only be satisfied by the identity
mapping, since the set $\\{x:\lambda(x)=z\\}$ is a single point. Additionally,
in that setting the critical points have a discontinuous Gâteaux derivative:
Consider a critical point with encoder $\lambda_{*}$ and decoder $g_{*}$, with
rank $\nabla_{\lambda}$ less than $n$. Let $\pi_{\alpha}$ be a set of maps
such that $\lambda+\pi_{\alpha}$ is injective and
$\lVert\pi_{\alpha}(x)\rVert\leq\alpha$. Now from the critical point
conditions $\int_{\lambda^{-1}(\\{z\\})}\left(g(z)-x\right)p(x)dx=0$. Let
$s=(\lambda+\pi_{\alpha})^{-1}(\\{z\\})$, now for any $\alpha>0$ we have
$\int_{(\lambda+\pi_{\alpha})^{-1}(\\{z\\})}\left(g(z)-x\right)p(x)dx=\left(g(s)-x\right)p(x)+\alpha\lVert\nabla_{g}(s)\rVert+O(\alpha^{2})$
which cannot be made arbitrarily small. This discontinuity is expected since
the expectation $E$ changes abruptly when moving to an injective function, or
in fact at any change in the rank of the Jacobian $\nabla_{\lambda}$. Thus, in
order to avoid the identity mapping it is necessary to constrain the
dimensionality of the reconstruction function.

##  3 Shaping the Unsupervised Least Squares Risk

To avoid fitting overly curved solutions Rifai et al. (2011) propose an
explicit penalty on the shape of the solution by adding a penalty on the
Hessian to contractive encoding. This approach combines a regularization on
the dimensionality, the Jacobian, and a regularization on the curvature, the
Hessian. Penalizing the Hessian is akin to the proposal by Kégl et al. (2000)
in the context of fitting principal manifolds. However, the saddlepoint nature
of the objective function makes it infeasible to use cross–validation for
tuning the amount of regularization required.

To address the saddlepoint challenge we propose to change the objective
function such that all critical points are local minima. Gerber and Whitaker
(2013) applied this approach to principal manifolds. They observed that
principal curves are saddlepoints of the risk because curves with smaller risk
can be achieved by either violating the conditional expectation constraint in
the pm–risk or by violating the orthogonality constraint in the cem–risk
formulation. This lead Gerber and Whitaker (2013) to minimize orthogonality
using the risk:

$q(\lambda,X)^{2}=E\left[\left\langle\left(g_{\lambda}(\lambda(X))-X\right),\left.\frac{d}{dz}g(z)\right|_{z=\lambda(X)}\right\rangle^{2}\right]=0\,.$
(3)

Gerber and Whitaker (2013) showed that all critical points of this risk are
minima and principal curves.

In this section we show that there is a general principle underlying the
derivation by Gerber and Whitaker (2013) that is not restricted to the
principal manifold case. In Section 3.1 we derive the general principle from
Newton’s method for optimization and show how it leads to the orthogonal risk
in the case of principal manifolds and in Section 3.3 we apply it to
auto–encoding which results in an orthogonal contractive penalty.

###  3.1 Gradient–Norm Minimization

Newton’s method for finding critical points of a function
$f:\mathbb{R}^{m}\to\mathbb{R}$ is to find the zero crossings of $\nabla f$.
Newton’s method applied to the gradient of a multivariate function
$f:\mathbb{R}^{m}\to\mathbb{R}$ yields updates of the form

$\mathbf{x}^{k+1}=\mathbf{x}^{k}-\alpha\mathbf{v}$

with $\mathbf{v}$ a solution to

$\nabla^{2}f(\mathbf{x}^{k})\mathbf{v}=\nabla f(\mathbf{x}^{k})$

where $\nabla^{2}f$ is the Hessian of $f$. For $\nabla^{2}f$ indefinite the
iterations moves—given an appropriate step size—towards a saddlepoint.

If the Newton step is difficult to solve, i.e., the inversion of the Hessian
to expensive, one can resort to minimizing the gradient norm $||\nabla
f(x)||^{2}$. Since $||\nabla f(x)||^{2}\geq 0$, the critical points of $f$ are
minima of the gradient–norm risk. However, depending on the structure of $f$,
additional critical points are possible. At critical points of $||\nabla
f(x)||^{2}$ the gradient $\nabla^{2}f(x)\nabla f(x)$ has to be zero. Thus,
either the gradient $\nabla f$ has to be zero, the Hessian $\nabla^{2}f$ is
zero or the gradient is a linear combination of directions with zero
curvature, i.e. $\nabla fv=0$ or $\nabla^{2}fv=0$ for all directions $v$. For
functions with non-degenerate Hessian all critical points require $\nabla
f=0$, and the gradient–norm minimization finds a critical point of $f$. For
functions with degenerate Hessians, inflection points in the direction of the
gradient are additional critical points of $||\nabla f||^{2}$. Such critical
points can pose a problem for finding critical points of $f$ through
gradient–norm minimization and need to be evaluated.

Newton’s method is a scaled steepest descent method with scaling by
$\nabla^{2}f(x)^{-1}$. The gradient of $\nabla f(x)$ is $\nabla^{2}f(x)\nabla
f(x)$, i.e., a steepest descent with scaling by $\nabla^{2}f(x)$. This avoids
having to invert the Hessian but worsen the condition number and results in
slower convergence (Boyd and Vandenberghe, 2004).

###  3.2 Gradient–Norm Minimization for Principal Manifolds

Applying the gradient-norm minimization procedure to the cem–risk recovers the
geometrically derived formulation by Gerber and Whitaker (2013). The gradient
of $d(\lambda,X)^{2}$ with respect to $\lambda$ is:

$E\left[\left\langle\left(g_{\lambda}(\lambda(X))-X\right),\left.\frac{d}{ds}g(s)\right|_{s=\lambda(X)}\right\rangle\right]\,.$
(4)

By the calculus of variations this has to hold pointwise. Applying the
gradient–norm minimization pointwise recovers the orthogonality risk in
Equation 3.

###  3.3 Gradient–Norm Minimization for Auto–encoding

Applying the gradient-norm minimization to the uls–risk from Equations (1) and
(2) results in the risk:

$E\left[\left(g\left(\lambda(X)\right)-X\right)^{2}\right]+\alpha
E\left[\left(g\left(\lambda(X)\right)-X\right)^{2}\nabla_{g}\left(\lambda(X)\right)^{2}\right]$
(5)

with $\alpha=1$. The first term is the squared residual and the second term
can be seen as a directional contraction penalty; the Jacobian of $g$ is
penalized but only in the direction of the residual vector. For principal
manifolds the second term is zero since the Jacobian of $g$ has to be zero in
the direction of the residual, i.e. $g\cdot\lambda$ is an orthogonal
projection to $g$. Treating the second term of the derivative as a penalty we
can weigh it differently through changing $\alpha$ during optimization.

Figure 4 illustrates this approach on a bottleneck neural network architecture
and compares it with no and contractive regularization.

|  |
---|---|---
(a) | (b) | (c)
Figure 4: The image show the minima found after 20,000 iterations using a
network architecture with hidden layers of 50–100–200–1–200–100–50, units and
(a) no regularization (b) contraction penalty and (c) orthogonal contractive
penalty.  Figure 5: The effect of the orthogonal contractive penalty on an
idealized example problem. The idealized setting assumes that the Jacobian
norm is perfectly anti–correlated with the residual. That is, as the
reconstruction functions moves away from the identity function (at $x-r(x)=0$)
towards a principal manifold (at $x-r(x)=1$) the increase in error is matched
by a decrease in the Jacobian. The orthogonal contraction has a minima at both
0 and 1, but combined with the squared residual term, the effect is
negligible. Increasing the orthogonal penalty creates a minima closer to the
principal manifold, however, the identify function still is minimal and has a
larger region of attraction. The normalized orthogonal penalty actively pushes
the solution away from the identity solution and combined with the residual
term leads to a minima close to the principal manifold.

The method for finding saddlepoints does not address the issue of
discontinuous saddlepoints if the dimensionality is not restricted. The
orthogonal contractive penalty does typically not help to find such degenerate
solutions and results in the identity solution. This behaviour is expected
since moving towards the identity solution often also reduces the orthogonal
contractive penalty as illustrated in an idealized setting in Figure 5. To
remedy this problem we consider normalizing the contractive penalty to:

$\alpha
E\left[\frac{\left(g\left(\lambda(X)\right)-X\right)^{2}\nabla_{g}\left(\lambda(X)\right)^{2}}{\left(g\left(\lambda(X)\right)-X\right)^{2}}\right]\,.$
(6)

This has the effect that the penalty increases quadratically towards the
identity solutions, as illustrated in Figure 5. The normalized penalty
counterweights the quadratic decrease in the reconstruction error. Figure 6
demonstrates the desired effect of pushing the solution away from the
identity.

|  |
---|---|---
(a) | (b) | (c)
Figure 6: The image show the minima found after 20’000 iterations using a
network architecture with hidden layers of 50–100–200–100–50, units and (a)
0.04 (b) 0.02 (c) 0.005 weighted orthogonal penalty. The orthogonal penalty
yields reasonable results for a range of penalty weights.

The orthogonal penalty works well for examples with a co–dimension of one. For
more realistic examples, with higher co–dimension, the orthogonal penalty
reaches zero if the residual vectors are contained in any subspace of the
normal bundle. In this case the orthogonal contractive penalty has to be
combined with a dimensionality constraint. Figure 7 shows the effect on
denoising auto–encoding. The orthogonal contractive penalty preferentially
selects directions that tend towards an orthogonal projection.

|  |
---|---|---
(a) | (b) | (c)
Figure 7: The (a) illustration depicts the effect of orthogonal contraction
with denoising auto–encoding. In the limit, points from the density (gray
area) with noise added, $x+\epsilon$ (black dot) are preferentially mapped
orthogonal to the contraction (purple) as compared to denoising alone
(orange). The (b) orthogonal contraction with denoising leads to sharper
boundary as compared to (c) denoising alone. This indicates that orthogonal
contraction with densoing can yield solutions that generalize better to unseen
data than denosing alone.

##  4 Conclusion

The connection of auto–encoding neural networks with principal manifolds casts
regularization as an approach to find saddlepoints of the mean squared error
risk. The issue of saddlepoints has been recently explored in the neural
network literature. Pascanu et al. (2014) develop an optimization strategy to
avoid saddlepoints, while Choromanska et al. (2015) argue that saddlepoints
are desirable solutions in deep learning. The connection to principal
manifolds makes the argument for saddlepoints as desirable solutions explicit
in the case of auto–encoding networks.

We proposed a new method, gradient–norm minimization for finding saddlepoints.
The gradient–norm minimization is potentially converging slowly. Both Newton’s
method and gradient–norm minimization are gradient descent schemes under
scaling. Newton’s method scales by the inverse Hessian, while the proposed
method corresponds to a scaling by the Hessian. This scaling increases the
condition number and decreases the convergence rate.

## References

  * Alain and Bengio [2014] G. Alain and Y. Bengio.  What regularized auto-encoders learn from the data-generating distribution.  _The Journal of Machine Learning Research_ , 15(1):3563–3593, 2014.
  * Boyd and Vandenberghe [2004] S. Boyd and L. Vandenberghe.  _Convex optimization_.  Cambridge university press, 2004.
  * Choromanska et al. [2015] A. Choromanska, M. Henaff, M. Mathieu, G. Ben Arous, and Y. LeCun.  The loss surface of multilayer networks.  In _AI & Statistics (AIStats 2015)_. arXiv:1412.0233, 2015.
  * Duchamp and Stuetzle [1996] T. Duchamp and W. Stuetzle.  Extremal properties of principal curves in the plane.  _The Annals of Statistics_ , 24(4):1511–1520, 1996.
  * Gerber and Whitaker [2013] S. Gerber and R. Whitaker.  Regularization-free principal curve estimation.  _The Journal of Machine Learning Research_ , 14(1):1285–1302, 2013.
  * Gerber et al. [2009] S. Gerber, T. Tasdizen, and R. Whitaker.  Dimensionality reduction and principal surfaces via kernel map manifolds.  In _IEEE 12th International Conference on Computer Vision_ , pages 529–536, 2009.
  * Hastie and Stuetzle [1989] T. Hastie and W. Stuetzle.  Principal curves.  _Journal of the American Statistical Association_ , 84(406):502–516, 1989.
  * Kawaguchi [2016] K. Kawaguchi.  Deep learning without poor local minima.  In _Advances in Neural Information Processing Systems_ , pages 586–594, 2016.
  * Kégl et al. [2000] B. Kégl, A. Krzyzak, T. Linder, and K. Zeger.  Learning and design of principal curves.  _IEEE Transaction On Pattern Analysis Machine Intelligence_ , 22(3):281–297, 2000.
  * Pascanu et al. [2014] R. Pascanu, Y. N. Dauphin, S. Ganguli, and Y. Bengio.  On the saddle point problem for non-convex optimization.  _arXiv preprint arXiv:1405.4604_ , 2014.
  * Rifai et al. [2011] S. Rifai, G. Mesnil, P. Vincent, X. Muller, Y. Bengio, Y. Dauphin, and X. Glorot.  Higher order contractive auto-encoder.  _Machine Learning and Knowledge Discovery in Databases_ , pages 645–660, 2011.
  * Vincent et al. [2008] P. Vincent, H. Larochelle, Y. Bengio, and P.-A. Manzagol.  Extracting and composing robust features with denoising autoencoders.  In _Proceedings of the 25th international conference on Machine learning_ , pages 1096–1103. ACM, 2008.