Optimal Multiscale Learning of Linear Operators

• URL: http://arxiv.org/abs/2606.16913v1
• Date: Mon, 15 Jun 2026 16:22:10 GMT
• Title: Optimal Multiscale Learning of Linear Operators
• Abstract summary: We study the limits of learning bounded linear operators between Sobolev spaces from noisy input-output data.<n>We establish minimax rates under Sobolev operator-norm loss and construct a finite-resolution blockwise least-squares estimator attaining these rates.
• Score: 1.1559118525005183
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Fitting Unknown Number of Hyperplanes with Manifold Optimization [57.48093263119306]
  Fitting unknown number of linearplanes to data is a fundamental yet challenging problem in machine learning.<n>Existing approaches often struggle with optimum optima or lack geometric consistency.
  arXiv  Detail & Related papers  (2026-05-27T14:02:20Z)
• Geometry-Aware Optimal Transport: Fast Intrinsic Dimension and Wasserstein Distance Estimation [32.357350666094156]
  We introduce a tuning-free estimator of $textOT_c(, hat)$ that utilizes the semi-dual OT functional and, remarkably, requires no OT solver.<n>This framework unlocks significant computational and statistical advantages in practice.<n> Numerical experiments demonstrate that our geometry-aware pipeline effectively mitigates the discretization error bottleneck.
  arXiv  Detail & Related papers  (2026-02-04T08:56:28Z)
• Robust Least-Squares Optimization for Data-Driven Predictive Control: A Geometric Approach [5.2456503500395275]
  The uncertainty in this geometric relation is modeled as a ball on the Grassmannian manifold.<n>The inner admits a closed-form solution, enabling an efficient algorithm with a transparent geometric interpretation.
  arXiv  Detail & Related papers  (2025-11-12T12:02:14Z)
• Approximate Gradient Coding for Distributed Learning with Heterogeneous Stragglers [8.873449722727026]
  We propose an optimally structured gradient coding scheme to mitigate the straggler problem in distributed learning.<n>Our approach significantly reduces the impact of stragglers and accelerates convergence compared to existing methods.
  arXiv  Detail & Related papers  (2025-10-26T05:32:18Z)
• Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization [7.114174944371803]
  The problem of finding suitable point embedding Euclidean distance information point pairs arises both as a core task and as a sub-machine learning learning problem. In this paper, we aim to solve this problem given a minimal number of samples.
  arXiv  Detail & Related papers  (2024-10-22T13:02:12Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Near-optimal estimation of smooth transport maps with kernel sums-of-squares [81.02564078640275]
  Under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds. The object of interest for applications such as generative modeling is the underlying optimal transport map. We propose the first tractable algorithm for which the statistical $L2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation.
  arXiv  Detail & Related papers  (2021-12-03T13:45:36Z)
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems [78.95866278697777]
  We propose two variants of the Truncated Orthogonal Iteration to compute multiple leading eigenvectors with sparsity constraints simultaneously. We then apply our algorithms to solve the sparse principle component analysis problem for a wide range of test datasets.
  arXiv  Detail & Related papers  (2021-03-24T23:11:32Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  We develop a framework that yields statistical accuracy based on interplay between the deterministic convergence rate of the algorithm at the population level, and its degree of (instability) when applied to an empirical object based on $n$ samples. We provide applications of our general results to several concrete classes of models, including Gaussian mixture estimation, non-linear regression models, and informative non-response models.
  arXiv  Detail & Related papers  (2020-05-22T22:30:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.