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.
169,291 papers · 148 categories
Trend · papers per month
48 results for “Polytope relaxation”
Novel approach tightens MAP inference for complex Markov fields.
problem Intractable message passing in MAP inference for large state spaces.
method Benders decomposition applied to local polytope relaxation.
result Upper envelope of messages tightens true message at minimizers.
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.
Paper shows non-integrality of dike building model and provides conditions for integrality.
problem Determining the integrality of a dike building model for flood protection.
method Analyzes experimental data and mathematical proofs to establish conditions for integrality.
result Established non-integrality of the polytope and conditions for linear programming relaxation to be integral.
We introduce a new method to handle permutations efficiently using variational inference.
problem Efficient probabilistic reasoning about permutations in high-dimensional spaces.
method We reparameterize the Birkhoff polytope to enable variational inference over permutations.
result Our method enables efficient and accurate Bayesian inference over permutations.
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…
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…
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…
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.
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.
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…
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.
Two operations transform simple polytopes with same manifold structure.
problem Transforming simple polytopes while maintaining a specific manifold structure.
method Biflip and puzzle-move operations on simple polytopes.
result Produced polytopes have diffeomorphic moment-angle manifolds.
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.
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…
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.
New infinite series of hyperbolic polytopes with special growth rates found.
problem Finding new infinite series of non-compact hyperbolic polytopes.
method Constructing infinite series of non-simple ideal hyperbolic Coxeter 4-polytopes.
result Growth rates of the constructed polytopes are Perron numbers.
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…
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.
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.
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.
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.
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.
New cohomological rigidity results for manifolds defined by right-angled polytopes.
problem Establishing cohomological rigidity for manifolds defined by specific polytopes.
method Using techniques from toric topology, the authors prove cohomological rigidity for families of manifolds associated with polytopes from a specific class.
result Cohomology ring isomorphisms imply diffeomorphisms for manifolds in the families, and vice versa.
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 mathematical invariants derived from polytopes of matrices over rings.
problem Understanding Bieri-Neumann-Strebel invariants via algebraic structures.
method Investigating Newton polytopes of determinants of matrices over rings of twisted Laurent polynomials.
result Established a connection between Bieri-Neumann-Strebel invariants and Newton polytopes.
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.
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.
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.
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.
Diffeomorphisms of convex polytopes form a Lie group.
problem Understanding transformations of convex polytopes.
method Forming a Lie group from diffeomorphisms of convex polytopes.
result The group of diffeomorphisms of a convex polytope is a regular Lie group.
Efficiently projects points onto polytopes, especially useful in web-scale applications.
problem Efficiently projecting points onto polytopes in large-scale applications.
method Developed a vertex-oriented incremental algorithm for polytope projection, tailored for simplex and unit-box cut polytopes.
result Majority of projections lie on vertices of polytopes, leading to significant performance improvements.
Geometric constraints help classify hyperbolic polytopes.
problem Classifying reflective anisotropic Lorentzian lattices and cocompact arithmetic hyperbolic reflection groups.
method Established geometric constraints on compact Coxeter polytopes in hyperbolic spaces.
result Geometric constraints are useful for classifying hyperbolic polytopes.
New noncompact Coxeter polytopes found in various dimensions.
problem Classifying and constructing noncompact hyperbolic Coxeter polytopes.
method Maximal-cusp density and noncompact analog of Bogachev-Douba-Raimbault's argument.
result Infinitely many pairwise incommensurable noncompact Coxeter polytopes in dimensions 4-9.
Proves weight polytope matches with energy vectors in toric varieties.
problem Understanding the relationship between weight polytopes and energy functionals in toric varieties.
method Combines two slope formulas of K-energy in the toric setting.
result Weight polytope of Hurwitz form matches with convex hull of characteristic vectors.
Unique floating and buoyancy surfaces identify convex polytopes.
problem Identifying convex polytopes from their flotation and buoyancy surfaces.
method Proving uniqueness of surfaces for polytopes with uniform or prescribed density.
result Floating and buoyancy surfaces uniquely determine convex polytopes.
Survey on constructing manifolds over simple polytopes using Lickorish's method.
problem Classifying manifolds over simple convex polytopes with torus action.
method Lickorish type construction over simple polytopes with torus action.
result Many classical classification results can be interpreted using this construction.
The paper classifies compact hyperbolic Coxeter polytopes and improves upper bounds.
problem Classifying compact hyperbolic Coxeter polytopes and understanding their combinatorial properties.
method Study of -products of Lannér diagrams, proving superhyperbolic properties, and analyzing Lannér subdiagrams.
result Improved upper bounds on the dimension of compact hyperbolic Coxeter polytopes.
The study proves curvature rigidity for convex polytopes.
problem Proving curvature rigidity for convex polytopes.
method Using Fredholm theory for Dirac operators and a theorem of Fefferman and Phong.
result Scalar curvature rigidity theorem for convex polytopes proved.
Classification of polytope metrics and complete scalar-flat Kähler 4-Manifolds with two symmetriesmath.DG
We study unbounded 2-dimensional metric polytopes such as those arising as Kähler quotients of complete Kähler 4-manifolds with two commuting symmetries and zero scalar curvature. Under a mild closedness condition, we obtain a complete classification of metrics on such polytopes, and as a result classify all possible m…