Semi-supervised learning on singular data sets

Guillaume Valette

cs.LGOct 18, 2026

Semi-supervised learning on singular data sets

Authors: Guillaume Valette

Abstract

We propose to model singular data clouds by subanalytic sets, and develop an approach to semi-supervised learning in this setting. It relies on a Morrey-type embedding for Sobolev spaces relative to globally subanalytic measures with possibly singular support. As an illustration, we present a greedy method based on a Monte Carlo approximation of the Sobolev norm of the candidate solutions. We report numerical experiments on point clouds sampled from real algebraic varieties, as well as a test on a classification problem based on MNIST images downsampled into $7\times7$ .

Figures & tables

Figure 1. Three-dimensional visualization of the singular algebraic hypersurface defined by $P_{1}\cdot P_{2}\cdot P_{3}=0$ (the set $X$ is its intersection with $[0,1]^{4}$ ).

Figure 2. MSE on the training and test sets as a function of the number of training samples on a logarithmic scale.

$n_{\mathrm{train}}$	Accuracy		AUC
	MISO	RBF ridge	MISO	RBF ridge
500	$95.2\pm 0.3$	$94.6\pm 0.3$	$0.988\pm 0.002$	$0.985\pm 0.002$
1000	$96.2\pm 0.3$	$95.9\pm 0.3$	$0.993\pm 0.001$	$0.991\pm 0.001$
1500	$96.7\pm 0.3$	$96.5\pm 0.2$	$0.994\pm 0.001$	$0.993\pm 0.001$
2000	$96.9\pm 0.3$	$96.7\pm 0.2$	$0.995\pm 0.001$	$0.994\pm 0.001$

Table 1. Accuracy rate and AUC on MNIST

3,5

vs.

8

, averaged over 10 random seeds. Values are reported as mean

\pm

standard deviation.

Semi-Supervised Learning

Semi-supervised learning uses both labeled and unlabeled data to improve prediction when reliable annotations are scarce.

See all 164 papers

Semi-supervised learning with max-margin graph cuts
Apr 29, 2026Branislav Kveton, Michal Valko, Ali Rahimi +1Graph-Based Semi-Supervised Learning Semi-Supervised Learning
Intel Labs Santa Clara · University of Pittsburgh · Intel Labs Berkeley
Relatively Smart: A New Approach for Instance-Optimal Learning
Mar 2, 2026Shaddin Dughmi, Alireza F. PourPAC Learning Semi-Supervised Learning
University of Southern California · University of Waterloo
High-dimensional Semi-supervised Classification via the Fermat Distance
Apr 26, 2026Ruoxu Tan, Yiming ZangMultidimensional Scaling k-Nearest Neighbors
School of Mathematical Sciences and School of Economics and Management, Tongji University · Department of Sciences, North China University of Technology

Apr 29, 2026J/K move · Enter open · S save

Semi-supervised learning with max-margin graph cuts

Branislav Kveton, Michal Valko, Ali Rahimi, Ling Huang

Intel Labs Santa Clara · University of Pittsburgh · Intel Labs Berkeley

Graph-Based Semi-Supervised Learning Semi-Supervised Learning

Open paper AskPDF arXiv

This paper proposes a novel algorithm for semisupervised learning. This algorithm learns graph cuts that maximize the margin with respect to the labels induced by the harmonic function solution. We motivate the approach, compare it to existing work, and prove a bound on its generalization error. The quality of our solutions is evaluated on a synthetic problem and three UCI ML repository datasets. In most cases, we outperform manifold regularization of support vector machines, which is a state-of-the-art approach to semi-supervised max-margin learning.

Abstract

Semi-Supervised Learning

Explore similar work

Semi-supervised learning with max-margin graph cuts

Relatively Smart: A New Approach for Instance-Optimal Learning

High-dimensional Semi-supervised Classification via the Fermat Distance