Communication complexity of convex optimization
type: Item
instance of: scholarly article
title: Communication complexity of convex optimization
zbMATH Open document ID: 0641.68063
DOI: 10.1016/0885-064X(87)90013-6
author: John N. Tsitsiklis
author: Zhi-Quan Luo
published in: Journal of Complexity
publication date: 1987-01-01T00:00:00Z
review text: We consider a situation where each of two processors has access to a different convex function \(f_ i\), \(i=1,2\), defined on a common bounded domain. The processors are to exchange a number of binary messages, according to some protocol, until they find a point in the domain at which \(f_ 1+f_ 2\) is minimized, within some prespecified accuracy \(\epsilon\). Our objective is to determine protocols under which the number of exchanged messages is minimized.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 65K10
zbMATH DE Number: 4045147
zbMATH Keywords: communication complexity
zbMATH Keywords: convex optimization
zbMATH Keywords: protocols
MaRDI profile type: Publication
cites work: Lower Bounds on Information Transfer in Distributed Computations
cites work: Q3967358
cites work: Communication Complexity of Computing the Hamming Distance
cites work: Q4739657
cites work: On the complexity of designing distributed protocols
cites work: Q3883494
cites work: Q3326832
full work available at URL: 0885-064x(87)90013-6
OpenAlex ID: W139031692
description: scientific article; zbMATH DE number 4045147