Title: NEURAL NETWORKS FOR IRREGULARLY OBSERVED CONTINUOUS-TIME STOCHASTIC PROCESSES

Abstract: Designing neural networks for continuous-time stochastic processes is challenging, especially when observations are made irregularly. In this article, we analyze neural networks from a frame theoretic perspective to identify the sufficient conditions that enable smoothly recoverable representations of signals in L 2 (R). Moreover, we show that, under certain assumptions, these properties hold even when signals are irregularly observed. As we obtain a family of (convolutional) neural networks that satisfy these conditions, we show that we can optimize our convolution filters while constraining them so that they effectively compute a Discrete Wavelet Transform. Such a neural network can efficiently divide the time-axis of a signal into orthogonal sub-spaces of different temporal scale and localization. We evaluate the resulting neural network on an assortment of synthetic and real-world tasks: parsimonious auto-encoding, video classification, and financial forecasting.

INTRODUCTION:

The predominant assumption made in deep learning for time series analysis is that observations are made regularly, with the same duration of time separating each successive timestamps (Cho et al., 2014; Graves et al., 2013; Sutskever et al., 2014; LeCun & Bengio, 1995; van den Oord et al., 2016; Bakshi & Stephanopoulos, 1993) . However, this assumption is often inappropriate, as many real-world time series are observed irregularly and are, occasionally, event-driven (e.g., financial data, social networks, internet-of-things).

One common approach in working with irregularly observed time series is to interpolate the observations to realign them to a regular time-grid. However, interpolation schemes may result in spurious statistical artifacts, as shown in (Huth & Abergel, 2014; Belletti et al., 2017) . Fortunately, procedures for working with irregularly observed time series in their unaltered form have been devised, notably in the field of Gaussian-processes and kernel-learning (Huth & Abergel, 2014; Belletti et al., 2017) and more recently in deep learning (Neil et al., 2016) .

In this article, we investigate the underlying representation of time series data as it is processed by a neural network. Our objective is to identify a class of neural networks that provably guarantee information preservation for certain irregularly observed signals. In doing so, we must analyze neural networks from a frame theoretic perspective, which has enabled a clear understanding of the impact discrete sampling has on representations of continuous-time signals (Benedetto & Heller, 1990; Benedetto, 1992; Benedetto & Ferreira, 2003; Feichtinger & Gröchenig, 1994; Gröchenig, 1992; Mallat, 2008) .

Although frame theory has historically been studied in the linear setting, recent work by Sun & Tang (2017) has related frames with non-linear operators in Banach space, to what can be interpreted as non-linear frames. Here, we extend this generalization of frames to characterize entire families of neural networks. In doing so, we can show that the composition of certain non-linear neural layers (i.e., convolutions and fully-connected layers) form non-linear frames in L 2 (R), while others do not (i.e., recurrent layers).

Moreover, frame theory can be used to analyze randomly-observed time series. In particular, when observations are made according to a family of self-exciting point processes known as Hawkes processes (Daley & Vere-Jones, 2007) . We prove that such processes, under certain assumptions of stability, almost surely yield non-linear frames on a class of band-limited functions. That is to say, that despite having discrete and irregular observations, the signal of interest can still be smoothly recovered.

As we obtain a family of convolutional neural networks that constitute non-linear frames, we show that under certain conditions, such networks can efficiently divide the time-axis of a time series into orthogonal sub-spaces of different temporal scale and localization. Namely, we optimize the weights of our convolution filters while constraining them so that they effectively compute a Discrete Wavelet Transform (Mallat, 1989) . Our numerical experiments on synthetic data highlight this unique capacity that allows neural networks to learn sparse representations of signals in L 2 (R), and how such a property is particularly powerful when training parsimoniously parameterized auto-encoders. Such auto-encoders learn optimal ways of compressing certain classes of input signals.

Finally, we show that the ability of these networks to divide time series into a set sub-spaces, corresponding to different temporal scales and localization, can be composed with existing predictive frameworks to improve both accuracy and efficiency. This is demonstrated on real-world video classification and financial forecasting tasks.

CONTRIBUTIONS & ORGANIZATION:

1. Neural representations of L 2 (R): We introduce the article with a theoretical analysis of the sufficient conditions on neural networks that enable smoothly recoverable representations of signals in L 2 (R) and prove that, under certain assumptions, this property holds true in the irregularly observed setting.

2.. Orthogonal representations in time::

We proceed to show that by enforcing certain constraints on convolutional filters, we can guarantee that the representation that the neural network produces only depends on the coordinates of the input signal in an learned orthonormal basis.

3. Numerical experiments: Finally, we evaluate the resulting constrained convolutional neural network on an assortment of synthetic and real-world tasks: parsimonious auto-encoding, video classification, and financial forecasting.

NOTATION:

• L 2 (R) is the space of square-integrable real-valued functions defined on R and equipped with the norm induced by the inner product f, g ∈ L 2 (R) → ∫ t∈R f (t)g(t)dt.

• L 2 d (R) is the space of square-integrable d-dimensional vector-valued functions defined on R and equipped with the norm induced by the inner product f, g

∈ L 2 d (R) → ∫ t∈R f (t) T g(t)dt. • l 2 (Z)

is the space of square-integrable real-valued sequences indexed by Z and equipped with the norm induced by the inner product (x), (y) ∈ l 2 (Z) → ∑ n∈Z x n y n .

• l 2 d (Z) is the space of square-integrable d-dimensional vector-valued sequences indexed by Z and equipped with the norm induced by the inner product (x), (y

) ∈ l 2 d (Z) → ∑ n∈Z x T n y n .

Note that the inner products of the spaces we consider are Hilbert spaces on the classes of equivalent functions for the Lebesgue measure.

• F T [⋅] denotes the Fourier transform and z denotes the complex conjugate of z ∈ C. Recall the Fourier transform of a sequence

(x n ) ∈ Z is given at any frequency ω by F T [(x n )](ω) = ∑ n∈Z e -2πiωn x n . • For a function f ∶ t ∈ R → f (t) ∈ R d , f (⋅ -h) is short-hand to denote f ∶ t ∈ R → f (t -h) ∈ R d , likewise, f (⋅ σ) is used to denote f ∶ t ∈ R → f (t σ) ∈ R d .

