We thank the reviewer for the positive and encouraging review. We address their comments one by one.
Weakness 1) a) Please see our general response addressing scalability, and we agree with the reviewer that experiments using adversarial robust training in combination with our randomization strategy, for example in conjunction with the mentioned efficient adversarial training strategy, is a very promising idea but out of scope for this work.
Weakness 1) b) Note that the lines 216-218 refer to equation 2 i.e. a general min-max loss where in generality one can not compute gradient attacks wrt to e.g. the inputs to efficiently find an attack. In cases such as [1], this is simplified by using continuous attacks, which can be turned into discrete attacks but still fall, we believe, out of the scope of the current work. We will clarify the text accordingly, thank you for pointing out this source of confusion.
Weakness 2) We thank the reviewer for raising this important point. We stress that the assumptions in Proposition 1 do contain the necessary condition for randomization to present a benefit raised in paragraph 2.1. Indeed, if the model were overparameterized w.r.t the training set, the model would be able to perfectly fit the data, i.e. achieve 0 loss on all training data points. This in turns would imply that for any seed $r_i$, the worst case data is the set of all training data (i.e. $\arg\max_{x'\in\mathcal{X}} L(A_{\theta^*}(x',r_i)) = \mathcal{X}$), which would violate the second condition in equation 3. On a more intuitive level, if the model has enough capacity to perfectly fit the training set without leveraging the random seed encodings, then there is no incentive in properly leveraging randomness. In principle, a lack of incentive in terms of optimization does not mean that randomness won't in fact be leveraged. However, in that case no theoretical guarantee can be made about proper randomization at a global optimum of the objective.
We hope we clarified this important point, thank you again for raising it, and remain open if you have any further questions.
Weakness 3) This is a very good point indeed. The reviewer is right that there are several paths of equal optimality in the second episode. However, there is no incentive for the model to not choose a single path, as the incurred losses are all equal. This highlights the crucial point that, simply because randomness is available to the model, the model will not necessarily make use of it. In fact, we hypothesize that due to e.g. the necessity for richer internal representation, it is in practice necessary that randomness be incentivized by a lower loss for proper randomization. We will comment on this in the revised manuscript, a very good observation that is important to discuss.
Weakness 4) The source of randomness is indeed an interesting question but we decided to have a simple source of randomness across all of our settings. Nevertheless, we indeed do not see any reason why in principle noise stemming from sampling actions in the autoregressive case could not be leveraged to learn randomized algorithms. We will clarify this in the text.
Question 1) We can indeed make this clearer. Intuitively the q-norm allows to account for a continuum of differentiable losses with different behaviors. For q = 1 we have the ERM loss $L^E$ while for $q \to \infty$ we have the adversarial loss $L^A$. While one would want to optimize for $L^A$, this would end up accounting for only one $x$ for an expense of computation the loss for a batch of input points, resulting in a slow and high variance training. In practice, it is better to relax this loss by scaling” the losses of different points as a function of their magnitude. This is what the $L^q$ allows to achieve.
Question 2) This is an excellent point. In our experiments, we have indeed been using the same random seeds for all inputs. Let’s first observe that whether we use fresh seeds or the same seeds, the resulting estimator of the loss $L^q $, which we aim to optimize, remains biased. Importantly, the bias of the gradients in both cases are comparable, as they align perfectly in expectation as the expected gradients are the same up to renormalization. Second, according to the strong law of large numbers, the estimators will almost surely converge to $L^q $ in either case. This aligns with both our intuition and our experimental results.
However, while the biases remain comparable, the variance can differ. It is mathematically possible to construct scenarios where one choice provides a better estimate than the other. Initially, we experimented with decorrelated seeds but found that using correlated seeds improved the outcomes, prompting us to adopt this approach.
Question 3) This is correct.
We thank the reviewer again for this detailed and very helpful review! Thank you for spotting the mentioned typos.