Title: TRAINING AUTOENCODERS BY ALTERNATING MINI-MIZATION

Abstract: We present DANTE, a novel method for training neural networks, in particular autoencoders, using the alternating minimization principle. DANTE provides a distinct perspective in lieu of traditional gradient-based backpropagation techniques commonly used to train deep networks. It utilizes an adaptation of quasi-convex optimization techniques to cast autoencoder training as a bi-quasi-convex optimization problem. We show that for autoencoder configurations with both differentiable (e.g. sigmoid) and non-differentiable (e.g. ReLU) activation functions, we can perform the alternations very effectively. DANTE effortlessly extends to networks with multiple hidden layers and varying network configurations. In experiments on standard datasets, autoencoders trained using the proposed method were found to be very promising and competitive to traditional backpropagation techniques, both in terms of quality of solution, as well as training speed.

1. INTRODUCTION:

For much of the recent march of deep learning, gradient-based backpropagation methods, e.g. Stochastic Gradient Descent (SGD) and its variants, have been the mainstay of practitioners. The use of these methods, especially on vast amounts of data, has led to unprecedented progress in several areas of artificial intelligence. On one hand, the intense focus on these techniques has led to an intimate understanding of hardware requirements and code optimizations needed to execute these routines on large datasets in a scalable manner. Today, myriad off-the-shelf and highly optimized packages exist that can churn reasonably large datasets on GPU architectures with relatively mild human involvement and little bootstrap effort.

However, this surge of success of backpropagation-based methods in recent years has somewhat overshadowed the need to continue to look for options beyond backprogagation to train deep networks. Despite several advancements in deep learning with respect to novel architectures such as encoderdecoder networks and generative adversarial models, the reliance on backpropagation methods remains. While reinforcement learning methods are becoming increasingly popular, their scope is limited to a particular family of settings such as agent-based systems or reward-based learning. Recent efforts have studied the limitations of SGD-based backpropagation, including parallelization of SGDbased techniques that are inherently serial (Taylor et al. (2016) ); vanishing gradients, especially for certain activation functions (Hochreiter & Schmidhuber (1997) ); convergence of stochastic techniques to local optima (Anandkumar & Ge (2016) ); and many more. For a well-referenced recent critique of gradient-based methods, we point the reader to Taylor et al. (2016) .

From another perspective, there has been marked progress in recent years in the area of non-convex optimization (beyond deep learning), which has resulted in scalable methods such as iterated hard thresholding (Blumensath & Davies (2009) ) and alternating minimization (Jain et al. (2013) ) as methods of choice for solving large-scale sparse recovery, matrix completion, and tensor factorization tasks. Several of these methods not only scale well to large problems, but also offer provably accurate solutions. In this work, we investigate a non-backpropagation strategy to train neural networks, leveraging recent advances in quasi-convex optimization. Our method is called DANTE (Deep AlterNations for Training autoEncoders), and it offers an alternating minimization-based technique for training neural networks -in particular, autoencoders.

DANTE is based on a simple but useful observation that the problem of training a single hidden-layer autoencoder can be cast as a bi-quasiconvex optimization problem (described in Section 3.1). This observation allows us to use an alternating optimization strategy to train the autoencoder, where each step involves relatively simple quasi-convex problems. DANTE then uses efficient solvers for quasiconvex problems including normalized gradient descent (Nesterov (1984) ) and stochastic normalized gradient descent (Hazan et al. (2015) ) to train autoencoder networks. The key contributions of this work are summarized below:

• We show that viewing each layer of a neural network as applying an ensemble of generalized linear transformations, allows the problem of training the network to be cast as a bi-quasiconvex optimization problem (exact statement later). • We exploit this intuition by employing an alternating minimization strategy, DANTE, that reduces the problem of training the layers to quasi-convex optimization problems. • We utilize the state-of-the-art Stochastic Normalized Gradient Descent (SNGD) technique (Hazan et al. (2015) ) for quasi-convex optimization to provide an efficient implementation of DANTE for networks with sigmoidal activation functions. However, a limitation of SNGD is its inability to handle non-differentiable link functions such as the ReLU. • To overcome this limitation, we introduce the generalized ReLU, a variant of the popular ReLU activation function and show how SNGD may be applied with the generalized ReLU function. This presents an augmentation in the state-of-the-art in quasi-convex optimization and may be of independent interest. This allows DANTE to train AEs with both differentiable and non-differentiable activation functions, including ReLUs and sigmoid. • We show that SNGD offers provably more rapid convergence with the generalized ReLU function than it does even for the sigmoidal activation. This is corroborated in experiments as well. A key advantage of our approach is that these theoretical results can be used to set learning rates and batch sizes without finetuning/cross-validation. • We also show DANTE can be easily extended to train deep AEs with multiple hidden layers.

• We empirically validate DANTE with both the generalized ReLU and sigmoid activations and establish that DANTE provides competitive test errors, reconstructions and classification performance (with the learned representations), when compared to an identical network trained using standard mini-batch SGD-based backpropagation.

2. RELATED WORK:

Backpropagation-based techniques date back to the early days of neural network research (Rumelhart et al. (1986) ; Chauvin & Rumelhart (1995) ) but remain to this day, the most commonly used methods for training a variety of neural networks including multi-layer perceptrons, convolutional neural networks, autoencoders, recurrent networks and the like. Recent years have seen the development of other methods, predominantly based on least-squares approaches, used to train neural networks. Carreira-Perpinan and Wang (Carreira-Perpinan & Wang ( 2014)) proposed a least-squares based method to train a neural network. In particular, they introduced the Method of Auxiliary Constraints (MAC), and used quadratic penalties to enforce equality constraints. Patel et al. (Patel et al. (2015) ) proposed an Expectation-Maximization (EM) approach derived from a hierarchical generative model called the Deep Rendering Model (DRM), and also used least-squared parameter updates in each of the EM steps. They showed that forward propagation in a convolutional neural network was equivalent to the inference on their DRM. Unfortunately, neither of these methods has publicly available implementations or published training results to compare against.

More recently, Taylor et al. proposed a method to train neural networks using the Alternating Direction Method of Multipliers (ADMM) and Bregman iterations (Taylor et al. (2016) ). The focus of this method, however, was on scaling the training of neural networks to a distributed setting on multiple cores across a computing cluster. Jaderberg also proposed the idea of 'synthetic gradients' in Jaderberg et al. (2016) . While this approach is interesting, this work is more focused towards a more efficient way to carry out gradient-based parameter updates in a neural network.

In our work, we focus on an entirely new approach to training neural networks -in particular, autoencoders -using alternating optimization, quasi-convexity and SNGD, and show that this approach shows promising results on the a range of datasets. Although alternating minimization has found much appeal in areas such as matrix factorization (Jain et al. (2013) ), to the best of our knowledge, this is the first such effort in using alternating principles to train neural networks with related performance guarantees.

3. DANTE: DEEP ALTERNATIONS FOR TRAINING AUTOENCODERS:

In this section, we will first set notation and establish the problem setting, then present details of the DANTE method, including the SNGD algorithm. For sake of simplicity, we consider networks with just a single hidden layer. We then offer some theoretical insight intro DANTE's inner workings, which also allow us to arrive at the generalized ReLU activation function, and finally describe how DANTE can be extended to deep networks with multiple hidden layers.

3.1. PROBLEM FORMULATION:

Consider a neural network with L layers. Each layer l ∈ {1, 2, . . . , L} has n l nodes and is characterized by a linear operator W l ∈ R n l-1 ×n l and a non-linear activation function φ l : R n l → R n l . The activations generated by the layer l are denoted by a l ∈ R n l . We denote by a 0 , the input activations and n 0 to be the number of input activations i.e. a 0 ∈ R n0 . Each layer uses activations being fed into it to compute its own activations as a l = φ l W l , a l-1 ∈ R n l , where φ ., . denotes φ( ., . ) for simplicity of notation. A multi-layer neural network is formed by nesting such layers to form a composite function f given as follows:

EQUATION

where W = {W l } is the collection of all the weights through the network, and x = a 0 contains the input activations for each training sample.

Given m data samples {(x i , y i )} m i=1 from some distribution D, the network is trained by tuning the weights W to minimize a given loss function, J:

EQUATION

Note that a multi-layer autoencoder is trained similarly, but with the loss function modified as below:

EQUATION

For purpose of simplicity and convenience, we first consider the case of a single-layer autoencoder, represented as f (W; x) = φ 2 W 2 , φ 1 W 1 , x to describe our methodology. We describe in a later section on how this idea can be extended to deep multi-layer autoencoders. (Note that our definition of a single-layer autoencoder is equivalent to a two-layer neural network in a classification setting, by nature of the autoencoder.)

A common loss function used to train autoencoders is the squared loss function which, in our simplified setting, yields the following objective.

min

W E x∼D f (W; x) -x 2 2 (4) Now denote f (W; x) -x 2 2 = φ 2 W 2 , φ 1 W 1 , x -x 2 2 (5)

An important observation here is that if we fix W 1 , then Eqn (5) turns into a set of Generalized Linear Model problems with φ 2 as the activation function, i.e.

min W2 E x∼D φ 2 W 2 , z -x 2 2

where z = φ 1 W 1 , x . We exploit this observation in this work. In particular, we leverage a recent result by Hazan et al. (2015) that shows that GLMs with nice, differentiable link functions such as sigmoid (or even a combination of sigmoids such as φ W2 (•)), satisfy a property the authors name Strict Locally Quasi-Convexity (SLQC), which allows techniques such as SNGD to solve the GLM problems effectively.

Similarly, fixing W 2 turns the problem into yet another SLQC problem, this time with W 1 as the parameter (note that

φ W2 • = φ 2 W 2 , φ 1 • ). min W1 E x∼D φ W2 W 1 , x -x 2 2 .

Algorithm 1: Stochastic Normalized Gradient Descent (SNGD)

Input :Number of iterations T , training data S = {(x i , y i )} m i=1 ∈ R d × R, learning rate η, minibatch size b, Initialization parameters w 0 for t = 1 to T do Sample {(x i , y i )} b i=1 ∼ Uniform(S) //Select a random mini-batch of training points Let f t (w) = 1 b b i=1 (y i -φ w, x i ) 2

Let g t = ∇f t (w t ), and ĝ(t) = gt gt w t+1 = w t -η • ĝt end Output :Model given by w T This is quite advantageous for us since it allows us to solve each sub-problem of the alternating setup efficiently. In a subsequent section, we will show that GLMs with non-differentiable activation -in particular, a generalized Rectified Linear Unit (ReLU) -can also satisfy the SLQC property, thus allowing us to extend the proposed alternating strategy, DANTE, to ReLU-based autoencoders too. We note that while we have developed this idea to train autoencoders in this work (since our approach relates closely to the greedy layer-wise training in autoencoders), DANTE can be used to train standard multi-layer neural networks too (discussed in Section 5).

3.2. METHODOLOGY:

