Accelerating Matroid Optimization through Fast Imprecise Oracles

• URL: http://arxiv.org/abs/2402.02774v2
• Date: Tue, 05 Nov 2024 16:34:46 GMT
• Title: Accelerating Matroid Optimization through Fast Imprecise Oracles
• Abstract summary: We analyze practical algorithms which only use few clean queries w.r.t. the quality of the dirty oracle. Notably, we prove that our algorithms are, in many respects, best-possible. We outline extensions to other matroid oracle types, non-free dirty oracles and other matroid problems.
• Score: 40.94053997358159
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Querying complex models for precise information (e.g. traffic models, database systems, large ML models) often entails intense computations and results in long response times. Thus, weaker models which give imprecise results quickly can be advantageous, provided inaccuracies can be resolved using few queries to a stronger model. In the fundamental problem of computing a maximum-weight basis of a matroid, a well-known generalization of many combinatorial optimization problems, algorithms have access to a clean oracle to query matroid information. We additionally equip algorithms with a fast but dirty oracle modelling an unknown, potentially different matroid. We design and analyze practical algorithms which only use few clean queries w.r.t. the quality of the dirty oracle, while maintaining robustness against arbitrarily poor dirty matroids, approaching the performance of classic algorithms for the given problem. Notably, we prove that our algorithms are, in many respects, best-possible. Further, we outline extensions to other matroid oracle types, non-free dirty oracles and other matroid problems.

Related papers

• Matroid Algorithms Under Size-Sensitive Independence Oracles [19.61677355524952]
  Matroid algorithms assume that each independence query can be answered in constant time, regardless of the size of the queried set.<n>In particular, for natural and widely studied classes such as graphic matroids, even a single independence query can require work linear in the size of the set.<n>We introduce a size-sensitive cost model where the cost of a query $Q$ scales with $|Q|$.
  arXiv  Detail & Related papers  (2026-04-30T20:26:35Z)
• Efficient Matroid Bandit Linear Optimization Leveraging Unimodality [3.620281545470954]
  This paper sheds a new light on the matroid semi-bandit problem by exploiting its underlying unimodal structure.<n> Experiments conducted on various matroid benchmarks show (i.e., no loss in regret compared to state-of-the-art approaches) no loss in regret compared to state-of-the-art approaches.
  arXiv  Detail & Related papers  (2025-11-29T19:41:13Z)
• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  We present a novel gradient-free algorithm to solve convex optimization problems. Such problems are encountered in medicine, physics, and machine learning. We provide convergence guarantees for the proposed algorithm under both types of noise.
  arXiv  Detail & Related papers  (2024-11-21T10:26:17Z)
• Navigating the Labyrinth: Evaluating LLMs' Ability to Reason About Search Problems [62.76627483915117]
  Large Language Models (LLMs) have recently achieved impressive performance in math and reasoning benchmarks.<n>We introduce a new benchmark, SearchBench, which contains 11 unique search problems inspired by intuitive puzzles.<n>We show that using step-by-step, language-only reasoning, even the most advanced LLMs fail to solve SearchBench.
  arXiv  Detail & Related papers  (2024-06-18T00:44:58Z)
• Fast White-Box Adversarial Streaming Without a Random Oracle [48.45771871410984]
  We consider a strong white-box adversarial model, in which the adversary has access to all past random coins and the parameters used by the streaming algorithm. We focus on the sparse recovery problem and extend our result to other tasks such as distinct element estimation. We construct a near-optimal solution for the sparse recovery problem in white-box adversarial streams, based on the subexponentially secure Learning with Errors assumption.
  arXiv  Detail & Related papers  (2024-06-10T21:23:19Z)
• Fully Dynamic Submodular Maximization over Matroids [27.83996903538686]
  maximizing monotone submodular functions under a matroid constraint is a classic algorithmic problem with multiple applications in data mining and machine learning. We study this classic problem in the fully dynamic setting, where elements can be both inserted and deleted in real-time. Our main result is a randomized algorithm that maintains an efficient data structure with an $tildeO(k2)$ amortized update time (in the number of additions and deletions) and yields a $4$-approximate solution, where $k$ is the rank of the matroid.
  arXiv  Detail & Related papers  (2023-05-31T14:55:47Z)
• ALGO: Synthesizing Algorithmic Programs with LLM-Generated Oracle Verifiers [60.6418431624873]
  Large language models (LLMs) excel at implementing code from functionality descriptions but struggle with algorithmic problems. We propose ALGO, a framework that synthesizes Algorithmic programs with LLM-Generated Oracles to guide the generation and verify their correctness. Experiments show that when equipped with ALGO, we achieve an 8x better one-submission pass rate over the Codex model and a 2.6x better one-submission pass rate over CodeT.
  arXiv  Detail & Related papers  (2023-05-24T00:10:15Z)
• Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer Programs [0.0]
  Current solvers for mixed-integer programming (MIP) problems are designed to perform well on a wide range of problems. Recent works have shown that machine learning (ML) can be integrated with an MIP solver to inject domain knowledge and efficiently close the optimality gap. This paper proposes an online solver that uses the notion of entropy to efficiently build a model with minimal training data and tuning.
  arXiv  Detail & Related papers  (2022-02-07T18:52:56Z)
• Robust and Accurate Superquadric Recovery: a Probabilistic Approach [29.7543198254021]
  We propose the first probabilistic method to recover superquadrics from point clouds. Our method outperforms the state-of-the-art in terms of accuracy, efficiency, and robustness on both synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-11-29T13:17:17Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters [10.279748604797911]
  Key problems in machine learning and data science are routinely modeled as optimization problems and solved via optimization algorithms. With the increase of the volume of data and the size and complexity of the statistical models used to formulate these often ill-conditioned optimization tasks, there is a need for new efficient algorithms able to cope with these challenges. In this thesis, we deal with each of these sources of difficulty in a different way. To efficiently address the big data issue, we develop new methods which in each iteration examine a small random subset of the training data only. To handle the big model issue, we develop methods which in each iteration update
  arXiv  Detail & Related papers  (2020-08-26T21:15:18Z)
• New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
  We present three new algorithms for constructing differentially private synthetic data. The algorithms satisfy differential privacy even in the worst case. Compared to the state-of-the-art method High-Dimensional Matrix Mechanism citeMcKennaMHM18, our algorithms provide better accuracy in the large workload.
  arXiv  Detail & Related papers  (2020-07-10T15:46:05Z)
• Learning fine-grained search space pruning and heuristics for combinatorial optimization [5.72274610208488]
  We propose a framework for leveraging machine learning techniques to scale-up exact optimization algorithms. Our framework learns the relatively simpler task of pruning the elements in order to reduce the size of the problem instances. We show that our framework can prune a large fraction of the input graph and still detect almost all of the maximum cliques.
  arXiv  Detail & Related papers  (2020-01-05T13:10:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.