Alternating Differentiation for Optimization Layers
Authors: Haixiang Sun
Ye Shi
Jingya Wang
Hoang Duong Tuan
H. Vincent Poor
Dacheng Tao
Venue: ICLR 2023 poster (2023)
Keywords: Alternating differentiation
optimization layers
unrolling
implicit models

Abstract: The idea of embedding optimization problems into deep neural networks as optimization layers to encode constraints and inductive priors has taken hold in recent years. Most existing methods focus on implicitly differentiating Karush–Kuhn–Tucker (KKT) conditions in a way that requires expensive computations on the Jacobian matrix, which can be slow and memory-intensive. In this paper, we developed a new framework, named Alternating Differentiation (Alt-Diff), that differentiates optimization problems (here, specifically in the form of convex optimization problems with polyhedral constraints) in a fast and recursive way. Alt-Diff decouples the differentiation procedure into a primal update and a dual update in an alternating way. Accordingly, Alt-Diff substantially decreases the dimensions of the Jacobian matrix especially for optimization with large-scale constraints and thus increases the computational speed of implicit differentiation. We show that the gradients obtained by Alt-Diff are consistent with those obtained by differentiating KKT conditions. In addition, we propose to truncate Alt-Diff to further accelerate the computational speed. Under some standard assumptions, we show that the truncation error of gradients is upper bounded by the same order of variables' estimation error. Therefore, Alt-Diff can be truncated to further increase computational speed without sacrificing much accuracy. A series of comprehensive experiments validate the superiority of Alt-Diff. 

Published as a conference paper at ICLR 2023
ALTERNATING DIFFERENTIATION FOR OPTIMIZATION LAYERS
Haixiang Sun', Ye Shi Jingya Wang', Hoang Duong Tuan?, H. Vincent Poor', Dacheng Tao ShanghaiTech University! University of Technology Sydney?, Princeton University?, ID Explore Academy*
{aunhx, shiye, wongglioyyleesammhaaaeee..... edu. en, Hoan.Hoang@uts.oo pooréprinceton. edu, dacheng www.wttaal.amm.m.. com
ABSTRACT
The idea of embedding optimization problems into deep neural networks as optimization layers to encode constraints and inductive priors has taken hold in recent years, Most existing methods focus on implicitly differentiating Karush-Kubi Kuhn-Tucker tations on the Jacobian matrix, which can be slow and memory-intensive. In this paper, we developed a new framework, named Alternating Differentiation (Alt- Diff), that differentiates optimization problems (here, specifically in the form of convex optimization problems with polyhedral constraints) in a fast and recursive way. Alt-Diff decouples the differentiation procedure into primal update and dual update in an alternating way. Accordingly, Alt-Diff substantially decreases the dimensions of the Jacobian matrix especially for optimization with large-scale constraints and thus increases the computational speed of implicit differentiation. We show that the gradients obtained by Alt-Diff are consistent with those obtained by differentiating KKT conditions. In addition, we propose to truncate Alt-Diff further accelerate the computational speed. Under some standard assumptions. we show that the truncation еπтоr of gradients is upper bounded by the same or- der of variables' estimation error. Therefore, Alt-Diff can be truncated to further increase computational speed without sacrificing much accuracy. A series of com- prehensive experiments validate the superiority of Alt-Diff.
Tucker (KKT) conditions in a way that requires expensive compu-
INTRODUCTION
Recent years have seen variety of applications in machine learning that consider optimization as a tool for inference learning Belanger McCallum (2016); BBllange al. (2017)[Diamonl)) DDiamnn et al.) (2077); Amos et al. (2017); Amos & Kolter (2017); Agrawal et al. (2019a). Embedding optimiza- tion problems as optimization layers in deep neural networks can capture useful inductive bias, such domain-specifie knowledge and priors. Unlike conventional neural networks, which are defined by an explicit formulation in each layer, optimization layers are defined implicitly by solving opti- mization problems. They can be treated as implicit functions where inputs are mapped to optimal solutions. However, training optimization layers together with explicit layers is not easy since ex- plicit closed-fome form solutions typically do not exist for the optimization layers.
Generally, computing the gradients of the optimization layers can be classified into two main cat- egories: differentiating the optimality conditions implicitly and applying unrolling methods. The ideas of differentiating optimality conditions have been used in bilevel optimization Kunisch & Pock (0113); (2ck) Gould et al. (2016) and sensitivity analysis Bonnans Shapiro (2013). Recently, Opt- Net Ammss & Kolter (2017) and CvxpyLayer Agrawal et al. (2019)) have extended this method to optimization layers so as enable end-to-end learning within the deep learning structure. How- ever, these methods inevitably require expensive computation on the Jacobian matrix. Thus they are prone to instability and are often intractable, especially for large-scate scale optimization layers. Another direction to obtain the gradients of optimization layers is based on the unrolling methods Diamond et al. )); Zhang et al. 2023), where an iterative first-order gradient method is applied. However,
"Corresponding author

---

Published as a conference paper at ICLR 2023
they memory cemooryinttensive since all the intermediate results have to be recorded. Besides, unrolling methods are not quite suitable to constrained optimization problems as expensive projection opera- tors are needed.
In this paper, we aim to develop a new method that significantly increases the computational speed of the differentiation procedure for convex optimization problems with polyhedral constraints. Mo- tivated by the scalability of the operator splitting method for optimization problem Glowinski & Le Tallec (1989); Stellato et al. (2020), we developed a new framework, namely Alternating Dif- ferentiation (Alt-Diff), that differentiates optimization layers in a fast and recursive way. Alt-Diff first decouples the constrained optimization problem into multiple subproblems based on the well- known alternating direction method of multipliers (ADMM) Boyd et al. (201T). Then, the differen- tiation operators for obtaining the derivatives of the primal and dual variables w.r.t the parameters are implemented on these subproblems in an alternating manner. Accordingly, Alt-Diff substantially decreases the dimensions of the Jacobian matrix, significantly increasing the computational speed of implicit differentiation, especially for large-scale problems. Unlike most existing methods that directly differentiate KKT conditions after obtaining the optimal solution for an optimization prob- lem, Alt-Diff performs the forward and backward procedures simultaneously. Both the forward and backward procedures can be truncated without sacrificing much accuracy in terms of the gradients of optimization layers. Overall, our contributions three-fold:
We develop new differentiation framework Alt-Diff that decouples the optimization layers in an alternating way. Alt-Diff significantly reduces the dimension of the KKT matrix, es- pecially for optimization with large-scale constraints and thus increases the computational speed of implicit differentiation.
We show that: 1) the gradient obtained by Alt-Diff' are consistent with those obtained by differentiating the KKT conditions; 2) the truncation error of gradients upper bounded by the same order of variables' estimation error given some standard assumptions. Therefore, Alt-Diff can be truncated accelerate the computational speed without scarifying much accuracy.
We conduct a series of experiments and show that Alt-Diff can achieve results comparable to state-of-the-an methods in much less time, especially for large-scale optimization prob- lems. The fast performance of Alt-Diff comes from the dimension reduction of the KKT matrix and the truncated capability of Alt-Diff.
RELATED WORK
Differentiation for optimization layers Embedding optimization problems into deep learning ar- chitectures as optimization layers to integrate domain knowledge has received increasing attention recent years Gould et al. (2016); Amos Kolter (2017): Agrawal et al. (2019)); Gould et al.) (202I). For example, Gould al. (2016) collected some general techniques for differentiating argmin and argmax optimization problems based on the Implicit Function Theorem, while Amos & Kolter 2017) proposed network architecture, namely OptNet, that integrates quadratic optimiza- tion into deep networks. This work was further extended for end-to-end learning with stochastic programming Donti et al. (2017). Recently, an efficient differentiable quadratic optimization layer Butler & Kwon (2022) based on ADMM was proposed to accelerate the differentiation procedure.
However, these methods are only restricted handling the differentiation of quadratic problems. For more general convex optimization, /Agrawal et al. (2019)) proposed CvxpyLayer that differenti- ates through disciplined convex programs and some sparse operations and LSQR Paige Saunders 1982) to speed up the differentiation procedure. Although these have been worthwhile attempts to accelerate the differentiation procedure, they still largely focus on implicitly differentiating the KKT conditions in way that requires expensive operations differentiation solver named JaxOpt Blondel et al. (2021) has also been put forward that is based on an implicit automatic differentiation mechanism under the Jax framework.
large-scale Jacobian matrix. Recently,
Unrolling methods Another direction for differentiating optimization problems is the unrolling methods Domke (2012); Monga et al. (2021). These approximate the objective function with first-order gradient method and then incorporate the gradient of the inner loop optimization into the training procedures Belanger & McCallum (2016); [Belanger et al. (201)): Amos et al. (2017); Metz
2

---

Published as a conference paper at ICLR 2023
al. (2019). This is an iterative procedure, which is usually truncated to a fixed number of itera- tions. Although unrolling methods are easy to implement, most their applications are limited to unconstrained problems. If constraints added, the unrolling solutions have to be projected into the feasible region, significantly increasing the computational burdens. By contrast, Alt-Diff only requires very simple operation that projects the slack variable to the nonnegative orthant. This substantially improves the efficiency of subsequent updates and reduces the method's computational complexity.
Implicit models There has been growing interest in implicit models in recent years J. Z. Kolter & Johnson (2020); Zhang et al. (2020); Bolte al. (202I). Implicit layers replace the traditional feed- forward layers of neural networks with fixed point iterations to compute inferences. They have been responsible for substantial advances in many applications, including Neural ODE
2018);
Dupont et al. (2019). Deep Equilibrium Models Bai et al. (2019) 2020); Gurumurthy et al. 2021
nonconvex optimization problems Wang al. (2019) and implicit 3D surface layers Micha
al. 2019); Park et al. (2019), etc. Implicit layers have similar computational complexity to optimization layers as they also requires solving a costly mncobian-based equation based on the Implicit Function Theorem. Recently, Fung al. (2021) proposed Jacobian-fin free backpropagation method to accelerate the speed of training implicit layers. However, this method is not suitable for the optimization layers with complex constraints. In terms of training implicit models, Geng al.) (202T) also proposed a novel gradient estimate called phantom gradient which relies on fixed-point unrolling and Neumann series provide a new update direction; computation of precise gradient is forgone. Implicit models have also been extended to more complex learning frameworks, such as attention mechanisms Geng et al. (2020) and Graph Neural Networks Gu al. (2020).
PRELIMINARY: DIFFERENTIABLE OPTIMIZATION LAYERS
We consider a parameterized convex optimization problems with polyhedral constraints:
min
fxx; 0)
s.t.
E
where x E IR" is the decision variable, the objective function f R" - R is convex and the constraint C(0) := {x|Az= b, Gr S h) is polyhedron. For simplification, we use 9 to collect the parameters in the objective function and constraints. For any given A, a solution of optimization problem ④ is xx R that minimizes (a; 0) while satisfying the constraints, i.e. x= E C(0). Then the optimization problem 4 can be viewed as mapping that maps the parameters to the solution x² Here, we focus on convex optimization with affine constraints due its wide applications in control systems Guo & Wang (010)). signal processing Mattingley & Boyd 2010). communication networks Luong al. (2017): Bui et (2017). etc.
Since optimization problems can capture well-defined specific domain knowledge in a model-driven way, embedding such optimization problems into neural networks within an end-to-end learning framework can simultaneously leverage the strengths of both the model-driven and the data-driven methods. Unlike conventional neural networks, which are defined through explicit expressions of each layer, optimization layer embedded in optimization problem ( is defined as follows:
Definition 3.1. (Optimization Layer) A layer a neural network is defined as an optimization layer its input is the optimization parameters 0 gM and its output x Rn is the solution of the optimization problem ①
The optimization layer can be treated as an implicit function R R with F(x*, O. In the deep learning architecture, optimization layers implemented together with other explicit layers an end-to-end framework. During the training procedure, the chain rule used to back propagate the gradient through the optimization layer. Given loss function R, the derivative of the loss w.r.t the parameter 9 of the optimization layer is
aR. JR Ox
00 Ox* 00
Obviously, the derivative DR. can be easily obtained by automatic differentiation techniques on explicit layers, such fully connected layers and convolutional layers. However, since explicit
3

---

Published as a conference paper at ICLR 2023
closed-form solutions typically do not exist for optimization layers, this brings additional compu- tational difficulties during implementation. Recent work, such as OptNet Amos & Kolter (2017) and CvxpyLayer Agrawal et al. (2019a) have shown that the Jacobian 2z ay can be derived by differ- entiating the KKT conditions the optimization problem based on the implicit Function Theorem Krantz & Parks (2002). This is briefty recalled Lemma 3.2
Lemma 3.2. (Implicit Function Theorem) Let F(x, 0) denote a continuously differentiable function
with F(x", f) = O. Suppose the Jacobian F(x, 8) is invertible at (x*;0), then the derivative of the solution x² with respect to 0 is
Or = - [Frx]] JF,e,
(3)
00
where FF == 2zF(x* and JF VaF(x* ()) are respectively the Jacobian of F(x, 0) w.r.t x and 0.
worth noting that the differentiation procedure needs to calculate the optimal value x" in the forward pass and involves solving linear system with Jacobian matrix FF in the backward pass. Both the forward and backward pass are generally very computationally expensive, especially for large-scale problems. This means that differentiating KKT conditions directly is not scalable to large optimization problems. Existing solvers have made some attempts to alleviate this issue. Specifi- cally, CvxpyLayer adopted LSQR technique accelerate implicit differentiation for sparse opti- mization problems. However, the method is not necessarily efficient for more general cases, which may not be sparse. Although OptNet uses a primal-dual interior point method in the forward pass and its backward pass can be very easy but OptNet is suitable only for quadratic optimization prob- lems. In this paper, our main target is to develop new method that can increase the computational speed of the differentiation procedure especially for sange-scale constrained optimization problems.
ALTERNATING DIFFERENTIATION FOR OPTIMIZATION LAYERS
This section provides the details of the Alt-Diff algorithm for optimization layers. Alt-Diff decom- poses the differentiation of a large-scale KKT system into a smaller problems that are solved in primal-dual alternating way (see Section 4.1). Alt-Diff reduces the computational complexity of the model and significantly improves the computational efficiency of the opúmization layers. In section 4.2, we theoretically analyze the truncated capability of Alt-Diff. Notably, Alt-Diff can be truncated for inexact solutions to further increase computational speeds without sacrificing much accuracy.
4.1 ALTERNATING DIFFERENTIATION
Motivated by the scalability of the operator splitting method Glowinski & Le Tallec (1989); Stellato ct al. 22020), Alt-Diff first decouples a constrained optimization problem into multiple subproblems based ADMM. Each splitted operator is then differentiated to establish the derivatives of the primal and dual variables w.r.t the parameters in an alternating fashion. The augmented Lagrange function of problem (1) with quadratic penalty term is:
max min C(x, s, A, 8)
A 2,820
(4)
=]<;;0 (A, Ar b) (v. Go h) (11Ax bll + +I h113),
where s 2 negatiee slack variable, and p hyperparameter associated with the penalty term. Accordingly, the following ADMM procedures are used to alternatively update the primary, slack and dual variables:
Fk+1 = arg min L(x, 8k, AE, Mk; A),
(5a)
8k+1 = arg min C( 8, Ak; Mks 0),
(5b)
+20
AR+1 Du p(Axx41 b),
(5c)
Mk+1 = u% + p(GGx411 + Sk+1 h).
(5d)
4

---

Published as a conference paper at ICLR 2023
Note that the primal variable 24+1 is updated by solving unconstrained optimization problem. The update the slack variable Sk+1 is easily obtained by a closed-form solution via a Rectified Linear Unit (RcLU)
Sk+1 = ReLU -- 1emk-Gaay 1G22441441 -h)-
(6)
The differentiations for the slack and dual variables trivial and can be done using automatic differentiation technique. Therefore, the computational difficulty is now concentrated around differ- entiating the primal variables, which be done using the Implicit Function Theorem. Applying differentiation technique to procedure (5) leads to:
0rs+1
V (V(((=+1)) V Vz,oL(E4+1I:
(7a)
09
0sh+1
@uv a(Gr+4 -hi )
sgn (gm(1)+1)= 1
00 p
(7b)
00
P
09
0h
aλk
0(AT++1 -
(7c)
00
00
00
0vk+1
dvk
O(Gr++1 8k+1 h)
+
(7d)
00
00
08
where v2((xx+1) = (2 + PAT + +pG G. O represents Hadamard production,
sgn( (gn(sa-1) denotes function such that sgn(s 1 if 441 2 0 and sgn(s (s) versa.
0 vice
We summarize the procedure of Alt-Diff in Algorithm/ and provide a framework of Alt-Diff in Appendix A The conver- gence behavior of Alt-Dilf can be in- spected by checking || 24 ///l//|/= where c is predefined threshold.
Algorithm 1 Alt-Diff
Parameter: @ from the previous layer
Initialize slack variable and dual variables
while || 2g 205ll/1ee
2 c do
Forward update by (5)
Notably, Alt-Diff is somehow similar unrolling methods as in Foo et al. (2007): Domke (2012). However, these unrolling methods were designed for unconstrained optimization. If constraints are added, the unrolling solutions have be projected into a feasible region. Generally this pro-
Primal update
0wa.1
89
by 7a
Slack update 0sk+1 by 7bb
89
Dual update
0AR11 and 00
dvg 00
by
7ch
and (d)
k := k end while return x² and its gradient Oz
jector operators very computationally expensive. By contrast, Alt-Diff can decouple constraints from the optimization and only involves very simple operation that projects the slack variable to the nonnegative orthant 2 0. This significantly improves the efficiency of subsequent updates and reduces the overall computational complexity of Alt-Diff. Besides, conventional unrolling methods usually need more memory consumption all the intermediate computational results have to be recorded. However, when updating 7 continuously, Alt-Diff does not need to save the results of the previous round. Instead, it only saves the results of the last round, that is, the previous dis is 20
replaced by the 0r1+1 iteratively. Besides, we show that the gradient obtained by Alt- consis- 30
tent with the one obtained by the gradient of the optimality conditions implicitly. A detailed proof as well as the procedure for differentiating the KKT conditions presented the Appendix
For more clarity, we take several optimization layers for examples to show the implementation of Alt-Diff, including Quadratic Layer|Amos Amos Kolter (2017), constrained Sparsemax Layer Malaviya al. (2018) and constrained Softmax Layer Martins & Astudillo (2016). These optimization layers were proposed to integrate specific domain knowledge in the learning procedure. Detailed deriva- tions for the primal differentiation procedure (7a) are provided in the Appendix B.2
In the forward pass, the unconstrained optimization problem (5a) can be easily solved by Newton's methods where the inverse of Hessian, i.e. (V3+(==))) is needed. It can be directly used in the backward pass (7a) to accelerate the computation after the forward pass. The computation even more efficient in the case of quadratic programmings, where ((r constant and only
5

---

Published as a conference paper at ICLR 2023
needs to be computed once. More details are referred to Appendix B.1 objective function and constraints, it is obviously that the dimension of Hessian matrix (x(((++1) reduced to the number of variables n. Therefore, the complexity for Alt-Diff becomes O (n which differs from directly differentiating the KKT conditions with complexity of O(n + n.) This also validates the superiority of Alt-Diff for optimization problem with many constraints. To further accelerate Alt-Diff, we propose to truncate its iterations and analyze the effects of truncated Alt-Diff.
As Alt-Diff decouples the
4.2 TRUNCATED CAPABILITY OF ALT-DIFF
As shown in recent work Fung et al. 202 y Geng et al. (2021), exact gradients are not necessary during the learning process of neural networks. Therefore, Alt-Diff given some threshold values c. The truncation in existing methods (OptNet and CvxpyLay- ers) that are based on interior point methods often does not offer significant improvements. This because the interior point methods often converge fast whereas the computational bottleneck comes from the high dimension of the KKT matrix instead of the number of iterations the interior points methods. However, the iteration truncation can benefit Alt-Diff more the iteration of Alt-Diff is more related to the tolerance due to the sublinear convergence of ADMM. Our simulation results in Section 5. and Appendix F.] also verify this phenomenon. Next, we give theoretical analysis to show the influence of truncated Dif-
can truncate the iterative procedure of
Assumption A (L-smooth) The first order derivatives of loss function R and the second derivatives of the augmented Lagrange function & are L-Lipschitz. For Væ1, 22 E R".
R mi) - V (2 S L [2] 22
(8a)
(=1 v2f < L2 Ø1 z2ll - 2 I L3 [1 x2|l.
(8b)
(8c)
Assumption B (Bound of gradients) The first and second order derivative of function L and R are bounded as follows:
vz,o((t) 3 M3T, where M1, A2 and H3 are positive constants. The above inequalities hold for Vz E R
V. R(0;x) I IT
V=(())
Assumption C (Nonsingular Hessian) Function f(x) is twice differentiable. The Hessian matrix of augmented Lagrange function L is invertiable any point x E R
Theorem 4.1. (Error of gradient obtained by truncated Alt-Diff) Suppose my is the truncated solu- tion the k-th iteration, the error between the gradient the real gradient Os" is bounded as follows,
azs obtained by the truncated Alt-Diff and 00
30
Orx
Ox
< Ci ( - x=11,
(10)
00
00
Log
2zI2 22
where C1
+
is a constant.
f22
Please refer to Appendix for our proof. The theorem has shown that the primal differentiation (7a obtained by Alt-Diff has the same order of error brought by the truncated iterations of (5a). Besides, this theorem also illustrates the convergence of Alt-Diff. By the convergence of ADMM itself, Ig will converge =². The convergence of the Jacobian is established accordingly and the results from the computational perspective are shown Appendix F.2 Moreover, we can derive the following corollary with respect the general loss function R accordingly.
Corollary 4.2. (Error of the inexact gradient in terms of loss function) Followed by Theorem the error of the gradient w.E.I. O in loss function R. is bounded as follows:
|VR σx)
VR(0;=*)Il S C2l1 - x=11.
(11)
where C2 = L1 HaL + L1
L1nba2 is a constant.
P22
p5
Please refer to Appendix D for our proof. Truncating the iterative process in advance will result in fewer steps and higher computational efficiency without sacrificing much accuracy. In the next section, we will show the truncated capability of Alt-Diff by several numerical experiments.

---

Published as a conference paper at ICLR 2023
5 EXPERIMENTAL RESULTS
In this section, we evaluate Alt-Diff over a series of experiments to demonstrate its performance in terms of computational speed well as accuracy. First, we implemented Alt-Diff over several opti- mization layers, including the sparse and dense constrained quadratie layers and constrained softmax layers. In addition, applied the Alt-Diff to the real-world task of energy generation scheduling under a predict- thenoitttte--opiiiize framework. Moreover, we also tested Alt-Diff with quadratic layer in image classification task the MNIST dataset. To verify the truncated capability of Alt-Diff, we also implemented Alt-Diff with different values of tolerance. All the experiments were imple- mented Core Intel(R) 17-10700 CPU @ 2.90GHz with 16 GB of memory. Our source code for these experiments is available at http://hhbb..com///ssSS////////
5.1 NUMERICAL EXPERIMENTS ON SEVERAL OPTIMIZATION LAYERS
In this section, compare Alt-Diff with OptNet and CvxpyLayer several optimization layers, including the constrained Sparsemax layer, the dense Quadratic layer and the constrained Softmax layer which are referred to typical cases of sparse, dense quadratic problems and problems with general convex objective function, respectively.
In the dense quadratic layer, with the objective function = + g xr the parameters
P. q. A, b, G, were randomly generated from the same random seed with P set 10-3 3 for OptNet, CvxpyLayer and Alt-Diff. As the parameters in optimization problems generated randomly, we compared Alt-Diff with the "dense" mode in CvxpyLayer. All the numerical experiments were executed 5 times with the average times reported the results in Table [ It can be seen that OptNet runs much faster than CvxpyLaye for the dense quadratic layer, while our Alt- Diff outperforms both the two counterparts. Additionally, the superiority of Alt-Diff becomes more evident with the increase of problem size. We also plot the trend of Jacobian drg with iterations in primal update (7a) in Figure [ As shown in Theorem 4.1] the gradient obtained by Alt-Diff can gradually converge to the results obtained by KKT derivative as the number of iterations increases. The results in Figure also validate this theorem.
2 0. The tolerance e is
8h
Table 1: Comparison of running time (s) and cosine distances of gradients in dense quadratic layers
with tolerance 10 10-3
Tiny
Small
Medium
Large
Num of variable
1500
3000
5000
10000
Num of ineq. m
500
1000
2000
5000
Num of eq. p
200
500
1000
2000
Num of elements
4.84 x 106
2.03 x 107
6.4 107
2.89 x 10
OptNet (total)
0.81
9,48
40.72
317.78
Forward
0.77
9.29
40.19
315.21
Backward
0.04
0.19
0.53
2.57
CvxpyLayer (total)
25.34
212.86
1056.18
Initialization
1.86
10.51
38.73
Canonicalization
0.37
1.47
4.40
Forward
14.00
117.06
572.24
Backward
9.11
83.82
440.80
Alt-Diff (total)
0.71
5.75
20.20
154.52
Inversion
0.11
0.91
3.03
21.12
Forward and backward
0.60
4.84
17.17
133.40
Cosine Dist.
0.999
0.999
0.999
0.998
"." represents that the solver cannot generate the gradients.
Further, we conduct experiments to compare the truncated performance among Dlt- OptNet and CvxpyLayer under different tolerance levels e. As shown Table 2 we can find that the truncated operation will not significantly improve the computational speed for existing methods but does have significant improvements for Alt-Diff. The detailed results other optimization layers are provided in Appendix F1

---

Published as a conference paper at ICLR 2023
Table 2: Comparison of running time (s) under different tolerances for dense quadratic layer with
3000, m = 1000 and 500.
Tolerance e
10
10-2
10-3
10-4
10-5
OptNet
8.58
9.32
9.48
9.59
10.13
LaxpyLayer Alt-Diff
212.34
216.66
212.86
215.75
213.08
1.18
3.50
5.75
8.04
10.76
1.00
1.2
0.50
0.85
CyxpyLayer
All-dif
0.75
20 Iteration
1.0
30
Beeation
(a) The variation trends. (Blue dotted line the gradient Se* obtained by CvxpyLayer).
(b) The cosine distance of the obtained gradient between Alt-Diff and Caxpylayer.
85
Figure 1: The variation of primal variable gradient of dense quadratic layers. (The threshold of iteration is set as 10 10-3)
5.2 ENERGY GENERATION SCHEDULING
In order to test the accuracy of sparse layers, we applied the Alt-Diff to the real-world task of energy generation scheduling Donti al. 2017) under a predict-then-optimize framework [llacchoub & Grigas (2021); ; Mandi et al. 22000; ; Mandi & Guns (2020). Prediet-then-optmmize an end-to-end learning model, which
unknown variables are first predicted by some machine learning methods and are then successively optimized. The main idea of cecdict-teenoptimmie is to use the
optimization loss [2) guide the prediction, rather than use the prediction loss in the normal learning style.
L(O,0) 0)
Σ (2) (0))
(12)
2 1=1
We consider the energy generation scheduling task based the actual power demand for electricity in certain region web) In this setting, a power system operator must decide the electricity genera- tion schedule for the next 24 hours based on some historical electricity demand information. In this paper, we used the hourly electricity demand data over the past 72 hours to predict the real power demand in the next 24 hours. The predicted electricity demand then input into the following optimization problem to schedule the power generation:
24
min 35
Σ 10
Pap 11
(13)
A=1
s.t. [K++1
Fal Sr. k 1,2,,
where Pa, and Ft denote the power demand and power generation at time slot l respectively. Due to physical limitations, the variation of power generation during single time slot is not allowed to exceed a certain threshold value r. During training procedures, we use a neural network with two hidden layers predict the electricity demand of the next 24 hours based the data of the previous 72 hours. All the Pa, have been normalized into the j0, 100) interval.
The optimization problem in this task be treated like the optimization layer previously consid- ered. As shown in Table since the constraints are sparse, OptNet runs much slower than the "Isqr" mode in CyxpyLayer. Therefore, respectively implemented Alt-Diff and CvxpyLayer to obtain
8

---

Published as a conference paper at ICLR 2023
the gradient of power generation with respect to the power demand. During the training procedure, we used the Adam optimizer Kingma Ba (2014) to update the parameter. Once complete, we compared the results obtained from CvxpyLayer (with tolerance 10 10-3) and those from Alt-Diff un- der different levels truncated thresholds, varying from 10-1, 10-2 to 10-3. The results are shown in F We old values are almost the same, but the running time of Alt-Diff' is much smaller than CvxpyLayer especially in the truncated cases.
that the losses for CvxpyLayer and Alt-Diff with different truncated thresh-
2430
Copyyayer,co <- AILOP, c
2200
M 10'1
2030
1830
1630
1430
1230
1000
02
c+30
iterations
models
(a) The convergence behaviors.
(b) The average running time.
Figure 2: The experimental results of Alt-diff and CvxpyLayer for energy generation scheduling.
5.3 IMAGE CLASSIFICATION
We follow similar experimental settings in OptNet & Kolter (2077) embed the optimization layer into the neural networks for image classification task on MNIST dataset. A layer in the neural networks is replaced by dense quadratic optimization layer. Then compare the computational speed and accuracy between Alt-Diff and OptNet. As the experiment results shown in Appendix F2 we can see Alt-Diff runs much faster and yields similar accuracy compared to OptNet. Since OptNet runs much faster than CvxpyLayer in dense quadratic layers (as shown in Section 5.1) therefore we only compare Alt-Diff with OptNet here. More details are provided in the Appendix F due to page limitation.
CONCLUSION
In this paper, have proposed Alt-Diff for computationally efficient differentiation optimization layers associated with convex objective functions and polyhedral constraints. Alt-Diff differentiates the optimization layers in fast and recursive way. Unlike differentiation the KKT conditions of optimization problem, Alt-Diff decouples the differentiation procedure into primal update and a dual update by alternating way. Accordingly. Alt-Diff substantially decreases the dimensions of the Jacobian matrix especially for large-scale constrained optimization problems and thus increases the computational speed. We have also showed the convergence of Alt-Diff and the truncated er- ror of Alt-Diff given some general assumptions. Notably, we have also shown that the iteration truncation can accelerate Alt-Diff more than existing methods. Comprehensive experiments have demonstrated the efficiency of Alt-Diff compared to the state-of-the-an Apart from the superiority of Alt-Diff, we also want to highlight its potential drawbacks. One issue is that the forward pass of Alt-Diff is based on ADMM, which does not necessarily always outperform the interior point meth- ods. addition, Alt-Diff currently designed only for specific optimization layers the form of convex objective functions with polyhedral constraints. Extending Alt-Diff to more general convex optimization layers and nonconvex optimization layers is under consideration in our future work.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This work was supported by the Shanghai Sailing Program (22YF1428800, 21YF1429400,, Shang- hai Local college capacity building program (23010503100) and Shanghai Frontiers Science Center of Humancentered Artificial Intelligence (ShangHAI).
REFERENCES
Eletrical load.
Accessed: 2021-12-30.
Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and Zico Kolter. Differentiable convex optimization layers. arXiv preprint arXiv:/910. /2430, 2019a.
Akshay Agrawal, Shane Barratt, Stephen Boyd, Enzo Busseti, and Walaa M Moursi. Differentiating through a cone program. arXiv preprint 1rXiv:/904.0900 2019b.
Brandon Amos and Zico Kolter. Optnet: Differentiable optimization layer in neural networks. In International Conference on Machine Learning, pp. 136-145. PMLR, 2017.
Brandon Amos, Lei Xu, and Zico Kolter. Input convex neural networks. In International Confer- ence on Machine Learning, pp. 146-155. PMLR, 2017.
Shaojie Bai, J Zico Kolter, and Vladlen Koltun. Deep equilibrium models. Advances in Neural Information Processing Systems, 32, 2019.
Shaojie Bai, Vladlen Koltun, and J Zico Kolter. Multiscale deep equilibrium models. Advances in Neural Information Processing Systems, 33:5238-5255 -2530, 2020.
David Belanger and Andrew McCallum. Structured prediction energy networks. In International Conference on Machine Learning, pp. 983-999399 992. PMLR, 2016.
David Belanger, Bishan Yang, and Andrew McCallum. End-to-end learning for structured prediction energy networks. In International Conference on Machine Learning, pp. 429-439. PMLR, 2017.
Mathieu Blondel, Quentin Berthet, Marco Cuturi, Roy Frostig, Stephan Hoyer, Felipe Llinares- López, Fabian Pedregosa, and Phillppi Vert. Efficient and modular implicit differentiation. arXiv preprint arXiv:2105./5183 2021.
Jérôme Bolte, Tam Le, Edouard Pauwels, and Tony Silveti-Falls Nonsmooth implicit differentiation for machine-learnnng and optimization. Advances in neural information processing systems, 34: 13537-13549, 2021.
J Frédéric Bonnans and Alexander Shapiro. Perturbation analysis of optimization problems. Springer Science & Business Media, 2013.
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al. Distributed optimiza- tion and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ in Machine learning, 3(1):1-122, 2011.
Nicola Bui, Matteo Cesana, S Amir Hosseini, Qi Liao, Ilaria Malanchini, and Joerg Widmer. A survey of anticipatory mobile networking: Context-based classification, prediction methodolo- gies, and optimization techniques. IEEE Communications Surveys & Tutorials, 190--1819,, 2017.
Andrew Butler and Roy H Kwon. Efficient differentiable quadratic programming layers: an ADMM approach. Computational Optimization and Applications, pp. 1-28, 2022.
Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differential equations. Advances in neural information processing systems, 31, 2018.
Steven Diamond, Vincent Sitzmann, Felix Heide, and Gordon Wetzstein. Unrolled optimization with deep priors. arXiv preprint arXiv: 1705. 08041, 2017.
10

---

Published as a conference paper at ICLR 2023
Justin Domke. Generic methods for optimization-buser modeling. In Artificial Intelligence and Statistics, pp. 318 -26.. PMLR, 2012.
Priya L Donti, Brandon Amos, and J Zico Kolter. Task-based end-to-end model learning in stochastic optimization. arXiv preprint arXiv: 1003: 021177033.2422 04529, 2017.
Emilien Dupont, Arnaud Doucet, and Yee Whye Teh. Augmented neural ODEs. Advances Neural Information Processing Systems, 32, 2019.
Adam N Elmachtoub and Paul Grigas. Smart "predict, then optimize". Management Science, 2021.
Chuan-sheng Foo, Andrew Ng, et al. Efficient multiple hyperparameter learning for lin-ainear mod- els. Advances neural information processing systems, 20, 2007.
Samy Wu Fung. Howard Heaton, Qiuwei Li, Daniel McKenzie, Stanley Osher, and Wotao Yin. JFB: Jacobian-free backpropagation for implicit networks. arXiv preprint arXiv:2103. 12803, 2021.
Zhengyang Geng, Meng- Hao Guo, Hongxu Chen, Xia Li, Ke Wei, and Zhouchen Lin. Is attention better than matrix decomposition? In International Conference on Learning Representations, 2020.
Zhengyang Geng, Xu Zhang, Shaojie Bai, Yisen Wang, and Zhouchen Lin. On training implicit models. Advances in Neural Information Processing Systems, 34:24247-24260, 2021.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246. 2018
Roland Glowinski and Patrick Le Tallec. Augmented Lagrangian and operator-splitting methods in nonlinear mechanics. SIAM, 1989.
Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo. On diffcrentiating parameterized argmin and argmax problems with application to bi-level optimization. arXiv preprint arXiv: 0.5400000747,... 2016.
Stephen Gould, Richard Hartley, and Dylan Campbell. Deep declarative networks. IEEE Transac- fions on Pattern Analysis and Machine Intelligence (568))398844044 2021.
Fangda Gu, Heng Chang, Wenwu Zhu, Somayeh Sojoudi, and Laurent El Ghaoui. Implicit graph neural networks. Advances in Neural Information Processing Systems,
2020.
Lei Guo and Hong Wang. Stochastic distribution control system design: convex optimization approach. Springer, 2010.
Swaminathan Gurumurthy, Shaojie Bai, Zachary Manchester, and Zico Kolter. Joint inference and input optimization in equilibrium networks. In Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
D. Duvenaud J. Z. Kolter and M. Johnson. Deep implicit layers neural ODEs, deep equilibirum models, and beyond.
al org/ 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXiv:1412.6980 2014.
Steven George Krantz and Harold R Parks. The implicit function theorem: history, theory, and applications. Springer Science & Business Media, 2002.
Karl Kunisch and Thomas Pock. A bilevel optimization approach for parameter learning in varia- tional models. SIAM Journal on Imaging Sciences, 6(2):938-))) 983, 2013.
Nguyen Cong Luong, Ping Wang, Dusit Niyato, Yonggang Wen, and Zhu Han. Resource man- agement in cloud networking using economic analysis and pricing models: A survey, IEEE Communications Surveys & Tutorials, 19(2):554-001, 2017.
Chaitanya Malaviya, Pedro Ferreira, and André FT Martins. Sparse and constrained attention for neural machine translation. arXiv preprint arXiv: /005:0880.0222 2018.

---

Published as a conference paper at ICLR 2023
Jayanta Mandi and Tias Guns. Interior point solving for LP-based prediction+ optimisation. arXiv preprint 1XXv:20100119433 2020.
Jayanta Mandi, Peter J Stuckey, Tias Guns, et al. Smart predict-and-optmiize for hard combina- torial optimization problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 1603-1610, 2020.
Andre Martins and Ramon Astudillo. From softmax to sparsemax: A sparse model of attention and multi-label classification. International conference on machine learning, pp. 1614-1623. PMLR, 2016.
John Mattingley and Stephen Boyd. Real-time convex optimization in signal processing. IEEE Signal processing magazine, 27(3):50-61, 2010.
Luke Metz, Niru Maheswaranathan, Jeremy Nixon, Daniel Freeman, and Jascha Sohl-Dickstein. Understanding and correcting pathologies in the training of learned optimizers. In International Conference on Machine Learning, pp. 4556-4565, PMLR, 2019.
Mateusz Michalkiewicz, Jhony K Pontes, Dominic Jack, Mahsa Baktashmotlagh, and Anders Eriksson. Implicit surface representations as layers in neural networks. Proceedings of the IEEE/CVF International Conference Computer Vision pp. 4743 2019.
Vishal Monga, Yuelong Li, and Yonina C Eldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. IEEE Signal Processing Magazine, 38-2):18-4,, 2021.
Christopher C Paige and Michael A Saunders. LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Transactions on Mathematical Software (TOMS), 8(1):43-71, 1982.
Jeong Joon Park, Peter Florence, Julian Straub, Richard Newcombe, and Steven Lovegrove. Deepsdf: Learning continuous signed distance functions for shape representation. In Proceed- ings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 165-174, 2019.
Bartolomeo Stellato, Goran Banjac, Paul Goulart, Alberto Bemporad, and Stephen Boyd. Osqp: An operator splitting solver for quadratic programs. Mathematical Programming Computation, 12 (4):637-672, 2020.
Po-Wei Wang, Priya L. Donti, Bryan Wilder, and Zico Kolter. SATNet: Bridging deep learning and logical reasoning using differentiable satisfiability solver. In ICML, 2019.
Juze Zhang. Ye Shi, Lan Xu, Jingyi Yu, and Jingya Wang. IKOL: Inverse kinematics optimization layer for 3D human pose and shape estimation via Gauss-Newton differentiation. arXiv preprint arXiv:2302.0000 01005 2023.
Qianggong Zhang, Yanyang Gu, Michalkiewiez Mateusz, Mahsa Baktashmotlagh, and Anders Eriksson. Implicitly defined layers in neural networks. arXiv preprint arXiv:2003.01822, 2020.
12

---

Published as a conference paper at ICLR 2023
Appendix
We present some details for the proposed Alf-Diff algorithm. including the framework of Alt-Diff, the derivation of some specific layers, the proof of theorems, detailed experimental results and im- plementation notes.
A FRAMEWORK OF ALT-DIFF
The Alt-Diff framework for optimization layers within an end-to-end learning architecture is illus- trated in Figure 3
Input
Optimization layer
forward
min
[x;; 8)
R
8.f.
A(o)s b(0)
G( S h(0)
Ox.
OR 3xx
backward
00
Alt-Diff
dual update
aA 29
Ohr 36
as
Yr 8#
3e
slack update
until convergence (ar truncation)
primal update
Figure 3: The model architecture of Alt-Diff for optimization layers.
B PRIMAL DIFFERENTIATION
B. INHERITANCE OF HESSIAN MATRIX
According to the first-order optimality condition in forward pass Sap. we have
V((T++1) Vf(zet1) + AT + GT us + P^ (Ax=11 - b) + p (GrR+1 + 8/: h) = 0.
(14)
Generally, the equation [4) can be efficiently solved by iterative methods such as Newton's 's methods as follows:
2 -g+1
V (2 (((T)+1
(15)
= = (2 + P A GC V(((T=1)
where oft denotes the value of .x+1 at the i-th Newton's 's iteration and a is the step size. Therefore, when 2t.1 converges at its optimal value Ik+1, i.e., after the forward pass, the inverse of Hessian (()+(()) -1 can be directly used to accelerate the computation of the backward pass (7a Especially, when f(x) quadratic, i.c. f(x) f inverse of Hessian becomes constant
3xPPx Px + g" Txx and P a symmetric matrix, the
13

---

Published as a conference paper at ICLR 2023
pG"
(16)
B.2 SPECIAL LAYERS
We take Quadratic Layer Amos & Kolter (201)), constrained Sparsemax Layer Malaviya et al. (2018) and constrained Softmax Layer Martins & Astudillo (2016) special cases order show the computation of backward pass (7) The details of these layers are provided in the first two columns of Table 3 The differentiation procedure (76) (7d) for these layers are exactly the same.
The only difference relies on the primal differentiation procedure
7a which is listed in the last
column of T
Table 3: The primal differentiation procedure of Alt-Diff for several optimization layers.
Layers
Opiamization problems
Primal differemtiaion 7a
Constrained Sparsemax Layer
min - v/ a.t. SSHSH
((2 2p)T + 1")
86
Qundratic Layer
min fz" Pxr + st. Gr GrSA
01++1
+P+ p p Emalzat))
(N)
Constrained Softmax Layer
min
x ((e) sd. 1.
Bree1
(dlag
+xx) + p1 11-111177 (aaltera)
In Table (xx( ==
a V 1 Aa, ux; P 0 in the Quadratic layer and H(x) =
09
Σ 2y log(2;) is the negative entropy in the constrained Softmax layer. We next give the detailed
derivation for the last column of Table 3
Proof. For the Quadratic layer and the contrained Sparsemax layer, we substitute Vf(x++1) =
PIR+1 + q into (14) and calculate the derivative with respect i.e.
p 0xR+1
0q
a
aG vs + p
OA (AxR+I b) OG (G + 88 h) 0.
+
+
00
80
00
00
00
00
(17)
Therefore we can derive the formulation of primal gradient update:
0Ik+1
(Qq
OA
0G in
0(ATb
CT((s h))
(P + *AAAAA pG
00
00
00
00 p
00
- - p
T A pG G) (ze(xe+1).
(18)
Compared with (6)), we can find that the forward pass and backward pass in quadratic layers shared the same Hessian matrix, which significantly reduces the computational complexity.
The constrained Sparsemax Layer is special quadratic layer that with sparse constraints, where P 21, A = 1" and G [-1, 1 Therefore the primal differentiation 7ap becomes
0 ((2+ 2p) pp 11" Lno((x+1)). 00
(19)
For constrained Softmax layer, the augmented Lagrange function is:
L = 1f st log + X (1T 1) + v(Gr + -
(20)
p | 1112 + ||Gr + -1ll?)
2
where G [| and h can be replaced by
00 u. Taking the gradient of the first-order optimality condition
0rk+1
01 X
TG vv
01(1" ætt1 1)
8G (Gx#+1 + h) = 0. (21)
diag
(x)
+
+ 00
00
00
00
00
14

---

Published as a conference paper at ICLR 2023
Similarly, the formulation of primal gradient update of the constrained Softmax layer is:
axx+1 diag (irag"((x= pG + + - p1.
@11x' du
0G
uu
0G (sx
h)
+
+
00
00
00
00
(22)
diag
((x) + + + pl. (zo(Ex+1).
we can see the implementation of primal differentiation for the constrained Sparsemax layers Malaviya et al. (2018) and the quadratic optimization layers Amos & Kolter (2017) are quite simple. The Jacobian matrix involved in the primal update keeps the same during the iteration.
From Table
C ERROR OF THE TRUNCATED ALT-DIFF
Theorem 4.1. (Error of gradient obtained by truncated Alt-Diff) Suppose 25 is the truncated solu- tion the k-th iteration, the error between the gradient azs obtained by the truncated Alt- and the real gradient 8g" is bounded as follows. 80
Ox"
|| s Cilla - =1'l,
(23)
00
00
La f12
2zL2 12
where C1
is a constant.
Proof.
In the differentiation procedure of Alt-Diff, we have primal update procedure (7)), so
that
Ork
Ox*
(n.o(("")
00
00
(xc Vo, e.0
(xw) V 2, 2.0((xx)
(2,0[(x') - vo,oL(0)))
(24)
(x*) - v2C (xx)) V Vzo((xx).
A2
By Assumption 8c
we can obtain that
ا [[ VLn. (xx)) S L3
xxll-
(25)
Since we have computed the closed form of the Hessian of augmented Lagrange function V (z + pA A pG G, by assumption 9 and Cauchy-Schwand Schwartz inequalities,
we have
|| IV (x") (xx)l
= | (xx) V=
< V (xx)) [V((((x)) - ve((x*) ((")
-
(26)
[+ -2/((m))
Therefore the difference of Jacobians is
drk
dr
= | (xx) Ao vz,o(IT'))
00
00
1
< 1
(xx) ||A||| +
V=.o(()))- - -3.((x)) (27)
L3
جلوو
<
10- - m4ll-
#12
51
15

---

Published as a conference paper at ICLR 2023
D ERROR OF THE GRADIENT OF LOSS FUNCTION
Corollary 4.2. (Error of the inexact gradient in terms of loss function) Followed by Theorem 4.1 the enror of the gradient w.r.t 0 in loss function R. is bounded as follows:
VVR xx) - vR(0;=")| & C2l1= - =x"11.
(28)
where C2 = T,1 paln + pa La
11
is a constant.
p
12
Proof. Firstly, optimization layer can be reformulated the following bilevel optimization prob- lems Ghadimi & Wang (0018:
min R(0;20 (0))
(29)
s.l. x² (0) arg min [z; 0), 2EC(0)
where R. denotes the loss function, therefore we can derive the following conclusions by Implicit Function Theorem. outer optimization problems, we have
d5
VR(0; = VgR +
(30)
00
Therefore,
A = VR(0;0N) - vR(0;x*)
VoR(O; - VOR(O;x*) + V=R(0;; Okk
Ox
V V=R(0;=")
(31)
00
00
A3
The second term is:
Ox*
A = V, V,((0;
R(((0x
00
00
0z
Ox
R(0;
V. ((;
00
00
Ox
Ox*
(32)
+ VoR(0:
VoR(0;x")
00
00
Ox
Ox
8x
V ((R(0) - Va v=R(0:x*)
+ (2R(0:0x))
00
00
00
Combining the results in 32.. assumption Sa and Theorem of truncated gradient with optimal gradients is
we can obtain that the differences
| VVR xx) VR xz Il
Ox
Osk
Ox
|| + ||s
+ + ((( xx)
00
00
00
La
+ 4332
(33)
Li 1 +
||:T - x=1|
+ l41
||
x II
112
1/2
112
(11
11
La
L2
| - x²
112
Therefore, the gradient of loss function R(0;za) shares the same order of error as the truncated solution Øik-
16

---

Published as a conference paper at ICLR 2023
E ALT-DIFF AND DIFFERENTIATING KKT
We first consider the gradient obtained by differentiating KKT conditions implicitly, and then show that it is the same as the result obtained by Alt-Diff.
E.1 DIFFERENTIATION OF KKT CONDITIONS
In convex optimization problem conditions:
I the optimal solution is implicitly defined by the following KKT
V + (T)) G* GT(())= =0
^(0)= - b0)
(34)
(()) h(0)) 0
where and y are the dual variables, diag(-) creates diagonal matrix from a vector. Suppose collects the optimal solutions 1 ,"",,, in order to obtain the derivative of the solution # w.r..
the parameters ((0). G(Ø), h(0), we need to calculate JF.e and Jy.p by differentiating KKT
conditions 34) follows Amos Kolter (2017); Agrawal al. 2019a): Zhang al. (2020):
(x*)
AT(0) 0 diag G(0) - (())
BT (0))
Fy
Jr: JF 1=
A(O) diag(v)G(()
0
(35a)
0
VJ
X
]
[FFA
JFib JFFG JFuh 1=
T (x+)T
-T
0
(35b)
diag A) @ (x*)T
-I
where (x)( (x)) & denotes the Kronecker product.
E.2 ILLUSTRATION EQUIVALENCE
In this section, we show the equivalence of the Jacobian obtained by differentiating KKT conditions and by Alt-Diff from the computational perspective. As we have shown in Theorem 4.1 this section further complement of the equivalence. Here we show that the results obtained by Alt-Diff is equal to differentiating KKT conditions. Note the alternating procedure of (5) is based on ADMM, which convergent for convex optimization problems. Assuming the optimal solutions by the alternating procedure of (5) are [rAN An Aau AA forward ADMM pass converges:
we can derive the following results after the
A = arg min L(x, Stles AAn VAKi 0),
*A1 RoLU (-1 -GGrān - h))
(36)
AA XA + p(Ax - b),
V vAn + p(Grān + SAn h).
Taking the derivative with respect to the parameters 0 in 36). the differentiation procedure 7 becomes 00
(FF + PAT A + PG G)
Lua (#Ai))
(37a)
0s
1
a(Gz - -h)
(37b)
00
P
a0
00
0(Ax) Alt b)
+
(37c)
00
00
20
Ov
aGGrAn
+ AA h)
(37d)
00
30
20
17

---

Published as a conference paper at ICLR 2023
Recall that the differentiation through KKT conditions the optimal solution [xt X3, 2/1 are as follows,
Or
O
0G
Fr (x
+
0,
(38a)
00
80
00
A(Ax* - b)
0,
(38b)
00
Ov (Gx - h) + 1/
OG h) 0.
(38c)
00
00
By the convergence of ADMM, is known that [x Alo Ane An is equal to [x", A*, v²). Since in
convex optimization problems, the KKT condition (34) and derivative (38) have unique solutions,
therefore we only need to show that 388 can be directly derived by (37).
33aa
38a
dr
(FE + PA A+ pG G)
00
OA
aGT
a(ATh
GT (s - -))
(39)
00
00
00
Therefore,
OEAA
OA
θGT
(F
00
00
00
Ox
0(A=
GO hb))
(PAT pG G)
(40)
00
00
O(A - -b))
O (Gx
+ 8A1l - 11))
00
00
Clearly, 40 is exactly the same as (38a).
37c
38b
By 37c we can obtain
0 ((Ar Anr b)
O,
(41)
00
which is exactly the same as 38b
33bb
and 37d
38c): By (37b) and (37d), we can obtain:
O(GrAn h)
as
00 -p
00
(42)
a(Gri -h)
sgn (s 1T
08
We discuss this issue in two situations. Since the equality Gæ + s h = 0 holds by optimality, we have (VAI sAn) = O using the complementary slackness condition.
If An.s 0, then VAn.
O, obtain
O(G,Iān h4)
O(G 1ain-ha h1))
sgn(sAn.))
1" о
+
00
80
00
(43)
@dvAn. 00
aGGr Alt hs))
o = -1-1²
00
Therefore,
0 and
30
Ovin.
a(G h1) 0.
(G - h4) + VAn.
(44)
08
00
18

---

Published as a conference paper at ICLR 2023
If Alt, 0, then G, h, and
a(G - -44) sgg(($An))
Quann + a(GGTAA h4))
1
P
00
00
(iVAn. 08
a(G ha)
(45)
10.1 1
00
0.
Therefore,
Vvana (G h4) VAn.i
a(GrrAn - h1) 0.
(46)
00
00
Therefore, 44 and
46
show
38c
holds.
F EXPERIMENTAL DETAILS
In this section, we give more simulation results as well as some implementation details.
F.1 ADDITIONAL NUMERICAL EXPERIMENTS
In constrained Sparsemax layer, the "Isqr" mode of CvxpyLayer is applied for fair comparison. The total running time of CvxpyLayer includes the canonicalization, forward and backward pass, retrieval and initialization. The comparison results are provided in Table Alt-Diff can obtain the competitive results OptNet and CvxpyLayer with lower executing time. The tolerances of the gradient are all set as 10 for OptNet, CvxpyLayer and Alt-Diff. Besides, we conduct experiments to compare the running time among Alt-Diff, OptNet and CvxpyLayer using different tolerances from 10-1 to 10 truncated operation will not significantly improve the computational speed for existing methods but does offer significant improvements for Alt-Diff, All the numerical experiments were executed times with the average times reported the results.
OptNet, CvxpyLayer and Alt-Diff. The results in Table 5 shows that the
Table 4: Comparison of running time (s) and cosine distances of gradients in constrained Sparsemax layers with tolerance 10-3
Small
Medium
Large
Large+
Num of variable n
3000
5000
10000
20000
Num of constraints ne
6000
10000
20000
40000
OptNet Forward
18.46
77.87
834.59
16.61
71.45
779.00
Backward
1.85
6.42
55.59
CvxpyLayer (total)
3.61
18.14
123.79
1024.69
Initialization
3.50
17.79
122.61
1020.41
Canonicalization
0.00
0.00
0.01
0.02
Forward
0.07
0.27
0.44
1.35
Backward
0.03
0.07
0.73
2.91
Alt-Diff (total)
3.16
9.96
58.51
539.19
Inversion
1.21
4.71
34.35
287.83
Forward and backward
1.95
5.25
24.15
251.36
Cos Dist.
0.999
0.998
0.997
0.998
represents that the solver cannot generate the gradients.
From Table 4 we can find that OptNet is much slower than CvxpyLayer in solving sparse Quadratic programmings. CvxpyLayer requires lot of time in the initialization procedure, but once the ini- tialization procedure completed, calling CvxpyLayer is very fast. However, Alt-Diff only needs to compute the inverse matrix once, significantly reducing the computational speed.
As special case for general convex objective functions, Di rj log(æ;), which is not a quadratic programming problem. Thus we can only compare Alt- Diff with CyxpyLayer. The constraints Ar b and Gr. < h randomly generated with dense
adopted f(z) --yr +
19

---

Published as a conference paper at ICLR 2023
Table 5: Comparison of running time (s) for constrained Sparsemax layers with 10000 and
ne = 20000 under different tolerances.
Tolerance 10
10
10-3
10 10-4
10-
OptNet
768.01
808.81
834.59
880.27
1026.85
LvxpyLayer
121.99
121.84
123.79
123.02
129.80
Alt-Diff
47.31
57.46
58.51
71.18
81.99
(5a is carried out by Newton's methods with the tolerance set as 10-1, The comparison of cosine distance and running time is in Table We can find that Alt-Diff significantly outperforms these cases especially for optimization problems with large size.
coefficients. Alt-Diff, each primal update 22+41
Table 6: Comparison of rumning time (s) and cosine distances of gradients in constrained Softmax layers. Since OptNet only works for quadratic optimization problems, thus cannot compare Alt- Diff with it for the constrained Softmax layers.
liny
small
medium
large
Num of ineq.
100
300
500
1000
Num of ineq. m
30
100
200
500
Num of eq. Elements
10
20
20
200
1.96 x 10
1.76 x 10
5.18 x 10
2.89 x 106
CvxpyLayer, total
0.11
0.97
2.09
9.67
Initialization Canonicalization
0.01
0.04
0.08
0.29
0.00
0.00
0.01
0.05
Forward
0.07
0.34
0.73
2.76
Backward
0.03
0.59
1.36
6.56
Alt-Diff, total
0.03
0.33
1.10
5.02
Cosine Dist.
0.999
0.996
0.999
0.999
"2" represents that the solver cannot generate the gradients.
F.2 IMAGE CLASSIFICATION
All neural networks are implemented using PyTorch with Adam optimizer Kingma & Ba (2014) We replaced layer optimization layer in the neural networks, and compared the running time and test accuracy in MNIST dataset using OptNet and Alt-Diff. The batch size is set as 64 and the learning rate is set as 10-3 We ran 30 epoches and provided the running time and test accuracy in Tabel 7 As we have shown that OptNet runs much faster than CvxpyLayer in dense quadratic layers, therefore we only compare Alt-Diff with OptNet.
Table 7: Comparison of OptNet and Alt-Diff MNIST with tolerance 10-3
models
Test accuracy (%)
Time per epoch (s)
OptNet
98.95 0.25
307.16 + 18.21
Alt-Diff
98.97 + 0.17
167.66 + 4.40
We used two convolutional layers followed by ReLU activation functions and max pooling for fea- ture extraction. After that, we added two fully connected layers with 200 and 10 neurons, both using the ReLU activation function. Among them, an optimization layer with an input of 200 dimensions and output of 200 dimensions is added. We set the dimension of the inequality and equality straints both as 50. Following similar settings in OptNet, we used the quadratic objective function f()) 1,x= Px + q" here, while taking g as the input of the optimization layer and the optimal x* as the output. Finally, the 10 neurons obtained by the fully connected layer were input into Softmax layer, and the nonnegative log likelihood was used the loss function here.
The experiment results are as follows, we can see Alt-Diff runs much faster and yields similar accuracy compared to OptNet.
20

---

Published as a conference paper at ICLR 2023
36"3
10"2
165.0
05
MCCUINCy PN
06.3
46.5
96.5
96.0
MNIST,
32.5
occurbiy
25.27
25.0
opoch
Figure 4: The training and testing performance of Alt-Diff and OptNet on MNIST.
Moreover, we show the training and testing performance of Alt-Diff and OptNet on MNIST in Figure g Obviously, Alt-Diff have similar performance under different tolerance values. Also, we can find that using a truncated threshold with low-accuracy in Alt-Diff will sacrifice much accuracy, further validating the truncated capability of Alt-Diff as claimed in Corollary 4.2
21


Reviews:
[{"review_id": "zYM_RuVugv", "reviewer": "Reviewer_apdv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes Alternating Differentiation for Optimization Layers (Alt-diff), a method for differentiation of parameterized optimization problems. Prior methods first solve the optimization problem on the forward pass using e.g. interior point methods, and then implicitly differentiate the KKT conditions on the backward pass by solving a linear system of equations.\n\nAlt-diff is based on instead using ADMM to solve the optimization problem on the forward pass by decoupling it into multiple subproblems, which are then solved in an iterative alternating fashion. The jacobian can then be computed simultaneously to the forward pass, by differentiating the subproblems in the same iterative alternating fashion as the forward computation. The main benefit from this new approach is a computational speedup due to the reduced complexity of implicitly differentiating the subproblems with a smaller KKT matrix, compared to directly differentiating the original problem.\n\nThe authors show that the backward pass enjoys quadratic complexity. They also show that the runtime can further be improved by truncating the iterative procedure. This gives a tradeoff between the error on the jacobian and the runtime, which is also theoretically analysed in the paper.\n\nThe proposed method is experimentally tested on multiple experiments, including a runtime analysis of optimization layers with randomly generated parameters, an energy scheduling problem in predict-then-optimize fashion, and an image classification task. The experiments show that the proposed method can often yield results of quality similar to state-of-the-art methods in less time.", "summary_of_the_review": "The idea of reducing the computational complexity of implicit differentiation by decomposing the optimization problem in an ADMM style is exciting.\nMy main concern is that the authors overstate the general superiority of the proposed method and do not highlight enough the importance of choosing an appropriate algorithm for the optimization problem at hand.\nIf the remaining issues regarding the presentation of the comparison to previous works are resolved, I believe this paper will be of great interest to the ICLR community.", "strength_and_weaknesses": "### Strengths:\n- The idea of using ADMM instead of competing methods to solve optimization problems in implicit layers is appealing, due to the simplicity, gneral applicability, and high parallelizability of ADMM.\n- The paper is overall well written and well structured.\n- The results are mostly convincing, with runtimes that are highly competitive with prior methods.\n\n### Weaknesses:\nWhile this paper proposes a method that brings clear advantages of ADMM to implicit layers, I believe that the claims of Alt-Diff being strictly better than previous methods are overstated.\n(Examples: \"Alt-Diff substantially decreases the dimensions of the Jacobian matrix and thus significantly increases the computational speed of implicit differentiation\",  \"comprehensive experiments demonstrate that Alt-Diff yields results comparable to the state-of-the-arts in far less time\")\n\nFirstly, the complexity analysis in Table 1 shows that in both prior methods and in Alt-Diff, the computation required for the backward pass is of the same order (or less) as the forward pass.  (Note that OptNet [1] even claims: \"The backward pass gradients can be computed “for free” after solving the original QP with this primal-dual interior point method, without an additional matrix factorization or solve.\")\n\nTherefore the backward pass computation is not necessarily the computational bottleneck. And for the forward pass, from the complexities in Table 1 it is by no means obvious that using ADMM (Alt-Diff) is always better than using e.g. an Interior Point Method (OptNet), as there is a strong dependence of the practical runtimes on the number of iterations M and T needed for convergence.\n\nThis is also evident in the experiments, as the results for the sparsemax layer in Table 4 show that Cvxpy is much faster than Alt-Diff when disregarding the initialization, which to my understanding only needs to be performed once in the training procedure, so Cvxpy has a clear advantage over Alt-Diff in this setup.\n\nIn my opinion the story of the paper should be adjusted to accurately reflect that Alt-Diff does not make previous methods obsolete, and instead is one promising option among others, and choosing the best one highly depends on the problem at hand.\n\n[1]: Brandon Amos and J Zico Kolter. Optnet: Differentiable optimization as a layer in neural networks. In International Conference on Machine Learning, pp. 136–145. PMLR, 2017.\n\n### Additional questions:\n- While I also believe that the idea of trading accuracy for runtime by truncation is very interesting, I do not think that this is inherent to ADMM and therefore could also be applied to speed up the competing methods. Have the authors tested increasing the tolerance to see if a similar speedup can be achieved?\n- It would be useful to split the reported computation time into forward and backward pass also for OptNet.\n- The results for OptNet are computed on a CPU, however, to my understanding OptNet was optimized for running on a GPU. This could potentially affect the runtime results. Have the authors attempted to run the experiments on a GPU?\n\n\n### Minor issues:\n- Equation 18, 19 (and text before): The computation misses the dependence on the parameter $q$. However, the final result in Equation 19 appears to be correct. A similar issue is in Equation 22, 23 with a missing dependence on $y$.\n- Equation 32: $A$ and $G$ transposed missing in third line.\n- Equation 35: First $\\rho$ should be removed from second line.\n- Equation 37: \"opt\" subscript is missing/missused.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IutOg9S6PU7", "reviewer": "Reviewer_kA5n", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "An optimization layer is a function that assigns to given parameters $\\theta$ the solution $x^*$ of an optimization problem $\\min_x f(x,\\theta)$ subject to constraints $x\\in C(\\theta)$. These layers are also implicit layers as $x^*$ is a solution of a certain implicitly defined function $\\cal F(x^*,\\theta)=0$. Under reasonable assumptions, these layers have analytical gradients $\\partial x^*/\\partial\\theta$, and they can be used in end-to-end trainable NN models. The aim is to study how to calculate the forward and backward passes of these layers efficiently.\n\nThe paper studies the alternating direction method of multipliers (ADMM) for convex optimization layers ($f$ is convex). On the forward pass, at every ADMM iteration, the primal and dual variables and their Jacobians are updated until convergence. The paper contains theoretical justification, complexity analysis and comparison to OptNet and Cvxpylayers (using the interior point method), and the performance is demonstrated and compared on a synthetic and two real-world datasets.", "summary_of_the_review": "The paper persuasively shows that differentiating ADMM leads to better runtimes in optimization layers where ADMM is the appropriate algorithm. If the authors address the abovementioned issues, the paper will be a valuable asset to the community.", "strength_and_weaknesses": "Strengths:\n- Approaches an important and difficult problem with a different viewpoint by using ADMM\n- Convincing evaluation showing performance improvement over SOTA in some cases\n- Well-written related work providing enough background to understand the paper\n\nWeaknesses:\n- As I understood the paper's message, it claims the supremacy of Alt-Diff over OptNet and cvxpylayer in all cases. However, this is overstated:\n\t- OptNet and cvxpylayers never compute the full Jacobian matrix on backward (as claimed in the abstract and also later in section 3). In fact, from how the forward is computed, the backward is \"for free\" (see the first line of 3.1.1. of OptNet paper), i.e. O(1). This is also true for Alt-Diff; there is, in fact, no backward pass. In any case, only the larger of the two (forward/backward) counts.\n\t- Hence, we are comparing $O(T(n+n_c)^3)$ of cvxpylayer (interior point method) to $O(Mn^3)$ of Alt-Diff (ADMM). What ultimately decides is the number of iterations $T$ and $M$. Therefore, one should use the method which is suitable for a given optimization problem: If the ADMM converges faster, Alt-Diff is the right method, and if the interior point method works better, cvxpylayer should be used.\n\t- 'Additional numerical experiments' in Appendix F.1 on sparse quadratic programs actually proves my point: cvxpylayer is 30x faster than Alt-diff since the initialization needs called only once.\n- Convergence analysis. It is evident from the experiments (Fig. 2a) that the gradient is correct. Unfortunately, I do not see how it follows from the proof of Theorem 4.2.\n\t- I do not understand where Lemma 4.1 is used. Also, why from all possible fixed point theorems, this particular one is quoted (for reflexive Banach spaces). The assumption should also be 1-Lipschitz (nonexpansive) mapping from a bounded closed convex set into itself.\n\t- Thm 4.2: The proof contains computations showing that differentiating optimality conditions of ADMM leads to the same analytical derivative as differentiating the KKT conditions (this seems to be more or less correct). Any proof that the convergence of values (guaranteed by the convergence of ADMM in the convex case) yields the convergence of derivatives is missing (referred as 'obvious'). In general, convergence (even uniform) of functions does not imply convergence of derivatives (see eg. https://en.wikipedia.org/wiki/Uniform_convergence#To_differentiability). It is not, in my opinion, obvious, and it should be clarified.\n\t- Theorems 4.3 and 4.4 present expected results under very strong assumptions with elementary estimates. However, in particular, estimate 11 proves the convergence of derivatives in this case.\n\nsugesstions, typos etc.:\n- eq. 6: is $s\\ge 0$ correct here?\n- Thm. 4.2: $\\partial x^*/\\partial\\theta$ denotes the true analytical Jacobian; there is no need to refer to cvxpy.\n- Algo. 1: The elements of the last iteration should be returned.\n- Tab. 1: Is $k$ correct here? ($=M$?)\n- Section 5.1 Matrix $P$ seems to be only defined later in the appendix.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3ZvTe0GzGW", "reviewer": "Reviewer_mj5g", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose Alt-Diff, a framework for differentiation of optimization layers in neural networks. The basic idea is to write down the augmented Lagrangian for the considered class of convex optimization problems with polyhedral constraints, derive associated ADMM updates in which objective and constraints are decoupled, and therefrom gradients of primal, slack and dual variables w.r.t. optimization parameters. The resulting recursive sequence of gradients is theoretically shown to converge (in terms of the number of ADMM iterations) towards the gradient obtainened by implicit differentiation. In addition, the authors provide a complexity analysis of the proposed method, theoretical upper bounds on the error in gradient computation introduced by truncation of the recursive scheme after a finite number of iterations, and numerical experiments.", "summary_of_the_review": "All in all, I think that this is a very good paper. The authors provide a tractable approach for the differentiation of optimization layers accompanied by a rigorous theoretical analysis, and the numerical results seem convincing to me. I would say that the above-mentioned weaknesses are rather mild, and the approach stands well for itself in comparison with existing approaches.", "strength_and_weaknesses": "Strengths:\n\nCompared to existing approaches that use implicit differentiation, namely OptNet and CvxpyLayer, the proposed framework needs no differentiation through KKT conditions which reduces the dimension of the required inverse Hessian by the number of constraints of the optimization problem. As a byproduct, the inverse Hessian for differentiation can be reused from the preceding ADMM update. This reduces the complexity of the backward pass from cubic to quadratic. Compared to unrolling, the proposed method does not require that intermediate iterates from the forward pass are stored for backpropagation as gradients are computed on the fly. The presented numerical results suggest that Alt-Diff yields state-of-the-art accuracy on benchmark problems while saving significant computational budget.\n\nWeaknesses:\n\nThe proposed approach still needs inverse Hessians. Through the decoupling of objective and constraints, the scalability in terms of the number of constraints is improved. On the other hand, if I see it correctly, the scalability in terms of the number of optimization variables is not better than in case of existing approaches. Moreover, the threshold $\\epsilon$ needed for the stopping criterion constitutes an additional tuning parameter which might not be obvious to choose in practice.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster