KOALA++: Efficient Kalman-Based Optimization with Gradient-Covariance Products

Zixuan XIa (University of Bern) · Aram Davtyan (Universität Bern) · Paolo Favaro (University of Bern)

algorithm scalabilitycompact gradient covariance productsdiagonal covariancefirst-order methods image classificationkalman-based optimizationkoala++matrix inversionsneural network trainingparameter covariance matrixsecond-order methodsstate-of-the-art optimizersstructured gradient uncertaintyuncertainty structure

We propose KOALA++, a scalable Kalman-based optimization algorithm that explicitly models structured gradient uncertainty in neural network training. Unlike second-order methods, which rely on expensive second order gradient calculation, our method directly estimates the parameter covariance matrix by recursively updating compact gradient covariance products. This design improves upon the original KOALA framework that assumed diagonal covariance by implicitly capturing richer uncertainty structure without storing the full covariance matrix and avoiding large matrix inversions. Across diverse tasks, including image classification and language modeling, KOALA++ achieves accuracy on par or better than state-of-the-art second-order optimizers while maintaining the efficiency of first-order methods.