Foundations of Multiple-Time-Scale Stochastic Approximation for Fast and Resilient Distributed Optimization Algorithms

This dissertation establishes a theoretical framework for analyzing and designing fast and resilient distributed optimization algorithms for large-scale networks. The central focus is on understanding and leveraging two-time-scale dynamics, which may arise naturally from the underlying network structure or be introduced through algorithmic design. Motivated by challenges in large-scale decentralized networks—such as communication constraints, agent failures, and dynamic participation—this work develops and analyzes four key aspects. First, we study consensus-based gradient methods over networks with a clustered structure, characterized by dense intra-cluster and sparse inter-cluster communication. This setting naturally gives rise to textit{two-time-scale} dynamics. We develop a framework to analyze these dynamics and, using the singular perturbation method, derive new convergence rate results that reveal how local and global interactions influence the scalability and performance of distributed algorithms over clustered networks. Second, we analyze a two-time-scale distributed gradient descent algorithm for networks where agents communicate using quantized information. By averaging the quantized values at a faster time scale and performing gradient updates at a slower time scale, the algorithm effectively mitigates the impact of quantization errors. We introduce a novel analysis and step-size selection strategy that allows us to establish exact convergence to the optimal solution at the optimal rate. Third, we develop a resilient distributed algorithm for networks exposed to malicious agents. By introducing separate update speeds for the gradient estimation and gradient descent steps, the algorithm exhibits a two-time-scale behavior. We show that this design effectively mitigates the impact of both malicious agents and stochastic gradients, while still ensuring exact convergence at the optimal rate. Finally, we study open networks, where agents can dynamically join or leave. By leveraging redundancy in local objectives, we convert the time-varying problem into an effectively static one. This enables us to design both a local stochastic gradient descent algorithm and a gradient-balancing protocol for resource allocation, each of which achieves optimal and exact convergence.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

doctoral

Discipline thesis:degree_discipline

Electrical Engineering

Department dc:contributor.department

Electrical Engineering

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

2025

Author dc:creator

• Dutta, Amit

Chair dc:contributor.committeechair

• Doan, Thinh Thanh

Committee members dc:contributor.committeemember

• Reed, Jeffrey H.
• Stilwell, Daniel J.
• L'Afflitto, Andrea
• Williams, Ryan K.

• Distributed optimization
• Cluster networks
• Federated optimization
• Byzantine fault-tolerance
• Quantized communication
• Two-time-scale methods

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en

Dc Identifier Other

vt_gsexam:43937

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/134989