On the Implicit Bias of Dropout

Introduction

Besides explicit regularization techniques, practitioners have used a spectrum of algorithmic approaches to improve the generalization ability of over-parametrized models. This includes early stopping of back-propagation (Caruana et al., 2001), batch normalization (Ioffe and Szegedy, 2015) and dropout (Srivastava et al., 2014). In particular, dropout, which is the focus of this paper, randomly drops hidden nodes along with their connections at training time. Dropout was introduced by Srivastava et al. (2014) as a way of breaking up co-adaptation among neurons, drawing insights from the success of the sexual reproduction model in the evolution of advanced organisms. While dropout has enjoyed tremendous success in training deep neural networks, the theoretical understanding of how dropout (and other algorithmic heuristics) provide regularization in deep learning remains somewhat limited.

A natural learning algorithm to consider is back-propagation with dropout, which can be seen as an instance of stochastic gradient descent on the following objective:

where the expectation is w.r.t. the underlying distribution on data as well as randomization due to dropout (each hidden unit is dropped independently with probability $1-\theta$). This procedure, which we simply refer to as dropout in this paper, is given in Algorithm 1.

It is easy to check (see Lemma A.1 in the supplementary) that the objective in equation (1) can be written as

where $\lambda=\frac{1-\theta}{\theta}$ is the regularization parameter, and ${\textrm{u}}_{i}$ and ${\textrm{v}}_{i}$ represent the $i^{\text{th}}$ columns of U and V, respectively. Note that while the goal was to minimize the expected squared loss, using dropout with gradient descent amounts to finding a minimum of the objective in equation (2); we argue that the additional term in the objective serves as a regularizer, $R(\textrm{U},\textrm{V}):=\lambda\sum_{i=1}^{r}{\|{\textrm{u}}_{i}\|^{2}\|{\textrm{v}}_{i}\|^{2}}$, and is an explicit instantiation of the implicit bias of dropout. Furthermore, we note that this regularizer is closely related to path regularization which is given as the square-root of the sum over all paths, from input to output, of the product of the squared weights along the path (Neyshabur et al., 2015). Formally, for a single layer network, path regularization is given as

Interestingly, the dropout regularizer is equal to the square of the path regularizer, i.e. $R(\textrm{U},\textrm{V})=\lambda\psi_{2}^{2}(\textrm{U},\textrm{V})$. While this observation is rather immediate, it has profound implications owing to the fact that path regularization provides size-independent capacity control in deep learning, thereby supporting empirical evidence that dropout finds good solutions in over-parametrized settings.

In this paper, we focus on studying the optimization landscape of the objective in equation (2) for a single hidden-layer linear network with dropout and the special case of an autoencoder with tied weights. Furthermore, we are interested in characterizing the solutions to which dropout (i.e. Algorithm 1) converges. We make the following progress toward addressing these questions.

Despite the non-convex nature of the problem, we completely characterize the global optima by giving necessary and sufficient conditions for optimality.

We describe the optimization landscape of the dropout problem. In particular, we show that for a sufficiently small dropout rate, all local minima of the objective in equation (2) are global and all saddle points are non-degenerate. This allows Algorithm 1 to efficiently escape saddle points and converge to a global optimum.

The rest of the paper is organized as follows. In Section 2, we study dropout for single hidden-layer linear auto-encoder networks with weights tied between the first and the second layers. This gives us the tools to study the dropout problem in a more general setting of single hidden-layer linear networks in Section 3. In Section 4, we characterize the optimization landscape of the objective in (2), show that it satisfies the strict saddle property, and that there are no spurious local minima. We specialize our results to matrix factorization in Section 5, and in Section 6, we discuss preliminary experiments to support our theoretical results.

Linear autoencoders with tied weights

We begin with a simpler hypothesis family of single hidden-layer linear auto-encoders with weights tied such that $\textrm{U}=\textrm{V}$. Studying the problem in this setting helps our intuition about the implicit bias that dropout induces on weight matrices U. This analysis will be extended to the more general setting of single hidden-layer linear networks in the next section.

so that applying a rotation matrix to a candidate solution U does not change the value of the loss function. However, the regularizer is not rotation-invariant and clearly depends on the choice of Q. Therefore, in order to solve Problem (4), we need to find a rotation matrix that minimizes the value of the regularizer for a given weight matrix.

where the inequality follows from Cauchy-Schwartz inequality. Hence, the regularizer is lower bounded by $\frac{\lambda}{r}\|\textrm{U}\|_{F}^{4}$, with equality if and only if ${\textrm{n}}_{\textrm{u}}$ is parallel to $\textrm{1}_{r}$, i.e. when all the columns of U have equal norms. Since the loss function is rotation invariant, one can always decrease the value of the overall objective by rotating U such that UQ has a smaller regularizer. A natural question to ask, therefore, is if there always exists a rotation matrix Q such that the matrix UQ has equal column norms. In order to formally address this question, we introduce the following definition.

A weight matrix U is said to be equalized if all its columns have equal norms. An autoencoder with tied weights is said to be equalized if the norm of the incoming weight vector is equal across all hidden nodes in the network. An orthogonal transformation Q is said to be an equalizer of U (equivalently, of the corresponding autoencoder) if UQ is equalized.