• For a set A, (ξ) denotes the sequence

(ξ n ) ∈ A Z . • (ξ)[∶∶ 2] denotes (ξ 2n ) n∈Z .

That is, the dilation of a sequence by a factor of 2.

• For two vectors (w 0 , w 1 ) ∈ R d1 × R d2 , their concatenation is denoted by [w 0 , w 1 ] ∈ R d1+d2 .

1. HOMEOMORPHIC NON-LINEAR ENCODINGS OF CONTINUOUS-TIME SIGNALS:

We begin by investigating sufficient conditions on composite functions that guarantee such functions produce discretized representations of continuous-time signals that can be smoothly reconstructed.

1.1. FRAMES:

To do so, we must leverage frame theory (Benedetto & Ferreira, 2003) , a theory developed to precisely to characterize the suitable properties for linear representations of irregularly observed signals. Intuitively, a frame is a representation of a signal that enables signal recovery in a smooth manner (i.e., suitable for the representation to be homeomorphic).

Formally (Benedetto & Ferreira, 2003) , we define a frame as an operator from L 2 (R) to l 2 (Z) that is characterized by a family of functions (S n ) n∈Z in L 2 (R) (i.e., the atoms of the frame).

Definition 1.1 Linear frame of L 2 (R): A linear operator corresponding to the family

(S) ∈ L 2 (R) Z , F (S) ∶ f ∈ L 2 (R) → (< f, S n >) n∈Z ∈ l 2 (Z)

is a frame of L 2 (R) if and only if there exist two real-valued constants 0 < A ≤ B such that

∀f ∈ L 2 (R), A f 2 2 ≤ F (S) (f ) 2 2 ≤ B f 2 2 .

Representations provided by frames depend smoothly on their inputs. Moreover, a direct consequence of the definition above is that a frame is invertible in a smooth manner on its image.

There are many examples of frames. For now, we provide two concrete examples from (Benedetto & Ferreira, 2003; Mallat, 2008) . Recall the definition of the Haar function as

t ∈ R → W Haar (t) = 1 if t ∈ [0, 1 2), -1 if t ∈ [1 2, 1

), 0 otherwise, the set of dilations and translations of W Haar , namely

W Haar ⋅ -2 l t 2 l t,l∈Z

constitutes a frame of L 2 (R). Shannon's sampling theorem shows that, with sampling frequency 1 ∆t , the set of translated functions ( √ ∆t sin(π(t-n) ∆t)

πt:

) n∈Z is also a frame for the set of functions in L 2 (R) whose Fourier transforms are supported on the interval -1 ∆t , 1 ∆t . In both cases, the atoms of the frame are orthonormal families of functions -it is trivial to prove that A = B = 1. While the first frame works for the entire space of square integrable functions, the second only applies to the sub-space of band-limited signals.

Proposition 1.1 Left inverses of Frames: If F (S) is a frame of L 2 (R) then F (S) has a left inverse F + = (F * (S) F (S) ) -1 F * (S) that is 1 √ A Lipschitz, where F * (S) is the adjoint of F (S) .

This fundamental proposition is proven in (Benedetto & Ferreira, 2003; Mallat, 2008) . As our goal is to find the conditions for non-linear representations of L 2 (R) to be homeomorphic, we unfortunately can not leverage properties in the linear setting. Therefore, we must adopt an alternative definition. Let a non-linear frame be an operator from L 2 (R) to l 2 (Z) that is characterized by a family of functions (S n ) n∈Z in L 2 (R) and a family of non-linear real valued functions (ψ n ) n∈Z defined over R (or R d as a trivial extension).

Definition 1.2 Non-linear frame of L 2 (R): A non-linear discrete representation scheme

F (S),(ψ) ∶ f ∈ L 2 (R) → (ψ n (< f, S n >)) n ∈ l 2 (Z) is a non-linear frame of L 2 (R) if there exist two real-valued constants 0 < A ≤ B such that ∀f, g ∈ L 2 (R), A f -g 2 2 ≤ F (S),(ψ) (f ) -F (S),(ψ) (g) 2 2 ≤ B f -g 2 2 .

It is worth noting that a linear frame (in the standard definition of the term) is still a frame in this non-linear setting.

Proposition 1.2 Smoothness of signal recovery: A non-linear frame is invertible on its image of L 2 (R) and the inverse is 1

√ A Lipschitz. Proof 1.1 Consider f, g ∈ L 2 (R) such that F (S),(ψ) (f ) = F (S),(ψ) (g), then, as A > 0, f -g 2 = 0

and therefore f and g are in same equivalence class in L 2 (R). Therefore, F (S),(ψ) is injective and if we consider (x), (y) ∈ F (S),(ψ) (L 2 (R)) and if we denote by f x the only element in L 2 (R) such that F (S),(ψ) (f x ) = (x), and f y the only element in L 2 (R) such that F (S),(ψ) (f y ) = (y) then, by definition of a non-linear frame,

f x -f y 2 2 ≤ 1 A x -y 2 2 . ∎

In a later section, we will show that smooth signal recovery is crucial for non-linear signal approximations (consisting of a finite number of coefficients) to remain stable during reconstruction. However in order to show this, we must first explore the sufficient conditions on non-linear operators to produce non-linear frames. We start by introducing several definitions on multivariate real-valued functions.

Definition 1.3 Bi-Lipschitz-Invertible (BLI) operators: An operator Φ ∶ l 2 (Z) → l 2 (Z) such that ∃ 0 < A < B s.t. ∀(x n ), (y n ) ∈ L 2 (Z), A x -y 2 2 ≤ Φ(x) -Φ(y) 2 2 ≤ B x -y 2 2

, is a BLI operator and we refer to (A, B) as some framing constants of Φ.

Theorem 1.1 BLI operators and linear frames: Let (Φ l ) l=1...L be a collection of BLI operators with framing constants ((A l , B l )) l=1...L and F a frame on L 2 (R) with framing constants A 0 and

B 0 . The composite operator φ L ○ ⋅ ⋅ ⋅ ○ φ 1 ○ F is a non-linear frame of L 2 (R) with framing constants ∏ L l=0 A 0 and ∏ L l=0 B 0 .

Proof 1.2 The proof of the theorem is immediate but we use it to expose how our careful choice of the definition of non-linear frames is leveraged. First let us recall that injectivity is preserved by composition. Then, we initiate an immediate proof by induction with a simple remark: consider two functions f, g ∈ L 2 (R)

A 1 A 0 f -g 2 2 ≤ A 1 F(f ) -F(g) 2 ≤ B 1 F(f ) -F(g) 2 2 ≤ B 1 B 0 f -g 2 2

To conclude the proof, a similar statement can then be made if we compose Φ 1 ○ F by Φ 2 , . . . Φ L . ∎

This proof allows us to make guarantees about operator pipelines while relying on conditions that are simple to verify. We can now use the theory we have established to analyze the representational properties of neural networks; in particular, convolutional neural networks (CNN) and recurrent neural networks (RNN).

1.2. SUFFICIENT CONDITIONS ON CNNS TO PRODUCE NON-LINEAR FRAMES:

Here, we study representational properties of recent CNN architectures (Chollet, 2016; Kaiser et al., 2017; Lebedev et al., 2014 ) that rely on depth-wise separable convolutions. We show that by enforcing certain constraints on the structure of temporal filters, we obtain a network that is, provably, a non-linear frame. Here we trade off expressiveness for representational guarantees as we impose constraints on network parameters.

In depth-wise separated convolution stacks (Chollet, 2016; Kaiser et al., 2017) a temporal convolution is applied before a depth-wise linear transform and finally a leaky ReLU layer. We assume that the depth-wise linear operators being learned are all full rank (or full column rank if they increase the number of dimensions of the representation). Such an assumption makes sense for CNNs being trained by a stochastic optimization method with non-pathological data-sets.

Inspired by the multi-scale parsing enabled by the discrete wavelet transform or dyadic wavelet transform we employ time domain convolutions that are conjugate mirror filters (Mallat, 2008) . Such time domain filters constitute a decomposition filter bank consisting of cascading convolutions. The decomposition filter bank admits a dual reconstruction filter bank thereby guaranteeing injectivity.

Definition 1.4 Element-wise Leaky ReLU (LReLU): Consider 0 < α << 1, LReLU applies a piecewise linear function element-wise as

LReLU α ∶ (x n ) ∈ l 2 d (Z) → (max(αx n , x n )) n∈Z ∈ l 2 d (Z).

Definition 1.5 Depth-wise fully connected layer (DFC): Consider two integers d i and

d o , A ∈ R do,di and b ∈ R do DF C A,b ∶ (x n ) ∈ l 2 di (Z) → (LReLU (A × x n + b)) n∈Z ∈ l 2 do (Z).

Lemma 1.1 Full column rank DFC (FDFC) layers are BLI: The function

w ∈ R di → LReLU (Aw + b) ∈ R do with d i ≤ d o and A is full column rank is left invertible. Also, the left inverse is Lipschitz as ∃0 < m ≤ M ∈ R such that ∀w ∈ R d i , m w -w ′ 2 ≤ LReLU (Aw + b) -LReLU (Aw ′ + b) 2 ≤ M w -w ′ 2 .

Proof 1.3 As LReLU is strictly increasing and continuous therefore it is invertible and as A is full column rank it admits a left inverse which proves the first part of the lemma. We finish the proof by using the fact that linear functions in vector spaces of finite dimensions are Lipschitz, the fact that LReLU and its inverse are Lipschitz, and the fact that Lipschitz-ness is preserved by composition. ∎

Let us now study the representational properties of time domain convolution layers whose filters are constrained in the Frequency domain.

Definition 1.6 Reconstructible convolution layer (RConv): Consider two convolution filters h, g ∈ l 2 (Z) such that there exist h, g ∈ l 2 (Z) and

∀ω ∈ R, F T [ h] × F T [h](ω) + F T [g] × F T [g]](ω) = 2. (1)

The following convolution is a Reconstructible convolution layer:

RConv l,h,g ∶ (x n ) ∈ l 2 d (Z) → ([h * x n , g * x n ]) n∈Z ∈ l 2 2×d (Z).

Later on, we show that entire families of such h, g ∈ l 2 (Z) exist under some conditions on h, g. In particular Eq. (4) will provide simple sufficient conditions on h and g for Eq.

(1) to hold.

Lemma 1.2 Temporal convolutions allowing reconstruction: Consider four temporal convolution filters h, h, g, g such that their Fourier transforms satisfy (1).

If x 0 l+1 = h * x l and x 1 l+1 = g * x l then x l = 1 2 h[∶∶ -1] * x 0 l+1 + g[∶∶ -1] * x 1 l+1

(where [∶∶ -1] means that we iterate in reverse order on the filter weights) which proves the pair of convolution filters constitutes an invertible operator. Also,

∃ 0 < m ≤ M such that m x l 2 2 ≤ x 0 l+1 2 2 + x 1 l+1 2 2 ≤ M x l 2 2 . Proof 1.4 By definition h[∶∶ -1] * x 0 l+1 +g[∶∶ -1] * x 1 l+1 = h[∶∶ -1] * h * x l + g[∶∶ -1] * g * x l

, therefore, if we recall that the Fourier Transform diagonalizes convolutions and turns time reversal into complex conjugacy, we have

