ATA: Adaptive Task Allocation for Efficient Resource Management in Distributed Machine Learning

Thank you for the review

they lack real-world experiments on real-world benchmarks such as MLPerf.'}

There might be a misunderstanding on the nature of our contribution: We propose an allocation strategy across workers that adapts to their computation times and that is agnostic to the specifics of the task. This means that the behaviour of our algorithm does not depend on the optimization algorithm used, the dataset, the loss function, etc. Instead, it only depends on the observed computation times. This means that, given a sequence of computation times for any number of workers and a training loss curve, anyone can immediately simulate how our algorithm would affect the total computation time. Indeed, this would even work for other tasks different than optimization. Besides, MLPerf does not contain benchmarks for distributed optimization or bandit algorithms.

That said, to answer the reviewer's point, we ran additional experiments using a CNN trained with Adam on the CIFAR-100 dataset. The plots can be found here.

We would like to thank the reviewer for their valuable feedback.

The paper only shows the simulation results, but there is no real dataset experiment (e.g. distributed deep learning training allocation) to show the performance of their approach.

There might be a misunderstanding on the nature of our contribution: We propose an allocation strategy across workers that adapts to their computation times and that is agnostic to the specifics of the task. This means that the behaviour of our algorithm does not depend on the optimization algorithm used, the dataset, the loss function, etc. Instead, it only depends on the observed computation times. This means that, given a sequence of computation times for any number of workers and a training loss curve, anyone can immediately simulate how our algorithm would affect the total computation time. Indeed, this would even work for other tasks different than optimization.

That said, to answer to the reviewer's point, we ran additional experiments using a CNN trained with Adam on the CIFAR-100 dataset. The plots can be found here.

Given that the computation time of worker nodes may be affected by dynamic load, task switching, etc. The distribution assumption and bound of the nodes may not be practical in real-world scenario.

We acknowledge the reviewer's point that incorporating dynamic load and task switching would align the model more closely with practical scenarios. However, to the best of our knowledge, this is the first work on adaptive online allocation under a limited budget that provides strong theoretical guarantees on the optimality of the allocation strategy. It seems a bit unfair to require the solution of all the possible problems in a single first paper. The assumptions made regarding the distribution of computing times are standard and commonly adopted in the literature for modeling such quantities. We leave extending the framework to accommodate more general and irregular distributions for future work.

It seems that there is no computational complexity analysis of the proposed method, and the comparison with baselines.

We do discuss the computational complexity, but maybe we could stress it more. Specifically, for our main procedures, ATA and ATA-Empirical, the computational complexity per round is primarily determined by the step of computing the allocation $a_k$ (line 5 in Algorithm 1). As stated in lines 205-208, the complexity of this step is linear in $n$ when the number of workers $n$ exceeds the task budget $B$, demonstrating the efficiency of our approach. For more details please check Section C of the appendix.

The experiment section lacks explanation of parameter settings.

Thank you for pointing this out. We noticed that the dimensionality and stepsize were missing. For our experiments, we chose $d=100$ and a stepsize of $\gamma=10^{-4}$. Is there anything else we may have missed? We will include all the missing information in the camera-ready version of the paper.

Thank you for the review

The paper provides theoretical guarantees in the framework of online convex bandit

Since the action set is discrete, the proposed reduction does not fall under the framework of online convex bandits but rather corresponds to a combinatorial bandit problem.

however, given that this is for a machine learning publication, a thorough evaluation (and adaptation) using standard benchmark datasets and more complex objective functions would be more appropriate.

Please take a look at our response to reviewer bw5d. We also provide additional experiments here.

Weakness 1

This choice does not affect the theoretical results. More in detail, in the initial phase of the procedure, due to the definition $s_{i,k} = (\hat{\mu}\_{i,k} - \text{conf}(i,k))\_{+}$, all workers satisfy $s\_ {i, k} = 0$. After this warm-up stage, the scores $s_{i,k}$ become strictly positive. Recall that at round $k$, $\hat{\mu}\_{i,k}$ denotes the empirical mean of the computation times for worker $i$, and $\text{conf}(i,k)$ is a confidence term of order $\alpha^2 \sqrt{\frac{\ln(2k^2)}{K{i,k}}}$, where $K_{i,k}$ is the number of times worker $i$ has been queried up to round $k$. This implies that the number of rounds for which $s_{i,k} = 0$ is at most $\alpha^2 \ln(k) / \mu_i^2$.