Next, we show that any matrix U can be equalized.

The key insight here is that if $\textrm{G}_{\textrm{U}}:=\textrm{U}^{\top}\textrm{U}$ is the Gram matrix associated with the weight matrix U, then $h_{\textrm{U},\textrm{U}}$ is equalized by Q if and only if all diagonal elements of $\textrm{Q}^{\top}\textrm{G}_{\textrm{U}}\textrm{Q}$ are equal. More importantly, if $\textrm{G}_{\textrm{U}}=\textrm{V}\Lambda\textrm{V}^{\top}$ is an eigendecomposition of $\textrm{G}_{\textrm{U}}$, then for ${\textrm{w}}=\frac{1}{\sqrt{r}}\sum_{i=1}^{r}{{\textrm{v}}_{i}}$, it holds that ${\textrm{w}}^{\top}\textrm{G}_{\textrm{U}}{\textrm{w}}=\frac{\operatorname*{Tr}\textrm{G}_{\textrm{U}}}{r}$; Proof of Theorem 2.2 uses this property to recursively equalize all diagonal elements of $\textrm{G}_{\textrm{U}}$.

Finally, we argue that the implicit bias induced by dropout is closely related to the notion of equalized network introduced above. In particular, our main result of the section states that the dropout enforces any globally optimal network to be equalized. Formally, we show the following.

If U is a global optimum of Problem 4, then U is equalized. Furthermore, it holds that

Theorem 2.3 characterizes the effect of regularization induced by dropout in learning autoencoders with tied weights. It states that for any globally optimal network, the columns of the corresponding weight matrix have equal norms. In other words, dropout tends to give equal weights to all hidden nodes – it shows that dropout implicitly biases the optimal networks towards having hidden nodes with limited overall influence rather than a few important ones.

While Theorem 2.3 makes explicit the bias of dropout and gives a necessary condition for global optimality in terms of the weight matrix $\textrm{U}_{*}$, it does not characterize the bias induced in terms of the network (i.e. in terms of $\textrm{U}_{*}\textrm{U}_{*}^{\top}$). The following theorem completes the characterization by describing globally optimal autoencoder networks. Since the goal is to understand the implicit bias of dropout, we specify the global optimum in terms of the true concept, M.

For any $j\in[r]$, let $\kappa_{j}:=\frac{1}{j}\sum_{i=1}^{j}{\lambda_{i}(\textrm{M})}$. Furthermore, define $\rho:=\max\{j\in[r]:\ \lambda_{j}(\textrm{M})>\frac{\lambda j\kappa_{j}}{r+\lambda j}\}$. Then, if $\textrm{U}_{*}$ is a global optimum of Problem 4, it satisfies that $\textrm{U}_{*}\textrm{U}_{*}^{\top}=\mathcal{S}_{\frac{\lambda\rho\kappa_{\rho}}{r+\lambda\rho}}\left(\textrm{M}\right)$.

In light of Theorem 2.3, the proof of Theorem 2.4 entails solving the following optimization problem

Single hidden-layer linear networks

Next, we consider the more general setting of a shallow linear network with a single hidden layer. Recall, that the goal is to find weight matrices $\textrm{U},\textrm{V}$ that solve

As a result of rescaling invariance, $f(\bar{\textrm{U}},\bar{\textrm{V}})=f(\textrm{U},\textrm{V})$. Now, following similar arguments as in the previous section, we define ${\textrm{n}}_{{\textrm{u}},{\textrm{v}}}=(\|{\textrm{u}}_{1}\|\|{\textrm{v}}_{1}\|,\ldots,\|{\textrm{u}}_{r}\|\|{\textrm{v}}_{r}\|)$, and note that

where the inequality is due to Cauchy-Schwartz, and the lower bound is achieved if and only if ${\textrm{n}}_{{\textrm{u}},{\textrm{v}}}$ is a scalar multiple of $\textrm{1}_{r}$, i.e. iff $\|{\textrm{u}}_{i}\|\|{\textrm{v}}_{i}\|=\|{\textrm{u}}_{1}\|\|{\textrm{v}}_{1}\|$ for all $i=1,\ldots,r$. This observation motivates the following definition.

Theorem 3.3 implies that for any network $h_{\textrm{U},\textrm{V}}$ there exists an equalized network $h_{\bar{\textrm{U}},\bar{\textrm{V}}}$ such that $h_{\bar{\textrm{U}},\bar{\textrm{V}}}=h_{\textrm{U},\textrm{V}}$. Hence, it is always possible to reduce the objective by equalizing the network, and a network $h_{\textrm{U},\textrm{V}}$ is globally optimal only if it is equalized.

If $(\textrm{U},\textrm{V})$ is a global optimum of Problem 6, then $\textrm{U},\textrm{V}$ are jointly equalized. Furthermore, it holds that

As in the case of autoencoders with tied weights in Section 2, a complete characterization of the implicit bias of dropout is given by considering the global optimality in terms of the network, i.e. in terms of the product of the weight matrices $\textrm{U}\textrm{V}^{\top}$. Not surprisingly, even in the case of single hidden-layer networks, dropout promotes sparsity, i.e. favors low-rank weight matrices.

For any $j\in[r]$, let $\kappa_{j}:=\frac{1}{j}\sum_{i=1}^{j}{\lambda_{i}(\textrm{M})}$. Furthermore, define $\rho:=\max\{j\in[r]:\ \lambda_{j}(\textrm{M})>\frac{\lambda j\kappa_{j}}{r+\lambda j}\}$. Then, if $(\textrm{U}_{*},\textrm{V}_{*})$ is a global optimum of Problem 6, it satisfies that $\textrm{U}_{*}\textrm{V}_{*}^{\top}=\mathcal{S}_{\frac{\lambda\rho\kappa_{\rho}}{r+\lambda\rho}}(\textrm{M})$.

Geometry of the Optimization Problem

While the focus in Section 2 and Section 3 was on understanding the implicit bias of dropout in terms of the global optima of the resulting regularized learning problem, here we focus on computational aspects of dropout as an optimization procedure. Since dropout is a first-order method (see Algorithm 1) and the landscape of Problem 4 is highly non-convex, we can perhaps only hope to find a local minimum, that too provided if the problem has no degenerate saddle points (Lee et al., 2016; Ge et al., 2015). Therefore, in this section, we pose the following questions: What is the implicit bias of dropout in terms of local minima? Do local minima share anything with global minima structurally or in terms of the objective? Can dropout find a local optimum?

For the sake of simplicity of analysis, we focus on the case of autoencoders with tied weight as in Section 2. We show in Section 4.1 that (a) local minima of Problem 4 inherit the same implicit bias as the global optima, i.e. all local minima are equalized. Then, in Section 4.2, we show that for sufficiently small regularization parameter, (b) there are no spurious local minima, i.e. all local minima are global, and (c) all saddle points are non-degenerate (see Definition 4.2).

All local optima of Problem 4 are equalized, i.e. if U is a local optimum, then $\|{\textrm{u}}_{i}\|=\|{\textrm{u}}_{j}\|$ $\forall i,j\in[r].$

Lemma 4.1 unveils a fundamental property of dropout. As soon as we perform dropout in the hidden layer – no matter how small the dropout rate – all local minima become equalized.

2 Landscape properties

Next, we characterize the solutions to which dropout (i.e. Algorithm 1) converges. We do so by understanding the optimization landscape of Problem 4. Central to our analysis, is the following notion of strict saddle property.

Strict saddle property ensures that for any critical point U that is not a local optimum, the Hessian has a significant negative eigenvalue which allows first order methods such as gradient descent (GD) and stochastic gradient descent (SGD) to escape saddle points and converge to a local minimum (Lee et al., 2016; Ge et al., 2015). Following this idea, there has been a flurry of works on studying the landscape of different machine learning problems, including low rank matrix recovery (Bhojanapalli et al., 2016), generalized phase retrieval problem (Sun et al., 2016), matrix completion (Ge et al., 2016), deep linear networks (Kawaguchi, 2016), matrix sensing and robust PCA (Ge et al., 2017) and tensor decomposition (Ge et al., 2015), making a case for global optimality of first order methods.

For the special case of no regularization (i.e. $\lambda=0$; equivalently, no dropout), Problem 4 reduces to standard squared loss minimization which has been shown to have no spurious local minima and satisfy strict saddle property (see, e.g. (Baldi and Hornik, 1989; Jin et al., 2017)). However, the regularizer induced by dropout can potentially introduce new spurious local minima as well as degenerate saddle points. Our next result establishes that that is not the case, at least when the dropout rate is sufficiently small.

For regularization parameter $\lambda<\frac{r\lambda_{r}(\textrm{M})}{\sum_{i=1}^{r}\lambda_{i}(\textrm{M})-r\lambda_{r}(\textrm{M})}$, (a) all local minima of Problem 4 are global, and (b) all saddle points are strict saddle points.

A couple of remarks are in order. First, Theorem 4.3 guarantees that any critical point U that is not a global optimum is a strict saddle point, i.e. $\nabla^{2}f(\textrm{U},\textrm{U})$ has a negative eigenvalue. This property allows first order methods, such as dropout given in Algorithm 1, to escape such saddle points. Second, note that the guarantees in Theorem 4.3 hold when the regularization parameter $\lambda$ is sufficiently small. Assumptions of this kind are common in the literature (see, for example (Ge et al., 2017)). While this is a sufficient condition for the result in Theorem 4.3, it is not clear if it is necessary.

Matrix Factorization with Dropout

which is identical to Problem 6. However, there are two key distinctions. First, we are interested in stochastic optimization problem whereas the matrix factorization problem is typically posed for a given matrix. Second, for the learning problem that we consider here, it is unreasonable to assume access to the true model (i.e. matrix M). Nonetheless, many of the insights we develop here as well as the technical results and algorithmic contributions apply to matrix factorization. Therefore, the goal in this section is to bring to bear the results in Sections 2, 3 and 4 to matrix factorization.

