Reproduce “Learning Randomized Algorithms with Transformers” on OpenResearch

About this paper

Johannes von Oswald, Seijin Kobayashi, Yassir Akram, Angelika Steger

Transformer models can learn to behave like randomized algorithms when trained with a relaxed adversarial loss and provided with varying random seeds, demonstrating enhanced robustness in adversarial scenarios and allowing performance amplification through majority voting. This approach enables deep networks to discover and utilize algorithmic randomization, moving beyond deterministic behavior.

Key insights

• The proposed Lq objective, coupled with providing varying random seeds as input, is essential for inducing 'proper randomness' and robust behavior in transformer models; standard ERM training does not achieve this.
• Learned randomized algorithms provide significant benefits primarily in adversarial or worst-case scenarios, aligning with theoretical principles like Yao's Minimax Principle, rather than for average-case performance.
• Simple aggregation techniques like majority voting can effectively amplify the success probability of the learned randomized algorithms, leading to near-optimal performance in challenging tasks.

Summary by alphaXiv.