東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Exploring Hybrid Algorithms and Opti...

Brown, Robin Alexandra,

Linked to FindBook

Google Book

Amazon

博客來

Exploring Hybrid Algorithms and Optimization Strategies in Non-Conventional Computing Architectures /

Record Type:	Electronic resources : Monograph/item
Title/Author:	Exploring Hybrid Algorithms and Optimization Strategies in Non-Conventional Computing Architectures // Robin Alexandra Brown.
Author:	Brown, Robin Alexandra,
Description:	1 electronic resource (158 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 86-03, Section: B.
Contained By:	Dissertations Abstracts International86-03B.
Subject:	Quantum computing. -
Online resource:	https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=31460310
ISBN:	9798384340713

Exploring Hybrid Algorithms and Optimization Strategies in Non-Conventional Computing Architectures /
Brown, Robin Alexandra,

Exploring Hybrid Algorithms and Optimization Strategies in Non-Conventional Computing Architectures /Robin Alexandra Brown. - 1 electronic resource (158 pages)

Source: Dissertations Abstracts International, Volume: 86-03, Section: B.

The relentless increase in computing workloads coupled with the potential slowdown of Moore's law has spurred the development of both non-conventional computing architectures and algorithms that make use of these novel architectures. This research is primarily conducted by disjoint communities that rely heavily on algorithmic "primitives" to abstract away the intricacies of the other's work, and to serve as a buffer between them to enable concurrent development. As additional research builds on existing primitives, it creates a feedback cycle where those primitives become increasingly entrenched, creating further justification for continuing to work with them. This is particularly problematic because it is unclear whether the small number of primitives that dominate the literature today were deliberately designed with real-world applications in mind. More broadly, we advocate for taking a holistic view of hardware, algorithm and abstraction interactions, with the goal of promoting primitives that appropriately balance ease of hardware implementation with impact of downstream applications.In this thesis, we primarily focus on the interaction between algorithms and the Ising abstraction, with the objective of deriving complexity metrics that quantify their "fit". To do so, we will begin by introducing copositive and completely-positive optimization as a bridge between convex and non-convex optimization. We find that this is a helpful lens for complexity analysis of hybrid algorithms because it allows for convex optimization algorithms to be applied to some of the non-convex problems that we hope to address with non-conventional computing.We will examine neural network verification as an illustrative example to develop geometric intuition for how copositive/completely positive optimization can exactly represent mixed-binary quadratic programs, while closely related semi-definite programs result in relaxation gaps. While the completely positive representation of neural network verification is intractable, it is useful in its own right due to its similarity to semi-definite programming (SDP). This perspective offers insights for how to construct tighter SDP-based relaxations for verification and unifies existing SDP-based verification methods.With this intuition in place, we will then present our hybrid Ising-classical cutting-plane algorithm for copositive optimization. We will examine the algorithm's convergence guarantees, which it notably inherits directly from existing analysis of convex optimization algorithms. Concluding this section, we leverage our proposed methodology to justify revising the Ising abstraction.Finally, we turn our attention to the Coherent Ising Machine as an example of hardware whose native physics is more closely aligned with the modified Ising abstraction -- this variant of the CIM is referred to as the Continuous-Variable Coherent Ising Machine (CV-CIM). We will show how existing optimization techniques, such as momentum and Adam, can be readily incorporated into the CV-CIM. These modifications allow the device to inherit many of the favorable properties of these algorithms, including accelerated convergence, superior navigation of non-convex landscapes, and robustness to parameter tuning.

English

ISBN: 9798384340713Subjects--Topical Terms:

2115803
Quantum computing.

Exploring Hybrid Algorithms and Optimization Strategies in Non-Conventional Computing Architectures /
LDR:04625nmm a22003973i 4500 001 2435921
005 20251014050542.5
006 m o d
007 cr|nu||||||||
008 261011s2024 miu||||||m |||||||eng d
020 $a 9798384340713
035 $a (MiAaPQD)AAI31460310
035 $a (MiAaPQD)Stanfordkx590cv4574
035 $a AAI31460310
040 $a MiAaPQD $b eng $c MiAaPQD $e rda
100 1 $a Brown, Robin Alexandra, $e author. $3 3826408
245 1 0 $a Exploring Hybrid Algorithms and Optimization Strategies in Non-Conventional Computing Architectures / $c Robin Alexandra Brown.
264 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2024
300 $a 1 electronic resource (158 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 86-03, Section: B.
500 $a Advisors: Pavone, Marco Committee members: Azizan, Navid; Udell, Madeleine.
502 $b Ph.D. $c Stanford University $d 2024.
520 $a The relentless increase in computing workloads coupled with the potential slowdown of Moore's law has spurred the development of both non-conventional computing architectures and algorithms that make use of these novel architectures. This research is primarily conducted by disjoint communities that rely heavily on algorithmic "primitives" to abstract away the intricacies of the other's work, and to serve as a buffer between them to enable concurrent development. As additional research builds on existing primitives, it creates a feedback cycle where those primitives become increasingly entrenched, creating further justification for continuing to work with them. This is particularly problematic because it is unclear whether the small number of primitives that dominate the literature today were deliberately designed with real-world applications in mind. More broadly, we advocate for taking a holistic view of hardware, algorithm and abstraction interactions, with the goal of promoting primitives that appropriately balance ease of hardware implementation with impact of downstream applications.In this thesis, we primarily focus on the interaction between algorithms and the Ising abstraction, with the objective of deriving complexity metrics that quantify their "fit". To do so, we will begin by introducing copositive and completely-positive optimization as a bridge between convex and non-convex optimization. We find that this is a helpful lens for complexity analysis of hybrid algorithms because it allows for convex optimization algorithms to be applied to some of the non-convex problems that we hope to address with non-conventional computing.We will examine neural network verification as an illustrative example to develop geometric intuition for how copositive/completely positive optimization can exactly represent mixed-binary quadratic programs, while closely related semi-definite programs result in relaxation gaps. While the completely positive representation of neural network verification is intractable, it is useful in its own right due to its similarity to semi-definite programming (SDP). This perspective offers insights for how to construct tighter SDP-based relaxations for verification and unifies existing SDP-based verification methods.With this intuition in place, we will then present our hybrid Ising-classical cutting-plane algorithm for copositive optimization. We will examine the algorithm's convergence guarantees, which it notably inherits directly from existing analysis of convex optimization algorithms. Concluding this section, we leverage our proposed methodology to justify revising the Ising abstraction.Finally, we turn our attention to the Coherent Ising Machine as an example of hardware whose native physics is more closely aligned with the modified Ising abstraction -- this variant of the CIM is referred to as the Continuous-Variable Coherent Ising Machine (CV-CIM). We will show how existing optimization techniques, such as momentum and Adam, can be readily incorporated into the CV-CIM. These modifications allow the device to inherit many of the favorable properties of these algorithms, including accelerated convergence, superior navigation of non-convex landscapes, and robustness to parameter tuning.
546 $a English
590 $a School code: 0212
650 4 $a Quantum computing. $3 2115803
650 4 $a Sample size. $3 3642155
650 4 $a Integer programming. $3 648270
650 4 $a Computers. $3 544777
650 4 $a Graphs. $3 3685259
650 4 $a Neural networks. $3 677449
650 4 $a Plot (Narrative). $3 3563398
650 4 $a Convex analysis. $3 3681761
650 4 $a Design. $3 518875
650 4 $a Complexity theory. $3 3562955
650 4 $a Optimization algorithms. $3 3683616
650 4 $a Geometry. $3 517251
650 4 $a Computer science. $3 523869
650 4 $a Mathematics. $3 515831
690 $a 0389
690 $a 0800
690 $a 0984
690 $a 0405
710 2 $a Stanford University. $e degree granting institution. $3 3765820
720 1 $a Pavone, Marco $e degree supervisor.
773 0 $t Dissertations Abstracts International $g 86-03B.
790 $a 0212
791 $a Ph.D.
792 $a 2024
856 4 0 $u https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=31460310