Reliable Learning of Halfspaces under Gaussian Marginals

Traditional agnostic learning models struggle in scenarios where one type of error is far costlier than others. The reliable agnostic model addresses this by prioritizing the reduction of the costlier error type. However, even in distribution-specific settings (like Gaussian marginals), efficiently learning halfspaces in this model remains challenging due to the inherent complexity of minimizing the one-sided error.

This research introduces a novel algorithm that efficiently learns Gaussian halfspaces under the reliable agnostic model. This approach leverages a clever combination of techniques, including a careful relaxation of the optimality condition, the construction of a low-dimensional subspace through a random walk, and a novel analysis based on a specific distributional assumption to ensure the reliability condition holds. The algorithm achieves significantly lower computational complexity than existing approaches. Further, a lower bound is established, demonstrating the near-optimality of the proposed algorithm’s complexity.