Finally, we note that Problem 7 is an instance of regularized matrix factorization which has recently received considerable attention in the machine learning literature (Ge et al., 2016, 2017; Haeffele and Vidal, 2017). These works show that the saddle points of a class of regularized matrix factorization problems have certain “nice” properties (i.e. escape directions characterized by negative curvature around saddle points) which allow variants of first-order methods such as perturbed gradient descent (Ge et al., 2015; Jin et al., 2017) to converge to a local optimum. Distinct from that line of research, we completely characterize the set of global optima of Problem 7, and provide a polynomial time algorithm to find a global optimum.

The work most similar to the matrix factorization problem we consider in this section is that of Cavazza et al. (2018), with respect to which we make several important contributions: (I) Cavazza et al. (2018) characterize optimal solutions only in terms of the product of the factors, and not in terms of the factors themselves, whereas we provide globally optimal solutions in terms of the factors; (II) Cavazza et al. (2018) require the rank $r$ of the desired factorization to be variable and above some threshold, whereas we consider fixed rank-$r$ factorization for any $r$; (III) Cavazza et al. (2018) can only find low rank solutions using an adaptive dropout rate, which is not how dropout is used in practice, whereas we consider any fixed dropout rate; and (IV) we give an efficient poly time algorithm to find optimal factors.

Empirical Results

Dropout is a popular algorithmic technique used for avoiding overfitting when training large deep neural networks. The goal of this section is not to attest to the already well-established success of dropout. Instead, the purpose of this section is to simply confirm the theoretical results we showed in the previous section, as a proof of concept.

We begin with a toy example in order to visually illustrate the optimization landscape. We use dropout to learn a simple linear auto-encoder with one-dimensional input and output (i.e. a network represented by a scalar $\textrm{M}=2$) and a single hidden layer of width $r=2$. The input features are sampled for a standard normal distribution. Figure 2 shows the optimization landscape along with the contours of the level sets, and a trace of iterates of dropout (Algorithm 1). The initial iterates and global optima (given by Theorem 2.4) are shown by red and green dots, respectively. Since at any global optimum the weights are equalized, the optimal weight vector in this case is parallel to the vector $(\pm 1,\pm 1)$. We see that dropout converges to a global minimum.

To verify that the solution found by dropout actually has equalized factors, we consider the following measure. At each iteration, we compute the “importance scores”, $\alpha_{t}^{(i)}=\|{{\textrm{u}}_{t}}_{i}\|\|{{\textrm{v}}_{t}}_{i}\|,\ i\in[r]$, where ${{\textrm{u}}_{t}}_{i}$ and ${{\textrm{v}}_{t}}_{i}$ are the $i$-th columns of $\textrm{U}_{t}$ and $\textrm{V}_{t}$, respectively. The rightmost panel of Figure 3 shows the variance of $\alpha_{t}^{(i)}$’s, over the hidden nodes $i\in[r]$, at each iterate $t$. Note that a high variance in $\alpha_{t}$ corresponds to large variation in the values of $\|{{\textrm{u}}_{t}}_{i}\|\|{{\textrm{v}}_{t}}_{i}\|$. When the variance is equal to zero, all importance scores are equal, thus the factors are equalized. We see that iterations of Algorithm 1 decrease this measure monotonically, and the larger the value of $\lambda$, the faster the weights become equalized.

Discussion

There has been much effort in recent years to understand the theoretical underpinnings of dropout (see Baldi and Sadowski (2013); Gal and Ghahramani (2016); Wager et al. (2013); Helmbold and Long (2015)). In this paper, we study the implicit bias of dropout in shallow linear networks. We show that dropout prefers solutions with minimal path regularization which yield strong capacity control guarantees in deep learning. Despite being a non-convex optimization problem, we are able to fully characterize the global optima of the dropout objective. Our analysis shows that dropout favors low-rank weight matrices that are equalized. This theoretical finding confirms that dropout as a procedure uniformly allocates weights to different subnetworks, which is akin to preventing co-adaptation.

We characterize the optimization landscape of learning autoencoders with dropout. We first show that the local optima inherit the same implicit bias as global optimal, i.e. all local optima are equalized. Then, we show that for sufficiently small dropout rates, there are no spurious local minima in the landscape, and all saddle points are non-degenerate. These properties suggest that dropout – as an optimization procedure – can efficiently converge to a globally optimal solution specified by our theorems.

Understanding dropout in shallow linear networks is a prerequisite for understanding dropout in deep learning. We see natural extensions of our results in two directions: 1) shallow networks with non-linear activation function such as rectified linear units (ReLU) which have been shown to enable faster training (Glorot et al., 2011) and are better understood in terms of the family of functions represented by ReLU-nets (Arora et al., 2018), and 2) exploring the global optimality in deeper networks, even for linear activations.

Acknowledgements

This research was supported in part by NSF BIGDATA grant IIS-1546482 and NSF grant IIS-1618485.

References

Appendix A Auxiliary Lemmas

In this section, we prove Lemma A.1 and a few auxiliary lemmas that we will need for the proofs of Theorem 2.4 and Theorem 3.6.

where we used the fact that ${\textrm{y}}=\textrm{M}{\textrm{x}}$. We have the following set of equalities for the second term on the right hand side of Equation (A):

Plugging Equations (A) and (11) into (A), we get

Lemma A.2 is an instance of the Woodbury’s matrix identity. Here, we include a proof for completeness.

