summaries: The paper studies the dynamics of privacy loss for noisy gradient descent algorithm, whose continuous-time analogue is the Langevin diffusion process. They obtain a tight bound on the Renyi divergence between the pair of probability distributions over parameters of models with neighboring datasets. They prove for smooth and strongly convex loss functions, the privacy loss converges exponentially in the number of iterations, instead of square root in the number of iterations as in composition-based analysis of the same algorithms in the literature. For Lipschitz, smooth and strongly convex loss functions, they prove optimal utility for differential policy algorithms with a small gradient complexity.

summaries: This paper presents a theoretical framework for analyzing the privacy loss of Noisy Gradient Descent during its execution. Using the Renyi divergence as the differential privacy metric, the authors aims to understand how much information leaks for an optimization function $\frac{1}{n} \sum_{x\in \mathcal{D}} \ell (\theta; \mathbf{x})  $ and for  the dataset $\mathcal{D}=(\mathbf{x}_1,\cdots,\mathbf{x}_n).$  In order to do that, they interpolate the discrete algorithmic method of "Noisy Gradient Descent" to its stochastic continuous analogue, the famous stochastic differential equation of Focker-Plank Equation. The authors carefully construct this tracing diffusion process among two consecutive steps such that $\theta_k = \Theta_{t=\eta k}$ but $\lim_{t\to \eta (k+1)} = \Theta_{t=\eta(k+1)}$ , where $\theta_k, \Theta_{t=\eta k}$ are the  discrete/continuous parameters for the optimization. This semi-continuous interpolation permits the authors to analyze tightly the information disclosure of the initial method of Noisy Gradient Descent using Gaussian perturbation for the case of  of smooth and strongly convex loss functions.

summaries: The paper analyze Differentially Private Gradient Descent (DPGD) for optimizing a function f, which perform gradient descent while adding Gaussian noise to the gradients. The authors consider when f is the sum of loss functions of users in a database, and we want to output a minimizer of f with approximate differential privacy. They analyze the privacy loss and error of DPGD by viewing it as an instance of Langevin Dynamics, which samples from the distribution p with pdf proportional to e^{-f(x)}. The main result of the paper is a bound on the Renyi divergences between two DPGD runs on adjacent databases. The main qualitative improvement of this bound is that the dependence on the number of iterations of DPGD, K, is something like (1-e^{-K}) when the loss functions f are strongly convex and smooth. That is, the divergence bound increases with K, but the asymptotic dependence on K is O(1). In comparison, many past bounds have a small polynomial dependence on K, since they effectively bound the divergence between the full chain of iterates produced by DPGD, rather than the final iterate. In particular, if we took K to be sufficiently large, this would enable sampling from a distribution very close to p with approximate DP. The authors show that indeed, this gets loss that has optimal dependence on dimension, epsilon, and the number of users n.

summaries: This paper investigates the information leakage of noisy gradient descent (GD) algorithms for smooth and strongly convex loss functions. The authors analyze the dynamics of (Renyi) privacy loss during training (over K iterations) when the internal state of the training algorithm is not observable. This leads to an upper bound on the rate of privacy loss of the released model by way of the Renyi divergence between a pair of distributions over model parameters learned on neighboring datasets. The bound turns out to be much better than that obtained using composition-based approaches.

abstractText: What is the information leakage of an iterative randomized learning algorithm about its training data, when the internal state of the algorithm is private? How much is the contribution of each specific training epoch to the information leakage through the released model? We study this problem for noisy gradient descent algorithms, and model the dynamics of Rényi differential privacy loss throughout the training process. Our analysis traces a provably tight bound on the Rényi divergence between the pair of probability distributions over parameters of models trained on neighboring datasets. We prove that the privacy loss converges exponentially fast, for smooth and strongly convex loss functions, which is a significant improvement over composition theorems (which over-estimate the privacy loss by upper-bounding its total value over all intermediate gradient computations). For Lipschitz, smooth, and strongly convex loss functions, we prove optimal utility with a small gradient complexity for noisy gradient descent algorithms.

authors:
Martin Abadi
Andy Chu
Ian Goodfellow
H Brendan McMahan
Ilya Mironov
Kunal Talwar
Li Zhang

title: Deep learning with differential privacy

venue: In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security,

authors:
Dominique Bakry
Ivan Gentil
Michel Ledoux

title: Analysis and geometry of Markov diffusion operators, volume 348

venue: Springer Science & Business Media,

authors:
Raef Bassily
Adam Smith
Abhradeep Thakurta

title: Private empirical risk minimization: Efficient algorithms and tight error bounds

venue: In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science,

title: Understanding computational Bayesian statistics, volume 644

authors:
Nicholas Carlini
Florian Tramer
Eric Wallace
Matthew Jagielski
Ariel Herbert-Voss
Katherine Lee
Adam Roberts
Tom Brown
Dawn Song
Ulfar Erlingsson

title: Extracting training data from large language models

authors:
Kamalika Chaudhuri
Claire Monteleoni
Anand D Sarwate

venue: Journal of Machine Learning Research,

authors:
Cynthia Dwork
Aaron Roth

title: The algorithmic foundations of differential privacy

venue: Foundations and Trends® in Theoretical Computer Science,

authors:
Vitaly Feldman
Ilya Mironov
Kunal Talwar
Abhradeep Thakurta

title: Privacy amplification by iteration

venue: IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS),

authors:
Vitaly Feldman
Tomer Koren
Kunal Talwar

title: Private stochastic convex optimization: optimal rates in linear time

venue: In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing,

title: Die mittlere energie rotierender elektrischer dipole im strahlungsfeld

venue: Annalen der Physik,

authors:
Arun Ganesh
Kunal Talwar

title: Faster differentially private samplers via Rényi divergence analysis of discretized Langevin MCMC

title: Logarithmic sobolev inequalities

venue: American Journal of Mathematics,

authors:
Matthew Jagielski
Jonathan Ullman
Alina Oprea

title: Auditing differentially private machine learning: How private is private sgd? Advances in Neural Information

venue: Processing Systems,

authors:
Daniel Kifer
Adam Smith
Abhradeep Thakurta

title: Private convex empirical risk minimization and high-dimensional regression

venue: In Conference on Learning Theory,

title: The concentration of measure phenomenon

venue: Number 89. American Mathematical Soc.,

authors:
Kentaro Minami
HItomi Arai
Issei Sato
Hiroshi Nakagawa

title: Differential privacy without sensitivity

venue: In Advances in Neural Information Processing Systems,

title: Rényi differential privacy

venue: IEEE 30th Computer Security Foundations Symposium (CSF),

authors:
Milad Nasr
Reza Shokri
Amir Houmansadr

title: Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning

venue: IEEE symposium on security and privacy (SP),

authors:
Milad Nasr
Shuang Song
Abhradeep Thakurta
Nicolas Papernot
Nicholas Carlini

title: Adversary instantiation: Lower bounds for differentially private machine learning

venue: arXiv preprint arXiv:2101.04535,

authors:
Issei Sato
Hiroshi Nakagawa

title: Approximation analysis of stochastic gradient Langevin dynamics by using fokker-planck equation and ito process

authors:
Reza Shokri
Marco Stronati
Congzheng Song
Vitaly Shmatikov

title: Membership inference attacks against machine learning models

venue: IEEE Symposium on Security and Privacy (SP),

authors:
Santosh Vempala
Andre Wibisono

title: Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices

authors:
Di Wang
Minwei Ye
Jinhui Xu

title: Differentially private empirical risk minimization revisited: Faster and more general

venue: arXiv preprint arXiv:1802.05251,

authors:
Yu-Xiang Wang
Stephen Fienberg
Alex Smola

title: Privacy for free: Posterior sampling and stochastic gradient monte carlo

authors:
Jiaqi Zhang
Kai Zheng
Wenlong Mou
Liwei Wang

title: Efficient private erm for smooth objectives

venue: In Proceedings of the 26th International Joint Conference on Artificial Intelligence,

heading: 1 Introduction

