자료유형  

 학위논문

Control Number  

0017162955

International Standard Book Number  

9798384340713

Dewey Decimal Classification Number  

004

Main Entry-Personal Name  

Brown, Robin Alexandra.

Publication, Distribution, etc. (Imprint  

[S.l.] : Stanford University., 2024

Publication, Distribution, etc. (Imprint  

Ann Arbor : ProQuest Dissertations & Theses, 2024

Physical Description  

158 p.

General Note  

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

General Note  

Advisor: Pavone, Marco.

Dissertation Note  

Thesis (Ph.D.)--Stanford University, 2024.

Summary, Etc.  

요약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.

Subject Added Entry-Topical Term  

Quantum computing.

Subject Added Entry-Topical Term  

Sample size.

Subject Added Entry-Topical Term  

Integer programming.

Subject Added Entry-Topical Term  

Computers.

Subject Added Entry-Topical Term  

Graphs.

Subject Added Entry-Topical Term  

Neural networks.

Subject Added Entry-Topical Term  

Plot (Narrative).

Subject Added Entry-Topical Term  

Convex analysis.

Subject Added Entry-Topical Term  

Design.

Subject Added Entry-Topical Term  

Complexity theory.

Subject Added Entry-Topical Term  

Optimization algorithms.

Subject Added Entry-Topical Term  

Geometry.

Subject Added Entry-Topical Term  

Computer science.

Subject Added Entry-Topical Term  

Mathematics.

Added Entry-Corporate Name  

Stanford University.

Host Item Entry  

Dissertations Abstracts International. 86-03B.

Electronic Location and Access  

로그인을 한후 보실 수 있는 자료입니다.

Control Number  

joongbu:655433