On the power of adaption and randomization

2024/06/11 by Krieg, David, Novak, Erich, Ullrich, Mario · 2 citations
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.2406.07108

Abstract

We present bounds on the maximal gain of adaptive and randomized algorithms over non-adaptive, deterministic ones for approximating linear operators on convex sets. If the sets are additionally symmetric, then our results are optimal. For non-symmetric sets, we unify some notions of n-widths and s-numbers, and show their connection to minimal errors. We also discuss extensions to non-linear widths and approximation based on function values, and conclude with a list of open problems.

Cited by

• Noisy nonlinear information and entropy numbers
• Sampling and entropy numbers in the uniform norm

Related

• Adaptive and Oblivious Randomized Subspace Methods for High-Dimensional\n Optimization: Sharp Analysis and Lower Bounds
• Uniform approximation of vectors using adaptive randomized information
• Randomized approximation of summable sequences -- adaptive and non-adaptive
• Lower Bound for Randomized First Order Convex Optimization
• Adaptive and non-adaptive randomized approximation of high-dimensional vectors