arXiv research

Unified framework for combinatorial and rounding algorithms in experimental design.

Local search algorithms applied to optimization problems often suffer from getting trapped in a local optimum. The common solution for this deficiency is to restart the algorithm when no progress is observed. Alternatively, one can start multiple instances of a local search algorithm, and allocate computational resourc…

Paper addresses linear regression with partially mismatched data using local search with theoretical guarantees.

Global optimization finds applications in a wide range of real world problems. The multi-start methods are a popular class of global optimization techniques, which are based on the ideas of conducting local searches at multiple starting points. In this work we propose a new multi-start algorithm where the starting poin…

New local-search methods close the gap in sparse tensor PCA.

Paper characterizes optimization landscape of Tucker decomposition.

Quantum algorithm improves portfolio construction accuracy.

Graph Neural Networks and Guided Local Search improve TSP solutions.

Combines global and local search for efficient global optimization with Gaussian processes.

The paper refines NOTEARS for learning Bayesian networks, improving accuracy and efficiency.

New computational methods improve clustering of objects.

Local search improves GFlowNets' ability to generate high-reward samples.

An algorithmic limit of compressed sensing or related variable-selection problems is analytically evaluated when a design matrix is given by an overcomplete random matrix. The replica method from statistical mechanics is employed to derive the result. The analysis is conducted through evaluation of the entropy, an expo…

MBExplainer provides explanations for models combining graph embeddings and tabular features.

New method speeds up k-means clustering for large k by improving nearest-neighbor search.

In this paper, a new sequential surrogate-based optimization (SSBO) algorithm is developed, which aims to improve the global search ability and local search efficiency for the global optimization of expensive black-box models. The proposed method involves three basic sub-criteria to infill new samples asynchronously to…

Unified algorithm for any $p$-norm experimental design problems.

This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix of a prespecified size from a covariance matrix. MESP has been widely applied to many areas, including healthcare, power system, manufacturing and data science. By investigating its Lagran…

New method selects sparse predictors in large LMMs.

Hill-climbing is a powerful baseline for NAS, even with reduced noise.

New method for better initial centers in clustering with improved accuracy and privacy.

In this paper we present an evolutionary optimization approach to solve the risk parity portfolio selection problem. While there exist convex optimization approaches to solve this problem when long-only portfolios are considered, the optimization problem becomes non-trivial in the long-short case. To solve this problem…

Study fairness in ordinal regression using threshold models.

A new model tracks indices without rebalancing, solving NP-hard problems.

New framework learns interpretable rule ensembles without sacrificing accuracy.

Optimal Survival Trees improve accuracy in medical data analysis.

Novel method for high-dimensional BO using CMA to define local regions.

When confronted with massive data streams, summarizing data with dimension reduction methods such as PCA raises theoretical and algorithmic pitfalls. Principal curves act as a nonlinear generalization of PCA and the present paper proposes a novel algorithm to automatically and sequentially learn principal curves from d…

We examine the squared error loss landscape of shallow linear neural networks. We show---with significantly milder assumptions than previous works---that the corresponding optimization problems have benign geometric properties: there are no spurious local minima and the Hessian at every saddle point has at least one ne…

FLOP algorithm speeds up causal structure learning for linear models.

Autodock is a widely used molecular modeling tool which predicts how small molecules bind to a receptor of known 3D structure. The current version of AutoDock uses meta-heuristic algorithms in combination with local search methods for doing the conformation search. Appropriate settings of hyperparameters in these algor…

Non-convex optimization with local search heuristics has been widely used in machine learning, achieving many state-of-art results. It becomes increasingly important to understand why they can work for these NP-hard problems on typical data. The landscape of many objective functions in learning has been conjectured to …

We consider a sparse high dimensional regression model where the goal is to recover a $k$-sparse unknown vector $β^*$ from $n$ noisy linear observations of the form $Y=Xβ^*+W \in \mathbb{R}^n$ where $X \in \mathbb{R}^{n \times p}$ has iid $N(0,1)$ entries and $W \in \mathbb{R}^n$ has iid $N(0,σ^2)$ entries. Under certa…

Reverse annealing boosts quantum matrix factorization performance.

The paper introduces a method for fitting complex models using simulation and optimization.

Gradients help find global optima in complex functions.

Local search heuristics for non-convex optimizations are popular in applied machine learning. However, in general it is hard to guarantee that such algorithms even converge to a local minimum, due to the existence of complicated saddle point structures in high dimensions. Many functions have degenerate saddle points su…

We compute approximate solutions to L0 regularized linear regression using L1 regularization, also known as the Lasso, as an initialization step. Our algorithm, the Lass-0 ("Lass-zero"), uses a computationally efficient stepwise search to determine a locally optimal L0 solution given any L1 regularization solution. We …

New method designs multilayer nanoparticles using AI.

Latent variable models are an elegant framework for capturing rich probabilistic dependencies in many applications. However, current approaches typically parametrize these models using conditional probability tables, and learning relies predominantly on local search heuristics such as Expectation Maximization. Using te…

In this paper is proposed a new heuristic approach belonging to the field of evolutionary Estimation of Distribution Algorithms (EDAs). EDAs builds a probability model and a set of solutions is sampled from the model which characterizes the distribution of such solutions. The main framework of the proposed method is an…

Developing efficient and guaranteed nonconvex algorithms has been an important challenge in modern machine learning. Algorithms with good empirical performance such as stochastic gradient descent often lack theoretical guarantees. In this paper, we analyze the class of homotopy or continuation methods for global optimi…

We show that there are no spurious local minima in the non-convex factorized parametrization of low-rank matrix recovery from incoherent linear measurements. With noisy measurements we show all local minima are very close to a global optimum. Together with a curvature bound at saddle points, this yields a polynomial ti…

Improved causal discovery methods for large graphs without strict assumptions.

Generalized Linear Models (GLMs) and Single Index Models (SIMs) provide powerful generalizations of linear regression, where the target variable is assumed to be a (possibly unknown) 1-dimensional function of a linear predictor. In general, these problems entail non-convex estimation procedures, and, in practice, itera…

DAEGEN generates adversarial inputs for neural networks using a black-box differential technique.

We provide new theoretical insights on why over-parametrization is effective in learning neural networks. For a $k$ hidden node shallow network with quadratic activation and $n$ training data points, we show as long as $k \ge \sqrt{2n}$, over-parametrization enables local search algorithms to find a \emph{globally} op…

This paper investigates the phase retrieval problem, which aims to recover a signal from the magnitudes of its linear measurements. We develop statistically and computationally efficient algorithms for the situation when the measurements are corrupted by sparse outliers that can take arbitrary values. We propose a nove…