F T h[∶∶ -1] * x 0 l+1 + g[∶∶ -1] * x 1 l+1 = F T h × F T [h] + F T [g] × F T [g] ×F T x l = 2F T x l with condition (1). Also with the Plancherel formula h * x l 2 2 = F T [h * x l ] 2 2 ≤ F T [h] 2 2 × F T [x l ] 2 2 = h 2 2 x l 2 2 . And finally, F T [x l ] 2 2 = 1 4 F T [ h[∶∶ -1] * x 0 l+1 + g[∶∶ -1] * x 1 l+1 ] 2 2 ≤ 1 4 F T [ h[∶∶ -1] * x 0 l+1 2 2 + F T [g[∶∶ -1] * x 1 l+1 ] 2 2 which concludes the proof with m = h 2 2 + g 2 2 4 and M = h 2 2 + g 2 2 .∎

We represent the recomposition operation introduced in Lemma 1.2 in . The next proposition shows how the convolutions RConv and non-linearity LReLU can be interleaved to produce non-linear frames.

Proposition 1.3 Compositions of FDFC and RConv layers are BLI: The composite function from

l 2 di (Z) onto l 2 do (Z) F DF C A L ,b L ○ RConv L,h l ,g l ○ ⋅ ⋅ ⋅ ○ F DF C A1,b1 ○ RConv 1,h1,g1

is BLI. Proof 1.5 Let us recall again that injectivity is stable by composition of operators. It is also clear that non-linear framing conditions remain true as composite bi-Lipschitz functions are also bi-Lipschitz. ∎

With the proposition above it is now trivial to prove the theorem below.

Theorem 1.2 Compositions of FDFC and dilated RConv layers are non-linear frame:

If F is a frame of L 2 (R) then the composite function from L 2 di (R) onto l 2 do (Z) F DF C A L ,b L ○ RConv L,h L ,g L ○ ⋅ ⋅ ⋅ ○ F DF C A1,b1 ○ RConv 1,h1,g1 ○ F is a non-linear frame.

Now, we expose the framing properties of RNNs (for an introduction on RNNs we refer the reader to (Bengio et al., 1994) ). For the vast majority of popular recurrent architectures (for instance, LSTMs, GRUs (Hochreiter & Schmidhuber, 1997; Cho et al., 2014) ) the use of bounded output layers leads to saturation and vanishing gradients. With such vanishing gradients Bengio et al. (1993) , it is possible to find series of input sequences that diverge in l 2 (Z) while their outputs through the RNN are a Cauchy sequence.

Proposition 1.4 Saturating RNNs do not provide non-linear frames: Let us consider a RNN

F (S),(ψ) ∶ f ∈ L 2 (R) → (ψ n ((< f, S n ′ >) n ′ ∈Z )) n ∈ l 2 (Z)

where F (S) is a given linear frame of L 2 (R). If there exists a sequence

(v k ) k∈Z ∈ F (S) (L 2 (R)) Z such that ((ψ n (v k )) n∈Z ) k∈N is a Cauchy sequence in l 2 (Z) while v k 2 → +∞, then F (S),(ψ) is not a linear frame. Proof 1.6 With the assumption on (v k ) k∈Z ∈ F (S) (L 2 (R)) Z , there cannot exist A > 0 such that ∀k 0 , k 1 ∈ Z, A v k0 -v k1 2 2 ≤ (ψ n ((< v k0 , S n ′ >) n ′ ∈Z )) n∈Z -(ψ n ((< v k1 , S n ′ >) n ′ ∈Z )) n∈Z 2 2

as the sequence (v k ) would then be Cauchy and therefore converge as l 2 (Z) is complete for the l 2 norm. ∎ Such a proposition highlights a key difference between the representational ability of RNNs and CNNs. We explore representations of irregularly sampled data through the lens of non-linear frames.

1.3. IRREGULAR SAMPLING:

We now show that even when signals are irregularly observed by a random sampling process, that particular neural networks can still, almost surely produce a homeomorphic representation.

Sampling by Hawkes processes is a common assumption in finance, seismology, and social media analytics (Ogata, 1988; Bacry et al., 2015; Belletti et al., 2017; Yang & Zha, 2013; Li & Zha, 2013; Zhao et al., 2015) . We use (I N t ) to denote the canonical filtration associated with the stochastic process (N t ) t∈R . We recommend (Daley & Vere-Jones, 2007) for a more thorough introduction to this concept. As a simplification, we denote I N t to be the information generated by (N s ) s<t . 

λ t = lim dt→0+ E N (t + dt) -N (t) I N t dt .

For a Hawkes process characterized by φ ∶ t ∈ R → φ(t) ≥ 0, ∀t < 0, φ(t) = 0, µ ≥ 0, we assume

EQUATION

In other words, λ t is the number of observations per unit of time expected given the events that occurred until time t. Intuitively, if λ t is higher, then it is more likely for observations to be available shortly after the time t.

As in (Belletti et al., 2017; Bacry et al., 2015) , Hawkes processes can be used to model the random observation time of a continuous-time series in a setting where information is observed asynchronously in an event-driven manner across multiple channels (the extension to multi-variate point processes is immediate).

Proposition 1.5 Sampling density of stable Hawkes processes: If the Hawkes process (2) is stable (i.e. ∫ t∈R φ(t)dt < 1), then almost surely

lim t→+∞ N t t = µ 1 -∫ t∈R φ(t)dt .

A complete proof of the ergodic behavior of stable Hawkes processes is provided in (Daley & Vere-Jones, 2007). Now, given an asymptotic Nyquist sampling rate for a random sampling scheme, the following lemma delineates which frames can still be used for signal recovery. In particular, we can no longer recover all signals in an unambiguous manner. Hence, exact recovery is only possible for band-limited functions (i.e. functions whose Fourier transform has bounded support).

Theorem 1.3 Irregular sampling frames: If a sequence of time-stamps have the property that

lim n→±∞ t n = ±∞ and lim n→+∞ n t n > 2R 1 , then (e -2itn⋅

) is a frame F of L 2 [-R, R] (where the real axis represents sampling frequencies) with left inverse

F + . Considering R < R 1 and S ∈ L 2 (R) such that F T [S] ∞ < +∞, support(F T [S]) ⊂ [-R 1 , R 1 ] and ∀ω ∈ [-R, R], F T [S](ω) = 1, (3) then ∀f ∈ L 2 (R) s.t. support(F T [f ]) ⊂ [-R, R], f = x n (f )S(⋅ -t n ) where x n (f ) = ∫ R1 ω=-R1 F + (F T [f ]1 [-R1,R1] )(ω)e 2itnω dω.

Complete proof is given in (Benedetto & Heller, 1990; Benedetto, 1992) ; the theorem is regarded as the fundamental theorem of frame analysis for irregularly observed signals. We now leverage the fundamental properties that were obtained in the deterministic setting and extend them to provide guarantees under random sampling schemes.

Proposition 1.6 Under Hawkes process random sampling, framing is preserved almost surely: Let (t n ) n∈Z be a family of sampling time-stamps generated by a stable Hawkes process whose intensity follows the dynamics described in (2), denote

R = 1 2 µ 1 -∫ t∈R φ(t)dt ,

and let S be a frame operator abiding by conditions (3), then almost surely the frame is injective on

f ∈ L 2 (R) s.t. support(F T [f ]) ⊂ [-R, R

] when translated by the irregular time-stamps (t n ) n∈Z .

Proof 1.7 The proposition is a direct consequence of Prop. 1.5 and Theorem 1.3. ∎ Theorem 1.4 Recovery of randomly observed band-limited signals: Let (t n ) n∈Z be a family of sampling time-stamps generated by a stable Hawkes process whose intensity follows the dynamics described in (2) Consider R = 1 2 µ 1-∫t∈R φ(t)dt , let F (S) be a frame operator with atoms (S(⋅ -t n )) n∈Z given by (3). A composite function from L 2 di (R) onto l 2 do (Z)

F DF C A L ,b L ○ RConv L,h L ,g L ○ ⋅ ⋅ ⋅ ○ F DF C A1,b1 ○ RConv 1,h1,g1 ○ F (S(⋅-tn)) n∈Z

is almost surely a non-linear frame over the set of functions in L 2 (R) whose Fourier Transform has its support included in [-R, R]. In particular such a representation is invertible on its image by a Lipschitz inverse.

Proof 1.8 Previously, we proved Theorem 1.2 on the preservation of framing properties by composition with FDFC and RConv layers. In Prop. 1.6 we proved that F (S(⋅-tn)) n∈Z is almost surely a frame of the subset of L 2 (R) of functions with band-limit [-R, R]. ∎ One concern, however, is that the theorems we developed assumed observations on the entire real axis are available as well as infinite representations indexed by Z. In particular, a theory of framing for band-limited functions is useful but only applies to periodic functions. Bounded support function of L 2 (R) are part of the many examples that are not band-limited Mallat (2008); Benedetto & Ferreira (2003) .

1.4. FINITE APPROXIMATIONS OF NON BAND-LIMITED SIGNALS:

In our objective to develop theoretical statements that can be leveraged in practice (i.e., when computing with finite time and memory), we must now extend our analysis to (1) functions observed on compact intervals and (2) finite approximations of signals. The following statements show how the requirements of Lipschitz-ness in non-linear frames provide guarantees on the impact of approximation errors associated with finite representation of continuous-time signals.

The theorems above can be employed for irregularly observed functions that are periodic and band-limited (Benedetto & Ferreira, 2003; Benedetto, 1992; Mallat, 2008) . However, since we hope to develop a representational theory that is applicable to non-stationary signals, we must also consider non-periodic functions. In the appendix, we show how wavelet decomposition can efficiently approximate certain classes of functions that are smooth and not band-limited.

With ⌊log 2 (N )⌋ scales of decomposition and O(N ) scalars representing the approximation of f as P

⌊log 2 (N )⌋ W (f ) the Wavelet approximation error is O(2 -N α ) in L 2 norm

for the space of α Lipschitz functions (see Definition 4.1 in appendix). As we employ functions that are BLI the impact of the approximation error remains controlled.

Proposition 1.7 Approximate representation: Let Φ L ○ ⋅ ⋅ ⋅ ○ Φ 1 be a BLI function from l 2 (Z) onto l 2 (Z). Let P l W be the projection operator from L 2 ([0, 1]) onto a Wavelet basis of l scales,

Φ L ○ ⋅ ⋅ ⋅ ○ Φ 1 ○ P ⌊log 2 (N )⌋ W (f ) -Φ L ○ ⋅ ⋅ ⋅ ○ Φ 1 P +∞ W (f ) 2 2 = O(2 -N 2α ).

In other words, the numerical representation can be arbitrarily close to the true representation of smooth, continuous-time functions with compact support. Indeed, if W is a wavelet basis, then Proj +∞ W (f ) = f . The argument stresses the critical role of our assumption of the Lipschitz-ness of frames and the BLI functions which guarantees that representations based on approximations can be arbitrarily accurate.

2. ORTHOGONAL MULTI-RESOLUTION CONVOLUTIONS IN TIME:

So far, we have focused on sufficient conditions to make accurate representation of continuous-time signals possible as they are observed randomly and as the corresponding observation are processed non-linearly. We now show that additional conditions on time-domain convolutional filter banks further guarantee that the representation is minimal (i.e., produces orthogonal outputs).

2.1. MULTI-RESOLUTION REPRESENTATION:

As our goal is to obtain different representations of a time series while avoiding redundancy, let us introduce multi-resolution approximations (Mallat, 2008) .

Definition 2.1 Multi-resolution approximation: A family (H l ) l∈Z of closed sub-spaces of L 2 (R) is a multi-resolution approximation if the family is nested (∀l ∈ Z, H l+1 ⊂ H l ); dense (∪ l∈Z H l = L 2 (R)); separated (∩ l∈Z H l = {0}); causal (∀l ∈ Z, g(⋅) ∈ H l ⇒ g(⋅ 2) ∈ H l+1 ); stable by trans- lation (∀(t, l) ∈ Z, g(⋅) ∈ H l ⇒ g(⋅ -2 l t) ∈ H l ).

In addition we require that (H 0 ) there exists an orthonormal family (S(⋅ -n)) n∈Z such that span((S(⋅) n∈Z )) = H l , i.e. S(⋅ -n) is a Riesz basis of H 0 with scaling function S.

Such Riesz basis is proven to exist in (Mallat, 2008) ; the family of Haar wavelets is merely an example. General conditions for a function S ∈ L 2 (R) to be a scaling function are given by the following theorem.

Theorem 2.1 Conjugate mirror temporal convolution layer (CMConv): (Mallat, 1989) Let κ S and κ W in l 2 (Z) be two convolution filters such that

EQUATION

EQUATION

)

