Abstract
Online Optimization with Budget Constraints (OOBC) presents significant challenges in scenarios with short decision horizons and strict resource limits. Traditional iterative algorithms often fail to converge quickly enough, while black-box reinforcement learning models struggle with robustness and constraint satisfaction. This paper proposes Learning-Assisted Algorithm Unrolling (LAAU), a hybrid framework that unrolls the optimization process and utilizes machine learning to predict Lagrangian multipliers. By embedding a differentiable optimization layer, LAAU leverages problem structure to achieve near-optimal utility and high robustness. Evaluations on real-world cloud workload data show that LAAU outperforms existing heuristics and traditional dual methods.
Introduction
In many real-world applications, such as cloud resource allocation or power grid management, decisions must be made sequentially under strict total budget constraints. These problems, termed Online Optimization with Budget Constraints (OOBC), are particularly difficult when the decision window is short. In such "short-horizon" settings, standard iterative methods like Dual Mirror Descent may not have sufficient time to converge to an optimal solution. Furthermore, physical constraints in these domains are often "hard," meaning violations are unacceptable.
The LAAU Framework
The core innovation of this work is Learning-Assisted Algorithm Unrolling (LAAU). Rather than treating the entire decision process as a black box, LAAU unrolls the optimization pipeline into a sequence of units, each corresponding to a time step.
As shown in Figure 1, each unrolling unit consists of three primary components:
- ML-based Multiplier Update: A neural network predicts the Lagrangian multiplier ($\lambda_t$), which acts as a "shadow price" for the resource. This allows the model to learn complex temporal patterns and adjust prices based on the remaining budget.
- Optimization Layer: This layer takes the predicted price and solves a standard convex optimization problem to determine the optimal action ($x_t$) for the current step.
- Budget Update: The framework explicitly tracks and updates the remaining budget, ensuring that the physical constraints of the problem are respected.
To enable end-to-end training via backpropagation, the authors utilize Karush-Kuhn-Tucker (KKT) conditions to derive gradients through the optimization layer, allowing the ML model to learn how its price predictions influence the final utility and budget consumption.
Experimental Evaluation
The researchers evaluated LAAU using the Azure cloud workload dataset, focusing on a resource allocation task aimed at maximizing weighted fairness under strict CPU budget constraints. LAAU was compared against several benchmarks, including heuristics (Equal allocation), traditional methods (DGD, MW), and end-to-end Reinforcement Learning (RL).
The results, summarized in Figure 2, highlight several key findings:
- Superior Utility: LAAU consistently achieves higher average utility than traditional experts like DGD and MW, especially in short episodes ($N=10$).
- Near-Oracle Performance: The performance of LAAU closely approaches the "Offline Optimal" (OPT), which represents the theoretical maximum utility achievable with full future knowledge.
- Robustness to Distribution Shift: LAAU demonstrated significant robustness to distribution shifts. While pure RL models saw performance drops when noise was introduced to the training data, LAAU's reliance on the underlying problem structure allowed it to maintain high utility.
Conclusion
LAAU represents a significant step forward in solving constrained online optimization problems. By combining the predictive power of machine learning with the mathematical rigor of optimization unrolling, it provides a robust and efficient solution for short-horizon resource allocation. Future work will focus on extending this framework to non-convex problems and multi-agent systems.
Summary updated