UC Louvain

A graph $X$ is defined inductively to be $(a_0, . . . , a_{n−1})$-regular if $X$ is $a_0$-regular and for every vertex $v$ of $X$, the sphere of radius 1 around $v$ is an $(a_1, . . . , a_{n−1})$-regular graph. A family $F$ of graphs is said to be an expander family if there is a uniform lower bound on the Cheeger constant of all the graphs in $F$. 

After briefly (re)introducing Coxeter groups and their geometries, we will describe how they can be used to construct very regular polytopes, which in turn can yield highly regular graphs. We will then use the super-approximation machinery, whenever the Coxeter group is hyperbolic, to obtain the expansion of these families of graphs. As a result, we obtain interesting infinite families of highly regular expander graphs, some of which are related to the exceptional groups. 

The talk is based on work joint with Conder, Lubotzky, and Schillewaert. 

We propose to use stochastic Riemannian coordinate descent on the Stiefel manifold for deep neural network training. The algorithm rotates successively two columns of the matrix, an operation that can be efficiently implemented as a multiplication by a Givens matrix. In the case when the coordinate is selected uniformly at random at each iteration, we prove the convergence of the proposed algorithm under standard assumptions on the loss function, stepsize and minibatch noise. Experiments on benchmark deep neural network training problems are presented to demonstrate the effectiveness of the proposed algorithm.

This talk concerns applications of differential geometry in numerical optimization. They arise when the optimization problem can be formulated as finding an optimum of a real-valued cost function defined on a smooth nonlinear search space. Oftentimes, the search space is a "matrix manifold", in the sense that its points admit natural representations in the form of matrices. In most cases, the matrix manifold structure is due either to the presence of certain nonlinear constraints (such as orthogonality or rank constraints), or to invariance properties in the cost function that need to be factored out in order to obtain a nondegenerate optimization problem. Manifolds that come up in practical applications include the rotation group SO(3) (generation of rigid body motions from sample points), the set of fixed-rank matrices (low-rank models, e.g., in collaborative filtering), the set of 3x3 symmetric positive-definite matrices (interpolation of diffusion tensors), and the shape manifold (morphing).

In the recent years, the practical importance of optimization problems on manifolds has stimulated the development of geometric optimization algorithms that exploit the differential structure of the manifold search space. In this talk, we give an overview of geometric optimization algorithms and their applications, with an emphasis on the underlying geometric concepts and on the numerical efficiency of the algorithm implementations.

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please contact @email.

We describe the main geometric tools required to work on the manifold of fixed-rank symmetric positive-semidefinite matrices: we present expressions for the Riemannian logarithm and the injectivity radius, to complement the already known Riemannian exponential. This manifold is particularly relevant when dealing with low-rank approximations of large positive-(semi)definite matrices. The manifold is represented as a quotient of the set of full-rank rectangular matrices (endowed with the Euclidean metric) by the orthogonal group. Our results allow understanding the failure of some curve fitting algorithms, when the rank of the data is overestimated. We illustrate these observations on a dataset made of covariance matrices characterizing a wind field.