Related papers: Computability of Optimizers

Computability of Optimizers

URL: http://arxiv.org/abs/2301.06148v1
Date: Sun, 15 Jan 2023 17:41:41 GMT
Title: Computability of Optimizers
Authors: Yunseok Lee, Holger Boche and Gitta Kutyniok
Abstract summary: We will show that in various situations the is unattainable on Turing machines and consequently on digital computers. We prove such results for a variety of well-known problems from very different areas, including artificial intelligence, financial mathematics, and information theory.
Score: 71.84486326350338
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Optimization problems are a staple of today's scientific and technical landscape. However, at present, solvers of such problems are almost exclusively run on digital hardware. Using Turing machines as a mathematical model for any type of digital hardware, in this paper, we analyze fundamental limitations of this conceptual approach of solving optimization problems. Since in most applications, the optimizer itself is of significantly more interest than the optimal value of the corresponding function, we will focus on computability of the optimizer. In fact, we will show that in various situations the optimizer is unattainable on Turing machines and consequently on digital computers. Moreover, even worse, there does not exist a Turing machine, which approximates the optimizer itself up to a certain constant error. We prove such results for a variety of well-known problems from very different areas, including artificial intelligence, financial mathematics, and information theory, often deriving the even stronger result that such problems are not Banach-Mazur computable, also not even in an approximate sense.

Related papers

Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z)
Quantum Optimization: Potential, Challenges, and the Path Forward [14.7608536260003]
Recent advances in quantum computers are demonstrating the ability to solve problems at a scale beyond brute force classical simulation. Across computer science and physics, there are different approaches for major optimization problems.
arXiv Detail & Related papers (2023-12-04T19:00:44Z)
A Framework for Data-Driven Explainability in Mathematical Optimization [0.0]
provably optimal solutions may not be accepted due to the perception of optimization software as a black box. We advocate for introducing the explainability of a solution as another evaluation criterion, next to its objective value. It turns out the cost of enforcing explainability can be very small.
arXiv Detail & Related papers (2023-08-16T12:12:24Z)
Landscape Surrogate: Learning Decision Losses for Mathematical Optimization Under Partial Information [48.784330281177446]
Recent works in learning-integrated optimization have shown promise in settings where the optimization is only partially observed or where general-purposes perform poorly without expert tuning. We propose using a smooth and learnable Landscape Surrogate as a replacement for $fcirc mathbfg$. This surrogate, learnable by neural networks, can be computed faster than the $mathbfg$ solver, provides dense and smooth gradients during training, can generalize to unseen optimization problems, and is efficiently learned via alternating optimization.
arXiv Detail & Related papers (2023-07-18T04:29:16Z)
Reliable AI: Does the Next Generation Require Quantum Computing? [71.84486326350338]
We show that digital hardware is inherently constrained in solving problems about optimization, deep learning, or differential equations. In contrast, analog computing models, such as the Blum-Shub-Smale machine, exhibit the potential to surmount these limitations.
arXiv Detail & Related papers (2023-07-03T19:10:45Z)
Black-box optimization for integer-variable problems using Ising machines and factorization machines [0.8057006406834467]
We propose an approach for integer-variable black-box optimization problems using Ising/annealing machines and factorization machines. The proposed approach can calculate the energy using any of the integer-encoding methods.
arXiv Detail & Related papers (2022-09-01T09:16:51Z)
Comparing the Digital Annealer with Classical Evolutionary Algorithm [0.0]
Examples of solvers that use specialised hardware are IBM's Quantum System One and D-wave's Quantum Annealer (QA) and Fujitsu's Digital Annealer (DA)
arXiv Detail & Related papers (2022-05-26T19:04:20Z)
Ising machines as hardware solvers of combinatorial optimization problems [1.8732539895890135]
Ising machines are hardware solvers which aim to find the absolute or approximate ground states of the Ising model. A scalable Ising machine that outperforms existing standard digital computers could have a huge impact for practical applications.
arXiv Detail & Related papers (2022-04-01T08:24:06Z)
Why Do Local Methods Solve Nonconvex Problems? [54.284687261929115]
Non-used optimization is ubiquitous in modern machine learning. We rigorously formalize it for instances of machine learning problems. We hypothesize a unified explanation for this phenomenon.
arXiv Detail & Related papers (2021-03-24T19:34:11Z)
From Checking to Inference: Actual Causality Computations as Optimization Problems [79.87179017975235]
We present a novel approach to formulate different notions of causal reasoning, over binary acyclic models, as optimization problems. We show that both notions are efficiently automated. Using models with more than $8000$ variables, checking is computed in a matter of seconds, with MaxSAT outperforming ILP in many cases.
arXiv Detail & Related papers (2020-06-05T10:56:52Z)

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