Coresets for the Average Case Error for Finite Query Sets.

Area of Science:

• Machine Learning
• Computational Theory

Background:

• Coresets are weighted subsets approximating data loss functions for query sets.
• Existing methods focus on worst-case error, leading to potentially large coreset sizes.
• The Vapnik-Chervonenkis (VC) dimension often influences coreset size in worst-case scenarios.

Purpose of the Study:

• To introduce and develop algorithms for average-case coresets, relaxing the worst-case error bound.
• To achieve coresets whose size is independent of input size and VC dimension.
• To improve computational efficiency in data approximation tasks.

Main Methods:

• Developed deterministic and randomized algorithms for computing average-case coresets.
• Reduced the average-case coreset problem to the vector summarization problem.
• Proposed a linear-time algorithm for computing weighted subsets in vector summarization.

Main Results:

• Introduced average-case coresets with bounded average error over query sets.
• Demonstrated that coreset size is independent of input size and VC dimension.
• Achieved a linear-time algorithm for vector summarization, improving upon prior work.
• Experimental results show significant practical improvements.

Conclusions:

• Average-case coresets provide a more efficient alternative to worst-case coresets.
• The proposed methods offer substantial computational advantages for data approximation.
• The new approach has broad applicability, including principal component analysis (PCA).