Empirical Hypothesis Space Reduction
This addresses the issue of slow convergence in regularized empirical risk minimization for machine learning practitioners, offering a significant improvement over existing methods.
The paper tackles the problem of selecting regularization coefficients in high-dimensional settings, where existing methods are over-conservative and lead to slow convergence dependent on hypothesis space dimension. It proposes an algorithm that achieves faster convergence with a generalization error bound of O(√(log n/n)), independent of the dimension, by empirically reducing the hypothesis space without losing the true optimum.
Selecting appropriate regularization coefficients is critical to performance with respect to regularized empirical risk minimization problems. Existing theoretical approaches attempt to determine the coefficients in order for regularized empirical objectives to be upper-bounds of true objectives, uniformly over a hypothesis space. Such an approach is, however, known to be over-conservative, especially in high-dimensional settings with large hypothesis space. In fact, an existing generalization error bound in variance-based regularization is $O(\sqrt{d \log n/n})$, where $d$ is the dimension of hypothesis space, and thus the number of samples required for convergence linearly increases with respect to $d$. This paper proposes an algorithm that calculates regularization coefficient, one which results in faster convergence of generalization error $O(\sqrt{\log n/n})$ and whose leading term is independent of the dimension $d$. This faster convergence without dependence on the size of the hypothesis space is achieved by means of empirical hypothesis space reduction, which, with high probability, successfully reduces a hypothesis space without losing the true optimum solution. Calculation of uniform upper bounds over reduced spaces, then, enables acceleration of the convergence of generalization error.