Akhavan, A;
Pontil, M;
Tsybakov, AB;
(2021)
Distributed Zero-Order Optimization under Adversarial Noise.
Advances in Neural Information Processing Systems
, 13
pp. 10209-10220.
Preview |
Text
NeurIPS-2021-distributed-zero-order-optimization-under-adversarial-noise-Paper.pdf - Published Version Download (289kB) | Preview |
Abstract
We study the problem of distributed zero-order optimization for a class of strongly convex functions. They are formed by the average of local objectives, associated to different nodes in a prescribed network. We propose a distributed zero-order projected gradient descent algorithm to solve the problem. Exchange of information within the network is permitted only between neighbouring nodes. An important feature of our procedure is that it can query only function values, subject to a general noise model, that does not require zero mean or independent errors. We derive upper bounds for the average cumulative regret and optimization error of the algorithm which highlight the role played by a network connectivity parameter, the number of variables, the noise level, the strong convexity parameter, and smoothness properties of the local objectives. The bounds indicate some key improvements of our method over the state-of-the-art, both in the distributed and standard zero-order optimization settings. We also comment on lower bounds and observe that the dependency over certain function parameters in the bound is nearly optimal.
| Type: | Article |
|---|---|
| Title: | Distributed Zero-Order Optimization under Adversarial Noise |
| Open access status: | An open access version is available from UCL Discovery |
| Publisher version: | https://proceedings.neurips.cc/paper/2021/hash/548... |
| Language: | English |
| Additional information: | This version is the version of record. For information on re-use, please refer to the publisher's terms and conditions. |
| UCL classification: | UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science UCL > Provost and Vice Provost Offices > UCL BEAMS UCL |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10150683 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
