Det-CGD: Compressed Gradient Descent with Matrix Stepsizes for Non-Convex Optimization

Abstract

This paper introduces a new method for minimizing matrix-smooth non-convex objectives through the use of novel Compressed Gradient Descent (CGD) algorithms enhanced with a matrix-valued stepsize. The proposed algorithms are theoretically analyzed first in the single-node and subsequently in the distributed settings. Our theoretical results reveal that the matrix stepsize in CGD can capture the objective's structure and lead to faster convergence compared to a scalar stepsize. As a byproduct of our general results, we emphasize the importance of selecting the compression mechanism and the matrix stepsize in a layer-wise manner, taking advantage of model structure. Moreover, we provide theoretical guarantees for free compression, by designing specific layer-wise compressors for the non-convex matrix smooth objectives. Our findings are supported with empirical evidence.

9 pages, 39 figures, published in ICLR 2024

References in corpus (19)

• Understanding Neural Networks Through Deep Visualization
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Visualizing Deep Neural Network Decisions: Prediction Difference Analysis
• Non-convex Optimization for Machine Learning
• Distributed Learning with Compressed Gradient Differences
• Stochastic Gradient Methods with Layer-wise Adaptive Moments for Training of Deep Networks
• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
• Better Theory for SGD in the Nonconvex World
• Unified Optimal Analysis of the (Stochastic) Gradient Method
• EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
• Why are Adaptive Methods Good for Attention Models?
• Distributed learning with compressed gradients
• SEGA: Variance Reduction via Gradient Sketching
• Block-Normalized Gradient Method: An Empirical Study for Training Deep Neural Network
• Adaptive Gradient Descent for Convex and Non-Convex Stochastic Optimization
• ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!
• Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization
• Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques
• GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity