Efficient Learning with Virtual Threshold Gates

AbstractWe reduce learning simple geometric concept classes to learning disjunctions over exponentially many variables. We then apply an online algorithm called Winnow whose number of prediction mistakes grows only logarithmically with the number of variables. The hypotheses of Winnow are linear threshold functions with one weight per variable. We find ways to keep the exponentially many weights of Winnow implicitly so that the time for the algorithm to compute a prediction and update its “virtual” weights is polynomial. Our method can be used to learnd-dimensional axis-parallel boxes whendis variable and unions ofd-dimensional axis-parallel boxes whendis constant. The worst-case number of mistakes of our algorithms for the above classes is optimal to within a constant factor, and our algorithms inherit the noise robustness of Winnow. We think that other online algorithms with multiplicative weight updates whose loss bounds grow logarithmically with the dimension are amenable to our methods