EQUATION

)

We further assume that

inf f ∈[-1 4 , 1 4 ] F T [κ S ](f ) > 0. The inverse Fourier Transform of ω → ∏ +∞ p=1 F T [κ S ](2 -p ω) √ 2

is a scaling function S of L 2 (R) for a multi-resolution approximation. Moreover, the Wavelet function W defined as the inverse Fourier transform of 1

√ 2 F T [κ W ]F T [S] is such that for any scale l W l,n = 1 √ 2 l W ⋅ -2 l n 2 l

n ∈ Z is an orthonormal basis W l defined as the orthogonal complement of H l in H l+1 . In particular, (W l,n ) l∈Z,n∈Z is an orthonormal basis of L 2 (R).

2.2. DEPTH-WISE SEPARABLE CONVOLUTIONS AND MULTI-RESOLUTION APPROXIMATIONS:

We now show how depth-wise separable convolutions with scaling and wavelet filters quickly come with guarantees of orthogonality.

In the following we consider an input space with d input channels and a series of affine operators with increasing output dimensions (d l ) L l=1 . We denote F S(⋅-tn) n∈Z by F to simplify notations.

Theorem 2.2 Conjugate mirror convolutions and FDFC: Consider two convolution filters κ S and κ W , if κ S , κ W respect the conditions Eq. ( 4) and

inf ω∈[-1 4 , 1 4 ] F T [κ S ](ω) > 0, then κ S , κ W constitute a pair of RConv filters. Consider the function which to f ∈ L 2 d (R) associates (θ l (f )) l=1...L : f → (< f, S(⋅ -n) >) n∈Z (κ W * ⋅)[∶∶2] → BLI → . . . . . . BLI → (θ 1 (f ) n ) n∈Z ↘ (κ S * ⋅)[∶∶2] (κ W * ⋅)[∶∶2] → BLI → . . . BLI → (θ 2 (f ) n ) n∈Z ↘ (κ S * ⋅)[∶∶2] . . . ⋮ ⋱ BLI → (θ L (f ) n ) n∈Z

The representation (θ l (f )) l=1...L is a non-linear frame that only depends on the coordinates of f in an orthonormal basis of L 2 (R).

Proof 2.1 We start the proof by showing that

(x n ) ∈ l 2 (Z) → ([(κ W * x) 2n , (κ S * x) 2n ]) ∈ l 2 (Z)

is a RConv reconstructible convolution layer. Based on Eq. ( 4), as

κ W n = (-1) 1-n κ S -n we have F T [κ W ](ω) = e iπω F T [κ S ](ω + 1 2 ) and then as ∀ω ∈ [-1 2, 1 2], F T [κ S ](ω) 2 + F T [κ S ](ω +

1 2) 2 = 2 the first part of the proof is concluded. The second part of the proof utilizes the fact that the cascading convolutions above compute a Discrete Wavelet Transform Mallat (2008) . Therefore, (θ

1 (f ) n ) n∈Z = (θ 1 (< f, W 1,n >) n ) n∈Z , (θ 2 (f ) n ) n∈Z = (θ 2 (< f, W 2,n > ) n ) n∈Z , . . . , (θ L-1 (f ) n ) n∈Z = (θ L-1 (< f, W L-1,n >) n ) n∈Z and (θ 1 (f ) n ) n∈Z = (θ L (< f, S L-1,n > ) n ) n∈Z where S l,n = 1 √ 2 l S ⋅-2 l n 2 l n ∈ Z . ∎

The cascaded time domain convolutions being computed yield the coordinates of f in an orthonormal basis. Therefore, as the orthogonal CNN grows deeper it can only yield novel orthogonal information about the input signal that is informative of its properties on a particular temporal scale. Such is the nature of our efficiency claim for the neural networks we consider. A key point here is that the 1x1 convolutions operate in depth and not along the axis of time which preserves the temporal scaling properties of the Discrete Wavelet Transform.

2.3. TRAINING OF RCONV LAYERS BY ALTERNATING SGD STEPS AND DC PROGRAMMING::

As noted in Mallat (2008) 

the constraint inf ω∈[-1 4 , 1 4 ] , F T [κ S ]

(ω) > 0 is always met in practice, which our numerical experiments confirm. The two critical constraints on the design of the temporal convolution filters is (1

) that κ W = (-1) 1-n κ S [∶∶ -1] and F T [κ S ](0) = √ 2, which is trivial to enforce, and (2) that ∀ω ∈ R, F T [κ S ](ω) 2 + F T [κ S ](ω + 1 2 ) 2 = 2.

In our implementation we approximate the constraint by computing the Fast Fourier Transform of the filter, since it is defined discretely in time by a finite set of weights. Therefore, we interleave the normal training step of κ S with solving the following following minimization problem

min κ S ∈R H 1 ω=0, 1 N -1 F T [κ S ](ω) 2 + F T [κ S ](ω + 1 2 ) 2 -2

where H is the number of free parameters we allow in our temporal convolution filter. Such an optimization problem can be rewritten as a difference of convex (DC) functions (as x = max(0, x)min(0, x), κ s → F T [κ S ](ω) 2 + F T [κ S ](ω + 1 2 ) 2 -2 is clearly convex and convexity is stable by composition by a non-decreasing function) and an adapted solver (Tao & An, 1998) can then take advantage of the particular structure of the problem to find an optimal solution rapidly.

3. NUMERICAL EXPERIMENTS:

Here, we show that the sufficient conditions for neural networks to yield non-linear frames are computationally tractable. The following experiments explore the empirical properties of such neural networks compared to various baselines.

3.1. SYNTHETIC COMPRESSION EXPERIMENT:

In our first numerical experiment, we generate regularly sampled non-stationary stochastic processes, characterized by a random mixture of Gabor functions (Mallat, 2008) and step functions. As shown in Figure 2 , the resulting signals are highly irregular, lack permanent seasonality, and have compact support. The objective here is to devise a procedure to train conjugate mirror (convolutional) filters with stochastic optimization methods to progressively improve representational power.

