Learning Randomized Algorithms with Transformers

We thank the reviewer for the constructive comments that have helped us improve the clarity of our paper. We reply to each point separately below.

Weakness 1) Please see our general response above. We remain open to discuss any further issue the reviewer might have.

Weakness 2) Thank you for pointing out this related work which we were not aware of. We clarify that randomization as an approach to improve robustness has been disproved in restricted settings (such as the 0-1 loss in the binary classification setting with specific hypothesis classes considered in Gnecco et al. 2023), but it has not been disproved in most practical settings. Furthermore, we emphasize that we are not advocating for using randomization at inference time - in fact, the majority vote inference which uses properly randomized models is a prime example of a deterministic inference. Rather, we believe that given a model architecture, achieving proper randomization is useful for various reasons, including for boosting robustness by flexibly allocating additional computation at inference time as we show in our paper. This is in fact aligned with the theoretical result of Gnecco et al. 2023, as well as existing approaches such as randomized smoothing.

We will clarify the paragraph by incorporating the known limitations of randomization as a strategy to improve robustness (Gnecco et al. (2023)) to better position our setting. We will also improve the presentation of the paragraph by better distinguishing existing procedures that aimed at properly randomizing models during training (e.g. Rakin et al. (2018)), and those that aimed at leveraging randomized models to improve inference.

We thank the reviewer again and remain open to discuss any follow up question. We hope our clarifications could address your concerns, and can convince the reviewer to vote for a strong acceptance of the paper.

Dear authors,

while reading the other comments I wanted to specifiy a bit more concret some of my comments:

• "While the paper presents conceptual tasks to validate the approach, it does not provide empirical results on large-scale or real-world datasets. This limitation raises questions about how well the method would scale and perform in more complex, realistic environments." --> About the datasets I was thinking about to use the algorithms and try to do some banchmark tests on some algorithm competions sides.

• "The paper's theoretical sections are rigorous but may be dense for readers without a background in adversarial training or randomized algorithms." --> Section 2.3 RANDOMIZATION CAN BE BENEFICIAL IN ADVERSARIAL SETTINGS looked a bit short to me.

• "The study assumes relatively static environments for tasks like grid world exploration and graph coloring. However, it does not address how the transformer's randomized strategies would perform in dynamic, non-stationary settings where environmental conditions change over time." --> How would it perform dynamic graph coloring? Are dynamics a limitation?

• "The approach requires sampling multiple seeds during training (controlled by the hyperparameter m), which can increase computational overhead significantly. The authors note that this limitation affects memory, training time, and inference time, making the method potentially impractical for large-scale applications." --> Some numbers (runtime, relative performance per operation) etc. would be good to have. Also if one has a "optimal" algorithms known how much more operations are need with the transformer approach?

We thank the reviewer for this positive and detailed review! We answer the questions one-by-one.

1. Please see our general response addressing scalability challenges.

2. Thank you for bringing up this important point. Please see again our general response addressing scalability challenges but we highlight here that we will add a discussion of real-world and future applications in the revised manuscript.

3. Thank you for raising this point. Any general hyperparameter search techniques should be applicable to $m$ and $q$ as well. On the other hand we speculate that generally, the choice of $m$ is actually not particularly sensitive and can be adjusted to computational constraints, as long as it is above 1. Too small $q$ on the other hand can, as our results show, lead to suboptimal randomized algorithm performance. Nevertheless, we do not see any downside of choosing moderate, for example $q=10$, when assuming multiple forward passes during inference time such that majority voting improvements can be obtained. Concluding: Although the hyperparameters are important and task dependent, we believe that default values of $q=10$ and $m>1$ will usually, as we observed, lead to powerful randomization.

We thank the reviewer again and remain open to discuss any follow up question.

I appreciate the authors response, which has addressed all of my questions. I will maintain my previous score.

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.