Optimal Multiscale Learning of Linear Operators

A new theoretical study maps the fundamental limits of learning linear operators between Sobolev spaces from noisy data, recasting the problem as an infinite-dimensional matrix regression in wavelet coordinates [1]. The work, submitted in June 2026, constructs a finite-resolution blockwise least-squares estimator and proves it attains minimax rates under Sobolev operator-norm loss [1]. The analysis uncovers a nonuniform local estimation difficulty across scales: some wavelet blocks dictate the global minimax rate, while others can be estimated to the same target accuracy with fewer samples [3]. By assigning scale-adaptive sample sizes, the estimator achieves the optimal computational cost among dense least-squares implementations [2]. The upper bound is constructive. In wavelet coordinates, the problem becomes an infinite-dimensional matrix regression with a diagonally weighted operator-norm loss. The authors build a finite-resolution blockwise least-squares estimator that targets a minimal collection of wavelet blocks and uses a nested-support regression step to control omitted-variable bias from interactions between retained and discarded input scales [3]. The estimator requires only finite-resolution observations of the training input–output pairs, with the required resolution determined by the sample size [3]. The minimax lower bound is obtained by applying Assouad’s lemma to three thin-strip perturbation families in the wavelet matrix model. These perturbations isolate coarse-scale, input-side, and output-side obstructions, demonstrating that each term in the minimax exponent is unavoidable [3]. The computational contribution hinges on the inhomogeneity of local estimation difficulty. Proposition 5.1 of the paper shows that if the target accuracy is ε, the cost of the estimator scales favorably when column-adaptive sample sizes are used: for the j′-th column block, the algorithm uses Nⱼ′ samples rather than the full sample size N [3]. This column-adaptive choice reduces computational cost to the optimal order while preserving the minimax rate [3]. Related work on kernel operator learning has explored similar multiscale trade-offs. A 2023 ICLR paper established information-theoretic lower bounds for learning Hilbert-Schmidt operators between infinite-dimensional Sobolev reproducing kernel Hilbert spaces and developed a multilevel kernel operator learning algorithm that is optimal for learning linear operators between infinite-dimensional function spaces [4]. That study showed that a regularization learning spectral components below the bias contour and ignoring those above the variance contour can achieve the optimal learning rate, with the region between the two contours offering flexibility for computationally feasible algorithms [5]. The multilevel training procedure, analogous to multilevel Monte Carlo methods, uses successive levels to fit higher-frequency information while keeping variance at a controlled scale [5][6].