Low rank approximation certification costs revealed for expanding matrix checks
Information Limits of Low-Rank Approximation Certification
Artificial IntelligenceInformation Theory
Summary
Low-rank approximation is a method used to simplify large matrices, but checking that this simplification is accurate can be costly. The authors studied how many checks or queries are needed to be confident the simplification error is within acceptable limits. They discovered that you can reuse some checks efficiently as you consider sequences of approximations, reducing the overall cost. Their findings precisely show how the cost scales depending on how many approximation paths are tested and the error levels desired.
What this means in practice
- •For machine learning engineers: Optimize validation steps for algorithms using low-rank matrix approximations to certify error efficiently during model training.
- •For numerical simulation developers: Design verification routines for low-rank approximations in large simulations while minimizing computational overhead for error checks.
A theory result. No direct application yet.
Authors
Kang Liu, Bohao Qu
Abstract
Low-rank approximation can require additional matrix--vector products to verify that its error meets a prescribed tolerance. We characterize this certification cost for both relative matrix error and mean-square output error. For a single approximation matrix candidate, we determine the exact dimension-uniform minimax query constant as the allowed failure probability vanishes. Our main result concerns reusing validation responses as the approximation space expands. For a candidate family constructed independently of validation, one batch supports an entire nested path without increasing the query budget with the number of checks. Across \(W\) paths, a concentration bound exploiting shared residual energy yields a \(\sqrt{\log(W+1)}\) dependence. A matching lower bound establishes its optimality for fixed interior error targets and sufficiently small separation gaps. Finally, we compare two uniformly valid certificates on the same dispersed-spectrum family. Optimizing the validation budget within each rule family yields costs of orders \(N^{1/3}\) and \(N^{2/3}\) for validation and construction beyond the true target. Code is available at https://anonymous.4open.science/r/Low-rank-approximation-1275/