Search

In this paper, we establish new convergence results for the quantized distributed gradient descent and suggest a novel strategy of choosing the stepsizes for the high-performance of the algorithm. Under the strongly convexity assumption on the aggregate cost function and the smoothness assumption on each local cost function, we prove the algorithm converges exponentially fast to a small neighborhood of the optimizer whose radius depends on the stepsizes. Based on our convergence result, we suggest an effective selection of stepsizes which repeats diminishing the stepsizes after a number of specific iterations. Both the convergence results and the effectiveness of the suggested stepsize selection are also verified by the numerical experiments., 21 pages, 4 figures

Gradient-push algorithm has been widely used for decentralized optimization problems when the connectivity network is a direct graph. This paper shows that the gradient-push algorithm with stepsize $\alpha>0$ converges exponentially fast to an $O(\alpha)$-neighborhood of the optimizer under the assumption that each cost is smooth and the total cost is strongly convex. Numerical experiments are provided to support the theoretical convergence results.

In this work, we are concerned with the decentralized optimization problem: \begin{equation*} \min_{x \in \Omega}~f(x) = \frac{1}{n} \sum_{i=1}^n f_i (x), \end{equation*} where $\Omega \subset \mathbb{R}^d$ is a convex domain and each $f_i : \Omega \rightarrow \mathbb{R}$ is a local cost only known to agent $i$. A fundamental algorithm is the decentralized projected gradient method (DPG) given by \begin{equation*} x_i(t+1)=\mathcal{P}_\Omega\Big[\sum^n_{j=1}w_{ij} x_j(t) -\alpha(t)\nabla f_i(x_i(t))\Big] \end{equation*} where $\mathcal{P}_{\Omega}$ is the projection operator to $\Omega$ and $ \{w_{ij}\}_{1\leq i,j \leq n}$ are communication weight among the agents. While this method has been widely used in the literatures, its sharp convergence property has not been established well so far, except for the special case $\Omega = \mathbb{R}^n$. This work establishes new convergence estimates of DPG when the aggregate cost $f$ is strongly convex and each function $f_i$ is smooth. If the stepsize is given by constant $\alpha (t) \equiv\alpha >0$ and suitably small, we prove that each $x_i (t)$ converges to an $O(\sqrt{\alpha})$-neighborhood of the optimal point. In addition, we take a one-dimensional example $f_i$ and prove that the point $x_i (t)$ converges to an $O(\alpha)$-neighborhood of the optimal point. Also, we obtain convergence estimates for decreasing stepsizes. Numerical experiments are also provided to support the convergence results., Comment: 27 pages, 3 figures

In this work, we establish convergence results for the distributed proximal point algorithm (DPPA) for distributed optimization problems. We consider the problem on the whole domain Rd and find a general condition on the stepsize and cost functions such that the DPPA is stable. We prove that the DPPA with stepsize $\eta > 0$ exponentially converges to an $O(\eta)$-neighborhood of the optimizer. Our result clearly explains the advantage of the DPPA with respect to the convergence and stability in comparison with the distributed gradient descent algorithm. We also provide numerical tests supporting the theoretical results.

In this paper, we consider the online proximal mirror descent for solving the time-varying composite optimization problems. For various applications, the algorithm naturally involves the errors in the gradient and proximal operator. We obtain sharp estimates on the dynamic regret of the algorithm when the regular part of the cost is convex and smooth. If the Bregman distance is given by the Euclidean distance, our result also improves the previous work in two ways: (i) We establish a sharper regret bound compared to the previous work in the sense that our estimate does not involve $O(T)$ term appearing in that work. (ii) We also obtain the result when the domain is the whole space $\mathbb{R}^n$, whereas the previous work was obtained only for bounded domains. We also provide numerical tests for problems involving the errors in the gradient and proximal operator., Comment: 16 pages, 5 figures

Distributed optimization has received a lot of interest in recent years due to its wide applications in various fields. In this work, we revisit the convergence property of the decentralized gradient descent [A. Nedi{\'c}-A.Ozdaglar (2009)] on the whole space given by $$ x_i(t+1) = \sum^m_{j=1}w_{ij}x_j(t) - \alpha(t) \nabla f_i(x_i(t)), $$ where the stepsize is given as $\alpha (t) = \frac{a}{(t+w)^p}$ with $0< p\leq 1$. Under the strongly convexity assumption on the total cost function $f$ with local cost functions $f_i$ not necessarily being convex, we show that the sequence converges to the optimizer with rate $O(t^{-p})$ when the values of $a>0$ and $w>0$ are suitably chosen., Comment: 25 pages, fixed typos

In this paper, we propose an integral based event-triggering controller for bipartite consensus of the multi-agent systems whose dynamics are described by general linear system. We prove that the system achieves the bipartite consensus in asymptotic regime and there is a positive minimum inter-event time (MIET) between two consecutive triggering times of each agent. The proof of the asymptotive stability involves a novel argument used to bound the norm of the difference between the true state and its estimated state (for each time) by an integration of its square. Numerical results are provided supporting the effectiveness of the proposed controller.

In this paper, we propose a framework under which the decentralized optimization algorithms suggested in \cite{JKJJ,MA, NO,NO2} can be treated in a unified manner. More precisely, we show that the distributed subgradient descent algorithms \cite{JKJJ, NO}, the subgradient-push algorithm \cite{NO2}, and the distributed algorithm with row-stochastic matrix \cite{MA} can be derived by making suitable choices of consensus matrices, step-size and subgradient from the decentralized subgradient descent proposed in \cite{NO}. As a result of such unified understanding, we provide a convergence proof that covers the algorithms in \cite{JKJJ,MA, NO,NO2} under a novel algebraic condition that is strictly weaker than the conventional graph-theoretic condition in \cite{NO}. This unification also enables us to derive a new distributed optimization scheme.

In this paper, we are concerned with a nonlinear optimal control problem of ordinary differential equations. We consider a discretization of the problem with the discontinuous Galerkin method with arbitrary order $r \in \mathbb{N}\cup \{0\}$. Under suitable regularity assumptions on the cost functional and solutions of the state equations, we provide sharp estimates for the error of the approximate solutions. Numerical experiments are presented supporting the theoretical results.