More Like this

1. Simple 𝑝-adic Lie groups with abelian Lie algebras

   https://doi.org/10.1515/crelle-2024-0030  

   Caprace, Pierre-Emmanuel; Minasyan, Ashot; Osin, Denis (June 2024, Journal für die reine und angewandte Mathematik (Crelles Journal))

   Abstract For each prime 𝑝 and each positive integer 𝑑, we construct the first examples of second countable, topologically simple 𝑝-adic Lie groups of dimension 𝑑 whose Lie algebras are abelian.This answers several questions of Glöckner and Caprace–Monod.The proof relies on a generalization of small cancellation methods that applies to central extensions of acylindrically hyperbolic groups. 

   more » « less
2. Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions

   Asi, Hilal; Liu, Daogao; Tian, Kevin (June 2024, https://doi.org/10.48550/arXiv.2406.02789)

   This paper studies differentially private stochastic convex optimization (DP-SCO) in the presence of heavy-tailed gradients, where only a 𝑘 kth-moment bound on sample Lipschitz constants is assumed, instead of a uniform bound. The authors propose a reduction-based approach that achieves the first near-optimal error rates (up to logarithmic factors) in this setting. Specifically, under ( 𝜖 , 𝛿 ) (ϵ,δ)-approximate differential privacy, they achieve an error bound of 𝐺 2 𝑛 + 𝐺 𝑘 ⋅ ( 𝑑 𝑛 𝜖 ) 1 − 1 𝑘 , n ​ G 2 ​ ​ +G k ​ ⋅( nϵ d ​ ​ ) 1− k 1 ​ , up to a mild polylogarithmic factor in 1 𝛿 δ 1 ​ , where 𝐺 2 G 2 ​ and 𝐺 𝑘 G k ​ are the 2nd and 𝑘 kth moment bounds on sample Lipschitz constants. This nearly matches the lower bound established by Lowy and Razaviyayn (2023). Beyond the basic result, the authors introduce a suite of private algorithms that further improve performance under additional assumptions: an optimal algorithm under a known-Lipschitz constant, a near-linear time algorithm for smooth functions, and an optimal linear-time algorithm for smooth generalized linear models. 

   more » « less
3. Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension

   Chandrasekaran, Gautam; Klivans, Adam; Kontonis, Vasilis; Meka, Raghu; Stavropoulos, Konstantinos (April 2025, https://doi.org/10.48550/arXiv.2407.00966)

   Traditional models of supervised learning require a learner, given examples from an arbitrary joint distribution on 𝑅 𝑑 × { ± 1 } R d ×{±1}, to output a hypothesis that competes (to within 𝜖 ϵ) with the best fitting concept from a class. To overcome hardness results for learning even simple concept classes, this paper introduces a smoothed-analysis framework that only requires competition with the best classifier robust to small random Gaussian perturbations. This subtle shift enables a wide array of learning results for any concept that (1) depends on a low-dimensional subspace (multi-index model) and (2) has bounded Gaussian surface area. This class includes functions of halfspaces and low-dimensional convex sets, which are only known to be learnable in non-smoothed settings with respect to highly structured distributions like Gaussians. The analysis also yields new results for traditional non-smoothed frameworks such as learning with margin. In particular, the authors present the first algorithm for agnostically learning intersections of 𝑘 k-halfspaces in time 𝑘 ⋅ poly ( log ⁡ 𝑘 , 𝜖 , 𝛾 ) k⋅poly(logk,ϵ,γ), where 𝛾 γ is the margin parameter. Previously, the best-known runtime was exponential in 𝑘 k (Arriaga and Vempala, 1999). 

   more » « less
4. Geometric Pattern Matching Reduces to k -SUM

   https://doi.org/10.1007/s00454-021-00324-1  

   Aronov, Boris; Cardinal, Jean (January 2021, Discrete & Computational Geometry)

   We prove that some exact geometric pattern matching problems reduce in linear time to 𝑘-SUM when the pattern has a fixed size 𝑘. This holds in the real RAM model for searching for a similar copy of a set of 𝑘≥3 points within a set of n points in the plane, and for searching for an affine image of a set of 𝑘≥𝑑+2 points within a set of n points in d-space. As corollaries, we obtain improved real RAM algorithms and decision trees for the two problems. In particular, they can be solved by algebraic decision trees of near-linear height. 

   more » « less
5. Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering

   Narayanan, S; Silwal, S; Indyk, P; Zamir, O (January 2021, International Conference on Machine Learning)

   Random dimensionality reduction is a versatile tool for speeding up algorithms for high-dimensional problems. We study its application to two clustering problems: the facility location problem, and the single-linkage hierarchical clustering problem, which is equivalent to computing the minimum spanning tree. We show that if we project the input pointset 𝑋 onto a random 𝑑=𝑂(𝑑𝑋)-dimensional subspace (where 𝑑𝑋 is the doubling dimension of 𝑋), then the optimum facility location cost in the projected space approximates the original cost up to a constant factor. We show an analogous statement for minimum spanning tree, but with the dimension 𝑑 having an extra loglog𝑛 term and the approximation factor being arbitrarily close to 1. Furthermore, we extend these results to approximating solutions instead of just their costs. Lastly, we provide experimental results to validate the quality of solutions and the speedup due to the dimensionality reduction. Unlike several previous papers studying this approach in the context of 𝑘-means and 𝑘-medians, our dimension bound does not depend on the number of clusters but only on the intrinsic dimensionality of 𝑋. 

   more » « less