Learning-Augmented Algorithms for Online Linear and Semidefinite Programming
Authors: Elena Grigorescu
Young-San Lin
Sandeep Silwal
Maoyuan Song
Samson Zhou
Venue: NeurIPS 2022 Accept (2022)
Keywords: Learning-augmented Online Algorithms
Primal-dual
Covering Linear Programming
Covering Semidefinite Programming

Abstract: Semidefinite programming (SDP) is a unifying framework that generalizes both linear programming and quadratically-constrained  quadratic programming, while also yielding efficient solvers, both in theory and in practice. However, there exist known impossibility results for approximating the optimal solution when constraints for covering SDPs arrive in an online fashion. In this paper, we study online covering linear and semidefinite programs in which the algorithm is augmented with advice from a possibly erroneous predictor. We show that if the predictor is accurate, we can efficiently bypass these impossibility results and achieve a constant-factor approximation to the optimal solution, i.e., consistency. On the other hand, if the predictor is inaccurate, under some technical conditions, we achieve results that match both the classical optimal upper bounds and the tight lower bounds up to constant factors, i.e., robustness. 

More broadly, we introduce a framework that extends both (1) the online set cover problem augmented with machine-learning predictors, studied by Bamas, Maggiori, and Svensson (NeurIPS 2020), and (2) the online covering SDP problem, initiated by Elad, Kale, and Naor (ICALP 2016).  Specifically, we obtain general online learning-augmented algorithms for covering linear programs with fractional advice and constraints, and initiate the study of learning-augmented algorithms for covering SDP problems. 

Our techniques are based on the primal-dual framework of Buchbinder and Naor (Mathematics of Operations Research, 34, 2009) and can be further adjusted to handle constraints where the variables lie in a bounded region, i.e., box constraints. 

Learning-Augmented Algorithms for Online Linear and Semidefinite Programming
Elena Grigorescu" Purdue University, USA Llena-gopurdue.cem edu
Young-San Lin University of Melbourne, Australia nilnamuh@gmall com
Sandeep Silwal MIT, USA silwal@mit.com
Maoyuan Song Purdue University, USA
Samson Zhou
UC Berkeley and Rice University, USA samsonzhou@@mail.. com
song683@purdue.cem
Abstract
Semidefinite programming (SDP) is a unifying framework that generalizes both linear programming and mnndratically-contraiiin also yielding efficient solvers, both in theory and in practice. However, there exist known impossibility results for approximating the optimal solution when con- straints for covering SDPs arrive an online fashion. In this paper, we study online covering linear and semidefinite programs, in which the algorithm is augmented with advice from possibly erroneous predictor. We show that if the predictor is accurate, we can efficiently bypass these impossibility results and achieve a constant- factor approximation to the optimal solution, i.e., consistency. On the other hand, if the predictor is inaccurate, under some technical conditions, we achieve results that match both the classical optimal upper bounds and the tight lower bounds up constant factors, i.e., robustness.
quadratic programming, while
More broadly, introduce framework that extends both (1) the online set cover problem augmented with machine-learning predictors, studied by Bamas, Maggiori, and Svensson (NeurIPS 2020), and (2) the online covering SDP problem, initiated by Elad, Kale, and Naor (ICALP 2016). Specifically, we obtain general online learning- -aggeeted algorithms for covering linear programs with fractional advice and constraints, and initiate the study of Barning--augmentr algorithms for covering SDP problems. Our techniques based the primal-dual framework of Buchbinder and Naor (Mathematics of Operations Research, 34, 2009) and can be further adjusted handle constraints where the variables lie in bounded region, i.c., box constraints.
1 Introduction
In the classical online model, an input is iteratively given to an algorithm that must make irrevocable decisions each point in time, while satisfying number of changing constraints and optimizing
*E.G, Y.I., and M.S were supported in part by NSF CCF-1910659, NSF CCF-1910411, NSF CCF-2228814, and a Ross-Lynn Award.
1 Work done while at Purdue University, USA.
1 'Supported by NSF Graduate Research Fellowship under Grant No. 1745302, NSF TRIPODS program (award DMS-2022448), and Simons Investigator Award.
Supported in part by NSF CCF-2127806
Work supported by Simons Investigator Award and by the National Science Foundation under Grant No. CCF-18 1OFF-1818844 (855400, and done in part while at Cameegce Mellon University, USA.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

fixed predetermined objective. A common metric for evaluating the quality of an online algorithm the competitive ratio, which is the ratio between the "cost" of the algorithm and the best cost in hindsight, i.e., that of an optimal offline algorithm given the entire input sequence in advance. In the context of the minimization problems we study in this paper, an online algorithm e-competitive if its cost is at most multiplicative factor more than the cost of the optimal solution. Due to the irrevocable decisions, the changing constraints, or the number of possible different worst-case inputs, many online algorithms have undesirable competitive ratios that are impossible to improve upon without additional assumptions, e.g. [AAA +09).
Due to advances in the predictive ability of machine learning models, natural approach to overcome these computational barriers is to incorporate models with predictions, e.g., models that predict outcomes based on historical data. Unfortunately. due to the lack of provable worst-case guarantees, these predictions can be embarrassingly inaccurate when attempting to generalize to unfamiliar inputs, as shown in (SZS-14) 14), or simply not even satisfy the given constraints [BMS20). Thus, rather than blindly following an erroneous machine learning predictor, recent focus has shifted to studying algorithms that use the output of these models as advice, and guarantee good competitive ratios both when the predictions are accurate, i.e., consistency, and when the predictions are poor, i.e., robustness.
Recently, MBS20] studied the learning- aurrring-uggenneed online set cover problem and related problems, using their linear programming (LP) formulation to incorporate additional advice through a primal- dual approach. One drawback of their seminal work, however, is that they assume both integral constraints, as well as integral advice, which restricts the modeling capabilities of the framework; it is natural to ask how an online algorithm can be improved when the advice is given in terms of probability distribution or some other meaningful fractional values. For example, for the online set cover problem, fractional advice can indicate how likely a set should be chosen instead of the binary decision of whether a set should be chosen or not; for the ski rental problem, the advice can be presented as probability distribution over the total number of vacation days; in online network connectivity problems, the advice can indicate how likely an edge should be chosen.
In addition, linear programs cannot handle quadratic constraints and thus often fail to capture important aspects of fundamental optimization problems, which motivates the study of more general programs, such as semidefinite programming (SDP). SDP is a unifying framework that generalizes both linear programs and quadratically constrained quadratic programming (QCQP), while also yielding very efficient solvers, both in theory and in practice [VB96].
Before stating our contributions, we introduce some notation. For a -agmentd problem, are given a confidence parameter À E [0, IJ. where lower values of À denote higher confidence in the advice, and higher values denote lower confidence. An advice is a suggested solution for the online problem that is given. In the context of optimization problems including linear and semidefinite programming. a solution is a vector consisting of real numbers. We denote APX as the objective value of the online solution obtained by an online algorithm and compare it with (1) the objective value of the advice, denoted as ADV, and (2) the objective value of the offline optimal solution, denoted as OPT. The consistency and robustness of an online algorithm or solution for a minimization optimization problem are defined as follows.
Definition 1.1. An online solution with objective value APX is C(A))-oonsistent if APX < C(A)ADV. An online algorithm is
if it outputs a C(A)-consistent solution for C¹: [0, 1] + R21-
Definition 1.2. An online solution with objective value APX is R(A)-robust if APX < R(A)OPT. An online algorithm is R(A)-robust if it generates an
solution. Here, R: [0, 1] + Izz1-
If an advice is accurate and we trust it, then we would like the solution to be close to the optimal, so ideally C(A) - 1 as x - O. On the other hand, having À being close to denotes no trust in the advice, so R(1) should be close to the optimal competitive ratio of the best pure online algorithm.
1.1 Background and Contributions
We give a general paradigm for designing learning- sremiing-uugmented algorithms for online covering linear programming (BN09b), which generalizes the set cover problem (BMS20), as well as online covering semidefinite programming (EKN16), with possibly non-integral constraints and advice. Specifi- cally, we present primal-duul learning-augmentter (PDLA) algorithms for these problems, whose performance is close to the optimal offline solution when the advice is accurate, and also whose performance is asymptotically close to the optimal oblivious algorithm, if the advice is inaccurate.

