In this paper we analyze the randomized block-coordinate descent (RBCD) methods proposed in Nesterov (SIAM J Optim 22(2):341-362, 2012), Richtarik and Taka (Math Program 144(1-2):1-38, 2014) for minimizing the sum of ...
详细信息
In this paper we analyze the randomized block-coordinate descent (RBCD) methods proposed in Nesterov (SIAM J Optim 22(2):341-362, 2012), Richtarik and Taka (Math Program 144(1-2):1-38, 2014) for minimizing the sum of a smooth convex function and a block-separable convex function, and derive improved bounds on their convergence rates. In particular, we extend Nesterov's technique developed in Nesterov (SIAM J Optim 22(2):341-362, 2012) for analyzing the RBCD method for minimizing a smooth convex function over a block-separable closed convex set to the aforementioned more general problem and obtain a sharper expected-value type of convergence rate than the one implied in Richtarik and Taka (Math Program 144(1-2):1-38, 2014). As a result, we also obtain a better high-probability type of iteration complexity. In addition, for unconstrained smooth convex minimization, we develop a new technique called randomized estimate sequence to analyze the accelerated RBCD method proposed by Nesterov (SIAM J Optim 22(2):341-362, 2012) and establish a sharper expected-value type of convergence rate than the one given in Nesterov (SIAM J Optim 22(2):341-362, 2012).
We consider decentralized large-scale continuous submodular constrained optimization problems over networks, where the goal is to maximize a sum of nonconvex functions with diminishing returns property. However, the c...
详细信息
We consider decentralized large-scale continuous submodular constrained optimization problems over networks, where the goal is to maximize a sum of nonconvex functions with diminishing returns property. However, the computations of the projection step and the whole gradient can become prohibitive in high-dimensional constrained optimization problems. For this reason, a decentralized randomizedblock-coordinate Frank-Wolfe algorithm is proposed for submoduar maximization over networks by local communication and computation, which adopts the randomized block-coordinate descent and the Frank-Wolfe technique. We also show that the proposed algorithm converges to an approximation fact (1-e(-pmax)/(pmin)) of the global maximal points at a rate of O(1/T) by choosing a suitable stepsize, where T is the number of iterations. In addition, we confirm the theoretical results by experiments.
In this paper, we study the convergence properties of a randomized block-coordinate descent algorithm for the minimization of a composite convex objective function, where the block-coordinates are updated asynchronous...
详细信息
In this paper, we study the convergence properties of a randomized block-coordinate descent algorithm for the minimization of a composite convex objective function, where the block-coordinates are updated asynchronously and randomly according to an arbitrary probability distribution. We prove that the iterates generated by the algorithm form a stochastic quasi-Fejer sequence and thus converge almost surely to a minimizer of the objective function. Moreover, we prove a general sublinear rate of convergence in expectation for the function values and a linear rate of convergence in expectation under an error bound condition of Tseng type. Under the same condition strong convergence of the iterates is provided as well as their linear convergence rate.
The problem of minimizing a separable convex function under linearly coupled constraints arises from various application domains such as economic systems, distributed control, and network flow. The main challenge for ...
详细信息
The problem of minimizing a separable convex function under linearly coupled constraints arises from various application domains such as economic systems, distributed control, and network flow. The main challenge for solving this problem is that the size of data is very large, which makes usual gradient-based methods infeasible. Recently, Necoara, Nesterov and Glineur [Random blockcoordinatedescent methods for linearly constrained optimization over networks, J. Optim. Theory Appl. 173(1) (2017) 227-254] proposed an efficient randomizedcoordinatedescent method to solve this type of optimization problems and presented an appealing convergence analysis. In this paper, we develop new techniques to analyze the convergence of such algorithms, which are able to greatly improve the results presented in the above. This refined result is achieved by extending Nesterov's second technique [Efficiency of coordinatedescent methods on huge-scale optimization problems, SIAM J. Optim. 22 (2012) 341-362] to the general optimization problems with linearly coupled constraints. A novel technique in our analysis is to establish the basis vectors for the subspace of the linear constraints.
This study considers a constrained huge-scale optimization problem over networks where the objective is to minimize the sum of nonsmooth local loss functions. To solve this problem, many optimization algorithms have b...
详细信息
This study considers a constrained huge-scale optimization problem over networks where the objective is to minimize the sum of nonsmooth local loss functions. To solve this problem, many optimization algorithms have been proposed by employing (sub)gradient descent methods to handle high-dimensional data, but the computation of the entire sub(gradient) becomes a computational bottleneck. To reduce the computational burden of each agent and preserve privacy of data in time-varying networks, we propose a privacy-preserving decentralized randomizedblock-coordinate subgradient projection algorithm over time-varying networks, in which the coordinates of the subgradient vector is randomly chosen to update the optimized parameter and the partially homomorphic cryptography is used to protect the privacy of data. Further, we prove that our algorithm is convergent asymptotically. Moreover, the rates of convergence are also established by choosing & RADIC;appropriate step sizes, i.e., O(log K/K) under local strong convexity and O(log K/ K) under local convexity, in which K represents the number of iterations. Meanwhile, we show that the privacy of data can be protected by the proposed algorithm. The results of experiments demonstrate the computational benefit of our algorithm on two real-world datasets. The theoretical results are also verified by different experiments.
暂无评论