Characterization of Overfitting in Robust Multiclass Classification
Authors: Jingyuan Xu
Weiwei Liu
Venue: NeurIPS 2023 poster (2023)
Keywords: Learning Theory

Abstract: This paper considers the following question: Given the number of classes m, the number of robust accuracy queries k, and the number of test examples in the dataset n, how much can adaptive algorithms robustly overfit the test dataset? We solve this problem by equivalently giving near-matching upper and lower bounds of the robust overfitting bias in multiclass classification problems.

Characterization of Overfitting in Robust Multiclass Classification
Jingyuan Xu
Weiwei Liu"
School of Computer Science, Wuhan University
National Engineering Research Center for Multimedia Software, Wuhan University
Institute of Artificial Intelligence, Wuhan University
Hubei Key Laboratory of Multimedia and Network Communication Engineering, Wuhan University { iiigyuanxu777 wwwwwwwwwiieeee (eeeeeiiiii333)@mmalll com
Abstract
This paper considers the following question: Given the number of classes m, the number of robust accuracy queries k; and the number of test examples the dataset n, how much adaptive algorithms robustly overfit the test dataset? We solve this problem by equivalently giving near-matching upper and lower bounds of the robust overfitting bias in multiclass classification problems.
Introduction
Learning models that are robust to adversarial perturbations has garnered significant research attention in recent years. However, despite this progress, pervasive issue continues to plague these models, namely robust overfitting []. A common approach to overcome overfitting is to divide the dataset into training set, and holdout (or test) set. Nonetheless, modern machine learning is adaptive in its nature. Prior information about a model's performance on the test set inevitably influences future modeling choices in extensive experiments and competitions. Recent studies have shown that excessive reuse of the holdout dataset can also leads to overfitting in non-robust setting 2 Bl and a body of subsequent work has quantitatively explored this phenomenon in the framework of perfect test label reconstruction [4,5] 6]. Accordingly, in this paper we attempt to address the following questions: Can adaptive behavior result in overfitting in an adversarial setting? If so, by how much can adaptive algorithms robustly overfit the test dataset?
To solve these questions, generalize the framework of perfect reconstruction to the adversarial setting, and analyze the average case performance that can be achieved by an adaptive algorithm, denoted (k, n. m., where k, n, represents the number of robust accuracy queries, test samples and classes, respectively. This term equivalently measures the maximum level of robust overfit- ting in multiclass classification problem. In this paper, we derive both upper and lower bounds of hee (k, n, m), and demonstrate that our upper bounds and lower bounds are matching within logarithmic factors when and the distribution of test dataset features Dx are fixed.
1.1 Related works
Perfect test label reconstruction. The question of perfect test label reconstruction in non-robust setting dates back to decades ago 77] g 9]. The developments on studying biasing results due to adaptive reuse of the test data start with the work of 44] 10], which broadly fall in the field of adaptive data analysis [T [2]. (5] first pose the problem of characterizing the overfitting bias as a function of k. n, m, but they fail give upper and lower bounds the same order of m, which is left an open
"Correspondence to: Weiwei Liu <liuweiwei863 @ gmail.com>
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

question 13.. 6 close this question and determine the amount of overfitting possible in multiclass
classification. The theory on quantitative overfitting analysis in adversarial setting remains blank.
Adversarial robustness. It has been shown that deep neural networks are fragile to imperceptible distortions in the input space [1]. Perhaps the most common method improve adversarial
robustness is adversarial training [15 [6]. Theoretically, [17 18] 19 20 study the PAC learnability
of adversarial robust learning problem, and [21 [2] study adversarial robustness under self-supervised
learning. [23 24 investigates the adversarial robustness from the perspective of ordinary differential
equations. Besides, [25] analyze the trade-off between robustness and fairness,
26 study the
worst-class adversarial robustness in adversarial training.
2 Summary of our results
In the remainder of this article, R, . and R4 represent the sets of real numbers, natural numbers and d-dimensional vectors over R, respectively. We denote the set [l....,n] n (for n E N) by [ni] If A and B are sets, we use A denote the collection of all mappings from to B and 2 denote the power set of A, that is the collection of all subsets of A. We denote the indicator function by (event), that is 1 if an event happens and otherwise. If D is a distribution, we use supp(D) to denote the support of 'D which is defined by the closure of the set of possible values of a random variable having D as its distribution. Besides, || llp represents the lp norm and dp(::)) represents the distance function induced by L, norm. Finally, we use big tilde notations O and é as variants of big O notations that ignores logarithmic factors.
2.1 Problem formulation
Let Rdd be the instance space and y f1..... m] be the label space. Let 5 {(x,, )= denote the test set, whose features, denoted Xs- { ... }, Io
are independent and identically distributed (i.id.) according to some distribution Dx on x For simplification, we use = (ci, (CI,..., Cn) to describe the vector of test set labels. Let f X + y be a function, its robust accuracy
on the test set with respect to (w...t)) a small perturbation U X' + 2 is defined by
Accu (f:S) A
1 (((x.).f(x)) = c.).
The perturbation (z)) is required to be nonempty, so some choice of x' is always available. This paper focuses the case when the perturbation is the p-norm ball with a small radius r, i.c. U(x) = {2 E X : || - =|Ip S r) for some 2 1. r= O gives the identity perturbation: I(x) & fz). Note
that in this case, the definition of robust accuracy reduced standard (non-robust) accuracy.
In this work, we mainly study the robust overfitting attack algorithms, which do not have access to the test set S. Instead, they have query access to robust accuracy of the model on S, that is, for any classifier f, the algorithm is able to obtain the value Accy (f: We refer to this access as a query. A k-query algorithm A makes i queries f1...., fa on S, and based on the values of X's and Accu (f1; S), .S,..., Accu (fk; 5), A outputs classifier f A(S). We say a k-query algorithm A is based on hypothesis class H C yd if fi,..., S& E H. The performance of the algorithm on S is measured by
S) & E [Accu (f:S)),
where the expectation is over the algorithm's 's randomization. It is also of interest to ask the per- formance of an algorithm when ε are drawn according some distribution Dy over [m]". Let D = Dx x Dy, for an algorithm A, define its performance w.r.t. D by
(x(A;
A E hu (A:
S~D
And we evaluate the algorithms under the assumption that they do not have any prior knowledge about the test labels. That is, the prior distribution of test labels is uniform over all possible labeling:
bu
A
(A;
S
Formally, there is sigma algebra F C 2 of events and Dx probability measure (XFF)

---

where pm denotes the uniform distribution over [m]". Since the best robust accuracy is 1/m without making any queries (k 0), (r, S) 1/m measures how much robustly overfits S. The goal of this paper is to find the largest robust overfitting possible for a multiclass classification problem. So we define the performance that is achievable by an algorithm after making queries on any by
(k, n. m) _ max (AA),,
and we are interested in the value of hey (k, n, m) - 11/m m, or huck,, n, m) equivalently, In the rest of this paper, we aim at deriving bounds of (k, n, m) for given k n and m.
2.2 Our main results
Our bounds on he n,, m. have two different regimes, which can be summarized as the following theorem.
Theorem (Informal). let Dx be the distribution of test sample features. For Ó(ffm);
(v
k
1 S
DDx (n)
+
S her n, m)
+
m
mn
m
m
For (((/mm).
1 - ái (+) S bu n, S + +
1
D (n)
m
m
where DD (n) I 1 and is monotonically decreasing w.r.t. n2
When 21 I, upper bounds match the best known upper bounds [51, while lower bounds differ from the known optimal lower bounds 66] by a factor LD (n). Since overfitting in the context of robust learning has some requirements on the test samples (e-g- the well-separated property for different classes (27)), we may not able to ensure a non-trivial lower bound on hy m, n) for some Dx. Intuitively. & @D (n) measures how easily to sample n. 'good' (for robust overfitting) test data features from Dx. The specific form of &D (n) is presented in Section 3322 Note that for a fixed size of S whose features are i.i.d. according to fixed distribution Dx, the upper and lower bounds are matching up to a logarithmic factor, that is,
k mn
had (k. m.) =
+
h: = Ō(/mm)
m
and
k
bz (k, m)
θ
k = Ū((n/m)
m
n
for any fixed and xx.
2.3 Overview of our techniques
Next, we give a brief overview of proof techniques used to obtain the main results. We first note that throughout this paper use the notion of corrupted hypothesis (28), which transforms the formulation robust accuracy to a non-robust one thus greatly simplifying the proofs. The definition of corrupted hypothesis is presented in the beginning of Section 3
We establish the upper bounds via minimum description length argument, following closely proof of an analogous result by (5) for non-robust setting. Note that their bounds can be viewed as trivial upper bounds of (k, n, m.) since non-robust accuracy always upper bounds robust accuracy. We tighten the bounds by considering the query class of an algorithm. The details are presented in Theorem 2
To obtain the lower bounds, we propose computationally efficient algorithms for two regions of k respectively. The algorithms are modified from (6], who study the worst case overfitting bias in a non-robust setting. To take the perturbation features into account, we extend their queries to the whole feature space X' by assigning each label of æ E X' to be the 'closest" label in Xs the sense of p-norm. The theoretical guarantees are given in Theorems 3 and
3

---

2.4 Discussion
Although we equivalently derive both upper bounds and lower bounds of robust overfitting bias, there remains gap in finding whether the lower and upper bounds can match up to constant factor. In non-robust setting, it is proven that the vlog n factor in upper bounds can be removed for k = [ It is interesting to ask if this result holds for adversarial robust setting and, more ambitiously, for all k. We leave as an open question.
3 Proofs of main results
To make the proofs more readable, we introduce the notion of corrupted hypothesis 28
Consider given hypothesis f X'' - V. A labeled adversarial sample (ž, y) is classified correctly if i (v). A labeled example (x, v) is classified correctly (x:) fy) Let y y U {1},
where the special "always wrong" output, i.e. y f I. for every y E V. We define the mapping Ku yx ye:
Ku (z) (M. 11,
Sv, ((t)
otherwise.
The corrupted set of hypotheses induced by perturbation UI is then defined by H (Fu(f) : f H).
3.1
Upper bounds
The upper bounds relies on the following theorem, showing in a probabilistic view that finding a classifier in some given hypothesis class with desired robust accuracy requires learning many bits about the test labeling.
Theorem 2. Let m, n, k be positive integers and D Dx pm where pm denotes the uniform distribution over [m]]". Let H C yd be hypothesis class and U be perturbation. Then there exists a constant Ch S satisfying: For every H-based quque algorithm A, > 0, = k In(n 1)1 + In(1/6), we have
Cn
b mm
Pr SwDD m (=A(()
Accu (f:5)
+
2
8
<< m(log(n + 1) + log(1/6))
m
and
Pr SwDa.f A(S)
Aceu (J:S) Cи
2h
S 8,
n k: m(log(1= n + 1) + log(1/8))
Proof. For any fixed hypothesis f, denote ku()) by j. By the definition of corrupted hypotheses, for every i E [n],
(Va' E e((z)), = = xx-xx
Pr
Pr (f(z) = a} DNDD
Pr (f(x)) = c.l()))) 11} Pr (f(z:) #1} D,DD
DNDD
Pr (f(x,) c,f((x)) =1: Pr (f(x.) =1}.
xx>xx
x->Dx
We observe that Pr (f(x)) #1} is a constant related to f. let C(f) - Pr (f(x) }1}, since
Pr (f(x)) = cx)((ss)))))))))))))))()) =1} = 0, we have
Pr (Va' e U(x:), f(x) c;) Pr (f(z,)=clll #1} Pr (f(x:) #1} C()) Dxx
x,-Dx
This implies that 1 1f4x' E U(x;), f(x') c,} is Bernoulli random variables with bias Cl By the Chernoff bound, for any fixed f.
n
C(f) m
Pr SwDD
1 iVaa EU(x)), c.)
6 5
20(7
i=1

---

Denote jaxjeH C(f) by Cn, then
C( + C# +c] S Pr (f:S) 2 m
mone
Pr (Acou (f:S)
2 m
S C
20
holds for every f. Consider the execution of A with responses of robust accuracy fixed some sequence of values = (Ol,...,, E {0, 1/n,..., 1... Denote the resulting predictor by A its output distribution is fixed, hence by Eq. we have
Accu (f:S) 2 CH +c Se
mane 20 Time
Pr SwDA
Denote the set of all possible values of a by V. For every test S, the accuracy oracle outputs some responses in V. Therefore,
Accuu (f:S)2
CH m
Pr of A(S)
+r]
DrDD
Σ
Pr
(Accu (f:5)
Cи + E
S~ Dr. Au
nEV
S 1)kh
ICN Fme.
Now if Aln(++1)+h((1/8))
L m: then by definition of b,
2h > 2. It follows that me 2 2 2 2CH,
hence
mne? 2Cx+me
2
ne and 2
(n 1)*h e
In ô. 20 Hmm S e In(n++)) 1)-
k +)m(1+))+
1 in this case 2 nm I 2 We obtain that me < 2, thus mon? +- 4
mite
and
+ 1)th
mane 20
S e In(n++))
mire? =n 8,
and complete the proof.
The corollary below follows immediately from Theorem hu(k, n, (k,,,, m.)
2 which gives the upper bounds of
Corollary 1. Let m, n,n.k k be positive integers and U be perturbation, then
1 1 + +21
(k: + log(n + 1)
huck, m) <
k: < m m(lo((n + 1) + log(n))
m n
nm
and
1
2(k 1) log(n 1) +
(k, n, m) S
m
n
m[log(n + 1) + log(n))
Proof. Denote Accy (f: & X E [0. 1]. for any hypothesis class H. hence for k
Substitute 1/n in Theorem 2 and notice that Cz S
millg(n (ogg(n1))+oon +o)+)g((3)) have
(k + 1) log(n + 1)
Pr
X
+ 2
< -
(2)
Let 1 + 2 lo+1)log(++1) it remains to show EX S c 1/n. It is trivial for 2 1. For the case that < 1, let Px be the probability distribution of X, by the definition of expectation,
EX = f XdPx = ['xaPx+ L' XdPx sel. dPx [ dPx <axx sct n'
Jo
where we use the fact that 1.2 dPx 1/n by 2 in the last step. The case of k > m[log(n+1])4<mm) can be proved using similar arguments, and we complete the proof.
5

---

3.2 Lower bounds
The lower bounds of hie (k, n, m) are derived from two designed algorithms, namely Asmall and (C). Aemali is divided into cases based whether = 1, and the precise analysis is presented in Theorem A accepts parameter C' for calculating intermediate variable, and we gain our Theorem by setting C' DDx (n). Finally, the lower bounds of (k n, m) follow from
ha n, m) = max (A) 2 (y or A ( (n))).
To simplify the expression, we first introduce some definitions. For each As E x,, define
{ x X Fi # ja E [x]] s.t. (2, = (2, min d2(2,, mi) } iE(m)
rs
and
DDx (n)
min
d.pxx.
Ne (supp()))) JU(s)
where U(Ts) = x E } and Ppx is the distribution function of Dx. With these definitions, we present that:
Algorithm Aaamil (k =
1. Let (x) be the all one query, i.c. f) 1, EX.
2. Output f that
f(x) = [1 Vx E X, if Accu (f', 2 1/m,
Vx E EX, otherwise.
Theorem 3. Let m and D = D x um Then for 1 S k S n/2mm,
hre (Asmall D > (n)
(n)
8
Proof. Case: For / E [l,...,m. m., let Nt be the number of examples with label L. Since the labels are uniformly distributed and f is always a constant predictor, (N1,..., "1....,Ny ,N,) follows multinomial distribution with parameters (n:: m ..... of robustly and correctly predicted labels is then given by N₂ 1(N, n/m) + N₂ ( n/m)), and the expected robust accuracy is given by
). Then by the construction of f. the number
[hr (Ammlll S)] Ernyer
E
[N 1[N1 2 n/m3 + N2 L(N1 < n/m3]]
n
We conclude that
E Bripe
Thee (Ac(AAsmae smaall ;
1
+ 4 mn
m
by citing the following lemma:
Lemma 1 (Lemma 4 in (6).). Let 2 m > 2. If (N,.... multinomial distribution with parameters (ni m 1n) then
Nm) is distributed according to
1 n
E [N, 1(N, 2 n/m} + N2 L[N, < n/mm] >
m 4 m
Case: & > For fixed S, and hence, fixed f = Asmall for each E (1,.... m, 1}, let Nº be the number of examples in B, s.t. (x) = 1. Since whether Fi (z)((()) equals to '1' is only depends the distribution of x, we have that (N 3,1....... (NV,,1.....
i. NS follows multinomial distribution with parameters ([B,); C(S) C(S) 1 C(S)), where C(S) Pr (mU(f) $1}.
NS

---

Algorithm 2 A (k
1. Divide [r]] into k blocks Bi...., BE-1 such that
k-1 <
m
[B:
< 2[k-1)
for each i.
2. For 1 sis k, define query fo satisfying:
Ji(2;) {2.
1, if E U U...U
otherwise.
for 2j E A's and
fe(x) = Si(ry), where j' = arg min dz (2,
JE(n]
for & Xs.
3. Output f. predicts xy by the following:
for all B,, if Accu (Jtt1, 2 Accu (fi: S), f(z)) 2 for j B,, otherwise.
and predicts the of æ by f(x) f(zy)), where j' arg min 2x,
Then our predictions robustly and correctly predicts max(NE, N
examples in B, and hence
bu (A: - max(N N }- We will show it later that
NS C(S)
1 4
C(S)
E [max ( 611 1.2 2
By summing the blocks, lower bound the expected total number of robustly correct predictions made by A Aemall
C(S)
k - 1 m 4 V
C(S) C(S)
1 88
C(S) nk
E [ N N 1
2(k: 1)m
m
m
To obtain lower bound of C(S) that is independent of the choice of S, for each we define gs satisfying:
gs(x) = c; (Z5(2))) where j' = arg min dz(x, xÿ)
Vx E X's: otherwise,
and let H., {gs S (supp(Dxx ")"). It easy to see that small E H., for all S. Hence by the definition of 4D. (n), we have
(n) = min Pr (Ne(g,))(()) #13 S C(S). gsEHn.
We conclude that
@D (n) n S
@D (n) nk m
max (N
8
m
Normalizing by proves the desired result.
It remains lower bound E |max ( N1 Since N and N follow binominal distribution
with parameters (IB,): C(S) ), E 11 + N 2C[5]]B] for all S. Let N' be independent copy

---

of N N and N' are negatively correlated, hence
C(S)
E [[ N..21
N'
No
[:]
m
E
(NE) C(S) [B:12
2
C(S) Bi
C(S)
2m
m
C(S) B:
4m
For all S.
Then we conclude that
NS
+
NE,
INS.
No
C(S)BBi
C
max N NS 1,1: 1.2
+
1,1
2
2
2
which completes the proof.
We then present A (C) and the theoretical analysis for & = 9(n/m))
Algorithm 3 (C)
1. Let = 1 + ml
Ck
2. Define query f1...., fA satisfying:
(a) For i < Ji (..) Su (2y) that have each element in [mi] appearing exactly k/m times.
are uniformly chosen from all sequences in [m]]
(b) For j > fi(z))
for all I.....k. k. (c) For x & Xs. f((x) = f((xy) for each i E [k],, where j' = arg min dp(x, x2))
3. Output f such that:
arg maxyelm) Exs(C Accu (f: S
15ist,
f(x,)) = 11,
j>t. t.
and predicts the of a by f(x) (xy), where j' arg min xz)
Theorem 4. Let log and let Dn = D' x pmo
Dox (n)
PD (n)
pDx (n) k 144n log m
bu (ii 4 (n)), D
+
Proof. For E [m], let A, be the total number of robustly and correctly predicted examples by all the queries that predict the first examples as 't', i.e.
A n
Σ
Accu (f: =
Σ Σ 1(f(22) = Uj. us, Va' u(x,))
War (()
wid ((
-Wo - 111= +
Σ
-)((d)=,, e((x)))
(3)
where Wo < m
the number of queries that predict the whole perturbation set (((1)) as 'y1".
Brreaking ties randomly.

---

Let
M =
Σ
Σ 1 =n, Ve' E u((;))),
then for 1 + V1:
An - A Wo My Mr.
Since 1 (f((x') = Mj Yx' E ([r)) } are independent for * j', and are negatively associated across i for any fixed j, therefore, by the Chernoff bound, satisfies that for e <
2
Pr [IM - [M]] > CE [M]] - 2xx(( [M]).
3
Suppose satisfies that E [M]] S
A
and
- 3
E [M]] 2 3 log m, then by Eq.
3
and the union bound
2m
Pr arg max A + 11 } < (m 1) m3
2
1
[E(m]
4'
and with probability at least 3/4, y1-
We now derive the bounds proof Theorem Let H., denotes the corrupted set of Hn. For each 9 E He, define タ1 : X + ý that takes value 'I" on (x,,) for =t I,..., and coincides with ğ otherwise, that is.
To this end, first need bound E. [M)) Define Hr that in the
x E otherwise.
(x;z),
(1(T) [g(z),
Let Gn be the set which contains all such g1 It is easy to see that that mingeg Pr (g(x)) + = @D (n), we have
E 9n. Note
D (n) = 1(f((²)) Us Va E {4({z)) =
m
m
Now for each by the linearity of expectations,
DD (n)
k 1
()
S SRM S (1 - 1)
m
m
m m
Thus EE [M]] holds for
m
k
m
S (1
1)kk
2m
2(1 - 1) m² @ (1-)
and [[M] 3 log holds for
9
log
Therefore, can find suitable
whenever
m²
9 log m
5
DD ( - 1)h
2(t - 1)
4 D (n)j
we choose / - +
36 log and l: TD (n) ( log m, the aforementioned conditions hold. Note
that Pr (f) #L} 2 DD (n), hence the expected number of robustly and correctly predicted
labels is at least
LD (n)
D (n)
D (1))
4Dx (n) n 4Dx (m) k
(n 1)
+ 11
144 log
which completes the proof.
Conclusion
In this work, we study the overfitting bias in the context of robust multiclass learning. We formally define the adaptive algorithms an adversarial setting and analyze the average case performance that can be achieved by an adaptive algorithm. Upper bounds and lower bounds are both derived, and are matching within logarithmic factors when the number of test samples and distribution of data features are fixed.

---

Acknowledgements
This work is supported by the National Natural Science Foundation of China under Grant 61976161, the Fundamental Research Funds for the Central Universities under Grant 2042022rc0016.
References
[1] Leslic Rice, Eric Wong, and J. Zico Kolter. Overfitting in adversarially robust deep learning. In ICML, volume 1 119, pages 8093 8104, 2020.
[2] Avrim Blum and Moritz Hardt. The ladder: A reliable leaderboard for machine learning competitions. In ICML, volume 37 of JMLR Workshop and Conference Proceedings, pages 1006-1014, 2015.
[3] Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? ICML, volume 97 of Proceedings of Machine Learning Research, pages 5389-5400, 2019.
[4] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In STOC, pages 117-126, 2015.
[5] Vitaly Feldman, Roy Frostig, and Moritz Hardt. The advantages of multiple classes for reducing overfitting from test reuse. In /CML, volume 97, pages 1892-1900, 2019.
[6] Jayadev Acharya and Ananda Theertha Suresh. Optimal multiclass overfitting by sequence reconstruction from hamming queries. In ALT, volume 117 of Proceedings of Machine Learning Research, pages 3-21, 2020.
[7] Paul Erdos and Alfréd Rényi. On two problems of information theory. Magyar Tud, Akad. Mat. Kutató Int. Közl, 8:229-243, 1963.
[8] Vasek Chvátal. Mastermind. Combinatorica, 3(3):325-329, 1983.
[9] Nader H. Bshouty. Optimal algorithms for the coin weighing problem with a spring scale. In COLT, 2009.
[10] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. The reusable holdout: Preserving validity in adaptive data analysis. Science, 34966248):636-638, 2015.
[11] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. Generalization in adaptive data analysis and holdout reuse. In NeurlPS, pages 2350-2358, 2015.
[12] Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algorithmic stability for adaptive data analysis. In STOC, pages 1046-1059, 2016
[13] Vitaly Feldman, Roy Frostig, and Moritz Hardt. Open problem: How fast can multiclass test be overfit? In COLT, volume 99 of Proceedings of Machine Learning Research, pages 3185-3188, 2019.
[14] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR, 2014.
[15] Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adver- sarial examples. In ICLR, 2015.
[16) Zekai Wang, Tianyu Pang, Chao Du, Min Lin, Weiwei Liu, and Shuicheng Yan. Better diffusion models further improve adversarial training. ICML, volume 202 of Proceedings of Machine Learning Research, pages 36246-36263 2023.
[17] Dong Yin, Kannan Ramchandran, and Peter L. Bartlett. Rademacher complexity for adversari- ally robust generalization. In ICMI., volume 97 of Proceedings of Muchine Learning Research, pages 7085-7094, 2019.
10

---

[18] Omar Montasser, Steve Hanneke, and Nathan Srebro. VC classes are adversarially robustly learnable, but only improperly. In COLT, volume 99 of Proceedings of Machine Learning Research, pages 2512-2530, 2019.
[19] Jingyuan Xu and Weiwei Liu. On robust multiclass learnability. In NeurIPS, 2022.
[20] Zhengyu Zhou and Weiwei Liu. Sample complexity for distributionally robust learning under chi-square divergence. Journal of Machine Learning Research, 24(230):1-27, 2023.
[21] Zekai Wang and Weiwei Liu. Robustness verification for contrastive learning. In ICMI,, volume 162 of Proceedings of Machine Learning Research, pages 22865-22883, 2022.
[22] Xin Zou and Weiwei Liu. Generalization bounds for adversarial contrastive learning. Journal of Machine Learning Research, 24: 14:118 14:1-111::4 2023.
[23] Hanshu Yan, Jiawei Du, Vincent Y. F. Tan, and Jiashi Feng. On robustness of neural ordinary differential equations. In ICLR, 2020.
[24] Xiyuan Li, Zou Xin, and Weiwei Liu. Defending against adversarial attacks via neural dynamic system. In NeurlPS, 2022.
[25] Xinsong Ma, Zekai Wang, and Weiwei Liu. On the tradeoff between robustness and faimess. In NeurIPS, 2022.
[26] Boqi Li and Weiwei Liu. WAT: improve the worst-class robustness in adversarial training. In Brian Williams, Yiling Chen, and Jennifer Neville, editors, AAAI, pages 19982,14990, 2023.
[27] Yao- Yuan Yang. Cyrus Rashtchian, Hongyang Zhang, Ruslan Salakhutdinov, and Kamalika Chaudhuri. A closer look at accuracy vs. robustness. In NewrlPS, 2020.
[28] Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal, Pac-learning in the presence of adversaries. In NeurlPS, pages
2018.


Reviews:
[{"review_id": "TwbVCaFPTU", "reviewer": "Reviewer_UhYx", "summary": "The authors present near-matching lower and upper bounds for the robust accuracy of an adaptive algorithm having a budget of k accesses to the oracle of accuracy on a test set of size n and m classes.", "questions": "No", "limitations": "No", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The proof is really clear and pedagogical. The related work is clear.", "weaknesses": "The problem is not well sold nor introduced. I had to look at the problem formulation to understand what the authors were intending to do. While related work is abundant, more space can be used for explaining what are the goals of the paper for new readers. And the conclusion could be more than just a summary, starting future work.\n\nAlso, as the authors are humble, they are borrowing tools from several existing proofs so it is not clear whether this is a breakthrough or incremental work. Still, it is nicely put.\n\nMinor comments:\n\"binominal\" => binomial", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the time you've dedicated to reviewing our work. We would like to highlight the originality of our proof techniques, which are outlined as follows.\n\nOn one hand, the upper bounds' proof technically differs from proofs in the standard case derived by [1] from the following 3 parts:\n\n1. To take the adversarial perturbation into account, we use Bayes' formula to represent the robust accuracy of a single sample by a Bernoulli r.v. parameterized by $C(f)$. This procedure is quite trivial in the standard case. \n\n2. As discussed in Section 2.3, we introduce the notion of hypothesis class to upper bound $C(f)$, which makes our bounds tighter. \n\n3. Some inequality scaling techniques, e.g., Eq.(1) in Line 125 and the inequalities at the end of the proof in Lines 132-135.\n\nOn the other hand, Compared to [2],  our technical novelty can be summarized as follow:\n\n1. To expand the domain from $\\mathcal{X} _S$ to the entire $\\mathcal{X},$ we borrow the idea of nearest neighbors algorithm. This construction is proved to be optimal (up to logarithmic factors) for fixed $n$ and $\\mathcal{D} _\\mathcal{X}$). \n\n2. In the proof of Theorems 3 & 4. the introduction of corrupted classes is very elegant, without whom one may not be able to derive the distribution of $(N^S _{i,1},\\dots,N^S _{i,m}),$ which is crucial in the standard case to prove the lower bounds. This is because the output $\\hat{f}$ may **always** predict a label that is not robust to adversarial perturbation. In other words, some samples may be not to be counted. So the \"always wrong\" label, i.e. $\\perp,$ not only facilitates our deduction, but also instruct us to study the distribution of $(N^S _{i,1},\\dots,N^S _{i,m},N^S _{i,\\perp}),$ which makes the counting well defined. \n\n3. In addition, there is a step to deriving lower bounds on $\\textbf{Pr}\\\\{\\kappa _\\mathcal{U}(\\hat{f}(x))\\neq\\perp\\\\}$ in both proofs of Theorems 3 & 4, (Lines 174-177 & Lines 197-201) which has no parallel in previous works. \n\n4. In our Algorithm $\\mathcal{A}^{big}(C),$ the step 2.(b), we make $f _i(x _j)=\\perp$. This construction makes the value of $A _l$ (Eq. (3) in Line 189) in our proof differs from that in [2], but the equation $A _{y _1}-A _l=W _0+M _{y _1}-M _l$ in Line 192 still holds so we can continue the proof. However, one can prove that this is not the case when the queries are designed such that $f _i(x _j)=1,$ as constructed in [2].\n\nWe will add more discusstion about this part in revision. Thank you again for checking this out.\n\n*Reference*\n\n*[1] Vitaly Feldman Et al. \"The advantages of multiple classes for reducing overfitting from test set reuse.\" ICML 2019*\n\n*[2] Acharya Et al. \"Optimal multiclass overfitting by sequence reconstruction from Hamming queries.\" ALT 2020*"}, {"review_id": "VVhPluWh7m", "reviewer": "Reviewer_JGWq", "summary": "This paper studies bounds on the maximal difference between the robust accuracy of a classifier on the test set. Here, robustness means when each instance is allowed to move within a given radius within an $L_p$ ball, and the maximal difference is obtained with respect to $1/m$, where $m$ is the number of classes. \n\nThe classifier's accuracy is obtained through querying an algorithm, and lower/upper bounds are obtained in terms of the number of queries made, the number of elements in the test set and the number of classes. ", "questions": "Questions\n---\n\n(wrap up weakness points for some)\n\n* Would it be possible to provide a slight illustration of the discussed results, or to give pointers to practical uses of these results? \n\n* The idealistic assumptions made in the paper (well-separatedness, label uniformity) are rarely met in practice. It is not clear how limiting this is, would one apply the obtained bounds in a practical setting? \n\n* I did not find in the paper a discussion about the quality of the provided bounds: can they expected to be tight? How useful are they likely to be in practice? \n\nSuggestions\n---\n\n* Some typos remain in the paper (e.g., in Theorem 2: an perturbation, $b=k ln(n+1)1$, L171: \"we will show it later than\")\n\n* Some parts of the proofs and technical aspects could be clarified by adding some steps that I missed while reading it. As examples:\n   * P2, L39: it may be obvious, but what is the \"closure\" here (are we speaking about a specific closure operator?)\n   * P5, L131: the derivation of $m\\epsilon \\geq 2 \\geq 2 \\mathcal{C}_\\mathcal{H}$ is not immediate to me, maybe add a step?\n   * P6, L161-L162: I do not see how we can obtain the numbers of correctly predicted labels only depend on the $N_m$, and also why it should only depends on $N_1,N_2$? \n", "limitations": "See weaknesses and questions comments about the initial assumptions. ", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* A concise paper that, for once, does not have tons of supplementary material. \n\n* A rather rigorous treatment of the problem, with the paper consisting almost entirely of providing the proofs of the results. I think the results presented are correct (but this is not in my main area of expertise, so I could have missed something, and it would be necessary to be checked by a more expert reviewer foxued on this area of research)", "weaknesses": "* Better motivation of the results through illustration/practical problem mention: the paper focuses on providing a rigorous bound proof for a particular setting (robust overfitting), and assumes that the reader is convinced of the importance of the problem. In this sense it is quite focused, and it would have been nice for the reader to have at least some indication of the practical setting where this result could be used, or even better a little illustrative (synthetic) example of the situation one would like to deal with. This could be done, e.g., by dropping Lemma 1 proof if this one is available elsewhere (Lemma 4 in [6], according to the paper), as it takes almost one pages.\n\n* Clarifications about the assumptions and their limitations: in order to obtain the provided results, the paper makes some key assumptions whose limitations and need should be discussed in more details. Two main examples of this are the following: \n\n   * Well-separatedness of the classes is mentioned P3, L3 (note: it is not mentioned this way in reference [14]) seems equivalent to assume a dceterministic relationship between input and classes, with furthermore the requirement to be separated by \"large margins\", so basically assuming that one is working under a version space assumption. There would be a need to clarify that, to discuss how realistic this is, and how it can impact the provided results\n\n  * Uniformity of the labels: another assumptions is that the output labels are perfectly uniformly distributed. This is unrealistic in most practical settings, and it is not clear how the results would change in case of imbalanced classes (goign from a slight departure of this prior information to a large one). \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our work and your considerate suggestions. Here are responses to your concerns.\n\n**About the results.**\n\nWe apologize for our presentation. Motivated by [1] and [2], the question we focus on is: Can excessive reuse of test datasets lead to overfitting in robust learning setting? The answer to this question is implied in our Theorem 1. For fixed number of classes $m$ and fixed number of test examples $n,$ the lower and upper bounds of $h_\\mathcal{U}$ is at least $\\tilde{\\Theta}(\\sqrt{k}),$ which states that one can expect better performance with more queries made to the test set. So the answer is positive. \n\nAs for the practical setting, for example, in modern ML benchmarks for adversarial robustness (e.g. RobustBench), hundreds of results have been reported on same test sets (e.g. ImageNet, SIFAR100). Large-scale hyperparameter tuning and experimental trials across numerous studies likely add thousands of queries to the test data, which may substantially \"improve\" robust accuracy according to our results. Our results may suggest to limit the query time or develop some monitoring mechanism to avoid malicious reuse of test sets, which, however, is far beyond the scope of this article.\n\nAll in all, thank you for the suggestion, we will add some discussion about this part in revision.\n\n**About the assumptions**\n\nSorry again for the confusion caused by our presentation.\n\n1. Actually we do not make the well-separated assumption. We mention this concept to emphasize that the term $\\Phi_{\\mathcal{D}_\\mathcal{X}}(n)$ is unavoidable if we make no assumption on the distribution of the data feature. In fact, one can easily show that under the well-separated assumption, our setting degenerates into standard perfect label reconstruction problem. \n2. Following [2], we assume the label to be uniform distributed since the algorithms have no prior knowledge about the test labels (as we state in Lines 63 & 64). Many experiments have also been conducted under this assumption, such as [3][4].\n\n**About the quality of our bounds**\n\nThe quality of our bounds are discussed in Lines 83-84: \"Note that for a fixed  size of  $S$ whose features are i.i.d. according to a fixed distribution $\\mathcal{D}_\\mathcal{X}$, the upper and lower bounds  are matching up to a logarithmic factor.\" \n\n**About the typos and suggestions on proofs and technical aspects**\n\nWe appreciate your careful review of the article and point these typos out, we will fix them in our final revision. The following is our response to your suggestions one by one:\n\n1. Thank you for your suggestion, we will define the \"support\" more explicitly in revision.\n2. The derivation $m\\epsilon\\geq2$ is obtained by setting $\\epsilon=\\frac{2b}{n}$ (see the second formula in Theorem 2), and we do miss it in our proof. We will perfect this proof in revision.\n3.  The numbers of correctly predicted labels only depend on $N_1$ and $N_2$ follows from the construction of our Algorithm 1, whose output $\\hat{f}$ only predicts labels $1$ and $2.$\n\n*Reference*\n\n*[1] Vitaly Feldman Et al. \"Open problem: How fast can a multiclass test set be overfit?\" Colt 2019*\n\n*[2] Vitaly Feldman Et al. \"The advantages of multiple classes for reducing overfitting from test set reuse.\" ICML 2019*\n\n*[3] Cynthia Dwork Et al. \"Generalization in Adaptive Data Analysis and Holdout Reuse\" NIPS 2015*\n\n*[4] Cynthia Dwork Et al. \"The reusable holdout: Preserving validity in adaptive data analysis\" Science 2015*"}, {"review_id": "5Ng6Qnp47D", "reviewer": "Reviewer_5K3z", "summary": "This paper considers the problem of learning from data while being robust to the possible transformations of these data. A common practice in machine learning is to split data into a training and a test set. The latter is a holdout to evaluate the performance of the algorithm. However, recent studies have shown that reusing many times this holdout set leads to overfitting in non-robust settings. This paper questions the problem of adaptivity in an adversarial/robust setting.", "questions": "Suggestions:\n- recall what are $O, \\Omega$ and $\\Theta$\n- define $\\widetilde{O}, \\widetilde{\\Omega}, \\widetilde{\\Theta}$ even if it seems to be trivial for the authors,\n- add an experimental section with experiments at least on simulated data and, better, on real datasets to illustrate the different theorems.\n\nQuestion:\n- are these $\\widetilde{O}, \\widetilde{\\Omega}, \\widetilde{\\theta}$ a classical tool in your community? Why not expose the full bound with the logarithm factor? Does it help the interpretation?", "limitations": "No limitations are declared in the paper. The paper is theoretical and seems far from having a possible negative impact.", "rating": 7, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The authors present a very theoretical work on robustly overfitting the test set of adaptative algorithms. They show an excellent understanding of the theory behind this problem. Remarkably, the upper bounds in the Theorem 1 match the ones of the literature when $\\mathcal{U} = \\mathcal{I}$ (no transformation of the set, i.e. no adversarial setting). Furthermore, for a fixed size of $S$, the test set, whose features are i.i.d. according to a fixed distribution, the upper and lower bounds match up to a logarithmic factor.", "weaknesses": "The paper is hard to follow for someone unfamiliar with the topic like myself. The Neurips conference gathers people from a broad audience, and this must be taken into account. In particular, no experimental part in the paper limits its impact on the community. Some numerical experiments could help understand how this work can be applied and its limits for future directions. Adding a toy numerical example could also motivate us why we should care about the question the authors ask in the abstract.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your for reviewing our paper. It is worth acknowledging that numerous studies have already indicated the presence of overfitting phenomena in adversarial training, e.g.,[1]. To this end, our paper is devoted to a certain **theoretical** question related to this phenomenon, that is, whether adaptively excessive reuse of test data leads to overfitting in robust learning. Our results answer this question in the affirmative and suggest that one can expect better performance with more queries made to the test data.\n\nThe $O,\\Omega,\\Theta$ notations, as known as the big O notations, are asymptotic notations. we occasionally use them to clarify the main results. They are common in computer science & machine learning community. They are defined as follows:\n\nGiven $f: \\mathbb{R} \\to \\mathbb{R} _{+}$ and $g: \\mathbb{R} \\to \\mathbb{R} _{+}$ we write $f=O(g)$ if there exist $x _0,\\alpha\\in\\mathbb{R} _+$ such that for all $x>x _0$ we have $f(x)\\leq\\alpha g(x).$ We write $f=\\Omega(g)$ if there exist $x _0,\\alpha\\in\\mathbb{R} _+$ such that for all $x>x _0$ we have $f(x)\\geq\\alpha g(x).$ The notation $f=\\Theta(g)$ means that $f=O(g)$ and $g=O(f).$ Finally, the notation $f=\\tilde{O}(g)$ means that there exist $k\\in\\mathbb{N}$ such that $f(x)=O(g(x)\\log^k(g(x))).$ The notation $f=\\tilde{\\Omega}(g)$ and $f=\\tilde{\\Theta}(g)$ are defined analogously.\n\n*Reference*\n\n*[1] Leslie Rice Et al. \"Overfitting in adversarially robust deep learning\" ICML 2019*"}, {"review_id": "09Jk6BDvE3", "reviewer": "Reviewer_YY54", "summary": "In this paper, the authors consider the following question: Given the number of classes m, the number of robust accuracy queries k, and the number of test examples in the dataset with size n, how much can adaptive algorithms robustly overfit the test dataset? They solve this problem by giving upper and lower bounds of the robust overfitting accuracy in multiclass classification problems.", "questions": "1.What's mathmatical definition for \\O, \\Omega, and \\Theta? They are not defined in the paper.\n\n2. Line 56-69: The definition of k-query is not reader-friendly. It's better to have some examples and figures. Could you provide a detailed explanation?\n\n3. In Lines 49-52, the perturbation is defined with radius r. However, in all main results, they don't contain r, and have no restriction on r. The result would be different between a tiny and a huge r. Could you explain the relation between accuracy and r?", "limitations": "This paper doesn't include limitations and the negative societal impact of their work.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. Robust classification and adversary perturbation are valuable topics in the learning theory community.\n2. Some adaptive algorithms are proposed and could be useful in practice.", "weaknesses": "Major\n1. The paper structure is not very clear. The algorithms are defined after the main results. It's very confusing.\n2. Line 56-69: The definition of k-query is not reader-friendly. It's better to have some examples and figures.\n3. Line 63-65: The assumption that the labels are uniformly distributed is very restricted and not general. It makes the study has limited practical and theoretical contribution. \n4. The gap between the upper and lower bound is large, which makes the two bounds have limited theoretical and practical contributions.\n5. In Lines 49-52, the perturbation is defined with radius r. However, in all main results, they don't contain r, and have no restriction on r. The result would be different between a tiny and a huge r.\n\nMinor\n1. The literature section needs a clearer analysis of the relationship among adaptive algorithms, overfitting, robustness, and multi-classification. In addition, the motivation is not fully explained.\n2. The title \"Characterization of Overfitting in Robust Multiclass Classification\" is too broad. It's better to be more specific with the adaptive algorithms and adversarial settings.\n3. What's mathmatical definition for \\O, \\Omega, and \\Theta? They are not defined in the paper.\n4. The main result, Theorem 1 (lines 74-76), is \nlabeled as informal. In addition, it's not proven and not reader-friendly.\n5. The paper lacks practical experiments to support the main results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time reviewing our work. \n\n**About the paper structure**\n\nWe focus on the question whether adaptively excessive reuse of test data lead to overfitting in robust learning. In Section 2 , we transform this problem into a problem of studying the value of $h _\\mathcal{U}(k,n,m),$ and our informal main result (Theorem 1) is a combination of our Corollary 1 and Theorems 3 & 4, which study the upper and lower bounds on $h _\\mathcal{U}(k,n,m)$ and are all proven strictly. \n\nThe reason why we designed the algorithms is to prove lower bounds on $h_\\mathcal{U}(k,n,m).$ So we do not present the algorithms in our main results section. \n\n**About the definition of $k$-query**\n\nSorry for the confusion. We would like to use our algorithm $\\mathcal{A}^{small}$ (k>1) as an example to explain the definition of $k$-query. As we defined in Lines 56-57, $\\mathcal{A}^{small}$ first makes $k$ queries, namely $f _1,\\dots,f _k$ (see Algorithm 2 for specific definitions) on the test set $S.$ Note that these queries are designed in advance hence are independent to $S$. Then $\\mathcal{A}^{small}$ receives the values of $\\text{Acc} _\\mathcal{U}(f _1;S),\\dots,\\text{Acc} _\\mathcal{U}(f _1;S),$ and utilizes these values (robust accuracies) to construct $\\mathcal{A}^{small}$'s final output $\\hat{f}.$\n\n**About the assumption of uniformly distributed labels**\n\nFollowing [1], we make this assumptions since the algorithms have no prior knowledge about the test labels (as we state in Lines 63 & 64). Many experiments have also been conducted under this assumption, such as [3][4]. We believe this definition reflects the fact that excessive reuse of test data leads to overfitting in robust learning. \n\n**About the gap of bounds**\n\nTheorem 1 shows that our upper bounds and lower bounds are matching up to a logarithmic factor for any fixed number of test examples $n$ and feature distribution $\\mathcal{D}_\\mathcal{X},$ which is optimal at present.\n\n**There is no $r$ in main results**\n\nIt needs to be clarified that our results definitely contain $r.$ However, to make our results more intuitive, we scale our bounds without changing its order. Specifically, in our full upper bounds, Theorem 2, $r$ affects the value of $C _\\mathcal{H},$ and we scale it by the fact $C _\\mathcal{H}\\leq1$ in Corollary 1, that is why there is no $r$ in Theorem 1's upper bounds. On the other hand, in our formal lower bounds, namely Theorems 3 & 4, $r$ affects the value of $\\Phi _{\\mathcal{D} _\\mathcal{X}}(n)$ explicitly (see Lines 152-154 for the definition of $\\Phi _{\\mathcal{D} _\\mathcal{X}}(n)$, and this term is preserved in our Theorem 1's lower bounds.\n\n**The definition of $O,\\Omega,\\Theta$**\n\nWe apologize for any confusion caused by our oversight in assuming familiarity with the definition.\n\nThe $O,\\Omega,\\Theta$ notations, as known as the big O notations, are asymptotic notations. They are defined as follows: Given $f:\\mathbb{R}\\to\\mathbb{R} _+$ and $g:\\mathbb{R}\\to\\mathbb{R} _+$ we write $f=O(g)$ if there exist $x _0,\\alpha\\in\\mathbb{R} _+$ such that for all $x>x _0$ we have $f(x)\\leq\\alpha g(x).$ We write $f=\\Omega(g)$ if there exist $x _0,\\alpha\\in\\mathbb{R} _+$ such that for all $x>x _0$ we have $f(x)\\geq\\alpha g(x).$ The notation $f=\\Theta(g)$ means that $f=O(g)$ and $g=O(f).$ Finally, the notation $f=\\tilde{O}(g)$ means that there exist $k\\in\\mathbb{N}$ such that $f(x)=O(g(x)\\log^k(g(x))).$ The notation $f=\\tilde{\\Omega}(g)$ and $f=\\tilde{\\Theta}(g)$ are defined analogously.\n\n**The paper lacks practical experiments to support the main results.**\n\nSince [2] has already indicated the presence of overfitting in adversarial training. Hence our paper is devoted to a certain theoretical question related to this phenomenon, that is, whether adaptively excessive reuse of test data leads to overfitting in robust learning. Our results answer this question in the affirmative and suggest that one can expect better performance with more queries made to the test data, which aligns with the experimental results.\n\n*Reference*\n\n*[1] Vitaly Feldman Et al. \"The advantages of multiple classes for reducing overfitting from test set reuse.\" ICML 2019*\n\n*[2] Leslie Rice Et al. \"Overfitting in adversarially robust deep learning\" ICML 2019*\n\n*[3] Cynthia Dwork Et al. \"Generalization in Adaptive Data Analysis and Holdout Reuse\" NIPS 2015*\n\n*[4] Cynthia Dwork Et al. \"The reusable holdout: Preserving validity in adaptive data analysis\" Science 2015*"}, {"review_id": "XCKOeQ5t9V", "reviewer": "Reviewer_PNTq", "summary": "This paper generalizes the framework of perfect reconstruction to the adversarial setting and studies how much a k-query algorithm can overfit the test set in the adversarial setting. Upper bounds and lower bounds are derived, which match in terms of the number of classes m and the number of queries k modulo logarithmic factors when the number of test examples n and the distribution are fixed.", "questions": "See Weaknesses.\n\nminors:\n1. In line 66, should it be h_U(A) - 1/m instead?\n2. In line 107, the explanation after 'i.e.' is confusing.\n3. In Algorithm 1, the definition of the output is not written in a very nice way. Probably move $\\forall x \\in X$ outside.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper gives a careful analysis that generalizes both the upper bound and the lower bound on how much an algorithm can overfit the test set in non-robust setting to the adversarial setting. The results are novel.", "weaknesses": "1. The dependence of the lower bound on the number of test examples n does not have a closed form and thus the question asked in the abstract is not fully solved.\n\n2. It is not clear what role the perturbation set U plays in the bounds. In the adversarial setting, other than the parameters m, k and n, the radius r of the perturbation ball is also an important parameter and it is usually more informative if we know how the bounds are affected by allowing stronger attacks, i.e. a larger r. Otherwise, some intuitions on why the perturbation size is irrelevant here would be helpful.\n\n3. This paper is in general not very well-written. For example, the term robust overfitting is confusing here: in line 9, robust overfitting [1] refers to the phenomenon that the robust test error can increase during adversarial training, but later on, e.g. in line 21 and 81, the term is used to describe the overfitting to the test set with k-query algorithms; there are not many detailed discussions on the motivation of the studied problem or what the derived bounds suggest such as how each parameter affects the bound and if robust multiclass classification requires benchmark datasets different from standard classification.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time reviewing our work and your helpful suggestions.\n\n**About the dependence of lower bound on $n$**\n\nAs we discuss in Lines 77-84, the term $\\Phi _{\\mathcal{D} _\\mathcal{X}}(n)$ highly depends on the distribution of $\\mathcal{D} _\\mathcal{X}$ and is unavoidable. Its specific form is presented in Section 3.2. This term measures how easily to sample $n$ 'good' (for robust overfitting) test data features from $\\mathcal{D} _\\mathcal{X}$. For example, if the test data features are well-separated, then we have $\\Phi _{\\mathcal{D} _\\mathcal{X}}(n)\\equiv1$. But in most case the well-separated property does not hold, it can be proven that some extreme distribution of test data feature (e.g. supp($\\mathcal{D} _\\mathcal{X}$)$\\subset\\mathcal{U}(x _0)$ for some $x _0\\in\\mathcal{X}$) may not allow one to derive bounds w.r.t $k$ when $k\\geq m$. So we keep this term in our results.\n\n**About the role $\\mathcal{U}$ plays**\n\nWe apologize for any confusion arising from our presentation. That is indeed an interesting issue. We first clarify that $\\mathcal{U},$ or equivalently $r,$ is relevant to our results. Intuitively, bigger $r$ shrink both upper and lower bounds on $h _\\mathcal{U}(k,n,m),$ and this is captured by the definitions of $C _\\mathcal{H}$ and $\\Phi _{\\mathcal{D} _\\mathcal{X}}(n)$ (see proof of Theorem 2 and definition of $\\Phi _{\\mathcal{D} _\\mathcal{X}}(n),$ respectively). Nevertheless, we deliberately mitigate the influence of $r,$ as our focus is placed on investigating the potential for overfitting when test data is excessively reused under **specific** adversarial perturbations. Besides, our analysis suggests that the affect of $r$ is closely intertwined  with $\\mathcal{D} _\\mathcal{X},$ which cannot be parameterized. More explicit dependence on $\\mathcal{U}$ or $r$ could potentially serve as a future avenue of exploration. Thank you again for bringing this to our attention.\n\n**About the term \"robust overfitting\"**\n\nSorry for any confusion caused by our oversight. Indeed, the overfitting phenomenon in [1] can also be formulated under the $k$-query framework, since the process of adversarial training can also be viewed as adaptive queries. Nevertheless, we greatly appreciate your highlighting the potential misunderstanding to this term, and we will add some discussion in revision.\n\n**\"In line 66, should it be $h_\\mathcal{U}(A)-1/m$ instead?\"**\n\nWe sincerely appreciate your meticulous review of our paper, but there is no typo here. $h_\\mathcal{U}(A;S)-1/m$ measures how much $\\mathcal{A}$ robustly overfits a specific test dataset $S.$\n\n**\"In line 107, the explanation after 'i.e.' is confusing.\"**\n\nSorry for the confusion. The explanation means the '$\\perp$' output satisfies $\\perp\\neq1,\\dots,m$ and $\\perp\\neq\\perp,$ see [2] for more details.\n\n**\"In Algorithm 1, the definition of the output is not written in a very nice way. Probably move $\\forall x\\in\\mathcal{X}$ outside.\"**\n\nThanks again for your careful reviewing. We totally agree and will fix it in revision.\n\n*Reference*\n\n*[1] Leslie Rice Et al. \"Overfitting in adversarially robust deep learning\" ICML 2019*\n\n*[2] Daniel Cullina Et al. \"Pac-learning in the presence of adversaries.\" NeurIPS 2018*"}, {"review_id": "Q2IgA54bxK", "reviewer": "Reviewer_WwD9", "summary": "The main worry regarding the excessive reuse of test datasets in machine learning is its potential to cause overfitting. The objective of this paper is to characterize the relationship between the amount of robust overfitting bias and three key factors: the number of classes (m), the number of robust accuracy queries (k), and the size of the test dataset (n). The main theoretical contributions of this paper consist of providing upper and lower bounds on the attainable robust overfitting bias in multiclass settings.", "questions": "See the above Flaws part.", "limitations": "No potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper showcases exceptional writing skills, surpassing the average standard of presentation seen in many well-written and well-structured papers. The introduction successfully establishes a clear motivation and provides a satisfactory outline of the contributions. Although the section on related works is concise, it not only acknowledges a broad range of prior research efforts but also effectively highlights the key distinctions and limitations. Despite my personal unfamiliarity with several of the cited works and some of the presented topics, I never felt lost. This is mainly attributed to the \"Summary of our results\" section, which introduces the various notations used in the paper, provides a very clear formulation of the addressed problem, and offers a summary of the main results and the techniques employed in their proofs. The proofs of the various theoretical results are generally clear and sufficiently detailed. However, there are occasional passages that I did not understand easily and, in my opinion, require more elaboration. For instance, the usage of the Chernoff bound for Bernoulli random variables with bias could benefit from further explanation.", "weaknesses": "My primary concern relates to the level of novelty and originality in the theoretical results presented in the paper, particularly concerning the techniques employed in the proofs. It is worth acknowledging that the paper serves as an extension of previous works by (Feldman et al., \"The advantages of multiple classes for reducing overfitting from test set reuse,\" ICML'19) and (Acharya & Suresh, \"Optimal multiclass overfitting by sequence reconstruction from Hamming queries,\" ALT'20) within an adversarial setting. However, it is important to note that the proofs in this paper largely follow a similar approach to those in the aforementioned papers, and the extension to the adversarial setting does not significantly contribute to the technical aspect.\n\nI have observed several errors in the paper (which I believe are oversights) that can be easily noticed but may lead to a misunderstanding of the contributions. One specific example is found in line 1 of Algorithm 2, where the division of n into (k-1) blocks should be denoted as (B_1...B_(k-1)) instead of (B_1, ..., b_k). It is crucial to maintain a consistent notation for the blocks using a capital B, and it should be noted that the last block is indexed as (k-1). Furthermore, on the same line, the upper and lower bounds of |B_i| need to be reversed due to the condition n > k-1. The correct bounds should be $\\frac{n}{2(k-1)} \\leq |B_i| \\leq \\frac{n}{k-1}$. These errors should be rectified to ensure the accuracy and clarity of the paper.\n\nAnother aspect that I find regrettable is the lack of discussion or interpretation regarding the various bounds presented in the paper. This absence leaves a gap in the understanding of the implications and significance of these bounds. It would have been valuable to explore the practical implications of the bounds, their relationship to existing theories or frameworks, and any potential limitations or extensions that arise from them. Providing such a discussion would have enhanced the overall comprehensiveness and depth of the paper. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for reviewing our work and affirming our presentation; this means a lot to us. Below are our responses to your comments. We hope these address your concerns. Do not hesitate to reach out if you have further questions or suggestions. \n\n**About the novelty and originality**\n\nWe feel very sorry for our inadequate referencing to known proof/techniques that may make you hard to access the originality. On one hand, the upper bounds' proof technically differs from proofs in the standard case derived by [1] from the following 3 parts:\n\n1. To take the adversarial perturbation into account, we use Bayes' formula to represent the robust accuracy of a single sample by a Bernoulli r.v. parameterized by $C(f)$. This procedure is quite trivial in the standard case. \n\n2. As discussed in Section 2.3, we introduce the notion of hypothesis class to upper bound $C(f)$, which makes our bounds tighter. \n\n3. Some inequality scaling techniques, e.g., Eq.(1) in Line 125 and the inequalities at the end of the proof in Lines 132-135.\n\nOn the other hand, Compared to [2],  our technical novelty can be summarized as follow:\n\n1. To expand the domain from $\\mathcal{X} _S$ to the entire $\\mathcal{X},$ we borrow the idea of nearest neighbors algorithm. This construction is proved to be optimal (up to logarithmic factors) for fixed $n$ and $\\mathcal{D} _\\mathcal{X}$). \n\n2. In the proof of Theorems 3 & 4. the introduction of corrupted classes is very elegant, without whom one may not be able to derive the distribution of $(N^S _{i,1},\\dots,N^S _{i,m}),$ which is crucial in the standard case to prove the lower bounds. This is because the output $\\hat{f}$ may **always** predict a label that is not robust to adversarial perturbation. In other words, some samples may be not to be counted. So the \"always wrong\" label, i.e. $\\perp,$ not only facilitates our deduction, but also instruct us to study the distribution of $(N^S _{i,1},\\dots,N^S _{i,m},N^S _{i,\\perp}),$ which makes the counting well defined. \n\n3. In addition, there is a step to deriving lower bounds on $\\textbf{Pr}\\\\{\\kappa _\\mathcal{U}(\\hat{f}(x))\\neq\\perp\\\\}$ in both proofs of Theorems 3 & 4, (Lines 174-177 & Lines 197-201) which has no parallel in previous works. \n\n4. In our Algorithm $\\mathcal{A}^{big}(C),$ the step 2.(b), we make $f _i(x _j)=\\perp$. This construction makes the value of $A _l$ (Eq. (3) in Line 189) in our proof differs from that in [2], but the equation $A _{y _1}-A _l=W _0+M _{y _1}-M _l$ in Line 192 still holds so we can continue the proof. However, one can prove that this is not the case when the queries are designed such that $f _i(x _j)=1,$ as constructed in [2].\n\n**About the errors**\n\nWe greatly appreciate your meticulous examination of our work and we apologize for any confusion may caused by these errors. Your postulations are totally right. We assure you that these factors do not compromise the validity of our results, and we will correct them in revision. Thanks again for your time.\n\n**About the absence of discussion**\n\nThanks for the suggestion! We would be more than happy to add more discussion about our results and practical implications, and we would like highlight some points here. Recall that the question we focus on is: Can excessive reuse of test datasets lead to overfitting in robust learning setting? The answer to this question is implied in our Theorem 1. For fixed number of classes $m$ and fixed number of test examples $n,$ the lower and upper bounds of $h_\\mathcal{U}$ is at least $\\tilde{\\Theta}(\\sqrt{k}),$ which states that one can expect better performance with more queries made to the test set. So the answer is positive. \n\nAs for the practical setting, for example, in modern ML benchmarks for adversarial robustness (e.g. RobustBench), hundreds of results have been reported on same test sets (e.g. ImageNet, SIFAR100). Large-scale hyperparameter tuning and experimental trials across numerous studies likely add thousands of queries to the test data, which may substantially \"improve\" robust accuracy according to our results. Our results may suggest to limit the query time or develop some monitoring mechanism to avoid malicious reuse of test sets.\n\n*Reference*\n\n*[1] Feldman Et al.  \"The advantages of multiple classes for reducing overfitting from test set reuse.\" ICML 2019*\n\n*[2] Acharya Et al. \"Optimal multiclass overfitting by sequence reconstruction from Hamming queries.\" ALT 2020*"}]

Author rebuttal:

Meta-review: This meta review is based on the reviews, the authors rebuttal and the discussions with the reviewers, discussions with the SAC, and ultimately my own judgement on the paper. There was a majority to feel that the paper contributes sound and interesting contributions. I feel this work deserves to be featured at NeurIPS and will attract interest from the community, although I would like to personally invite the authors to carefully revise their manuscript to take into account the remarks and suggestions made by reviewers. Congratulations!
Decision: Accept (poster)