We begin our presentation of the proposed method by briefly reviewing the Stochastic Normalized Gradient Descent (SNGD) method, which is used to execute the inner steps of DANTE. We explain in the next subsection, the rationale behind the choice of SNGD as the optimizer. We stress that although DANTE does use stochastic gradient-style methods internally (such as the SNGD algorithm), the overall strategy adopted by DANTE is not a descent-based strategy, rather an alternating-minimization strategy.

Stochastic Normalized Gradient Descent (SNGD): Normalized Gradient Descent (NGD) is an adaptation of traditional Gradient Descent where the updates in each iteration are purely based on the direction of the gradients, while ignoring their magnitudes. This is achieved by normalizing the gradients. SNGD is the stochastic version of NGD, where weight updates are performed using individual (randomly chosen) training samples, instead of the complete set of samples. Mini-batch SNGD generalizes this by applying updates to the parameters at the end of every mini-batch of samples, as does mini-batch Stochastic Gradient Descent (SGD). In the remainder of this paper, we refer to mini-batch SNGD as SNGD itself, as is common for SGD. Algorithm 1 describes the SNGD methodology for a generic GLM problem. DANTE: Given this background, Algorithm 2 outlines the proposed method, DANTE. Consider the autoencoder problem below for a single hidden layer network:

min W f (W 1 , W 2 ) = E x∼D φ 2 W 2 , φ 1 W 1 , x -x 2 2

Upon fixing the parameters of the lower layer i.e. W 1 , it is easy to see that we are left with a set of GLM problems:

min

W E x∼D φ 2 W 2 , z -x 2 2 ,

where z = φ 1 W 1 , x . DANTE solves this intermediate problem using SNGD steps by sampling several mini-batches of data points and performing updates as dictated by Algorithm 1. Similarly, fixing the parameters of the upper layer, i.e. W 2 , we are left with another set of problems:

min W E x∼D φ W2 W 1 , x -x 2 2 ,

where 

φ W2 • = φ 2 W 2 , φ 1 • .

t := 1 while |f (W t 1 , W t 2 ) -f (W t-1 1 , W t-1 2 )| ≥ or t < T AM do W t 2 ← arg min W E x∼D φ 2 W, φ 1 W t-1 1 , x -x 2 2 //use SNGD W t 1 ← arg min W E x∼D φ 2 W t 2 , φ 1 W, x -x 2 2 //use SNGD t := t + 1 end Output :W t 1 , W t 2 3.3 RATIONALE

To describe the motivation for our alternating strategy in DANTE, we first define key terms and results that are essential to our work. We present the notion of a locally quasi-convex function (as introduced in Hazan et al. ( 2015)) and show that under certain realizability conditions, empirical objective functions induced by Generalized Linear Models (GLMs) are locally quasi-convex. We then introduce a new activation function, the generalized ReLU, and show that the GLM with the generalized ReLU also satisfies this property. We cite a result that shows that SNGD converges to the optimum solution provably for locally quasi-convex functions, and subsequently extend this result to the newly introduced activation function. We also generalize the definition of locally quasi-convex to functions on matrices, which allows us to relate these ideas to layers in neural networks.

Definition 3.1 (Local-Quasi-Convexity). Let x, z ∈ R d , κ, > 0 and let f : R d → R be a differentiable function. Then f is said to be ( , κ, z)-Strictly-Locally-Quasi-Convex (SLQC) in x, if

at least one of the following applies:

1. f (x) -f (z) ≤

2. ∇f (x) > 0, and ∀y ∈ B (z, /κ), ∇f (x), yx ≤ 0

where B (z, /κ) refers to a ball centered at z with radius /κ.

We generalize this definition to functions on matrices in Appendix A.3. Definition 3.2 (Idealized and Noisy Generalized Linear Model (GLM)). Given an (unknown) distribution D and an activation function φ : R → R, an idealized GLM is defined by the existence of a

w * ∈ R d such that y i = φ w * , x i ∀i ∈ [m]

where w * is the global minimizer of the error function:

ê rr(w) = 1 m m i=1 (y i -φ( w, x i )) 2

Similarly, a noisy GLM is defined by the existence of a

w * ∈ R d such E (x,y)∼D [y| x] = φ( w * , x ),

which is the global minimizer of the error function:

err(w) = E (x,y)∼D (y i -φ( w, x i )) 2

Without any loss in generality, we use x i ∈ B d , the unit d-dimensional ball. (Hazan et al., 2015, Lemma 3.2) shows that if we draw m ≥ Ω exp(2 w * )

2 log 1 δ samples of {(x i , y i )} m

i=1 from a GLM with the sigmoid activation function, then with probability at least 1 -δ, the empirical error function

f (w) = 1 m m i=1 (y i -φ w, x i ) 2

is ( , e w * 2 , w * )-SLQC in w. However, this result is restrictive, since its proof relies on properties of the sigmoid function, which are not satisfied by other popular activation functions such as the ReLU. We hence introduce a new generalized ReLU activation function to study the relevance of this result in a broader setting (which has more use in practice).

Definition 3.3. (Generalized ReLU) The generalized ReLU function f : R → R, 0 < a < b, a, b ∈ R is defined as: f (x) = ax x ≤ 0 bx x > 0

This function is differentiable at every point except 0. Note that this definition subsumes variants of ReLU such as the leaky ReLU (Xu et al. (2015) ). We define the function g that provides a valid subgradient for the generalized ReLU at all x to be:

g(x) = a x < 0 b x ≥ 0

