Overparameterization from Computational Constraints
Authors: Sanjam Garg
Somesh Jha
Saeed Mahloujifar
Mohammad Mahmoody
Mingyuan Wang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Large models
Robustness
Adversarial examples
Computational hardness

Abstract: Overparameterized models with millions of parameters have been hugely successful. In this work, we ask:  can the need for large models be, at least in part, due to the \emph{computational} limitations of the learner? Additionally, we ask, is this situation exacerbated for \emph{robust} learning? We show that this indeed could be the case. We show learning tasks for which computationally bounded learners need \emph{significantly more} model parameters than what information-theoretic learners need. Furthermore, we show that even more model parameters could be necessary for robust learning. In particular, for computationally bounded learners, we extend the recent result of Bubeck and Sellke [NeurIPS'2021] which shows that robust models might need more parameters, to the computational regime and show that bounded learners could provably need an even larger number of parameters. Then, we address the following related question: can we hope to remedy the situation for robust computationally bounded learning by restricting \emph{adversaries} to also be computationally bounded for sake of obtaining models with fewer parameters? Here again, we show that this could be possible. Specifically, building on the work of Garg, Jha, Mahloujifar, and Mahmoody [ALT'2020], we demonstrate a learning task that can be learned efficiently and robustly against a computationally bounded attacker, while to be robust against an information-theoretic attacker requires the learner to utilize significantly more parameters.

Overparameterization from Computational Constraints
Sanjam Garg"
Somesh Jha
Saeed Mahloujifar
Mohammad Mahmoody
Mingyuan Wang
Abstract
Overparameterized models with millions of parameters have been hugely successful. In this work, we ask: can the need for large models be, least in part, due to the computational limitations of the learner? Additionally, we ask, is this situation exacerbated for robust learning? We show that this indeed could be the case. We show learning tasks for which computationally bounded learners need significantly more model parameters than what Furthermore, we show that even more model parameters could be necessary for robust learning. In particular, for computationally bounded learners, we extend the recent result of Bubeck and Sellke [NeurIPS' 2022] which shows that robust models might need more parameters, the computational regime and show that bounded learners could provably need an even larger number of parameters. Then, we address following related question: can we hope to remedy the situation for robust computationally bounded learning by restricting adversaries to also be computationally bounded for sake of obtaining models with fewer parameters? Here again, we show that this could be possible. Specifically, building on the work Garg, Jha, Mahloujifar, and Mahmoody [0L0, we demonstrate a learning task that can be learned efficiently and robustly against computationally bounded attacker, while to be robust against an information-theorett attacker requires the learner to utilize significantly more parameters.
learners need.
Introduction
In recent years, deep neural nets with millions even billions of parameters [Wortsman et al., 2022, Dai et al., 2021, Yu et al., 2022] have emerged as one of the most powerful models for very basic tasks such as image classification. magic of DNNs is that they generalize without falling into the classical theories mentioned above, and hence they are the subject of an active line of work aiming understand how DNNs generalize Arora al. [2019], Allen-Zhu et al. [2019b,a], Novak al. [2018 8], Neyshabur et al. [2014], Kawaguchi et al. [2017], Zhang et al. [2021]. Arora et al. [2018h) 8bb]] and the various benefits of overparametrized regimes Xu et [2018], Chang et al. [2020], Arora et al. [2018a], Du et al. [2018], Lee et al. [2019]. In fact, the number of parameters in such models so large that it is enough to memorize (and fit) to a large number of rundom labels [Zhang et al.,
"CC Berkeley and NTT Research sanjamg @ berreleyy.du 1 University Wisconsin. Madison jha@ @eueesswee Peeesswwie www.ws..eedu Princetonn University sfar caar@prinnetoocom edu
$ University Virginia mohammad virginia.edu
"UC Berkeley mingyuan @ herkeley.edu
"See https: /tapps:/paapee /wwpr/pppppswweeeeeee thcode. com/ sota/ immaemmaaaaa classification on imagenet for the size of the most successful models for image classification of Imagenet.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

2021]. This leads us to our first main question, in which we investigate the potential cause for having large models:
Are there any learning lasks for which computationally bounded learners need utilize significantly more model parameters than needed cetermatiooo-thorrticlee
One should be cautious in how to formulate the question above. That is because, many simple iiformationthhooreticlly learnable) tasks are believed be computationally hard to learn (e.g., learning parity with noise [Pietrzak, 2012]). In that case, one can interpret this as saying that the efficient learner requires infinite number of parameters, possible at all! However, as explained above, we are interested in understanding the reason behind needing a large number of model parameters when learning is possible.
way of saying that the learning is not
Could robustness also a cause for overparameterizaaioon? A highly sought-after property of machine learning models is their robustness to the so-called adversarial examples [Goodfellow et al., 2014]. Here we would like to find a model f such that f(z) = f==) holds with high probability when < D is honestly sampled instance and x' s is a close instance that is perhaps minimally (yet adversarially) perturbed.' A recent work of Bubeck and Sellke [2021] showed that having large model parameters could be due to the robustness of the model. Here, we asking whether such phenomenon can have a computational variant that perhaps leads to needing even more parameters when the robust learner is running in polynomial time.
Are there any learning lasks for which computationally bounded robust learning comes at the cost of huving even more model parameters than non-robust learning?
In fact, it was shown by Bubeck et al. [2019] and Degwaker et al. [Degwekar al., 2019] that computational limitations of the learner could be the reason behind the vulnerability of models to adversarial examples. In this work, we ask whether the phenomenon investigated by the prior works is also crucial when the model size is considered.
Can computational intractability of adversary help? We ask whether natural restrictions on the adversary can help reduce model sizes. In particular, we consider the restriction to the class of polynomially bounded adversaries. In fact, when comes to robust learning, the computationally bounded aspect could be imposed both on the learner as well as the adversary.
Are there any learning tasks for which robust learning can be done with fewer model parameters when dealing with polynomial-time adversaries?
Previously, it was shown that indeed working with computationally bounded adversaries can help achieving robust models [Mahloujifar and Mahmoody, 2019, Bubeck et al., 2019, Garg et al., 2020b]. Hence, we are asking similar question in the context of model parameters.
1.1 Our results
In summary, we prove that under the computational assumption that one-way functions exist, the answer all three of our main questions above is positive. Indeed, show that the computational efficiency of the learner could be the cause of having overparametarized models. Furthermore, the computational efficiency of the adversary could reduce the size of the models. In particular, we prove the following theorem, in which a learning task is parameterized by X, a hypothesis class H. and class of input distributions (see Section 2.1 for formal definitions).
Theorem 1 (Main results, informal). If one-way functions exist. then for arbitrary polynomials n < a < 3 (e.g., n = 001 a..,aa= a= X5, 3 = 1)) over the following hold.
Part I: There is learning task parameterized by X and robustness bound (to limit how much an adversary can perturb the inputs) such that:
The instance size is (n)). (That is, the length of the input is ((n).)
There is a robust learner that uses (A) parameters.
Any polynomial-tin -ime learner needs ((a) parameters to learn the task.
The closeness here could mean that human cannot tell the difference between the two images x'.

---

Any polynomial -imeommeeeeeeeeeeeee learner needs ( parameters to robustly learn the task.
There is learning task parameterized by X and robustness bound (to limit how much an adversary can perturb the inputs) such that:
Part 2:
The instance size is (nn).
When the adversary that generates the adversarial examples runs in polynomial time, there is an (efficient) learner that outputs model with O(1) parameters that robustly predicts the output labels with small error.
Against information-theore (computationally unbounded) adversaries, no learner can produce model with < ((a) parameters that later robustly make the predictions.
In Sections 3 and 4, we explain the high-level ideas behind the proof's of the two parts of Theorem 1 and formalize these statements. The full proofs can be found in the supplemental material.
Takeaway. Here we put our work in perspective. As discussed above, prior works have considered the effect of computational efficiency (for both the learnr and the attacker) the robustness of the model. Informally, these works have shown that requiring a learner to be efficient hinders robustness, while requiring attacker to be efficient helps achieve robustness. Our work studies the effect of computational efficiency as well but focuses on the number of parameters of the model. In spirit, we have shown similar phenomenon. Namely, requiring learner to be efficient increases the size of the model, while requiring an attacker to be efficient helps reduce the size the model. Our results can be summarized as follows. In the non-robust case, requiring the learner be efficient increases the size of the model. In the robust case: (I) Requiring the learner to be efficient increases the size of the model. This holds for robustness against both efficient and inefficient attackers. (2) Restricting to only computational efficient attackers reduces the size of the model. This holds for both efficient and inefficient learners.
Limitations, Implications, and Open Question. Our work shows that the phenomenon of having larger models due to computational efficiency could provably happen in certain scenarios. It does not imply, however, that this holds for all learning problems. It a fascinating open question whether similar phenomena also happen real-world problems. We note that this is not particular to our work, but common to most prior works in the theory of learning showing "separation" results [Bubeck al., 2019, Degwekar al., 2019, Mahloujifar and Mahmoody, 2019, Garg al., 2020b].
Our results provides an explanation on why small but representative classes (e.g. layers neural networks) of functions do not obtain same (robust) accuracy larger models. This phenomenon that cannot be solely explained based on representation power of the function class might be due to computational limitations of the learning algorithm.
Finally, we note that our theorem demonstrates the separation by using the simplest setting of binary output. One can extend it to more sophisticated settings of any finite output, particularly real numbers with bounded precision. However, our work does not consider real numbers with infinite precision. In such cases, one needs to revisit computational efficiency, as the inputs are infinitely long.
2 Preliminaries
For distribution D, x D denotes that is sampled according to D. We use Us for the uniform distribution over S, and we use Un to represent U... For a set S, s < S means s +- Us For any two distributions X and Y over finite universe Ω, their statistical distance is defined as
1 SD SD(X,Y) = Pr
w]- -r = w|l-
We sometimes write X 2g to denote SD(X,Y) < For a vector I (I1, . kn) F and a subset S = (ii..... ir} C f1,2,..., n). denotes (Zi,...., Ri,). For any two vec- tors x = .i.......3 ... and y = (y1,.... ..), their Hamming distance is defined as HD(x, y) Hi E 21, mn] x4 F yi )- For set S and an integer 0 & & S), (9) represents the set of subsets of S of size t. stands for the indicator function. The base for all logarithms in this paper is 2.
3

---

2.1 Definitions related to learning and attacks
In this subsection, we present notions and definitions that are related learning.
We use X' to denote the inputs and y = {00.1 to denote the outputs or the labels. By 7. we denote a hypothesis class of functions from X' to V We use D to denote distribution over X' x V. A learning algorithm, takes a set S E (X' x 3)" and a parameter and outputs a function f that is supposed to predict fresh sample from the same distribution that has generated the set S. The parameter À is supposed to capture the complexity of the problem, e.g.. by allowing the inputs (and the running times) to grow, (E.g., this could be the VC dimension, but not necessarily so.) In particular, we assume that the members of the sets Xx V can be represented with (Aly(A) bits. A proper learning for a hypothesis class H outputs f E H. while improper learner is allowed output arbitrary functions. By default, we work with improper learning as we do not particularly focus on whether the learning algorithms output function from the hypothesis class. For a S S X' and a function h: X' + y by 8h we denote the labeled set {zz, h(x)) 2 E S}. For a distribution D and an oracle-aided algorithm A, by A we denote giving A access a D sampler.
Definition 2 (Learning problems and learners). We use F {Fx (x, xx, Ha)) to denote family of learning problems where each Hy is a set of hypothesis functions mapping X3, to V) and D is set of distributions supported on Xx.
For function E(::), ), we say L E-learns F if
AA N, Dx E D2, EH, E N; S-
E
[Risk(h, Dx, < <((A.)).
where Risk(h, Dx. Pr (h(z) + f(x)).
L outputs models with at most p(-) bits of parameters if E N; [Supp(L(,))) & 2P(A),
T. is an e-robust learner against (all) adversaries of budget r w.r.l. distance metric d if
VAEN, DA E DA. E HA, E N; ST [Riska, Dx, f]] < =(),n),,
E
where (is (h,, f) Pr [max ((((x)) M(x)) A A(d(x,, Er) DtDs
L runs in polynomial time if there is a polynomial poly(-) such that for all X E N and Se (x). the running time of L(S, A) bounded by poly(|S)- A).
L is an e-robust learner against polynomial-time adversaries of budget w.e distance if for any any family of -oly(A) (oracle aided) adversaries A = (A JAEN we have
VAEN E Dx, E HA Se-DgsfeLIsh ((S
Riska Dx, & e(),
Pr where (isk Dx, xt 1
[T(((=)) + [())) r))
2.2 Cryptographic primitives
Definition 3 (Negligible function). A function E()) is said to be negligible, denoted by =(A) neg)(A), if for all polynomial poly()), it holds that eA)) 11/poly(A) for all sufficiently large X.
Definition (Pscudorandom generator). Suppose a > X. A function f: {0, 13^ + {0, 1)as is called pseudorandom generator (PRG) for all polynomial-tinn probabilistic algorithm A, it holds that
Pr [A([())==1 2+1011JA
=
Pr (A(v) = = neg)
--(0,13-
The ratio a/> X is refer as the (multiplicative) stretch of the PRG.
Lemma 5 (Hástad et al. [1999]). Pseudorandom generators (with arbitrary polynomial stretch) can be constructed from any one-way functions.
A one-way function is function that easy compute, but hard to invert (see Definition 21).

---

Definition 6 (Signature scheme). A signature scheme consists of three algorithms (Gen, Sign, Verify).
(vk, sk) &- ): on input the security parumeter 1^, the randomized algorithm Gen outpuss a (public) verification key vk and (private) signing key sk.
Sign(sk, m): input the signing key sk and message m, Sign outputs signature
b (vk, m, o): input verification key vk, message and a signature Verify outpus a bit b, and = indicates tha the signature is accepted.
We require (secure) signature scheme satisfy the following properties.
Correctness. For every message m, holds that
Pr Verify(vk, m. o) =1: (vk, + Gen(1A)] Sign(ssk, m) = 1.
Weak unforgeability." For any PPT algorithm A and message it holds that
(vk, sk) Gen(1*)
m' + m and
Pr
a = Sign(sk, m) Verify(vk, m', ,0) (m',o') oo) + A(vk, m, o.
= neg)
Lemma (Naor and Yung [1989], Rompel [1990]). Signature schemes can be constructed from any one-way function.
2.3
Coding theory
Let IF be finite field. A linear code H. with block length and dimension h is a k-dimensional subspace of the vector space F". The generator matrix G E pkxx maps every message m E I its encoding, namely, the message m encoded minimum distance between any two codewords. That is, d (a.vEH))
G. The distance of the code H is the min HD(x, y). The rate of
the codeword defined as R= R-k/n. k/n.
Reed-Solomon code. In this work, we will mainly use the Reed-Solomon (RS) code. For the RS code, every message m (m,,..., m,) E F2 parsed as degree polynomial
f(x) = mi + m2 x ... + my k-1
and the encoding is simply (f(1,, (2)), f(n)) F
Definition 8 (List-decodable code). A code 7 S F" is said to be (p, d.-liis-decodable for any string F", there are & L messages whose encoding satisfies HD(x, c) & p.n.
n.. We say the code H. is efficiently (p, -i--ids--ecod if there is efficient algorithm that finds all such messages.
Lemma 9 (Guruswami and Sudan [1998]). For any constant R. > 0, the Reed-Solomon code with constant rate and block length is efficiently (1 /R, poly poll(nt))-iist-deeee -ist--ii--ecedablle
2.4 Randomness extraction
Definition 10 (Min-entropy). The min-entropy of a distribution X over finite set Ω is defined as
Pr [ (IX=w]] =l).
(x) = - llgg max wEn
We need the following result about the sampler. A sampler (for a target set of coordinates is a deterministic mapping that only takes randomness as input and outputs subset of ... n2) (1.2....,n))
11.2....,n.. n). Below, we let (!n)) {S [S] S [n]].
"We consider a rather weak notion of unforgability. Here, we require that the adversary cannot forge a signature when he is given only one valid pair of message and signature. This weaker security notion already suffices for purposes. In the stronger notion, the adversary is allowed to pick based the given vk.
5

---

Lemma 11 (Lemma 6.2 and Lemma 8.4 of Vadhan [2004]), For any 0 < K1, < 1 and any n, E M, there exists a deterministic sampler samp: {0, 13" + (in)) such that the following hold.
If X is a random variable over {0, 13"h with min-entropy 2 j there exists random variable Y over {0, 13 with min-entropy & (# k1) -f and
SD ( (Ur, Xsamp(U.)) (Ur. & exp(- + exp ( where the two Ur in the first joint distribution refer to the same sample.
Furthermore, r (n)
This lemma by Vadhan Vadhan [2004] states that one could use small amount of randomness to sub-sample from a distribution with the guarantee that sammp(U..) is close to another distribution Y that preserves the same min- min-entropy rate as X.
Due to space limitations, additional preliminaries are included in Appendix A.
3 Efficient learner vs. information-theoreti learner
In this section, we explain the ideas behind the proof of Part 1 of Theorem 1. We start with the high-level ideas behind our construction. Then, we formally state the construction of the learning task and its properties through formal statements. The proofs can be found in the supplemental material.
Consider the problem learning an inner product function IP P defined as p(z) (x, P). where the inner product is done in GF2, Our first observation is that to learn IPp with a small error where P uniformly random, the number of model parameters that the learner employs must be as (almost) as large as the length of P. Intuitively, one can argue it as follows. Let Z denote the parameters in the model that the learner outputs. Suppose that Z is shorter than P. Then P must still be unpredictable given Z. By standard result in randomness extraction, one can argue that, for uniform
(7, x. (z, P)) z (Z,, x, U(o.)))
That is, the label (I, P) looks information-theorrtiaalll theoretically uniform the classifier who holds Z and Therefore, the classifier can only output the correct label with (the trivial) probability = 1/2.
The conclusion is that learning all linear functions need learner that outputs as many parameters as the function's 's description is. However, even an efficient learner can perform the learning just as well informatiion-hhoretitt one (e.g., using the Gaussian elimination). We now show how modify this task to make a big difference between an efficient learner and an information-theoree learner in terms of the number of parameters that they output.
Computational perspective. Now, suppose P is computationally pseudorandom [Goldwasser and Micali, 1984] rather than being truly random." 11 That is, fet 10, + 10 be pseudorandom generator (Definition 4) and P is distributed as fUx),, where Ux denotes the uniform distribution over À bits. Since (1) an efficient learner cannot distinguish p + f(U)) from P t- Ua and (2) any learner who tries to learn IPp P with P < Ua needs a parameters, it can be proved that an efficient learner who tries learn IP with P f(Ux) must also uses parameters. However, an information-theoreel essentially find the seed such that P = fs) and output the seed To conclude, to learn IPp for P (Ux), an information-theoreti learner only needs a few (i.e., A) parameters and an efficient learner needs lot of (i.e., a) parameters. We emphasize that for a pseudorandom generator, its output length a could have an arbitrarily large polynomial dependence on its input length X. For instance, could be a 10
learner needs only parameters to learn IPr with P < f(Ux) as it can
Robustness. We now explain the ideas behind Theorem 15 in which we study the role of model robustness in the size of the model parameters. We now suppose the instance is sampled according to the distribution Do (parametrized by a string Q), which defined by
Enc(U) +.
1That is, with high probability over choice of Z = 2, the conditional distribution P(Z =2) has high min-entropy. More formally, this unpredicrability is measured by the average-case min-entropy (Definition 23). A pseudorandom string is indistinguishable from random for computationally bounded distinguishers.

---

Here, U is the uniform distribution (over the right number of bits), Enc(U) is an crror-corretio encoding of U, and the addition is coordinate-wise field addition. Moreover, the label for this instance is the inner product (U, P) for some vector P. Observe that if the learner learns Q, it can always find the correct label on a perturbed instance due to the error-correcting property of Enc(U). We argue that, in order to robustly learn this task for a uniformly random Q, the number of parameters in the model that the learner outputs must be almost as large as the length of Q. Intuitively, the argument is as follows. Let Z be the model that the learner outputs. Since |Z| [Q], then Q must still be unpredictable given Z. In this case, we prove that
(2, Enc(U) + +Q+ (Z.U".
Here, P stands for the noise that the adversary adds to the instance. In words, the classifier holding the parameter Z cannot distinguish the perturbed instance Enc(U) + Q + from a uniformly random string U.. Since U is informationttheoreticall hidden to the classifier, can only output the correct label (U, P) with probability ~ 1/2.
Next, explore the difference between an efficient and information- learner, we consider the case where Q is pseudorandomly distributed, i.e. Q + fUxx) for some f: 10, - {0. 13 Again, since (1) an efficient learner cannot distinguish Q <- Us from Q < ((Ux) and (2) any learner needs at least RV [Q] parameters to learn the task with Q + Ug. an efficient learner must also need least [Q parameters to learn the task. On the other hand, an information-theoreti learner could again find the seed s such that Q f(s) and output the seed s as the parameter. To conclude, an information- information-thhorrtiee theoretic learner requires few (i.e., A) parameters robustly learn the task and an efficient learner needs a lot of (i.e., R B) parameters to robustly learn the task. (Again, 3 could have an arbitrary polynomial dependence on X.)
Making instances small. The learning tasks we considered above suffer from one drawback: the size of the instance is very large, at least is related to the number of parameters of the model. Here ask: is it possible to have a small instance size while an efficient learner still needs to output a very large model? We answer this question positively. In particular, for any n poly()) (e.g., n 10.1), we construct a learning problem where the instance size is (n) and the efficient learner still needs (resp. 3) parameters to learn (resp. robustly learn) the task. Our construction uses the "sampler" by Vadhan [2003]. Informally, sampler samp (see Lemma 11) needs small seed and outputs a subset of { 2. . a} of size n. The sampler comes with the guarantee that if P is source with high entropy, Pl sumppp) also has high enough entropy. To illustrate the usage of the sampler, consider learning this new inner product function IPp defined as
IP IP)( = (xr, Plsamp(u))-
For uniformly random P, one can similarly argue that a model must output at least |P| parameters to learn the task. Let Z denote the parameters in the model that the learner outputs. If [Z] < [P], then P contains high entropy conditioned on Z. By the property of the sampler, it must hold that Pl Plaamp(u) contains high entropy conditioned on Z and u. Consequently,
(Z, u. IP (Pp(u,))) Ri (Z, u, x; U(0.1))-
Namely, the classifier who sees the parameter Z and the instance (u, x) can only predict the label with probability ~ 1/2. Observe that the size of the instance (u, x)) is roughly n, 12 while P could have length a > n. The use of the sampler in the robust learning case is similar to the non-robust case above. We refer the readers to Appendix B for more details.
To sum up, we present our formal construction and formal theorem statement below. The formal proof is presented in the supplemental material.
Construction 12 (Parameter-heavy models under efficient learning). Given the parameter n < X < 3, we construct the following learning problem. We rely on the following building blocks.
Let Si: (0,1)* + {o, 1) and f2: (0, 13 + {0, be PRGs (Definition 4).
Let Enc be a RS encoding with dimension k, block length n, and rate R ls n. The rate is chosen to be any constant < 1/3 and k is defined by R and n. This RS code is over the field Ez for some f (log A).
12 As the seed u is very small.
All the other parameters are implicitly defined by these parameters.
7

---

Let samp1 {0,1)* -
(1))))) and samp2: {0.1) - (m.)))) be samplers. We obtain these samplers by invoking Lemma 11 with sufficiently small H2 and R2 (e.g., Ri (11/log X) and sufficiently small constant K2). Note that Ki, K2 define ri, 12-
For any binary string v, we use [o] for an arbitrary error-correcting encoding of v (over the field IF 2e) such that [v] can correct > R)n/2 errors. This can always be done by encoding using RS code with suitable (depending on the dimension of v) rate. Looking forward, we shall consider an adversary that may perturb & (1-R)n/ /2 symbols. Therefore.
when string is encoded as [e] and the adversary perturb it to be [v], it will always be error-corrected and decoded back to u.
We now construct the following learning task Fx = Dh, H)).
Xx implicitly defined by the distribution Dx, and V> {0,
D consists of distributions D, for s {0, 13A, where D& is
D, = (lui), [u2], m, Enc(m) +
where
Mi and u2 are sampled uniformly at random from (0, 10,1) and {0, 13-2, respectively. m is sampled uniformly at random from F2.-
f2(() (am) is interpet as a vector over Fz and Enc(m) + (fz(s) samp2(22)) is coordinate- wise addition over E.z..
Hy consists of all functions ha : X + y {0, 1} for all s E {0,1),, where he is:
((m))(mm)))) (fi()) (amppsma))) (m.))
and the inner product is over F2 and m is interpreted as a string E F2- in the natural way.
Adversary. The entire input x = ([ur), [u2], m, Enc(m) + (f2()) (amp(())))(()) is interpreted as vector over Fz and we consider an adversary that may perturb & (1 R)n/2 symbols. That is, the adversary has a budget of (1 R2)n22 in Hamming distance over Ezt.
learner can (robustly) s-learn the task of Construction 12 with parameter size 2X and sample complexity (²)). Moreover, an efficient learner can (robustly) e-learn this task with parameter size a + 3 and sample complexity O 2(=+2).
Theorem 13. An information-theon
Theorem 14. Any efficient learner that outputs models with a parameters cannot E-learn Fx, of Construction for << 1/3.
Theorem 15. There exists some constant such that the following holds. the presence of an adversary that may perturb (1 - Ryn/2 symbols, any efficient learner for the task of Construction 12 that outputs a model with e B/ log parameters cannot e-robustly learn for e < 1//3.
Efficient adversary vs. information-theoreti adversary
In this section, we explain the ideas behind the proof of Part 2 of Theorem 1. At the end of this section, we formally state the construction of the learning task and state properties through formal statements. The proofs can be found in the supplemental material.
We now explore whether the computational efficiency of the adversary could affect the number of parameters required to robustly learn a task. Garg et al. [2020a] considered the difference between an efficient adversary and an information-theoretti one in terms of their running time. We first recall their construction. The learning instance is sampled from the distribution
[vk]. b, Sign b).
Here, (vk, sk) is the verification key and signing key pair of signature scheme (Definition 6); [vk] is an error-corredd corre-coreectig encoding of vk, which ensures that [vk] can always be recovered after perturbation by the adversary; b is uniform random bit and the label of the instance is simply b.
"Every instance samples fresh pair of verification key and signing key (vk, sk).

---

The signature scheme ensures that an efficient adversary cannot forge valid signature and, hence, any efficient adversary that perturbs (b. Sign(sk, b)) will result in an invalid message/signature pair. A classifier could then detect such perturbations and output special symbol I indicating that perturbation is detected. On the other hand, an information-theoreti adversary could launch a successful attack by forging valid signature (1 b, Sign(sk, instance to be [vk], 1 - b, Sign (sk, 6) and, hence, flipping the label of the output.
Therefoer it could perturb the
First idea. We want to construct a learning problem such that the learner needs few parameters against an efficient adversary, but lot of parameters against an information informatiin-theorriicc adversary. Our first idea is to add another way of recovering b in the above learning problem. Consider the learning problem where the instance is sampled from distribution Dp defined as
[vk], b, Sign(sk, b), [b + (u, P)], [m]--
Here, u is uniformly distributed. Observe that if the learner learns P. can recover correctly from [b (u, PI] and [u] by error-correction decoding. However, if the number of parameters in the model that the learner outputs have < |P] parameters, then [b + {u, Pb] and [u] information-theorrticall hides b. Again, this is because P is unpredictable given the parameter Zts and, hence,
Z, u, (u, P) ~ Z, u, (0,1).
Consequently, information adversary could again launch the attack that replace b, Sign(sk, b) with 1 b, Sign(sk, 1-b) and successfully flipping the label. Therefore, a learner must employ [P] parameters to robustly learn the task against information-theorett adversaries.
Second idea. In the above learning task, a learner employing |P] parameters can always recover the correct label against learner with fewer paramcters may not always recover the correct label but will sometimes output the special symbol 1 indicating that tampering is detected. Could we twist it to ensure that a learner with fewer parameters can also always recover the correct label against efficient adversaries? We positively answer this question by using list-decodable code (Definition 8). Intuitively, list-decoding ensures that given an erroneous codeword, the decoding algorithm will find the list of all messages whose encoding is close enough to the erroneous codeword.
cettmmatiio-thhorette adversaries. However, against efficient adversaries,
Our new learning task has instances drawing from the distribution Dp defined as
[vk]. LEn Sign(sk, b)), [6 + (u, Pb],
Here, LEnc is the encoding algorithm of the list-decoding code. The main idea is that: after the perturbation on LEnc(b, Sign(sk, b)), the original message/signature pair b, Sign(sk, b) will always appear in the list output by the decoding algorithm. Now, against an efficient adversary, b, Sign(sk, b) must be the only valid message/signature pair in the list. Otherwise, this adversary breaks the unforgeability of the signature scheme. Against an information-theoretiee adversary, however, it could introduce (1 Sign (k. b)) into the list recovered by the list-decoding algorithm. Consequently, the learner cannot tell if the correct label is b or b. Consequently, for this learning task, against -hoooatiin-theorttiicc adversaries, one still needs [P| parameters. Against efficient adversaries, one information- theoretic
needs only a few parameters and can always recover the correct label.
Making instances small. Again, we have this unsatisfying feature that the instance has the same size as the model. We resolve this issue using the sampler in a similar way. We refer the readers to Appendix C for more details.
We present our formal construction and theorem statement below. The formal proof is in Appendix C. Construction 16 (Learning task for bounded/unbounded attackers). Given the parameters < X a, we construct the following learning problem. 16 We use the following tools.
(Gen, Sign, Verify) be a signature scheme (see Definition 6).
Let LEnc be RS encoding with dimension k block length and rate R = k/n. We pick the rate R to be any constant <, 1/4 and k is defined by R and n. This RS code is over the field Fz for some = (log X).
Thaat is, with high probability over choice of Z 2, the conditional distribution P(Z has high min-entropy. More formally, this unpredictability is measured by the average-case min-entropy (Definition 23). All the other parameters are implicitly defined by these parameters.

---

Let samp: {0.1}" 7 (()...)) be samplers. (We obtain these samplers by invoking Lemma 11 with sufficiently small Hi and Kiz. For instance, setting 8i = (1/ log X) and Ki2 be any small constant suffices))
For any binary string v, we use for an arbitrary error-correcting encoding of v (over the field Fzz) such that [v] can correct > (1 RR)n errors. This can always be done by encoding using RS code with suitable (depending on the dimension of 0) rate. Looking forward, we shall consider an adversary that may perturb & (1 - v RRnn symbols. Therefore. when a string is encoded as [t] and the adversary perturbs it to be [e], it will always be error-corrected and decoded back to U.
We now construct the following learning task Fx = (2x, 2x, Hx))
Xx is 10,1) for some N that implicitly defined by Dx, and V> {0, 1}.
The distribution Dx consists of all distribution D& for 8 {0, 13a
D, = (Iu), [u], [vk], LEnc(b, Sign(sk, 6)), [b (v, slamp(())))) such that
sampled uniformly from {0, 1Y and is sampled uniformly from {0, 1)" - (vk, sk) t Gen(1>) are sampled from the signature scheme. b is sampled uniformly at random from (0, 1}. Sign(sk, b)) is intepreted as a vector in Why in the natural way.
hy consists of one single function h. On input x ([u), [e], LEnc(b, Sign b), [b (v, slssmm())))) h(z) simply decodes LEnc(b, Sign(sk, b)) and output
[v], Adversary. The entire imput [[u),[]], juk],
LEnc(b, Sign(sk, b)), [b + (v, ((am((())))) is inter- preted as vector over F2 and we consider an adversary that may perturb < (1 / Rym symbols. That is, the adversary has budget of (1 / RR)nff for Hamming distance over Fzz.
Theorem 17. For the learning task of Construction 16, there is an efficient learner (with 0 sam- ple complexity) that outputs model with no parameter and meg)())-robuatn learns Fx against computationalll-
adversaries of budget (1 (1-vV -Iyn.
Theorem 18. For computationally unbounded adversaries, any iioomationntheorees learner with a/2 parameters cannot E-robustly learn Fx, For < 1/3 for the learning task of Construction 16.
5
Acknowledgement
Sanjam Garg and Mingyuan Wang are supported by DARPA under Agreement No. HR001 12020026. AFOSR Award 149550-19-1-0220 Foundation, and Visa Inc. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Govermentt or DARPA. Mohammad Mahmoody is supported by NSF grants CCF-1910681 and CNS1936799. Somesh Jha is partially supported by Air Force Grant FA9550-18- 18-1-0166, the National Science Foundation (NSF) Grants
NSF CNS Award 1936826, and research grants by the Sloan
IIS- IIS-2008559, BrTC-Frontiers 1804648, CCF-20467 10 and CCF-1652140, and ARO grant number W91 17-1--111----55 Somesh Jha also partially supported by the DARPA-GARD problem under agreement number 885000.
References
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. Advances in neural information processing systems, 32, 2019a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pages 242-252, PMLR, 2019b.
10

---

Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterizzation. In International Conference on Machine Learning, pages 244-253. PMLR, 201 8a.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Learning, pages 254-263. PMLR, 201
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine- Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference Machine Learning, pages 322 332. PMLR, 2019.
Sébastien Bubeck and Mark Sellke. A universal law of robustness via isoperimetry. Advances in Neural Information Processing Systems, 34, 2021.
Sébastien Bubeck, Yin Tat Lee, Eric Price, and llya Razenshteyn. Adversarial examples from computational constraints. In International Conference on Machine Learning, pages 831-840. PMLR, 2019.
Xiangyu Chang, Yingcong Li, Samet Oymak, and Christos Thrampoulidis. Provable benefits of overparameterization model compression: From double descent pruning neural networks. arXiv preprint arXiv:2012.087749 2020.
Zihang Dai, Hanxiao Liu, Quoc V Le, and Mingxing Tan. Coatnet: Marrying convolution and attention for all data sizes. Advances in Neural Information Processing Systems, 34:3965-3977, 2021.
Akshay Degwekar, Preetum Nakkiran, and Vinod Vaikuntanathan. Computational limitations in robust classification and win-win results. In Conference on Learning Theory, pages 992-1028. PMLR, 2019.
Yevgeniy Dodis and Adam Smith. Correcting errors without leaking partial information. In Harold N. Gabow and Ronald Fagin, editors, 37th Annual ACM Symposium on Theory of Computing, pages 654-663, Baltimore, MA, USA, May 22-24, 2005. ACM Press. doi: 10. 145/1060590, 1000590.1000668090
Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam D. Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM J. Comput., 38(1):97-139 2008. doi: 137//3660 18066518811 1880. URL https://don org/10 10. 1137/06065380.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterizzed neural networks. arXiv preprint arXiv: 180.0004 2018
Sanjam Garg, Somesh Jha, Saeed Mahloujifar, and Mohammad Mahmoody. Adversarially robust learning could leverage computational hardness. In Aryeh Kontorovich and Gergely Neu, editors, Algorithmic Learning Theory, ALT 2020, 8-11 February 2020, San Diego, CA, USA, volume 117
of Proceedings of Machine Learning Research, pages 364-385, PMLR, 2020a.
Sanjam Garg, Somesh Jha, Saeed Mahloujifar, and Mahmoody Mohammad. Adversarially robust learning could leverage computational hardness. In Algorithmic Learning Theory, pages 385-385. PMLR, 2020b.
Shafi Goldwasser and Silvio Micali. Probabilistic encryption. J. Comput. Syst. Sci., 28(2):270-299, 1984.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572. 2014.
Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed-Solomon and algebraic- geometric codes. In 39th Annual Symposium on Foundations of Computer Science, pages 28 39, Palo Alto, CA, USA, November 8-11, 1998. IEEE Computer Society Press. doi: 10.1 109//SSS $998.743426.
Johan Hästad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudorandom generator from any way function. SIAM Journal on Computing, 28(4):1364-138) 1999.

---

Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio. Generalization in deep learning. arXiv preprint drXiv:1710.05468, 2017.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Advances in neural information processing systems, 32, 2019.
Saeed Mahloujifar and Mohammad Mahmoody. Can adversarially robust learning leveragecomputa- tional hardness? In Algorithmic Learning Theory, pages 581-609. PMLR, 2019.
Omar Montasser, Steve Hanneke, and Nathan Srebro. Ve classes are adversarially robustly learnable, but only improperly. In Conference on Learming Theory, pages 25 PMLR, 2019.
Joseph Naor and Moni Naor. Small-biaz probability spaces: Efficient constructions and applications. SIAM Comput., 22(():838-88) 856, 1993.
Moni Naor and Moti Yung. Universal one-way hash functions and their cryptographic applications. In st Annual ACM Symposium Theory of Computing, pages 33 33-43, Seattle, WA, USA, May 15-17, 1989. ACM Press. doi: 10.1145773007.70011
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv:1412.661 2014.
Roman Novak, Yasaman Bahri, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl- Dickstein. Sensitivity and generalization in neural networks: an empirical study, arXiv preprint 10Xiv:1802.08870, 2018
Krzysztof Pietrzak. Cryptography from learning parity with noise. In International Conference on Current Trends in Theory and Practice of Computer Science, pages 99-114. Springer, 2012.
John Rompel. One-way functions necessary and sufficient for secure signatures. In 22nd Annual ACM Symposium on Theory of Computing, pages 387-394, Baltimore, MD, USA, May 14-16, 1990. ACM Press. doi: 10.1 14.1145/10021.11 100269.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Salil P. Vadhan. On constructing locally computable extractors and cryptosystems in the bounded
storage model. In Dan Boneh, editor, Advances in Cryptology CRYPTO 2003, volume 2729 of Lecture Notes in Computer Science, pages 61-77, Santa Barbara, CA, USA, August 17-21, 2003. Springer, Heidelberg. Germany. doi: 10. 1007/977 3-540-45146-4
Salil P. Vadhan. Constructing locally computable extractors and cryptosystems in the bounded-storage model. J. Cryptol., 17(1):43-77, 2004.
Mitchell Wortsman, Gabriel Ilharco, Samir Yitzhak Gadre, Rebecca Roelofs, Raphael Gontijo-Lopes, Ari S Morcos, Hongseok Namkoong, Ali Farhadi, Yair Carmon, Simon Komblith, et al. Model soups: averaging weights of multiple fine-tuned models improves accuracy without increasing inference time. arXiv preprini SEKi::2203.04883 2022.
Ji Xu, Daniel Hsu, and Arian Malcki. Benefits of over-parameterizztion with em. Advances in Neural Information Processing Systems, 31, 2018
Jiahui Yu, Zirui Wang, Vijay Vasudevan, Legg Yeung, Mojtaba Seyedhosseini, and Yonghui Wu. Coca: Contrastive captioners are image-text foundation models. arXiv preprint arXiv:2005.01917, 2022.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115. 2021.
12

---

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]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(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]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(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 (c.g., type of GPUs, internal cluster, or 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? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) 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? [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": "xqlYa8M1s3C", "reviewer": "Reviewer_7oiG", "summary": "The paper considers the tasks of adversarial robustness and explores the difference between omniscient adversary, and the computationally bounded adversary. It constructs several learning tasks demonstrating the difference  between informatic theoretic and efficient learning.", "questions": "Do the results work also for infinite (and in particular, uncountable) domains? Such as learning something from real-numbered observations? Specially the number of parameters needs to be reconsidered here due to space filling curves.\n\nI'm sorry for such an uninformative review; it did not match my knowledge and I don't have the time to understand the relevant context.", "limitations": "-", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I did not find anything wrong with the paper, but I haven't understood its arguments either due to my limited knowledge of this area.", "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": "aPHzi_eEN6q", "reviewer": "Reviewer_WAyy", "summary": "This paper studies the computational benefits of overparametrization in standard and robust learning. The paper suggests that there are learning tasks where overparametrization is needed from a computationally efficient, standard and robust, learning. \n\nMore specifically, as I understand it,  the paper shows in Theorem 1 (Part 1) that there are learning tasks where “efficient” standard learning and “efficient” robust learning require polynomial (in the input/instance size) overparameterization. \n\nIn Theorem 1 Part 2, the paper shows that there are robust learning tasks such that there are efficient underparameterized learners against computationally bounded adversaries, but overparamertization is needed when the adversary is computationally unbounded (even for information-theoretically efficient robust learners). \n\nThe result indicates that there is a statistical-computational tradeoff between efficient robust learning and inefficient robust learning.\n", "questions": "In Theorem 1 Part 1, by checking Theorem 11, it seems that the sample complexity is also polynomially larger. I wonder if it is possible to obtain a result where the efficient learner only needs overparamterization but no increase in sample complexity compared to the information-theoretic learner.\n", "limitations": " It might be good to reflect on the results of the paper, and discuss their practical implications, and any future directions that might be good to address from this work.\n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I find the main result of the paper interesting. The gaps established in this work are polynomial (as opposed to exponential), but I think that’s still interesting from a practical perspective. The paper is rigorous and formal in its treatment of the definition of “efficient” learning, which is nice. The paper is clear and well-written.\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": "2CC1oXIyKmh", "reviewer": "Reviewer_Sv39", "summary": "This work studies whether there exist any learning tasks that are computationally bounded robust learning need to have more model parameters than non-robust learning; and whether such tasks can be done with fewer model parameters for polynomial-time adversaries compared with information-theoretic adversaries. The author gives positive answers to both of the questions by leveraging cryptography and coding theory.", "questions": "1. Missing formal definition of $L(\\cdot,\\lambda)$.\n2. In the main paper top of page 6 you discuss theorem 32, which is a restatement of theorem 13, and would be good to state theorem 13 before discussing it. In the statement of construction 10, you mention theorem 20 which also does not appear in the main paper. \n3. Personally I did not find it’s helpful to give construction 10 and 14 in detail in the main paper.  It’d be helpful to combine theorem 11, 12, 13, 15, 16 with their discussion or comments instead of isolating them separately.\n4. It seems to me that the argument of computational perspective on page 5 line 154-164 has a similar idea as the robustness on page 6 line 169-177, and I did not find any arguments regarding why $\\alpha<\\beta$, but this should be an important criterion in theorem 1. Can you claim what would happen if I replace $\\beta$ with $\\alpha$ in argument line 169-177?\n", "limitations": "Yes", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The questions asked by the work are interesting and novel to the best of my knowledge. Such studies would be helpful for the robust adversarial learning community. \nThe writing needs to have more structure improvement. However, since I’m not familiar with cryptography and coding theory, I’m not able to judge whether the technical idea is novel or sound.", "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