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.
We propose an SDP relaxation for the Gromov-Wasserstein distance, providing globally optimal solutions.
A number of recent work studied the effectiveness of feature selection using Lasso. It is known that under the restricted isometry properties (RIP), Lasso does not generally lead to the exact recovery of the set of nonzero coefficients, due to the looseness of convex relaxation. This paper considers the feature selecti…
New regularizers tighten convex relaxation bounds for neural networks.
Improved Compressed Sensing by optimizing sparse solutions with mixed integer programming.
Paper relaxes convexity assumptions in mean curvature flow results.
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…
MAP inference for general energy functions remains a challenging problem. While most efforts are channeled towards improving the linear programming (LP) based relaxation, this work is motivated by the quadratic programming (QP) relaxation. We propose a novel MAP relaxation that penalizes the Kullback-Leibler divergence…
In this paper, we study a nonconvex continuous relaxation of MAP inference in discrete Markov random fields (MRFs). We show that for arbitrary MRFs, this relaxation is tight, and a discrete stationary point of it can be easily reached by a simple block coordinate descent algorithm. In addition, we study the resolution …
Paper finds maximum curvature of Bézier-spline curves.
Verification of neural networks enables us to gauge their robustness against adversarial attacks. Verification algorithms fall into two categories: exact verifiers that run in exponential time and relaxed verifiers that are efficient but incomplete. In this paper, we unify all existing LP-relaxed verifiers, to the best…
Paper analyzes Birkhoff relaxation for graph alignment, providing theoretical guarantees.
CPRA efficiently finds diverse solutions in CO problems using UL and parallelization.
Value iteration is a fixed point iteration technique utilized to obtain the optimal value function and policy in a discounted reward Markov Decision Process (MDP). Here, a contraction operator is constructed and applied repeatedly to arrive at the optimal solution. Value iteration is a first order method and therefore …
We consider the densest -subgraph problem, which seeks to identify the -node subgraph of a given input graph with maximum number of edges. This problem is well-known to be NP-hard, by reduction to the maximum clique problem. We propose a new convex relaxation for the densest -subgraph problem, based on a nucle…
Paper presents a randomized algorithm for SPCA with high probability approximation.
Renet improves Elastic Net by dynamically selecting between convex blending and refitting, enhancing prediction accuracy.
Approximate algorithms for structured prediction problems---such as LP relaxations and the popular alpha-expansion algorithm (Boykov et al. 2001)---typically far exceed their theoretical performance guarantees on real-world instances. These algorithms often find solutions that are very close to optimal. The goal of thi…
New method relaxes optimization problems to find solutions more reliably.
New method for sparse kernel selection improves prediction accuracy.
Plain vanilla K-means clustering has proven to be successful in practice, yet it suffers from outlier sensitivity and may produce highly unbalanced clusters. To mitigate both shortcomings, we formulate a joint outlier detection and clustering problem, which assigns a prescribed number of datapoints to an auxiliary outl…
New algorithm solves large cardinality-constrained clustering problems.
The stochastic block model (SBM) is a popular tool for community detection in networks, but fitting it by maximum likelihood (MLE) involves a computationally infeasible optimization problem. We propose a new semidefinite programming (SDP) solution to the problem of fitting the SBM, derived as a relaxation of the MLE. W…
The (constrained) minimization of a ratio of set functions is a problem frequently occurring in clustering and community detection. As these optimization problems are typically NP-hard, one uses convex or spectral relaxations in practice. While these relaxations can be solved globally optimally, they are often too loos…
CRA improves UL-based CO solvers by dynamically smoothing and enforcing discreteness.
Finding efficient and provable methods to solve non-convex optimization problems is an outstanding challenge in machine learning and optimization theory. A popular approach used to tackle non-convex problems is to use convex relaxation techniques to find a convex surrogate for the problem. Unfortunately, convex relaxat…
Recent results in Compressive Sensing have shown that, under certain conditions, the solution to an underdetermined system of linear equations with sparsity-based regularization can be accurately recovered by solving convex relaxations of the original problem. In this work, we present a novel primal-dual analysis on a …
Regularized regression problems are ubiquitous in statistical modeling, signal processing, and machine learning. Sparse regression in particular has been instrumental in scientific model discovery, including compressed sensing applications, variable selection, and high-dimensional analysis. We propose a broad framework…
Given a graphical model, one essential problem is MAP inference, that is, finding the most likely configuration of states according to the model. Although this problem is NP-hard, large instances can be solved in practice. A major open question is to explain why this is true. We give a natural condition under which we …
In this paper we propose an algorithm for exact partitioning of high-order models. We define a general class of -degree Homogeneous Polynomial Models, which subsumes several examples motivated from prior literature. Exact partitioning can be formulated as a tensor optimization problem. We relax this high-order combi…
Paper solves graph matching problem using convex relaxation to the simplex.
Graph alignment problem solved with convex relaxations for correlated matrices.
We consider the problem of estimating the discrete clustering structures under the Sub-Gaussian Mixture Model. Our main results establish a hidden integrality property of a semidefinite programming (SDP) relaxation for this problem: while the optimal solution to the SDP is not integer-valued in general, its estimation …
New method decomposes corrupted data matrices into sparse and low-rank components.
We study the problem of controlling linear time-invariant systems with known noisy dynamics and adversarially chosen quadratic losses. We present the first efficient online learning algorithms in this setting that guarantee regret under mild assumptions, where is the time horizon. Our algorithms rely …
We introduce Taylor expansions that do not require the differentiability. We also provide new solutions to partial differential equations. We apply our methods to finance.
Signal estimation problems with smoothness and sparsity priors can be naturally modeled as quadratic optimization with -"norm" constraints. Since such problems are non-convex and hard-to-solve, the standard approach is, instead, to tackle their convex surrogates based on -norm relaxations. In this paper…
Safe screening rules reduce computation time in logistic regression with regularization.
An explicit representation formula for all positive ancient solutions of the heat equation in the Euclidean case is found. In the Riemannian case with nonnegative Ricci curvature, a similar but less explicit formula is also found. Here it is proven that any positive ancient solution is the standard Laplace transform of…
In this paper, we consider the classical variational problem in the Galilean space. we develop the Euler-Lagrange equations for a elastic line on an oriented surface in the Galilean 3-dimensional space . Using the varia- tion method, we will try to give some characterization for the solution curve (the elastic lin…
New LP method recovers MAP solution from noisy stable instances.
The framework of Integral Quadratic Constraints (IQC) reduces the computation of upper bounds on the convergence rate of several optimization algorithms to a semi-definite program (SDP). In the case of over-relaxed Alternating Direction Method of Multipliers (ADMM), an explicit and closed form solution to this SDP was …
PEREGRiNN verifies safety of ReLU NNs by penalizing relaxation in a greedy manner.
The paper analyzes the generalization performance of spectral clustering algorithms and proposes new methods to improve their effectiveness.
Sparse principal component analysis (PCA) involves nonconvex optimization for which the global solution is hard to obtain. To address this issue, one popular approach is convex relaxation. However, such an approach may produce suboptimal estimators due to the relaxation effect. To optimally estimate sparse principal su…
We introduce a model-free relax-and-round algorithm for k-means clustering based on a semidefinite relaxation due to Peng and Wei. The algorithm interprets the SDP output as a denoised version of the original data and then rounds this output to a hard clustering. We provide a generic method for proving performance guar…
Maximum a posteriori (MAP) inference is a fundamental computational paradigm for statistical inference. In the setting of graphical models, MAP inference entails solving a combinatorial optimization problem to find the most likely configuration of the discrete-valued model. Linear programming (LP) relaxations in the Sh…
Sparse regression models are increasingly prevalent due to their ease of interpretability and superior out-of-sample performance. However, the exact model of sparse regression with an constraint restricting the support of the estimators is a challenging (\NP-hard) non-convex optimization problem. In this paper…
In many applications we seek to maximize an expectation with respect to a distribution over discrete variables. Estimating gradients of such objectives with respect to the distribution parameters is a challenging problem. We analyze existing solutions including finite-difference (FD) estimators and continuous relaxatio…