Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces

• URL: http://arxiv.org/abs/2503.15294v3
• Date: Sun, 27 Apr 2025 14:17:16 GMT
• Title: Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces
• Authors: Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak,
• Abstract summary: We prove that the list replicability number of $d$-dimensional $gamma$-margin half-spaces satisfies [ fracd2+1 le mathrmLR(Hd_gamma) le d, ] which grows with dimension.<n>For partial classes, list replicability and global stability do not necessarily follow from bounded Littlestone dimension.
• Score: 0.12815904071470702
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent remarkable advances in learning theory have established that, for total concept classes, list replicability, global stability, differentially private (DP) learnability, and shared-randomness replicability all coincide with the finiteness of Littlestone dimension. Does this equivalence extend to partial concept classes? We answer this question by proving that the list replicability number of $d$-dimensional $\gamma$-margin half-spaces satisfies \[ \frac{d}{2}+1 \le \mathrm{LR}(H^d_\gamma) \le d, \] which grows with dimension. Consequently, for partial classes, list replicability and global stability do not necessarily follow from bounded Littlestone dimension, pure DP-learnability, or shared-randomness replicability. Applying our main theorem, we resolve several open problems: $\bullet$ Every disambiguation of infinite-dimensional large-margin half-spaces to a total concept class has unbounded Littlestone dimension, answering an open question of Alon et al. (FOCS '21). $\bullet$ The maximum list-replicability number of any finite set of points and homogeneous half-spaces in $d$-dimensional Euclidean space is $d$, resolving a problem of Chase et al. (FOCS '23). $\bullet$ Every disambiguation of the Gap Hamming Distance problem in the large gap regime has unbounded public-coin randomized communication complexity. This answers an open question of Fang et al. (STOC '25). $\bullet$ There exists a partial concept class with Littlestone dimension $1$ such that all its disambiguations have infinite Littlestone dimension. This answers a question of Cheung et al. (ICALP '23). Our lower bound follows from a topological argument based on the local Borsuk-Ulam theorem of Chase, Chornomaz, Moran, and Yehudayoff (STOC '24). For the upper bound, we construct a list-replicable learning rule using the generalization properties of SVMs.

Related papers

• On Reductions and Representations of Learning Problems in Euclidean Spaces [15.07787640047213]
  Many practical prediction algorithms represent inputs in Euclidean space and replace the discrete 0/1 classification loss with a real-trivial surrogate loss. We develop a generalization of the Borsuk-Ulam Theorem that combines the classical topological approach with convexity considerations. We also present natural classification tasks that can be represented in much smaller dimensions by leveraging randomness.
  arXiv  Detail & Related papers  (2024-11-16T12:09:37Z)
• Bridging the Gap Between Approximation and Learning via Optimal Approximation by ReLU MLPs of Maximal Regularity [8.28720658988688]
  We identify a class of ReLU multilayer perceptions (MLPs) that are optimal function approximators and are statistically well-behaved. We achieve this by avoiding the standard approach to constructing optimal ReLU approximators, which sacrifices by relying on small spikes.
  arXiv  Detail & Related papers  (2024-09-18T22:05:07Z)
• Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem [26.292576184028924]
  This work continues to investigate the link between differentially private (DP) and online learning. We show that for general classification tasks, DP learnability implies online learnability.
  arXiv  Detail & Related papers  (2024-07-10T15:43:30Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Improved Hardness Results for Learning Intersections of Halfspaces [2.1393480341554736]
  We show strong (and surprisingly simple) lower bounds for weakly learning intersections of halfspaces in the improper setting. We significantly narrow this gap by showing that even learning $omega(log log N)$ halfspaces in $N$ takes super-polynomial time. Specifically, we show that for any $k$ halfspaces in dimension $N$ requires accuracy $N-Omega(k)$, or exponentially many queries.
  arXiv  Detail & Related papers  (2024-02-25T05:26:35Z)
• Local Borsuk-Ulam, Stability, and Replicability [16.6959756920423]
  We show that both list-replicable and globally stable learning are impossible in the PAC setting. Specifically, we establish optimal bounds for list replicability and global stability numbers in finite classes.
  arXiv  Detail & Related papers  (2023-11-02T21:10:16Z)
• Principle of minimal singularity for Green's functions [1.8855270809505869]
  We consider a new kind of analytic continuation of correlation functions, inspired by two approaches to underdetermined Dyson-Schwinger equations in $D$-dimensional spacetime. We derive rapidly convergent results for the Hermitian quartic and non-Hermitian cubic theories.
  arXiv  Detail & Related papers  (2023-09-05T13:06:57Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  We show that our algorithm achieves an $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ are the cardinalities of the state and action spaces
  arXiv  Detail & Related papers  (2023-05-15T05:37:32Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems. We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
  arXiv  Detail & Related papers  (2023-02-03T03:19:14Z)
• A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D Shape Matching [69.14632473279651]
  We present a scalable algorithm for globally optimizing over the space of geometrically consistent mappings between 3D shapes. We propose a novel primal coupled with a Lagrange dual problem that is several orders of magnitudes faster than previous solvers.
  arXiv  Detail & Related papers  (2022-04-27T09:47:47Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
  arXiv  Detail & Related papers  (2021-07-13T12:31:06Z)
• From Geometry to Topology: Inverse Theorems for Distributed Persistence [0.0]
  We show that the correct invariant is not the persistence diagram of X, but rather the collection of persistence diagrams of many small subsets. This invariant, which we call "distributed persistence," is trivially parallelizable, more stable to outliers. Results are complemented by two synthetic experiments demonstrating the use of distributed persistence in practice.
  arXiv  Detail & Related papers  (2021-01-28T21:36:45Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  We study the complexity of PAC learning halfspaces in the presence of Massart (bounded) noise. We show that there an exponential gap between the information-theoretically optimal error and the best error that can be achieved by a SQ algorithm.
  arXiv  Detail & Related papers  (2020-12-17T16:43:11Z)
• Sample-efficient proper PAC learning with approximate differential privacy [51.09425023771246]
  We prove that the sample complexity of properly learning a class of Littlestone dimension $d$ with approximate differential privacy is $tilde O(d6)$, ignoring privacy and accuracy parameters. This result answers a question of Bun et al. (FOCS 2020) by improving upon their upper bound of $2O(d)$ on the sample complexity.
  arXiv  Detail & Related papers  (2020-12-07T18:17:46Z)
• Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
  We show that the average-case teaching complexity is $Theta(d)$, which is in sharp contrast to the worst-case teaching complexity of $Theta(n)$. Our insights allow us to establish a tight bound on the average-case complexity for $phi$-separable dichotomies.
  arXiv  Detail & Related papers  (2020-06-25T19:59:24Z)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  We present a differentially private learner for halfspaces over a finite grid $G$ in $mathbbRd$ with sample complexity $approx d2.5cdot 2log*|G|$. The building block for our learner is a new differentially private algorithm for approximately solving the linear feasibility problem.
  arXiv  Detail & Related papers  (2020-04-16T16:12:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.