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,341 papers · 148 categories

Trend · papers per month

count % of corpus

5 results for “Sherali-Adams”

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adamscs.DS

New algorithm for MDS with quasi-polynomial dependency on aspect ratio.

problem Finding an embedding that minimizes a specific objective function for given dissimilarities.

method A novel geometry-aware analysis of a conditional rounding of the Sherali-Adams LP hierarchy.

result Achieved a solution with cost \(O(\log Δ) \cdot extrm{OPT}^{Ω(1)} + ε\) in quasi-polynomial time.

Metric Embeddings Multi-dimensional Scaling Sherali-Adams LP Approximation Algorithms Quasi-Polynomial Time

2023-11-29abs ↗pdf ↗

Inference in Graphical Models via Semidefinite Programming Hierarchiesstat.ML

Improved SDP relaxations for MAP inference in graphical models.

problem Efficient inference in graphical models with combinatorial optimization.

method Binary SDP relaxations using the SOS hierarchy with Burer-Monteiro method and sequential rounding.

result Demonstrated scalability to tens of thousands of variables with minutes of computation.

graphical models MAP inference semidefinite programming Sherali-Adams hierarchy Sum-of-Squares hierarchy

2017-09-19abs ↗pdf ↗

How to calculate partition functions using convex programming hierarchies: provable bounds for variational methodscs.LG

New methods approximate partition functions for Ising models using convex programming hierarchies.

problem Approximating partition functions for Ising models.

method Combining Sherali-Adams and Lasserre convex programming hierarchies with variational methods.

result New, non-trivial approximation guarantees for partition functions, beyond correlation decay.

partition functions Ising models convex programming variational methods Sherali-Adams

2016-07-11abs ↗pdf ↗

Convergence Rates of Smooth Message Passing with Rounding in Entropy-Regularized MAP Inferencecs.LG

The paper analyzes the convergence rates of smooth message passing algorithms in entropy-regularized MAP inference.

problem Finding the most likely configuration in graphical models with combinatorial optimization.

method Entropy-regularized linear programming relaxations and smooth message passing algorithms.

result The number of iterations sufficient to recover the true integral MAP solution is determined.

MAP inference graphical models smooth message passing entropy regularization convergence rates

2019-07-02abs ↗pdf ↗

Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspectivecs.LG

Unified analysis of mean-field and convex hierarchies for estimating Ising model free energy.

problem Estimating the free energy of Ising models in various regimes.

method Unified analysis using mean-field approximation and convex hierarchies, proving tight bounds and optimality.

result Unified tight bounds for both mean-field and convex hierarchies, showing they are within

O((n\|J\|_{F})^{2/3})

of the free energy.

Ising model free energy mean-field approximation convex hierarchies optimality

2018-08-22abs ↗pdf ↗