More Like this

1. An Experimental Study of Balance in Matrix Factorization

   https://doi.org/10.1109/CISS50987.2021.9400232  

   Hsia, Jennifer; Ramadge, Peter J. (March 2021, 2021 55th Annual Conference on Information Sciences and Systems)

   null (Ed.)

   We experimentally examine how gradient descent navigates the landscape of matrix factorization to obtain a global minimum. First, we review the critical points of matrix factorization and introduce a balanced factorization. By focusing on the balanced critical point at the origin and a subspace of unbalanced critical points, we study the effect of balance on gradient descent, including an initially unbalanced factorization and adding a balance-regularizer to the objective in the MF problem. Simulations demonstrate that maintaining a balanced factorization enables faster escape from saddle points and overall faster convergence to a global minimum. 

   more » « less
2. Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization

   Zhang, Jialun; Fattahi, Salar; Zhang, Richard Y (December 2021, Advances in Neural Information Processing Systems)

   In practical instances of nonconvex matrix factorization, the rank of the true solution r^{\star} is often unknown, so the rank rof the model can be over-specified as r>r^{\star}. This over-parameterized regime of matrix factorization significantly slows down the convergence of local search algorithms, from a linear rate with r=r^{\star} to a sublinear rate when r>r^{\star}. We propose an inexpensive preconditioner for the matrix sensing variant of nonconvex matrix factorization that restores the convergence rate of gradient descent back to linear, even in the over-parameterized case, while also making it agnostic to possible ill-conditioning in the ground truth. Classical gradient descent in a neighborhood of the solution slows down due to the need for the model matrix factor to become singular. Our key result is that this singularity can be corrected by \ell_{2} regularization with a specific range of values for the damping parameter. In fact, a good damping parameter can be inexpensively estimated from the current iterate. The resulting algorithm, which we call preconditioned gradient descent or PrecGD, is stable under noise, and converges linearly to an information theoretically optimal error bound. Our numerical experiments find that PrecGD works equally well in restoring the linear convergence of other variants of nonconvex matrix factorization in the over-parameterized regime. 

   more » « less
3. HyLo: a hybrid low-rank natural gradient descent method

   Mu, Baorun; Soori, Saeed; Can, Bugra; Gurbuzbalaban, Mert; Dehnavi, Maryam Mehri (January 2022, Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis)

   This work presents a Hybrid Low-Rank Natural Gradient Descent method, called HyLo, that accelerates the training time of deep neural networks. Natural gradient descent (NGD) requires computing the inverse of the Fisher information matrix (FIM), which is typically expensive at large-scale. Kronecker factorization methods such as KFAC attempt to improve NGD's running time by approximating the FIM with Kronecker factors. However, the size of Kronecker factors increases quadratically as the model size grows. Instead, in HyLo, we use the Sherman-Morrison-Woodbury variant of NGD (SNGD) and propose a reformulation of SNGD to resolve its scalability issues. HyLo uses a computationally-efficient low-rank factorization to achieve superior timing for Fisher inverses. We evaluate HyLo on large models including ResNet-50, U-Net, and ResNet-32 on up to 64 GPUs. HyLo converges 1.4×-2.1× faster than the state-of-the-art distributed implementation of KFAC and reduces the computation and communication time up to 350× and 10.7× on ResNet-50. 

   more » « less
4. Distributed-Memory Parallel JointNMF

   https://doi.org/10.1145/3577193.3593733  

   Eswar, Srinivas; Cobb, Benjamin; Hayashi, Koby; Kannan, Ramakrishnan; Ballard, Grey; Vuduc, Richard; Park, Haesun (June 2023, Proceedings of the 37th International Conference on Supercomputing)

   Joint Nonnegative Matrix Factorization (JointNMF) is a hybrid method for mining information from datasets that contain both feature and connection information. We propose distributed-memory parallelizations of three algorithms for solving the JointNMF problem based on Alternating Nonnegative Least Squares, Projected Gradient Descent, and Projected Gauss-Newton. We extend well-known communication-avoiding algorithms using a single processor grid case to our coupled case on two processor grids. We demonstrate the scalability of the algorithms on up to 960 cores (40 nodes) with 60\% parallel efficiency. The more sophisticated Alternating Nonnegative Least Squares (ANLS) and Gauss-Newton variants outperform the first-order gradient descent method in reducing the objective on large-scale problems. We perform a topic modelling task on a large corpus of academic papers that consists of over 37 million paper abstracts and nearly a billion citation relationships, demonstrating the utility and scalability of the methods. 

   more » « less
5. How and When Random Feedback Works: A Case Study of Low-Rank Matrix Factorization

   Shivam Garg and Santosh S. Vempala (January 2022, AISTATS)

   The success of gradient descent in ML and especially for learning neural networks is remarkable and robust. In the context of how the brain learns, one aspect of gradient descent that appears biologically difficult to realize (if not implausible) is that its updates rely on feedback from later layers to earlier layers through the same connections. Such bidirected links are relatively few in brain networks, and even when reciprocal connections exist, they may not be equi-weighted. Random Feedback Alignment (Lillicrap et al., 2016), where the backward weights are random and fixed, has been proposed as a bio-plausible alternative and found to be effective empirically. We investigate how and when feedback alignment (FA) works, focusing on one of the most basic problems with layered structure n×m, the goal is to find a low rank factorization Zn×rWr×m that minimizes the error ∥ZW−Y∥F. Gradient descent solves this problem optimally. We show that FA finds the optimal solution when r≥rank(Y). We also shed light on how FA works. It is observed empirically that the forward weight matrices and (random) feedback matrices come closer during FA updates. Our analysis rigorously derives this phenomenon and shows how it facilitates convergence of FA*, a closely related variant of FA. We also show that FA can be far from optimal when r 

   more » « less