cs.LGFeb 20, 2026

Learning Without Training

Authors: Ryan O'Dowd

Organizations: Claremont Graduate University

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Machine learning is at the heart of managing the real-world problems associated with massive data. With the success of neural networks on such large-scale problems, more research in machine learning is being conducted now than ever before. This dissertation focuses on three different projects rooted in mathematical theory for machine learning applications. The first project deals with supervised learning and manifold learning. In theory, one of the main problems in supervised learning is that of function approximation: that is, given some data set D={(xj,f(xj))}j=1M\mathcal{D}=\{(x_j,f(x_j))\}_{j=1}^M, can one build a model F≈fF\approx f? We introduce a method which aims to remedy several of the theoretical shortcomings of the current paradigm for supervised learning. The second project deals with transfer learning, which is the study of how an approximation process or model learned on one domain can be leveraged to improve the approximation on another domain. We study such liftings of functions when the data is assumed to be known only on a part of the whole domain. We are interested in determining subsets of the target data space on which the lifting can be defined, and how the local smoothness of the function and its lifting are related. The third project is concerned with the classification task in machine learning, particularly in the active learning paradigm. Classification has often been treated as an approximation problem as well, but we propose an alternative approach leveraging techniques originally introduced for signal separation problems. We introduce theory to unify signal separation with classification and a new algorithm which yields competitive accuracy to other recent active learning algorithms while providing results much faster.

Figures & tables

Figure 1.1 : A depiction of the standard supervised learning paradigm. The universe of discourse X\mathcal{X} is assumed to contain a target function ff and hypothesis spaces VnV_{n} are judiciously chosen based on the algorithm of choice. P#P^{\#} denotes the empirical risk minimizer, P~\tilde{P} denotes the minimizer of the generalization error, and P∗P^{*} denotes the best approximation.
Figure 1.2 : Comparison of recoveries for f(θ)=∣cos⁡θ∣1/4f(\theta)=\left|\cos\theta\right|^{1/4} by the best approximation (black) and a good approximation (red) for degrees n=63,127,255n=63,127,255 . Figure credit: Hrushikesh Mhaskar.
Figure 1.3 : Depiction of nonlinear width. Here X\mathbb{X} is a metric space of functions with K\mathbb{K} some subset. The goal is to understand the error associated with approximating any function f∈Kf\in\mathbb{K} , where P\mathcal{P} is a continuous parameterization of K\mathbb{K} and A\mathcal{A} is an approximation scheme mapping into X\mathbb{X} .
Figure 2.1 : A depiction of a new machine learning paradigm, where one constructs an approximation σn\sigma_{n} in the space VnV_{n} directly from the data. This is done in such a way that one can also measure a direct reconstruction error from the approximation to the target function.
Figure 2.2 : Error comparison between our method, the Nadaraya-Watson estimator, and an interpolatory RBF network. (Left) Comparison of absolute errors between the methods with the target function plotted on the right yy -axis for benefit of the viewer. We note that the error from the RBF method is scaled by 10−310^{-3} so as to not dominate the figure. (Right) Percent point plot of the log absolute error for all three methods.
Figure 2.3 : Visualization of our approximation approach. Here, X\mathbb{X} is a submanifold of the sphere SQ\mathbb{S}^{Q} . The map ηx\eta_{x} , analogous to the exponential map, allows us to relate the part of the integral in ( 2.3.3 ) near xx with an integral on the tangent sphere at xx via a change of variables (solid curves). The localization of the kernels in our method allow for the approximation to be extended over X{\mathbb{X}} and the tangent sphere Sx\mathbb{S}_{x} (dotted curves).
SpaceDescriptionDefinition
Ambient spaceEuclidean ballBQ+1(x,r)={y∈RQ+1:∣∣x−y∣∣2≤r}B_{Q+1}(x,r)=\{y\in\mathbb{R}^{Q+1}:\left|\left|x-y\right|\right|_{2}\leq r\}
Ambient sphereSpherical capSQ(x,r)={y∈SQ:arccos⁡(x⋅y)≤r}S^{Q}(x,r)=\{y\in\mathbb{S}^{Q}:\arccos(x\cdot y)\leq r\}
Tangent spaceTangent ballBT(x,r)={y∈Tx(X):∣∣x−y∣∣2≤r}B_{\mathbb{T}}(x,r)=\{y\in\mathbb{T}_{x}(\mathbb{X}):||x-y||_{2}\leq r\}
Tangent sphereTangent capSx(r)={y∈Sx:arccos⁡(x⋅y)≤r}\mathbb{S}_{x}(r)=\{y\in\mathbb{S}_{x}:\arccos(x\cdot y)\leq r\}
ManifoldGeodesic ballB(x,r)={y∈X:ρ(x,y)≤r}\mathbb{B}(x,r)=\{y\in\mathbb{X}:\rho(x,y)\leq r\}
Table 2.1 : Definition and description of balls in different spaces.
Figure 2.4 : Left y-axis: Plot of the true function ff compared with F32F_{32} constructed by 2132^{13} noiseless training points. Right y-axis: Plot of ∣f−F32∣\left|f-F_{32}\right| .
Figure 2.5 : (Left) Percent point plot of log absolute error for various nn with M=213M=2^{13} training points and no noise. (Center) Percent point plot of log absolute error for various choices of MM with no noise. (Right) Percent point plot of log absolute error for various noise levels with M=213M=2^{13} training points.
Figure 2.6 : (Left) Percent point plot of log combined error for various nn with M=213M=2^{13} training points, and no noise. (Center) Percent point plot of log combined error for fixed n=32n=32 , various choices of MM , and no noise. (Right) Percent point plot of log combined error for fixed n=32n=32 , fixed M=213M=2^{13} training points, and various noise levels.
Figure 2.7 : Plot of RMS error for approximation by F32F_{32} for various qq values with M=213M=2^{13} and no noise.
Figure 2.8 : (Left) Percent point plot of log combined error for various nn , fixed M=213M=2^{13} , and no noise. (Center) Percent point plot of log combined error for fixed n=64n=64 , various MM , and no noise. (Right) Percent point plot of log combined error for fixed n=64n=64 , fixed M=213M=2^{13} , and various noise levels.
Figure 4.1 : Left: ∣σ256(μ)(x)∣|\sigma_{256}(\mu)(x)| has peaks at the points −1,2,2.05-1,2,2.05 , and is small everywhere else. Vertical red lines indicate the positions of these points. Middle: A close-up view of ∣σ256(μ)(x)∣|\sigma_{256}(\mu)(x)| near x=2x=2 to show an accurate detection of the close-by points 2,2.052,2.05 . Right: A close-up view of ∣σ64(μ)(x)∣|\sigma_{64}(\mu)(x)| near x=2x=2 to show the non-detection of the close-by points 2,2.052,2.05 .
Figure 4.2 : Normalized histogram of the density of interest (left), paired with our density estimation by σ128\sigma_{128} based on 39003900 samples (right).
 Signal separationClassification
