acceptodds
Under review as a conference paper at ICLR 2027

Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult

53 views

Abstract

Modern large-scale machine learning tasks often require multiple workers, devices, CPUs, or GPUs to compute stochastic gradients in parallel and asynchronously to train model weights. Theoretical results typically distinguish between two settings: (i) the homogeneous setting, where all workers have access to the same data distribution, and (ii) the heterogeneous setting, where each worker operates on different data distributions. Known optimal time complexities in these settings reveal a significant gap, with far more pessimistic guarantees in the heterogeneous case. In this work, we investigate whether these pessimistic optimal time complexities can be overcome under different assumptions. Surprisingly, we show that improvement is provably impossible under widely used first- and second-order similarity assumptions for any randomized algorithm. We then turn to the interpolation regime and demonstrate that the weak interpolation assumption alone is also insufficient. Finally, we introduce a minimal combination of irreducible assumptions, strong interpolation and the local Polyak-Lojasiewicz condition, to derive a new time complexity bound that matches the dependence on worker computation times in the best-known result in the homogeneous setting, without requiring identical data distributions.

Primary area:
optimization
Keywords:
parallel and asynchronous methods, lower bounds, homogeneous optimization, heterogeneous optimization

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.75 over 4 reviews, above 99% of the others.
Reviewer_C4d5OpenReview ↗
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
  1. 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.

  2. 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?

Reviewer_qW48OpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This article analyzes the convergence rate of stochastic algorithms to bridge the gap between homogeneous and heterogeneous asynchronous setups. By studying which assumptions on the convex objective function are required to achieve a similar convergence rate in both setups, lower bounds on the convergence rates are given. Under a quite strong assumption, a similar rate is obtained for a special asynchronous SGD method.

Critical strengths

It is an original contribution to study various theoretical conditions under which the gap between homogeneous and heterogeneous asynchronous setups can be closed. The results show that common assumptions based on first and second-order similarity are not sufficient, based on the lower bounds of the convergence rate obtained from min-max estimation theory in statistics.

Critical weaknesses

From the results obtained in the article, it is not clear whether a similar convergence gap in homogeneous and heterogeneous asynchronous setups could be said for non-convex functions. Maybe I missed this point in the article, but if this point could be clarified, that would be better.

Questions for authors

I have only some minor questions to clarify the results:

  1. The complexity given on line 085 for the strongly convex case may have a typo, as the first part sqrt(L) / sqrt(mu) does not depend on epsilon.

  2. Please clarify whether the complexity of Minibatch SGD on line 106 to the critical points in the non-convex setting uses some average or the last iterate, or is based on some other stopping criterion.

  3. A typo in Table 1 regarding x_star on line 325, should it be replaced by bar x_star ?

Reviewer_jeuzOpenReview ↗
Rating
4
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the convergence of asynchronous SGD. In particular, in the heterogeneous setting, the theoretical convergence rate bound for asynchronous SGD is worse than in the homogeneous setting. They study the problem of adding what conditions could make the error bound in the heterogeneous setting have the same order as in the homogeneous setting. First, they show that under some standard similarity assumptions, it is unlikely to bridge the gap. Then, they propose stronger assumptions and show that these assumptions are sufficient and necessary to bridge the gap.

Critical strengths

This paper is theoretically valuable in that it answers the question of under what conditions the convergence rate bound of asynchronous SGD in the heterogeneous setting could match that in the homogeneous setting.

They not only show that some standard assumptions are not sufficient to bridge the gap, but also prove that some stronger assumptions are both sufficient and necessary to bridge the gap. This is elegant.

Critical weaknesses

Honestly, I have no critical concerns regarding this paper. I have the only one comment:

Can the authors provide some insights on why the counterexample in Theorem 2.3 works? I think this is important because, although the counterexamples show that bridging the gap is unlikely, additional explanations of why it is unlikely would also be valuable and help readers understand it better.

Questions for authors

I have two questions:

First, Assumption 3.3 seems very strong since it implies that minfi(x)min f_i(x) is equivalent to min∑i=1nfi(x)min \sum_{i=1}^n f_i(x). Then, under this assumption, the training problem becomes much easier. Can you provide some comments on what additional valuable information (such as in algorithm design) this work can offer, beyond its theoretical significance?

Second, does the theoretical result in this paper match the practice? For example, if we consider a heterogeneous setting (each f_i corresponds to a data set DiD_i) and the corresponding homogeneous setting (all fif_i's are identical and are defined by ∪i=1nDi\cup_{i=1}^n D_i), and we run the asynchronous SGD to solve the optimization problem, then will the convergence speed differ significantly?

Reviewer_soaDOpenReview ↗
Rating
4
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper investigates the gap in time complexity between homogeneous and heterogeneous asynchronous stochastic optimization. Through an analysis of Malenia SGD and Rennala SGD, the authors examine which assumptions allow improved guarantees in the heterogeneous setting. They show that first- and second-order similarity, as well as weak interpolation, are insufficient to close the gap in the small-error regime. Under convexity, local smoothness, strong interpolation, and a local Polyak–Łojasiewicz (PŁ) condition, they establish that Rennala SGD achieves the same dependence on worker computation times as the homogeneous bound, without requiring identical local objectives. The paper appears sufficiently complete, although I have questions about the extent of objective heterogeneity that the strong interpolation assumption permits.

Critical strengths
  1. The paper investigates a well-motivated question: which additional assumptions allow heterogeneous asynchronous optimization to overcome the unfavorable dependence on the arithmetic mean of worker computation times τi\\{\tau_i\\}?
  2. The paper systematically examines the roles of different assumptions. It establishes the insufficiency of first- and second-order similarity and weak interpolation, and shows that neither strong interpolation nor the local PŁ condition can be dropped from its proposed sufficient combination in the studied setting.
  3. Remarks 3.5 and 3.9 provide useful examples that clarify the relationship between similarity and interpolation assumptions and illustrate how strong interpolation accommodates non-identical local objectives.
  4. Appendix A extends the positive convergence guarantee to a model with time-varying worker computation power, including periods of worker inactivity.
Critical weaknesses
  1. The final result relies on a restrictive form of heterogeneity. Strong interpolation requires every local objective to have exactly the same set of minimizers as the global objective, so solving any individual worker’s local problem is sufficient to solve the global problem. Although the local objectives can differ, this assumption excludes disagreement among workers, a central difficulty in heterogeneous federated learning. Thus, this optimality gap is closed for a very narrow class of heterogeneous problems. The paper would benefit from a clearer discussion of this scope and of practical settings in which equality among the entire set of minimisers is justified.
  2. Assumption 1.2, Local Smoothness, is also not used for general optimal complexity bounds. This should be included in the set of assumptions that close the gap, rather than treated as a standard assumption, since it is stronger than global smoothness.
Questions for authors
  1. Although the paper focuses on asynchronous optimization, could the authors discuss whether analogous results hold in synchronous federated learning? Would closing the gap require the same assumptions, or could these assumptions be relaxed?
  2. Under strong interpolation, solving any single worker’s local problem also solves the global problem. Is the improved time complexity therefore driven by the fact that fast workers alone contain enough information to find a global solution? Could the authors explain this mechanism and explain the intuition behind why weak interpolation is not able to achieve this, where a fast worker may converge to a local minimizer that does not minimize the global objective?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.