Global Optimality in Tensor Factorization, Deep Learning, and Beyond

Benjamin D. Haeffele; Rene Vidal

Source-linked AI summary

Global Optimality in Tensor Factorization, Deep Learning, and Beyond

Benjamin D. Haeffele, Rene Vidal

arXiv:1506.07540v1Jun 24, 2015math.NAcs.LGstat.ML

TL;DR

Factorization models are broadly useful but usually yield non-convex optimization problems because of multilinear or other convexity-destroying mappings. The paper develops a convex-analysis framework for these factorized problems and shows global-optimality and local-descent guarantees under structural conditions, with applications including matrix and tensor factorization and neural networks.

Problem
Factorization objectives are widely used but typically become non-convex through bilinear, multilinear, or other convexity-destroying mappings, while existing convex relaxations do not cover the full range of desired factor properties.
Method
The paper analyzes factorized models through convex output-space regularization and positively homogeneous mappings, allowing factor size to adapt through regularization.
Results
For models in the framework, local minima satisfying an all-zero slice condition are global minima, and sufficiently large factors permit reaching a global minimizer from any feasible initialization by local descent.
Takeaways & Limitations
The framework covers matrix and tensor factorization and certain neural-network formulations, and provides a partial theoretical explanation for using positively homogeneous nonlinearities such as ReLU.
Takeaways & Limitations
The guarantees are challenging to apply in practice and are limited for current state-of-the-art architectures because they require factor size to change or be initialized sufficiently large.

Abstract

from arXiv · show

Techniques involving factorization are found in a wide range of applications and have enjoyed significant empirical success in many fields. However, common to a vast majority of these problems is the significant disadvantage that the associated optimization problems are typically non-convex due to a multilinear form or other convexity destroying transformation. Here we build on ideas from convex relaxations of matrix factorizations and present a very general framework which allows for the analysis of a wide range of non-convex factorization problems - including matrix factorization, tensor factorization, and deep neural network training formulations. We derive sufficient conditions to guarantee that a local minimum of the non-convex optimization problem is a global minimum and show that if the size of the factorized variables is large enough then from any initialization it is possible to find a global minimizer using a purely local descent algorithm. Our framework also provides a partial theoretical justification for the increasingly common use of Rectified Linear Units (ReLUs) in deep neural networks and offers guidance on deep network architectures and regularization strategies to facilitate efficient optimization.

1. Introduction

Factorization models are widely used, but their bilinear, multilinear, or nonlinear mappings typically make optimization non-convex. The paper extends convex-relaxation ideas into a framework covering matrix and tensor factorization and neural-network training.

1. Introduction: Most factorization objectives remain non-convex because bilinear or multilinear mappings destroy convexity even when loss and regularization are convex.This applies to matrix and tensor formulations, including neural-network mappings with alternating linear and nonlinear operations.
1. Introduction: Convex nuclear-norm relaxations efficiently promote low rank but may not recover factors satisfying properties such as sparsity or non-negativity.They also do not directly provide the desired factors in the general constrained setting.
1. Introduction: The framework analyzes non-convex factorized problems directly while using convexity in the output representation, extending beyond standard matrix-factorization relaxations.Its scope includes matrix factorization, tensor factorization, and certain neural-network training formulations.
1.1 Generalized Factorization: Tensor factorization generalizes matrix factorization by combining K factor tensors through a multilinear map Φ to approximate an observed tensor.The resulting objective remains typically non-convex because of Φ.
1. Introduction: The paper shows that sufficiently large factorized variables permit reaching a global minimizer from any initialization through purely local descent.The contribution also establishes global optimality of local minima under a simple zero-slice condition.

2. Prior Work

Prior work developed convex and factorized approaches for matrix problems, but these methods do not fully address practical factorized objectives or broader tensor and neural-network models. This paper extends global-optimality guarantees to that wider family.

2. Prior Work: Existing optimization methods for factorization problems are generally guaranteed only to reach a critical point or local minimum.The cited methods include alternating minimization, gradient descent, stochastic gradient descent, block coordinate descent, back-propagation, and quasi-Newton methods.
2. Prior Work: The factorization norm ∥X∥u,v remains convex in X while allowing vector norms or gauge functions to promote structure in U and V.With l2 norms, it becomes the nuclear norm.
2. Prior Work: Under general conditions, some earlier factorized semidefinite-programming results show that local minima can be global minima.These results can reduce dimensionality but do not cover the more practically useful formulation addressed here.
2. Prior Work: The formulations in which every factorization of an optimal product is acceptable and those requiring a factorization attaining the regularizer’s infimum are not equivalent.The paper targets the latter, more useful family and extends guarantees to tensor factorization and selected neural-network models.
2. Prior Work: Related work connects variable-width, sparsity-regularized single-hidden-layer networks with selecting finitely many hidden units from an infinite-dimensional unit space.This provides context for adapting factorization ideas to neural-network training.

3. Preliminaries

The preliminaries establish notation for multidimensional tensor spaces, factor sets, slices, derivatives, and positive homogeneity. These definitions support the framework’s later treatment of factorized mappings and regularization.

3. Preliminaries: The framework uses capital letters for collections of dimensions and card(D) for their product cardinality.This notation permits a uniform treatment of vectors, matrices, and higher-order tensors.
3. Preliminaries: Tensor slices are indexed along the final dimension, and matching tensors can be concatenated along that dimension.For matrices, a slice is a column; for cubes, it is a third-mode slice.
3. Preliminaries: The notation defines tensor dot products through vectorization and distinguishes gradients, subgradients, images, Fenchel duals, and directional derivatives.These operators provide the analytical vocabulary for subsequent results.
3. Preliminaries: A size-r set of K factors consists of K tensors whose final dimension is r.The factors lie in a product of tensor spaces with shapes D_i×r.
3. Preliminaries: Positive homogeneity of degree p means jointly scaling all inputs by α scales the output by α^p for α≥0.For p≠0, the definition also implies the function vanishes at the all-zero input.
3. Preliminaries: Positive semidefiniteness requires a function to be nonnegative everywhere and zero at the all-zero input.This property is later used for elemental regularization functions.

4. Problem Formulation

The formulation represents outputs as sums of positively homogeneous elemental mappings over factor slices and regularizes the factors without fixing their size. This construction covers matrix, CP tensor, and several ReLU-network mappings while imposing scope limitations on some architectures and regularizers.

4.1 Factorization Mappings: The factorization mapping Φ_r sums an elemental mapping φ applied to corresponding slices from K factor tensors.The elemental mapping is required to be positively homogeneous, but need not be multilinear.
4.1 Factorization Mappings: Matrix multiplication and CP tensor decomposition arise as special cases of the elemental mapping framework.The CP case uses the tensor outer product x1⊗···⊗xK.
4.1 Factorization Mappings: ReLU networks fit the framework because rectification is positively homogeneous, with factor matrices representing layer connection weights.A two-factor construction yields a network with ReLU hidden units and linear outputs.
4.1 Factorization Mappings: The same construction can describe deeper ReLU architectures as sums of r subnetworks whose outputs feed a final linear layer.The example uses a five-layer network with hidden-layer ReLU nonlinearities.
4.1 Factorization Mappings: The framework can include broad neural architectures when their nonlinearities are positively homogeneous, including max-pooling and rectification.Response normalization is excluded from the cited ImageNet-style example because it is not positively homogeneous.
4.1 Factorization Mappings: More general tensor decompositions such as Tucker decomposition are not explicitly included, although analogous results may follow from similar arguments.Those results are not developed in the paper.
4.2 Factorization Regularization: The regularization framework allows factor size to adapt to data and defines elemental regularizers as positive semidefinite, positively homogeneous functions.Norms and even l_q pseudonorms for q∈(0,1) are permitted because convexity of the elemental regularizer is not required.
4.2 Factorization Regularization: The induced regularizer Ω_φ,g is convex in the output and attains its infimum with a finite factorization, but generally cannot be evaluated in polynomial time.In the matrix l2-product case, the induced regularizer is the nuclear norm and a factorization needs at most rank(X) components.

5. Main Analysis

The analysis constructs a convex regularizer for factorized models and uses it to connect local minima of non-convex formulations to global optimality. It then shows that sufficiently overparameterized factorizations can reach a global minimum through local descent from arbitrary initialization.

Preliminary Results: The regularizer Ωφ,g is convex, its infimum is attained by a finite factorization, and a factorization of size at most card(D) suffices.The bound can be smaller in special cases, including r ≤ rank(X) for the nuclear-norm example.
Preliminary Results: The convexity proof follows from positive homogeneity and subadditivity, which also make the finite-domain set of Ωφ,g convex.The construction combines scaled factorizations for positive homogeneity and concatenated factors for subadditivity.
Preliminary Results: The polar problem supplies subgradient characterizations, but solving it can remain computationally challenging and limit practical application.The paper presents the polar formulation as a generalization of the dual norm.
Main Results: Any local minimizer satisfying the zero-slice condition, with one all-zero slice in each factorized tensor, is a global minimizer.The theorem applies to objectives of the form fr(X1, . . . , XK, Q).
Main Results: When r > card(D), every finite-valued initialization has a non-increasing path to a global minimizer.This establishes global reachability through local descent rather than only characterizing special local minima.
Main Results: The resulting meta-algorithm guarantees a global minimum with finite factorization size, using no more than card(D) + 1 factors in the worst case.If r starts above card(D), the factorization size does not increase.

6. Discussion and Conclusions

The framework links factorization optimization to convex analysis, identifying conditions under which local minima are globally optimal and local descent can reach a global minimizer. The discussion also highlights balanced homogeneity, neural-network implications, and practical limitations of applying the theory.

6. Discussion and Conclusions: Practical application remains difficult because alternating-minimization methods may only reach critical points, and verifying local minimality can itself be challenging.Even so, the framework reduces the theoretical search from full global optimization to finding a local minimum under its assumptions.
6.1 Balanced Degrees of Homogeneity: Balancing the positive-homogeneity degrees of the mapping and regularizer is critical for global-optimality guarantees and for controlling factorization size.The paper states that unmatched degrees can either prevent guarantees or make the regularizer ineffective at limiting model size.
6.1 Balanced Degrees of Homogeneity: Mismatched homogeneity degrees can create spurious local minima at the origin or let the objective decrease as factor size grows.When p > p′, the origin can be a local minimum requiring an increasing escape path; when p′ > p, duplicating and scaling factors can reduce the objective.
6.2 Implications for Neural Networks: For positively homogeneous neural networks, the framework makes training analyzable through a convex formulation and can make all local minima equivalent when the network is sufficiently large.The analysis offers a partial explanation for observed benefits of rectification and max-pooling over sigmoid or hyperbolic-tangent nonlinearities.
6.2 Implications for Neural Networks: Applying the theory to existing state-of-the-art neural networks is limited because the studied mapping requires architectures composed of parallel subnetworks.Testing global optimality may require checking whether adding an entire parallel network with the same subnetwork architecture lowers the objective.
The framework guarantees global optimality for local minima under a simple condition and enables purely local descent to reach a global minimizer when factor dimensions are sufficiently large.The sufficient condition includes a zero slice of the factorized tensors.