Theses and Dissertations from UMD
Permanent URI for this communityhttp://hdl.handle.net/1903/2
New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a give thesis/dissertation in DRUM
More information is available at Theses and Dissertations at University of Maryland Libraries.
Browse
74 results
Search Results
Item Efficient Optimization Algorithms for Nonconvex Machine Learning Problems(2024) Xian, Wenhan; Huang, Heng HH; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In recent years, the success of the AI revolution has led to the training of larger neural networks on vast amounts of data to achieve superior performance. These powerful machine learning models have enabled the creation of remarkable AI products. Optimization, as the core of machine learning, becomes especially crucial because most machine learning problems can ultimately be formulated as optimization problems, which require minimizing a loss function with respect to model parameters based on training samples. To enhance the efficiency of optimization algorithms, distributed learning has emerged as a popular solution for addressing large-scale machine learning tasks. In distributed learning, multiple worker nodes collaborate to train a global model. However, a key challenge in distributed learning is the communication cost. This thesis introduces a novel adaptive gradient algorithm with gradient sparsification to address this issue. Another significant challenge in distributed learning is the communication overhead on the central parameter server. To mitigate this bottleneck, decentralized distributed (serverless) learning has been proposed, where each worker node only needs to communicate with its neighbors. This thesis investigates core nonconvex optimization problems in decentralized settings, including constrained optimization, minimax optimization, and second-order optimality. Efficient optimization algorithms are proposed to solve these problems. Additionally, the convergence analysis of minimax optimization under the generalized smooth condition is explored. A generalized algorithm is proposed, which can be applied to a broader range of applications.Item Understanding and Enhancing Machine Learning Models with Theoretical Foundations(2024) Hu, Zhengmian; Huang, Heng HH; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Machine learning has become a key driver of many contemporary technological advancements. With its empirical success, there is an urgent need for theoretical research to explain and complement these practical achievements. This includes understanding the empirical success of machine learning, especially deep learning, and aiding the design of better algorithms in terms of performance, efficiency, and security. This dissertation aims to advance the understanding and practical development of machine learning through three interrelated research directions, while emphasizing reliable theoretical guarantees throughout the process. In the first part, we study the deep learning theory under overparameterization conditions. The core objects of study are the Conjugate Kernel and Neural Tangent Kernel, which have deep connections to the training dynamics of deep learning. Based on the analysis of these kernels, we prove several new concentration results characterizing the trainability and generalization of infinitely wide neural networks. In the second part, we focus on training algorithms. On one hand, we propose new algorithms to improve learning efficiency. This includes a new underdamped Langevin MCMC method called ALUM, for which we prove its complexity reaches the theoretical lower bound. On the other hand, we propose new theoretical tools to analyze existing algorithms and obtain tighter convergence results. For Proxskip, our analysis shows it can still achieve an improvement in communication complexity from sublinear to linear convergence under stochastic oracle. We also generalize the concept of Lipschitz smoothness for tighter non-convex optimization analysis. In the third part, we develop new Monte Carlo methods to large language models (LLMs) to improve their efficiency and security. We develop unbiased watermarking techniques to protect model outputs and propose an Accelerated Speculative Sampling method for faster inference. We also investigate the trade-off between watermark strength and inference sampling efficiency, pointing out the conflict between the two.Item OPTIMAL PROBING OF BATTERY CYCLES FOR MACHINE LEARNING-BASED MODEL DEVELOPMENT(2024) Nozarijouybari, Zahra; Fathy, Hosam HF; Mechanical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This dissertation examines the problems of optimizing the selection of the datasets and experiments used for parameterizing machine learning-based electrochemical battery models. The key idea is that data selection, or “probing” can empower such models to achieve greater fidelity levels. The dissertation is motivated by the potential of battery models to enable theprediction and optimization of battery performance and control strategies. The literature presents multiple battery modeling approaches, including equivalent circuit, physics-based, and machine learning models. Machine learning is particularly attractive in the battery systems domain, thanks to its flexibility and ability to model battery performance and aging dynamics. Moreover, there is a growing interest in the literature in hybrid models that combine the benefits of machine learning with either the simplicity of equivalent circuit models or the predictiveness of physics-based models or both. The focus of this dissertation is on both hybrid and purely data-driven battery models. Moreover, the overarching question guiding the dissertation is: how does the selection of the datasets and experiments used for parameterizing these models affect their fidelity and parameter identifiability? Parameter identifiability is a fundamental concept from information theory that refers to the degree to which one can accurately estimate a given model’s parameters from input-output data. There is substantial existing research in the literature on battery parameter identifiability. An important lesson from this literature is that the design of a battery experiment can affect parameter identifiability significantly. Hence, test trajectory optimization has the potential to substantially improve model parameter identifiability. The literature explores this lesson for equivalent circuit and physics-based battery models. However, there is a noticeable gap in the literature regarding identifiability analysis and optimization for both machine learning-based and hybrid battery models. To address the above gap, the dissertation makes four novel contributions to the literature. The first contribution is an extensive survey of the machine learning-based battery modeling literature, highlighting the critical need for information-rich and clean datasets for parameterizing data-driven battery models. The second contribution is a K-means clustering-based algorithm for detecting outlier patterns in experimental battery cycling data. This algorithm is used for pre-cleaning the experimental cycling datasets for laboratory-fabricated lithium-sulfur (Li-S) batteries, thereby enabling the higher-fidelity fitting of a neural network model to these datasets. The third contribution is a novel algorithm for optimizing the cycling of a lithium iron phosphate (LFP) to maximize the parameter identifiability of a hybrid model of this battery. This algorithm succeeds in improving the resulting model’s Fisher identifiability significantly in simulation. The final contribution focuses on the application of such test trajectory optimization to the experimental cycling of commercial LFP cells. This work shows that test trajectory optimization is s effective not just at improving parameter identifiability, but also at probing and uncovering higher-order battery dynamics not incorporated in the initial baseline model. Collectively, all four of these contributions show the degree to which the selection of battery cycling datasets and experiments for richness and cleanness can enable higher-fidelity data-driven and hybrid modeling, for multiple battery chemistries.Item A Framework for Remaining Useful Life Prediction and Optimization for Complex Engineering Systems(2024) Weiner, Matthew Joesph; Azarm, Shapour; Groth, Katrina M; Reliability Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Remaining useful life (RUL) prediction plays a crucial role in maintaining the operational efficiency, reliability, and performance of complex engineering systems. Recent efforts have primarily focused on individual components or subsystems, neglecting the intricate relationships between components and their impact on system-level RUL (SRUL). The existing gap in predictive methodologies has prompted the need for an integrated approach to address the complex nature of these systems, while optimizing the performance with respect to these predictive indicators. This thesis introduces a novel methodology for predicting and optimizing SRUL, and demonstrates how the predicted SRUL can be used to optimize system operation. The approach incorporates various types of data, including condition monitoring sensor data and component reliability data. The methodology leverages probabilistic deep learning (PDL) techniques to predict component RUL distributions based on sensor data and component reliability data when sensor data is not available. Furthermore, an equation node-based Bayesian network (BN) is employed to capture the complex causal relationships between components and predict the SRUL. Finally, the system operation is optimized using a multi-objective genetic algorithm (MOGA), where SRUL is treated as a constraint and also as an objective function, and the other objective relates to mission completion time. The validation process includes a thorough examination of the component-level methodology using the C-MAPSS data set. The practical application of the proposed methodology in this thesis is through a case study involving an unmanned surface vessel (USV), which incorporates all aspects of the methodology, including system-level validation through qualitative metrics. Evaluation metrics are employed to quantify and qualify both component and system-level results, as well as the results from the optimizer, providing a comprehensive understanding of the proposed approach’s performance. There are several main contributions of this thesis. These include a new deep learning structure for component-level PHM, one that utilizes a hybrid-loss function for a multi-layer long short-term memory (LSTM) regression model to predict RUL with a given confidence interval while also considering the complex interactions among components. Another contribution is the development of a new framework for computing SRUL from these predicted component RULs, in which a Bayesian network is used to perform logic operations and determine the SRUL. These contributions advance the field of PHM, but also provide a practical application in engineering. The ability to accurately predict and manage the RUL of components within a system has profound implications for maintenance scheduling, cost reduction, and overall system reliability. The integration of the proposed method with an optimization algorithm closes the loop, offering a comprehensive solution for offline planning and SRUL prediction and optimization. The results of this research can be used to enhance the efficiency and reliability of engineering systems, leading to more informed decision-making.Item Advancing the State of Auto-tuning with Programming Languages(2024) Chen, Ray Sun; Hollingsworth, Jeffrey K; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In the realm of computer science, auto-tuning refers to techniques for software performance optimization. The focus of traditional auto-tuning research is to identify novel performance parameters to expand the optimization space for a given target software/platform combination, and improve the automated search within this optimization space. This makes high-performance computing (HPC) a prime candidate for auto-tuning research, as it sits at the nexus of architectural diversity and performance criticality. However, the major successes for HPC auto-tuning to date involve tailoring memory access patterns to specific cache hierarchies. While important, this is just a small piece of the overall performance portability puzzle. I argue that auto-tuning has room to expand and optimize a richer set of HPC application tuning parameters through the combination of novel non-intrusive programming language idioms and advanced lightweight online search techniques. I support my argument through four contributions to the field. This dissertation describes two techniques for expanding auto-tuning optimization spaces, and two techniques for distributing the auto-tuning search for parallel efficiency.Item Aero Database Development and Two-Dimensional Hypersonic Trajectory Optization for the High-speed Army Reference Vehicle(2023) James, Brendan; Brehm, Christoph; Larsson, Johan; Aerospace Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Steady-flow inviscid and simulations of the High-Speed Army Reference Vehicle geometry were performed within the CHAMPS solver framework at Mach numbers of 4, 6, and 8, and an integrated streamline method was used to apply viscous corrections for Reynolds numbers up to 2x10^8. For each flow Mach, angle of attack sweeps from -10° to +10° were used to determine baseline drag, lift, and moment coefficient alpha dependencies. Coefficient values were then interpolated across Mach, alpha, and Reynolds number parameter spaces to construct an aerodynamic force coefficient database for use in two-dimensional flight simulation and trajectory optimization. By simulating flight with a maximum lift-to-drag control input, sample trajectories for determining maximum vehicle range were produced. A proportional-navigation (PN) controller was implemented which allowed for the targeting of specific altitudes throughout the progression of a trajectory. The PN controller and simulation schemes were then utilized in genetic-algorithm optimization to produce trajectory profiles for achieving minimum time-to-target for gliding flight in standard atmospheric conditions. Over the examined range of initial altitudes, Mach numbers, and release angles, the fastest trajectories were consistently shown to be those which achieved or maintained stratospheric altitudes and consequently benefited from significantly reduced drag before performing a nose-over maneuver for an accurate ground strike.Item Safe Navigation of Autonomous Vehicles in Structured Mixed-Traffic Environments(2023) Tariq, Faizan Muhammad; Baras, John S; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The primary driving force behind autonomous vehicle (AV) research is the prospect of enhancing road safety by preventing accidents caused by human errors. To that end, it seems rather improbable that AVs will replace all human-driven vehicles in the near future. The more plausible scenario is that AVs will gradually be introduced on public roads and highways in the presence of human-driven vehicles, leading to mixed-traffic scenarios. In addition to the existing challenges associated with autonomous driving stemming from various uncertainty factors associated with sensing, prediction, control, and computation, these situations pose further difficulties pertaining to the variability in human driving patterns. Therefore, to ensure widespread public acceptance of AVs, it is crucial to develop planning and decision-making algorithms, while benefiting from modern sensing, computation, and control methods, that can deliver safe, efficient, and reliable performance in mixed-traffic situations. Considering the need to cater to the behavior variability of human drivers, we address the joint decision-making and motion planning problem in structured environments with a multi-timescale navigation architecture. Specifically, we design algorithms for commonly encountered highway driving scenarios that require effective real-time decision-making, reliable motion prediction of on-road entities, behavior consideration of on-road agents, and attention to safety as well as passenger comfort. The specific problems addressed in this dissertation include bidirectional highway overtaking, highway maneuvering in traffic, and crash mitigation on highways. In the proposed framework, we first identify and exploit the different timescales involved in the navigation architecture. Then, we propose algorithmic modules while pursuing systematic complexity (data and computation) reduction at different timescales to gain immediate performance improvements in inference and action/response delay minimization. This leads to real-time situation assessment, computation, and action/control, allowing us to satisfy some of the key requirements for autonomous driving algorithms. Notably, the algorithms proposed in this dissertation ensure that the safety of the overall system is a fundamental constraint built into the system. Distinctive features of the proposed approaches include real-time operation capability, consideration for behavior variability of on-road agents, modularity in design, and optimality with respect to various metrics. The algorithms developed and implemented as part of this dissertation fundamentally rely upon the application of optimization techniques in a receding horizon fashion which allows for optimality in performance while explicitly accounting for actuation limits, vehicle dynamics, and safety. Even though the modularity of the proposed navigation framework allows for the incorporation of modern prediction and control methods, we develop various prediction modules for the trajectory prediction of on-road agents. We further benefit from risk evaluation methodologies to ensure robustness to behavior variability of human drivers on the road and handle collision-prone situations. In the spirit of emulating real-world situations, we place special emphasis on utilizing realistic driving simulations that capture the effects of communication delays between different modules, limitations in computation resources, and randomization of scenarios. For the developed algorithms, we evaluate the performance in comparative singular case studies as well as randomized Monte Carlo simulations with respect to several metrics to assess the efficacy of the developed methods.Item QUANTUM COMBINATORIAL OPTIMIZATION ALGORITHMS FOR PACKING PROBLEMS IN CLASSICAL COMPUTING AND NETWORKING(2023) Unsal, Cem Mehmet; Oruc, Yavuz A; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In Computer Engineering, packing problems play a central role in many aspects of hardware control. The field aims to maximize computer processing speed, network throughput, and dependability in industry applications. Many of these constrained maximization problems can be expressed as packing problems in integer programming when working with restrictions such as latency, memory size, race conditions, power, and component availability. Some of the most crucial of these integer programming problems are NP-hard for the global optimum. Therefore, real-world applications heavily rely on heuristics and meta-heuristics to find good solutions. With recent developments in quantum meta-heuristic methods and promising results in experimental quantum computing systems, quantum computing is rapidly becoming more and more relevant for complex real-world combinatorial optimization tasks. This thesis is about applications of quantum combinatorial optimization algorithms in classical computer engineering problems. These include novel quantum computing techniques that respect the constraints of state-of-the-art experimental quantum systems. This thesis includes five projects. FASTER QUANTUM CONCENTRATION VIA GROVER'S SEARCH:One of the most important challenges in information networks is to gather data from a larger set of nodes to a smaller set of nodes. This can be done via the use of a concentrator architecture in the connection topology. This chapter is a proof-of-concept that demonstrates a quantum-based controller in large interconnection networks can asymptotically perform this task faster. We specifically present quantum algorithms for routing concentration assignments on full-capacity fat-and-slim concentrators, bounded fat-and-slim concentrators, and regular fat-and-slim concentrators. Classically, the concentration assignment takes O(n) time on all these concentrators, where n is the number of inputs. Powered by Grover's quantum search algorithm, our algorithms take O(√(nc) ln(c)) time, where c is the capacity of the concentrator. Thus, our quantum algorithms are asymptotically faster than their classical counterparts when (c ln^2(c))=o(n). In general, c = n^μ satisfies (c ln^2(c))=o(n), implying a time complexity of O(n^(0.5(1+ μ )) ln (n)), for any μ, 0 < μ < 1. QUANTUM ADVERSARIAL LEARNING IN EMULATION OF MONTE-CARLO METHODS FOR MAX-CUT APPROXIMATION: QAOA IS NOT OPTIMAL:One of the leading candidates for near-term quantum advantage is the class of Variational Quantum Algorithms. However, these algorithms suffer from classical difficulty in optimizing the variational parameters as the number of parameters increases. Therefore, it is important to understand the expressibility and power of various ansätze to produce target states and distributions. To this end, we apply notions of emulation to Variational Quantum Annealing and the Quantum Approximate Optimization Algorithm (QAOA) to show that variational annealing schedules with equivalent numbers of parameters outperform QAOA. Our Variational Quantum Annealing schedule is based on a novel polynomial parameterization that can be optimized in a similar gradient-free way as QAOA, using the same physical ingredients. In order to compare the performance of ansätze types, we have developed statistical notions of Monte-Carlo methods. Monte-Carlo methods are computer programs that generate random variables that approximate a target number that is computationally hard to calculate exactly. While the most well-known Monte-Carlo method is Monte-Carlo integration (e.g., Diffusion Monte-Carlo or path-integral quantum Monte-Carlo), QAOA is itself a Monte-Carlo method that finds good solutions to NP-complete problems such as Max-cut. We apply these statistical Monte-Carlo notions to further elucidate the theoretical framework around these quantum algorithms. SCHEDULING JOBS IN A SHARED HIGH-PERFORMANCE COMPUTER WITH A NISQ COMPUTER:Several quantum approximation algorithms for NP-hard optimization problems have been described in the literature. The properties of quantum approximation algorithms have been well-explored for optimization problems of Ising type with 2-local Hamiltonians. A wide range of optimization problems can be mapped to Ising problems. However, the mapping overhead of many problem instances puts them out of the reach of Noisy Intermediate-scale Quantum (NISQ) devices. In this chapter, we develop a way of mapping constrained optimization problems to higher-order spin interactions to put a larger set of problem instances within reach of spin interaction devices with potential NISQ applications. We demonstrate the growth in the practicable set of problem instances by comparing the resource requirements as a function of coupling. As an example, we have demonstrated our techniques on the problem of scheduling jobs in a high-performance computer queue with limited memory and CPUs. PROTEIN STRUCTURES WITH OSCILLATING QPACKER:A significant challenge in designing proteins for therapeutic purposes is determining the structure of a protein to find the sidechain identities given a protein backbone. This problem can be easily and efficiently encoded as a quadratic binary optimization problem. There has been a significant effort to find ways to solve these problems in the field of quantum information, both exactly and approximately. An important initiative has applied experimental quantum annealing platforms to solve this problem and got promising results. This project is about optimizing the annealing schedule for the sidechain identity problem, inspired by cutting-edge developments in the algorithmic theory of quantum annealing. ON THE COMPLEXITY OF GENERALIZED DISCRETE LOGARITHM PROBLEM:The Generalized Discrete Logarithm Problem (GDLP) is an extension of the Discrete Logarithm Problem where the goal is to find x∈ℤ_s such that g^x mod s=y for a given g,y∈ℤ_s. The generalized discrete logarithm is similar, but instead of a single base element, it uses a number of base elements that do not necessarily commute. In this chapter, we prove that GDLP is NP-hard for symmetric groups. The lower-bound complexity of GDLP has been an open question since GDLP was defined in 2008 until our proof. Furthermore, we prove that GDLP remains NP-hard even when the base elements are permutations of at most three elements. Lastly, we discuss the implications and possible implications of our proofs in classical and quantum complexity theory.Item Optimization Problems in Quantum Machine Learning(2023) You, Xuchen; Wu, Xiaodi; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The variational algorithm is a paradigm for designing quantum procedures implementable on noisy intermediate-scale quantum (NISQ) machines. It is viewed as a promising candidate for demonstrating practical quantum advantage. In this dissertation, we look into the optimization aspect of the variational quantum algorithms as an attempt to answer when and why a variational quantum algorithm works. We mainly focus on two instantiations of the family of variational algorithms, the Variational Quantum Eigensolvers (VQEs) and the Quantum Neural Networks (QNNs). We first established that, for almost all QNN architecture designs, there exist hard problem instances leading to an optimization landscape swarmed by spurious local minima provided that the QNN is under-parameterized. This observation rules out the possibility of a universal good QNN design achieving exponential advantage against the classical neural networks on any dataset and calls for instance-dependent designs for variational circuits. We then show that VQE training converges linearly when the number of parameters exceeds an over-parameterization threshold. By tying the threshold to instance-dependent quantities, we developed variants of VQE algorithms that allow the training and testing of shallower variational circuits, as depths are usually the implementation bottlenecks on NISQ machines. For QNNs, by looking into its convergence, we show that the dynamics of QNN training are different from the dynamics of any kernel regression, therefore ruling out the popular conjecture that over-parameterized QNNs are equivalent to certain versions of neural tangent kernels like their classical counterparts. As a practical implication, our analysis showcases the measurement design as a way to accelerate the convergence of QNNs. At the end of this dissertation, we consider the classical problem of optimization with partial information, the Multi-arm Bandits (MABs). We show that, when enhanced with quantum access to the arms, there is a quadratic speed-up against the classical algorithms, which can serve as the building block for quantum reinforcement learning algorithms.Item Ordering Non-Linear Subspaces for Airfoil Design and Optimization via Rotation Augmented Gradients(2023) Van Slooten, Alec; Fuge, Mark; Mechanical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Airfoil optimization is critical to the design of turbine blades and aerial vehicle wings, among other aerodynamic applications. This design process is often constrained by the computational time required to perform CFD simulations on different design options, or the availability of adjoint solvers. A common method to mitigate some of this computational expense in nongradient optimization is to perform dimensionality reduction on the data and optimize the design within this smaller subspace. Although learning these low-dimensional airfoil manifolds often facilitates aerodynamic optimization, these subspaces are often still computationally expensive to explore. Moreover, the complex data organization of many current nonlinear models make it difficult to reduce dimensionality without model retraining. Inducing orderings of latent components restructures the data, reduces dimensionality reduction information loss, and shows promise in providing near-optimal representations in various dimensions while only requiring the model to be trained once. Exploring the response of airfoil manifolds to data and model selection and inducing latent component orderings have potential to expedite airfoil design and optimization processes. This thesis first investigates airfoil manifolds by testing the performance of linear and nonlinear dimensionality reduction models, examining if optimized geometries occupy lower dimensional manifolds than non-optimized geometries, and by testing if the learned representation can be improved by using target optimization conditions as data set features. We find that autoencoders, although often suffering from stability issues, have increased performance over linear methods such as PCA in low dimensional representations of airfoil databases. We also find that the use of optimized geometry and the addition of performance parameters have little effect on the intrinsic dimensionality of the data. This thesis then explores a recently proposed approach for inducing latent space orderings called Rotation Augmented Gradient (RAG) [1]. We extend their algorithm to nonlinear models to evaluate its efficacy at creating easily-navigable latent spaces with reduced training, increased stability, and improved design space preconditioning. Our extension of the RAG algorithm to nonlinear models has potential to expedite dimensional analyses in cases with near-zero gradients and long training times by eliminating the need to retrain the model for different dimensional subspaces