Majorizing Measures, Sequential Complexities, and Online Learning
We introduce the technique of generic chaining and majorizing measures for controlling sequential Rademacher complexity. We relate majorizing measures to the notion of fractional covering numbers, which we show to be dominated in terms of sequential scale-sensitive dimensions in a horizon-independent way, and, under additional complexity assumptions establish a tight control on worst-case sequential Rademacher complexity in terms of the integral of sequential scale-sensitive dimension. Finally, we establish a tight contraction inequality for worst-case sequential Rademacher complexity. The above constitutes the resolution of a number of outstanding open problems in extending the classical theory of empirical processes to the sequential case, and, in turn, establishes sharp results for online learning.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Online Learning via Sequential Complexities
We consider the problem of sequential prediction and provide tools to study the minimax value of the associated game. Classical statistical learning theory provides several useful complexity measures to study learning wi…
Learning TheoryPredictionMajorizing Measures, Codes, and Information
The majorizing measure theorem of Fernique and Talagrand is a fundamental result in the theory of random processes. It relates the boundedness of random processes indexed by elements of a metric space to complexity measu…
Image segmentation by optimal and hierarchical piecewise constant approximations
Piecewise constant image approximations of sequential number of segments or clusters of disconnected pixels are treated. The method of majorizing of optimal approximation sequence by hierarchical sequence of image approx…
Image SegmentationSemantic SegmentationHierarchical pixel clustering for image segmentation
In the paper a piecewise constant image approximations of sequential number of pixel clusters or segments are treated. A majorizing of optimal approximation sequence by hierarchical sequence of image approximations is st…
ClusteringImage SegmentationSegmentationSemantic SegmentationMajorizing Stress Formula Two
Modifications of the smacof algorithm for multidimensional scaling are proposed that provide a convergent majorization algorithm for Kruskal's stress formula two.