The proof simply follows from the following set of equations.

Then $g(\rho)$ is monotonically non-increasing in $\rho$.

Let denote the sum of the top $\tau$ elements of a by ${\textrm{h}}_{\tau}=\sum_{i=1}^{\tau}{a_{i}}$. Furthermore, let the sum of squared of $\tau$ bottom elements of a be denoted by $t_{\tau}=\sum_{i=\tau+1}^{d}{a_{i}^{2}}$. We can simplify $g(\rho)$ and give it in terms of $h_{\rho}$ and $t_{\rho}$ as follows:

It suffices to show that $g(\rho+1)\leq g(\rho)$ for all $\rho\in[r-1]$.

Hence $g(\rho)$ is monotonically non-increasing in $\rho$. ∎

Appendix B Proofs of Theorems in Section 2

Consider the matrix $\textrm{G}_{1}:=\textrm{G}_{\textrm{U}}-\frac{\operatorname*{Tr}{\textrm{G}_{\textrm{U}}}}{r}\textrm{I}_{r}$. We exhibit an orthogonal transformation Q, such that $\textrm{Q}^{\top}\textrm{G}_{1}\textrm{Q}$ is zero on its diagonal. Observe that

so that all diagonal elements of $\textrm{G}_{\textrm{U}}$ are equal to $\frac{\operatorname*{Tr}{\textrm{G}_{\textrm{U}}}}{r}$, i.e. $\textrm{G}_{\textrm{U}}$ is equalized.

Our construction closely follows the proof of a classical theorem in matrix analysis, which states that any trace zero matrix is a commutator [Albert and Muckenhoupt, 1957, Kahan, 1999]. For the zero trace matrix $\textrm{G}_{1}$, we first show that there exists a unit vector ${\textrm{w}}_{11}$ such that ${\textrm{w}}_{11}^{\top}\textrm{G}_{1}{\textrm{w}}_{11}=0$.

Assume G is a zero trace matrix and let $\textrm{G}=\sum_{i=1}^{r}{\lambda_{i}{\textrm{u}}_{i}{\textrm{u}}_{i}^{\top}}$ be an eigendecomposition of G. Then ${\textrm{w}}=\frac{1}{\sqrt{r}}\sum_{i=1}^{r}{{\textrm{u}}_{i}}$ has a vanishing Rayleigh quotient, that is, ${\textrm{w}}^{\top}\textrm{G}{\textrm{w}}=0$, and $\|{\textrm{w}}\|=1$.

It is easy to see that w has a zero Rayleigh quotient

Let $\textrm{W}_{1}:=[{\textrm{w}}_{11},{\textrm{w}}_{12},\cdots,{\textrm{w}}_{1d}]$ be such that $\textrm{W}_{1}^{\top}\textrm{W}_{1}=\textrm{W}_{1}\textrm{W}_{1}^{\top}=\textrm{I}_{d}$. Observe that $\textrm{W}_{1}^{\top}\textrm{G}_{1}\textrm{W}_{1}$ has zero on its first diagonal elements

This procedure can be applied recursively so that for the equalizer $\textrm{Q}=\textrm{W}_{1}\textrm{W}_{2}\cdots\textrm{W}_{d}$ we have

Let us denote the squared column norms of U by ${\textrm{n}}_{\textrm{u}}=(\|{\textrm{u}}_{1}\|^{2},\ldots,\|{\textrm{u}}_{r}\|^{2})$. Observe that for any weight matrix U:

By Theorem 2.3, if W is an optimum of Problem 4, then it holds that $\lambda\sum_{i=1}^{r}{\|{\textrm{w}}_{i}\|^{4}}=\frac{\lambda}{r}\|\textrm{W}\|_{F}^{4}$. Also, by Theorem 2.2, it is always possible to equalize any given weight matrix. Hence, Problem 4 reduces to the following problem:

Let $\textrm{M}=\textrm{U}_{\textrm{M}}\Lambda_{\textrm{M}}\textrm{U}_{\textrm{M}}^{\top}$ and $\textrm{W}=\textrm{U}_{\textrm{W}}\Sigma_{\textrm{W}}\textrm{V}_{\textrm{W}}^{\top}$ be an eigendecomposition of M and a full SVD of W respectively, such that $\lambda_{i}(\textrm{M})\geq\lambda_{i+1}(\textrm{M})$ and $\sigma_{i}(\textrm{W})\geq\sigma_{i+1}(\textrm{W})$ for all $i\in[d-1]$. Rewriting objective of Problem 13 in terms of these decompositions gives:

where $\Lambda_{\textrm{W}}:=\Sigma_{\textrm{W}}\Sigma_{\textrm{W}}^{\top}$ and $\textrm{U}^{\prime}=\textrm{U}_{\textrm{M}}^{\top}\textrm{U}_{\textrm{W}}$. By Von Neumann’s trace inequality, for a fixed $\Sigma_{\textrm{W}}$ we have that

where the equality is achieved when $\Lambda_{i}(\textrm{W})$ have the same ordering as $\Lambda_{i}(\textrm{M})$ and $\textrm{U}^{\prime}=\textrm{I}$, i.e. $\textrm{U}_{\textrm{M}}=\textrm{U}_{\textrm{W}}$. Now, Problem 13 is reduced to

