Localization of VC classes: Beyond local Rademacher complexities

Zhivotovskiy Nikita; Hanneke S.

doi:10.1016/j.tcs.2017.12.029

Publications

Article

Localization of VC classes: Beyond local Rademacher complexities

Theoretical Computer Science. 2018. Vol. 9. No. 742. P. 27-49.

Zhivotovskiy N., Hanneke S.

In statistical learning the excess risk of empirical risk minimization (ERM) is controlled by (COMPn(F)n)α, where n is a size of a learning sample, COMPn(F) is a complexity term associated with a given class F and α∈[12,1] interpolates between slow and fast learning rates. In this paper we introduce an alternative localization approach for binary classificationthat leads to a novel complexity measure: fixed points of the local empirical entropy. We show that this complexity measure gives a tight control over COMPn(F) in the upper bounds under bounded noise. Our results are accompanied by a minimax lower bound that involves the same quantity. In particular, we practically answer the question of optimality of ERM under bounded noise for general VC classes.

Priority areas: IT and mathematics mathematics

Language: English

DOI

Text on another site

Keywords: Statistical learning theory

Conference on Learning Theory, 25-28 June 2019, Phoenix, USA

Vol. 99. 2019.

Volume 99: Conference on Learning Theory, 25-28 June 2019, Phoenix, USA

Added: Oct 31, 2020

Optimal learning via local entropies and sample compression

Zhivotovskiy N. Proceedings of Machine Learning Research. 2017. Vol. 65. P. 2023-2065.

Under margin assumptions, we prove several risk bounds, represented via the distribution dependent local entropies of the classes or the sizes of specific sample compression schemes. In some cases, our guarantees are optimal up to constant factors for families of classes. We discuss limitations of our approach and give several applications. In particular, we provide a new tight PAC bound for the hard-margin SVM, an extended analysis of certain empirical risk minimizers under log-concave distributions, a new variant of an online to batch conversion, and distribution dependent localized bounds in the aggregation framework. As a part of our results, we give a new upper bound for the uniform deviations under Bernstein assumptions, which may be of independent interest. The proofs for the sample compression schemes are based on the moment method combined with the analysis of voting algorithms.

Added: Dec 6, 2018

Математическое разрешение парадокса Гиббса

Маслов В. П. Математические заметки. 2011. Т. 89. № 2. С. 272-284.

In this paper, we construct a new distribution corresponding to a real noble gas as well as the equation of state for it.

Added: Apr 12, 2012

Сабейские этюды

Коротаев А. В. М.: Восточная литература, 1997.

Added: Mar 9, 2013

Математическое моделирование социальных процессов

Edited by: А. Михайлов Вып. 14. М.: Социологический факультет МГУ, 2012.

Added: Mar 14, 2013

Оптимальный особый режим и режим с учащающимися переключениями в задаче управления колебаниями струны с закрепленными концами

Манита Л. А. Прикладная математика и механика. 2010. Т. 74. № 5. С. 873-880.

The problem of minimizing the root mean square deviation of a uniform string with clamped ends from an equilibrium position is investigated. It is assumed that the initial conditions are specified and the ends of the string are clamped. The Fourier method is used, which enables the control problem with a partial differential equation to be reduced to a control problem with a denumerable system of ordinary differential equations. For the optimal control problem in the l2 space obtained, it is proved that the optimal synthesis contains singular trajectories and chattering trajectories. For the initial problem of the optimal control of the vibrations of a string it is also proved that there is a unique solution for which the optimal control has a denumerable number of switchings in a finite time interval.

Added: Apr 12, 2012

Оптимальный синтез в бесконечномерном пространстве

Манита Л. А., Борисов В. Ф., Зеликин М. И. Труды Математического института им. В.А. Стеклова РАН. 2010. Т. 271. С. 40-58.

For a class of optimal control problems and Hamiltonian systems generated by these problems in the space l 2, we prove the existence of extremals with a countable number of switchings on a finite time interval. The optimal synthesis that we construct in the space l 2 forms a fiber bundle with piecewise smooth two-dimensional fibers consisting of extremals with a countable number of switchings over an infinite-dimensional basis of singular extremals.

Added: Apr 12, 2012

Dynamics of Information Systems: Mathematical Foundations

Iss. 20. NY: Springer, 2012.

This proceedings publication is a compilation of selected contributions from the “Third International Conference on the Dynamics of Information Systems” which took place at the University of Florida, Gainesville, February 16–18, 2011. The purpose of this conference was to bring together scientists and engineers from industry, government, and academia in order to exchange new discoveries and results in a broad range of topics relevant to the theory and practice of dynamics of information systems. Dynamics of Information Systems: Mathematical Foundation presents state-of-the art research and is intended for graduate students and researchers interested in some of the most recent discoveries in information theory and dynamical systems. Scientists in other disciplines may also benefit from the applications of new developments to their own area of study.

Added: Dec 19, 2012

Асимптотические разложения решений пятого уравнения Пенлеве

Парусникова А. В., Брюно А. Д. Институт прикладной математики им. М.В. Келдыша Российской академии наук, 2010. № 39.

Added: Apr 18, 2012

Bounded limit cycles of polynomial foliations of ℂP²

Goncharuk N. B., Kudryashov Y. arxiv.org. math. Cornell University, 2015. No. 1504.03313.

In this article we prove in a new way that a generic polynomial vector field in ℂ² possesses countably many homologically independent limit cycles. The new proof needs no estimates on integrals, provides thinner exceptional set for quadratic vector fields, and provides limit cycles that stay in a bounded domain.

Added: Apr 15, 2015

Conjugacy classes in discrete Heisenberg groups

Roman Budylin. arxiv.org. math. Cornell University, 2014

We study some extension of a discrete Heisenberg group coming from the theory of loop-groups and find invariants of conjugacy classes in this group. In some cases including the case of the integer Heisenberg group we make these invariants more explicit.

Added: Nov 14, 2014