
Globally Optimal Training of Generalized Polynomial Neural Networks with Nonlinear Spectral Methods
The optimization problem behind neural networks is highly nonconvex. Training with stochastic gradient descent and variants requires careful parameter tuning and provides no guarantee to achieve the global optimum. In contrast we show under quite weak assumptions on the data that a particular class of feedforward neural networks can be trained globally optimal with a linear convergence rate with our nonlinear spectral method. Up to our knowledge this is the first practically feasible method which achieves such a guarantee. While the method can in principle be applied to deep networks, we restrict ourselves for simplicity in this paper to one and two hidden layer networks. Our experiments confirm that these models are rich enough to achieve good performance on a series of realworld datasets.
10/28/2016 ∙ by Antoine Gautier, et al. ∙ 0 ∙ shareread it

An Efficient Multilinear Optimization Framework for Hypergraph Matching
Hypergraph matching has recently become a popular approach for solving correspondence problems in computer vision as it allows to integrate higherorder geometric information. Hypergraph matching can be formulated as a thirdorder optimization problem subject to the assignment constraints which turns out to be NPhard. In recent work, we have proposed an algorithm for hypergraph matching which first lifts the thirdorder problem to a fourthorder problem and then solves the fourthorder problem via optimization of the corresponding multilinear form. This leads to a tensor block coordinate ascent scheme which has the guarantee of providing monotonic ascent in the original matching score function and leads to stateoftheart performance both in terms of achieved matching score and accuracy. In this paper we show that the lifting step to a fourthorder problem can be avoided yielding a thirdorder scheme with the same guarantees and performance but being two times faster. Moreover, we introduce a homotopy type method which further improves the performance.
11/09/2015 ∙ by Quynh Nguyen, et al. ∙ 0 ∙ shareread it

A Flexible Tensor Block Coordinate Ascent Scheme for Hypergraph Matching
The estimation of correspondences between two images resp. point sets is a core problem in computer vision. One way to formulate the problem is graph matching leading to the quadratic assignment problem which is NPhard. Several so called second order methods have been proposed to solve this problem. In recent years hypergraph matching leading to a third order problem became popular as it allows for better integration of geometric information. For most of these third order algorithms no theoretical guarantees are known. In this paper we propose a general framework for tensor block coordinate ascent methods for hypergraph matching. We propose two algorithms which both come along with the guarantee of monotonic ascent in the matching score on the set of discrete assignment matrices. In the experiments we show that our new algorithms outperform previous work both in terms of achieving better matching scores and matching accuracy. This holds in particular for very challenging settings where one has a high number of outliers and other forms of noise.
04/29/2015 ∙ by Quynh Nguyen, et al. ∙ 0 ∙ shareread it

The Power Mean Laplacian for Multilayer Graph Clustering
Multilayer graphs encode different kind of interactions between the same set of entities. When one wants to cluster such a multilayer graph, the natural question arises how one should merge the information different layers. We introduce in this paper a oneparameter family of matrix power means for merging the Laplacians from different layers and analyze it in expectation in the stochastic block model. We show that this family allows to recover ground truth clusters under different settings and verify this in real world data. While computing the matrix power mean can be very expensive for large graphs, we introduce a numerical scheme to efficiently compute its eigenvectors for the case of large sparse graphs.
03/01/2018 ∙ by Pedro Mercado, et al. ∙ 0 ∙ shareread it

A unifying PerronFrobenius theorem for nonnegative tensors via multihomogeneous maps
Inspired by the definition of symmetric decomposition, we introduce the concept of shape partition of a tensor and formulate a general tensor spectral problem that includes all the relevant spectral problems as special cases. We formulate irreducibility and symmetry properties of a nonnegative tensor T in terms of the associated shape partition. We recast the spectral problem for T as a fixed point problem on a suitable product of projective spaces. This allows us to use the theory of multihomogeneous orderpreserving maps to derive a general and unifying PerronFrobenius theorem for nonnegative tensors that either implies previous results of this kind or improves them by weakening the assumptions there considered. We introduce a general power method for the computation of the dominant tensor eigenpair, and provide a detailed convergence analysis.
01/12/2018 ∙ by Antoine Gautier, et al. ∙ 0 ∙ shareread it
Antoine Gautier
is this you? claim profile