The KKT conditions ensures that at the optima it holds for all $i\in[r]$ that

Let $\rho=|{i:\bar{\lambda}_{i}>0}|\leq r$ be the number of nonzero $\bar{\lambda}_{i}$. For $i=1,\ldots,\rho$ we have $\alpha_{i}=0$, hence

where $\kappa_{\rho}:=\frac{1}{\rho}\sum_{i=1}^{\rho}{\lambda_{i}(\textrm{M})}$ and the second implication is due to Lemma A.2. It only remains to find the optimal $\rho$. Let’s define the function

By Lemma A.3, $g(\rho)$ is monotonically non-increasing in $\rho$, hence $\rho$ should be the largest feasible integer, i.e.

It remains to show that for any diagonal matrix D, $\textrm{Z}_{k}^{\top}\textrm{D}\textrm{Z}_{k}$ is diagonalized. First note that

so that $\textrm{Z}_{2}$ is indeed a rotation. By induction, it is easy to see that $\textrm{Z}_{k}$ is a rotation for all $k$. Now, we show that $\textrm{Z}_{k}$ equalizes any diagonal matrix D. Observe that

so that all the diagonal elements are identically equal to the average of the diagonal elements of D. ∎

Appendix C Proofs of Theorems in Section 3

where the inequality is due to Cauchy-Schwartz, and it holds with equality if and only if ${\textrm{n}}_{{\textrm{u}},{\textrm{v}}}$ is parallel to $\textrm{1}_{r}$. Let $(\bar{\textrm{U}},\bar{\textrm{V}})$ be a global optima of Problem 6. The inequality above together with Theorem 3.3 imply that $\bar{\textrm{U}}$ and $\bar{\textrm{V}}$ should be jointly equalized up to dilation transformations, hence the first equality claimed by the theorem.

To see the second equality, note that if U and V are jointly equalized, then

where $\Sigma$ is the matrix of singular values of $\textrm{U}\textrm{V}^{\top}$. Hence,

which is equal to $\frac{\lambda}{r}\|\bar{\textrm{U}}\bar{\textrm{V}}^{\top}\|_{*}^{2}$ as claimed. ∎

By Theorem 3.4, if $(\textrm{X},\textrm{Y})$ is an optimum of Problem 6, then it holds that

Hence, Problem 6 reduces to the following problem:

Let $\textrm{M}=\textrm{U}_{\textrm{M}}\Sigma_{\textrm{M}}\textrm{V}_{\textrm{M}}^{\top}$ and $\textrm{W}:=\textrm{X}\textrm{Y}^{\top}=\textrm{U}_{\textrm{W}}\Sigma_{\textrm{W}}\textrm{V}_{\textrm{W}}^{\top}$ be full SVDs of M and W respectively, such that $\sigma_{i}(\textrm{M})\geq\sigma_{i+1}(\textrm{M})$ and $\sigma_{i}(\textrm{W})\geq\sigma_{i+1}(\textrm{W})$ for all $i\in[d-1]$ where $d=\min\{d_{1},d_{2}\}$. Rewriting objective of Problem 14 in terms of these decompositions,

where $\textrm{U}^{\prime}=\textrm{U}_{\textrm{M}}^{\top}\textrm{U}_{\textrm{W}}$. By Von Neumann’s trace inequality, for a fixed $\Sigma_{\textrm{W}}$ we have that $\langle\Sigma_{\textrm{M}},\textrm{U}^{\prime}\Sigma_{\textrm{W}}\textrm{U}^{\prime\top}\rangle\leq\sum_{i=1}^{d}{\sigma_{i}(\textrm{M})\sigma_{i}(\textrm{W})}$, where the equality is achieved when $\Sigma_{i}(\textrm{W})$ have the same ordering as $\Sigma_{i}(\textrm{M})$ and $\textrm{U}^{\prime}=\textrm{I}$, i.e. $\textrm{U}_{\textrm{M}}=\textrm{U}_{\textrm{W}}$. Now, Problem 14 is reduced to

The KKT conditions ensures that $\forall i=1,\ldots,r$,

Let $\rho=|{i:\bar{\sigma}_{i}>0}|\leq r$ be the number of nonzero $\bar{\sigma}_{i}$. For $i=1,\ldots,\rho$ we have $\alpha_{i}=0$, hence

where $\kappa_{\rho}=\frac{1}{\rho}\sum_{i=1}^{\rho}{\sigma_{i}(\textrm{M})}$ and the second implication holds since $(\textrm{I}_{\rho}+\frac{\lambda}{r}\textrm{1}\textrm{1}^{\top})^{-1}=\textrm{I}_{\rho}-\frac{\lambda}{r+\lambda\rho}\textrm{1}\textrm{1}^{\top}$. It only remains to find the optimal $\rho$. Let’s define the function

By Lemma A.3, $g(\rho)$ is monotonically non-increasing in $\rho$, hence $\rho$ should be the largest feasible integer, i.e.

Appendix D Proofs of Theorems in Sections 4

It is easy to see that the gradient of the objective of Problem 4 is given by