While SLQC is originally defined for differentiable functions, we now show that with the above definition of the subgradient, the GLM with the generalized ReLU is also SLQC. This allows us to use the SNGD as an effective optimizer for DANTE to train autoencoders with different kinds of activation functions. Theorem 3.4. In the idealized GLM with generalized ReLU activation, assuming

||w * || ≤ W , êrr(w) is , 2b 3 W a , w * -SLQC in w for all w ∈ B d (0, W ). Proof. Consider ||w|| ≤ W such that ê rr m (w) = 1 m m i=1 (y i -φ w, x i ) 2 ≥

, where m is the total number of samples. Also let v be a point /κ-close to minima w * with κ = 2b 3 W a . Let g be the subgradient of the generalized ReLU activation and G be the subgradient of ê rr m (w). (Note that as before, g ., . denotes g( ., . )). Then:

G(w), w -v = 2 m m i=1 g w, x i (φ w, x i -y i ) x i , (w -v) = 2 m m i=1 g w, x i (φ w, x i -φ w * ,x i ) [ x i , w -w * + x i , w * -v ] (Step 1) ≥ 2 m m i=1 g w, x i b -1 (φ w, x i -φ w * ,x i ) 2 +(φ w, x i -φ w * ,x i ) x i , w * -v (Step 2) ≥ 2 m m i=1 g w, x i (b -1 (φ w, x i -φ w * ,x i ) 2 -|φ w, x i -φ w * ,x i |||x i ||||w * -v|| ≥ 2 m m i=1 ab -1 (φ w, x i -φ w * , x i ) 2 -b|φ w, x i -φ w * ,x i |||x i ||||w * -v|| (Step 3) ≥ 2 m m i=1 ab -1 (φ w, x i -φ w * , x i ) 2 -b 2 || w, x i -w * ,x i || κ ||x i || (Step 4) ≥ 2ab -1 - a bW || w, x i -w * ,x i ||||x i || (Step 5) ≥ ab -1 (2 - 1 W ||w -w * ||||x i || 2 ) ≥ 0

In the above proof, we first use the fact (in Step 1) that in the GLM, there is some w * such that φ w * , x i = y i . Then, we use the fact (in Steps 2 and 4) that the generalized ReLU function is b-Lipschitz, and the fact that the minimum value of the quasigradient of g is a (Step 3). Subsequently, in Step 5, we simply use the given bounds on the variables x i , w, w * due to the setup of the problem (w ∈ B d (0, W ), and x i ∈ B d , the unit d-dimensional ball, as defined earlier in this section).

We also prove a similar result for the Noisy GLM below.

Theorem 3.5. In the noisy GLM with generalized ReLU activation, assuming ||w * || ≤ W , given w ∈ B(0, W ), then with probability ≥ 1 -δ after m ≥ 288b 4 W 2 a 2 2 log(1/δ)/ 2 samples, ê rr(w) is , 2b 3 W a , w * -SLQC in w.

The proof for Theorem 3.5 is included in Appendix A.1.

We connect the above results with a result from Hazan et al. (2015) (stated below) which shows that SNGD provably converges to the optimum for SLQC functions, and hence, with very high probability, for empirical objective functions induced by noisy GLM instances too. 

M 2 log( 4T δ ) 2 2 , b 0 ( , δ, T ) , with probability 1 -2δ, f (w) -f (w * ) ≤ 3 .

The results so far show that SNGD provides provable convergence for idealized and noisy GLM problems with both sigmoid and ReLU family of activation functions. We note that alternate activation functions such as tanh (which is simply a rescaled sigmoid) and leaky ReLU (Xu et al. (2015) ) are variants of the aforementioned functions.

In Algorithm 2, it is evident that each node of the output layer presents a GLM problem (and hence, SLQC) w.r.t. the corresponding weights from W 2 . We show in Appendices A.2 and A.3 how the entire layer is SLQC w.r.t. W 2 , by generalizing the definition of SLQC to matrices. In case of W 1 , while the problem may not directly represent a GLM, we show in Appendix A.3 that our generalized definition of SLQC to functions on matrices allows us to prove that Step 4 of Algorithm 2 is also SLQC w.r.t. W 1 .

Thus, given a single-layer autoencoder with either sigmoid or ReLU activation functions, DANTE provides an effective alternating minimization strategy that uses SNGD to solve SLQC problems in each alternating step, each of which converges to its respective -suboptimal solution with high probability, as shown above in Theorem 3.6. Importantly, note that the convergence rate of SNGD depends on the κ parameter. Whereas the GLM error function with sigmoid activation has κ = e W Hazan et al. (2015) , we obtain κ = 2b 3 W a (i.e. linear in W ) for the generalized ReLU setting, which is an exponential improvement. This is significant as in Theorem 3.6, the number of iterations T depends on κ 2 . This shows that SNGD offers accelerated convergence with generalized ReLU GLMs (introduced in this work) when compared to sigmoid GLMs.

3.4. EXTENDING TO A MULTI-LAYER AUTOENCODER:

In the previous sections, we illustrated how a single hidden-layer autoencoder can be cast as a set of SLQC problems and proposed an alternating minimization method, DANTE. This approach can be generalized to deep autoencoders by considering the greedy layer-wise approach to training a neural network (Bengio et al. (2007) ). In this approach, each pair of layers of a deep stacked autoencoder is successively trained in order to obtain the final representation. Each pair of layers considered in this paradigm is a single hidden-layer autoencoder, which can be cast as pairs of SLQC problems that can be trained using DANTE. Therefore, training a deep autoencoder using greedy layer-wise approach can be modeled as a series of SLQC problem pairs. Algorithm 3 summarizes the proposed approach to use DANTE for a deep autoencoder, and Figure 1 illustrates the approach. Note that it may be possible to use other schemes to use DANTE for multi-layer autoencoders such as a round-robin scheme, where each layer is trained separately one after the other in the sequence in which the layers appear in the network.

4. EXPERIMENTS AND RESULTS:

We validated DANTE by training autoencoders on an expanded 32×32 variant of the standard MNIST dataset (LeCun et al. ( 1998)) as well as other datasets from the UCI repository. We also conducted experiments with multi-layer autoencoders, as well as studied with varying number of hidden neurons 

t := 1 for l = 1 to n do while |f (U t , V t ) -f (U t-1 , V t-1 )| ≥ or t < T AM do //Use SNGD for minimizations u t l ← arg min u E x∼D d(e(x, U t [1:l-1] • u • U t-1 [l+1:n-1] ), V t [1:l-1] • V t-1 [l:n-1] ) -x 2 v t n-l ← arg min v E x∼D d(e(x, U t [1:l] • U t-1 [l+1:n-1] ), V t [1:n-l-1] • v • V t-1 [n-l+1:n-1] ) -x 2 t := t + 1 end end Output :U, V

on single-layer autoencoders. Our experiments on MNIST used the standard benchmarking setup of the dataset1 , with 60, 000 data samples used for training and 10, 000 samples for testing. Experiments were conducted using Torch 7 ( Collobert et al. (2011) ).

Autoencoder with Sigmoid Activation: A single-layer autoencoder (equivalent to a neural network with one hidden layer) with a sigmoid activation was trained using DANTE as well as standard backprop-SGD (represented as SGD in the results, for convenience) using the standard Mean-Squared Error loss function. The experiments considered 600 hidden units, a learning rate of 0.001, and a minibatch size of 500 (same setup was maintained for SGD and the SNGD used inside DANTE for fair comparison; one could optimize both SGD and SNGD to improve the absolute result values.) We studied the performance by varying the number of hidden neurons, and show those results later in this section. The results are shown in Figure 2a . The figure shows that while DANTE takes slightly (negligibly) longer to reach a local minimum, it obtains a better solution than SGD. (We note that the time taken for the iterations were comparable across both DANTE and backprop-SGD.)

Autoencoder with ReLU Activation: Similar to the above experiment, a single-layer autoencoder with a leaky ReLU activation was trained using DANTE and backprop-SGD using the Mean-Squared Error loss function. Once again, the experiments considered 600 units in the hidden layer of the 2b . The results for ReLU showed an improvement, and DANTE was marginally better than back-prop SGD across the iterations (as shown in the figure).

In Figure 3 , we also show the reconstructions obtained by both trained models (DANTE and Backprop-SGD) for the autoencoder with the Generalized ReLU activation. The model trained using DANTE shows comparable performance as a model trained by SGD under the same settings, in this case. We also conducted experiments to study the effectiveness of the feature representations learned using the models trained using DANTE and SGD in the same setting. After training, we passed the dataset through the autoencoder, extracted the hidden layer representations, and then trained a linear SVM. The classification accuracy results using the hidden representations are given in Table 1 . The table clearly shows the competitive performance of DANTE on this task.

Experiments on other datasets: We also studied the performance of DANTE on other standard datasets 2 , viz. Ionosphere (34 dimensions, 351 datapoints), SVMGuide4 (10 dimensions, 300 datapoints), Vehicle (18 dimensions, 846 datapoints), and USPS (256 dimensions, 7291 datapoints). Figure 4 and Table 1 show the performance of the proposed method vs SGD on the abovementioned datasets. It can be seen that DANTE once again demonstrates competitive performance across the datasets, presenting its capability as a viable alternative for standard backprop-SGD.

Varying Number of Hidden Neurons: Given the decomposable nature of the proposed solution to learning autoencoders, we also studied the effect of varying hyperparameters across the layers, in particular, the number of hidden neurons in a single-layer autoencoder. The results of these experiments are shown in Figure 5 . The plots show that when the number of hidden neurons is low, DANTE reaches its minumum value much sooner (considering this is a subgradient method, one can always choose the best iterate over training) than SGD, although SGD finds a slightly better solution. However, when the number of hidden neurons increases, DANTE starts getting consistently better. This can be attributed to the fact that the subproblem is relatively more challenging for an alternating optimization setting when the number of hidden neurons is lesser. Multi-Layer Autoencoder: We also studied the performance of the proposed multi-layer DANTE method (Algorithm 3) for the MNIST dataset. Figure 6 shows the results obtained by stacking two single-layer autoencoders, each with the generalized (leaky) ReLU activation (note that a two singlelayer autoencoder corresponds to 4 layers in the overall network, as mentioned in the architecture on the figure). The figure shows promising performance for DANTE in this experiment. Note that Figure 6b shows two spikes: one when the training for the next pair of layers in the autoencoder begins, and another when the end-to-end finetuning process is done. This is not present in Figure 6a , since the 500 → 500 layer in between is only randomly initialized, and is not trained using DANTE or SGD.

5. CONCLUSIONS AND FUTURE WORK:

In this work, we presented a novel methodology, Deep AlterNations for Training autoEncoders (DANTE), to efficiently train autoencoders using alternating minimization, thus providing an effective alternative to backpropagation. We formulated the task of training each layer of an autoencoder as a Strictly Locally Quasi-Convex (SLQC) problem, and leveraged recent results to use Stochastic Normalized Gradient Descent (SNGD) as an effective method to train each layer of the autoencoder.

While recent work was restricted to using sigmoidal activation functions, we introduced a new generalized ReLU activation function, and showed that a GLM with this activation function also satisfies the SLQC property, thus allowing us to expand the applicability of the proposed method to autoencoders with both sigmoid and ReLU family of activation functions. In particular, we extended the definitions of local quasi-convexity to use subgradients in order to prove that the GLM with generalized ReLU activation is , b 3 W 2a , w * -SLQC, which improves the convergence bound for SLQC in the GLM with the generalized ReLU (as compared to a GLM with sigmoid). We also showed how DANTE can be extended to train multi-layer autoencoders. We empirically validated DANTE with both sigmoidal and ReLU activations on standard datasets as well as in a multi-layer setting, and observed that it provides a competitive alternative to standard backprop-SGD, as evidenced in the experimental results.

Future Work and Extensions. DANTE can not only be used to train autoencoders, but can be extended to train standard multi-layer neural networks too. One could use DANTE to train a neural network layer-wise in a round robin fashion, and then finetune end-to-end using backprop-SGD. In case of autoencoders with tied weights, one could use DANTE to learn the weights of the required layers, and then finetune end-to-end using a method such as SGD. Our future work will involve a more careful study of the proposed method for deeper autoencoders, including the settings mentioned above, as well as in studying performance bounds for the end-to-end alternating minimization strategy for the proposed method.

A APPENDICES A.1 NOISY GLM WITH GENERALIZED RELU ACTIVATION FUNCTION:

The theorem below is a continuation of the discussion in Section 3.3 (see Theorem 3.5). We prove this result below. Theorem A.1. In the noisy GLM with generalized ReLU activation, assuming ||w * || ≤ W , given w ∈ B(0, W ), then with probability ≥ 1 -δ after m ≥ 288b 4 W 2 a 2 (1-W -1 ) 2 2 log(1/δ)/ 2 samples, êrr(w)

is , 2b 3 W a , w * -SLQC in w.

Proof. Here, ∀i, y i ∈ [0, 1], the following holds:

y i = φ w * , x + ξ i (6)

where {ξ i } m i=1 are zero mean, independent and bounded random variables, i.e. ∀i ∈ [m], ||ξ i || ≤ 1. Then, ê rr m (w) may be written as follows (expanding y i as in Eqn 6):

ê rr m (w) = 1 m m i=1 (y i -φ w, x i ) ) 2 = 1 m m i=1 (φ w * , x i -φ w, x i ) 2 + m i=1 2ξ i (φ w * , x i -φ w, x i ) + m i=1 ξ 2 i

