18 citations · 73 across the 13 of their papers we have counts for
15 papers
Grokking through the Lens of Minimum-Norm Interpolation
Gil Kur, Ileana Rugina, Clémentine Carla Juliette Dominé +1
Grokking shows that fitting the training data and learning the underlying signal can occur at very different stages. However, existing theories offer limited quantitative insight i…
On the Optimality of Random Partial Sphere Coverings in High Dimensions
Steven Hoehner, Gil Kur
Given geodesic caps on the unit sphere in , whose total normalized surface area is one, what is the maximal proportion of the sphere that their union can cover? I…
On the Variance, Admissibility, and Stability of Empirical Risk Minimization
Gil Kur, Eli Putterman, Alexander Rakhlin
It is well known that Empirical Risk Minimization (ERM) may attain minimax suboptimal rates in terms of the mean squared error (Birgé and Massart, 1993). In this paper, we prove th…
Tyler's and Maronna's M-estimators: Non-Asymptotic Concentration Results
Elad Romanov, Gil Kur, Boaz Nadler
Tyler's and Maronna's M-estimators, as well as their regularized variants, are popular robust methods to estimate the scatter or covariance matrix of a multivariate distribution. I…
An Efficient Minimax Optimal Estimator For Multivariate Convex Regression
Gil Kur, Eli Putterman
This work studies the computational aspects of multivariate convex regression in dimensions . Our results include the \emph{first} estimators that are minimax optimal (up…
On the Minimal Error of Empirical Risk Minimization
Gil Kur, Alexander Rakhlin
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 sh…
A bounded-noise mechanism for differential privacy
Yuval Dagan, Gil Kur
We present an asymptotically optimal differentially private mechanism for answering multiple, adaptively asked, -sensitive queries, settling the conjecture of Steinke an…
On Suboptimality of Least Squares with Application to Estimation of Convex Bodies
Gil Kur, Alexander Rakhlin, Adityanand Guntuboyina
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,…
Convex Regression in Multidimensions: Suboptimality of Least Squares Estimators
Gil Kur, Fuchang Gao, Adityanand Guntuboyina +1
Under the usual nonparametric regression model with Gaussian errors, Least Squares Estimators (LSEs) over natural subclasses of convex functions are shown to be suboptimal for esti…
Double descent in the condition number
Tomaso Poggio, Gil Kur, Andrzej Banburski
In solving a system of linear equations in variables , the condition number of the matrix measures how much errors in the data affect the solution .…
Intrinsic and Dual Volume Deviations of Convex Bodies and Polytopes
Florian Besau, Steven Hoehner, Gil Kur
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…
Optimality of Maximum Likelihood for Log-Concave Density Estimation and Bounded Convex Regression
Gil Kur, Yuval Dagan, Alexander Rakhlin
In this paper, we study two problems: (1) estimation of a -dimensional log-concave distribution and (2) bounded multivariate convex regression with random design with an underly…
Space lower bounds for linear prediction in the streaming model
Yuval Dagan, Gil Kur, Ohad Shamir
We show that fundamental learning tasks, such as finding an approximate linear separator or linear regression, require memory at least \emph{quadratic} in the dimension, in a natur…
A Concentration Inequality for Random Polytopes, Dirichlet-Voronoi Tiling Numbers and the Geometric Balls and Bins Problem
Steven Hoehner, Gil Kur
Our main contribution is a concentration inequality for the symmetric volume difference of a convex body with positive Gaussian curvature and a circumscribed random polytop…
Approximation of the Euclidean ball by polytopes with a restricted number of facets
Gil Kur
We prove that there is an absolute constant such that for every and there exists a polytope with at most fa…