We first make the following important observation about the critical points of Problem 4.

If U is a critical point of Problem 4, then it holds that $\textrm{U}\textrm{U}^{\top}\preceq\textrm{M}$.

Since $\nabla f(\textrm{U})={\textrm{0}}$, we have that

multiply both sides from right by $\textrm{U}^{\top}$ and rearrange to get

Note that the right hand side is symmetric, which implies that the left hand side must be symmetric as well, i.e.

so that M and $\textrm{U}\textrm{U}^{\top}$ commute. Note that in Equation (15), $\textrm{U}\operatorname*{diag}(\textrm{U}^{\top}\textrm{U})\textrm{U}^{\top}\succeq{\textrm{0}}$. Thus, $\textrm{M}\textrm{U}\textrm{U}^{\top}\succeq\textrm{U}\textrm{U}^{\top}\textrm{U}\textrm{U}^{\top}$. Let $\textrm{U}\textrm{U}^{\top}=\textrm{W}\Gamma\textrm{W}^{\top}$ be a compact eigendecomposition of $\textrm{U}\textrm{U}^{\top}$. We get

Multiplying from right and left by $\textrm{W}\Gamma^{-1}$ and $\textrm{W}^{\top}$ respectively, we have that

Lemma D.1 allows us to bound different norms of the critical points, as will be seen later in the proofs.

To explore the landscape properties of Problem 4, we first focus on the non-equalized critical points in Lemma D.2. We show that the set of non-equalized critical points does not include any local optima. Furthermore, all such points are strict saddles. Therefore, we turn our focus to the equalized critical points in Lemma D.3. We show all such points inherit the eigenspace of the input matrix M. This allows us to give a closed-form characterization of all the equalized critical points in terms of the eigendecompostion of M. We then show that if $\lambda$ is chosen appropriately, all such critical points that are not global optima, are strict saddle points.

All local minima of Problem 4 are equalized. Moreover, all critical points that are not equalized, are strict saddle points.

We show that if U is not equalized, then any $\epsilon$-neighborhood of U contains a point with objective strictly smaller than $f(\textrm{U})$. More formally, for any $\epsilon>0$, we exhibit a rotation $\textrm{Q}_{\epsilon}$ such that $\|\textrm{U}-\textrm{U}\textrm{Q}_{\epsilon}\|_{F}\leq\epsilon$ and $f(\textrm{U}\textrm{Q}_{\epsilon})<f(\textrm{U})$. Let U be a critical point of Problem 4 that is not equalized, i.e. there exists two columns of U with different norms. Without loss of generality, let $\|{\textrm{u}}_{1}\|>\|{\textrm{u}}_{2}\|$. We design a rotation matrix Q such that it is almost an isometry, but it moves mass from ${\textrm{u}}_{1}$ to ${\textrm{u}}_{2}$. Consequently, the new factor becomes “less un-equalized” and achieves a smaller regularizer, while preserving the value of the loss. To that end, define

and let $\hat{\textrm{U}}:=\textrm{U}\textrm{Q}_{\delta}.$ It is easy to verify that $\textrm{Q}_{\epsilon}$ is indeed a rotation. First, we show that for any $\epsilon$, as long as $\delta^{2}\leq\frac{\epsilon^{2}}{2\operatorname*{Tr}(\textrm{M})}$, we have $\hat{\textrm{U}}\in\mathcal{B}_{\epsilon}(\textrm{U})$:

where the second to last inequality follows from Lemma D.1, because $\|{\textrm{u}}_{1}\|^{2}+\|{\textrm{u}}_{2}\|^{2}\leq\|\textrm{U}\|_{F}^{2}=\operatorname*{Tr}(\textrm{U}\textrm{U}^{\top})\leq\operatorname*{Tr}(\textrm{M})$, and also the fact that $1-\sqrt{1-\delta^{2}}=\frac{1-1+\delta^{2}}{1+\sqrt{1-\delta^{2}}}\leq\delta^{2}$.

Next, we show that for small enough $\delta$, the value of the function at $\hat{\textrm{U}}$ is strictly smaller than that of U. Observe that

and the remaining columns will not change, i.e. for $i=3,\cdots,r$, $\hat{\textrm{u}}_{i}={\textrm{u}}_{i}$. Together with the fact that $\textrm{Q}_{\delta}$ preserves the norms, i.e. $\|\textrm{U}\|_{F}=\|\textrm{U}\textrm{Q}_{\delta}\|_{F}$, we get

We now prove the second part of the lemma. Let U be a critical point that is not equalized. To show that U is a strict saddle point, it suffices to show that the Hessian has a negative eigenvalue. In here, we exhibit a curve along which the second directional derivative is negative. Assume, without loss of generality that $\|{\textrm{u}}_{1}\|>\|{\textrm{u}}_{2}\|$ and consider the curve

Since U is a critical point and $f$ is continuously differentiable, it should hold that $g^{\prime}(0)=4({\textrm{u}}_{1}^{\top}{\textrm{u}}_{2})(\|{\textrm{u}}_{1}\|^{2}-\|{\textrm{u}}_{2}\|^{2})=0$. Since by assumption $\|{\textrm{u}}_{1}\|^{2}-\|{\textrm{u}}_{2}\|^{2}>0$, it should be the case that ${\textrm{u}}_{1}^{\top}{\textrm{u}}_{2}=0$. We now consider the second order directional derivative:

We now focus on the critical points that are equalized, i.e. points U such that $\nabla f(\textrm{U})={\textrm{0}}$ and $\operatorname*{diag}(\textrm{U}^{\top}\textrm{U})=\frac{\|\textrm{U}\|_{F}^{2}}{r}\textrm{I}$.

Assume that $\lambda<\frac{r\lambda_{r}}{\sum_{i=1}^{r}\lambda_{i}-r\lambda_{r}}$. Then all equalized local minima are global. All other equalized critical points are strict saddle points.

Let $\textrm{U}=\textrm{W}\Sigma\textrm{V}^{\top}$ be a compact SVD of the rank-$r^{\prime}$ weight matrix U. We have:

where $\sigma^{2}:=\operatorname*{diag}(\Sigma^{2})$ and $\vec{\lambda}=\operatorname*{diag}(\textrm{W}^{\top}\textrm{M}\textrm{W})$. By Lemma A.2, the solution to this linear system is given by

The set $\mathcal{E}$ belongs to one of the following categories:

$\mathcal{E}=[r^{\prime}],\ r^{\prime}=\rho$

$\mathcal{E}=[r^{\prime}],\ r^{\prime}<\rho$

The case $\mathcal{E}=[r^{\prime}],\ r^{\prime}>\rho$ is excluded from the above partition, since whenever $\mathcal{E}=[r^{\prime}]$, it should hold that $r^{\prime}\leq\rho$. To see this, note that due to $\textrm{U}=\textrm{W}\Sigma\textrm{V}^{\top}$ being a compact SVD of M, it holds that $\sigma_{j}>0$ for all $j\in[r^{\prime}]$. Specifically for $j=r^{\prime}$, plugging $\sigma_{r^{\prime}}>0$ back to Equation (17), we get

Then it follows from definition of $\rho$ in Theorem 2.4 that $r^{\prime}\leq\rho$. We provide a case by case analysis for the above partition here.

When W corresponds to the top-$\rho$ eigenvectors of M, we retrieve the global optimal solution described by Theorem 2.4. Therefore, all such critical points are global minima.

so that for all $t$, the parametric curve $\textrm{U}(t)$ is equalized. The value of the loss function at $\textrm{U}(t)$ is given by:

Furthermore, since $\textrm{U}(t)$ is equalized, we obtain the following form for the regularizer:

It is easy to verify that $g^{\prime}(0)=0$. Moreover, the second derivative of $g$ at the origin is given as:

where the last equality follows from the fact Equation (17) and the fact that $\|\textrm{U}\|_{F}^{2}=\sum_{i=1}^{r^{\prime}}{\sigma_{i}^{2}}$. To get a sufficient condition for U to be a strict saddle point, we set $g^{\prime\prime}(0)<0$:

where $h(r^{\prime}):=\frac{\sum_{i=r^{\prime}+1}^{r}{\lambda_{i}}}{r-r^{\prime}}$ is the average of the eigenvalues $\lambda_{r^{\prime}+1},\cdots,\lambda_{r}$. It is easy to see that the right hand side is monotonically decreasing with $r^{\prime}$, since $h(r^{\prime})$ monotonically decrease with $r^{\prime}$. Hence, it suffices to make sure that $\lambda$ is smaller than the right hand side for the choice of $r^{\prime}=r-1$, i.e. $\lambda<\frac{r\lambda_{r}}{\sum_{i=1}^{r}(\lambda_{i}-\lambda_{r})}$.

We show that all such critical points are strict saddle points. Let ${\textrm{w}}^{\prime}$ be one of the top $r^{\prime}$ eigenvectors that are missing in W. Let $j\in\mathcal{E}$ be such that ${\textrm{w}}_{j}$ is not among the top $r^{\prime}$ eigenvectors of M. For any $t\in$, let $\textrm{W}(t)$ be identical to W in all the columns but the $j^{\text{th}}$ one, where ${\textrm{w}}_{j}(t)=\sqrt{1-t^{2}}{\textrm{w}}_{j}+t{\textrm{w}}^{\prime}$. Note that $\textrm{W}(t)$ is still an orthogonal matrix for all values of $t$. Define the parametrized curve $\textrm{U}(t):=\textrm{W}(t)\Sigma\textrm{V}^{\top}$ for $t\in$ and observe that:

That is, for any $\epsilon>0$, there exist a $t>0$ such that $\textrm{U}(t)$ belongs to the $\epsilon$-ball around U. We show that $f(\textrm{U}(t))$ is strictly smaller than $f(\textrm{U})$, which means U cannot be a local minimum. Note that this construction of $\textrm{U}(t)$ guarantees that $R(\textrm{U}^{\prime})=R(\textrm{U})$. In particular, it is easy to see that $\textrm{U}(t)^{\top}\textrm{U}(t)=\textrm{U}^{\top}\textrm{U}$, so that $\textrm{U}(t)$ remains equalized for all values of $t$. Moreover, we have that