Matrix-Free Two-to-Infinity and One-to-Two Norms Estimation
This work addresses computational efficiency challenges in matrix norm estimation for machine learning practitioners, though it appears incremental as it builds on existing Hutchinson-based methods.
The paper tackles the problem of estimating matrix norms (two-to-infinity and one-to-two) without storing the full matrix, using only matrix-vector multiplications, by modifying Hutchinson's diagonal estimator and Hutch++ methods, with results including oracle complexity bounds and practical applications in deep neural network training and adversarial attack mitigation.
In this paper, we propose new randomized algorithms for estimating the two-to-infinity and one-to-two norms in a matrix-free setting, using only matrix-vector multiplications. Our methods are based on appropriate modifications of Hutchinson's diagonal estimator and its Hutch++ version. We provide oracle complexity bounds for both modifications. We further illustrate the practical utility of our algorithms for Jacobian-based regularization in deep neural network training on image classification tasks. We also demonstrate that our methodology can be applied to mitigate the effect of adversarial attacks in the domain of recommender systems.