Therefore, we also have (by definition of noisy GLM in Defn 3.2):

ê rr m (w) -ê rr m (w * ) = 1 m m i=1 (φ w * , x i -φ w, x i ) 2 + 1 m m i=1 2ξ i (φ w * , x i -φ w, x i )

Consider ||w|| ≤ W such that ê rr m (w) -ê rr m (w * ) ≥ . Also, let v be a point /κ-close to minima w * with κ = 2b 3 W a . Let g be the subgradient of the generalized ReLU activation and G be the subgradient of ê rr m (w), as before. Then:

G(w), w -v = 2 m m i=1 g w, x i (φ w, x i -y i ) x i , (w -v) = 2 m m i=1 g w, x i (φ w, x i -φ w * , x i -ξ i ) [ x i , w -w * + x i , w * -v ] (Step 1) ≥ 2b -1 m m i=1 g w, x i (φ w * , x i -φ w, x i ) 2 - 2 m m i=1 g w, x i ξ i ( w, x i -w * , x i ) + 2 m m i=1 g w, x i (φ w, x i -φ w * , x i -ξ i ) w * -v, x i ) (Step 2)

Here, λ i (w) = 2g w, x i ( w, x i -w * , x i ) -4ab -1 (φ w, x i -φ w * , x i ), and

