Optimal Multiscale Learning of Linear Operators
Provides theoretical and algorithmic foundations for learning linear operators in infinite-dimensional settings, relevant to inverse problems and PDEs.
The paper establishes minimax optimal rates for learning linear operators between Sobolev spaces and constructs a blockwise least-squares estimator that achieves these rates with optimal computational cost by using scale-adaptive sample sizes.
We study the statistical and computational limits of learning bounded linear operators between Sobolev spaces from noisy input-output data. In wavelet coordinates, the problem is recast as an infinite-dimensional matrix regression problem with a heterogeneous two-sided multiscale structure. We establish minimax rates under Sobolev operator-norm loss and construct a finite-resolution blockwise least-squares estimator attaining these rates. The analysis reveals a nonuniform local estimation difficulty across scales, which can be exploited algorithmically: by assigning scale-adaptive sample sizes, the estimator achieves the optimal computational cost among dense least-squares implementations.