We train a 16 parameter filter κ S to optimally conduct the following compression (i.e., auto-encoding) task. The pair of filters specified in Eq. ( 4) are employed as in Theorem 2.2 to produce the coordinates of the input signal in the wavelet basis corresponding to the (learned) filters κ S and κ W . The input signals are uni-variate with 128 observations each.The encoding, therefore, initially consists of 128 scalar values, of which, only the 64 with higher magnitude are selected -all other values are set to 0.

An inverse Discrete Wavelet Transform is then employed to reconstruct the input signal. The quality of this reconstruction is measured by the squared L 2 loss, which penalizes discrepancies between the input signal and its reconstruction. To train this model, we use a stochastic optimization algorithm, RMSProp, to minimize the aforementioned loss. We train for 2,500 iterations with a learning rate of 10 -3 . This optimization is interleaved with a constraint enforcing program that enforces Eq. ( 4) every 100 iterations. Figure 2 shows that this procedure progressively improves the randomly-initialized filters and significantly out-performs an LSTM-based auto-encoder model.

3.2. MULTI-SCALE VIDEO CLASSIFICATION:

We further show that a wavelet representation can be composed with classical recurrent architecture (in regularly observed settings) to mitigate the effect of noisy data. This is particularly useful for LSTM networks Hochreiter & Schmidhuber (1997) , since hyperbolic tangent layers tend to saturate in the presence of high-magnitude perturbations.

The YouTube-8M data-set contains millions of YouTube videos and their associated genres (Abu-El-Haija et al., 2016) . Because the frames in each video are pre-featurized (i.e., a time series of featurized frames), models designed for this data-set must solely leverage the temporal structure in the data. In particular, the raw video feed is not available. A thorough description of the baselines we employ is available in Abu- El-Haija et al. (2016) . This has enabled the authors of the paper to achieve state-of-the-art results in video classifications using a 2-layer LSTM model.

In our experiment, we train a similar model to learn on a multi-scale wavelet representation of data. This representation separates the original time series into d scales, varying from fine to coarse. Each of the d time series in this multi-scale representation are fed into a similar 2-layer LSTMs with d 2 times fewer parameters which results in a decrease of the total number of parameters in the recurrent layers by a factor of d. The outputs of each LSTM, are then concatenated before the final soft-max layer. We provide a model diagram detailing these components in the appendix. Our experimental results in Figure 3 indicate that this multi-scale representation greatly improves the performance of recurrent neural networks while using far fewer parameters.

3.3. MULTI-SCALE FINANCIAL FORECASTING:

In 2015, an astounding medium volume of 40 million shares of AAPL (Apple Inc.) were traded each day. With the price of each share at approximately 100 USD, each 15-minute trading period represents an exchange of 142 million USD. Trades are highly irregular events characterized by an instantaneous exchange of shares between actors. Forecasting trade volume at a very fine resolution is essential in leveraging arbitrage opportunities. However, the noisy nature of financial markets makes this task incredibly challenging (Abergel et al., 2012) .

Using AAPL price data from 2015, we train two neural networks: a standard LSTM and a wavelet transform network, to predict the next 15 minutes of trading given the 15 minutes that have just elapsed. On average, the duration between time-stamps was 907ms (25th percentile: 200ms, median: 220ms, 75th percentile: 1800ms).

After the first scale projection onto a Haar wavelet basis (Mallat, 2008) is produced (with a characteristic resolution τ = 8 seconds), both wavelet transform network (with M = 8) and the LSTM make predictions with this first scale as input. Each model is evaluated by the L 2 loss against a baseline predicting a constant trading volume equal to the average over the previous 15 observed minutes. Notice that in Figure 4 , the LSTM struggles with the noisiness of the data, whereas the wavelet transform network is robust, and manages to improve the prediction performance by a half-percent. This half-percent represents 50 thousand USD of exchanged volume over a 15 minute period.

4. CONCLUSION:

In this article, we analyze neural networks from a frame theoretic perspective. In doing so, we come to the conclusion that by considering time series as an irregularly observed continuous-time stochastic processes, we are better able to devise robust and efficient convolutional neural networks. By leveraging recent contributions to frame theory, we prove properties about non-linear frames that allow us to make guarantees over an entire class of convolutional neural networks. Particularly regarding their capacity to produce discrete representations of continuous time signals that are both injective and bi-Lipschitz. Moreover, we show that, under certain conditions, these properties almost certainly hold, even when the signal is irregularly observed in an event-driven manner. Finally, we show that bounded-output recurrent neural networks do not satisfy the sufficient conditions to yield non-linear frames.

This article is not limited to the theoretical statements it makes. In particular, we show that we can build a convolutional neural network that effectively computes a Discrete Wavelet Transform. The network's filters are dynamically learned while being constrained to produce outputs that preserve both orthogonality and the properties associated with non-linear frames. Our experiments on real-world prediction tasks further demonstrate the benefits of such neural networks. Notably, their ability to produce compact representations that allow for efficient learning on latent continuous-time stochastic processes.

NEURAL ARCHITECTURES EMPLOYED IN THE VIDEO CLASSIFICATION EXPERIMENT:

The present section of the appendix describes in detail the architectures employed in our Youtube8 video classification experiments. In Figure 5 we present the baseline architecture in the form of a block-diagram. In Figure 6 we expose our architectural choices which split the input into independent sub-spaces of representation that all correspond to different characteristic scales of variation of the input signal. 

:



Figures and Tables:

Figure 1: Decomposition and recomposition principle for depth-wise separable convolutions. We denote the Moore-Penrose inverse of the full column rank matrix A by A + .

Figure2: For a ratio of compression of 2, the learned wavelet basis auto-encoder outperforms an LSTM-based auto-encoder with the same number of parameters.

Figure 3: Top: An LSTM model trained on a wavelet-transformed YouTube-8M data-set achieves comparable results against the baseline while using half the number of parameters. Bottom: Table evaluating the wavelet-transformed LSTM model against the results from Abu-El-Haija et al. (2016) on held-out data.

