Online semi-supervised perception: Real-time learning without explicit feedback

arXiv:2604.27562 · cs.LG, stat.ML · Submitted 2026-04-30 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "Online semi-supervised perception".

Tom: This paper proposes an algorithm for real-time learning without explicit feedback by combining semi-supervised learning on graphs and online learning.

Jane: First, who's behind it and why it matters.

Title and authors: Tom: This paper, "Online semi-supervised perception: Real-time learning without explicit feedback," tackles the problem of learning from unlabeled data in real time without needing constant manual labeling. The authors are Branislav Kveton, Matthai Philipose, and Michal Valko from Intel Labs and the University of Pittsburgh.

Jane: It's clear that by combining semi-supervised learning on graphs with online learning, they are proposing a method that builds an evolving map of the world using what we see now and updates it as new things come in. It’s about inferring labels for new data without needing to explicitly tell the system what those labels are for every single example.

Lu: The title highlights the real-time aspect, which is crucial because traditional methods often require you to wait until all the data is collected before you can even start learning anything meaningful. This approach allows perception to keep up with live inputs.

Meng: So, they’re proposing an algorithm that learns incrementally? I wonder if that incremental building process means the initial structure they set up using offline labeled data dictates a lot of the early behavior, doesn't it? We need to understand how much influence that initial bias has.

Lalam: I think the core implication here is about autonomy in learning. If an AI can refine its understanding based on unlabeled data streams without constant human intervention, it fundamentally alters how we design intelligent systems and what we expect them to do in complex, dynamic environments.

The paper's summary: Tom: To summarize the core of "Online semi-supervised perception: Real-time learning without explicit feedback," the algorithm takes an offline set of labeled examples to start, then it uses a stream of unlabeled examples coming in online to refine its understanding through an iterative process on a data adjacency graph.

Jane: Basically, they use the structure derived from those initial labels to guide how they interpret new, unseen data points by looking at their relationships within that growing graph representation. It’s all about using the harmonic function solution of a graph to infer what labels should be for the unlabeled examples in that moment.

Lu: The paper shows that this inference is formalized by minimizing a quadratic objective function subject to constraints from the labeled data, which leads to a closed-form solution for finding those missing labels, which they call the harmonic function solution (one) and (two) <ref:2604.27562#pg1>.

Meng: That mathematical foundation sounds solid, but I'm still curious about the practical implementation detail—they mention that maintaining the full graph structure grows in complexity as time increases. How do they manage that growing structure so it doesn't become computationally impossible?

Lalam: The summary really emphasizes how they handle the complexity of real-time inference by introducing data quantization, which allows them to maintain a compact representation of the world up to any point in time, addressing that scalability issue head-on.

The paper's improvements: Tom: One significant improvement they discuss is moving from an offline learning algorithm to an online one by continually updating the graph structure at each time step using newly observed data points. This allows the system to adapt its learned representation as it encounters new information continuously.

Jane: They tackle the complexity issue by employing data quantization, specifically using Proposition one which allows them to compute the harmonic function solution compactly even when identical vertices exist in their graph representation up to time t <ref:2604.27562#pg0>.

Lu: The paper also details an incremental way to update this graph structure using an algorithm called the doubling algorithm of Charikar et al., which keeps a set of representative vertices that are spaced far apart, ensuring the computation complexity remains independent of the total time elapsed.

Meng: So, they’re not just doing one clever trick; they’re integrating multiple techniques—quantization and incremental graph maintenance—to keep the computational load manageable for real-time operation. That makes it much more grounded for an engineer looking at deployment.

Lalam: This combination of techniques allows the system to maintain a compact world model while still being able to make predictions on new data points in real time, which is exactly what we need for practical, deployable AI systems.

Conclusion: Tom: So, to wrap up our discussion on "Online semi-supervised perception: Real-time learning without explicit feedback," the main implication is that we can develop adaptive perception systems that learn continuously from unlabeled data streams without needing constant human input.

Jane: It really shows how well they control the extrapolation of predictions by using regularization parameters, like setting gamma g as ten epsilon, which gives them a mathematical way to penalize extrapolating too far into the unknown <ref:2604.27562#pg2>.

Lu: The theoretical analysis provides a regret bound: one/n X t (t

t: - y t) squared at most nine/(2nl) X i in l (* i - y i) squared + O(n-one/two), which suggests that as the learner is regularized properly, its regret per step decreases over time at a rate of O(n-one/two).

Meng: From an engineering standpoint, this bound tells us that we can predict how much error we can expect to accumulate over time if we keep our regularization parameter tuned correctly; it gives us control over the performance degradation.

Lalam: Ultimately, the paper on "Online semi-supervised perception: Real-time learning without explicit feedback" suggests a future where AI can be deeply integrated into dynamic systems, making them more robust and capable of handling the continuous flow of information with far greater independence from human supervision.

Branislav Kveton, Matthai Philipose, Michal Valko, Ling Huang

Intel Labs · Department of Computer Science University of Pittsburgh

cs.LG, stat.ML

Submitted: 2026-04-30

Updated: 2026-04-30

Comments: IEEE Computer Vision and Pattern Recognition Workshop on Online Learning for Computer Vision (CVPR 2010 OLCV)

DOI: 10.1109/CVPRW.2010.5543877

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 87/100

The gist: This paper proposes an algorithm for real-time learning without explicit feedback by combining semi-supervised learning on graphs and online learning.

Key concepts

Semi-supervised Learning on Graphs
This technique infers labels for unlabeled data by modeling the relationships between all data points as a graph. It seeks a 'harmonic function' solution that satisfies constraints imposed by known, labeled examples, effectively spreading label information across the entire network based on connectivity.
Online Learning Formulation
Learning is treated as an ongoing process where the system receives new data points sequentially. Instead of retraining from scratch, it continuously updates its internal model—the graph representation—using each new observation to adapt to changing environmental conditions in real-time.
Data Quantization
To keep the growing graph manageable for real-time use, this method quantizes the unlabeled data. This involves simplifying the complex structure of the full data graph into a compact representation, allowing computations to remain fast even as more examples are added over time.

Terminology

Summary

This paper proposes an algorithm for real-time learning without explicit feedback by combining semi-supervised learning on graphs and online learning. The core idea involves iteratively building and updating a graphical representation of the world using observed examples, leveraging offline labeled data as initial bias and online unlabeled data to refine this bias. This approach is significant because it enables adaptive machine learning algorithms suitable for real-world problems where labeled data is scarce, such as real-time face recognition.

The gist

This paper proposes an algorithm for real-time learning without explicit feedback by combining the ideas of semi-supervised learning on graphs and online learning.

Semi-supervised Learning Foundation

The algorithm builds upon the concept of computing a harmonic function solution on a data adjacency graph to infer labels for unlabeled examples. The standard approach involves minimizing a quadratic objective function subject to constraints imposed by labeled data:

  1. Minimize the quadratic objective function:

min &ell∈Rn &ell T L &ell s.t. &ell i = y i for all i ∈ l, where L = D - W is the Laplacian of the data adjacency graph, and W represents pairwise similarities wij between vertices.

  1. The closed-form solution for the unlabeled examples is given by:

&ell u = (Duu − Wuul)−1Wul l, which satisfies the harmonic property &ell i = 1/di P j i wij &ell j, and is viewed as a product of a random walk on the graph W with transition matrix P = D-1W.

Online Learning Formulation

The paper frames learning as a repeating game against an adversarial nature where at each step t, an example xt is observed and its label yˆt is predicted. To adapt to environmental changes without explicit feedback, the algorithm tracks the data adjacency graph and infers labels based on the harmonic function solution on this graph. The paradigm involves:

  1. Labeled examples constituting the initial bias provided offline.

  2. A stream of unlabeled examples collected online to update this bias.

Online Harmonic Function Solution and Quantization

To make the algorithm practical for real-time use, data quantization is employed to maintain a compact representation of the complete data adjacency graph up to time t, addressing the impracticality of growing complexity O(t 3).

  1. The method focuses on the quantization of unlabeled examples, leveraging Proposition 1 which states that if identical vertices are deleted from W˜ by deleting all but a single instance, the harmonic function solution can be computed compactly as:

&hatell u = (Lˆuu + γgV)−1Wˆul l, where Lˆ is the Laplacian of Wˆ and V is a diagonal matrix of vertex multiplicities.

  1. The graph can be updated incrementally using the doubling algorithm of Charikar et al. [5], which maintains a set of representative vertices Ct such that the distance between any two vertices in Ct is at least R. This allows for an update on-the-fly and incrementally, with the time complexity of computation being independent of t, yielding O(n 3g) time steps for a graph with at most ng distinct vertices.

Theoretical Analysis and Regret Bound

The error in predictions is decomposed into three terms: the error due to the harmonic function solution, the online learning error, and the data quantization error. By choosing a regularization parameter γg = Ω(n 1/4), where n ≫ nl, a regret bound is derived:

1/n X t (&hatell t[t] − y t) squared ≤ 9/(2nl) X i∈l (&ell∗ i − y i) squared + O(n-1/2).

This bound indicates that when the learner is regularized enough, its per-step regret decreases over time at the rate of O(n-1/2).

Application to Face Recognition

The problem is formulated on a data adjacency graph where vertices are faces and edge weights wij reflect similarity, computed as wij = exp(-d 2(xi,xj) squared / 2σ 2i), where d(xi, xj) is a distance function correcting for illumination. The graph is made sparse by setting wij to 0 if it falls below an epsilon threshold. The learner's performance is evaluated on three datasets (V1, V2, VO), demonstrating superior precision and recall compared to existing methods like nearest-neighbor classifiers when tracking the manifold of data. Furthermore, the learner shows capability in adapting to sudden changes in the environment, such as varying light conditions and locations.

Outlier Robustness

The online learner is made more robust by altering its behavior when an example xt is identified as an outlier (when &hatell t[t] = 0).

Improvements for AI systems

Here are the specific improvements that can be made to existing AI systems based on this scientific paper, and what those improved systems can achieve:

  1. Real-Time, Adaptive Label Inference in Unlabeled Data (Core Improvement):

The system can move beyond static semi-supervised models by treating learning as a continuous game against an evolving environment. By iteratively building and updating a graphical representation (data adjacency graph) of the world based on incoming unlabeled examples, the system can infer labels for new data points in real-time without requiring explicit human feedback at every step.

  1. Robustness to Data Drift and Environmental Change:

The system gains the ability to adapt dynamically to changes over time (e.g., varying light conditions or different locations) because it tracks the manifold of data. It can maintain high performance even when the underlying data distribution shifts, unlike static models that require complete retraining.

  1. Efficient Representation via Quantization and Dynamic Graph Maintenance:

The algorithm overcomes the computational bottleneck of maintaining a full graph by employing sophisticated quantization techniques (Proposition 1). This allows the system to maintain a compact representation of the world, focusing only on representative vertices, leading to a time complexity that is independent of the total number of training examples and dependent only on the fixed number of representative vertices.

  1. Guaranteed Quality Bounds for Extrapolation:

The incorporation of regularization (via parameterting the graph Laplacian as described in Section 2.1) provides theoretical guarantees on solution quality. This means when making predictions on unlabeled data, the system can quantify and control how much it extrapolates beyond its labeled knowledge, ensuring a bounded regret against the true optimal solution.

  1. Improved Face Recognition Precision and Recall:

When applied to face recognition tasks (as demonstrated in Section 4), this method can achieve superior precision and recall compared to traditional methods (like Nearest Neighbor classifiers) by effectively leveraging unlabeled data to refine the similarity manifold of faces, especially when bootstrapping from different datasets.

  1. Adaptive Outlier Handling:

The system can be made more robust by explicitly handling outliers. By refraining from making predictions when an unlabeled example is identified as an outlier (where the harmonic function solution is zero), the system avoids propagating noise from anomalous data points into its core learned representation, leading to more reliable classifications.

  1. High-Frequency Real-Time Operation:

The optimized structure allows the final recognizer to run in real time (e.g., processing about 7 frames per second even with a moderate number of representative vertices). This makes it viable for live video processing applications where low latency is critical, unlike complex offline graph computations.

Abstract

This paper proposes an algorithm for real-time learning without explicit feedback. The algorithm combines the ideas of semi-supervised learning on graphs and online learning. In particular, it iteratively builds a graphical representation of its world and updates it with observed examples. Labeled examples constitute the initial bias of the algorithm and are provided offline, and a stream of unlabeled examples is collected online to update this bias. We motivate the algorithm, discuss how to implement it efficiently, prove a regret bound on the quality of its solutions, and apply it to the problem of real-time face recognition. Our recognizer runs in real time, and achieves superior precision and recall on 3 challenging video datasets.

Related papers