|ξ i λ i (w)| ≤ 2b(| w, x i -w * , x i | + 4ab -1 |φ w, x i -φ w * , x i |) ≤ 2b(3| w, x i -w * , x i |) ≤ 2b(6W ) = 12bW

The above proof uses arguments similar to the proof for the idealized GLM (please see the lines after the proof of Theorem 3.4, viz. the b-Lipschitzness of the generalized ReLU, and the problem setup). Now, when

1 m m i=1 ξλ i (w) ≥ ab -1 W -1

our model is SLQC. By simply using the Hoeffding's bound, we get that the theorem statement holds for m ≥ 288b 4 W 4 a 2 2 log(1/δ)/ 2 .

A.2 VIEWING THE OUTER LAYER OF AN AUTOENCODER AS A SET OF GLMS:

Given an (unknown) distribution D, let the layer be characterized by a linear operator W ∈ R d×d and a non-linear activation function defined by φ : R → R. Let the layer output be defined by φ W, x , where x ∈ R d is the input, and φ is used element-wise in this function.

Consider the mean squared error loss, commonly used in autoencoders, given by: min

W err(W ) = min W E x∼D φ W, x -y 2 2 = min W E x∼D d i=1 φ W :,i , x -y i 2 2 = min W d i=1 E x∼D φ W :,i , x -y i 2 2 = d i=1 min W E x∼D φ W :,i , x -y i 2 2

Each of these sub-problems above is a GLM, which can be solved effectively using SNGD as seen in Theorem 3.6, which we leverage in this work.

A.3 LOCAL QUASI-CONVEXITY OF THE AUTOENCODER:

In Algorithm 2, while it is evident that each of the problems in Step 3 is a GLM and hence, SLQC, w.r.t. the corresponding parameters in W 2 , we show here that the complete layer in Step 3 is also SLQC w.r.t. W 2 , as well as show that the problem in Step 4 is SLQC w.r.t. W 1 . We begin with the definition of SLQC for matrices, which is defined using the Frobenius inner product.

Definition A.2 (Local-Quasi-Convexity for Matrices). Let x, z ∈ R d×d , κ, > 0 and let f : R d×d → R be a differentiable function. Then f is said to be ( , κ, z)-Strictly-Locally-Quasi-Convex (SLQC) in x, if at least one of the following applies:

1. f (x) -f (z) ≤ 2. ∇f (x) > 0, and ∀y ∈ B (z, /κ), T r(∇f (x) T (y -x)) ≤ 0

where B (z, /κ) refers to a ball centered at z with radius /κ.

We now prove that the ê rr(W) of a multi-output single-layer neural network is indeed SLQC in W. This corresponds to proving that the one-hidden layer autoencoder problem is SLQC in W 2 . We then go on to prove that a two layer single-output neural network is SLQC in the first layer W 1 , which can be trivially extended using the basic idea seen in Theorem A.4 to show that the one hidden-layer autoencoder problem is also SLQC in W 1 . , w * 1 -SLQC in w 1 for all w 1 ∈ B d (0, W 1 ).

Proof. Let f (w 1 ; w 2 ; x) -x 2 2 = φ 2 w 2 , φ 1 w 1 , xx 2 2 and • F be the Frobenius inner product.

G(w 1 ), w 1 -v 1 F = 2 m m i=1 (φ 2 w 2 , φ 1 w 1 , x i -y i ) ∂(φ 2 w 2 , φ 1 w 1 , x i ) ∂w 1 , (w 1 -v 1 ) F (Step 1)

Using chain rule, we can simplify ∂(φ2 w2,φ1 w1,x ) ∂w1 as

∂(φ 2 w 2 , φ 1 w 1 , x ) ∂w 1 T = ∂(φ 2 w 2 , φ 1 w 1 , x ) ∂ w 2 , φ 1 w 1 , x • ∂ w 2 , φ 1 w 1 , x ∂φ 1 w 1 , x T • ∂φ 1 w 1 , x ∂ w 1 , x i T T • ∂ w 1 , x ∂w 1 T = g 2 (w 1 , w 2 , x) • g 1 (w 1 , x) • w 2 • x T (Let)

Continuing from Step 1:

= 2 m m i=1 g 2 (w 1 , w 2 , x i ) (φ 2 w 2 , φ 1 w 1 , x i -y i ) x i w T 2 g 1 (w 1 , x i ) T , (w 1 -v 1 ) F = 2 m m i=1

g 2 (w 1 , w 2 , x i ) (φ 2 w 2 , φ 1 w 1 , x i -y i ) [ x i w T 2 g 1 (w 1 , x i ) T , (w 1 -w * 1 ) F + x i w T 2 g 1 (w 1 , x i ) T , (w * 1 -v 1 ) F ]

