Learning Latent Algebraic Structure from Ambiguous Set Observations
Abstract
We study when statistically learnable latent structure can also be recovered efficiently, and how membership queries change the answer. An unknown support A⊆𝔽2n has small additive doubling and is observed through a fixed set B satisfying |A△ B|≤η|A|. We seek one linear subspace V such that every compatible support A is covered by few V-cosets and satisfies |V|≤|A|. For every η<1, polynomially many uniform samples suffice statistically, with cost polynomial in the doubling constant and proportional to (1−η)−1; this radius dependence is sharp. Under a specified hardness assumption for learning parities with noise (search-LPN), however, no polynomial-time sample-only learner achieves even constant covering cost, including when the latent support is unique. At fixed structural parameters and the same constant covering budget, adding exact membership queries to B permits polynomial-time recovery. The general query learner constructs a short structural list and uses fresh samples to select one common output through a majority-coverage rule. Persistent structured cores make this candidate construction possible. At doubling one, a complementary distinction appears at η=1/3: coarse recovery remains polynomial time, while exact recovery requires exponentially many accesses in the worst case when latent cardinality is unknown.
Related
- Algebraic Theory of Inductive Mathematical Modeling: From Experimental Observations to State-Space Representations
- Geometry and observability of latent texture-coherence diffusions in coherent sea-clutter radar observations
- Harmonic torsion of algebraic generalized Ricci solitons and the structure of solvable extensions
- Nonlinear differential-algebraic systems with dissipative port-Hamiltonian structure
- Algebraic Structure and Orthogonality Properties of Rational Polynomial Phase Rings on Discrete Lattices
BibTeX
@misc{peng2026learning,
title = {{Learning Latent Algebraic Structure from Ambiguous Set Observations}},
author = {Cheng Peng},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.00451},
eprint = {2608.00451},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.00451},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Learning Latent Algebraic Structure from Ambiguous Set Observations
AU - Cheng Peng
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2608.00451
UR - https://arxiv.org/abs/2608.00451
AB - We study when statistically learnable latent structure can also be recovered efficiently, and how membership queries change the answer. An unknown support A⊆𝔽_2^n has small additive doubling and is observed through a fixed set B satisfying |A△ B|≤η|A|. We seek one linear subspace V such that every compatible support A is covered by few V-cosets and satisfies |V|≤|A|. For every η<1, polynomially many uniform samples suffice statistically, with cost polynomial in the doubling constant and proportional to (1−η)^−1; this radius dependence is sharp. Under a specified hardness assumption for learning parities with noise (search-LPN), however, no polynomial-time sample-only learner achieves even constant covering cost, including when the latent support is unique. At fixed structural parameters and the same constant covering budget, adding exact membership queries to B permits polynomial-time recovery. The general query learner constructs a short structural list and uses fresh samples to select one common output through a majority-coverage rule. Persistent structured cores make this candidate construction possible. At doubling one, a complementary distinction appears at η=1/3: coarse recovery remains polynomial time, while exact recovery requires exponentially many accesses in the worst case when latent cardinality is unknown.
ER -