How to Learn a Star: Binary Classification with Starshaped Polyhedral Sets

• URL: http://arxiv.org/abs/2505.01346v1
• Date: Fri, 02 May 2025 15:33:31 GMT
• Title: How to Learn a Star: Binary Classification with Starshaped Polyhedral Sets
• Authors: Marie-Charlotte Brandenburg, Katharina Jochemko,
• Abstract summary: We consider binary classification restricted to a class of continuous piecewise functions whose decision boundaries are (possibly non) star polyhedral sets.<n>We investigate the geometric structure of the loss-functions most prominently the sublevel sets for two loss-functions: 0/1-loss (discrete loss) and an exponential loss function.
• Score: 1.360022695699485
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider binary classification restricted to a class of continuous piecewise linear functions whose decision boundaries are (possibly nonconvex) starshaped polyhedral sets, supported on a fixed polyhedral simplicial fan. We investigate the expressivity of these function classes and describe the combinatorial and geometric structure of the loss landscape, most prominently the sublevel sets, for two loss-functions: the 0/1-loss (discrete loss) and an exponential loss function. In particular, we give explicit bounds on the VC dimension of this model, and concretely describe the sublevel sets of the discrete loss as chambers in a hyperplane arrangement. For the exponential loss, we give sufficient conditions for the optimum to be unique, and describe the geometry of the optimum when varying the rate parameter of the underlying exponential probability distribution.

Related papers

• Classification by Separating Hypersurfaces: An Entropic Approach [0.0]
  We consider the classification problem of individuals characterized by a set of attributes represented as a vector in $mathbb RN$.<n>The goal is to find a hyperplane in $mathbb RN$ that separates two sets of points corresponding to two distinct classes.<n>We propose a novel approach by searching for a vector of parameters in a bounded $N-dimensional hypercube.
  arXiv  Detail & Related papers  (2025-07-03T15:43:54Z)
• Decomposition Polyhedra of Piecewise Linear Functions [4.594829845106234]
  We contribute to the frequently studied question of how to decompose a continuous piecewise linear (CPWL) function into a convex CPWL function. Every CPWL function has infinitely decompositions, but a difference two convex CPWL functions. We apply our framework to find decompositions with as few linear pieces as possible.
  arXiv  Detail & Related papers  (2024-10-07T10:48:36Z)
• General Loss Functions Lead to (Approximate) Interpolation in High Dimensions [6.738946307589741]
  We provide a unified framework to approximately characterize the implicit bias of gradient descent in closed form. Specifically, we show that the implicit bias is approximated (but not exactly equal to) the minimum-norm in high dimensions. Our framework also recovers existing exact equivalence results for exponentially-tailed losses across binary and multiclass settings.
  arXiv  Detail & Related papers  (2023-03-13T21:23:12Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  We propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. Comprehensive experimental results on six commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-21T01:47:17Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  We study reinforcement learning for partially observed decision processes (POMDPs) with infinite observation and state spaces. We make the first attempt at partial observability and function approximation for a class of POMDPs with a linear structure.
  arXiv  Detail & Related papers  (2022-04-20T21:15:38Z)
• On the convex hull of convex quadratic optimization problems with indicators [2.867517731896504]
  We show that a convex hull description of the associated mixed-integer set in an extended space with a quadratic number of additional variables consists of a single positive semidefinite constraint and linear constraints. The new theory presented here paves the way toward utilizing polyhedral methods to analyze the convex hull of mixed-integer nonlinear sets.
  arXiv  Detail & Related papers  (2022-01-02T18:04:52Z)
• Universal Online Convex Optimization Meets Second-order Bounds [74.0120666722487]
  We propose a simple strategy for universal online convex optimization. The key idea is to construct a set of experts to process the original online functions, and deploy a meta-algorithm over the linearized losses. In this way, we can plug in off-the-shelf online solvers as black-box experts to deliver problem-dependent regret bounds.
  arXiv  Detail & Related papers  (2021-05-08T11:43:49Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)
• Stochastic spectral embedding [0.0]
  We propose a novel sequential adaptive surrogate modeling method based on "stochastic spectral embedding" (SSE) We show how the method compares favorably against state-of-the-art sparse chaos expansions on a set of models with different complexity and input dimension.
  arXiv  Detail & Related papers  (2020-04-09T11:00:07Z)
• Reduced Dilation-Erosion Perceptron for Binary Classification [1.3706331473063877]
  Dilation-erosion perceptron (DEP) is a neural network obtained by a convex combination of a dilation and an erosion. This paper introduces the reduced dilation-erosion (r-DEP) classifier.
  arXiv  Detail & Related papers  (2020-03-04T19:50:35Z)
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees [106.91654068632882]
  We consider the bipartite graph and formalize its representation learning problem as a statistical estimation problem of parameters in a semiparametric exponential family distribution. We show that the proposed objective is strongly convex in a neighborhood around the ground truth, so that a gradient descent-based method achieves linear convergence rate. Our estimator is robust to any model misspecification within the exponential family, which is validated in extensive experiments.
  arXiv  Detail & Related papers  (2020-03-02T16:40:36Z)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  We develop a convex analytic approach to analyze finite width two-layer ReLU networks. We show that an optimal solution to the regularized training problem can be characterized as extreme points of a convex set. In higher dimensions, we show that the training problem can be cast as a finite dimensional convex problem with infinitely many constraints.
  arXiv  Detail & Related papers  (2020-02-25T23:05:33Z)

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.