(Step 2) = 2 m m i=1 g 2 (w 1 , w 2 , x i ) (φ 2 w 2 , φ 1 w 1 , x i -y i ) [T r(g 1 (w 1 , x i )w 2 x T i (w 1 -w * 1 )) + T r(g 1 (w 1 , x i )w 2 x T i (w * 1 -v 1 )] = 2 m m i=1

g 2 (w 1 , w 2 , x i ) (φ 2 w 2 , φ 1 w 1 , x i -y i ) [T r(g 1 (w 1 , x i )w 2 x T i w 1 ) -T r(g 1 (w * 1 , x i )w 2 x T i w * 1 ) + T r((g 1 (w * 1 , x i ) -g 1 (w 1 , x i ))w 2 x T i w * 1 ) + T r(g 1 (w 1 , x i )w 2 x T i (w * 1 -v 1 ))] (

Step 3)

In order to convert the above terms into a more familiar form, we begin with the following observation:

w 2 , φ 1 w, x F = T r(g 1 (w, x)w 2 x T (w))

Also, note that g 1 (w, x) is a diagonal d × d matrix consisting of a's and b's on the diagonal:

( w 2 , φ 1 w 1 , xw 2 , φ 1 w, x ) = T r(g 1 (w 1 , x)w 2 x T w 1 ) -T r(g 1 (w, x)w 2 x T w)

:

http://yann.lecun.com/exdb/mnist/

Figures and Tables:

Theorem 3.6(Hazan et al. (2015)). Let , δ, G, M, κ > 0, let f : R d → R and w * = arg min w f (w). Assume that for b ≥ b 0 ( , δ, T ), with probability ≥ 1 -δ, f t defined in Algorithm 1 is ( , κ, w * )-SLQC ∀w, and|f t | ≤ M ∀t ∈ {1, • • • , T } . If we run SNGD with T ≥ κ 2 ||w1-w * || 2 2and η = κ , and b ≥ max

Figure1: An illustration of the proposed multi-layer DANTE (best viewed in color). In each training phase, the outer pairs of weights (shaded in gold) are treated as a single-layer autoencoder to be trained using single-layer DANTE, followed by the inner single-layer auroencoder (shaded in black). These two phases are followed by a finetuning process that may be empirically determined, similar to standard deep autoencoder training.

Figure 2: Plots of training and test errors vs training iterations for single hidden-layer autoencoder with Sigmoid (left) and Generalized ReLU (right) activations for both DANTE and SGD.

Figure 3: Reconstructions using autoencoder models with ReLU activation. Top: Original Images; Middle:Model trained using DANTE; Bottom: Model trained using Backprop-SGD.

Figure 4: Comparison of DANTE vs Backprop-SGD on other datasets from the UCI repository. The x-axis on all figures is the number of mini-batch iterations and y-axis denotes test error, which shows the generalization performance. (Best viewed in color; DANTE = purple, SGD = green)

Figure 6: Plots of training error and test error vs training iterations for multi-layer autoencoders with generalized (leaky) ReLU activations for both DANTE and SGD.

Theorem A.3. Let an idealized single-layer multi-output neural network be characterized by a linear operatorW ∈ R d×d = [w 1 w 2 • • • w d ]and a generalized ReLU activation function φ : R → R. Let the output of the layer be φ W, x where x ∈ R d is the input, and φ is applied element-wise.Assuming ||W * || ≤ C, ê rr(W) is , 2b 3 C a , W * -SLQC in W for all W ∈ B d (0, C). j ), w j -v j (By defn of Frobenius inner product) j , x i -y ij ) ∂(φ w j , x i ) ∂w j , (w j -v j ) F (j , x i ) (φ w j , x i -y ij ) [ x i , w j -w * j + x i , w * j -v j F ] w j , x i b -1 φ w j , x i -φ w * j , x i 2 + φ w j , x i -φ w * j x i x i , w * j -, x i (b -1 φ w j , x i -φ w * j ,x i 2 -|φ w j , x i -φ w * j ,x i |||x i ||||w * jφ w j , x i -φ w * j , x i 2 -b|φ w j , x i -φ w * j ,x i |||x i ||||w * j -v j || (Step 4) φ w j , x i -φ w * j , x i 2 -b 2 || w j , x i -w * j ,x i || κ ||x i || (Step 5) ≥ 2ab -1 d -ad bC || w, x i -w * ,x i ||||x i || (Step 6) ≥ ab -1 d (2 -1 C ||w -w * ||||x i || 2 ) ≥The remainder of the proof proceeds precisely as in Theorem 3.4.Theorem A.4. Let an idealized two-layer neural network be characterized by a linear operatorw 1 ∈ R d×d , w 2 ∈ R d andgeneralized ReLU activation functions φ 1 : R d → R d , φ 2 : R → R with a setting similar to Equation 5. Assuming ||w * 1 || ≤ W 1 , ||w * 2 || ≤ W 2 , ê rr(w 1 , w 2 ) is ,

Algorithm 2: DANTE: Deep AlterNations for Training autoEncoders Input :Stopping threshold , Number of iterations of alternating minimization T AM , Number of iterations for SNGD T SN GD , initial values W 0 1 , W 0 2 , learning rate η, minibatch size b

Table content: <table/>



Table content: <table><tr><td/><td>DANTE</td><td>SGD</td></tr><tr><td>MNIST</td><td>93.6%</td><td>92.44%</td></tr><tr><td colspan="3">ionosphere 92.45% 96.22%</td></tr><tr><td colspan="3">svmguide4 87.65% 70.37%</td></tr><tr><td>USPS</td><td colspan="2">90.43% 89.49%</td></tr><tr><td>vehicle</td><td colspan="2">77.02% 74.80%</td></tr></table>

Peer review (iclr2018):
 After reading the rebuttal: The authors addressed some of my theoretical questions. I think the paper is borderline, leaning towards accept. I do want to note my other concerns: I suspect the theoretical results obtained here are somewhat restricted to the least-squares, autoencoder loss. And note that the authors show that the proposed algorithm performs comparably to SGD, but not significantly better. The classification result (Table 1) was obtained on the autoencoder features instead of training a classifier on the original inputs. So it is not clear if the proposed algorithm is better for training the classifier, which may be of more interest. ============================================================= This paper presents an algorithm for training deep neural networks. Instead of computing gradient of all layers and perform updates of all weight parameters at the same time, the authors propose to perform alternating optimization on weights of individual layers. The theoretical justification is obtained for single-hidden-layer auto-encoders. Motivated by recent work by Hazan et al 2015, the authors developed the local-quasi-convexity of the objective w.r.t. the hidden layer weights for the generalized RELU activation. As a result, the optimization problem over the single hidden layer can be optimized efficiently using the algorithm of Hazan et al 2015. This itself can be a small, nice contribution. What concerns me is the extension to multiple layers. Some questions are not clear from section 3.4: 1. Do we still have local-quasi-convexity for the weights of each layer, when there are multiple nonlinear layers above it? A negative answer to this question will somewhat undermine the significance of the single-hidden-layer result. 2. Practically, even if the authors can perform efficient optimization of weights in individual layers, when there are many layers, the alternating optimization nature of the algorithm can possibly result in overall slower convergence. Also, since the proposed algorithm still uses gradient based optimizers for each layer, computing the gradient w.r.t. lower layers (closer to the inputs) are still done by backdrop, which has pretty much the same computational cost of the regular backdrop algorithm for updating all layers at the same time. As a result, I am not sure if the proposed algorithm is on par with / faster than the regular SGD algorithm in actual runtime. In the experiments, the authors plotted the training progress w.r.t. the minibatch iterations, I do not know if the minibatch iteration is a proxy for actual runtime (or number of floating point operations). 3. In the experiments, the authors found the network optimized by the proposed algorithm generalize better than regular SGD. Is this result consistent (across dataset, random initializations, etc), and can the authors elaborate the intuition behind?