Measure:μ=∑kakδωk\mu=\sum_{k}a_{k}\delta_{\omega_{k}}μ=∑kakμk\mu=\sum_{k}a_{k}\mu_{k}
Domain:R/(2πZ)\mathbb{R}/(2\pi{\mathbb{Z}})unknown subset of a metric space
Data:Fourier momentssamples from μ\mu
Key quantity:min⁡j≠k∣(ωj−ωk)mod  2π∣\min_{j\neq k}\left|(\omega_{j}-\omega_{k})\mod 2\pi\right|min⁡j≠k dist⁡(supp⁡(μj),supp⁡(μk))\min_{j\neq k}\ \operatorname{dist}(\operatorname{supp}(\mu_{j}),\operatorname{supp}(\mu_{k}))
Table 4.1 : Comparison between traditional signal separation and our approach to machine learning classification.
Figure 4.3 : Demonstration of the support estimation set G32(0.15)\mathcal{G}_{32}(0.15) (yellow) applied to a simple two-moons data set from [ 48 ] (blue and red). By querying one point from each component of the support estimation set and extending the label to the other points in the same component, we can classify the entire data set with 100% accuracy.
Figure 4.4 : This figure illustrates the result of applying MASC to a synthetic circle and ellipse data set. On the left are true labels of the given data, and on the right is the estimation attained by MASC.
Figure 4.5 : This figure illustrates the classification process undergone MASC on the document data set at two points. On the left, we see the classification of points before the k‾\overline{k} -nearest neighbors extension. On the right, we see the result after k‾\overline{k} -nearest neighbors extension.
Figure 4.6 : Further details on the classification results for the document data set. (Left) Confusion matrix for single run of MASC algorithm. (Right) Accuracy of MASC algorithm vs. the number of queries used.
Figure 4.7 : Visual comparison of true labels (left) versus predicted labels output by the model (right) for the document data set.
Figure 4.8 : This figure illustrates the classification process undergone by MASC at two points on the Salinas hyperspectral data set. On the left, we see the classification of points before the k‾\overline{k} -nearest neighbors extension. On the right, we see the result after k‾\overline{k} -nearest neighbors extension.
Figure 4.9 : Confusion matrix for single run of MASC algorithm on Salinas.
Figure 4.10 : Visual comparison of true labels (left) versus predicted labels output by the model (right) for the Salinas hyperspectral data set.
Figure 4.11 : This figure illustrates the classification process undergone by MASC at two points on the Salinas hyperspectral data set. On the left, we see the classification of points before the k‾\overline{k} -nearest neighbors extension. On the right, we see the result after k‾\overline{k} -nearest neighbors extension.
Figure 4.12 : Confusion matrix for result of MASC applied to Indian Pines.
Figure 4.13 : Visual comparison of true labels (left) versus predicted labels output by the model (right) for the Indian Pines hyperspectral data set.
Figure 4.14 : Plots indicating the accuracy of MASC, LAND, and LEND for different query budgets, for both Salinas (left) and Indian Pines (right).
Figure 5.1 : The implementation of a linear combination as a ReLU network. Here all operations are pointwise. The symbols ⊙\odot represents Hadamard product of matrices, ⊕\oplus is the sum of matrices.
Figure 5.2 : One step of the Clenshaw algorithm, using two circuits of the form LC (4 neurons) as in Figure 5.1 . The circuit diagram is shown in general with four input pins and two output pins.
Figure 5.3 : Unrolling the Clenshaw algorithm as a cascade of the circuits of the form CL( kk ) as in Figure 5.2 .
More in this topic

