NDLI: Distributed Nesterov-like gradient algorithms

Content Provider	IEEE Xplore Digital Library
Author	Jakovetic, D. Moura, J.M.F. Xavier, J.
Copyright Year	2012
Description	Author affiliation: Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, USA (Moura, J.M.F.) \|\| Institute for Systems and Robotics (ISR), Instituto Superior Técnico (IST), Technical University of Lisbon, Portugal (Jakovetic, D.; Xavier, J.)
Abstract	In classical, centralized optimization, the Nesterov gradient algorithm reduces the number of iterations to produce an ε-accurate solution (in terms of the cost function) with respect to ordinary gradient from O(1/ε) to equation. This improvement is achieved on a class of convex functions with Lipschitz continuous first derivative, and it comes at a very small additional computational cost per iteration. In this paper, we consider distributed optimization, where nodes in the network cooperatively minimize the sum of their private costs subject to a global constraint. To solve this problem, recent literature proposes distributed (sub)gradient algorithms, that are attractive due to computationally inexpensive iterations, but that converge slowly-the ε error is achieved in $O(1/ε^{2})$ iterations. Here, building from the Nesterov gradient algorithm, we present a distributed, constant step size, Nesterov-like gradient algorithm that converges much faster than existing distributed (sub)gradient methods, with zero additional communications and very small additional computations per iteration k. We show that our algorithm converges to a solution neighborhood, such that, for a convex compact constraint set and optimized stepsize, the convergence time is O(1/ε). We achieve this on a class of convex, coercive, continuously differentiable private costs with Lipschitz first derivative. We derive our algorithm through a useful penalty, network's Laplacian matrix-based reformulation of the original problem (referred to as the clone problem) - the proposed method is precisely the Nesterov-gradient applied on the clone problem. Finally, we illustrate the performance of our algorithm on distributed learning of a classifier via logistic loss.
Starting Page	5459
Ending Page	5464
File Size	419007
Page Count	6
File Format	PDF
ISBN	9781467320658
ISSN	07431546
e-ISBN	9781467320665
e-ISBN	9781467320641
DOI	10.1109/CDC.2012.6425938
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-12-10
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Cloning Convergence Vectors Logistics Cost function Approximation algorithms
Content Type	Text
Resource Type	Article
Subject	Control and Optimization Control and Systems Engineering Modeling and Simulation

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Distributed Nesterov gradient methods for random networks: Convergence in probability and convergence rates

Distributed algorithms for optimization problems with equality constraints

Convergence Rates of Distributed Nesterov-Like Gradient Methods on Random Networks

The convergence rate of Newton-Raphson consensus optimization for quadratic cost functions

Network optimization under uncertainty

Newton-Raphson consensus for distributed convex optimization

Distributed Nesterov-like gradient algorithms

Convergence Rates of Distributed Nesterov-Like Gradient Methods on Random Networks

Hierarchical gradient based identification of discrete-time delay systems

Distributed Nesterov-like gradient algorithms

Similar Documents

Distributed Nesterov gradient methods for random networks: Convergence in probability and convergence rates

Distributed algorithms for optimization problems with equality constraints

Convergence Rates of Distributed Nesterov-Like Gradient Methods on Random Networks

The convergence rate of Newton-Raphson consensus optimization for quadratic cost functions

Network optimization under uncertainty

Newton-Raphson consensus for distributed convex optimization

Distributed Nesterov-like gradient algorithms

Convergence Rates of Distributed Nesterov-Like Gradient Methods on Random Networks

Hierarchical gradient based identification of discrete-time delay systems

Distributed Nesterov-like gradient algorithms