text:
Machine learning models leak a significant amount of information about their training data, through their parameters and predictions [21, 18, 5]. Iterative randomized training algorithms can limit this information leakage and bound the differential privacy loss of the learning process [3, 1, 8, 9]. The strength of this certified defense is determined by an upper bound on the (Rényi) divergence between the probability distributions of model parameters learned on any pair of neighboring datasets.
The general method to compute the differential privacy bound for gradient perturbation-based learning algorithms is to view the process as a number of (identical) differential privacy mechanisms, and to compute the composition of their bounds. However, this over-estimates the privacy loss of the released model [13, 19], and results in a loose differential privacy bound. This is because composition bounds also accounts for the leakage of all intermediate gradient updates, even though only the final model parameters are observable to adversary. Feldman et al. [8, 9] address this issue for the privacy analysis of gradient computations over one single training epoch, for smooth and convex loss functions. However, in learning a model over multiple training epochs, such a guarantee is quantitatively similar to composition bounds of privacy amplification by sub-sampling [8]. The open challenge, that we tackle in this paper, is to provide an analysis that can tightly bound the privacy loss of the released model after K training epochs, for any K.
We present a novel analysis for privacy dynamics of noisy gradient descent with smooth and strongly convex loss functions. We construct a pair of continuous-time Langevin diffusion [20] processes that trace the probability distributions over the model parameters of noisy GD. Subsequently, we derive differential inequalities bounding the rate of privacy loss (worst case Rényi divergence between the coupled stochastic processes associated with neighboring datasets) throughout the training process.
*Equal contribution. Alphabetical Order.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
We then prove an exponentially-fast converging privacy bound for noisy GD: (simplified theorem) Under 1-strongly convex and β-smooth loss function `(θ;x) with total gradient sensitivity 1, the noisy GD Algorithm 1, with initial parameter vector θ0 ∼ ΠC(N (0, 2σ2Id)) and step size η < 1β ,
satisfies (α, ε)-Rényi DP with ε = O (
α σ2n2 (1− e
−ηK2 ) ) , where n is the size of the training set.
This guarantee shows that the privacy loss converges exponentially in the number of iterations K, instead of growing proportionally with K as in the composition-based analysis of the same algorithms. Our bound captures a strong privacy amplification due to the dynamics (and convergence) of differential privacy over the noisy gradient descent algorithm with private internal state.
We analyze the tightness of the bound, the utility of the randomized algorithm under the computed differential privacy bound, as well as its gradient complexity (number of required gradient computations). We prove the tightness guarantee for our bound by showing that there exist a loss function and neighboring datasets such that the divergence between corresponding model parameter distributions matches our privacy bound. For Lipschitz, smooth, and strongly convex loss functions, we prove that noisy GD achieves optimal utility under differential privacy with an error of order O( dn2ε2 ), with a small gradient complexity of order O(n log(n)). This improves over the prior utility results for noisy SGD algorithms [3]. Our analysis results in a significantly smaller gradient complexity by a factor of n/ log(n), and a slightly better utility by a factor of polylog(n).
We anticipate that our work will have a positive societal impact, by paving the way for building accurate and privacy preserving machine learning systems for sensitive personal data.

heading: 2 Preliminaries on differential privacy

text:
Let X be the data universe, and a dataset D contain n records from it: D = (x1,x2, · · · ,xn) ∈ Xn. We refer to a dataset pair D,D′ as neighboring if they differ in one data record. A measure ν is said to be absolutely continuous with respect to another measure ν′ on same space (denoted as ν ν′) if for all measurable set S, ν(S) = 0 whenever ν′(S) = 0.
Definition 2.1 ([17] Rényi differential privacy). Let α > 1. A randomized algorithm A : Xn → Rd satisfies (α, ε)-Rényi Differential Privacy (RDP), if for any two neighboring datasets D,D′ ∈ Xn, the α Rényi divergence Rα (A(D)‖A(D′)) ≤ ε. For a pair of measures ν, ν′ over the same space with ν ν′, Rα (ν‖ν′) is defined as
Rα (ν‖ν′) = 1
α− 1 logEα (ν‖ν′) , where Eα (ν‖ν′) =
∫ ( dν
dν′
)α dν′. (1)
We refer to Rα (A(D)‖A(D′)) also as the Rényi privacy loss of algorithm A on datasets D,D′. An RDP guarantee can be converted to (ε, δ)-DP guarantee [17, Proposition 5].
Definition 2.2 ([22] Rényi information). Let α > 1. For any two measures ν, ν′ over Rd with µ ν′ and corresponding probability density functions p, p′, if p(θ)p′(θ) is differentiable, the α-Rényi Information of ν with respect to ν′ is
Iα (ν‖ν′) = 4
α2 E θ∼p′ [∥∥∥∥∇ p(θ)α2p′(θ)α2 ∥∥∥∥2
2
] = E θ∼p′ [ p(θ)α−2 p′(θ)α−2 ∥∥∥∥∇ p(θ)p′(θ) ∥∥∥∥2
2
] . (2)
See the Appendix B for a comprehensive presentation of preliminaries.

heading: 3 Privacy analysis of noisy gradient descent

text:
Let D = (x1,x2, · · · ,xn) be a dataset of size n with records taken from a universe X . For a given machine learning algorithm, let `(θ;x) : X × Rd → R be a loss function of a parameter vector θ ∈ C on the data point x, where C is a closed convex set (can be Rd). A generic formulation of the optimization problem to learn the model parameters, is in the form of empirical risk minimization (ERM) with the following objective, where LD(θ) is the empirical loss
of the model, with parameter vector θ, on a dataset D.
θ∗ = arg min θ∈C
LD(θ), where LD(θ) = 1
n ∑ x∈D `(θ;x). (3)
Releasing this optimization output (i.e., θ∗) can leak information about the dataset D, hence violating data privacy. To mitigate this risk, there exist randomized algorithms to ensure that the (α-Rényi) privacy loss of the ERM algorithm is upper-bounded by ε, i.e., the algorithm satisfies (α, ε)-RDP.
Algorithm 1 ANoisy-GD: Noisy Gradient Descent
Input: Dataset D = (x1,x2, · · · ,xn), loss function `(θ;x), closed convex set C ⊆ Rd, learning rate η, noise variance σ2, initial parameter vector θ0.
1: for k = 0, 1, · · · ,K − 1 do 2: g(θk;D) = ∑n i=1∇`(θk;xi)
3: θk+1 = ΠC(θk − ηng(θk;D) + √
2ηN (0, σ2Id)) 4: Output θK
In this paper, our objective is to analyze privacy loss of Noisy Gradient Descent (Algorithm 1), which is a randomized ERM algorithm. Let θk, θ′k be the parameter vectors at the k’th iteration of ANoisy-GD on neighboring datasets D and D′, respectively. We denote by Θηk and Θ′ηk the corresponding random variables that model θk and θ′k. We abuse notation to also denote their probability distributions by Θηk and Θ′ηk. In this paper, our objective is to model and analyze the dynamics of differential privacy of this algorithm. More precisely, we focus on the following.
1. Compute an RDP bound (i.e., the worst case Rényi divergence Rα (ΘK‖Θ′K) between the output distributions of two neighboring datasets) for Algorithm 1, and analyze its tightness.
2. Compute the contribution of each iteration to the privacy loss. As we go from step k = 1 to K in Algorithm 1, we investigate how the algorithm’s privacy loss changes as it runs the k’th iteration (computed as Rα ( Θηk ∥∥∥Θ′ηk)−Rα (Θη(k−1)∥∥∥Θ′η(k−1))). In the end, we aim to provide a RDP bound that is tight, thus facilitating optimal utility [3]. We emphasize that our goal is to construct a theoretical framework for analyzing privacy loss of releasing the output θK of the algorithm, assuming private internal states (i.e., θ1, · · · , θK−1).

heading: 3.1 Tracing diffusion for Noisy GD

text:
To analyze the privacy loss of Noisy GD, which is a discrete-time stochastic process, we first interpolate each discrete update from θk to θk+1 with a piece-wise continuously differentiable diffusion process. Let D and D′ be a pair of arbitrarily chosen neighboring datasets. Given step-size η and initial parameter vector θ0 = θ′0, the respective k’th discrete updates in Algorithm 1 on neighboring datasets D and D′ are{
θk+1 = ΠC(θk − η∇LD(θk) + √ 2ησ2Zk), θ′k+1 = ΠC(θ ′ k − η∇LD(θ′k) + √ 2ησ2Zk), with Zk ∼ N (0, Id). (4)
These two discrete jumps can be interpolated with two stochastic processes Θt and Θ′t over time ηk ≤ t ≤ η(k + 1) respectively. At the start of each step, t = ηk, the random variables Θηk and Θ′ηk model the distribution of the θk and θ ′ k in the noisy GD processes respectively. During time ηk < t < η(k + 1), we model the respective gradient updates on D and D′ with the following stochastic processes.{
Θt = Θηk − η · U1(Θηk)− (t− ηk) · U2(Θηk) + √
2(t− ηk)σ2Zk Θ′t = Θ ′ ηk − η · U1(Θ′ηk) + (t− ηk) · U2(Θ′ηk) + √ 2(t− ηk)σ2Zk
(5)
where the vectors U1(θ) = 12 (∇LD(θ) +∇LD′(θ)) and U2(θ) = 1 2 (∇LD(θ)−∇LD′(θ)) represent the average and difference between gradients on neighboring datasets D and D′ respectively.
At the end of step, i.e. at t→ η(k + 1), we project Θt and Θ′t onto convex set C, and obtain
Θη(k+1) = ΠC
( lim
t→η(k+1)− Θt
) ,Θ′η(k+1) = ΠC ( lim
t→η(k+1)− Θ′t
) . (6)
By plugging (5) into (6), we compute that the projected random variable Θη(k+1) and Θ′η(k+1) have the same distributions as the parameters θk+1 and θ′k+1 at k + 1
th step of noisy GD respectively. Repeating the construction for k = 0, · · · ,K − 1, we define two piece-wise continuous diffusion processes {Θt}t≥0 and {Θ′t}t≥0 whose distributions at time t = ηk are consistent with θk and θ′k in the noisy GD processes (4) for any k ∈ {0, · · · ,K − 1}. Definition 3.1 (Coupled tracing diffusions). Let Θ0 = Θ′0 be two identically distributed random variables. We refer to the stochastic processes {Θt}t≥0 and {Θ′t}t≥0 that evolve along diffusion processes (5) in ηk < t < η(k + 1) and undergo projection steps (6) at the end of step t = η(k + 1), as coupled tracing diffusions for noisy GD on neighboring datasets D,D′.
The Rényi divergence Rα(ΘηK‖Θ′ηK) reflects the Rényi privacy loss of Algorithm 1 with K steps. Conditioned on observing θk and θ′k, the processes {Θt}ηk<t<η(k+1) and {Θ′t}ηk<t<η(k+1) in (5) are Langevin diffusions along vector fields −U2(θk) and U2(θ′k) respectively, for duration η. Therefore, conditioned on observing θk and θ′k, the diffusion processes in (5) have the following stochastic differential equations (SDEs) respectively.
dΘt = −U2(θk)dt+ √ 2σ2dWt, dΘ ′ t = U2(θ ′ k)dt+ √ 2σ2dWt, (7)
where dWt ∼ √ dtN (0, Id) describe the Wiener processes on Rd. Therefore, the conditional probability density functions pt|ηk(θ|θk) and p′t|ηk(θ|θ ′ k) follow the following Fokker-Planck equation. For brevity, we use pt|ηk(θ|θk) and p′t|ηk(θ|θ ′ k) to represent the conditional probability density function p(Θt = θ|Θηk = θk) and p(Θ′t = θ|Θ′ηk = θ′k) respectively. ∂pt|ηk(θ|θk) ∂t = ∇ · ( pt|ηk(θ|θk)U2(θk) ) + σ2∆pt|ηk(θ|θk) ∂p′t|ηk(θ|θ ′ k) ∂t = −∇ · ( p′t|ηk(θ|θ ′ k)U2(θ ′ k) ) + σ2∆pt|ηk(θ|θ′k) (8)
By taking expectations over probability density function pηk(θk) or p′ηk(θ ′ k) on both sides of (8), we obtain the partial differential equation that models the evolution of (unconditioned) probability density function pt(θ) and p′t(θ) in the coupled tracing diffusions. Lemma 1. For coupled tracing diffusion processes (5) in time ηk < t < η(k + 1), the equivalent Fokker-Planck equations are{
∂pt(θ) ∂t = ∇ · (pt(θ)Vt(θ)) + σ 2∆pt(θ) ∂p′t(θ) ∂t = ∇ · (p ′ t(θ)V ′ t (θ)) + σ 2∆p′t(θ), (9)
where Vt(θ) = −V ′t (θ) = E θk∼pηk|t [U2(θk)|θ] are time-dependent vector fields on Rd, and U2(θ) = 1 2 [∇LD(θ)−∇LD′(θ)] is the difference between gradients on neighboring datasets.
By this density evolution equation, we model the noisy gradient descent updates with coupled tracing diffusions. The tracing diffusion process is similar to Langevin diffusion. Therefore, we first study the privacy dynamics in coupled tracing (Langevin) diffusions.

heading: 3.2 Privacy erosion in tracing (Langevin) diffusion

text:
The Rényi divergence (privacy loss) Rα (Θt‖Θ′t) between coupled tracing diffusion processes increases over time, as the vector fields Vt, V ′t underlying two processes are different. We refer to this phenomenon as privacy erosion. This increase is determined by the amount of change in the probability density functions for coupled tracing diffusions, characterized by the Fokker-Planck equations (9) for diffusions under different vector fields.
Using equation (9), we compute a bound on the rate (partial derivative) of Rα (Θt‖Θ′t) over time in the following lemma, to model privacy erosion between two different diffusion processes. We refer to coupled diffusions as respective diffusion processes under different vector fields Vt and V ′t .
Lemma 2 (Rate of Rényi privacy loss). Let Vt and V ′t be two vector fields on Rd corresponding to a pair of arbitrarily chosen neighboring datasets D and D′ with max
θ∈Rd ‖Vt(θ)− V ′t (θ)‖2 ≤ Sv for all
t ≥ 0. Then, for corresponding coupled diffusions {Θt}t≥0 and {Θ′t}t≥0 under vector fields Vt and V ′t and noise variance σ
2, the Rényi privacy loss rate at any t ≥ 0 is upper bounded by ∂Rα (Θt‖Θ′t)
∂t ≤ 1 γ αS2v 4σ2 − (1− γ)σ2α Iα (Θt‖Θ ′ t) Eα (Θt‖Θ′t) . (10)
where γ > 0 is a tuning parameter that we can fix arbitrarily according to our need.
Although this lemma bounds the Rényi privacy loss rate, the term Iα (Θt‖Θ′t) depends on unknown distributions Θt,Θ′t, and is intractable to compute. Even with explicit expressions for distributions Θt,Θ ′ t, the calculation would involve integration in Rd which is computationally prohibitive for large d. Note that, however, the ratio Iα/Eα is always positive by definition. Therefore, the Rényi divergence (privacy loss) rate in (10) is bounded by its first component (a constant) given any fixed α. Theorem 1 (Linear Rényi divergence bound). Let Vt and V ′t be two vector fields on Rd, with max θ∈Rd ‖Vt(θ)− V ′t (θ)‖2 ≤ Sv for all t ≥ 0. Then, the coupled diffusions under vector fields Vt and V ′t with noise variance σ 2 for time T has α-Rényi divergence bounded by ε = αS 2 vT 4σ2 .
When the vector fields are Vt = −∇LD and V ′t = −∇LD′ , the coupled diffusions follow Langevin diffusion. By definition B.10 of total gradient sensitivity, max
θ∈Rd ‖∇LD(θ)−∇LD′(θ)‖2 ≤ Sg n . There-
fore, this naïve privacy analysis gives linear RDP guarantee for Langevin diffusion, which resembles the moment accountant analysis [1]. However, a tighter bound of Rényi privacy loss is possible with finer control of the ratio Iα (Θt‖Θ′t)/Eα (Θt‖Θ′t), which by definition depends on the likelihood ratio between Θt and Θ′t, thus is connected with Rényi privacy loss itself. When this ratio grows, the Rényi privacy loss rate decreases, thus slowing down privacy loss accumulation, and leading to tighter privacy bound.
Controlling Rényi privacy loss rate under isoperimetry We control the Iα/Eα term in lemma 2 by making an isoperimetric assumption known as log-Sobolev inequality [2], described as follows. Definition 3.2 ([12] Log-Sobolev Inequality (c-LSI)). Distribution of a random variable Θ on Rd satisfies logarithmic Sobolev inequality with parameter c > 0, i.e. it is c-LSI, if for all functions f in the function set FΘ = {f : Rd → R|∇f is continuous, and E(f(Θ)2) <∞}, we have
E[f(Θ)2 log f(Θ)2]− E[f(Θ)2] logE[f(Θ)2] ≤ 2 c E[‖∇f(Θ)‖22]. (11)
LSI was introduced by Gross [12] as a necessary and sufficient condition for rapid convergence of a diffusion processes. Recently, Vempala and Wibisono [22] showed that this isoperimetry condition is sufficient for rapid convergence of Langevin diffusion in Rényi divergence. Under LSI, they provide the following useful lower bound on Iα/Eα for an arbitrary pair of distributions. Lemma 3 ([22] c-LSI in terms of Rényi Divergence). Suppose Θt,Θ′t ∈ Rd are random variables such that the density ratio between distributions of Θt and Θ′t lies in FΘ′t . Then for any α ≥ 1,
Rα (Θt‖Θ′t) + α(α− 1) ∂Rα (Θt‖Θ′t) ∂α ≤ α 2 2c Iα (Θt‖Θ′t) Eα (Θt‖Θ′t) , (12)
if and only if distribution of Θ′t satisfies c-LSI.
Note that ∂Rα(Θt‖Θ′t)
∂α is always positive, as Rα (Θt‖Θ ′ t) monotonically increases with α > 1 [17].
This lemma shows that Iα (Θt‖Θ′t)/Eα (Θt‖Θ′t) grows monotonically with the Rényi privacy loss Rα (Θt‖Θ′t). By Lemma 2, this implies a throttling privacy loss rate as privacy loss accumulates.Combining Lemma 2 and Lemma 3, we therefore model the dynamics for Rényi privacy loss under c-LSI with the following PDE, which describes the relation between privacy loss, its changes over time, and its change over Rényi parameter α. For brevity, let R(α, t) represent Rα (Θt‖Θ′t).
∂R(α, t) ∂t ≤ 1 γ αS2v 4σ2
− 2(1− γ)σ2c [ R(α, t)
α + (α− 1)∂R(α, t) ∂α
] (13)
The initial privacy loss R(α, 0) = 0, as Θ0 = Θ′0. The solution for this PDE increases with time t ≥ 0, and models the erosion of Rényi privacy loss in coupled tracing diffusions Θt and Θ′t.

heading: 3.3 Privacy guarantee for Noisy GD

text:
We now use the privacy dynamics (13) of coupled tracing diffusions to analyze the privacy dynamics for noisy GD. We first bound the difference between the underlying vector fields Vt and V ′t for coupled tracing diffusions for noisy GD on neighboring datasets D and D′. Lemma 4. Let `(θ;x) be a loss function on closed convex set C, with a finite total gradient sensitivity Sg . Let {Θt}t≥0 and {Θ′t}t≥0 be the coupled tracing diffusions for noisy GD on neighboring datasets D,D′ ∈ Xn, under loss `(θ;x) and noise variance σ2. Then the difference between underlying vector fields Vt and V ′t for coupled tracing diffusions is bounded by
max θ∈Rd ‖Vt(θ)− V ′t (θ)‖2 ≤ Sg n , (14)
where Vt(θ) and V ′t (θ) are time-dependent vector fields on Rd, defined in Lemma 1.
We then substitute Sv in PDE (13) with Sg/n, and compute the following PDE modelling Rényi privacy loss dynamics of tracing diffusion at ηk < t < η(k + 1), under c-LSI condition.
∂R(α, t) ∂t ≤ 1 γ αS2g 4σ2n2
− 2(1− γ)σ2c [ R(α, t)
α + (α− 1)∂R(α, t) ∂α
] (15)
We solve this PDE under γ = 12 for each time piece, and combine multiple pieces by seeing projection as privacy-preserving post-processing step. We derive the RDP guarantee for the Noisy GD algorithm. Theorem 2 (RDP for noisy GD under c-LSI). Let {Θt}t≥0 and {Θ′t}t≥0 be the tracing diffusion for ANoisy-GD on neighboring datasets D and D′, under noise variance σ2 and loss function `(θ;x). Let `(θ;x) be a loss function on closed convex set C ⊆ Rd, with a finite total gradient sensitivity Sg. If for any neighboring datasets D and D′, the corresponding coupled tracing diffusions Θt and Θ′t satisfy c-LSI throughout 0 ≤ t ≤ ηK, then ANoisy-GD satisfies (α, ε) Rényi Differential Privacy for
ε = αS2g
2cσ4n2 (1− e−σ 2cηK). (16)
This theorem offers a strong converging privacy guarantee, on the condition that c-LSI is satisfied throughout the Noisy GD process. We then analyze the LSI constant c for given Noisy GD process.
Isoperimetry constants for noisy GD When the loss function is strongly convex and smooth, we prove that tracing diffusion of noisy GD satisfies LSI. This is because the gradient descent update is Lipschitz under smooth loss, and the Gaussian noise preserves LSI, as discussed in Appendix D.3. Lemma 5 (LSI for noisy GD). If loss function `(θ;x) is λ-strongly convex and β-smooth over a closed convex set C, the step-size is η < 1β , and initial distribution is Θ0 ∼ ΠC(N (0, 2σ2
λ Id)), then the coupled tracing diffusion processes {Θt}t≥0 and {Θ′t}t≥0 for noisy GD on any neighboring datasets D and D′ satisfy c-LSI for any t ≥ 0 with c = λ2σ2 .
Using the LSI constant proved by this lemma, we immediately prove the following RDP bound for noisy GD on Lipschitz smooth strongly convex loss, as a corollary of Theorem 2. Corollary 1 (Privacy Guarantee for noisy GD). Let `(θ;x) be a λ-strongly convex, and β-smooth loss function on closed convex set C, with a finite total gradient sensitivity Sg , then the noisy gradient descent algorithm (Algorithm 1) with start parameter θ0 ∼ ΠC(N (0, 2σ 2 λ Id)), and step-size η < 1 β , satisfies (α, ε) Rényi Differential Privacy with
ε = αS2g λσ2n2 (1− e−ληK/2).
This privacy bound has quadratic dependence on the total gradient sensitivity Sg, which is upper bounded by Sg ≤ 2L for L-Lipschitz loss functions. The smoothness condition β restricts the step-size and ensures Lipschitz gradient mapping, thus facilitating LSI by Lemma 5. Figure 1 demonstrates how this RDP guarantee for noisy GD converges with the number of iterations K. Through y-axis, we show the ε guaranteed for noisy GD under various Rényi divergence orders c and strong convexity constant λ. The RDP order α linearly scales the asymptotic guarantee, but does not affect the convergence rate of RDP guarantee. However, the strong convexity parameter λ positively affects the asymptotic guarantee as well as the convergence rate; the larger the strong convexity parameter λ is, the stronger the asymptotic RDP guarantee and the faster the convergence.
analysis: ε = αS2g λσ2n2 ·
(
1− e−ληK/2
)
; and Baseline composition-based analysis (derived by moment accountant [1] with details in Appendix E): ε = αS2g
4n2σ2 · ηK.

heading: 4 Tightness analysis: a lower bound on privacy loss of noisy GD

text:
Differential privacy guarantees reflect a bound on privacy loss on an algorithm; thus, it is very crucial to also have an analysis of their tightness (i.e., how close they are to the exact privacy loss). We prove that our RDP guarantee in Theorem 2 is tight. To this end, we construct an instance of the ERM optimization problem, for which we show that the Rényi privacy loss of the noisy GD algorithm grows at an order matching our guarantee in Theorem 2.
It is very challenging to lower bound the the exact Rényi privacy loss Rα ( ΘKη ∥∥Θ′Kη) in general. This might require having an explicit expression for the probability distribution over the last-iterate parameters θk. Computing a close-form expression is, however, feasible when the loss gradients are linear. This is due to the fact that, after a sequence of linear transformations and Gaussian noise additions, the parameters follow a Gaussian distribution. Therefore, we construct such an ERM objective, compute the exact privacy loss, and prove the following lower bound. Theorem 3 (Lower bound on RDP of ANoisy-GD). There exist two neighboring datasets D,D′ ∈ Xn, a start parameter θ0, and a smooth loss function `(θ;x) on unconstrained convex set C = Rd, with a finite total gradient sensitivity Sg, such that for any step-size η < 1, noise variance σ2 > 0, and iteration K ∈ N, the privacy loss of ANoisy-GD on D,D′ is lower-bounded by
Rα ( ΘηK ∥∥Θ′ηK) ≥ αS2g4σ2n2 (1− e−ηK) . (17) We prove this lower bound using the `2-squared norm loss as ERM objective: minθ∈Rd ∑n i=1 ‖θ−xi‖22 n . We assume bounded data domain s.t. the gradient has finite sensitivity. With start parameter θ0 = 0d, the kth step parameter θk is distributed as Gaussian with mean µk = ηx̄ ∑k−1 i=0 (1− η)i and variance σ2k = 2ησ2 n2 ∑k−1 i=0 (1− η)2i in each dimension, where x̄ = ∑n i=1 xi/n is the empirical dataset mean. We explicitly compute the privacy loss at any step K, which is lower bounded by αS2g
4σ2n2 (1− e −ηK).
Meanwhile, Corollary 1 gives our RDP upper bound = αS2g σ2n2
( 1− e−ηK ) for this same ERM
objective. This upper bound matches the lower bound at every step K, up to a small constant of 4.
Moreover, Theorem 2 facilitates a smaller RDP upper bound than Corollary 1 by bounding the LSI constant throughout Noisy GD exactly. For squared-norm loss function, Theorem 2 gives the
following tighter RDP upper-bound for Noisy GD, because all intermediate Gaussian distributions satisfy c-LSI with c = 2−η2σ2 , as proved in Appendix E. Corollary 2 (RDP guarantee of ANoisy-GD on `2-norm squared loss). For any two neighboring datasets D,D′ ∈ Xn, start parameter θ0, step-size η, noise variance σ2, and K ∈ N, if the loss function is `2-norm squared loss `(θ;x) = 12 ‖θ − x‖ 2 2 on unconstrained convex set C = Rd, with a finite total gradient sensitivity Sg , the privacy loss of ANoisy-GD on D,D′ is upper-bounded by
Rα ( ΘηK ∥∥Θ′ηK) ≤ αS2g(2− η)σ2n2 (1− e− 2−η2 ηK). (18) This RDP guarantee converges fast to O(
αS2g σ2n2 ), which matches the lower bound at every step K,
up to a constant of 42−η ≈ 2. This immediately shows tightness of our converging RDP guarantee throughout the training process, for a converging noisy GD algorithm. A different approach is to completely ignore the dynamics of differential privacy, and instead analyze privacy only at the convergence time (or when the algorithm is near convergence). Wang et al. [25], Minami et al. [16] show that sampling from the Gibbs posterior distribution ν(θ) ∝ e−LD(θ)/σ2 for bounded LD satisfies differential privacy. However, sampling exactly from the Gibbs distribution is difficult [4]. Thus, Minami et al. [16], Ganesh and Talwar [11] extend the DP guarantees of Gibbs posterior distribution to gradient-descent based samplers such as Unadjusted Langevin Algorithm (ULA) that can sample from distributions arbitrarily close to Gibbs distribution after a sufficient number of iterationsK with extremely small step-size η. Minami et al. [16] compute the distance to convergence in total variation, and Ganesh and Talwar [11] improve the prior bound by measuring the distance in Rényi divergence (building on the rapid convergence results of Vempala and Wibisono [22]). The latter results in a better gradient complexity Ω(nd), which however still grows with model dimension d. In comparison, our DP guarantees are unaffected by parameter dimension d, which in practice can be much larger than the dataset size n.
In contrast, composition-based privacy bound grows linearly as training proceeds, as shown in Figure 1. When the number of iterations K is small, however, composition-based bound grows at the same rate with the lower bound, as discussed in Appendix E. Therefore, to conclude whether our RDP guarantee is superior to composition-based bound, we need to understand the number of iterations noisy GD needs, to achieve optimal utility. We discuss this in the following section.

heading: 5 Utility analysis for noisy gradient descent

text:
The randomness, required for satisfying differential privacy, can adversely affect the utility of the trained model. The standard way to measure the utility of a randomized ERM algorithm (for example, ANoisy-GD) is to quantify its worst case excess empirical risk, which is defined as
max D∈Xn
E[LD(θ)− LD(θ∗)], (19)
where θ is the output of the randomized algorithm ANoisy-GD on D, θ∗ is the solution to the standard (no privacy) ERM (3), and the expectation is computed over the randomness of the algorithm.
We provide the optimal excess empirical risk (utility) of noisy GD algorithm under (α, ε′)-RDP constraint. The notion of optimality for utility is defined as the smallest upper-bound for excess empirical risk that can be guaranteed under (α, ε′)-RDP constraint by tuning the algorithm’s hyperparameters (such as the noise variance σ2 and the number of iterations K). We focus here on smooth and strongly convex loss functions with a finite total gradient sensitivity. Lemma 6 (Excess empirical risk for smooth and strongly convex loss). For L-Lipschitz, λ-strongly convex and β-smooth loss function `(θ;x) over a closed convex set C ⊆ Rd, step-size η ≤ λ2β2 , and start parameter θ0 ∼ ΠC(N (0, 2σ 2 λ Id)), the excess empirical risk of Algorithm 1 is bounded by
E[LD(θK)− LD(θ∗)] ≤ 2βL2
λ2 e−ληK +
2βdσ2
λ , (20)
where θ∗ is the minimizer of LD(θ) in the relative interior of convex set C, and d is the dimension of parameter.
This lemma shows decreasing excess empirical risk for noisy GD algorithm under Lipschitz smooth strongly convex loss function as the number of iterations K increases. The utility is determined by K and the noise variance σ2, which are constrained under (α, ε′)-RDP. Using our tight RDP guarantee in Corollary 1, we prove optimal utility for noisy GD.
Theorem 4 (Upper bound for (α, ε′)-RDP and (ε, δ)-DP Noisy GD). For Lipschitz smooth strongly convex loss function `(θ;x) on a bounded closed convex set C ⊆ Rd, and dataset D ∈ Xn of size n, if the step-size η = λ2β2 and the initial parameter θ0 ∼ ΠC(N (0, 2σ2
λ Id)), then the noisy GD Algorithm 1 is (α, ε′)-Rényi differentially private, where α > 1 and ε′ > 0, and satisfies
E[LD(θK∗)− LD(θ∗)] = O( αβdL2
ε′λ2n2 ), (21)
by setting noise variance σ2 = 4αL 2 λε′n2 , and number of updates K ∗ = 2β
2 λ2 log( n2ε′ αd ).
Equivalently, for ε ≤ 2 log(1/δ) and δ > 0, Algorithm 1 is (ε, δ)-differentially private, and satisfies
E[LD(θK∗)− LD(θ∗)] = O( βdL2 log(1/δ)
2λ2n2 ), (22)
by setting noise variance σ2 = 8L 2(ε+2 log(1/δ)) λε2n2 , and number of updates K ∗ = 2β 2 λ2 log( n2ε2 4 log(1/δ)d ).
Our algorithm achieves this utility guarantee with O(β 2 λ2n log ( ε2n2 d ) ) gradient computations of ∇`(θ;x), which is faster than noisy SGD algorithm [3] with a factor of n. However, we additionally assume smoothness for the loss function. Our gradient complexity also matches that of other efficient gradient perturbation and output perturbation methods [23, 26], as shown in Table 1.
This utility matches the following theoretical lower bound in Bassily et al. [3] for the best attainable utility of ( , δ)-differentially private algorithms on Lipschitz smooth strongly convex loss functions.
Theorem 5 ([3] Lower bound for (ε, δ)-DP algorithms). Let n, d ∈ N, ε > 0, and δ = o( 1n ). For every (ε, δ)-differentially private algorithm A (whose output is denoted by θpriv), there is a dataset D ∈ Xn such that, with probability at least 1/3 (over the algorithm random coins), we must have
LD(θpriv)− LD(θ∗) = Ω ( min { 1, d
ε2n2
}) , (23)
where θ∗ minimizes a constructed 1-Lipschitz, 1-strongly convex objective LD(θ) over convex set C.
Our utility matches this lower bound upto the constant factor log(1/δ), when assuming βλ2 = O(1). This improves upon the previous gradient perturbation methods [3, 24] by a factor of log(n), and matches the utility of previously know optimal ERM algorithm for Lipschitz smooth strongly convex loss functions, such as objective perturbation [6, 14] and output perturbation [26].
Utility gain from tight privacy guarantee As shown in Table 1, our utility guarantee for noisy GD is logarithmically better than that for noisy SGD in Bassily et al. [3], although the two algorithms are extremely similar. This is because we use our tight RDP guarantee, while Bassily et al. [3] use a composition-based privacy bound. More specifically, noisy SGD needs n2 iterations to achieve the optimal utility, as shown in Table 1. This number of iterations is large enough for the compositionbased privacy bound to grow above our RDP guarantee, thus leaving room for improving privacy utility trade-off, as we further discuss in Appendix F. This concludes that our tight privacy guarantee enables providing a superior privacy-utility trade-off, for Lipschitz, strongly convex, and smooth loss functions.
Our algorithm also has significantly smaller gradient complexity than noisy SGD [3], for strongly convex loss functions, by a factor of n/log n. We use a (moderately large) constant step-size, thus achieving fast convergence to optimal utility. However, noisy SGD [3] uses a decreasing step-size, thus requiring more iterations to reach optimal utility.

heading: 6 Conclusions

text:
We have developed a novel theoretical framework for analyzing the dynamics of privacy loss for noisy gradient descent algorithms. Our theoretical results show that by hiding the internal state of the training algorithm (over many iterations over the whole data), we can tightly analyze the rate of information leakage throughout training, and derive a bound that is significantly tighter than that of composition-based approaches.
Future Work. Our main result is a tight privacy guarantee for Noisy GD on smooth and strongly convex loss functions. The assumptions are very similar to that of the prior work on privacy amplification by iteration [8], and have obvious advantages in enabling the tightness and utility analysis. However, the remaining open challenge is to extend this analysis to non-smooth and non-convex loss functions, and stochastic gradient updates, which are used notably in deep learning.
Acknowledgements and Funding
The authors would like to thank Joe P. Chen, Hedong Zhang and anonymous reviewers for helpful discussions on the earlier versions of this paper.
This research is supported in part by Intel Faculty Award (within the www.private-ai.org center), Huawei, Google Faculty Award, VMWare Early Career Faculty Award, and the National Research Foundation, Singapore under its Strategic Capability Research Centres Funding Initiative (any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not reflect the views of National Research Foundation, Singapore).

title: Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent


summaries: This paper presents a method to improve QP solving speed via reinforcement learning.  A regularization parameter used in OSQP solver is being updated via a RL policy. The approach is shown to improve OSQP performance on various benchmarks.

summaries: The paper introduces a RL formulation and training pipeline to accelerate quadratic programming. The main idea is based on learning the multi-dimensional multiplier for ADMM. The paper shows some empirical performance gains over a number of setups.  ====== updated post rebuttal =====  Thanks the reviewers for the replies. Aggregating all information so far, I think the major weakness of the paper is the following:  It does not provide a clear reason why formulating the whole problem as a multi-agent Markov game is useful (I am not fully convinced by the rebuttal). The algorithm I can see is still essentially a single agent policy but with a specialized architecture.  Now that after exchanging messages with the author a few times, I have understood how the detailed architecture works, and I am convinced about my point above. I would suggest that the authors present their architecture (such as mapping from R^6 to R^1) in a clear way, so as to make the architecture easier to understand. Also, I would like to see less stress on the Markov games, because it does not provide much gains -- once again, I'd like to frame it as a form of specialized architecture for single agent problem.  The paper is overall an application of RL to optimization problem. The gains are ok though the idea-wise contributions are not very novel (no extremely novel architecture or formulation).  Still, overall I think the paper provides a solid contribution and I am willing to raise my eval to 6.

summaries: The authors use RL to tune the step size policy of OSQP, an ADMM-based solver for quadratic programming problems. They develop policies for both a scalar and a diagonal step size. Numerical tests are performed on the suite of benchmark instances used by the OSQP developers and external benchmark sets (QPLIB, Netlib, and Maros-Meszaros). The results show clear gains within specific problem classes and some evidence of generalization across problem classes.

summaries: In this paper, the authors proposed a novel method to accelerate the QP  (quadratic programming) solving process using reinforcement learning. In their formulation, the state of the problem is the internal variables of the QP solver (in this case, OSQP's internal variables), the action space consists of the ADMM step size vector rho. Since the vector/matrix sizes of the QP can change between different problems, the authors used a multi-agent single-policy formulation, so each agent only observes the internal states that are relevant for a single coefficient in the step vector rho. The authors demonstrated that after training, their RLQP can converge faster for different classes of problems in the benchmark suite, especially if the problem is cold-started.

abstractText: First-order methods for quadratic optimization such as OSQP are widely used for large-scale machine learning and embedded optimal control, where many related problems must be rapidly solved. These methods face two persistent challenges: manual hyperparameter tuning and convergence time to high-accuracy solutions. To address these, we explore how Reinforcement Learning (RL) can learn a policy to tune parameters to accelerate convergence. In experiments with well-known QP benchmarks we find that our RL policy, RLQP, significantly outperforms state-ofthe-art QP solvers by up to 3x. RLQP generalizes surprisingly well to previously unseen problems with varying dimension and structure from different applications, including the QPLIB, Netlib LP and Maros-Mészáros problems. Code, models, and videos are available at https://berkeleyautomation.github.io/rlqp/.

authors:
Maria-Florina Balcan
Travis Dick
Tuomas Sandholm
Ellen Vitercik

title: Learning to branch

venue: In International conference on machine learning,

authors:
Andrew G Barto
Sridhar Mahadevan

title: Recent advances in hierarchical reinforcement learning

venue: Discrete event dynamic systems,

authors:
Peter W Battaglia
Jessica B Hamrick
Victor Bapst
Alvaro Sanchez-Gonzalez
Vinicius Zambaldi
Mateusz Malinowski
Andrea Tacchetti
David Raposo
Adam Santoro
Ryan Faulkner

title: Relational inductive biases, deep learning, and graph networks

venue: arXiv preprint arXiv:1806.01261,

authors:
Yoshua Bengio
Andrea Lodi
Antoine Prouvost

title: Machine learning for combinatorial optimization: a methodological tour d’horizon

venue: European Journal of Operational Research,

authors:
Dimitris Bertsimas
Bartolomeo Stellato

title: The voice of optimization

venue: Machine Learning,

authors:
Stephen Boyd
Neal Parikh
Eric Chu

title: Distributed optimization and statistical learning via the alternating direction method of multipliers

venue: Now Publishers Inc,

authors:
Xinyun Chen
Yuandong Tian

title: Learning to perform local rewriting for combinatorial optimization

venue: In Conference on Neural Information Processing Systems (NeurIPS),

authors:
Andrew R Conn
Nicholas IM Gould
Philippe L Toint

title: Trust region methods

authors:
Hanjun Dai
Elias B Khalil
Yuyu Zhang
Bistra Dilkina
Le Song

title: Learning combinatorial optimization algorithms over graphs

authors:
Thomas Elsken
Jan Hendrik Metzen
Frank Hutter

title: Neural architecture search: A survey

venue: J. Mach. Learn. Res.,

authors:
Lasse Espeholt
Hubert Soyer
Remi Munos
Karen Simonyan
Volodymir Mnih
Tom Ward
Yotam Doron
Vlad Firoiu
Tim Harley
Iain Dunning
Shane Legg
Koray Kavukcuoglu

title: IMPALA: Scalable distributed deep-RL with importance weighted actor-learner architectures, 2018

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

venue: In International Conference on Machine Learning,

authors:
Scott Fujimoto
Herke Hoof
David Meger

title: Addressing function approximation error in actor-critic methods

title: QPLIB: A library of quadratic programming instances

venue: Mathematical Programming Computation,

authors:
Daniel Gabay
Bertrand Mercier

title: A dual algorithm for the solution of nonlinear variational problems via finite element approximation

venue: Computers & mathematics with applications,

title: Electronic mail distribution of linear programming test problems

authors:
P. Giselsson
S. Boyd

title: Linear convergence and metric selection for douglas-rachford splitting and ADMM

venue: IEEE Transactions on Automatic Control,

authors:
Roland Glowinski
A Marroco

title: Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de dirichlet non linéaires

venue: ESAIM: Mathematical Modelling and Numerical Analysis-Modélisation Mathématique et Analyse Numérique,

authors:
Nicholas Gould
Jennifer Scott

title: A note on performance profiles for benchmarking software

venue: ACM Transactions on Mathematical Software (TOMS),

authors:
Tuomas Haarnoja
Aurick Zhou
Pieter Abbeel
Sergey Levine

title: Soft actor-critic: Offpolicy maximum entropy deep reinforcement learning with a stochastic actor

authors:
B.S. He
H. Yang
S.L. Wang

title: Alternating Direction Method with Self-Adaptive Penalty Parameters for Monotone Variational Inequalities

venue: Journal of Optimization Theory and Applications,

authors:
Wenlong Huang
Igor Mordatch
Deepak Pathak

title: One policy to control them all: Shared modular policies for agent-agnostic control

authors:
Jeffrey Ichnowski
Yahav Avigal
Vishal Satish
Ken Goldberg

title: Deep learning can accelerate grasp-optimized motion planning

venue: Science Robotics,

authors:
Jeffrey Ichnowski
Michael Danielczuk
Jingyi Xu
Vishal Satish
Ken Goldberg

title: GOMP: Grasp-optimized motion planning for bin picking

venue: IEEE International Conference on Robotics and Automation (ICRA)

authors:
Paras Jain
Ajay Jain
Aniruddha Nrusimha
Amir Gholami
Pieter Abbeel
Joseph Gonzalez
Kurt Keutzer
Ion Stoica

title: Checkmate: Breaking the memory wall with optimal tensor rematerialization

venue: In Proceedings of Machine Learning and Systems

authors:
Elias Khalil
Pierre Le Bodic
Le Song
George Nemhauser
Bistra Dilkina

title: Learning to branch in mixed integer programming

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
Ke Li
Jitendra Malik

title: Learning to optimize

authors:
Timothy P Lillicrap
Jonathan J Hunt
Alexander Pritzel
Nicolas Heess
Tom Erez
Yuval Tassa
David Silver
Daan Wierstra

title: Continuous control with deep reinforcement learning

venue: arXiv preprint arXiv:1509.02971,

title: Markov games as a framework for multi-agent reinforcement learning

venue: In Machine learning proceedings

authors:
Ryan Lowe
Yi Wu
Aviv Tamar
Jean Harb
Pieter Abbeel
Igor Mordatch

title: Multi-agent actorcritic for mixed cooperative-competitive environments

authors:
Istvan Maros
Csaba Mészáros

title: A repository of convex quadratic programming problems

venue: Optimization Methods and Software,

authors:
Jacob Mattingley
Stephen Boyd

title: CVXGEN: A code generator for embedded convex optimization

venue: Optimization and Engineering,

authors:
Luke Metz
Niru Maheswaranathan
Jeremy Nixon
Daniel Freeman
Jascha Sohl-Dickstein

title: Understanding and correcting pathologies in the training of learned optimizers

authors:
Yurii Nesterov
Arkadii Nemirovskii

title: Interior-point polynomial algorithms in convex programming

authors:
Alex Nichol
Joshua Achiam
John Schulman

title: On first-order meta-learning algorithms

venue: arXiv preprint arXiv:1803.02999,

authors:
Franco Scarselli
Marco Gori
Ah Chung Tsoi
Markus Hagenbuchner
Gabriele Monfardini

title: The graph neural network model

venue: IEEE transactions on neural networks,

authors:
John Schulman
Jonathan Ho
Alex X Lee
Ibrahim Awwal
Henry Bradlow
Pieter Abbeel

title: Finding locally optimal, collision-free trajectories with sequential convex optimization

venue: In Robotics: science and systems,

authors:
John Schulman
Filip Wolski
Prafulla Dhariwal
Alec Radford
Oleg Klimov

title: Proximal policy optimization algorithms

venue: arXiv preprint arXiv:1707.06347,

authors:
David Silver
Guy Lever
Nicolas Heess
Thomas Degris
Daan Wierstra
Martin Riedmiller

title: Deterministic policy gradient algorithms

authors:
B. Stellato
G. Banjac
P. Goulart
A. Bemporad
S. Boyd

title: OSQP: an operator splitting solver for quadratic programs

authors:
Richard S Sutton
David A McAllester
Satinder P Singh
Yishay Mansour

title: Policy gradient methods for reinforcement learning with function approximation

venue: In Advances in neural information processing systems,

authors:
Kaixuan Wei
Angelica Aviles-Rivero
Jingwei Liang
Ying Fu
Carola-Bibiane Schönlieb
Hua Huang

title: Tuning-free plug-and-play proximal algorithm for inverse imaging problems

title: The simplex method for quadratic programming

venue: Econometrica: Journal of the Econometric Society,

heading: 1 Introduction

text:
Solving quadratic programs (QPs) efficiently is critical to applications in finance, robotic control and operations research. While state-of-the-art interior-point methods scale poorly with problem dimensions, first-order methods for solving QPs typically require thousands of iterations. Moreover, real-time control applications have tight latency constraints for solvers [33]. Therefore, it is important to develop efficient heuristics to solve QPs in fewer iterations.
The Alternating Direction Method of Multipliers (ADMM) [6, 15, 18] is an efficient first-order optimization algorithm, and is the basis for the widely used and state-of-the art Operator-Splitting QP (OSQP) solver [44]. ADMM performs a linear solve on a matrix based on the optimality conditions of the QP to generate a step direction, and then projects the step onto the constraint bounds.
While state-of-the-art, the ADMM algorithm has numerous hyperparameters that must be tuned with heuristics to regularize and control optimization. Most importantly, the step size parameter ρ has considerable impact on the convergence rate. However, is still unclear how to select ρ before attempting the QP solution. While some theoretical works compute the optimal ρ [17], they rely on solving semidefinite optimization problems which are much harder than solving the QP itself. Alternatively, some heuristics introduce “feedback” by adapting ρ throughout optimization in order to balance primal and dual residuals [44, 6, 22].
We propose RLQP (see Fig. 1), an accelerated QP solver based on OSQP that uses reinforcement learning (RL) to adapt the internal parameters of the ADMM algorithm between iterations to minimize solve times. An RL algorithm learns a policy πθ : S → A, parameterized by θ (e.g., the weights of a neural network), that maps states in a set S to actions in setA such that the selected action maximizes the accumulated reward r. To train the policy for RLQP, we define S to be the internal state of the
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
QP solver (e.g., the constraint bounds, the primal and dual estimates), A to be the adaptation to the internal parameter (ρ) vector, and r to minimize the number of ADMM iterations taken.
RLQP’s policy can be trained either jointly across general classes of QPs or with respect to a specific class. The general version of RLQP is trained once on a broad class of QPs and can be used out-ofthe-box on new problems. The specialized version of RLQP is trained on a specific class of problems that the solver will repeatedly encounter. While this requires additional setup and training time, it is useful when QPs will be repeatedly solved in application (e.g., in a 100 Hz control loop).
In experiments, we train RLQP on a set of randomized QPs, and compare convergence rates of RLQP to non-adaptive and heuristic adaptive policies. To compare generalization and specialization, we investigate RLQP’s performance in the settings where 1) the train and test sets of QPs come from the same class of problems, 2) the train set contains problems from a superset of classes contained in the test set, 3) the train set contains a subset, and 4) when the train and test sets are from distinct classes. In the results section we show that RLQP outperforms OSQP by up to 3x.
The contributions of this paper are: • Two RL formulations to train policies that provide coarse (scalar) and fine (vector) grain updates
to the internal parameters of a QP solver for faster convergence times • Policies trained jointly across QP problem classes or to specialize to specific classes • Experimental results showing that RLQP reduces convergence times by up to 3x and generalizes
to different problem classes and outperform existing methods

heading: 2 Related Work

text:
This work touches a number of related research areas, including convex optimization, ML-accelerated optimization, learning in 1st-order methods and RL. We summarize related work in Table 1.
Convex optimization Many researchers have proposed algorithms for quadratic programs, which generally fall into three classes: active set [47], interior point [37], and first-order methods. Of the active set and interior point solvers, perhaps the most well-known are Gurobi [20] and MOSEK [36]. Active-set solvers operate by iteratively adapting an active set of constraints based on the cost function gradient and dual variables [39]. Interior-point solvers iteratively introduce and vary barrier functions to represent constraints and solve unconstrained convex problems. We instead base this work on a first-order method solver, OSQP [44]. One of the advantages of OSQP over interior points solvers, is that it can readily be warm started from a near-by solution, as is common in many applications such as solving a sequential quadratic program [41] and solving QPs for model-predictive control.
ML-accelerated combinatorial optimization Accelerating combinatorial optimization problems with deep learning has been explored with wide application [4, 5], including branch-and-bound for
mixed-integer linear programming [1, 27], graph algorithms [9] and boolean satisfiability problems (SAT) [7]. Many combinatorial optimization problems have exponential search spaces and are NP-hard in a general setting. However, learning-augmented combinatorial algorithms utilize very different methods to RLQP as combinatorial problems have discrete search spaces.
Learning in first-order methods Accelerating first-order methods with machine learning has gained considerable recent interest. Li and Malik [28] demonstrate a learned optimization algorithm outperforms common first-order methods for several convex problems and a small non-convex problem. Metz et al. [34] show a learned policy outperforms first-order methods when optimizing neural networks, but finds that directly learning parameter update values can be sensitive to exploding gradient problems. We avoid this instability during optimization by learning a policy to adapt parameters of the ADMM algorithm. Wei et al. [46] recently proposed an RL agent to tune parameters for an ADMM-based inverse imaging solver.
Reinforcement Learning Overview Reinforcement learning (RL) algorithms include both onpolicy algorithms, such as Proximal Policy Optimization [42], REINFORCE [45], and IMPALA [11], and off-policy algorithms, such as DQN [35] and Soft Actor Critic [21]. RLQP extends the offpolicy Twin-Delayed DDPG (TD3) [13], an actor-critic framework with an exploration policy for continuous action spaces that extends Deep Deterministic Policy Gradient (DDPG) algorithm [29] while addressing approximation errors. Furthermore, in one formulation of RLQP, we train a shared policy for multiple agents following an RL approach proposed by Huang et al. [23]. With this single policy, RLQP updates multiple parameters using state associated with each constraint of a QP.

heading: 3 Background

text: In this section, we summarize QPs, the OSQP solver, and an MDP formalization.

heading: 3.1 Quadratic Programs

text:
A quadratic program with n variables and m constraints takes the form:
minimize (1/2)xTPx+ qTx subject to l ≤ Ax ≤ u,
where x ∈ Rn is the optimization variable, P is an n× n symmetric positive semi-definite matrix that defines the quadratic cost, q ∈ Rn defines the linear cost, A is an m × n matrix that defines the m linear constraints, and l, u ∈ Rm are the constraint’s lower and upper bounds. Here, ≤ is an element-wise less-than-or-equal-to operator. In this form, to specify an equality constraint, the lower and upper bounds are set to the same value, and to specify a constraint unbounded from one side, a sufficiently large value (or ±∞) is specified for the other side.

heading: 3.2 First-Order QP Solver Algorithm

text:
The solver we speed up is OSQP, which uses a first-order ADMM method to solve QPs. We summarize OSQP here. Given a QP, OSQP first forms a KKT matrix (below), then iteratively refines a solution from an initialization point for vectors x(0) ∈ Rn, y(0) ∈ Rm, and z(0) ∈ Rm, where the
superscript in parenthesis refers to the iteration. Each iteration computes the values for the k + 1 iterates by solving following linear system (e.g., with an LDLT solver):[
P + σI AT
A diag(ρ)−1 ] ︸ ︷︷ ︸
KKT matrix
[ x(k+1)
v(k+1)
] = [ σx(k) − q z(k) − diag(ρ)−1y(k) ]
(1)
and then performing the following updates:
z̃(k+1) ← z(k) + diag(ρ)−1(v(k+1) − y(k)) z(k+1) ← Π[l,u] ( z̃(k+1) + diag(ρ)−1y(k) ) y(k+1) ← y(k) + diag(ρ) ( z̃(k+1) − z(k+1) ) ,
where σ ∈ R+ and ρ ∈ Rm+ are regularization and step-size parameters, and Π[l,u] : Rm → Rm projects its argument on the constraint bounds. We use the notation diag : Rm → Sm to denote the operator that maps a vector to a diagonal matrix. We define the primal and the dual residual vectors as
ξ (k) primal = Ax (k) − z(k), and ξ(k)dual = Px (k) + q +AT y(k).
When the primal and dual residual vectors are small enough in norm after k iterations, x(k+1) and y(k+1) are primal and dual (approximate) solutions to the QP.
Internally, OSQP has a single scalar ρ̄ that it uses to form ρ according to the following formula:
ρ = ρ̄ h1... hm  , where hi = {1 if li ̸= ui (inequality constraints) 103 if li = ui (equality constraints),
(2)
where the subscript i denotes the i-th coefficient of h, and the bounds l and u.
Periodically, between ADMM iterations, OSQP will adapt the value of ρ̄. The existing handcrafted formula for adapting ρ attempts to balance between primal and dual residuals, by setting ρ̄(k+1) ← ρ̄(k) √ ∥ξprimal∥∞/∥ξdual∥∞. Empirically, adapting ρ between iterations can speed up the convergence rate.

heading: 3.3 Multi-Agent Single-Policy MDP

text:
In a Markov Decision Process (MDP), an agent can be in any state s ∈ S, take an action a ∈ A, and with the transition dynamics function, T (· | s, a), transitions from state s to state s′ after taking action a. The agent receives a reward R : S ×A → R for transitioning from s to s′ by taking action a. Given a tuple (S,A, T,R, γ), the MDP optimization objective is to find a policy πθ : S → A, parameterized by θ, that maximizes the expected cumulative reward E [ ∑∞ t=0 γ
trt] , where rt is the reward at time t and γ ∈ [0, 1) is a discount factor. We also formulate a multi-agent single-policy MDP setting in which m agents collaborate in a shared environment in state senv ∈ Senv. At each time step, each collaborating agent (CA) i has its own state si ∈ Sca, action ai ∈ Aca, and observations oi ∈ O, but, for computation feasibility, share a single policy πθ : Sca → Aca. State transitions for the environment and all m agents occur simultaneously according to a state transition function T : Senv × Smca ×Amca → Senv × Sca
m and result in a single shared reward R : Senv×Smca×Amca → R and discount factor. The objective is to find a single shared policy πθ that maximizes the expected cumulative reward. This can be thought of as a special case of a multi-agent MDP [31] or Markov game [30], and we adapt a formulation from Huang et al. [23].

heading: 4 Method

text:
The goal of RLQP is to learn a policy to adapt the ρ ∈ Rm vector used in the ADMM update in (1) (see Fig. 1). As the dimensions of this vector vary between QPs, we propose two methods that can handle the variation in m. The first method learns a policy to adapt a scalar ρ̄ and then applies (2) to populate the coefficients of the ρ vector. The second method learns a policy to adapt individual coefficients of the ρ vector.
Algorithm 1 TD3 for ρ̄ (scalar) 1: Input: exploration noise σ, buffer size rs 2: π,Q← initialize policy and critic (see TD3) 3: D ← replay buffer w/ rs 4: env, s(0) ← new QP, state 5: for t ∈ {0, . . . , T} do 6: ρ̄
(t) ← π(s(t)) + ϵ, ϵ ∼ N (0, σ) 7: s(t+1), r(t), done(t)←step(env, s(t), a(t)) 8: store (s(t), ρ̄(t), r(t), s(t+1)) in D 9: if done(t) then 10: env, s(t) ← new QP, state 11: update π and Q using data sampled from D
Algorithm 2 TD3 for ρ (vector) 1: Input: exploration noise σ, buffer size rs 2: π,Q← initialize policy and critic (see TD3) 3: D ← replay buffer w/ rs×(avg no. of constraints) 4: env, s(0),m← new QP, state, no. of constraints 5: for t ∈ {0, . . . , T} do 6: ρ
(t) i ← π(s (t) i ) + ϵ, ϵ ∼ N (0, σ) ∀i ∈ [1 . . m]
7: s(t+1), r(t), done(t) ← step(env, s(t),ρ(t)) 8: store (D, s(t)i , ρ (t) i , r (t), s (t+1) i ) ∀i ∈ [1 . . m]
9: if done(t) then 10: env, s(t),m← new QP, state, no. of constr. 11: update π and Q using data sampled from D
Since both the number of variables n and the number of constraints m can vary from problem to problem, and the same QP can be written in (n!m!) permutations, we propose learning policies that are problem size and permutation invariant. To do this, we provide a permutation-invariant fixed-size state of the QP solver to either policy.

heading: 4.1 RL Policy for Scalar Adaptation

text:
To speed up convergence of OSQP, we hypothesize that RL can learn a scalar ρ̄ adaptation policy (πscalar) that can perform as-well-as or better than the current handcrafted policy (πhc) of OSQP. The handcrafted policy in OSQP periodically adapts ρ by computing a single scalar ρ̄, then sets the coefficients of ρ based on the value of ρ̄. In both handcrafted and RL cases, the policy is a function π : Sρ̄ → Aρ̄, where Sρ̄ ∈ R2 are the norms of the primal and dual residuals stacked into a vector, Aρ̄ ∈ R is the value to set to ρ̄. One advantage of this approach is that a simple heuristic can check that the proposed change to ρ̄ is sufficiently small and leave the KKT matrix unchanged to avoid a costly matrix factorization.
To compute this policy, π, we use Twin-Delayed DDPG TD3 [13], an extension of deep-deterministic policy gradients (DDPG) [29], as the action space is continuous. We summarize TD3 in Alg. 1. TD3 learns the parameters θ of a policy πscalar network and critic Q network, where πscalar determines the action to take and Qπ(s, a) = r(s, a) + γEs′∼T (·|s,a)[Qπ(s′, π(s′))] is the expected reward for a given state-action pair following the recursive Bellman equation. TD3 updates Qπ by minimizing the loss on the Bellman equation, and updates the policy network using a policy gradient [45] of the objective
J(θ) = Es∼D[R(s, πscalar(s))],
that is, ∇θJ = Es∼D[∇θπscalar(s)∇aQπ(s, a)|a=πscalar(s)]
where D is the discounted state visitation distribution [43]. For brevity, we leave out some details of TD3 in the algorithms, including: Q is composed of two networks, the minimum value of the two networks estimates the reward, exploration noise is clamped, and πscalar updates are staggered.
In RLQP, the “environment” env is an instance of a randomized QP problem, and a call to step() applies a change to ρ̄ (and thus via (2) to ρ), advances a QP a fixed number of ADMM iterations, and returns the updated internal state s, a reward r, and a termination flag done. In this case, the internal state s is a vector containing the current norms of the primal and dual residuals of the QP. The reward r is −1 if not done, and 0 if the QP is solved. We train with randomized QPs across various problem classes (Sec. 5) that have solutions guaranteed by construction. To ensure progress, we set a step limit (not shown in the algorithm) since bad actions can cause the solver to fail to converge in a timely manner. During training, we also always adapt ρ in each step and ignore the heuristic adapt/no-adapt policy.
For well-scaled QPs, the residuals and ρ can reasonably range between 10−6 and 106. Since this can cause issues with training the policy networks, we train the policy network with logs of the residuals, and exponentiate the network’s output to get the action to apply.

heading: 4.2 RL Policy for Vector Coefficient Adaptation

text:
For some classes of QPs, the solver can further speed up convergence by adapting all coefficients of the vector ρ, instead of applying (2) to a scalar ρ̄. Conceptually, this could be accomplished with a policy πvec : SQP → Avec, where SQP ∈ RO(n+m) is the internal state of the solver and Avec ∈ Rm+ is the new value for ρ. However, due to variation in problem size and permutation, we instead propose a simplification in which πvec is formulated as a policy πρ : Sρ → Aρ that is applied per coefficient of ρ. Here, Sρ ∈ R6 is state corresponding to a single coefficient in ρ, and Aρ ∈ R is the value to set for that coefficient.
To define Sρ, we observe that coefficients in ρ are one-to-one with coefficients in y, z, l, u, and Ax. We observe that constraint bounds are likely to have an impact on an ADMM iteration when coefficients of z are “close” to their bounds in l or u. A coefficient in z is also “close” to a solution when it is nearly equal to the corresponding coefficient in Ax. Finally, to include a permutationinvariant signal on the overall convergence, we borrow the idea of max-pooling inputs from graph neural networks [40, 3] and include the infinity norms of the primal and dual residuals of the QP solver. We thus define a coefficient’s state as:
si =  min(zi − li, ui − zi) zi − (Ax)i yi ρi
∥ξprimal∥∞ ∥ξdual∥∞
 ∈ Sρ.
In practice, we clamp values in each state si to reasonable ranges (e.g., [10−8, 106], [−106, 106], [−106, 106], [10−6, 106], [10−6, 106], [10−6, 106] for the coefficients of si, in order). Empirically, training is more efficient if the policy operates on states with the log of the first and last 3 coefficients.
Since each step in the vector formulation applies m actions and updates m states simultaneously, we adapt the multi-agent single-policy TD3 formulation from Huang et al. [23], and show it in Alg. 2, next to Alg. 1, with the main differences highlighted in blue. Before each step, step applies the policy with exploration noise to generate m actions corresponding to m coefficient updates to ρ. After each step, Alg. 2 adds the m tuples to the replay buffer with each tuple consisting of coefficient-specific states and actions, along with the single shared reward for the step. Since each step results in m tuples added to the replay buffer, Alg. 2 allocates a replay buffer large enough to hold the average number of tuples expected to be in the individual QPs in the training set.
The hypothesis of this approach is that the some coefficients, and thus policy actions for coefficients, will have more of an effect on convergence, and thus the reward, than others. When the domain for the policy function has more of an effect, the range of the actions will have lower variance. Similarly, when the policy values have less effect, the variance will be higher. This suggests that when training the policy network in this case, having a lower learning rate, and higher batch size can help. A lower learning rate will cause smaller gradient steps when training the network so that it does not overfit to some part of the high variance training data. A higher batch size will allow gradients to average out in high variance training data so that the gradient step better matches the true mean of the data.

heading: 5 Experiments

text:
To train and test the proposed methods, we modify OSQP to support direct querying and modification of its ρ vector, and integrate both πρ̄ and πvec policies for benchmarking, and a runtime flag to switch between policies. We train the network using randomly generated QPs from OSQP’s benchmark suite. The form of these QPs falls into 7 classes (see below), but the specific coefficient values in the objective and constraints are generated from a random-number generator. These QPs are also guaranteed to be feasible by construction (e.g., by reverse engineering constraint values from a pre-generated solution). To separate train and test sets, we ensure that each set is generated from uniquely seeded random-number generators. Training is performed in PyTorch with a Python wrapper around the modified OSQP which is written C/C++. During benchmarking, the solver performs runtime adaptation of ρ using PyTorch’s C++ API on the already-trained policy network. We train a small model to keep runtime network inference as fast as possible.
We evaluate all policies with 7 problem domains (referred to as the “benchmark problem”) defined in Appendix A of the paper on OSQP [44]. These policies cover control, Huber fitting, support-vector machines (SVM), Lasso regression, Portfolio optimization, equality constrained, and random QP domains. Alongside RLQP, we benchmark the unmodified OSQP solver to evaluate how the RL policy improves convergence. For both RLQP and OSQP, we evaluate to the high-accuracy settings (10−5) of the OSQP benchmarks. While our focus is on improving the first-order method in OSQP with an RL policy, we include some benchmarks against the state-of-the-art commercial Gurobi solver [20] (using default settings) as it may be of interest to a practitioner.
We consider three evaluation configurations: (1) multi-task policy learning in which we train a single RLQP policy on a suite of random benchmark problems and test it across all problems, (2) class-specific policy learning in which we train and test the policy for a single problem domain and (3) zero-shot generalization where we test a general policy on a novel unseen problem class.
We evaluate speedups with the shifted geometric mean [19] as problems have wide variations in runtime across several orders of magnitude. This metric is the standard benchmark used by optimization community. The shifted geometric mean is computed as:
exp N∑ i=1 (1/N) log(max(1, vi + s))− s,
where vi is compute time in seconds, s = 10, and N is the number of values (e.g., QPs solved).
We also evaluate on QPLIB [14], Netlib [16], and Maros and Mészáros [32], as they are wellestablished benchmark problems in the optimization community.
In all experiments, the policy network architecture has 3 fully-connected hidden layers of 48 with ReLU activations between the input and output layers. The input layer is normalized, and the output activation is Tanh. The critic network architectures use the identity function as the output activation, but otherwise matches the policy. As small networks for fast CPU inferences are desirable here, we attempted to keep the network as small as possible. We performed minimal experimentation before settling on this architecture—finding that smaller networks fail to converge during training.
We trained on a system with 256 GiB RAM, two Intel Xeon E5-2650 v4 CPUs @ 2.20 GHz for a total of 24 cores (48 hyperthreads), and five NVIDIA Tesla V100s. We ran benchmarks on a system with Intel i9 8-core CPU @ 2.4 GHz and without GPU acceleration.

heading: 5.1 Multi-task/General RLQP Policy

text:
We train a general policy on a broad set of problem classes and compare solve times with different classes. During training, we sample one of seven QP domains from benchmark problem. From that sampled problem domain, we generate a random problem.
In Fig. 2, we compare the shifted geometric mean of solving 10 problems of 20 different dimension, for a total of 200 runs per class per solver. The problem dimensions for Control, Huber, SVM, Lasso are (10, 11, 12, 13, 14, 16, 17, 20, 23, 26, 31, 37, 45, 55, 68, 84, 105, 132, 166, 209); for Random
and Eq are (10, 11, 12, 13, 15, 18, 23, 29, 39, 53, 73, 103, 146, 211, 304, 442, 644, 940, 1373, 2009), and for Portfolio are (5, 6, 7, 8, 9, 10, 12, 14, 16, 20, 24, 28, 35, 43, 52, 65, 80, 99, 124, 154). From the results, we observe that both RLQP adaptation policies typically improve upon convergence rate from the handcrafted policy in OSQP, and in some cases, e.g. Portfolio optimization, by up to 3x.

heading: 5.2 Problem Dimension Scaling

text: To test how a trained policy scales to higher dimensions, we train a policy on low dimensional problems (10 to 50), and solve problems with varying dimensions, including dimensions higher than the training set (up to 2000). For comparison, we also include a policy trained on the full dimension range (10 to 2000). From the results plotted in Fig. 3, we observe that a policy trained on a lower dimensional training set, can show improvement beyond its training range. However, as the problem size diverges more from the training set, its performance suffers and it eventually loses to the handcrafted policy. Both low-dimensional and full-dimension range polices, were trained using the same network architecture, we hypothesize that this behavior is a function of the training data and not a limitation of the network expressiveness. While this is a disadvantage of using smaller problems for training, in practice it may be outweighed by the advantage in training time—as each RL step requires O((n+m)3) compute time.

heading: 5.3 Training a Class-Specific Policy

text: Many applications in control [25] and optimization [26] require QPs from the same class to be repeatedly solved. To test if training a policy specific to a QP class can outperform a policy trained on the benchmark suite, we train policies specific to the problems generated by the trustregion [8] based solver for sequential quadratic program (SQP) from a grasp-optimized motion planner (GOMP) [25, 24] for robots. With these problems, RLQP trained on the benchmarks converges more slowly than the handcrafted policy included in OSQP. With a vector policy trained on the the QPs from the SQP, the shifted geometric mean of OSQP is 1.37. This result suggests that while a general policy may work for multiple problem classes, there are cases in which it is beneficial to train a policy specific to a problem class, particularly if the QPs from that problem class are repeatedly solved.

heading: 5.4 Warm Starting QPs

text:
One benefit of first-order method such as OSQP is their ability to warm start—that is, rapidly converge from a good initial guess. We test if RLQP retains the benefit of warm start on OSQP’s warm-start benchmark and show the results in Fig. 2 (right). As warm starts require fewer iterations, and thus
fewer adaptations than cold starts, we expect RLQP to show a smaller improvement here. In the plot, we can see that RLQP retains the benefit of warm starting, and also gains a improvement over OSQP.

heading: 5.5 QPLIB

text: We benchmark convex continuous QP instances with constraints from QPLIB [14], and show the results in Table 2. Since there are only a few such QPLIB instances and they come from varying classes, creating a train/test split is problematic. We thus use the general policy trained on the benchmark classes. From the table, we observe that the general RLQP policy beats OSQP’s heuristic policy in all but three cases. In two cases RLQP fails due to reaching an iteration or time limit. Training on similar problems should help avoid a timeout.

heading: 5.6 Netlib Linear Programming benchmark

text: The Netlib Linear Programming benchmark [16] contains 98 challenging real-world problems including supply-chain optimization, scheduling and control problems. As with the QPLIB benchmark, we evaluate results with a general policy trained on the benchmark classes. We solve problems to high-accuracy as many of these benchmarks are poorly scaled. Overall, vector formulation of RLQP is 1.30× faster than OSQP by the scaled geomean of runtimes. We include a problem-specific breakdown in the supplementary materials.

heading: 5.7 Maros and Mészáros

text: In a manner similar to the QPLIB problems, we also benchmark on the Maros and Mészáros repository of QPs. [32]. This collection of 138 QP problems, includes many poorly scaled problems that cause OSQP to fail to converge. We compute the shifted geometric mean for problems solved by both OSQP and RLQP with the general vector policy. RLQP converges faster, with OSQP’s shifted geometric mean is 1.829 times that of RLQP. Because the dataset contains 138 problems, a table of the full results is included in the Supplementary Material.

heading: 5.8 Learned Policy Analysis

text:
We plot and evaluate a learned policy in Fig. 4. From the plot, we see that when z approaches either bound, the output ρ increases. We also observe that with higher y, the policy outputs a higher ρ. Both of these observations are consistent with the intent and observations behind OSQP’s heuristic policy: a high ρ is desirable when the primal residual is smaller than the dual, and a low ρ is desirable
when the dual is smaller than the primal. However, the learned policy is not a simple square root of residuals like OSQP. The results suggest that the optimal policy is non-linear and problem specific.

heading: 6 Limitations

text: RLQP has limitations. For QPs that converge after few iterations, and thus do not adapt ρ, having a better adaptation policy is moot. Training RLQP can take a prohibitively long time and require a large replay buffer for some applications, for example, to train the benchmark suite of QPs required several days on a high-end computer with 256 GiB—this may be mitigated to an extent by sharing learned policies between interested practitioners. The time it takes to evaluate the RL policy, especially the vector version, may reduce the performance benefit of faster convergence—this may be mitigated by learning more efficient representations, or by using dedicated neural-network processing hardware.

heading: 7 Conclusion

text:
We presented RLQP, a method for using reinforcement learning (RL) to speed up the convergence rate of a first-order method quadratic program solver. RLQP uses RL to learn a policy to adapt the internal parameters of the solver to allow for fewer iterations and faster convergence. In experiments, we trained a generic policy and results suggest that a single policy can improve convergence rates for a broad class of problems. Results for a problem-specific policy suggest that fine-tuning can further accelerate convergence rates.
In future work, we will explore whether additional RL policy options can speed up convergence rate further, such as training a hierarchical policy [2] in which the higher-level policy determines the interval between adaptation, performing a neural-architecture search [10], using meta-learning [12, 38] to speed up problem-specific training, and online-learning to adjust the policy at runtime to adapt to changing problems. Furthermore, we will investigate how to analyze the learned policies (e.g., Fig. 4) to devise new optimization algorithms with analytical step-size updates and faster theoretical convergence rates.

heading: Acknowledgements

text: This research was performed at the AUTOLAB at UC Berkeley in affiliation with the Berkeley AI Research (BAIR) Lab, and the CITRIS “People and Robots" (CPAR) Initiative. In addition to NSF CISE Expeditions Award CCF-1730628, this research is supported by gifts from Amazon Web Services, Ant Group, Ericsson, Facebook, Futurewei, Google, Intel, Microsoft, Nvidia, Scotiabank, Splunk and VMware. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the sponsors. We thank Ashwin Balakrishna, Arnav Gulati as well as other colleagues for their helpful feedback.

title: Accelerating Quadratic Optimization with Reinforcement Learning