Source author record

Gil Kur

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Machine Learning math.MG math.ST Statistics Theory Computational Geometry math.PR

Catalog footprint

Research overview

7works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

On the Minimal Error of Empirical Risk Minimization

We study the minimal error of the Empirical Risk Minimization (ERM) procedure in the task of regression, both in the random and the fixed design settings. Our sharp lower bounds shed light on the possibility (or impossibility) of adapting to simplicity of the model generating the data. In the fixed design setting, we show that the error is governed by the global complexity of the entire class. In contrast, in random design, ERM may only adapt to simpler models if the local neighborhoods around the regression function are nearly as complex as the class itself, a somewhat counter-intuitive conclusion. We provide sharp lower bounds for performance of ERM for both Donsker and non-Donsker classes. We also discuss our results through the lens of recent studies on interpolation in overparameterized models.

preprint2020arXiv

A Concentration Inequality for Random Polytopes, Dirichlet-Voronoi Tiling Numbers and the Geometric Balls and Bins Problem

Our main contribution is a concentration inequality for the symmetric volume difference of a $C^2$ convex body with positive Gaussian curvature and a circumscribed random polytope with a restricted number of facets, for any probability measure on the boundary with a positive density function. We also show that the Dirichlet-Voronoi tiling numbers satisfy $\text{div}_{n-1} = (2πe)^{-1}(n+\ln n) + O(1)$ , which improves a classical result of Zador by a factor of $o(n)$ . In addition, we provide a remarkable open problem which is the natural geometric generalization of the famous and fundamental "balls and bins" problem from probability. This problem is tightly connected to the optimality of random polytopes in high dimensions.

preprint2020arXiv

Approximation of the Euclidean ball by polytopes with a restricted number of facets

We prove that there is an absolute constant $C$ such that for every $n \geq 2$ and $N\geq 10^n,$ there exists a polytope $P_{n,N} \subset \mathbb{R}^n$ with at most $N$ facets that satisfies $Δ_{v}(D_n,P_{n,N}):=\text{vol}_n\left(D_n ΔP_{n,N}\right)\leq Cn^{-2/(n-1}\text{vol}_n\left(D_n\right)$ and $Δ_{s}(D_n,P_{n,N}):=\text{vol}_{n-1}\left(\partial\left(D_n\cup P_{n,N}\right)\right) - \text{vol}_{n-1}\left(\partial\left(D_n\cap P_{n,N}\right)\right) \leq 4CN^{-\frac{2}{n-1}} \text{vol}_{n-1}\left(\partial D_n\right),$ where $D_n$ is the $n$ -dimensional Euclidean unit ball. This result closes gaps from several papers of Hoehner, Ludwig, Schütt and Werner. The upper bounds are optimal up to absolute constants. This result shows that a polytope with an exponential number of facets (in the dimension) can approximate the $n$ -dimensional Euclidean ball with respect to the aforementioned distances.

preprint2020arXiv

Double descent in the condition number

In solving a system of $n$ linear equations in $d$ variables $Ax=b$ , the condition number of the $n,d$ matrix $A$ measures how much errors in the data $b$ affect the solution $x$ . Estimates of this type are important in many inverse problems. An example is machine learning where the key task is to estimate an underlying function from a set of measurements at random points in a high dimensional space and where low sensitivity to error in the data is a requirement for good predictive performance. Here we discuss the simple observation, which is known but surprisingly little quoted (see Theorem 4.2 in \cite{Brgisser:2013:CGN:2526261}): when the columns of $A$ are random vectors, the condition number of $A$ is highest if $d=n$ , that is when the inverse of $A$ exists. An overdetermined system ( $n>d$ ) as well as an underdetermined system ( $n<d$ ), for which the pseudoinverse must be used instead of the inverse, typically have significantly better, that is lower, condition numbers. Thus the condition number of $A$ plotted as function of $d$ shows a double descent behavior with a peak at $d=n$ .

preprint2020arXiv

Intrinsic and Dual Volume Deviations of Convex Bodies and Polytopes

We establish estimates for the asymptotic best approximation of the Euclidean unit ball by polytopes under a notion of distance induced by the intrinsic volumes. We also introduce a notion of distance between convex bodies that is induced by the Wills functional, and apply it to derive asymptotically sharp bounds for approximating the ball in high dimensions. Remarkably, it turns out that there is a polytope which is almost optimal with respect to all intrinsic volumes simultaneously, up to absolute constants. Finally, we establish asymptotic formulas for the best approximation of smooth convex bodies by polytopes with respect to a distance induced by dual volumes, which originate from Lutwak's dual Brunn-Minkowski theory.

preprint2020arXiv

On Suboptimality of Least Squares with Application to Estimation of Convex Bodies

We develop a technique for establishing lower bounds on the sample complexity of Least Squares (or, Empirical Risk Minimization) for large classes of functions. As an application, we settle an open problem regarding optimality of Least Squares in estimating a convex set from noisy support function measurements in dimension $d\geq 6$ . Specifically, we establish that Least Squares is mimimax sub-optimal, and achieves a rate of $\tildeΘ_d(n^{-2/(d-1)})$ whereas the minimax rate is $Θ_d(n^{-4/(d+3)})$ .

preprint2020arXiv

Optimality of Maximum Likelihood for Log-Concave Density Estimation and Bounded Convex Regression

In this paper, we study two problems: (1) estimation of a $d$ -dimensional log-concave distribution and (2) bounded multivariate convex regression with random design with an underlying log-concave density or a compactly supported distribution with a continuous density. First, we show that for all $d \ge 4$ the maximum likelihood estimators of both problems achieve an optimal risk of $Θ_d(n^{-2/(d+1)})$ (up to a logarithmic factor) in terms of squared Hellinger distance and $L_2$ squared distance, respectively. Previously, the optimality of both these estimators was known only for $d\le 3$ . We also prove that the $ε$ -entropy numbers of the two aforementioned families are equal up to logarithmic factors. We complement these results by proving a sharp bound $Θ_d(n^{-2/(d+4)})$ on the minimax rate (up to logarithmic factors) with respect to the total variation distance. Finally, we prove that estimating a log-concave density - even a uniform distribution on a convex set - up to a fixed accuracy requires the number of samples \emph{at least} exponential in the dimension. We do that by improving the dimensional constant in the best known lower bound for the minimax rate from $2^{-d}\cdot n^{-2/(d+1)}$ to $c\cdot n^{-2/(d+1)}$ (when $d\geq 2$ ).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Gil Kur

Research overview

Is this your work?

7 publications

On the Minimal Error of Empirical Risk Minimization

A Concentration Inequality for Random Polytopes, Dirichlet-Voronoi Tiling Numbers and the Geometric Balls and Bins Problem

Approximation of the Euclidean ball by polytopes with a restricted number of facets

Double descent in the condition number

Intrinsic and Dual Volume Deviations of Convex Bodies and Polytopes

On Suboptimality of Least Squares with Application to Estimation of Convex Bodies

Optimality of Maximum Likelihood for Log-Concave Density Estimation and Bounded Convex Regression

See the researcher in context

Building this map preview