Overview
This paper introduces the Adaptive Decentralized Quasi-Newton (AdaDQN) method, designed to solve smooth nonconvex optimization problems within undirected networks. AdaDQN addresses a theoretical limitation observed in existing decentralized algorithms that employ multiple local updates, where the convergence stepsize tends to be inversely proportional to the number of local updates. The proposed method establishes global convergence to a first-order stationary point and demonstrates a convergence stepsize bound that is independent of the maximum number of local updates.
Research Context
Decentralized algorithms with multiple local updates performing optimization over undirected networks typically face a constraint where their theoretical convergence stepsize is detrimentally linked to the quantity of local updates. This inverse proportionality suggests a significant bottleneck for their performance and scalability. Overcoming this limitation requires a re-evaluation of how local updates are integrated and managed within decentralized optimization frameworks.
Approach
The development of AdaDQN involved revisiting local update methods through the lens of Majorization-Minimization (MM). This re-examination led to the establishment of a Robust Inexact Algorithm (RIA) framework. Inspired by this framework, AdaDQN incorporates several key components:
- A safeguarded consensus-aware termination criterion: This criterion dynamically balances the gains from local computations against the consensus error present in the decentralized system.
- A scalable memoryless BFGS update: This component is integrated into the optimization process.
- An event-triggered communication protocol: This protocol is designed to significantly reduce the communication overhead typically associated with decentralized methods.
Findings
- AdaDQN achieves global convergence to a first-order stationary point for smooth nonconvex optimization problems over undirected networks.
- The convergence stepsize bound in AdaDQN is theoretically decoupled from the reciprocal of the maximum number of local updates. This represents a solution to the pessimistic theoretical bottleneck present in other decentralized algorithms.
- Numerical experiments indicate that AdaDQN offers a superior computation-communication tradeoff compared to other state-of-the-art decentralized methods.
- AdaDQN outperformed existing decentralized methods across various performance metrics in numerical experiments.
Why This Matters
The ability of AdaDQN to mitigate the stepsize degradation issue in decentralized optimization algorithms holds implications for solving complex nonconvex problems in distributed environments. By decoupling the convergence stepsize from the number of local updates, the method potentially enables more efficient and scalable optimization in settings where computational resources are distributed across multiple nodes, reducing overhead and improving performance.