Motivation

Parallelism is a popular approach to scale SGD, in which a large number of processing devices (think CPUs, GPUs, etc.) are orchestrated together to improve training throughput. Traditionally, parallel SGD is formulated as a synchronous algorithm, but unfortunately that struggles due to significant synchronisation overhead.

For this reason, asynchronous implementations are increasingly common. These provide an improvement in throughput at the expense of introducing stale gradients which reduce the effectiveness of individual SGD steps. Previous approaches to mitigate the downsides of asynchronous processing include adaptively adjusting the number of worker threads or the learning rate, but at their core these are still fully asynchronous and hence still suffer from lower accuracy due to frequent staleness.

Interval-Asynchrony

When executing SGD asynchronously (i.e. according to Hogwild! semantics), workers are free to update a shared set of model parameters at any time. This means that between the moment that a given worker pulls a copy of the parameters, and the moment that they finish calculating a gradient to update the model, the model may have been updated several times by other workers. The number of overlapping updates is called staleness.

In this work we analyse the origin of such staleness, and as a result propose Interval-Asynchrony, a semi-asynchronous method which retains high throughput while reducing gradient staleness, both on average as well as with a hard upper bound.

To do so, we introduce periodic asynchronous intervals, within which SGD is executed asynchronously, but between which gradient computations may not cross. The size of these intervals determines the degree of asynchrony, providing us with an adjustable scale.

Interval Size

It turns out that the optimal size of asynchronous intervals — the parameter that Interval-Asynchrony introduces — depends on the stage of execution. It tends to require smaller intervals later on, and can put up with larger intervals earlier for better throughput.

Unsurprisingly, it's not trivial to determine the interval size schedule beforehand. In the paper we propose two methods for adjusting it, and evaluate each:

• Linear decay. Reduce interval size by a constant for every n accepted steps.
• Probing. This method, inspired by ElAsyncSGD, periodically trials execution at nearby interval sizes and checks if any seem to work better at the current stage.

When dialled in, linear decay has the potential to outperform probing. However, we propose that probing is easier to apply to new, unknown workloads. This behaviour can be seen in figures 4 and 5 in the paper.

Artefacts & Downloads

Here, you can find a recording from my presentation of this paper at Euro-Par 2025 in Dresden. You can also find a slightly more in-depth blog post about the paper and the conference here!

• Presentation slides (PDF) (ODP)
• Conference paper (PDF)
• C++ implementation

Evaluation

Our focus for this work is on CPU training for highly parallel systems. We therefore picked baseline algorithms and training workloads that are sensible for this setting.

We compared against the following algorithms that control the execution:

• Fully synchronous (traditional);
• Fully asynchronous; and
• ElAsyncSGD — fully asynchronous with dynamic number of threads.

And we considered both CIFAR-10 and CIFAR-100 datasets, for which we train a model to recognise what a given image is of.

I recommend reading section 5 of the paper for an in-depth evaluation, but the takeaway numbers are:

• Reduction in training time to same accuracy of up to 32%.
• Solid scalability up to 128 threads.
• Better final accuracy compared to asynchronous baselines, and competitive with fully synchronous (exact) method.

Visualisation

To better explain how Interval-Asynchrony works, compared to synchronous and asynchronous, you can play around with the interactive visualisation below. Experiment with each execution mode, and consider:

• How do different interval sizes affect throughput and staleness?
• What's the difference in staleness distribution between our method and asynchronous?

Simply press "Begin" to start.

---

Motivation

Hyperparameter tuning is a critical component of modern machine learning pipelines, as the performance and efficiency of many data processing workloads depend heavily on the choice of hyperparameters. We can see a perfect example of this by looking at Paper A, in which we significantly speed up SGD but only by introducing a tuneable hyperparameter.

While most traditional tuning methods in the literature assume static configurations, many hyperparameters (including the aforementioned interval size for Interval-Asynchrony) benefit from being adapted during execution.

There are existing works which implicitly exploit scheduling effects, including PBT and PB2, however they just consider a flat population of independent trials, and only model algorithmic hyperparameters as tuneable. As a result, they lack principled mechanisms for branching executions, consideration of system-level parameters for scheduling, and re-evaluation of configurations under stochasticity.

ForestTune

Overall, our idea is this: organise tuning trials as nodes in a forest structure. This allows checkpoints to branch and consider several hyperparameter schedules more efficiently.

Our proposed method, ForestTune, represents a tuning checkpoint (i.e. a pair of a model checkpoint and a set of hyperparameters which that checkpoint was reached with) as a node in a forest, pictured below. This structure allows executions to branch and explore alternative schedules without restarting training from scratch. Furthermore, system resource parameters are treated as first‑class hyperparameters, enabling efficient trial scheduling and reuse of intermediate execution state.

The diagram above represents an example of how a forest might develop over the course of a ForestTune execution. The numbers refer to the iteration during which a node was created.

Forest Growth

All nodes that get created are subsequently evaluated to guage their performance. Our growth algorithm therefore needs to be designed precisely: it must be discerning enough that it only proposes new nodes that are actually worth taking the time to evaluate, while simultaneously being broad enough to discover unexpected optimal schedules.

We divide an entire ForestTune execution into a number of seasons. In each season, a forward pass is run over the whole forest from root to leaf, and at each depth, new nodes are branched from existing ones.

The diagram above describes the different mechanisms through which new nodes can be produced. Each individual node holds its own Bayesian optimisation model (which it initially inherits from its parent) that allows it to smartly choose child configurations. Bayesian optimisation is therefore the preferred generation method, but in such cases that the B.O. models are not yet populated with enough samples, we use random sampling for root nodes and mutation (small offsets from parent configurations) for non-root nodes' configurations.

Evaluation

We assess ForestTune against two state-of-the-art hyperparameter tuning baselines: PB2, which, like ForestTune, also adjusts hyperparameters during training; and BOHB, a widely-used method that holds each configuration fixed per trial. Our evaluation aims to address the following questions:

• Does ForestTune's support for mutable hyperparameters yield better-tuned models, and reach a given quality faster, than the baselines?
• Does ForestTune efficiently convert wall-clock time and evaluation budget into tuning progress?
• Is ForestTune practical in terms of the memory and storage overhead?

In short, the answer to all the above questions is "yes". I'd recommend taking a look at the paper for a detailed evaluation, but for a taste, look at this plot:

Higher is better. ForestTune is able to much more efficiently reach better model accuracy, due to its efficient resource-aware configuration evaluation scheduling and the fact that it can evaluate several similar schedules much more quickly than PB2 due to its ability to resume from checkpoints.