Abstract
Optimization theory has been widely studied in academia and finds a large variety of applications in industry. Robust convex optimization is a branch of optimization theory in which the variables or parameters involved have a certain level of uncertainty. In this work, we consider the online robust optimization meta-algorithm by Ben-Tal et al. and show that for a large range of stochastic subgradients, this algorithm has the same guarantee as the original non-stochastic version. We develop a hybrid quantum-classical version of this algorithm and show that an at most quadratic improvement in terms of the dimension can be achieved. The speedup is due to the use of quantum state preparation, quantum norm estimation, and quantum multi-sampling. We apply our quantum meta-algorithm to examples such as robust linear programs and robust semidefinite programs and give applications of these robust optimization problems in finance and engineering.
Introduction
Convex optimization is a cornerstone of modern machine learning, engineering, and finance. However, in real-world scenarios, the parameters fed into these models are rarely exact; they are subject to noise, measurement errors, and inherent uncertainty. Robust convex optimization addresses this by requiring that optimization constraints hold true for all possible parameters within a defined "uncertainty set."
While theoretically sound, robust optimization is notoriously expensive to compute for large-scale problems. To bypass this, Ben-Tal et al. previously developed a classical "meta-algorithm." Instead of solving the massive robust problem directly, their algorithm uses online learning (specifically, online subgradient descent) to iteratively update the noise parameters and solve a sequence of simpler, non-robust problems. This paper explores whether quantum computing can accelerate this meta-algorithm, specifically targeting the computational bottleneck of calculating exact subgradients for every noise parameter at every iteration.
Methodology: From Classical to Quantum
The authors tackle the problem in two main steps: generalizing the classical algorithm to handle stochasticity and then implementing a quantum sampling subroutine.
1. Generalizing to Stochastic Subgradients
First, the authors prove that the original Ben-Tal meta-algorithm does not actually need exact subgradients to guarantee convergence. They adapt the algorithm to use a stochastic (noisy) subgradient oracle, proving that as long as the expected value of the random vectors is proportional to the true subgradients, the regret bounds and convergence guarantees still hold. This realization is the crucial "aha" moment: because quantum mechanics is inherently probabilistic, framing the classical algorithm stochastically creates the perfect opening for a quantum sampling subroutine.
2. Quantum Sampling-Based Algorithm
With the stochastic foundation laid, they design a quantum algorithm to efficiently generate these stochastic subgradients. Instead of computing the full $md$-dimensional subgradient vector exactly (where $m$ is the number of noise vectors and $d$ is their dimension), they use:
- Quantum state preparation to create a superposition proportional to the subgradients.
- Quantum norm estimation to estimate the $\ell_1$-norm of the subgradient vectors.
- Quantum multi-sampling to perform $\ell_1$-sampling from the quantum state.
By measuring this quantum state multiple times, they construct an $\ell_1$-sampled stochastic subgradient, drastically reducing the number of times they need to query the underlying subgradient oracle.
Complexity Analysis and Key Results
The primary contribution of this work is the theoretical speedup in algorithmic complexity. The classical algorithm requires $\mathcal{O}(\frac{G_2^2 m d D^2}{\epsilon^2})$ calls to the subgradient oracle. The new quantum algorithm requires $\tilde{\mathcal{O}}(\frac{\sqrt{G_1 G_\infty} G_2 \sqrt{m d} D^2}{\epsilon^2})$ calls.
As shown in the table above, the quantum algorithm achieves up to a quadratic speedup in both $m$ (number of noise vectors) and $d$ (dimension). This speedup is most pronounced when the product of the $\ell_1$ and $\ell_\infty$ bounds ($G_1 G_\infty$) is comparable to the squared $\ell_2$ bound ($G_2^2$). Even in less ideal geometric scenarios, a quadratic speedup in $d$ is maintained. Furthermore, the quantum approach offers improvements in the number of calls to the optimization oracle ($\mathcal{O}_{\mathcal{P}}$).
Real-World Applications
The authors mathematically demonstrate how this quantum meta-algorithm applies to critical industry problems:
- Robust Linear Programs: For example, the Global Maximum Return Portfolio (GMRP) problem in finance, where asset returns are uncertain.
- Robust Semidefinite Programs (SDPs): For example, the Truss Topology Design (TTD) problem in civil engineering, where external physical loads on a structure are uncertain.
Limitations and Future Work
The quantum speedup is highly dependent on the geometric properties of the subgradients—specifically, the relationship between their $\ell_1$, $\ell_2$, and $\ell_\infty$ norms. If there is no good mathematical promise on these quantities, the quantum algorithm's complexity degrades to match the classical algorithm. Additionally, the current framework assumes the uncertainty set is strictly convex.
Future work suggests extending this quantum framework to more general problems where the uncertainty set is not necessarily convex, such as robust quadratic programming (useful for Markowitz mean-variance portfolio optimization). The authors also highlight the open problem of proving a theoretical lower bound on the number of calls required to the optimization oracle.
Summary updated