Function Approximation

See all 32 papers

Explore similar work

CardsList
May 19, 2026

Sample Complexity of Transfer Learning: An Optimal Transport Approach

Transfer learning is an essential technique for many machine learning/AI models of complex structures such as large language models and generative AI. The essence of transfer learning is to leverage knowledge from resolved source tasks for a new target task, especially when the sample size mm of the training data for the latter is low. In this work, we rigorously analyze the potential benefit of transfer learning in terms of sample efficiency. Specifically, taking an optimal transport viewpoint of transfer learning, we find that when the data dimension dd is higher than 33, the sample complexity for transfer learning is O(m−(α+1)/d)O(m^{-(α+1)/d}), with αα indicating the smoothness of the data distribution, as opposed to the O(m−p/d)O(m^{-p/d}) sample complexity for direct learning with pp indicating the smoothness of the optimal target model. Our finding theoretically supports a better sample efficiency for transfer learning, when the target task is optimizing over a family of not-so-smooth models (i.e., highly complex networks with the possible use of non-smooth activation functions). Using image classification as an example, we numerically demonstrate the sample efficiency for transfer learning, that is, in the data hungry regime, the model performance can be significantly improved by transfer learning.

Haoyang Cao, Xin Guo, Wenpin Tang +1

Department of Applied Mathematics and Statistics, John Hopkins University, Baltimore, MD, USA · Department of Industrial Engineering and Operations Research, University of California, Berkeley, CA, USA · Department of Industrial Engineering and Operations Research, Columbia University, New York, NY, USA +1

Sample ComplexityTransfer LearningStatistical Learning TheoryData-Efficient Learning
AskPDF
Mar 15, 2026

Learning in Function Spaces: An Unified Functional Analytic View of Supervised and Unsupervised Learning

Many machine learning algorithms can be interpreted as procedures for estimating functions defined on the data distribution. In this paper we present a conceptual framework that formulates a wide range of learning problems as variational optimization over function spaces induced by the data distribution. Within this framework the data distribution defines operators that capture structural properties of the data, such as similarity relations or statistical dependencies. Learning algorithms can then be viewed as estimating functions expressed in bases determined by these operators. This perspective provides a unified way to interpret several learning paradigms. In supervised learning the objective functional is defined using labeled data and typically corresponds to minimizing prediction risk, whereas unsupervised learning relies on structural properties of the input distribution and leads to objectives based on similarity or smoothness constraints. From this viewpoint, the distinction between learning paradigms arises primarily from the choice of the functional being optimized rather than from the underlying function space. We illustrate this framework by discussing connections with kernel methods, spectral clustering, and manifold learning, highlighting how operators induced by data distributions naturally define function representations used by learning algorithms. The goal of this work is not to introduce a new algorithm but to provide a conceptual framework that clarifies the role of function spaces and operators in modern machine learning.

K. Lakshmanan

Department of Computer Science and Engineering, Indian Insititute of Technology (BHU), Varanasi 221005.

Supervised LearningStatistical Learning Theory
AskPDF
Jun 23, 2020

Limits of Transfer Learning

Transfer learning involves taking information and insight from one problem domain and applying it to a new problem domain. Although widely used in practice, theory for transfer learning remains less well-developed. To address this, we prove several novel results related to transfer learning, showing the need to carefully select which sets of information to transfer and the need for dependence between transferred information and target problems. Furthermore, we prove how the degree of probabilistic change in an algorithm using transfer learning places an upper bound on the amount of improvement possible. These results build on the algorithmic search framework for machine learning, allowing the results to apply to a wide range of learning problems using transfer.

Jake Williams, Abel Tadesse, Tyler Sam +2

Harvey Mudd College, Claremont, CA 91711, USA · Claremont McKenna College, Claremont, CA 91711, USA · Pomona College, Claremont, CA 91711, USA

Transfer Learning
AskPDF