Problem-dependent Convergence Bounds for Randomized Linear Gradient Compression

Flynn, Thomas; Johnstone, Patrick; Yoo, Shinjae

Permalink

https://hdl.handle.net/2142/130310 Copy

Description

Title

Problem-dependent Convergence Bounds for Randomized Linear Gradient Compression

Author(s)

• Flynn, Thomas
• Johnstone, Patrick
• Yoo, Shinjae

Issue Date

2025-09-17

Keyword(s)

• Stochastic optimization
• Compression
• Random matrices
• Distributed optimization
• Machine learning

Abstract

In distributed optimization, the communication of model updates can be a performance bottleneck. Consequently, gradient compression has been proposed as a means of increasing optimization throughput. In general, due to information loss, compression introduces a penalty on the number of iterations needed to reach a solution. In this work, we investigate how the iteration penalty depends on the interaction between compression and problem structure, in the context of non-convex stochastic optimization. We focus on linear schemes, where compression and decompression can be modeled as multiplication with a random matrix. We consider several distributions of matrices, among them Haar-distributed orthogonal matrices and matrices with random Gaussian entries. We find that the impact of compression on convergence can be quantified in terms of a smoothness matrix associated with the objective function, using a norm defined by the compression scheme. The analysis reveals that in certain cases, compression performance is related to low-rank structure or other spectral properties of the problem and our bounds predict that the penalty introduced by compression is significantly reduced compared to worst-case bounds that only consider the compression level, ignoring problem data. We verify the theoretical findings experimentally, including fine-tuning an image classification model.

Publisher

Allerton Conference on Communication, Control, and Computing

Series/Report Name or Number

2025 61st Allerton Conference on Communication, Control, and Computing Proceedings

ISSN

2836-4503

Type of Resource

Text

Genre of Resource

Conference Paper/Presentation

Language

eng

Handle URL

https://hdl.handle.net/2142/130310&&

Copyright and License Information

Copyright 2025 owned by the authors.

Owning Collections