**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# Reprint of: Weak epsilon-nets have basis of size O(1/epsilonlog(1/epsilon)) in any dimension

2010

Journal paper

Journal paper

Abstract

Given a set P of n points in R-d and epsilon > 0, we consider the problem of constructing weak E-nets for P. We show the following: pick a random sample Q of size O(1/epsilon log(1/epsilon)) from P. Then, with constant probability, a weak epsilon-net of P can be constructed from only the points of Q. This shows that weak epsilon-nets in R-d can be computed from a subset of P of size O(1/epsilon log(1/epsilon)) with only the constant of proportionality depending on the dimension, unlike all previous work where the size of the subset had the dimension in the exponent of 1/epsilon. However, our final weak epsilon-nets still have a large size (with the dimension appearing in the exponent of 1/epsilon). (C) 2010 Published by Elsevier B.V.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (31)

Related publications (33)

Continuous function

In mathematics, a continuous function is a function such that a continuous variation (that is a change without jump) of the argument induces a continuous variation of the value of the function. This means that there are no abrupt changes in value, known as discontinuities. More precisely, a function is continuous if arbitrarily small changes in its value can be assured by restricting to sufficiently small changes of its argument. A discontinuous function is a function that is .

Limit of a function

Although the function \tfrac{\sin x}{x} is not defined at zero, as x becomes closer and closer to zero, \tfrac{\sin x}{x} becomes arbitrarily close to 1. In other words, the limit of \tfrac{\sin x}{x}, as x approaches zero, equals 1. In mathematics, the limit of a function is a fundamental concept in calculus and analysis concerning the behavior of that function near a particular input. Formal definitions, first devised in the early 19th century, are given below. Informally, a function f assigns an output f(x) to every input x.

Compact space

In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space. The idea is that a compact space has no "punctures" or "missing endpoints", i.e., it includes all limiting values of points. For example, the open interval (0,1) would not be compact because it excludes the limiting values of 0 and 1, whereas the closed interval [0,1] would be compact.

Weighted least squares polynomial approximation uses random samples to determine projections of functions onto spaces of polynomials. It has been shown that, using an optimal distribution of sample locations, the number of samples required to achieve quasi ...

2020Rachid Guerraoui, Anne-Marie Kermarrec, Sadegh Farhadkhani, Rafael Pereira Pires, Rishi Sharma, Marinus Abraham de Vos

We present Epidemic Learning ( EL ), a simple yet powerful decentralized learning (DL) algorithm that leverages changing communication topologies to achieve faster model convergence compared to conventional DL approaches. At each round of EL, each node sen ...

2023Estimation of causal effects using machine learning methods has become an active research field in econometrics. In this paper, we study the finite sample performance of meta-learners for estimation of heterogeneous treatment effects under the usage of sam ...

2022