Optimal Approximations Made Easy

2020-08-20 · Mónika Csikós, Nabil H. Mustafa

The fundamental result of Li, Long, and Srinivasan on approximations of set systems has become a key tool across several communities such as learning theory, algorithms, computational geometry, combinatorics and data analysis. The goal of this paper is to give a modular, self-contained, intuitive proof of this result for finite set systems. The only ingredient we assume is the standard Chernoff's concentration bound. This makes the proof accessible to a wider audience, readers not familiar with techniques from statistical learning theory, and makes it possible to be covered in a single self-contained lecture in a geometry, algorithms or combinatorics course.

📄 PDF Abstract BibTeX arXiv:2008.08970

Code (0)

등록된 구현이 없습니다.

Tasks

Learning Theory

Optimal Piecewise Local-Linear Approximations

2018-06-27 · Kartik Ahuja, William Zame, Mihaela van der Schaar

Existing works on "black-box" model interpretation use local-linear approximations to explain the predictions made for each data instance in terms of the importance assigned to the different features for arriving at the …

Clustering

Improved Fixed-Rank Nyström Approximation via QR Decomposition: Practical and Theoretical Aspects

2017-08-08 · Farhad Pourkamali-Anaraki, Stephen Becker

The Nystrom method is a popular technique that uses a small number of landmark points to compute a fixed-rank approximation of large kernel matrices that arise in machine learning problems. In practice, to ensure high qu…

Interpretable & Explorable Approximations of Black Box Models

2017-07-04 · Himabindu Lakkaraju, Ece Kamar, Rich Caruana, Jure Leskovec

We propose Black Box Explanations through Transparent Approximations (BETA), a novel model agnostic framework for explaining the behavior of any black-box classifier by simultaneously optimizing for fidelity to the origi…

Bayesian Optimal Active Search and Surveying

2012-06-27 · Roman Garnett, Yamuna Krishnamurthy, Xuehan Xiong, Jeff Schneider 외

We consider two active binary-classification problems with atypical objectives. In the first, active search, our goal is to actively uncover as many members of a given class as possible. In the second, active surveying, …

Binary Classification

ChebNet: Efficient and Stable Constructions of Deep Neural Networks with Rectified Power Units via Chebyshev Approximations

2019-11-07 · Shanshan Tang, Bo Li, Haijun Yu

In a previous study [B. Li, S. Tang and H. Yu, Commun. Comput. Phy. 27(2):379-411, 2020], it is shown that deep neural networks built with rectified power units (RePU) as activation functions can give better approximatio…