Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Decentralized Tracking with ADMM for Problems with Time-Varying Curvature
329
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We analyze the performance of the alternating direction method of multipliers (ADMM) to track, in a decentralized manner, a solution of a stochastic sequence of optimization problems parametrized by a discrete time Markov process. The main advantage of considering a stochastic model is that we allow the objective functions to occasionally lose strong convexity and/or Lipschitz continuity of their gradients. Due to the stochastic nature of our model, the tracking statement is given in a mean square deviation error.
rate research
Read More
Decentralized optimization over time-varying graphs has been increasingly common in modern machine learning with massive data stored on millions of mobile devices, such as in federated learning. This paper revisits the widely used accelerated gradient tracking and extends it to time-varying graphs. We prove the $O((frac{gamma}{1-sigma_{gamma}})^2sqrt{frac{L}{epsilon}})$ and $O((frac{gamma}{1-sigma_{gamma}})^{1.5}sqrt{frac{L}{mu}}logfrac{1}{epsilon})$ complexities for the practical single loop accelerated gradient tracking over time-varying graphs when the problems are nonstrongly convex and strongly convex, respectively, where $gamma$ and $sigma_{gamma}$ are two common constants charactering the network connectivity, $epsilon$ is the desired precision, and $L$ and $mu$ are the smoothness and strong convexity constants, respectively. Our complexities improve significantly over the ones of $O(frac{1}{epsilon^{5/7}})$ and $O((frac{L}{mu})^{5/7}frac{1}{(1-sigma)^{1.5}}logfrac{1}{epsilon})$, respectively, which were proved in the original literature only for static graphs, where $frac{1}{1-sigma}$ equals $frac{gamma}{1-sigma_{gamma}}$ when the network is time-invariant. When combining with a multiple consensus subroutine, the dependence on the network connectivity constants can be further improved to $O(1)$ and $O(frac{gamma}{1-sigma_{gamma}})$ for the computation and communication complexities, respectively. When the network is static, by employing the Chebyshev acceleration, our complexities exactly match the lower bounds without hiding any poly-logarithmic factor for both nonstrongly convex and strongly convex problems.
Communication compression techniques are of growing interests for solving the decentralized optimization problem under limited communication, where the global objective is to minimize the average of local cost functions over a multi-agent network using only local computation and peer-to-peer communication. In this paper, we first propose a novel compressed gradient tracking algorithm (C-GT) that combines gradient tracking technique with communication compression. In particular, C-GT is compatible with a general class of compression operators that unifies both unbiased and biased compressors. We show that C-GT inherits the advantages of gradient tracking-based algorithms and achieves linear convergence rate for strongly convex and smooth objective functions. In the second part of this paper, we propose an error feedback based compressed gradient tracking algorithm (EF-C-GT) to further improve the algorithm efficiency for biased compression operators. Numerical examples complement the theoretical findings and demonstrate the efficiency and flexibility of the proposed algorithms.
The present paper considers leveraging network topology information to improve the convergence rate of ADMM for decentralized optimization, where networked nodes work collaboratively to minimize the objective. Such problems can be solved efficiently using ADMM via decomposing the objective into easier subproblems. Properly exploiting network topology can significantly improve the algorithm performance. Hybrid ADMM explores the direction of exploiting node information by taking into account node centrality but fails to utilize edge information. This paper fills the gap by incorporating both node and edge information and provides a novel convergence rate bound for decentralized ADMM that explicitly depends on network topology. Such a novel bound is attainable for certain class of problems, thus tight. The explicit dependence further suggests possible directions to optimal design of edge weights to achieve the best performance. Numerical experiments show that simple heuristic methods could achieve better performance, and also exhibits robustness to topology changes.
There is an increasing interest in designing differentiators, which converge exactly before a prespecified time regardless of the initial conditions, i.e., which are fixed-time convergent with a predefined Upper Bound of their Settling Time (UBST), due to their ability to solve estimation and control problems with time constraints. However, for the class of signals with a known bound of their $(n+1)$-th time derivative, the existing design methodologies are either only available for first-order differentiators, yielding a very conservative UBST, or result in gains that tend to infinity at the convergence time. Here, we introduce a new methodology based on time-varying gains to design arbitrary-order exact differentiators with a predefined UBST. This UBST is a priori set as one parameter of the algorithm. Our approach guarantees that the UBST can be set arbitrarily tight, and we also provide sufficient conditions to obtain exact convergence while maintaining bounded time-varying gains. Additionally, we provide necessary and sufficient conditions such that our approach yields error dynamics with a uniformly Lyapunov stable equilibrium. Our results show how time-varying gains offer a general and flexible methodology to design algorithms with a predefined UBST.
The CASH problem has been widely studied in the context of automated configurations of machine learning (ML) pipelines and various solvers and toolkits are available. However, CASH solvers do not directly handle black-box constraints such as fairness, robustness or other domain-specific custom constraints. We present our recent approach [Liu, et al., 2020] that leverages the ADMM optimization framework to decompose CASH into multiple small problems and demonstrate how ADMM facilitates incorporation of black-box constraints.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
