A CUSUM-Based Approach for the Dynamic Step-Size Selection Problem in Primal-Based Distributed Optimization Algorithms

We present a novel approach to dynamically select step-sizes in primal-based distributed optimization algorithms. The proposed method is based on the local evaluation of local parameters, and thus does not come with any additional communication burden (particularly important in communication environments with limited data rates, such as underwater systems), is computationally lightweight (particularly important when agents have limited computation or power capabilities, such as in internet of underwater things scenarios), and require no prior information about the network topology or objective function (particularly important in situations where the agents may change location and solve different tasks in different times). The analysed scheme ladders on classical hypothesis testing methods to estimate where the local dynamics of the local variables are evolving towards. In this approach, we utilized cumulative sum (CUSUM) to detect the average growth in the evolution of local parameters. This enables establishing mechanisms for changing dynamically the local step-sizes so to simultaneously avoid divergence but also increase convergence speed when necessary. We thus evaluate the performance of the novel method using a dedicated Monte Carlo analysis that compares it against oracle-based selectors, i.e., against situations where the network employs the best possible fixed step-size. The results show that the proposed method can sometimes lead to faster convergence than such optimal fixed step-sizes, often have comparable performance against them, and in any case guarantee convergence.