Parallelized Computation and Backpropagation Under Angle-Parametrized Orthogonal Matrices

Abstract

We present a methodology for parallel acceleration of learning in the presence of matrix orthogonality and unitarity constraints of interest in several branches of machine learning. We show how an apparently sequential elementary rotation parametrization can be restructured into blocks of commutative operations using a well-known tool for coloring the edges of complete graphs, in turn widely applied to schedule round-robin (all-against-all) sports tournaments. The resulting decomposition admits an algorithm to compute a fully-parametrized orthogonal matrix from its rotation parameters in $O(n)$ sequential steps and one to compute the gradient of a training loss with respect to its parameters in $O(n\log n)$ steps. We discuss parametric restrictions of interest to generative modeling and present promising performance results with a prototype GPU implementation.

References in corpus (5)

• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Orthogonal Weight Normalization: Solution to Optimization over Multiple Dependent Stiefel Manifolds in Deep Neural Networks
• Generalized BackPropagation, Étude De Cas: Orthogonality
• Optimization on Submanifolds of Convolution Kernels in CNNs
• Fast Approximation of Rotations and Hessians matrices