Figure4: Predicting trade volume of a 15 minute window given the previous 15 minutes of observations. We evaluate the performance of neural networks against a simple averaging model. Even with L 1 regularization, the LSTM does not have the same predictive power as the neural network specified in Theorem 2.2 with L = 2 or L = 4.

domain dyadic wavelet transform (cascaded dilated convolutions by Daubechies 4 Scale and Wavelet filters) 1024 features 2 layer stacked LSTM with 1024 hidden units in each layer Weighted sum along time axis (linearly increasing from 1/T to T)

Figure 5: Baseline architecture from (Abu-El-Haija et al., 2016).

LSTM with 1024 hidden units in each layer 2 layer stacked LSTM with 1024 hidden units in each layer 2 layer stacked LSTM with 1024 hidden units in each layer 2 layer stacked LSTM with 256 hidden units in each layer 4

Figure 6: The architecture we propose for the Youtube video classification task that leverages a multi-resolution approximation computed by a wavelet convolution stack.

Definition 1.7 Random sampling Hawkes process: A stochastic point process (N t ) (Daley & Vere-Jones, 2007) defines a random measure over the axis of time and is defined by stochastic local Poisson intensities for (N t )

Table content: <table/>

Peer review (iclr2018):
 Summary This article considers neural networks over time-series, defined as a succession of convolutions and fully-connected layers with Leaky ReLU activations. The authors provide relatively general conditions for transformations described by such networks to admit a Lipschitz-continuous inverse. They extend these results to the case where the first layer is a convolution with irregular sampling. Finally, they show that the first convolutional filters can be chosen so as to represent a discrete wavelet transform, and provide some numerical experiments. Main remarks While the introduction seemed promising, and I enjoyed the writing style, I was disappointed with this article. (1) There are many mistakes in the mathematical statements. First, in Theorem 1.1, I do not think that phi_L .circ ... .circ phi_1 .circ F is a non-linear frame, because I do not see why it should be of the form of Definition 1.2 (what would be the functions psi_n?). For the same reason, I also do not understand Theorem 1.2. In Proof 1.4, the line of equalities after « Also with the Plancherel formula » is, in my opinion, not true, because the L^2 norm of a product of functions is not the product of the L^2 norms of the functions. It also seems to me that Theorem 1.3, from [Benedetto, 1992], is incorrect: it is not the limit of t_n/n that must be larger than 2R, but the limit of N_n/n (with N_n the number of t_i*s that belong to the interval [-n;n]), and there must probably be a compatibility condition between (t_n)_n and R_1, not only between (t_n)_n and R. In Proposition 1.6, I think that the equality should be a strict inequality. Additionally, I do not say that Proof 2.1 is not true, but the fact that the undersampling by a factor 2 does not prevent the operator from being a frame should be justified. (2) The authors do not justify, in the introduction, why admitting a continuous inverse should be a crucial criterion of quality for the representation described by a neural network. Additionally, the existence of this continous inverse relies on the fact that the non-linearity that is used is a Leaky ReLU, which looks a bit like "cheating" to me, because the Lipschitz constant of the inverse of a Leaky ReLU, although finite, is large, so it seems to me that cascading several layers with Leaky ReLUs could encode a transformation with strictly positive, but still very poor frame bounds. (3) I also do not understand why having "orthogonal outputs", as in Section 2, is really desirable; I think that it should be better justified. Also, there are probably other ways to achieve orthogonality than using wavelets in the first layer, so the fact that wavelets achieve orthogonality does not really justify why using wavelets in the first layer is a good choice, compared to other filters. (4) I had understood in the introduction that the authors would explain how to define a (good) deep representation for data of the form (x_n)_{n.in.N}, where each x_n would be the value of a time series at instant t_n, with the t_n non-uniformly spaced. But all the representations considered in the article seem to be applicable to functions in L^2(.R) only (like in Theorem 1.4 and Theorem 2.2), and not to sequences (x_n)_{n.in.N}. There is something that I did not get here. Minor remarks - Fourth paragraph, third line: "this generalization frames"? - Last paragraph before "Contributions & Organization": "that that". - Paragraph about notations: it seems to me that what is defined as l^2(R) is denoted as l^2(Z) after the introduction. - Last line of this paragraph: R^d_1 should be R^{d_1}, and R^d_2 R^{d_2}. - I think "smooth" could be replaced by "continuous" (smoothness implies a notion of differentiability). - Paragraph before Proposition 1.1: .sqrt{s} is not defined, and "is supported" should be "are supported". - Theorem 1.1: the f_k should be phi_k. - Definition 1.4: "piece-linear" -> "piecewise linear"? - Lemma 1.2 and Proof 1.4: there are indices missing to .tilde h and .tilde g. - Proof 1.4: "and finally" -> "And finally". - Proof 1.5: I do not understand the grammatical structure of the second sentence. - Proposition 1.4: the definition of a RNN is the same as definition 1.2 (except for the frame bounds); I do not see why such transformations should model RNNs. - Paragraph before Proposition 1.5: "in,formation". - Proposition 1.6: it should be said on which space the frame is injective. - On page 8, "Lipschitz" is erroneously written (twice). - Proposition 1.7: "ProjW,l"? - Definition 2.1: in the "nested" property, I think that the inclusion should be the other way around. - Before Theorem 2.1, the sentence "Such Riesz basis is proven" is unclear to me. - Theorem 2.1: "filters convolution filters". - I think the architecture described in Theorem 2.2 could be clarified; I am not exactly sure where all the arrows start from. - First line of Subsection 2.3: ". is always" -> "is always". - First paragraph of Subsection 3.2: "the the". - Paragraph 3.2: could the previous algorithms developed for this dataset be described in slightly more detail? I also do not understand the meaning of "must solely leverage the temporal structure". - I think that the section about numerical experiments could be slightly rewritten, so that the architecture used in each experiment is clearer. In Paragraph 3.2 in particular, I did not get why the architecture presented in Figure 6 has far fewer parameters than the one in Figure 5; it would help if the authors clearly precised how many parameters each layer contains. - Conclusion: "we can to" -> "we can". - Definition 4.1: p_v(s) -> p_v(t).