Furthermore, in the theoretical guarantees--specifically in the upper bound of Theorem 6.1 (see also Equation (11))--the number of rounds in which worker $i$ incurs a loss due to overallocation is of order $\alpha^2 \ln(k)/\left(\mu_i - \frac{\ell(\bar{a}, \mu)}{\bar{a}i + k_i}\right)^2$. This shows that the losses incurred during the warm-up stage, where $s_{i,k} = 0$, are dominated by those arising when $s_{i,k} > 0$ for all $i$. A more detailed analysis is provided in the proof of Theorem 6.1 (Section D.1).

In practice, during the warm-up phase when many $s_{i,k} = 0$, the allocation $a_k$ (line 5 of Algorithm 1) is not uniquely defined. As noted by the reviewer, we resolve this by uniformly distributing the workload among the workers with $s_{i,k} = 0$. However, any heuristic that ensures $a_k \in \arg\min_a \ell(a, s_k)$ could be used without any change to the theoretical guarantees. We chose the uniform strategy for its simplicity, and as our experiments show, it applies only during a small fraction of the early rounds. We will add this clarification as a remark in the main body of the paper.

Weakness 2

This is a limitation of virtually any bandit algorithm. In fact, in the case of bounded distributions, many existing procedures assume knowledge of the range of the losses. Moreover, we do not believe it is possible to design a completely parameter-free procedure for the problem we considered because proving any concentration result on the empirical mean of a random variable without any assumption on its variance is known to be impossible.

That said, we would like to draw the reviewer's attention to the fact that ATA-Empirical requires only $\eta$ as input, instead of $\alpha$. That is, each of our algorithms requires only a single distribution-dependent parameter. For example, in cases where the learner knows that the computation times approximately follow an exponential distribution--which is a common modeling assumption (see lines 152–160)--it is advantageous to use ATA-Empirical, since $\eta$ is necessarily of constant order (i.e., $O(1)$).

Regarding the warm-up phase where $s_{i,k} = 0$: as with ATA, in ATA-Empirical, a larger value of $\eta$ results in a longer initial phase during which $s_{i,k} = 0$. However, the previous observation still holds: The loss incurred during this stage is asymptotically dominated by the regret bound guaranteed by the algorithm.

Weakness 3

We are not entirely certain we understand the reviewer’s point. The confidence bounds used for the computation times increase with the number of iterations (ensuring exploration) and naturally shrink with the number of observed samples from the corresponding distribution (this quantity is denoted $K_{i,k}$ for worker $i$ up to round $k$). These bounds are derived using concentration inequalities for sub-exponential distributions (see Proposition E.1).

Also, our theoretical guarantees are established under the assumption of stationary distributions, hence, the expected value of the workers' running times cannot change. We believe that, given this is--to the best of our knowledge--the first contribution addressing adaptive allocation with partial feedback and theoretical guarantees, it is both natural and appropriate to begin with the stationary setting. This assumption is also standard in the majority of bandit literature. We leave extending the analysis to the non-stationary case, where workers' distributions may vary over time, as an important direction for future work.

We would like to thank the reviewer for their valuable feedback.

missing ablation study (e.g., impact of data-dependent concentration inequality)

We are not sure what the reviewer means here: We did study the impact of the data-dependent concentration inequality. Indeed, we test both ATA (the algorithm without the adaptive concentration) and ATA-Empirical (the one with the adaptive one).

realistic simulation (when workers have heterogeneous and time-vayring computation speeds)

We did additional experiments with heterogeneous time distributions for the workers, using five types: Exponential, Uniform, Half-Normal, Lognormal, and Gamma. The plots are available here. The results show that the algorithms are robust across different distributions.

Also, the computation speeds are time-varying because they are stochastic. It is true that we did not consider the setting of distribution changing over time, however, we believe that, given this is -to the best of our knowledge- the first contribution addressing adaptive allocation with partial feedback and theoretical guarantees, it is both natural and appropriate to begin with the stationary setting.

Is there any case that information of previous runs degrade performance or slow down the convergence? Could you elaborate more on the impact of using prior information?

On page 8, we discussed the possibility of using prior estimates of computation times from previous runs. We add more details here on this possibility: If the prior estimates are completely off, the algorithm could make wrong choices in the first rounds, however sooner or later the exploration (that is always active) will cause the algorithm to gather enough data to converge to the correct estimate of the means. Hence, the asymptotic guarantee will be the same and prior knowledge almost always accelerates convergence. To validate this, we conducted additional experiments, please check the plots here.