On the power of adaption and randomization

Key Points

• Adaptive and randomized algorithms can significantly outperform deterministic methods for approximating linear operators.
• Optimal results were found when operating on symmetric convex sets, ensuring maximal gain in approximation.
• The study unifies concepts like n-widths and s-numbers, illustrating their relationship to error minimization in approximations.
• Extensions to nonlinear widths and function-based approximations indicate broad applicability, while also highlighting open research challenges.

Abstract