A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization
Authors: Tesi Xiao
Krishna Balasubramanian
Saeed Ghadimi
Venue: NeurIPS 2022 Accept (2022)
Keywords: Projection-Free algorithm
Conditional gradient algorithm
Stochastic multi-level composition optimization
Moving-average
Oracle complexity
High-probability bounds

Abstract: We propose a projection-free conditional gradient-type algorithm for smooth stochastic multi-level composition optimization, where the objective function is a nested composition of $T$ functions and the constraint set is a closed convex set. Our algorithm assumes access to noisy evaluations of the functions and their gradients, through a stochastic first-order oracle satisfying certain standard unbiasedness and second-moment assumptions. We show that the number of calls to the stochastic first-order oracle and the linear-minimization oracle required by the proposed algorithm, to obtain an $\epsilon$-stationary solution, are of order $\mathcal{O}_T(\epsilon^{-2})$ and $\mathcal{O}_T(\epsilon^{-3})$ respectively, where $\mathcal{O}_T$ hides constants in $T$. Notably, the dependence of these complexity bounds on $\epsilon$ and $T$ are separate in the sense that changing one does not impact the dependence of the bounds on the other. For the case of $T=1$, we also provide a high-probability convergence result that depends poly-logarithmically on the inverse confidence level. Moreover, our algorithm is parameter-free and does not require any (increasing) order of mini-batches to converge unlike the common practice in the analysis of stochastic conditional gradient-type algorithms.

A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization
Tesi Xiao Department of Statistics University California, Davis texiao@ucdavis..e
Krishnakumar Balasubramanian
Department of Statistics
University of California, Davis
kbala@ucdavis... edu
Saeed Ghadimi
Department of Management Sciences
University of Waterloo
sghadimi iasaadiiuuuattrroooo. ca
Abstract
We propose a projection-fiee conditional gradient-type algorithm for smooth stochastic multi-level composition optimization, where the objective function is a nested composition functions and the constraint set a closed convex set. Our algorithm assumes access to noisy evaluations of the functions and their gradients, through stochastic first-order oracle satisfying certain standard unbiasedness and second-moment assumptions. We show that the number of calls to the stochas- tie first-order oracle and the finear-minmiization oracle required by the proposed algorithm, to obtain e-stationary solution, are of order Or(e (2) and Or ()) respectively, where Or hides constants in T. Notably, the dependence of these complexity bounds and T are separate in the sense that changing one does not impact the dependence the bounds on the other. For the case of = 1, we also provide high-probability convergence result that depends poly- logarithmicallly the inverse confidence level. Moreover, our algorithm parameter- free and does not require any (increasing) order of mini-batches to converge unlike the common practice in the analysis of stochastic conditional gradient-type algorithms.
Introduction
We study projection-free algorithms for solving the following stochastic multi-level composition optimization problem
min SEX
F(x) == f1 .... fr(x),
(1)
where ft dRd Rd.
L, -, composite function F is bounded below by F* > -oo and X Rd is closed convex set. We assume that the exact function values and derivatives of fi's are not available. In particular, we assume that fa(w) Eg, (v. E:) for some random variable & Our goal is solve the above optimization problem, given access to noisy evaluations V.i's and fi's.
(do 1) are continuously differentiable functions, the
There are two main challenges to address in developing efficient projection-free free algorithms for solving (T). First, note that denoting the transpose the Jacobian of f, by V V... the gradient of the objective function F(z) in ( is given by VF(x) V fr(()) ( fr (3r-())11)--
V (J1), where V: f+1 .... o (x) for < i T, and yr = I. Because of the nested nature the gradient Fz),, obtaining an unbiased gradient estimator in the stochastie first-order setting, with controlled moments, becomes non-trivial, Using naive stochastic gradient estimators lead to oracle complexities
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

that depend exponentially on T (in terms of the accuracy parameter). Next, even when T = 1 in the stochastic setting, projection-fre algorithms like the conditional gradient method its sliding variants invariably require increasing order of mini-batched 28 40 practical implementation infeasible.
24
which make their 39 52
In this work, we propose projection-free conditional gradient-type algorithm that achieves level- independent oracle complexities (i.e., the dependence of the complexities on the target accuracy is independent of (') using only one sample of (5:) in each iteration, thereby addressing both of the above challenges. Our algorithm uses moving average based stochastic estimators of the gradient and function values, also used recently by [19] and 44, along with an inexact conditional gradient method used by [3] (which in turn is inspired by the sliding method by (28).. order to establish our oracle complexity results, we use novel merit function based convergence analysis. To the best of our knowledge, such an analysis technique is used for the first time the context of analyzing stochastic conditional gradient-type algorithms.
1.1 Preliminaries and Main Contributions
We now introduce the technical preliminaries required state and highlight the main contributions of this work. Throughout this work, || || denotes the Euclidean norm for vectors and the Frobenius norm for matrices. We first describe the set of assumptions on the objective functions and the constraint set. Assumption 1 (Constraint set). The set X' C Rd is convex and closed with max || vll < Dx. 2.yEX
Assumption 2 (Smoothness). All fumctions fi..... fr and their derivatives are Lipschitz continuous with Lipschitz constants L,, and f, respectively.
The above assumptions on the constraint set and the objective function are standard in the literature stochastic optimization, and in particular in the analysis of conditional gradient algorithms and multi-level optimization; see, for example, (28). [50] and 4 We emphasize here that the above smoothness assumptions are made only on the functions (fe) and not on the stochastic functions (G:)ıser (which would be a stronger assumption). Moreover, the Lipschitz continuity of fi's 's are implied by the Assumption [ and assuming the functions are continuously differentiable. However, for sake of illustration, we state both assumptions separately. In addition to these assumptions, we also make unbiasedness and bounded-variance assumptions on the stochastic first-order oracle. Due to its technical nature, we state the precise details later in Section 3 (see Assumption 3
We next turn our attention to the convergence criterion that performance of the proposed algorithm. Gradient-based algorithms iteratively solve ppoobloobbe in the form of
in this work to evaluate the
B (g.u) + - =1|2 =
arg arg NEX
(2)
for some 3 > 0, g E Idd and x E X. Denoting the optimal solution of the above problem by Px 9, and noting its optimality condition, one can easily show that
-VF(Z) (x) + B 0. llg VF(T) + B|| - (x 9. 3) + IVV(()1/3))
where (T) is the normal cone to X' at T and ((0,) r) denotes a ball centered at the origin with radius Thus, reducing the radius of the ball in the above relation will result in finding an approximate first- order stationary point of the problem for non-convex constrained minimization problems. Motivated by this fact, we can define the gradient mapping at point X as
Gx V) = B Px VF = 3 x - II
(3)
where (y) denotes the Fuclidean projection of the vector onto the set X' The gradient mapping classical measure has been widely used in the literature convergence criterion when solving nonconvex constrained problems [35]. It plays an analogous role of the gradient for constrained optimization problems; in fact when the set X' Rd the gradient mapping just reduces to VF should be emphasized that while the gradient mapping cannot be computed in the stochastic setting, it
We discuss in detail about some recent works that avoid requiring increasing mini batches, albeit under stronger assumptions, in Section 1.2

---

Algorithm
Criterion
# of levels
Batch size
SFO
LMO
SPIFER-SFI 52
FW-gap
1
O(c²))
O(c
0
I-SFW [54
FW-gap
1
O
0
SCFW [
FW-gap
2
Ole
Ole )
SCGS [39
GM
1
O(e
Ole
Ole
SGD+ICG
GM
1
O(e
Ole
LINASA+IGG (Algorithm)
GM
T
Or((²) Or(c²)
Table I: Complexity results for stochastic conditional gradient type algorithms to find an e-stationary solution in the nonconvex setting. FW-Gap and GM stands for Frank-Wole Gap (see 4 and Gradient Mapping (see (3) respectively. Or hides constants in T. Existing one-sample based stochastic conditional gradient algorithms are either (i) not applicable the case of general T > or (ii) require strong assumptions [54), or (iii) are not truly online [[]: see Section 1.2 for detailed discussion. The results in [3] are actually presented for the zeroth-order setting; however the above stated first-order complexities follow immediately.
still serves as a measure of convergence. Our main goal in this work is to find an c-stationary solution to (I) in the sense described below.
Definition 1. A point ā E X generated by an algorithm for solving I is called an e-stationary point, if we have B[llxx(,, FF( S where the expectation is taken over all the randommess involved in the problem.
In the literature on conditional gradient methods for the nonconvex setting, the so-called Frank- Wolfe gap is also widely used provide convergence analysis. The Frank-Wolfe Gap defined formally as (" F()))
max (VF(T), y)-
(4)
yEx
As pointed out by Bl. the gradient mapping criterion and the Frank-Wold gap are related to each other in the following sense.
Proposition 1. 3 Let gx(+) be the Frunk- Woole gap defined (4) and gx(+) be the gradient mapping defined in (3. Then, we have [[9x(x, F((x), 3) I (x F((x)), do E X. Moreover
under Assumption we have (x, VF(x)) < (1/3) Ly. + Dx (x, 8)1x
For stochastic conditional gradient-type algorithms, the oracle complexity is measured in terms of number of calls to the Stochastic First-order Oracle (SFO) and the Linear Minimization Oracle (LMO) used to the solve the sub-problems (that are of the form of minimizing a linear function over the convex feasible set) arising in the algorithm. In this work, we hence measure the number calls to SFO and LMO required by the proposed algorithm obtain an e-stationary solution in the sense of Definition !
We now highlight our main contributions:
We propose projection-free conditional gradient-type method (Algorithm T for solving [ In Theorem 2 we show that the SFO and LMO complexities of this algorithm, in order to achieve an c-stationary solution in the sense of Definition | of order O 2) and O(e respectively,
The above SFO and LMO complexities are in particular invll-indepedeent (i.e., the dependence of the complexities the target accuracy is independent of 7). The proposed algorithm is parameter-free and does not require any mini-batches, making it applicable for the online setting.
When considering the case of < 2, we present a simplified method (Algorithm) and 4 to obtain the same oracle complexities. Intriguingly, while this simplified method is still parameter- free for 1, it is not when of T = 1, we also establish high-probability bounds (see Theorem
(see Theorem and Remark B.I.. Furthermore, for the case
summary of oracle complexities for stochastic conditional gradient-type algorithms is in Table I
1.2 Related Work
Conditional Gradient-Typp Method. The conditional gradient algorithm [.. 29], has had renewed interest in the machine learning and optimization communities in the past decade; see [33
3

---

26 20 27 5
for partial list of recent works. Considering the stochastic convex setup, [2 24 provided expected oracle complexity results for the stochastic conditional gradient algorithm. The complexities were further improved by sliding procedure in [28]. based on Nesterov's 8 acceleration considered variance reduced stochastic conditional gradient algorithms, and provided expected oracle complexities in the non-convex setting. [3 analyzed the sliding algorithm in the non-convex setting and provided results for the gradient mapping criterion. All of the above works require increasing orders of mini-batches to obtain their oracle complexity results.
17
method. [40 52 24
and [44] proposed stochastic conditional gradient-type algorithm with moving-averagg
gradient estimator for the convex and non-convex setting that uses only one-sample in each iteration.
However, [4 and [54]] require several restrictive assumptions, which we explain next (focusing
on [54] which considers the nonconvex case). Specifically, [54] requires that the stochastic function
G1(2, (1) has uniformly bounded function value, gradient-norm and Hessian spectral-nomn and the
distribution of the random vector &ı has an absolutely continuous density p such that the norm of the gradient of p and spectral norm of the Hessian of logp p has finite fourth and aecond-moment respectively. In contrasts, we do not require such stringent assumptions. Next, all of the above works focus only on the case of T = 1. 0 considered stochastic conditional gradient algorithm for solving D. with T = 2. However, M also makes stringent assumptions: (i) the stochastic objective functions G1 (zz &1) and G2 {1) themselves have Lipschitz gradients almost surely and (ii) for a given instance of random vectors & and ε2, one could query the oracle at the current and previous iterations, which makes the algorithm not to be truly online. See Table [ for a summary.
Stochastic Multi-level Composition Optimization. Compositional optimization problems of the form in ① have been considered as early as 1970s by [12]. Recently, there has been renewed interest on this problem. [13] and [00 considered a sample-average approximation approach for solving ( and established several asymptotic results. For the case of T 2, 488), [4) and [6]
proposed and analyzed stochastic gradient descent-type algorithms in the smooth setting. 9 and considered the non-smooth setting and established oracle complexity results. Furthermore, [25) proposed algorithms when the randomness between the two levels are not necessarily independent. For the general case of T 2 1, [50] proposed stochastic gradient descent-typs algorithms and established oracle complexities established that depend exponentially on T and are hence sub-optimal. Indeed, large deviation and Central Limit Theorem results established in [13] [0], respectively, show that in the sample-average samples, converges at cevel-independent rate (i.e., dependence of the convergence rate on the target accuracy is independent of ') to the true minimizer, under suitable regularity conditions.
approximation setting, the arg min of the problem in (I) based on n
19 proposed single time-scale Nested Averaged Stochastic Approximation (NASA) algorithm and established optimal rates for the cases of T = 1,2. For the general case of T Z 1, proposed a linearized NASA algorithm and established iiveedindeeendent and optimal convergence rates. Concurrently, [43] considered the case when the function f; are non-smooth and established asymptotic convergence results. [53] also established non-asymptotic level-independent oracle complexities, however, under stronger assumptions than that in [4]. Firstly, they assumed that for fixed batch of samples, one could query the oracle on different points, which is not suited for the general online stochastic optimization setup. Next, they assume a much stronger mean-square Lipschitz smoothness assumption on the individual functions fi and their gradients. Finally, they required mini-batches sizes that depend exponentially on T. which makes their method impractical. Concurrent 4 level-independent rates were also obtained for unconstrained problems by [7). albeit, under the stronger assumption that the stochastic functions Gz Ei) are Lipschitz, almost surely. It is also worth mentioning that while some of the above papers considered constrained problems, the algorithms proposed and analyzed in the above works are not projection-free, which is the main focus of this work.
2 Methodology
In this section, we present our projection-free algorithm for solving problem (.. The method generates three random sequences, namely, approximate solutions {x²), J. average gradients {a*], and average function values {u²), defined a certain probability space (St P). We let F to be the olaggebra generated by {a= ,...,, x 2o...., 2t, uff..., ux ....... u...,uf.... uf...., 3 The overall method is given in Algorithm In 77. the stochastic Jacobians Je+1 14xxd11,, and the product

---

Algorithm Linearized NASA with Inexact Conditional Gradient Method (LiNASA+ICG)
Input: nº E X, 20 =0 R.,
uf E Rd
-....... T, Bk > O, t > O, T E (0, 11. 6 2
for k 0, 0,1,2.... N do
1. Update the solution:
8² = ICG(x", 2 Bx, x ++ = xº (5 -2*),
(5)
(6)
and compute stochastic Jacobians J and function values G at u for i = 1, .......... T.
2. Update average gradients and function value estimates u, for each level i 1....,
x =1 (1 Th II T+I-8
u k-1 (1 +Tk) + G + (J++1 - u(+1)-
(8)
end for Output: (I R uf wf), where R is uniformly distributed over 21,
Algorithm 2 Inexact Conditional Gradient Method (ICG)
Input: 2,, M, Set wd = 2. for t 0,1,2,... ...., M do 1. Find v² E X with quantity 5 2 0 such that
BD2
(2 B(w' - 2)) v²) I min
(z + 3(w - 2) +
veX
t 2
{1.
2. Set w = (1 - p))w" + mao with min
31v
end for Output: W
J is calculated (1-) to represent both matrix-vector multiplication and vector-vector inner product. There two aspects of the algorithm that we highlight specifically: (i) In addition to estimating the gradient of F. we also estimate stochastic linear approximation of the inner functions by moving-averan aveerge technique. In the multi-level setting we consider, helps us to avoid the accumulation of bias, when estimating the f, directly. Linearization techniques similar approach was used in 4 in the context of projected- -ased methods for solving ① It is also worth mentioning that other linearization techniques have been used in [9] and 11 for estimating the stochastic inner function values for weakly convex two-level composition problems, and (ii) The ICG method given in Algorithm 2 is essentially applying deterministic conditional gradient method with the exact line search for solving the quadratic minimization subproblem in (2) with the estimated gradient 24 in (7). was also used in sub-routine and is motivated by the sliding approach of (28).
R = R In (8) use the notation
used in the stochastic optimization since
the work of 42
Main Results
In this section, we present our main result on the oracle complexity Algorithm proceed, we present our assumptions on the stochastic first-order oracle.
Before we
Assumption 3 (Stochastic First-Order Oracle). Denote ut+1 x For each k, witn being the input, the stochastic oracle outputs Gk-- E Rdd and J such that given Fn and for any i E (I....,T)
(a) [ Vi((u)))) E.GH Fx) f((u(-1).
5

---

(b) BIIGH+
& a. EIIJ (f - o.
(c) The outputs of the stochastic oracle at level i, G and + , are independent. The oulputs of the stochastic oracle are independent between levels, i.e, ( are independent and are { " /1=1....
gg++1
Parts (a) and (b) in Assumption 3 are standard unbiasedness and bounded variance assumptions on the stochastic gradient, common in the literature. Part (c) is essential to establish the convergence results in the multi-level case. Similar assumptions have been made, for example, in [50] and [4]. We also emphasize that unlike some prior works (see e.g., (54)), Assumption 3 allows the case of endogenous uncertainty, and we do not require the distribution of the random variables (Ei)ssigr to be independent of the distribution of the decision variables (us)ıgieT-
2 and 3 we can immediately conclude that 1[I = B[|J - [[]:((++)))) + (u S o + 123 = o3.-- In the sequel, o3, will be used to simplify the presentation.
Remark. Under Assumption
We start with the merit function used in this work and its connection to the gradient mapping criterion. Our proof leverages the following merit function:
2, = - -() =||²
7 allli(uc+1) - w.l.. (9)
where a, trtsssss are positive constants and
n 2)
min yEN
H,,5,,2,8) = (2, x) 2 lly =1
3
(10)
Compared to 44) we require the additional term F[)) - =|13, which turns out to be essential in our proof due to the ICG routine. The following proposition relates the merit function above to the gradient mapping.
Proposition 2. Let (x(+)) be the gradient mapping defined in 3 and n(---) be defined in 100) For any pair of (z, 2) and? B we have 119x(2, (F))). B)12 4.,n(x 2) + F[x) =!1
Proof. By expanding the square, and using the properties of projection operation, we have
1 (²2= - x=1² + [xxx [x
1 3²) (x 3 2) - I (x
1 1 2)11 g =
Thus, have 7(x, 2) S 111x =) x1|2. The proof completed immediately by noting
that (x VF(x). 12 < 2. 2,- +=) 1| (z) =1|²-
We now present out main result on the oracle complexity of Algorithm[]
Theorem 2. Under Assumption /
2 let (a*t
2h (uf (uisrs J220 be the sequence generated by
Algorithm 7 with N 2 1 and
1
3x = B > O,
1. to Th
4 = [VA], Ak 2
(11)
VN
where 3 is an arbitrary positive constant. Provided that the merit function Wa, (2, 2, u) is defined as ( with
8
8 2¹ (T (T- )
a
m1
71 = 2a + 4aL?
25J5T,
(12)
20L2 F
2'
we have,
2(B +
2012 3
[2W any (00 20,00000000000 (,,)) + B(B, 0² T., Dx, T,
E [x(x" (,
VN
(13)

---

2W a,, (x",,",,, ) + +B(3, 00, L,, 1sisT.
, BVN
E [[(l(((((tt) - 13
(14)
where WT+1 x 2,,+1==,,B(B0rr) ,2, - 3 +0) ( SLee - and 8² is constant
depending the purameters (3, (3,0², L, Dx. T) given in (42). The expectation is laken with respect
to all random sequences generated by the method and an independent random integer number R uniformly distributed over {1....,N] N... That is to say, the number of calls to SFO and LMO get
e-stationary point is upper bounded by Or(e 2), Or(e 9) respectively.
Remark. The constant B(3, o², Lx,x,T, (, is (TT) given the definition of o² and the value of "/ in (12). which further implies that the total number of calls to SFO and LMO of Algorithm for finding Or respectively. Furthermore, it is worth noting that this complexity bound for Algorithm is obtained without any dependence of the parameter 3r Lipschitz constants due to the choice of arbitrary positive constart (3 in (11). and Tk, 1 depend only on the number of iterations N and le respectively. This makes Algorithm Saanthmmmparnnn parameter-free and easy to implement.
an e-stationary point of (.) are bounded by O 2) Orle 2) and O
Remark. As discussed in Section 2 the ICG routine given in Algorithm 2 is a deterministic method with the estimated gradient 2 in 7 The number of iterations, tRp required run Algorithm 2 is given by tx =[V]] That is, require more precise solutions for the ICG routine, only for later outer iterations. Furthermore, due to the deterministic nature of the ICG routine, further advances in the analysis deterministic conditional gradient methods under additional assumptions on the constraint set X (see, for example, [6 18]) could be leveraged to improve the overall LMO complexity.
3.1 The special cases of T = and T
We now discuss several intriguing points regarding the choice of tuning parameter B3, for the case of T = 2. and the more standard case of T = 1. Specifically, the linearization technique used in Algorithm [ turns out to be not necessary for the case of T 2 and T to obtain similar rates. However, without linearization, the choice of 33 is dependent on the problem parameters for T= 2. Whereas it turns out to be independent of the problem parameters (similar to Algorithm| [and and Theorem
2 which holds for all 7 2 1) for T As the outer function value estimates (i.e., sequence) are not required for the convergence analysis, we remove them in Algorithms 3 and
Algorithm 3 NASA with Inexact Conditional Gradient Method (NASA+ICO) for T =
Replace Step 2 of Algorithm 1 with the following:
2'. Update the average gradient 2 and the function value estimate u2 respectively as:
+++ = (1 - =x + + of
and u2 k-1 = (1 - Tx) + Gx G
Algorithm 4 ASA with Inexact Conditional Gradient Method (ASA+ICG) for T Replace Step 2 of Algorithm with the following:
2". Update the average gradient z as: k+1 (1 - Tx)=** TKJH
Theorem 3. Let Assumptions 2 3 be satisfied by the optimization problem T.. Let C₁, C2 and C3. be some constants depending on the parameters (B, 0z, L,, Dx, 8), as defined in (54) and (62. Let
To 1, Tk- Jx: [V), vk 2 where N is the total number of iterations.
(a) Let T 2, and let fat ,², ut J120 be the sequence generated by Algorithm with
2
Bk = 3 2 6pLvF + (2p+
LV L3 p p>0. 0.
(15)
3p
Then, have VN 2 1,
C
E - C₂
E [I
VN'
VN
7

---

(b) Let = and let 1e,,2" be the sequence generated by Algorithm Then, have VN 2 1,
with 3x 0.
C3
E VFFx",
VN
All expectations are taken with respect to all random sequences generated by the respective algorithms and an independent random integer number R uniformly distributed over {I....,N .N In both cases, the number of calls SFO and LMO get an e-stationary point upper bounded by O )) O respectively.
Remark. While we can obtain the same complexities without using the linear approximation of the inner function for T = 2, it seems necessary have parameter-free algorithm as the choice of in (15) depends on the knowledge of the problem parameters. Indeed, the linearization term in (8) helps use to betler exploit the Lipschitz smoothness of the gradients get error bound in the order of +élld" for estimating the inner function values. Without this term, we are only able to use the Lipschitz continuity of the inner functions and the error estimate will increase to the order of Telld (||,| I]. Hence, we need to choose a larger beta (as in (15) to reduce ||dh) and handle the error term without compromising the complexities. However, this is not the case for T as it can be seen as a two-level problem whose inner function is exactly known (the identity map). In this case, the choice of is independent of the problem parameters with without the linearization term.
3.2 High-Probability Convergence for =
In this subsection, we establish an oracle complexity result with boobb-bbbbbiiityy for the case of T = 1. We first provide notion of (e, -sstationnyy point and a related tail assumption the stochastic first-order oracle below.
Definition 4. A point z X' generated by an algorithm for solving is called an (c, -sttationnyy point, if we have 1| (z, FF( 9)12
with probability 1
Assumption 4. Let A h+1 EJA 4++1
(* - Jk+1 for k 2 0. For each k. given Fx we have
and A R++ Fx is E-ssub--uussin
The above assumption is commonly used in the literature; see 12 45) and Appendix for additional details. The probbbbrbbbiittyy bound for solving non-convex constrained problems by Algorithm 4 ii given below.
21 30 55
We also refer to
be satisfied by the optimization problem I with T 1. Let To = 1, to = 0, Tk V Vk, vk 2 1, where N is the total number of iterations. Let = 1
Theorem 5. Let Assumptions
and let {æ* 2xx 1220 be the sequence generated by Algorithm with Br. 3 Then, we have
VN > 1,5 > O, with probability at least 1-8, 8.
K (12101110))
(x 3)(x"), so k=I....N
min
VN
Therefore, the number of calls SFO and LMO get (e, 8)-stationary point is upper bounded by 0(e-2log" log)((1))),, Oc3 log log2(1 respectively.
Remark. To the best of our knowledge, the above result is (i) the first high-probability bound for one-sample stochastic conditional gradient-type algorithm for the case of T 1. and (ii) the first high-probability bound for constrained stochastic optimization algorithms in the non-convex setting; see Appendix J of (32
4 Proof Sketch of Main Results
In this section, we only present the proof sketch. The complete proofs are provided the appendix. For convenience, let uT+11 xc, and we denote Hg the function value of the subproblem step y as the optimal solution of the subproblem i.e.,
Hx ((y t t (k), y² -ag
arg min Hz(y). yEX
(16)
Then, the proof of Theorem 2 proceeds via the following steps:

---

1. We first leverage the merit function Wa = Wan , , defined in (9) with appropriate choices of a, y for any 3 > to obtain
T
WK+1 - W S 2
Th 3 1
(8
+
(1li(u++1) - uu,1
FV =013
201 F
1=1
12
20L
+ RR +
+
(Hx Hx()"))
4k 2 0
5
B
where R2 is the residual term (see (3T) and E[R A I T² as shown in Proposition
2. Telescoping the above inequality, in Lemma 11
we obtain the following:
B
Σ Th 3 ||c
Σ
llf((u
1212
VF(a - x11
20
1=1
N
24
40LEE 8²
N
- 2W + + RR
+
+
Tk (H&(T*) H)( 2
5
A=
k=0
3. To further control the error term H Hx Hx((²)) introduced by the ICG method, we set Ex. the number of iterations in ICG method at step k, to [vk]. By Lemma we therefore have
(x H4(3*)) 28D 6)
Vi 2 1.
4 +
Also, with the choice of Th = tN and n0 = O, we can conclude that
Th (HAr(* -1x())))) 21 + +
Σ
VT S
41
VN
k=
4. Then, taking expectation of both sides and by the definition of random integer R, we have
E B
R 1
Σ
1 - uBl1? 20L2
B
[VF(2R)- - R s 2Wa B,
VN 2 1, where B is a constant depending on the problem parameters (8,02, L, Dx, T,8). 5. As result,
obtain 133 and (1) by noting that Ak: 2
1 1----F(C (VP(at))
1 B
1 VF(x") B)1) < 1akk 2,32 Txx x
1Ix
x
s 2 2,331aa1112 21( +
12.
where the second inequality follows the non-expansiveness of the projection operator.
The proofs of Theorems and 5 follow the same argument with appropriate modifications. The high-probabiling convergence proof of Theorem mainly consists of controlling the tail probability of the residual term R, being large.
Discussion
In this work, we propose and analyze projection-free conditional gradient-type algorithms for con- strained stochastic multi-level composition optimization of the form in (I). We show that the oracle complexity of the proposed algorithms is level-independenr Furthermore, our algorithm does require any increasing order of mini-batches under standard unbiasedness and bounded recond-moment assumptions on the stochastic first-order oracle, and is parameter-free. Some open questions for future research:
in terms of the target accuracy.
(1) Considering the one sample setting, either improving the LMO complexity from O(c-3) to O(c for general closed convex constraint sets or establishing lower bounds showing that O (3) is necessary while keeping the SFO in the order of ((c-2) is extremely interesting; and (ii) Providing high-probability bounds for stochastic multi-level composition problems (T > 1) and under sub-Gaussian or heavy-tail assumptions (as in
32 B1) is interesting to explore.

---

Acknowledgment
The authors are grateful to anonymous reviewers for their constructive comments that greatly im- proved the presentation of this paper. TX was partially supported by seed grant from the Center for Data Science and Artificial Intelligence Research, UC Davis and National Science Foundation (NSF) grant CCF-1934568. KB was partially supported by seed grant from the Center for Data Science and Artificial Intelligence Research, UC Davis and NSF grant DMS-2053918. SG was partially supported by NSERC Discovery Grant.
References
[1] Zeeshan Akhtar, Amrit Singh Bedi, Srujan Teja Thomdapu, and Ketan Rajawat. Projection-Free Algorithm for Stochastic Bi-level Optimization. arXiv preprint arXiv:2110.1172,, 2021.
[2] Raul Astudillo and Peter Frazier. Bayesian optimization of function networks. Advances in Neural Information Processing Systems, 34, 2021.
[3] Krishnakumar Balasubramanian and Saeed Ghadimi. Zeroth-order nonconvex stochastic op- timization: Handling constraints. high dimensionality, and saddle points. Foundations of Computational Mathematics, 22(1):35-76, 2022.
[4] Krishnakumar Balasubramanian, Saeed Ghadimi, and Anthony Nguyen. Stochastic multilevel composition optimization algorithms with level-independent convergence rates. SIAM Journal on Optimization, 32(2):519-544 2022.
[5] Amir Beck and Shimrit Shtern. Linearly convergent away-step conditional gradient for non- strongly convex functions. Mathematical Programming. 164(1-2):1-27, 2017.
[6] Jose Blanchet, Donald Goldfarb, Garud Iyengar, Fengpei Li, and Chaoxu Zhou. Unbiased simulation for optimizing stochastic function compositions. arXiv preprint arXiv: 2017.
[7] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Solving stochastic compositional optimization is nearly as easy solving stochastic optimization. IEEE Transactions on Signal Processing, 69:4937-4948, 2021.
[8] Weilin Cong, Rana Forsati, Mahmut Kandemir, and Mehrdad Mahdavi. Minimal variance sampling with provable guarantees for fast training of graph neural networks. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1393-1403 2020.
[9] Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):207-239, 2019.
[10] Darinka Dentcheva, Spiridon Penev, and Andrzej Ruszezyáski, Statistical estimation of com- posite risk functionals and risk optimization problems. Annals of the Institute of Statistical Mathematics, 69(4):737-76) 2017.
[11] John Duchi and Feng Ruan. Stochastic methods for composite and weakly convex optimization problems. SIAM Journal on Optimization, 28(():3229 (001322999999,,,,, 2018
[12] Yuri Ermoliev. Methods of stochastic programming. Nauka, Moscow, 1976.
[13] Yuri Ermoliev and Vladimir Norkin. Sample average approximation method for compound stochastic optimization problems. SIAM Journal on Optimization, 23(4):2231-226,
2013. 2013.
[14] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Generalization of model-agnostic meta- learning algorithms: Recurring and unseen tasks. Advances in Neural Information Processing Systems, 34, 2021.
[15] Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2)955-10, 1956.
10

---

[16] Dan Garber and Elad Hazan. Faster rates for the wrole method over strongly-conven sets. In International Conference on Machine Learning, pages 541-549. PMLR, 2015.
[17] Dan Garber, Atara Kaplan, and Shoham Sabach. Improved complexities of conditional gradient- type methods with applications to robust matrix recovery problems, Mathematical Programming. 186(1):185-206 2021.
[18] Dan Garber and Noam Wolf. Frank-Wolfe with a nearest extreme point oracle. Conference on Learning Theory, pages 2103-2132. PMLR, 2021.
[19] Saced Ghadimi, Andrzej Ruszczynski, and Mengdi Wang, A single timescale stochastic approximation method for nested stochastic optimization. SIAM Journal on Optimization, 30(1):960-973 2020.
[20] Zaid Harchaoui, Anatoli Juditsky, and Arkadi Nemirovski. Conditional gradient algorithms for norn-regularized smooth convex optimization. Mathematical Programming, 152(1-2):55-112, 2015.
[21] Nicholas JA Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non-smooth stochastic gradient descent. In Conference on Learning Theory, pages 1579-1613, PMLR, 2019.
[22] Elad Hazan and Satyen Kale. Projection-free free online learning. In 29th International Conference on Machine Learning, ICML 2012, pages 521-528 2012.
[23] Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization. The Journal of Machine Learning Research, 15(1):2489-255 2512, 2014.
[24] Elad Hazan and Haipeng Luo. Variance-reduced and projection-free stochastic optimization. In International Conference on Machine Learning, pages 1263-1271, 2016.
[25] Yifan Hu, Siqi Zhang, Xin Chen, and Niao He. Biased stochastic first-order methods for conditional stochastic optimization and applications in meta learning. Advances in Neural Information Processing Systems, 33, 2020.
[26] Martin Jaggi. Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In Interna- tional Conference on Machine Learning, pages 427-435. PMLR, 2013.
[27] Simon Lacoste-Julien and Martin Jaggi. On the global linear convergence of Frank- Wolff optimization variants. In Advances in Neural Information Processing Systems, pages 496-504, 2015.
[28] Guanghui Lan and Yi Zhou. Conditional gradient sliding for convex optimization. SIAM Journal on Optimization, 26(2): 2016.
[29] Evgeny Levitin and Boris Polyak. Constrained minimization methods. USSR Computational mathematics and mathematical physics, 6(5):1-50, 1966.
[30] Xiaoyu Li and Francesco Orabona. A high probability analysis of adaptive sgd with momentum. arXiv preprint MrXii:2007.142290 2020.
[31] Zhipeng Lou, Wanrong Zhu, and Wei Biao Wu. Beyond sub- aab-gaussian noises: Sharp concentra- tion analysis for stochastic gradient descent. Journal of Muchine Learning Reseurch, 23:1-22, 2022.
[32] Liam Madden, Emiliano Dall' Anese, and Stephen Becker. High-probability convergence bounds for non-convex stochastic gradient descent. arXiv preprint arXiv:2006.055: 05010, 2021.
[33] Athanasios Migdalas. A regularization of the frank-wolf method and unification of certain nonlinear programming methods. Mathematical Programming, 65(1):331-345, 1994.
[34] Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Stochastic conditional gradient methods: From convex minimization to submodular maximization. Journal of machine learning research, 2020.
11

---

[35] Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
[36] Qi Qi, Zhishuai Guo, Yi Xu, Rong Jin, and Tianbao Yang. An online method for class of distributionally robust optimization with non-convex objectives. Advances in Neural Information Processing Systems, 34, 2021.
[37] Qi Qi, Youzhi Luo, Zhao Xu, Shuiwang Ji, and Tianbao Yang. Stochastic optimization of areas under precision-recall curves with provable convergence. Advances in Neural Information Processing Systems, 34, 2021.
[38] Zi-Hao Qiu, Quanqi Hu, Yongjian Zhong, Lijun Zhang, and Tianbao Yang. Large-scale stochastic optimization of ndeg surrogates for deep learning with provable convergence. arXiv preprint arXiv: 12183, 2022.
[39] Chao Qu, Yan Li, and Huan Xu. Non-convex conditional gradient sliding. In International Conference Machine Learning, pages 4208 -217. PMLR, 2018.
[40] Sashank Reddi, Suvrit Sra. Barnabás Póezos, and Alex Smola. Stochastic frank-wolfe methods for nonconvex optimization. In 2016 54th Annual Allerton Conference Communication, Control, and Computing (Allerton), pages 1244-1251. IEEE, 2016.
[41] David Ruppert, Matt Wand, and Raymond J Carroll. Semiparametric regression Number 12. Cambridge university press, 2003.
[42] Andrzej Ruszezyíski. A linearization method for nonsmooth stochastic programming problems. Mathematics of Operations Research, 12(1):32 04.32-99,11 1987.
[43] Andrzej Ruszczynski. A stochastic subgradient method for nonsmooth nonconvex multilevel composition optimization. SIAM Journal on Control and Optimization, 59(3):3301-2300, 2021.
[44] Andrzej Ruszezyúski and Alexander Shapiro. Optimization of convex risk functions. Mathe- matics of operations research, 31(3):433 452, 2006.
[45] Roman Vershynin. High-ddmeensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[46] Gang Wang, Georgios B Giannakis, and Yonina C Eldar. Solving systems of random quadratic equations via truncated amplitude flow. IEEE Transactions on Information Theory, 64(2):73- 794, 2017.
[47] Guanghui Wang, Ming Yang, Lijun Zhang, and Tianbao Yang. Momentum accelerates the convergence of stochastic AUPRC maximization. In International Conference on Artificial Intelligence and Statistics, pages 3753-3771. PMLR, 2022.
[48] Mengdi Wang, Ethan Fang, and Han Liu. Stochastic compositional gradient descent: Algorithms for minimizing compositions of expected-value functions. Mathematical Programming, 161 2):419-449, 2017.
[49] Mengdi Wang. Liu, and Ethan Fang. Accelerating stochastic composition optimization. In Advances in Neural Information Processing Systems, 2016.
[50] Shuoguang Yang, Mengdi Wang, and Ethan Fang. Multilevel stochastic gradient methods for nested composition optimization. SIAM Journal on Optimization, 29(1):616 (00666656600 2019.
[51] Zhuoran Yang, Krishnakumar Balasubramanian, and Han Liu. High-dimensional non- gaussian single index models via thresholded score function estimation. In International conference on machine learning, pages 3851-3860. PMLR, 2017.
[52] Alp Yurtsever, Suvrit Sra, and Volkan Cevher. Conditional gradient methods via stochastic path-integrated differential estimator. In International Conference on Machine Learning, pages 7282-7291. PMLR, 2019.
[53] Junyu Zhang and Lin Xiao. Multilevel composite stochastic optimization via nested variance reduction. SIAM Journal on Optimization, 31(2):133-1157 2021.
12

---

[54] Mingrui Zhang, Zebang Shen. Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. One- sample Stochastic Frank-Wolfe. In International Conference on Artificial Intelligence and Statistics, pages 4012-4023. PMLR, 2020.
[55] Dongruo Zhou, Jinghui Chen, Yuan Cao. Yiqi Tang, Ziyan Yang. and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint arXiv:1808.05671,
2018. 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] This work considers particular
projection-free algorithm for a specific class of optimization problems. See also
Section []]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This is theoretical paper which does not have any direct negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assumption
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as a URL)? [Yes] We included a
ipynb file reproduce the experimental results.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable?x [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "h5jrGmZURkc", "reviewer": "Reviewer_R3Vn", "summary": "In this work, the authors proposed a projection-free algorithm (LiNASA-ICG) to solve the constrained stochastic multi-level optimization problem. The oracle complexities are derived for the algorithm and the algorithm is shown to be parameter-free. In addition, improvements in the T=1,2 case are provided and a high-probability bound is derived for the T=1 case.", "questions": "Major:\n(1) The comparison to [4] is not sufficient. Maybe I missed something, I think the major difference between the proposed algorithm and the algorithm in [4] is the generation of the next iteration point. Namely, sub-problem (5) in this work and sub-problem (3) in [4], which is the same as sub-problem (2) in this work. Since both this work and [4] aimed at solving (2), it is unclear how much advantage one can gain by utilizing the \"projection-free\" ICG procedure. Therefore, I would suggest the authors provide a more detailed comparison to [4] and numerical experiments, which will also help highlight the contributions of this work.\n\n\nMinor: \n(1) It would be better to clarify the difference between \"stochastic conditional gradient-type algorithms\" and \"stochastic gradient-type algorithms\". I guess the second term refers to the gradient descent-type algorithms?\n\n(2) The sentence at ln.135-138 is confusing and hard to parse. I would suggest the authors revise this sentence.\n\n(3) Ln.144 and ln.146: \"assume\" -> \"assumed\".\n\n(4) Ln.187-188: I do not understand why \\xi_i could be independent of u_i? I think they are related by relation (8) and cannot be independent. It would be better if more details can be included.\n\n(5) Ln.251: \"beta\" -> \"\\beta\".\n\n(6) It would be better if the authors could mention the difficulty of deriving high-probability bounds for the general T case. Alternatively, I wonder if it is possible to derive a (possibly worse) high-probability bound using the proof technique of the T=1 case.", "limitations": "See my comments in the \"questions\" section.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The topic of this paper is interesting to audiences in the optimization and machine learning fields. As the authors mentioned, the proposed algorithm has the advantage that it is projection-free and parameter-free. In addition, the algorithm does not require mini-batch, which will enable its application to the online optimization case. The paper is also well written and easily to follow. \n\nMy major concern is the contributions compared to [4]. It seems to me that many components in this work were already proposed in [4]. For example, the LiNASA algorithm and the construction of the merit function. Additionally, the comparison to [4] is not sufficient, which makes it hard to judge the contribution of this work. Hence, I would like to stay borderline and wait for the authors' response at this time.", "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": "U0W0C28wqC3", "reviewer": "Reviewer_41Ug", "summary": "This paper studies stochastic multi-level composition optimization problem, and especially focus on the class of projection-free algorithms. By combining the linearized NASA in existing works on multi-level composition problem and the existing conditional gradient algorithms, this paper propose a new algorithm that theoretically outperform other existing projection-free algorithms in the stochastic multi-level composition optimization problem.", "questions": "1. Could the author provide some insights for their proofs on why the algorithms can work without increasing batchsize, comparing to existing results.?\n\n2. I am confused on why the authors says that the bound in equation (13) is independent of T. From equation (42), it seems like the the bound should be exponentially dependent on T (There are summations over T and comulative product over T in the constant \\hat \\sigma^2.)?", "limitations": "See my comments above.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. I think one major theoretical novelty in this paper is that their proposed algorithm does not need an increasing batchsize and extra assumptions.\n\nWeakness:\n1. This paper appears to be incremental, and the problem setting seems contrive to me. First, it seems that the independence of the levels is due to the linearized NASA technique in existing works. Second, the theoretical analysis (Using gradient mapping as criterion and the moving averaging technique) seems standard in the existing literatures on SCG. Therefore, it looks like this paper is a direct combination of the existing results in multi-level composition optimization and conditional gradient algorithms.", "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": ["I don’t know"]}, "extra_text": {}}, {"review_id": "R0vTg1HAkwl", "reviewer": "Reviewer_nJmK", "summary": "The authors propose a projection-free method to solve the multi-level optimization problem, and analyse the number of calls to the stochasic first-order oracle and the linear-minimization oracle. The complexity is comparable with exisiting results for single-level problems. For single-level case (T=1), they also give a high-probability convergence result. Another merit of the proposed method is that it dose not require large batchsize and is parameter-free.", "questions": "1. Since this paper is about multi-level optimization, why not compare the complexity of the algorithm with other multi-level methods, such as [4],[7],[50],[52]?", "limitations": "No problems here. The authors discuss the limitations in Section 5, and I think they are proper.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n1. The proposed method is projection-free and parameter-free. It also does not require any increasing order of mini-batches. This paper is clear-written and analyses are supported by proofs that are sound to me.\n\nWeaknesses:\n\n1. As pointed out by the authors, the LMO complexity of the proposed method is worse than the single-level problem, i.e., $\\mathcal{O}(\\epsilon^{-3})$ vs $\\mathcal{O}(\\epsilon^{-2})$. Whether this rate is improvable is an important problem.\n\n2. The algorithm proposed is not novel enough. As mentioned in Section 2, the techniques used are already known in other literature. Especially, the method is a bit similar to existing multi-level work, i.e., [4], although the latter uses the projection operation to ensure the final point in the domain.\n\n3. Experiment results are not provided to show the practical performance of the proposed method.", "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