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…
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-search methods”
Unified framework for combinatorial and rounding algorithms in experimental design.
problem Designing and analyzing combinatorial and rounding algorithms for experimental design problems.
method Local search framework for combinatorial algorithms and regret minimization framework for rounding algorithms.
result Unified approach to match and improve all known results in D/A/E-design and obtain new results in unknown settings.
New local-search methods close the gap in sparse tensor PCA.
problem Sparse tensor PCA underperforms compared to other methods.
method Proposes new local-search methods including greedy and random-threshold variants.
result Proves local-search methods close the gap to best known polynomial-time procedures.
Local search improves GFlowNets' ability to generate high-reward samples.
problem GFlowNets struggle with over-exploration in high-reward space.
method Local search focusing on high-reward samples via backtracking and reconstruction.
result Significant performance improvement in biochemical tasks.
Paper addresses linear regression with partially mismatched data using local search with theoretical guarantees.
problem Linear regression with partially mismatched data.
method Optimization formulation and greedy local search algorithm with theoretical guarantees.
result Local search algorithm converges to nearly-optimal solution at a linear rate under certain conditions.
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 characterizes optimization landscape of Tucker decomposition.
problem Finding exact Tucker decomposition is a nonconvex optimization problem.
method Characterized the optimization landscape and provided a local search algorithm.
result All local minima are globally optimal if tensor has an exact Tucker decomposition.
Graph Neural Networks and Guided Local Search improve TSP solutions.
problem Finding optimal solutions to the Traveling Salesperson Problem quickly.
method Hybrid approach combining Graph Neural Networks and Guided Local Search.
result Significant reduction in optimality gap for TSP solutions.
Combines global and local search for efficient global optimization with Gaussian processes.
problem Difficulties in building accurate GP models and getting stuck in suboptimal regions.
method Adopting AGLGP model combining global and local GP models, dividing space into regions, and switching between global and local searches.
result Efficiently locates the global optimum with benefits of both global and local search.
New computational methods improve clustering of objects.
problem Clustering objects based on their joint occurrence in sets.
method Genetic algorithm with renumbering, local search, and simplified model.
result Improvements enhance computational performance of genetic algorithm.
New method speeds up k-means clustering for large k by improving nearest-neighbor search.
problem Efficiently clustering large datasets with high-dimensional points.
method Seeded Approximate Nearest-Neighbor Search methods to improve Lloyd's algorithm.
result Significantly faster k-means clustering for large k values.
Quantum algorithm improves portfolio construction accuracy.
problem Efficiently constructing portfolios with real-world constraints.
method Sampling-based CVaR Variational Quantum Algorithm (VQA) combined with local-search post-processing.
result Achieved a relative solution error of 0.49% on IBM Heron processors.
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…
Statistical mechanical analysis of sparse linear regression as a variable selection problemcond-mat.dis-nn
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…
The paper refines NOTEARS for learning Bayesian networks, improving accuracy and efficiency.
problem Learning Bayesian networks from continuous optimization.
method Generalized algebraic characterizations and Karush-Kuhn-Tucker (KKT) conditions for optimization.
result Local search post-processing improves structural Hamming distance by a factor of 2 or more.
Study fairness in ordinal regression using threshold models.
problem Fairness in ordinal regression predictions.
method Adapted fairness notions from fair ranking; use threshold model with scoring function and thresholds; apply binary classification for scoring function and local search for thresholds.
result Generalization guarantees on predictor error and fairness violation; effectiveness demonstrated in experiments.
Improved causal discovery methods for large graphs without strict assumptions.
problem Sub-optimal solutions due to faithfulness assumption violations.
method Super-structure estimation and local search strategies.
result The proposed method scales to hundreds of nodes with high accuracy.
New method selects sparse predictors in large LMMs.
problem Sparse learning for LMMs is computationally infeasible for large datasets.
method Developed an regularized method with coordinate descent and local search algorithms.
result Method selects thousands of predictors in seconds to minutes.
MBExplainer provides explanations for models combining graph embeddings and tabular features.
problem Explaining models using a mix of graph embeddings and tabular features.
method Model-agnostic approach using Shapley values and Monte Carlo Tree Search.
result MBExplainer efficiently finds human-readable explanations for model predictions.
New framework learns interpretable rule ensembles without sacrificing accuracy.
problem Trade-off between accuracy and interpretability in rule ensembles.
method Introduces local interpretability and a regularizer to promote it, using coordinate descent with local search.
result Learns rule ensembles with fewer rules to explain individual predictions, maintaining comparable accuracy.
-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacycs.DS
New method for better initial centers in clustering with improved accuracy and privacy.
problem Improving the quality of clustering centers in metric spaces.
method HST initialization based on metric embedding tree structure, combined with efficient search algorithm and DP extension.
result HST initialization produces better initial centers than -median++ with comparable efficiency and improved privacy.
The paper proposes modern computational methods for optimizing reinsurance contracts.
problem Optimizing catastrophe excess-of-loss reinsurance contracts with realistic constraints and risk measures.
method Two approaches: simulated annealing for local search and quantum branch & bound for future potential.
result Quantum branch & bound approach shows potential for future optimization with quantum computers.
Novel method for high-dimensional BO using CMA to define local regions.
problem Challenges in applying BO to high-dimensional optimization problems.
method CMA strategy to learn search distribution and define local regions.
result Our method outperforms existing techniques on various benchmarks.
The paper solves a maximum entropy sampling problem with efficient algorithms and performance guarantees.
problem Selecting the most informative principal submatrix from a covariance matrix.
method Derive a novel convex integer program, develop efficient sampling algorithms with approximation bounds, and analyze local search algorithms.
result Efficient algorithms with near-optimal performance guarantees for solving MESP and A-MESP.
The paper analyzes conditions for solving low-rank matrix recovery problems with noisy measurements.
problem Low-rank matrix recovery with corrupted measurements.
method Analysis of the restricted isometry property (RIP) and local search methods.
result Sharp bounds on the maximum distance between local minimizers and the ground truth.
Optimal Survival Trees improve accuracy in medical data analysis.
problem Analyzing censored outcomes in medical data.
method Mixed-integer optimization and local search techniques.
result Improves accuracy in large datasets compared to existing methods.
Paper tackles causal effect estimation in observational data with hidden variables.
problem Estimating causal effects in observational data with hidden confounders.
method Developed a theorem for local search to find superset of adjustment variables, proposing a data-driven algorithm.
result Proposed algorithm produces more accurate causal effect estimates than existing methods.
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…
Gradients help find global optima in complex functions.
problem Finding global optima in functions with many local minima.
method A principle for generating search directions from non-local quadratic approximants based on gradients.
result The proposed algorithm and CMA-ES perform better than random reinitialized BFGS.
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…
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…
The paper introduces a method for fitting complex models using simulation and optimization.
problem Fitting models with intractable likelihood or moments.
method Sequential sampling and local smoothing, combining global and local search phases.
result The proposed method outperforms alternative approaches in fitting complex models.
In this paper, we consider the problem of unsupervised video object segmentation via background subtraction. Specifically, we pose the nonsemantic extraction of a video's moving objects as a nonconvex optimization problem via a sum of sparse and low-rank matrices. The resulting formulation, a nonnegative variant of rob…
Hill-climbing is a powerful baseline for NAS, even with reduced noise.
problem Noise in evaluating neural architectures.
method Hill-climbing algorithm, denoising training pipeline.
result Hill-climbing outperforms state-of-the-art NAS algorithms with reduced noise.
Algorithm provides fair clustering guarantees for k-means and k-median.
problem Ensuring fair clustering guarantees for every point in a dataset.
method Local search algorithm for -median and -means, with individual fairness as a key metric.
result Achieves fair clustering with a constant factor approximation of the optimal solution.
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…
Unified algorithm for any -norm experimental design problems.
problem Experimental design problems for various -norm objectives.
method Randomized local search approach for all .
result First approximation algorithm for general -norm objective.
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…
Mixture models are a fundamental tool in applied statistics and machine learning for treating data taken from multiple subpopulations. The current practice for estimating the parameters of such models relies on local search heuristics (e.g., the EM algorithm) which are prone to failure, and existing consistent methods …
Improved diffusion models for sampling from given distributions.
problem Training diffusion models to sample from a given distribution.
method Benchmarked and improved off-policy methods for diffusion sampling.
result A novel exploration strategy improves sample quality.
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…
A new model tracks indices without rebalancing, solving NP-hard problems.
problem Tracking indices without rebalancing and minimizing deviations.
method Metaheuristic algorithms and local branching for solving mixed integer linear programming.
result The heuristic generates portfolios that outperform commercial solvers in both in-sample and out-of-sample data.
Proposes a method to generate high-quality candlestick data for financial trading.
problem Lack of labeled financial trading data.
method Modified Local Search Attack Sampling method for candlestick data augmentation.
result Generated high-quality data that are hard to distinguish by humans.
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 the optimization of active extension portfolios. For this purpose, the optimization problem is rewritten as a stochastic programming model and solved using a clever multi-start local search heuristic, which turns out to provide stable solutions. The heuristic solutions are compared to optimization results o…
Inverse design of multilayer nanoparticles using artificial neural networks and genetic algorithmeess.SP
New method designs multilayer nanoparticles using AI.
problem Difficult to design multilayer nanoparticles by trial and error.
method Combines genetic algorithm and neural network for inverse design.
result Successfully designs multilayer nanoparticles efficiently.
An Efficient Calibration Framework for Volatility Derivatives under Rough Volatility with Jumpsq-fin.CP
A fast calibration method for rough volatility models with jumps.
problem Calibrating stochastic volatility models to market data efficiently.
method Structure-preserving approach: split pricing formula, precompute data-independent integrals, and approximate market-dependent remainder with neural networks.
result Calibration achieves high accuracy and speed, and a pure-jump rough volatility model adequately captures VIX dynamics.
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…