Pointwise-competitive classifier from class F is required to classify identically to the best classifier in hindsight from F. For noisy, agnostic settings we present a strategy for learning pointwise-competitive classifiers from a finite training sample provided that the classifier can abstain from prediction at a certain region of its choice. For some interesting hypothesis classes and families of distributions, the measure of this rejected region is shown to be diminishing at a fast rate, with high probability. Exact implementation of the proposed learning strategy is dependent on an ERM oracle that can be hard to compute in the agnostic case. We thus consider a heuristic approximation procedure that is based on SVMs, and show empirically that this algorithm consistently outperforms a traditional rejection mechanism based on distance from decision boundary.

This paper examines the possibility of a `reject option' in the context of least squares regression. It is shown that using rejection it is theoretically possible to learn `selective' regressors that can $\epsilon$-pointwise track the best regressor in hindsight from the same hypothesis class, while rejecting only a bounded portion of the domain. Moreover, the rejected volume vanishes with the training set size, under certain conditions. We then develop efficient and exact implementation of these selective regressors for the case of linear regression. Empirical evaluation over a suite of real-world datasets corroborates the theoretical analysis and indicates that our selective regressors can provide substantial advantage by reducing estimation error.

For a learning problem whose associated excess loss class is $(\beta,B)$-Bernstein, we show that it is theoretically possible to track the same classification performance of the best (unknown) hypothesis in our class, provided that we are free to abstain from prediction in some region of our choice. The (probabilistic) volume of this rejected region of the domain is shown to be diminishing at rate $O(B\theta (\sqrt{1/m}))^\beta)$, where $\theta$ is Hanneke's disagreement coefficient. The strategy achieving this performance has computational barriers because it requires empirical error minimization in an agnostic setting. Nevertheless, we heuristically approximate this strategy and develop a novel selective classification algorithm using constrained SVMs. We show empirically that the resulting algorithm consistently outperforms the traditional rejection mechanism based on distance from decision boundary.

Bandwidth-optimal open-loop near-video-on-demand streaming (NVOD) entails the optimal assignment of transmission rates to a large number of program segments. These are transmitted concurrently and repetitively at their assigned rates. At any given time in its viewing of the program, a client must record data belonging to a contiguous subsequence of the segments for subsequent display. Limited client recording rates and storage capacity affect the rate assignments. In practice, the concurrent streams must be time-multiplexed onto a single channel, and efficient operation of the client disk drive used to store received data until its viewing prevents fine-grain multiplexing. The bucket-interleaving multiplexing scheme presented in this paper guarantees that each segment is repeated in its entirety within any contiguous time interval of the appropriate length, and reduces the required client "rate-smoothing" RAM buffer by two orders of magnitude relative to pure earliest-deadline-first multiplexing.