- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper studies whether the gap between homogeneous and heterogeneous asynchronous optimization can be reduced under additional assumptions, without requiring identical local objectives. In the convex setting, it establishes lower bounds showing that first- and second-order similarity cannot improve the unfavorable dependence on worker computation times for arbitrary randomized algorithms in sufficiently high-accuracy regimes. It further shows that weak interpolation alone is insufficient. Under strong interpolation and a uniform local Polyak–Łojasiewicz condition, the paper proves that Rennala SGD achieves a time-complexity bound matching the worker-time dependence of the best-known homogeneous result.
Critical strengths
-
The lower bounds identify fundamental limitations of commonly used assumptions. The paper shows that the unfavorable arithmetic-mean dependence on worker computation times persists even with arbitrarily small first-order differences and identical Hessians, in the specified high-accuracy regime. Since the result applies to arbitrary randomized algorithms, it provides a consequential explanation of why similarity assumptions alone cannot generally bridge the homogeneous–heterogeneous gap.
-
The positive result provides a meaningful alternative to identical local objectives. Under strong interpolation and a uniform local PL condition, the analysis recovers the favorable worker-time dependence despite the biased gradient aggregation of Rennala SGD.
Critical weaknesses
None
Questions for authors
Clarification on the validation of Theorem 3.8. Algorithm 3 shifts the local matrices using the minimum eigenvalue of their average, although the Gaussian scaling can make individual matrices indefinite. In Section H.2, setting $ b_i = A_i \bar{x}_* $ therefore ensures a common stationary point, but does not by itself establish strong interpolation. How were the local convexity and common-minimizer assumptions verified for the reported instances? Were additional safeguards used in the implementation but omitted from Algorithm 3?