----------------------- REVIEW 1 ---------------------
PAPER: 39
TITLE: Robust Multi-Agent Optimization: Coping with Byzantine Agents with Input Redundancy
AUTHORS: Lili Su and Nitin Vaidya
OVERALL EVALUATION: 2 (accept)
REVIEWER'S CONFIDENCE: 3 (medium)
----------- Review -----------
The paper considers the problem of distributed optimization of an objective function obtained by averaging local input functions, in presence of byzantine faults. The main result is showing that, if certain properties of the input functions are fulfilled (namely, redundancy of local optima), then the problem can be solved also in presence of byzantine faults.
The results presented in the paper are non-trivial and of interest. However, the authors could have done a better job in motivating and presenting their work.
In term of motivations, these are limited to one sentence in the abstract and one sentence in the conclusions. Please elaborate more on the potential applications of your theoretical result.
In terms of presentation, the authors should work on:
- improving notation: for instance, the constant L used in Lemma 5 and onward is not defined in the paper (I guess it is related to Lipschitz continuity, but this is not stated in the paper); also, constant \v is used in Lemma 2, but only defined later on in Th. 3.
- the authors should explicitly state that f cannot have arbitrary values, but it is upper bounded to a fraction of n depending on the case at hand. E.g., 2f+1<=n for the case of side information.
- in presenting in Section 4.1, the authors should explicitly mention that the following concern Case 2 only.
- in Section 4.5, the authors should start with a paragraph describing the conceptual steps of the sufficiency proof.
- ref [1] is missing, and there are a number of hanging references in the text.
- Appendix C, step 2; the algorithm to be referred is Algorithm 2, not Algorithm 1.
----------------------- REVIEW 2 ---------------------
PAPER: 39
TITLE: Robust Multi-Agent Optimization: Coping with Byzantine Agents with Input Redundancy
AUTHORS: Lili Su and Nitin Vaidya
OVERALL EVALUATION: 0 (borderline paper)
REVIEWER'S CONFIDENCE: 3 (medium)
----------- Review -----------
The main problem of this paper comes from its poor organization. Indeed, it does not contain any introduction, and the abstract as well as the first section starts immediately with notations and formulas, without explaining the objective of the paper from a higher perspective. Despite a section dedicated to the related work, it is hard to understand the scientific position of the paper, and its contributions. Moreover, the authors have recently published a paper at PODC on the same topic, which is not mentioned in the related work. Therefore, even if the paper may merit, the presentation appears to me as too poor for publication at SSS.
----------------------- REVIEW 3 ---------------------
PAPER: 39
TITLE: Robust Multi-Agent Optimization: Coping with Byzantine Agents with Input Redundancy
AUTHORS: Lili Su and Nitin Vaidya
OVERALL EVALUATION: 2 (accept)
REVIEWER'S CONFIDENCE: 4 (high)
----------- Review -----------
This paper presents a new algorithm for distributed optimization in the presence of Byzantine agents. Apart from minor typos, the paper is well written and results are sound. It will provide a good addition to the existence literature in this topic.
Some minor comments are in order, see bellow:
Not sure about the page limit of submissions, 33 pages seems excessive for a conference.
There is an empty spot at reference 1.
At the beginning of page 4, there is sentence that starts with reference [5], please refrain from starting a sentence with a reference number.
In page 4, the sentence “Duchi et al. [7] assumed that each realizable link failure pattern considered in [7] is assumed to admit a doubly stochastic matrix which governs the evolution dynamics of local estimates of the optimum.” requires rewrite.
Title from section 3 seems incomplete, consider a complete sentence.
The sentence at beginning of page 5 requires rewrite “Let A ∈ R k×n be a matrix that can corrects up to f arbitrary entry-wise errors in [3].”
Definitions and conditions about Byzantine broadcast should be made explicit.
Does algorithm 1 requires a complete graph? Step 2 states that communication to all agents are required. Same for step 3. This might take the distributed property of the algorithm away. This seems to be a very strong condition for the algorithm to work. This a necessary condition for x_i = x_j for all I and j for all t>0. Under this very strong assumption one could assume almost full knowledge on the network making this algorithm very restrictive and with no ad-hoc properties usually required for distributed algorithms.
Step 3 of algorithm 1 reads strange. Is this step just the assignment of the received gradients to variable y?
Please provide further justification about the classification provided in page 6. How interesting are case 1 and 2 in the context of distributed settings? It seems only case 3 is non-trivial.
There is a reference missing at the end of page 8.
In subsection 4.5 the size of faulty agents set is denoted as \phi, but previously in the paper this quantity was defined as f. Are these distinct quantities?
In Algorithm 2 it seems that w_i should depend on time. It is recommended to make this dependency explicit.
Lemma 2 used \beta without any prior definition. Idem for Theorem 2 and Lemma 3.
It is important to emphasize the difference with previous works by the same authors [7,15,21]. Please be explicit about what parts of these new extensions are not trivial.