More Like this

1. Optimal angle bounds for Steiner triangulations of polygons

   https://doi.org/10.1137/1.9781611977073.121  

   Christopher J. Bishop (January 2022, Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA))

   For any simple polygon P we compute the optimal upper and lower angle bounds for triangulating P with Steiner points, and show that these bounds can be attained (except in one special case). The sharp angle bounds for an N-gon are computable in time O(N), even though the number of triangles needed to attain these bounds has no bound in terms of N alone. In general, the sharp upper and lower bounds cannot both be attained by a single triangulation, although this does happen in some cases. For example, we show that any polygon with minimal interior angle θ has a triangulation with all angles in the interval I = [θ, 90°–min(36°, θ)/2], and for θ ≤ 36° both bounds are best possible. Surprisingly, we prove the optimal angle bounds for polygonal triangulations are the same as for triangular dissections. The proof of this verifies, in a stronger form, a 1984 conjecture of Gerver. 

   more » « less
2. Extreme singular values of inhomogeneous sparse random rectangular matrices

   https://doi.org/10.3150/23-BEJ1699  

   Dumitriu, Ioana; Zhu, Yizhe (November 2024, Bernoulli)

   We develop a unified approach to bounding the largest and smallest singular values of an inhomogeneous random rectangular matrix, based on the non-backtracking operator and the Ihara-Bass formula for general random Hermitian matrices with a bipartite block structure. We obtain probabilistic upper (respectively, lower) bounds for the largest (respectively, smallest) singular values of a large rectangular random matrix X. These bounds are given in terms of the maximal and minimal 2-norms of the rows and columns of the variance profile of X. The proofs involve finding probabilistic upper bounds on the spectral radius of an associated non-backtracking matrix B. The two-sided bounds can be applied to the centered adjacency matrix of sparse inhomogeneous Erd˝os-Rényi bipartite graphs for a wide range of sparsity, down to criticality. In particular, for Erd˝os-Rényi bipartite graphs G(n,m, p) with p = ω(log n)/n, and m/n→ y ∈ (0,1), our sharp bounds imply that there are no outliers outside the support of the Marˇcenko-Pastur law almost surely. This result extends the Bai-Yin theorem to sparse rectangular random matrices. 

   more » « less
3. Sharp lower bounds on the manifold widths of Sobolev and Besov spaces

   https://doi.org/10.1016/j.jco.2024.101884  

   Siegel, Jonathan W (December 2024, Journal of Complexity)

   We consider the problem of determining the manifold $$n$$-widths of Sobolev and Besov spaces with error measured in the $$L_p$$-norm. The manifold widths control how efficiently these spaces can be approximated by general non-linear parametric methods with the restriction that the parameter selection and parameterization maps must be continuous. Existing upper and lower bounds only match when the Sobolev or Besov smoothness index $$q$$ satisfies $$q\leq p$$ or $$1 \leq p \leq 2$$. We close this gap and obtain sharp lower bounds for all $$1 \leq p,q \leq \infty$$ for which a compact embedding holds. A key part of our analysis is to determine the exact value of the manifold widths of finite dimensional $$\ell^M_q$$-balls in the $$\ell_p$$-norm when $$p\leq q$$. Although this result is not new, we provide a new proof and apply it to lower bounding the manifold widths of Sobolev and Besov spaces. Our results show that the Bernstein widths, which are typically used to lower bound the manifold widths, decay asymptotically faster than the manifold widths in many cases. 

   more » « less
4. Off-policy Evaluation Beyond Overlap: Sharp Partial Identification Under Smoothness

   Khan, Samir; Saveki, Martin; Ugander, Johan (July 2024, International Conference on Machine Learning (ICML))

   Off-policy evaluation, and the complementary problem of policy learning, use historical data collected under a logging policy to estimate and/or optimize the value of a target policy. Methods for these tasks typically assume overlap between the target and logging policy, enabling solutions based on importance weighting and/or imputation. Absent such an overlap assumption, existing work either relies on a well-specified model or optimizes needlessly conservative bounds. In this work, we develop methods for no-overlap policy evaluation without a well-specified model, relying instead on non-parametric assumptions on the expected outcome, with a particular focus on Lipschitz smoothness. Under such assumptions we are able to provide sharp bounds on the off-policy value, along with asymptotically optimal estimators of those bounds. For Lipschitz smoothness, we construct a pair of linear programs that upper and lower bound the contribution of the no-overlap region to the off-policy value. We show that these programs have a concise closed form solution, and that their solutions converge under the Lipschitz assumption to the sharp partial identification bounds at a minimax optimal rate, up to log factors. We demonstrate the effectiveness our methods on two semi-synthetic examples, and obtain informative and valid bounds that are tighter than those possible without smoothness assumptions. 

   more » « less
5. The size of wild Kloosterman sums in number fields and function fields

   https://doi.org/10.1007/s11854-023-0325-9  

   Sawin, Will (December 2023, Journal d'Analyse Mathématique)

   We study p-adic hyper-Kloosterman sums, a generalization of the Kloosterman sum with a parameter k that recovers the classical Kloosterman sum when k = 2, over general p-adic rings and even equal characteristic local rings. These can be evaluated by a simple stationary phase estimate when k is not divisible by p, giving an essentially sharp bound for their size. We give a more complicated stationary phase estimate to evaluate them in the case when k is divisible by p. This gives both an upper bound and a lower bound showing the upper bound is essentially sharp. This generalizes previously known bounds in the case of ℤ/p. The lower bounds in the equal characteristic case have two applications to function field number theory, showing that certain short interval sums and certain moments of Dirichlet L-functions do not, as one might hope, admit square-root cancellation. 

   more » « less