A numerical algorithm for attaining the Chebyshev bound in optimal learning
Given a compact subset of a Banach space, the Chebyshev center problem consists of finding a minimal circumscribing ball containing the set. In this article we establish a numerically tractable algorithm for solving the Chebyshev center problem in the context of optimal learning from a finite set of data points. For a hypothesis space realized as a compact but not necessarily convex subset of a finite-dimensional subspace of some underlying Banach space, this algorithm computes the Chebyshev radius and the Chebyshev center of the hypothesis space, thereby solving the problem of optimal recovery of functions from data. The algorithm itself is based on, and significantly extends, recent results for near-optimal solutions of convex semi-infinite problems by means of targeted sampling, and it is of independent interest. Several examples of numerical computations of Chebyshev centers are included in order to illustrate the effectiveness of the algorithm.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
On a Gradient Approach to Chebyshev Center Problems with Applications to Function Learning
We introduce $\textsf{gradOL}$, the first gradient-based optimization framework for solving Chebyshev center problems, a fundamental challenge in optimal function learning and geometric optimization. $\textsf{gradOL}$ hi…
Convergence Acceleration via Chebyshev Step: Plausible Interpretation of Deep-Unfolded Gradient Descent
Deep unfolding is a promising deep-learning technique, whose network architecture is based on expanding the recursive structure of existing iterative algorithms. Although convergence acceleration is a remarkable advantag…
On Estimating the Probabilistic Region of Attraction for Partially Unknown Nonlinear Systems: An Sum-of-Squares Approach
Estimating the region of attraction for partially unknown nonlinear systems is a challenging issue. In this paper, we propose a tractable method to generate an estimated region of attraction with probability bounds, by s…
Gaussian ProcessesTheoretical Interpretation of Learned Step Size in Deep-Unfolded Gradient Descent
Deep unfolding is a promising deep-learning technique in which an iterative algorithm is unrolled to a deep network architecture with trainable parameters. In the case of gradient descent algorithms, as a result of the t…
Improved Semi-Parametric Bounds for Tail Probability and Expected Loss: Theory and Applications
Many management decisions involve accumulated random realizations for which only the first and second moments of their distribution are available. The sharp Chebyshev-type bound for the tail probability and Scarf bound f…
Management