---

Because of space constraints, we defer further discussions, additional related work, full algorithms, formal statements of theorems, and all the proofs the full version of the paper.
Our PDLA algorithms consider the advice while approximately minimizing the objective value when the input arrives online. Our unifying paradigm applies to both online covering linear programs (LPP and online covering semidefinite programs (SDP) described below.
Online covering linear programs. A covering LP is defined follows:
minimize c² x over x E R22o subject to Az 2 1.
(I)
Here, E Rg consists of m covering constraints, is a vector of all ones, and E IR50 denotes the positive coefficients of the linear cost function. In the online covering problem, the cost vector e given offline, and each of these covering constraints (rows) presented one by one in an online fashion, that is, m can be unknown. The goal is to update x in a non-decreasing manner such that all the covering constraints are satisfied and the objective value c² x approximately minimized.
The Oloog n) competiiive algorithm for online covering LPs presented in [BN09b] simultaneously solves both the primal covering LP ①1 and the dual packing LP (2). defined as follows:
maximize 1 1"y y over y E 12 subject to A" S
(2)
The analysis in [BN99] crucially uses LP-duality and strong connections between the two solutions to argue that they are both nearly optimal. The covering solution r is exponential function of the packing solution y and both x and y are monotonically increasing. The problem naturally extends to the setting that relies a separation oracle to retrieve unsatisfied covering constraint where the number of constraints can be unbounded. However, as the framework in (BN09b) fixes all violating constraints, each arriving constraint might be slightly violated so that each individual fix may require a diminishingly small adjustment. Consequently, the algorithm may have to address exponentially many constraints. The framework was later modified in [GLQ2T] which guarantees that addressing polynomially many constraints suffices.
In the Cearning-augmentte problem, are given confidence parameter À E [0, 1] and x' R" served fractional advice for LP ( However, we do not have guarantees about the advice x'. More specifically, the objective value of the advice c x' could be a horrendous approximation to the optimal objective value of LP II or x' might not even satisfy the constraints.
We first show an efficient, consistent, and robust PDLA algorithm for the online covering LPP (T). We use the condition number k to denote the upper bound for the ratio between the maximum positive entry and the minimum positive entry for each fixed column of A. For ease of presentation, we assume that x' is feasible, i.c., there are violating constraints caused by the advice x'.
Theorem 1.3 (Informal). Given a feasible advice x' E for LP
① with confidence parameter -consistent and O (log * -robust online algorithm for the online
A E [0, 11, there exists an O covering LP problem that encounters polynomially many violating constraints.
The formal version of Theorem 1.3 (see full version GLS+22al also addresses the case when x' is infeasible for LP (T. We note that Theorem I.3 implies that when λ poly(n). the algorithm is log(n/A)-robbls
Online covering semidefinite programs. We generalize our approach for learning- augmented covering LPs to handle a more expressive family of optimization problems, namely, covering semidefinite programs. First, we introduce some standard notation. A matrix A Rdxd is said to be positive semidefinite (PSD), i.e., A ž 0, if ot Au 2 0 for every vector v E Rdd, or equivalently, all the eigenvalues of A are non-negative. If A is PSD and symmetric, then is symmetric positive semidefinite (SPSD). A partial order over SPSD matrices in Rdxd can be induced such that A > B if B > 0. The setting of covering SDP problem is as follows.
and only if
minimize cT over E 12 subject to Σ A
(3)
where An E Rdxd and B E Rdxd are SPSD matrices and e E RR-0-
In the online covering SDP problem introduced in [EKN16], we have the matrices AI,..., A, and the cost vector given offline. In each round i [m] where can be unknown, we given new
3

---

SPSD matrix B(*) satisfying B(*) = B(i-1), The goal is to cover B(x) using a linear combination Ii...., In of the matrices , An. so that Ej=1 2jA, - Búd, while minimizing the cost cf x. Moreover, we must update x in a non-decreasing manner, so that once some amount of the matrix Aj used in the covering at round then it must be used in all subsequent coverings in later rounds. The online covering SDP problem and its dual in round i are as follows:
n
minimize et over 2 Ro subject to
Σ
Ajz = B B
(4)
j=1
maximize B(0) Y over Y subject Y Sg
(5)
where A& B., = trace (A"B) is the Frobenius product.
We remark that the formulation of online covering SDP generalizes online covering LP ① when the constraint matrix is known offline but there is no guarantee which covering constraint (row) will arrive. In particular, the SDP formulation for online set cover with n sets and d elements all given offline (but without the knowledge of which elements arrive and their order) is the following: we define matrices ....... A., {0, 13 jdxd where Aj is a diagonal matrix whose diagonal is simply the indicator vector for the j-th set across the d elements, i.e., entry (k,, k) of Aj is 1 if and only if set contains element k. The matrices (8) encode the variables that must be covered in round i, so that B0) is the all zeros matrix and ( - B is the all-zeros matrix except with a single one in entry (k, k) for the variable k that must be newly covered in round i. Thus no online SDP algorithm can achieve competitive ratio o(ogg n) because even if fractional sets are allowed, no online algorithm can achieve competitive ratio better than Olog for the online set cover problem [BN09a].
An optimal (loo n)) coompeiitive online algorithm for covering SDPs was presented in [EKN16]. Similar to online covering LPs, an important idea in this line of work is to use weak duality and the strong connections between the primal and the dual solutions. Observe that if x and Y are feasible
solutions for the primal and the dual, then c. 2 (A= & Y)z, (}=,(A,a)) @ Y 2
B < Y, and hence the primal and the dual satisfy weak duality.
In the x' E RS that serves advice. We have no guarantees about the advice, the objective value of the advice ct z' could be a terrible approximation or x' might not even be feasible.
problem, we are given a confidence parameter E [o, 1] and a vector
We use & to denote the ratio of the largest positive eigenvalue to the smallest positive eigenvalue of the matrices AI,..., An, BQ),.., B(m) and achieve the following. Theorem 1.4 (Informal). Given a feasible advice x' E ER2o for SDP (4) with confidence parameter A E [0, there exists a polynomial time, O (1-x) consistent, and O (log Ku) X -robust online algorithm for the online covering SDP problem.
The formal version of Theorem 1.4 also addresses the case when x' is infeasible for SDP (4). It implies that we can achieve a constant factor approximation to the optimal solution when the advice is accurate (0(1) comppetiii), which breaks the known 2(log n) competitive ratio obtained by the oblivious online algorithm for covering SDP in [EKN16]. Moreover, for k = poly(n), we match the optimal approximation ratio of Ollog n) up to constants when the advice is arbitrarily bad.
Adding box constraints. In both the LP and SDP case, is natural to have the requirement that the variables must lie in a bounded region. We extend our results for both online covering IPss and online covering SDPs to this case where each coordinate Z, of the variable vector x is required to lie in the interval [0, u,]. We achieve qualitatively similar consistency and robustness trade-off's as before which are summarized in Table [ Instead of k, a sparsity term s now appears in the robustness portion of the competitive ratio. In the LP case for set cover, s exactly captures the row sparsity (i.e.. the maximum number of non-zero entries of any row).
Theoretical applications. We emphasize that our framework uses continuous approach that is amenable to other learning-augmento optimization problems and supports fractional advice, which may be interpreted as probabilities. For example, as in [KKN66/AW02 W WX06), our framework for covering SDPs may be applied to the quantum hypergraph covering problem. In the full version paper [LS++22 22a), we apply our PDLA algorithm for covering LPs with box constraints in order to

---

Paper
Problem
Approximation Guarantee
Approach
with and without
continuous
BN09a
online covering LP
box constraints:
guess-and bess-and-double
(log n) -t-ompettiiive
without box constraints:
continuous
Olog ccoompettievee
6KNI6
online covering SDP
guess aad--ndd-ouul double
with box constraints:
efficient updating
Ollog -compettitvve
without box constraints:
ieamnin-auggmntted online set cover
BMS20
( 2) -C-oosisstt
discretized
O (log(d/A))-robux
continuous
without constraints:
GLQ21
online covering LP
guess-and-double
Ollog n) competttiveee
efficient updating
without box constraints:
O A))-consistent
Icarning augmented
continuous guess-and-dool efficient updating
(log((m//) (amm/A))/ -robuuttst
This Work
online covering LP and SDP with fractional advice
with box constraints:
( 2)) -coosisstt
((lo((/AA))-rr
Table 1: Summary of the competitive, consistency, and robustness ratios. We assume that the advice feasible for the srmning-augmented problems. Here, n refers to the number of sets or variables, A [0, 1] refers the confidence parameter, refers to the condition number, d refers to sparsity, and refers to sparsity. We note that online covering LP with box constraints generalizes online set cover with s d. In [EKNI6], the guess-and-double scheme not used for online SDP covering with box constraints.
obtain online algorithms for: (1) the fractional online cover problem with fractional advice, and for (2) the online group Steiner tree problem on trees, where min-cut algorithm is used as separation oracle retrieve violating constraints. Our learning-augmented solver for the group Steiner problem on trees can be employed as a black-box for other related problems, including group Steiner tree on general graphs, multicast problem on trees, and the non non-metric facility location problem [AAA [06.
1.2 Subsequent developments
Subsequent to work, significantly simpler algorithm with tighter qualitative guarantees was brought to our attention by Roie Levin. We describe the algorithm in the full version of the paper |LS 22b) with his permission. Nevertheless, we expect that the techniques and analysis that introduce this paper may be independent interest for other related problems or settings, such as the advice being adaptive, in settings of multiple experts. We believe that understanding the full power of the techniques developed in this paper is an intriguing direction for further research in the still emerging of maaning-auggmett algorithms.
1.3 Overview of our Techniques
We now give technical overview of our algorithms and describe how both our algorithms for covering LPs and SDPs are guided by several common underlying principles.
Previous approaches. A natural starting point would be the PDLA algorithm for online set cover by [BMS20], who adapted the primal-dual approach in [BN09a] incorporate external advice. We recall that in the covering LP formulation of the online set cover problem, each row denotes an element and each column denotes a set. The constraint matrix has entries that are either 0 1. An entry is 1 if and only if the element (row) belongs to the set (column). Additionally, for the online set cover problem considered [BMS20) each set either included the advice or not, i.e., each coordinate of the suggested indicator vector for the set selection is either 1 or O. While it seems plausible that one could extend the discretized approach of (BMS20) handle general coefficients in the constraint matrix, i.c., the online covering LP problem, is unclear how the growth rates of
5

---

For each update, while there exists a violating constraint:
1. Determine violating constraint.
2. Acquire "growth rate" for each variable depending on its coefficient in the violating constraint, the corresponding cost, and the advice.
Use a guess-and-doubbe approach to determine how fast each of the variables are increased by their growth rates.
4. Increase the variables continuously until the constraint is satisfied.
Figure 1: Summary of our framework
the variables can be adjusted to guarantee dual feasibility. This is because the positive coefficients in every covering constraint (all with value 1) are bulanced in the online set cover problem, which turns out to be a crucial ingredient to argue dual feasibility by the discretized approach, but we do not have this guarantee for general covering LPs with arbitrary positive coefficients. Instead, we use a different framework inspired by the classical online algorithm literature, e.g.. (BN09b[EKNIO) We present a summary of our framework in Figure | and describe it in more details below.
Continuous updates. Each time a new constraint arrives, we continuously increase the variables until the constraint satisfied. We adjust this growth rate of each variable based on its cost in the objective linear function, its coefficient in the arriving constraint, and the advice: variable is increased at slower rate if its cost is more expensive. its coefficient in the constraint has smaller value, or it is less recommended by the predictor. The introduction of fractional values in the advice is the main technical obstacle in our setting. In particular, our algorithm must behave differently in the case where a variable has not reached the fractional value recommended by the advice compared to the case where it has reached the recommended value, but the solution does not satisfy all constraints. By contrast, in the integral advice setting of (BMS20), the recommendation value always coincides with the limit at 1. To this end, once the variable reaches the recommended value, our algorithms judiciously decelerate the growth of the variable.
-ueusennd-doubee However, by allowing the coefficients of the constraint matrix be arbitrary, the optimal objective value OPT can be arbitrary and we need a nice estimate for this. Thus, we adopt the guess-and-doose
where the algorithm is executed in phases, so that in each phase we propose a lower-bound estimate of OPT, and the algorithm enters the next phase when the value exceeds our estimate. Note that such techniques are not necessary for BMS20), as their assumption of coefficients in {0, 1} implicitly provided bounds on OPT.
technique, e.g.. [B EEKN6GGL.22
Efficient updating. In more general applications, each arriving update may induce a large or even infinite number of constraints, such as an infinite number of directions induced by an SDP constraint. But now we sequentially choose a violating constraint and satisfy the constraint exactly as in [BMS20), then there is no guarantee that we will satisfy all the constraints in a small number of iterations. Thus, another technique we adopt to ensure efficiency in conjunction with the guess-and double technique is to satisfy each arriving constraint by factor of 2. That is, we instead continue to increment the primal variables until the violating constraint satisfied by a factor of 2, which ensures that at least one primal variable is doubled, which also implies polynomial upper bound on the number of violating constraints that must be considered.
Showing robustness and consistency. With the introduction of general coefficients within many components of our LP formulation, the robustness analysis in [BMS20) is no longer applicable, so instead we adapt the primal-dual analysis in (BN095) for general covering LP problems. In particular, we deal with the general coefficients via a delicate telescoping argument for dual feasibility, since we tune and change the growth rates multiple times even within the same phase. Towards obtaining the consistency bound, we partition the growth rate based on whether the variable has exceeded the value in the advice, and argue that the growth rate not credited to the advice is at most a certain factor of the growth rate credited to the advice, similar to the line of the argument presented in [BMS200.
Extending to online covering SDPs with advice. We now have arriving matrices rather than arriving elements, so that at each time we need to cover a new PSD matrix B that can be larger than the previous PSD matrix B ((--1) in an infinite number of directions. We repeatedly look at the direction with the largest mass that needs to be covered, i.c., the largest eigenvector of B(t) EE= Azzy.

---

Then to cover the direction v, we set the growth rate of the coefficient of each matrix A, proportional to the amount that the matrix aligns with v, i.c., proportional to v" A Aj & V. where V = ve" and is the Frobenius product. Unfortunately, it does not suffice to cover alone there may be many other directions for which B شラー Ajzı is not covered. However, as we satisfy the violating constraint by a factor of 2, the amount of vectors we have to cover is similarly upper- -opur-bounded as in the aforementioned approach for the online covering LP problem. Lastly, we remark that our unifying framework can be naturally applied to any online problem that has covering LP or SDP formulation, equipped with a fractional advice and a confidence parameter.
2 PDLA Algorithms for Online Covering LPs and SDPs
We describe our PDLA algorithms for online covering LPs and SDPs and sketch the proof for their guarantees. For covering LPs (I). we have A E R250 with m covering constraints, 1 is vector of all ones, and с 185, denotes the positive coefficients of the cost function. We use A, denote row i of A and ag to denote the entries of A, and C to denote the j-th entry of c. For the covering SDP 4 we have SPSD matrices Aj 's and "O's. For both covering LPs and SDPs, the covering constraints arrive online and e is given offline. The goal is to update x a non-decreasing manner such that is feasible and the objective of x is minimized. We are given an advice x' E BR2
We use a and--dubde approach. The algorithms work in phases. Let OPT be the optimal objective value of LP (I) or SDP (4). We estimate a lower bound a(r) for OPT in phase r. In
phase 1, let (1) & minzejn] /e/////a/a /ai;} be a proper lower bound for OPT in LP ① (a(1) + minge[n) fcy ( trace( (A,)] in SDP 4). For each subsequent phase, a(r + 1) < (r(r).
In the beginning of phase r, o <- min(a', (((r)((2n)))) xf S (2ncg) then it is possible that (2nc)) is large, so we have to set jr (r) = s'j to ensure consistency. On the other hand, if 5 2 (2n))) then it is possible that a' is large and the advice is bad, so we have to set = =2(r)/22nc)) to ensure robustness.
Whenever we have new constraint i in LP (I. introduce a new dual variable y < 0. For SDP 4 the dual variable Y is reset to zero matrix in a new phase. Once the online objective in phase r exceeds a(r), we proceed to the next phase + 1 from the current constraint (let us call it constraint 4y41, in particular, 41 = 1). The purpose of (<r) is to accelerate the growth rate of each variable x ( so that violating constraint can be quickly covered without incurring a high cost for the objectíve. For a violating constraint i, the growth rate of each variable z/") is then scaled proportional to a,j for covering LPs (A, @ V for covering SDPs) and inversely proportional to cj. so that the variables that are more aligned with the violating constraint in the LP (implicit violating linear constraint induced by V in the SDP) are valued more and the variables that are more expensive are valued less. If the advice does not adequately cover constraint i, then we increase each variable according to its growth rate until the (implicit) constraint is satisfied by a factor of 2. Otherwise the advice covers constraint i, then before we increase each variable, we further adjust the growth rate of each variable based on a combination of the suggested weight by the advice and our confidence in the advice. Here
we use an indicator function where Lece = 1ff x < x²) otherwise 1 1,), = 0. It should be 2
noted that since z must be updated in a non-decreasing manner, the algorithm maintains ( ]e([)) which denotes the value of each variable v, from phase to phase r, and the value of each variable
Ij is set to max (z) }. We defer the phase scheme to the full version paper GLS + 22a). We describe the continuous primal-dual approach in phase r and round i in Algorithiss and 2 We note that the dual variables are used as the proxy to increase the primal variables. The increment functions are exponential so that the primal variables are increased in terms of their growth rates. The coefficients Bj and D, are used to match the boundary conditions.
We remark that although we would like to increase the variables in a continuous fashion, we can nevertheless implement our algorithm in discrete manner for any desired precision by using binary search. For covering I. LPss the approach of satisfying each arriving violating constraint by a factor of 2 guarantees that the number of iterations is polynomially upper-bounded. This implies efficient
7

---

applications on problems that generate covering LPs with exponentially many or unbounded number of constraints, where violating constraints are retrieved by a separation oracle.
Proof Sketch for Theorem 1.3, We analyze Algorithm 1 Let P(r) = c x and D(r) = 1 be the primal covering and the dual packing objective in phase r, respectively. To show robustness, show that the following claims are satisfied: (1) x is feasible for LP ① (2) for each, cach,fnished phase
r, a(r) I (r(r), (3) y/O (log x is feasible for LP 22. and (4) the covering objective satisfies FFx: x S 2x(("), where r' is the last phase.
Claim (1) follows by the termination condition at line 9 and the phase scheme. Claim (2) follows by taking the partial derivatives of the increment function and analyzing the accumulative primal objective value. Claim (3) follows by a careful telescoping argument. Claim (4) follows by observing that the sum of the objective value of all phases does not exceed 2a(r") where r' is the last phase.
We can then deduce that cxxx < ((1)a(r') < ((I)((r') I O (log 2m) OPT where the first inequality follows by claim (4), the second inequality follows by claim (2), and the last inequality follows by claim (3) and weak duality, i.e., the objective value of any feasible packing solution for I.P 2 upper-bounded by OPT.
To show consistency, upon the arrival of constraint i in phase r, increment (r)r) in terms of y and decompose P(r) into two parts: P.. the contribution from the advice, and Pa. the contribution from the online algorithm. The increase of P(r) is also decomposed, i... aP(r) aP. PP, We initialize P. to non-negative value and P. = 0 in the beginning of phase show that aP.
dy. .y: By. 2+A OP2 and
.y. < T-X dy.
ultimately conclude that P(r) Pc + Pa < 0 { Since the algorithm increments xx() until the violating constraint is satisfied by a factor of 2, the growth of (+() is sufficient so that we only have polynomially many constraints to address.
Proof Sketch for Theorem 1.4. We analyze Algorithm 2 The proof is analogous to the proof of Theorem 1.3 The difference is that now we have ((r) = g @ Y. In the third claim of the proof robustness, we instead show that Y/O (log en) is feasible for SDP (5). For consistency, we X increment (r(r) in terms of Y, where the increase of Y is 8V for ā = 0 in the beginning. Here we increment 8 and consider the derivatives of P(r), namely Pc. and Pa w.r.t. ō instead of yi-
Algorithm 1 PDLA Online Covering LP Algorithm 2 PDLA Online Covering SDP
1: for each j E [n] do if Apx' 1 then
1:
while ΣØ=1 A,o, x B(9)
2:
2: Find SPSD matrix V: (A ( oV,
(1 (1-1)/22
3:
D3 x.
3:
for cach j [n] do
ΣT- m2 20
4:
if Σ A&t 2 B(S) then
4: else
(1- (t) Mtec B
5:
D₂ A&I
5:
D3 Ixm AL&V
AB
6:
y t kumi akjuk-
EF- (0) A
6:
else
7:
By + exp (xp((r)) +
7:
D, + ΣE= ALSV.
pligg
8:
if (r < 1 then while (rz(t) do
8:
Bj +- exp 4,
9:
10: for each [n] do
9:
while ΣE=1 Asal @ V
2 @ do
Increase J/ continuously.
10:
for each j E [m] do
Increase 2/7 simultancously by 11:
Set 8 0 and increase it continuously.
12:
Increase Y by continuously adding Vg to Y.
1) azjy4
2/
B, exp
D,.
13:
Increase 2/71 simultaneously by
Cj
A, 2 Y 6
By exp
D,-
13:
if any x. reaches x², then Break and go to line
14:
14:
if any x/ reaches x' then Break and go to line 3
15:
8

---

3 Empirical Evaluations
We demonstrate the upplicabilitt of our algorithmic framework on a synthetic and real datasets. Our focus will be on online covering algorithms with fractional hints and entries. We focus on this setting since it is the simplest of our algorithms and already captures key points of the overall framework. Note that prior work [BMS20) has already demonstrated the empirical benefit of Sarning-hasee methods for online covering with integral hints/constraints, albeit on synthetic datasets.
Datasets. For our synthetic dataset, the constraint matrix A represents a n X n matrix where each entry is uniformly in {0, } and whose rows arrive online. We set n 500. The objective function e is scaled vector with entries uniform in [0, I]. Our graph dataset is constructed as follows. We have a sequence of nine (unweighted) graphs which represents an internet router network sampled across time [LK14] LKFOS The graphs have approximately n ~ 10 nodes and m ~ 2.2 10 edges. We note that the nodes of the graphs are labeled and the labeling is consistent throughout the different time stamps. Each graph defines an instance of the set cover problem derived from the standard vertex cover to set cover reduction [Kar The objective funetion e will be the same as the synthetic case so our problem represents an instance of weighted vertex cover. All experiments are done in 2021 M1 Macbook Pro with 32 gigabytes of RAM and implemented in Python 3.9.
Predictions. First we describe predictions for the synthetic dataset. We consider 2 types of predictions: (I) first find the optimal offline solution by solving the full linear program and then noisily corrupt the entries of x by setting the entries to be 0 independently with probab. p. This is the same prediction used in [BMS20] which is referred as 'replacement rate' strategy. (2): the motivation of these predictions is the following: we are solving many related problem instances. To mimic this, we have matrices Ag, AI.... where each index represents a new problem instance. Ao is our synthetic matrix and Ai+1 updates A; by flipping n entries at random. We fix e to be the same. The predictions for all instances i 2 are given by the optimal offline solution generated from the first instance Ag. This "batch" experimental design naturally models the scenario where the current problem instance is similar to past instances and so one can hope to utilize past learned information. A similar style of predictions, although not in online context, has been employed in [CEI+ + 22 EFS 22 DIIL +1 CSVZ22). For our graph dataset, we first solve the set cover instance on the 1st graph in the family using an offline algorithm. We then the solution from the 1st graph as the hint for all subsequent graphs. We also noisy alter this hint for one of our experiments using the replacement rate strategy. Note that the set of vertices might vary across graphs. In this case, set the corresponding entry in the hint vector to be O.
Results. Figure 2 shows the results on the synthetic dataset while Figure 3 refers to our graph dataset. First, Figure 2a considers a single online instance of the synthetic dataset. Our prediction is the offline optimal solution. It shows smooth trade-off in the competitive ratio the parameter À ranges from (full trust in the predictions) to (no hints), as predicted by our theoretical bounds. Since the instance is random, we plot the average of 20 trials for each setting of À and show standard deviation. The plot validates the consistency of our algorithms as the competitive ratio is a factor of 2 lower with accurate predictions. In contrast, Figure 2b validates the robustness of our algorithm. There we consider the "replacement rate" strategy and randomly zero out the entries of the prediction (which is again the offline optimum) independently. The expected fraction of entries in the hint vector being set to zero is denoted as the corruption rate and is shown in the aaiiss. We see that for a fixed setting of X, such as X= = 0.1, our algorithm performs much better with hints than without when the corruption factor is low. However, as we increase the corruption, the performance of the algorithm degrades. Crucially, the performance does not degrade arbitrarily worse compared to X = 1 (no hints) performance and our algorithm with hints is able to outperform the baseline up to a high corruption factor. In Figure 2c we consider a "batch" experimental design for our synthetic dataset with 20 time steps. The green curve shows the competitive ratio without using any hints, i.c., À = 1 (the bascline). The orange curve shows the competitive ratio across the varying instances when we use batch prediction. The blue curve showcases more powerful predictions where the offline optimal of time step is used as the hint for time step f. We display the average values across 20 instances. As the time step increases, the orange curve drifts upwards, which is intuitive as the problem instances are increasingly different. Nevertheless, the batch hint stays valid for many time steps. As expected, the blue curve consistently has the lowest competitive ratio as the hints are also updated.
Graphs can be accessed in https: http:://sappp....sate
h.mml

---

10
10
1.1.1
8.0
A=1
7.5
Compattiov ledto
Ra55
8
Compota
Onlne Predicttors
Prodictions
5.5
5.0
4.5
0,2
(a)
(b)
(c)
Figure 2: Figures for our synthetic dataset.
Compattion Betto
2.45
2.0
2.35
2.30
1.4
Onine hredctions Batch Predictions
2.20
0.1
0.2
0.3
0.4
0.5
0.6
0.7
Graph
Cumpption Fractimn
(a)
(b)
Figure 3: Figures for our time-varying graph dataset.
We now describe results represents not using any hints (baseline) while the orange curve shows the competitive ratio as we vary the graph instance while using the hint derived from graph #1 (A is set to 0.1). It is shown that the hints help outperform the baseline and in addition, the hints stay accurate even the structure of graph #9 has drifted away from that of graph #1. The online predictions, shown in blue, does marginally better than the batch version. Figure 36 shows a similar plot as Figure 26) We consider a replacement rate strategy where we
graph dataset, given in Figure In Figure 3a the green curve
coordinates of the hint vector independently with varying probabilities. The curve shows the average of 5 trials and X = 0.1 again. The same qualitative message Figure 2b holds: while the corruption rate is small, achieve similar competitive ratio as in Figure 3a and as the corruption rate increases, there is smooth increase in the competitive ratio.
In addition to extending and complementing the experimental results of [MS200, we summarize experimental results in the following points: (a) Our theory is predictive of experimental performance and qualitatively validates which underlies all of our algorithm contributions efficient to carry out and execute in practice. (c) Learning augmeened online algorithms be applied to real world datasets varying time such as in the analysis of graphs derived from a dynamic network.
robustness and consistency trade-offs. (b) Our algorithm framework
Open Problems. As stated in [BM220, natural future direction is to design PDLA algorithms for packing LPs. For general online packing LPs, an ( log k) coompetitivee online solution can be obtained only if condition number is known offline (BN09b), implying impossibility results without assumptions. The hope here is to study structured packing problems, c.g., load balancing [BN09a] and ad-auction revenue maximization [BN07].
Acknowledgment
We thank Roie Levin for bringing to our attention the significantly simpler algorithm described in the full version of the paper [GLS (2b))22b)
10

---

References
[AAA*06] Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. A general approach to online network optimization problems. ACM Transactions Algorithms (TALG), 2(4):640-660, 2006.
[AAA+09 Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. The online set cover problem. SIAM Journal Computing, 39(2)3611-370, 2009.
[AW02] Rudolf Ahlswede and Andreas Winter. Strong converse for identification via quantum channels. IEEE Transactions on Information Theory, 48(3):569-577 2002.
[BJN07] Niv Buchbinder, Kamal Jain, and Joseph Seffi Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. European Symposium on Algorithms, pages 253-264. Springer, 2007.
[BMS20]
Étienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS, 2020.
[BN09a]
Niv Buchbinder and Joseph Naor. The design of competitive online algorithms via primal-dual approach. Found. Trends Theor. Comput. Sci., 3(2-3)993-263, 2009.
[BN09b]
Niv Buchbinder and Joseph Naor. Online primal-dual algorithms for covering and packing. Mathematics of Operations Research, (4(2):270-285 2009.
(CEI+22) 22]
Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Ru- binfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, and Michael Zhang. Triangle and four cycle counting with predictions in graph streams. In The Tenth International Conference on Learning Representations, ICLR, 2022.
[CSVZ22]
Justin Y. Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang. Faster fundamental graph algorithms via learned predictions. In International Conference on Machine Learning, ICML, pages 3583-3602, 2022.
[DII++21] Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvit- skii. Faster matchings via learned duals. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS, pages 10393-10406, 2021.
[EFS+22] Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, and Samson Zhou. k-means clustering. The Tenth International Conference on Learning Representations, ICLR, 2022.
[EKN16] Noa Elad, Satyen Kale, and Joseph (Seffi) Naor. Online semidefinite programming. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP, pages 40:1-40:13 2016.
[GLQ21] Elena Grigorescu, Young San Lin, and Kent Quanrud. Online directed spanners and steiner forests. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), 2021.
[2L Elena Grigorescu, Young-San -an Lin, Sandeep Silwal, Maoyuan Song, and Samson Zhou. Dearning-augmenter algorithms for online linear and semidefinite programming. arXiv preprint arXiv:2209.106 200.:2099.111 2022.
[GLS+22b) Elena Grigorescu, Young-San Lin, Sandeep Silwal, Maoyuan Song, and Samson Zhou. algorithms for online linear and semidefinite programming. 2022.
[Kar72]
Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. Springer, 1972.
[LK14]
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http: snap. stanford edu/data] June 2014.
[LKFOS]
Jure Leskovec, Jon M. Kleinberg, and Christos Faloutsos. Graphs over time: densifica- tion laws, shrinking diameters and possible explanations. In Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 177-187, 2005.

---

[SZS + 14]
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In 2nd International Conference Learning Representations, ICLR, Conference Track Proceedings, 2014.
[VB96]
Lieven Vandenberghe and Stephen P. Boyd. Semidefinite programming. SIAM Rev., 38(1):49-95, 1996.
[WX06]
Avi Wigderson and David Xiao. Derandomizing the aw matrix-valle valled chernoff bound using pessimistic estimators and applications. ECCC TR06-105, 2006.
12


Reviews:
[{"review_id": "XTO_sCM2NvH", "reviewer": "Reviewer_b8M5", "summary": "This paper studies online covering linear and semidefinite programs, and proposed algorithms that incorporate models with prediction. The main technical results show that the proposal primal and dual learning-augmented algorithm can achieve both consistency (when the prediction is accurate) and robustness (when the prediction is inaccurate). The techniques work for both online linear programs and semidefinite programs. Some empirical evaluations are presented to demonstrate the performance of the proposed algorithmic framework. ", "questions": "It is not good to say semidefinite programming is a unifying framework that generalizes quadratically-constrained quadratic programs (QCQPs). The authors may mean that convex QCQPs can be reformulated into a special SDP. However, a general QCQP can be highly non-convex and contain NP-hard instances as special cases. ", "limitations": "It is fine to put some technical proofs to the extended version. But it is better to make the main text be more independent, not like an extended abstract. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ The problem is well-motivated, and the contributions seem novel compared to the previous results.\n+ The technical proofs in the extended version appear to be solid (but the reviewer didn't check the details).\n+ The comparison between online linear programs and online semidefinite programs is well-organized. \n\nWeaknesses:\n- The main results have not been rigorously stated in the main text. Indeed, the informal results in Theorem 1.3 and Theorem 1.4 are not rigorous. The authors put the full algorithms, formal statements of theorems, and all the proofs into the extended version. The main text appears less complete and is more like an extended abstract. \n- The overview of techniques in Section 1.2 is not easy to follow. The overview still appears to be very technical and has many jargons.\n- The proof sketch for Theorem 1.3 and Theorem 1.4 on Page 7 and Page 8 does not present sufficient proof ideas, which is not easy to follow.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FxCjUkp6TmJ", "reviewer": "Reviewer_8aZd", "summary": "An online optimization algorithm is a method where the data of the problem can be presented in a piecemeal fashion, and the optimizer must make certain irrevocable decisions at each step. This is a strong limitation, and usually results in a loss in performance described by the \"competitive ratio\" (ratio of online optimum to offline optimum). \n\nThe present paper belongs to a growing line of research where one studies online algorithms that receive \"advice\" on the solution. This advice may come from a predictive algorithm that guesses the next problem instances. The desiderata for a good method in this setting are the following: (1) if the advice is good, then the performance of the method should nearly match the optimal offline solution; and (2) if the advice is not good, the usual, assumption-free competitive ratio is (nearly) achieved.  \n\nIn comparison with previous work, such as the one by Bamas et al. in NeurIPS 2020, the main novelties here are twofold. First, the present method can deal with certain \"covering LPs\" with non-integral constraints. Second, covering SDPs are also considered, which extends the scope of the \"primal-dual method\". In all cases, one obtains desiderata (1) and (2) above. A small experimental section is also presented. \n\nLet me add a few words about the main ideas. As mentioned, Bamas et al. consider integral constraints. The present paper allows for fractional constraints; so decision variables must be increased continuously from round to round. The analysis of the method is not terribly difficult, but is a bit subtle and (at least to me) surprising.  ", "questions": "Can you comment a bit more on the motivation for the setting? E.g. where and when would it be a good idea to use these methods. ", "limitations": "Yes, they have.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*\n\nThe paper is easy to read, clear, and seemingly original. The main issues at stake stated and the contribution is quite nice. Some previous results are subsumed by the present manuscript. While I am not an expert on this topic, I am fairly convinced that the extension of the primal-dual method to this setting is non-trivial.\n\n*Weaknesses* \n\nIn practical applications, better control of the constants in the approximation ratios is needed. \n\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0-0_ehqHpA0", "reviewer": "Reviewer_LaFt", "summary": "The paper considers online linear and semidefinite programming problem and makes use of the predicted optimal solutions to give algorithms. The authors extend the primal-dual learning-augmented framework of online set cover (NeurIPS 2020) to online LP and SDP covering. For online LP covering, they show a $O(1/(1-\\lambda))$-consistent and $O(\\log \\frac{kn}{\\lambda}$-robust algorithm, where $\\lambda$ is a given parameter, $n$ is the number of variables, and $k$ is the upper bound for the ratio between the maximum positive entry and the minimum positive entry in each column of the constraint matrix. For online SDP covering, the same consistency and robustness are also obtained. If the variables in the (linear or semidefinite) program lie in a bounded region, the robustness can be improved slightly to $O(\\log(s/\\lambda)$, where $s$ is the sparsity.", "questions": "- The definition of ``consistency\" in the paper is different from the standard one where the consistency refers to the competitive ratio when the prediction is accurate. In the context, the two definitions are the same because the optimal solution is predicted in the paper, and thus, ADV=OPT when the the prediction is accurate. However, in many other problems, even with an accurate prediction, ADV could be larger than OPT. \n\n- The statements of algorithm 1 and algorithm 2 miss the update of the dual variables $y$. So when I first read the proof sketch, I got confused. The algorithms provided in the supplementary material are correct I guess. ", "limitations": "The authors adequately addressed the limitations and I didn't see any potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- Online LP and SDP covering are very important frameworks in the field of online algorithmic design. They capture a large number of problems, such as ski rental, online set cover, and so on. The authors show a general framework to leverage the predicted (fractional) optimal solutions to design non-trivial algorithms. The work is solid and the proposed idea could be widely applied to many online covering problems.\n\nWeakness:\n- The robustness ratio matches the pure online worst-case bound only when the condition number $k$ is $poly(n)$, but in the general case, $k$ might be a very large value. The work can be strengthened if the paper has a discussion about the optimality of the consistency-robustness tradeoff. Ideally, prove that the dependence on $k$ is unavoidable when the consistency is $O(1/(1-\\lambda))$. Furthermore, the authors can consider the case that $k$ is known in advance and see if a better ratio can be obtained. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept