Using Synthetic Data to estimate the True Error is theoretically and practically doable

Thanh Hai Hoang, Duy-Tung Nguyen, Hung The Tran, Khoat Than

Abstract

Evaluating machine learning models in data-scarce environments remains a significant challenge, as small labeled test sets often yield high-variance error estimates. This paper presents OSYN (Optimizing SYnthetic data), a method that leverages generative models to provide a reliable lower bound on a model's true error. By deriving novel generalization bounds and treating evaluation as an optimization problem over synthetic samples, OSYN achieves stable and accurate error estimation even when labeled data is extremely limited.

1. Introduction

In many real-world applications, such as rare disease diagnosis or climate modeling, obtaining high-quality labeled data is prohibitively expensive or logistically difficult. While practitioners often rely on small hold-out sets for model evaluation, these samples are prone to high variance, potentially leading to misleading performance metrics.

Conversely, the rise of generative AI has made synthetic data abundant. However, the lack of a rigorous framework to relate synthetic performance to real-world performance has hindered its use in formal evaluation. This research bridges that gap by demonstrating that synthetic data can be used to estimate true error with theoretical guarantees, even when the generator itself is imperfect.

2. The OSYN Methodology

The authors introduce the OSYN algorithm, which moves beyond simple random sampling of synthetic data toward a targeted optimization approach.

2.1 Theoretical Generalization Bounds

The core of the method lies in new mathematical bounds that relate a model's true error to its performance on synthetic data. These bounds incorporate the "sensitivity" of the loss function and the quality of the generator (measured via KL Divergence). Crucially, the authors prove that the error estimate becomes significantly tighter as the quality of the generator improves.

2.2 The OSYN Algorithm

OSYN treats evaluation as an optimization problem rather than a simple measurement task. The process involves three key steps:

  1. Partitioning: The data space is divided into regions (Voronoi cells) centered around the few available real labeled points.
  2. Iterative Selection: From a massive pool of synthetic candidates, the algorithm selects specific points that maximize the theoretical lower bound of the error.
  3. Local Search Constraints: To ensure the synthetic data remains "realistic," the search is restricted to a sphere around real data points, ensuring the synthetic samples cover the local areas of the true distribution.

3. Experimental Evaluation

The efficacy of OSYN was tested across diverse regimes, including simulated Gaussian Mixture Models (GMM) and several real-world datasets:

  • Classification Tasks: CREDIT (predicting defaults), BANK (telemarketing success), and ADULT (census income levels).
  • Regression Tasks: The BIKE (bike-sharing demand) dataset was used to demonstrate the method's applicability to continuous values.

The researchers evaluated the method across eight different classifier architectures, ranging from Decision Trees to Neural Networks, to ensure the findings were consistent across different model types.

4. Key Insights

4.1 Coverage Over Quantity

A significant theoretical finding is that the error bound does not explicitly depend on the size of the real labeled set ($n$). Instead, it depends on how well the synthetic data covers the local areas around those real samples. This suggests that even a handful of real points can be highly informative if the synthetic generator is sufficiently expressive.

4.2 Stability through Optimization

Simply measuring error on a random batch of synthetic data is often unstable. By optimizing the synthetic set to satisfy the theoretical bound, OSYN provides a "tight-from-below" estimate. This conservative approach is particularly useful for safety-critical deployments where overestimating model accuracy can have severe consequences.

4.3 Robustness to Bias

Traditional methods like Bootstrap Loss often fail when the small labeled test set is biased (e.g., over-representing a majority class). OSYN remained stable in these scenarios, consistently providing error estimates within 1-2% of the "Oracle Loss" (the actual true error).

5. Limitations and Future Work

While OSYN represents a major step forward, the authors identify several areas for further development:

  • Lower Bound Focus: The method currently provides a lower bound on error ("the error is at least X"). Future work aims to derive corresponding upper bounds to create full confidence intervals.
  • Hyperparameter Sensitivity: The method requires tuning the number of partitions ($K$) and an adjustment parameter ($b$), which currently relies on heuristics.
  • High-Dimensional Scaling: Scaling the partitioning and search mechanisms to high-dimensional spaces, such as image or text data, remains computationally expensive.

6. Conclusion

OSYN demonstrates that synthetic data can be used to rigorously estimate model performance in the absence of large labeled datasets. By providing a theoretically grounded optimization framework, this research offers a path toward more reliable model validation in domains where data is scarce but generative models are available.

Summary updated

BibTeX
@article{hoang2026using,
  author = {Thanh Hai Hoang and Duy-Tung Nguyen and Hung The Tran and Khoat Than},
  title = {{Using Synthetic Data to estimate the True Error is theoretically and practically doable}},
  journal = {Machine Learning},
  year = {2026},
  doi = {10.1007/s10994-025-06971-2},
}
Figure