We introduce a globally-convergent algorithm for optimizing the tree-reweighted (TRW) variational objective over the marginal polytope. The algorithm is based on the conditional gradient method (Frank-Wolfe) and moves pseudomarginals within the marginal polytope through repeated maximum a posteriori (MAP) calls. This m…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “local polytope relaxation”
LP-SparseMAP relaxes SparseMAP for more complex structures.
problem SparseMAP's tractable MAP inference oracle limits its applicability.
method Local polytope relaxation for factor graphs.
result LP-SparseMAP outperforms SparseMAP and Structured SVM in structured prediction tasks.
We introduce a novel mechanism to tighten the local polytope relaxation for MAP inference in Markov random fields with low state space variables. We consider a surjection of the variables to a set of hyper-variables and apply the local polytope relaxation over these hyper-variables. The state space of each individual h…
We consider clustering problems where the goal is to determine an optimal partition of a given point set in Euclidean space in terms of a collection of affine subspaces. While there is vast literature on heuristics for this kind of problem, such approaches are known to be susceptible to poor initializations and getting…
This article announces the completion of the classification of rank 4 locally projective polytopes and their quotients. There are seventeen universal locally projective polytopes (nine nondegenerate). Amongst their 441 quotients are a further four (nonuniversal) regular polytopes, and 152 nonregular but section regular…
We consider the problem of learning the structure of undirected graphical models with bounded treewidth, within the maximum likelihood framework. This is an NP-hard problem and most approaches consider local search techniques. In this paper, we pose it as a combinatorial optimization problem, which is then relaxed to a…
Locally rigid groups from 5-polytopes with Fuchsian ends.
problem Constructing locally rigid right-angled Coxeter groups with Fuchsian ends.
method Constructing a right-angled 5-polytope P and analyzing its right-angled Coxeter groups.
result Locally rigid right-angled Coxeter groups with Fuchsian ends can be constructed.
Many matching, tracking, sorting, and ranking problems require probabilistic reasoning about possible permutations, a set that grows factorially with dimension. Combinatorial optimization algorithms may enable efficient point estimation, but fully Bayesian inference poses a severe challenge in this high-dimensional, di…
We consider a fundamental integer programming (IP) model for cost-benefit analysis flood protection through dike building in the Netherlands, due to Verweij and Zwaneveld. Experimental analysis with data for the Ijsselmeer lead to integral optimal solution of the linear programming relaxation of the IP model. This natu…
RbX generates local explanations for black-box models using greedy polytope construction.
problem Generating interpretable local explanations for complex models.
method Greedy algorithm for building a convex polytope to approximate feature regions.
result RbX can more accurately identify important features compared to existing methods.
Traversing the Local Polytopes of ReLU Neural Networks: A Unified Approach for Network Verificationcs.LG
Unified approach to verify NN properties using ReLU's unique polytope structure.
problem Lack of robustness and interpretability in ReLU NNs for risk-sensitive applications.
method Identifying and traversing the local polytopes of ReLU NNs, developing an algorithm to verify properties.
result Unified approach to examine network behavior in risk-sensitive settings.
Novel singularity models for 4D harmonic forms and spinors from polytopes.
problem Understanding harmonic forms and spinors in 4D.
method Homogeneous singularity models based on regular 4-polytopes.
result Models describe cones on the 1-skeletal of polytopes.
We introduce a numerical isomorphism invariant p(T) for any triangulation T of S^3. Although its definition is purely topological (inspired by the bridge number of knots), p(T) reflects the geometric properties of T. Specifically, if T is polytopal or shellable then p(T) is `small' in the sense that we obtain a linear …
Regularization vs. Relaxation: A conic optimization perspective of statistical variable selectioncs.LG
Variable selection is a fundamental task in statistical data analysis. Sparsity-inducing regularization methods are a popular class of methods that simultaneously perform variable selection and model estimation. The central problem is a quadratic optimization problem with an l0-norm penalty. Exactly enforcing the l0-no…
Constructs combinatorial 2D topological field theories from cyclic A-infinity algebras.
problem Developing a combinatorial framework for 2D topological field theories.
method Using triangulations and polygonal decompositions, constructing cochains on a CW complex.
result Existence of combinatorial 2D topological field theories based on cyclic A-infinity algebras.
PEREGRiNN verifies safety of ReLU NNs by penalizing relaxation in a greedy manner.
problem Formal verification of safety specifications for ReLU NNs.
method Uses a relaxed convex program to verify polytopic input/output constraints, penalizing relaxation and forcing largest relaxations to early layers.
result Significantly faster and more properties verified compared to other approaches.
New algorithms learn graph structures privately, matching best results.
problem Private learning of graph structures with multiple blocks.
method Sum-of-squares relaxation and exponential mechanism for score function.
result Matches statistical utility of previous best non-private methods.
We call complex quasifold of dimension k a space that is locally isomorphic to the quotient of an open subset of the space C^k by the holomorphic action of a discrete group; the analogue of a complex torus in this setting is called a complex quasitorus. We associate to each simple polytope, rational or not, a family of…
A new method learns DAGs from Gaussian data without verifying acyclicity.
problem Learning DAGs from Gaussian data without verifying acyclicity.
method Relaxation technique for permutation matrix estimation and cyclic coordinatewise descent for sparse Cholesky factor estimation.
result The method recovers DAGs without verifying acyclicity constraints.
The study broadens the concept of cyclic polytopes to Veronese polytopes.
problem Extending the framework of cyclic polytopes to a broader class of polytopes.
method Described facial structure and combinatorial characterisation of facets via σ-parity alternating sequences.
result Established a bijective correspondence between combinatorial types of Veronese polytopes and partitions of finite sets.
A small cover was introduced by Davis and Januszkiewicz as an -dimensional closed manifold with a locally standard -action such that its orbit space is a simple convex polytope. There exist a one-to-one correspondence between small covers and -colored polytopes. In this paper we study a construction…
New method relaxes spatial invariance in locally connected layers, improving accuracy.
problem Improving classification accuracy with locally connected layers.
method Designing a low-rank locally connected layer with varying spatially varying combining weights.
result Relaxing spatial invariance improves classification accuracy over convolution and locally connected layers.
The paper studies deformation spaces of Coxeter truncation polytopes.
problem Understanding the geometric properties and deformations of Coxeter truncation polytopes.
method Analyzing Coxeter truncation polytopes and their deformation spaces.
result Description of deformation spaces for Coxeter truncation polytopes of dimension .
Neural Polytopescs.LG
Neural networks approximate unit spheres as polytopes.
problem Approximating unit spheres with neural networks.
method Using ReLU activation in neural networks to generate polytopes.
result Neural networks can approximate unit spheres as polytopes.
The study classifies all compact hyperbolic polytopes with eight facets.
problem Classifying compact hyperbolic Coxeter four-polytopes with specific numbers of facets.
method Complete classification through mathematical analysis.
result The complete classification of compact hyperbolic Coxeter four-polytopes with eight facets.
In this article we consider a generalization of manifolds and orbifolds which we call quasifolds; quasifolds of dimension k are locally isomorphic to the quotient of R^k by the action of a discrete group - tipically they are not Hausdorff topological spaces. The analogue of a torus in this geometry is a quasitorus. We …
We present a semi-supervised learning algorithm for learning discrete factor analysis models with arbitrary structure on the latent variables. Our algorithm assumes that every latent variable has an "anchor", an observed variable with only that latent variable as its parent. Given such anchors, we show that it is possi…
Proves stability in Weyl polytopes using optimal transport.
problem Stability of Weyl polytopes under optimal transport.
method Optimal transport stability for reflexive Weyl polytopes.
result Weak metric SYZ conjecture holds for Delzant reflexive Weyl polytopes.
Faces of quasi-arithmetic Coxeter polytopes are also quasi-arithmetic.
problem Characterizing faces of quasi-arithmetic Coxeter polytopes.
method Proof of quasi-arithmetic property of faces and sufficient condition for arithmetic faces.
result Lower-dimensional faces of quasi-arithmetic Coxeter polytopes are quasi-arithmetic.
Given a finite collection P of convex n-polytopes in RP^n (n>1), we consider a real projective manifold M which is obtained by gluing together the polytopes in P along their facets in such a way that the union of any two adjacent polytopes sharing a common facet is convex. We prove that the real projective structure on…
The study classifies all compact 5D polytopes with 9 facets.
problem Classifying compact hyperbolic Coxeter polytopes.
method Complete classification through mathematical analysis.
result A complete list of compact hyperbolic Coxeter 5D polytopes with 9 facets.
We propose a DC proximal Newton algorithm for solving nonconvex regularized sparse learning problems in high dimensions. Our proposed algorithm integrates the proximal Newton algorithm with multi-stage convex relaxation based on the difference of convex (DC) programming, and enjoys both strong computational and statist…
Smooth deformation space of Coxeter polytopes proven for orderable orbifolds.
problem Proving smoothness of deformation space for Coxeter polytopes.
method Analyzing natural map into realization space.
result Deformation space of Coxeter 3-polytopes is smooth.
Given a lattice L of R^n, a polytope D is called a Delaunay polytope in L if the set of its vertices is S\cap L where S is a sphere having no lattice points in its interior. D is called perfect if the only ellipsoid in R^n that contains S\cap L is exactly S. For a vector v of the Leech lattice Λ_{24} we define Λ_{24}(v…
The study classifies 331 specific 4D polytopes with 7 facets.
problem Classifying finite-volume hyperbolic Coxeter 4D polytopes.
method Complete classification through exhaustive search.
result 331 unique polytopes with 7 facets identified.
Contact manifolds' momentum polytopes are convex.
problem Understanding the structure of contact manifolds.
method Using isomorphism to toric varieties.
result Momentum polytopes of contact manifolds are convex.
Smooth approximations bound dihedral angles of convex polytopes.
problem Bounding dihedral angles of convex polytopes.
method Approximating polytopes with smooth hypersurfaces and using geometric relations.
result Established lower bounds on dihedral angles.
Polytopic Matrix Factorization models data as latent vectors from a polytope, maximizing determinant for identifiability.
problem Data decomposition with semi-structured latent vectors and polytope constraints.
method Model input data as latent vectors from a polytope, using determinant maximization for identifiability.
result Identifiability condition for polytopes with specific symmetry restrictions.
The article studies factorization structures in geometry and their applications to cones and polytopes.
problem Understanding and characterizing factorization structures in geometry.
method Comprehensive study of factorization structures, including structure theory, construction of compatible polytopes and cones, and derivation of generalised Gale's evenness condition.
result Established generalised Vandermonde identities and found examples of Delzant and rational Delzant compatible polytopes.
Examines nonrational polytopes and fans in toric geometry.
problem Understanding nonrational convex polytopes and fans in toric geometry.
method Discussion and interrelation of recent developments.
result Exploration of nonrational polytopes and fans in toric geometry.
New methods classify hyperbolic polytopes with up to 40 facets.
problem Classifying compact hyperbolic Coxeter polytopes with specific facet counts.
method New combinatorial method via point set order types.
result Proves existence of a compact hyperbolic Coxeter 29-polytope with at least 40 facets.
We apply a local differential geometric framework from Kähler toric geometry to (re)construct Calabi's extremal Kähler metrics on $\bbC\bbP^n$ blown-up at a point from data on the moment polytope.
The paper explains how to parameterize facets of moment polytopes in real symplectic geometry.
problem Understanding the moment polytopes in real symplectic geometry.
method Parameterizing equations of facets of Delta(Z) in terms of real Ressayre's pairs of Z.
result Parameterization of facets of moment polytopes explained.
We introduce two operations named biflip and puzzle-move on simple polytopes producing polytopes with diffeomorphic moment-angle manifolds.
Proves necessity of at least log2(n) layers to compute maximum of n numbers.
problem Computing the maximum of n numbers with ReLU neural networks.
method Uses lattice polytopes and duality with Newton polytopes to prove depth lower bounds.
result Proves that log2(n) hidden layers are necessary and sufficient.
Unified cosmological and Einstein polytope theories.
problem Unified understanding of cosmological and Einstein polytope theories.
method Unified combinatorial perspective of cosmological and Einstein polytope theories.
result Unified construction of cosmological and Einstein polytope theories.
By studying -combinations of strongly isomorphic polytopes, we prove the equivalence of the -Brunn-Minkowski inequality conjectured by Böröczky, Lutwak, Yang and Zhang to the local version of the inequality studied by Colesanti, Livshyts, and Marsiglietti and by Kolesnikov and Milman, settling a conjecture of…
The study of symmetries in manifolds derived from colored polytopes.
problem Existence and types of symmetries in rational homology 3-spheres.
method Analysis of hyperbolic manifolds and right-angled polytopes.
result Described how to create colorings with specific symmetries.