Non-Stationary Gradient Descent for Optimal Auto-Scaling in Serverless Platforms

Jonatha Anselmi, Bruno Gaujal, Louis-Sébastien RebuffiIEEE Trans. Netw 2025 · DOI

Sure, here's a blog-style summary of the paper "Non-Stationary Gradient Descent for Optimal Auto-Scaling in Serverless Platforms":

TL;DR

This paper introduces a novel non-stationary gradient descent algorithm to optimize auto-scaling in serverless platforms. By dynamically adjusting the number of server instances provisioned, it aims to strike a better balance between user-perceived performance and energy consumption than existing methods. The proposed algorithm is shown to converge to an optimal scaling strategy with a theoretical guarantee.

What Problem Does This Paper Address?

Serverless computing platforms, like AWS Lambda, automatically scale resources to meet demand. A common auto-scaling strategy is "per-request" scaling, where a new server instance is launched only when a job arrives and no idle servers are available. This can lead to delays (cold starts) for users. The challenge is to decide how many new server instances to launch when this happens. Launching too few can lead to poor performance, while launching too many wastes energy. Existing approaches often launch just one new server, which is suboptimal. This paper addresses the problem of finding the optimal number of additional server instances to launch proactively to minimize a cost function that balances performance (minimizing latency) and energy consumption, especially in dynamic and unpredictable environments.

Methods

The core of this paper is a novel non-stationary Kiefer-Wolfowitz (KW) algorithm. Traditional KW algorithms rely on samples from stationary distributions of Markov chains. However, in real-world systems like serverless platforms, we can only observe transient behavior. The authors adapt the KW algorithm to handle these "non-stationary samples."

Key methodological contributions include:

  • A Generalized Markov Model: They extend a standard Markov model for serverless platforms to include a parameter $\theta$, representing the number of extra idle servers to provision when a job arrives and no servers are busy.
  • Non-Stationary Gradient Descent: The proposed algorithm simulates the system for a duration related to its mixing time to obtain samples that are "close enough" to stationary. This allows them to estimate the gradient of the cost function even with transient data.
  • Theoretical Guarantees: They provide theoretical proofs for the algorithm's convergence to the optimal scaling parameter $\theta^*$ and establish a convergence rate of $O(n^{-2/3})$, where $n$ is the number of iterations.
  • Smooth Parameter Function: To ensure the algorithm's stability and theoretical properties, they introduce a smoothed version of the scaling parameter $\theta$ that maps any real value to a feasible range of server instances.

Datasets

Not discussed in the paper. The evaluation uses simulated data based on a Markov model of serverless platform dynamics.

Key Insights and Ideas

  • Proactive Scaling is Key: Launching just one server when needed is often suboptimal. Proactively provisioning a small surplus of idle servers can significantly improve performance without excessive energy waste.
  • Non-Stationarity is the Main Hurdle: The biggest challenge in applying optimization techniques to real-world systems is dealing with transient, non-stationary data, rather than clean stationary samples. This paper offers a principled way to handle this.
  • The Trade-off is Quantifiable: The paper demonstrates that there's a clear trade-off between performance and energy, and their algorithm can find a sweet spot that offers significant gains (5-8%) over simpler strategies.
  • Theoretical Rigor Matters: Providing convergence guarantees is crucial for trusting and deploying such optimization algorithms in critical systems.

Key Results

  • The proposed non-stationary KW algorithm converges almost surely to the optimal scaling parameter $\theta^*$.
  • The algorithm achieves a convergence rate of $O(n^{-2/3})$.
  • Numerical simulations show that their approach can yield relative performance gains of around 5-8% compared to existing scale-up rules (where $\theta=0$).
  • The simulations also highlight that the "fast $\theta$-update" approach (updating $\theta$ too frequently without waiting for sufficient data) does not work and leads to suboptimal or unstable behavior.

Limitations and Future Work

  • Assumptions: The theoretical results rely on several assumptions, including the uniform mixing time of the underlying Markov chain and the strong convexity of the cost function. While these are argued to be satisfied in the auto-scaling context, they might limit applicability to other domains.
  • Parameter Tuning: The performance of the algorithm depends on the choice of step-size sequences and simulation lengths ($T_n$). While they provide guidance, optimal tuning might still require experimentation.
  • Future Work: The authors suggest exploring extensions to more complex scenarios, such as non-exponential service times or more intricate auto-scaling policies. They also mention that the framework could be applied beyond auto-scaling to other problems involving non-stationary stochastic optimization.

Summary updated

BibTeX
@article{anselmi2025non,
  author = {Jonatha Anselmi and Bruno Gaujal and Louis-Sébastien Rebuffi},
  title = {{Non-Stationary Gradient Descent for Optimal Auto-Scaling in Serverless Platforms}},
  journal = {IEEE Trans. Netw.},
  year = {2025},
  doi = {10.1109/ton.2025.3538982},
}
Figure