Compressive learning is an emerging approach to drastically reduce the memory
footprint of large-scale learning, by first summarizing a large dataset into a
low-dimensional sketch vector, and then decoding from this sketch the latent
information needed for learning. In light of recent progress on information
preservation guarantees for sketches based on random features, a major
objective is to design easy-to-tune algorithms (called decoders) to robustly
and efficiently extract this information. To address the underlying non-convex
optimization problems, various heuristics have been proposed. In the case of
compressive clustering, the standard heuristic is CL-OMPR, a variant of sliding
Frank-Wolfe. Yet, CL-OMPR is hard to tune, and the examination of its
robustness was overlooked. In this work, we undertake a scrutinized examination
of CL-OMPR to circumvent its limitations. In particular, we show how this
algorithm can fail to recover the clusters even in advantageous scenarios. To
gain insight, we show how the deficiencies of this algorithm can be attributed
to optimization difficulties related to the structure of a correlation function
appearing at core steps of the algorithm. To address these limitations, we
propose an alternative decoder offering substantial improvements over CL-OMPR.
Its design is notably inspired from the mean shift algorithm, a classic
approach to detect the local maxima of kernel density estimators. The proposed
algorithm can extract clustering information from a sketch of the MNIST dataset
that is 10 times smaller than previously.

压缩学习是一种新兴方法，通过首先将大规模数据集总结为低维度的草图向量，然后从这个草图中解码出学习所需的潜在信息，从而极大地减少大规模学习的内存占用。我们的研究旨在设计易于调优的算法（称为解码器），以稳健高效地提取这些信息，然后通过分析压缩聚类中的 CL-OMPR 算法的局限性，提出了一种改进方案，大大提高了信息提取的准确性和效率。