As the domain of adversarial attack countermeasures continues to expand, the accurate evaluationof these defenses remains a challenge. Adversarial attacks pose significant challenges to the security and robustness of deep learning models. Traditional methods typically depend on predetermined parameters, such as ensembles of certain methods and manually designed rules, which may not be optimal for generating effective attacks. In this research, we propose a parameter-free adversarial attack by leveraging a learning-to-learn (L2L) framework. We train a recurrent neural network-based optimizer to adaptively update directions and steps, enabling more efficient and adaptive adversarial attacks. We conduct extensive experiments on robust models trained on the MNIST and CIFAR-10 datasets. Our findings show that the learned optimizer outperforms traditional methods, such as PGD, in generating adversarial attacks for small networks and smaller datasets like MNIST. For larger networks, our method demonstrates improved performance only for smaller attack steps. These results highlight the potential of parameter-free attacks in evaluating and understanding the robustness of deep learning models.

Although machine learning has achieved great success in numerous complicated tasks, many machine learning models lack robustness under the presence of adversaries and can be misled by imperceptible adversarial noises. In this dissertation, we first study the robustness verification problem of machine learning, which gives provable guarantees on worst case performance under arbitrarily strong adversaries. We study two popular machine learning models, deep neural networks (DNNs) and ensemble trees, and design efficient and effective algorithms to provably verify the robustness of these models. For neural networks, we develop a linear relaxation based framework, CROWN, where we relax the non-linear units in DNNs using linear bounds, and propagate linear bounds through the network. We generalize CROWN into a linear relaxation based perturbation analysis (LiRPA) algorithm on any computational graphs and general network architectures to handle irregular neural networks used in practice, and released an open source software package, auto_LiRPA, to facilitate the use of LiRPA for researchers in other fields. For tree ensembles, we reduce the robustness verification algorithm to a max-clique finding problem on a specially created graph, which is very efficient compared to existing approaches and can produce high quality lower or upper bounds for the output of a tree ensemble based classifier. After developing our robustness verification algorithms, we utilize them to create a certified adversarial defense for neural networks, where we explicitly optimize the bounds obtained from verification to greatly improve network robustness in a provable manner. Our LiRPA based training method is very efficient: it can scale to large datasets such as downscaled ImageNet and modern computer vision models such as DenseNet. Lastly, we study the robustness of reinforcement learning (RL), which is more challenging than the problem in supervised learning settings. We focus on the robustness of state observations for a RL agent, and develop the state-adversarial Markov decision process (SA-MDP) to characterize the behavior of a RL agent under adversarially perturbed observations. Based on SA-MDP, we develop two orthogonal approaches to improve the robustness of RL: a state-adversarial regularization helping to improve the robustness of function approximators, and alternating training with learned adversaries (ATLA) to mitigate the intrinsic weakness in a policy. Both approaches are evaluated in various simulated environments and they significantly improve the robustness of RL agents under strong adversarial attacks, including a few novel adversarial attacks proposed by us.

This thesis summarizes the work I have done during my master's study at UCLA. We ranked 38th among all the participants of the KDD 21 challenge on large-scale graph machine learning. We built a two-stage model, taking the most out of UniMP and Correct and Smooth architectures in Pytorch. We studied a social network graph with 121 million nodes and 153 categories, achieving node classification accuracy of 65$\%$.

The second part of thesis summarizes a mini-batch attention-based graph machine learning model that we developed. We first learned a dense self-attention based on graph node features and overlayed it with the original adjacencymatrix. It achieves about the same test accuracy of $69.00 \pm 0.28\%$ on the Arxiv dataset compared to clusterGCN, but it has the potential to outperform. This is especially true when graph node features are rich and informative. Interesting results may yield for a deeper GCN.

How and when can we depend on machine learning systems to make decisions for human-being? This is probably the question everybody may (and should) ask before deploying machine learning models in their own fields. Failure to do so can suffer from unexpected consequences: the text recognition systems in the mail distribution center may send the package to the wrong addresses; the self-driving cars may recognize a stop sign as a speed sign; or even worse, the AI-based medical imaging system may mislead the doctors into wrong diagnostics. We attribute a trustworthy machine learning model to three properties: robustness, interpretation, and precise uncertainty estimation. Robustness concerns how the model withstands unexpected inputs, also called out-of-distribution (OOD) data. Depending on whether the data is maneuvered in purpose, the OOD data comprises adversarial examples or unadversarial examples. Interpretation is a set of algorithms that uncover the black-box model inference process, trying to help humans understand why or why not the model generates the desired results. Finally, we seek the uncertainty estimation tools to locate the ground-truth value relative to the estimated value. It also protects the model users by holding the machine predictions for human inspections once the uncertainties raise above some threshold.

In this thesis, I will walk through robustness, interpretation, and uncertainty estimation in three parts. In the first part, I will introduce the backgrounds of robust machine learning models with an example in graph-based semi-supervised learning, followed by a series of methods to train robust neural networks. In the next part, we will move to model interpretation tools, we relate this part to the previous part by discussing our work called Greedy-AS. In the final part, I will discuss my works on robust uncertainty estimation and confidence calibration, this part contains the algorithms, software packages, as well as a demo on how uncertainty estimation helps biological scientists to do quality control of stem cells more efficiently.

Machine learning systems have been shown to be vulnerable to adversarial examples. We study the most practical problem setup for evaluating adversarial robustness of a machine learning system with limited access: the hard-label black-box attack setting for generating adversarial examples, where limited model queries are allowed and only the decision is provided to a queried data input. Several algorithms have been proposed for this problem but they typically require huge amount (>20,000) of queries for attacking one example. Among them, one of the state-of-the-art approaches (Cheng et al., 2019) showed that hard-label attack can be modeled as an optimization problem where the objective function can be evaluated by binary search with additional model queries, thereby a zeroth order optimization algorithm can be applied. In this thesis, we adopt the same optimization formulation but propose to directly estimate the sign of gradient at any direction instead of the gradient itself, which enjoys the benefit of single query. Using this single query oracle for retrieving sign of directional derivative, we develop a novel query-efficient Sign-OPT approach for hard-label black-box attack. We provide a convergence analysis of the new algorithm and conduct experiments on several models on MNIST, CIFAR-10 and ImageNet. We find that Sign-OPT attack consistently requires 5X to 10X fewer queries when compared to the current state-of-the-art approaches and usually converges to an adversarial example with smaller perturbation.

Robustness and counterfactual bias are usually evaluated on a test dataset. However, are these evaluations robust? In other words, if a model is robust or unbiased on a test set, will the properties still hold under a slightly perturbed test set? In this paper, we propose a ``double perturbation'' framework to uncover model weaknesses beyond the test dataset. The framework first perturbs the test dataset to construct abundant natural sentences similar to the test data, and then diagnoses the prediction change regarding a single-word substitution. We apply this framework to study two perturbation-based approaches that are used to analyze models' robustness and counterfactual bias. (1) For robustness, we focus on synonym substitutions and identify vulnerable examples where prediction can be altered. Our proposed attack attains high success rates ($96.0\%$\textendash$99.8\%$) in finding vulnerable examples on both original and robustly trained CNNs and Transformers. (2) For counterfactual bias, we focus on substituting protected tokens (e.g., gender, race), and measure the shift of the \emph{expected} prediction. In the experiments, our method reveals the hidden model bias even if the test set is adversarially chosen.

Recently, bound propagation based certified robust training methods have been proposed for training neural networks with certifiable robustness guarantees. Despite that state-of-the-art (SOTA) methods including interval bound propagation (IBP) and CROWN-IBP have succeeded in providing certified robustness with efficient per-batch training complexity, there are several challenges faced by these certified robust training methods. First, they usually use a long warmup schedule with hundreds or thousands epochs to increase the perturbation radius for SOTA performance and are thus still costly. Second, the convergence of IBP training remains unknown. In this paper, we identify two important issues related to slow warmup schedule for IBP training, namely exploded bounds at initialization, and the imbalance in ReLU activation states. These two issues make certified training difficult and unstable, and thereby long warmup schedules were needed in prior works. We proposed improvements to mitigate these issues and we are able to obtain \textbf{65.03\%} verified error on CIFAR-10 ($\epsilon=\frac{8}{255}$) using very short training schedules. For the convergence problem, we show that for a randomly initialized two-layer ReLU neural network with logistic loss, with sufficiently small perturbation radius and large network width, gradient descent for IBP training can converge to zero training robust error with a linear convergence rate with a high probability, and at this convergence state the robustness certification by IBP can accurately reflect the true robustness of the network.

The field of Automated Machine Learning (AutoML) has gained immense attention for its ability to automate complex machine learning tasks, yet it is still an evolving discipline requiring nuanced approaches to be fully realized. This thesis, "Advancing Automated Machine Learning: Neural Network Architectures and Optimization Algorithms," provides a comprehensive investigation into two foundational pillars: Neural Architecture Search (NAS) and optimization algorithms.

In the first half of the thesis, we confront the inherent challenges of stability and robustness in NAS, enhancing its reliability through a perturbation-based regularization scheme. This allows for more consistent and dependable architecture choices. Furthermore, we extend the traditional paradigms of NAS by framing it as a distribution learning problem, and additionally, by applying it to collaborative filtering. These extensions not only broaden the applicability of NAS but also lead to marked improvements in the efficiency and accuracy of recommendation systems.

The latter part of the thesis focuses on the role of optimization in achieving high performance, particularly in transformer architectures. We identify a critical optimization gap and propose strategies for its mitigation, emphasizing the necessity of a transition from purely architecture-based search to include optimization techniques. Then we delve into a groundbreaking approach to optimization algorithm design through symbolic program discovery. This framework automatically discover new optimization methods that outperform traditional algorithms, thereby introducing an unprecedented level of automation in the development of optimization techniques. Our developed Lion algorithm has been widely adopted by the community. This not only advances the state-of-the-art in optimization algorithms but also significantly augments the capabilities and reach of AutoML systems.

By addressing these multifaceted challenges in both neural architecture and optimization algorithm design, this thesis presents a coherent, unified contribution to the advancement of Automated Machine Learning. It is hoped that these collective insights serve as a robust foundation for future research in the ever-evolving landscape of AutoML.

Neural networks provide state-of-the-art results for most machine learning tasks. Unfortunately, neural networks are vulnerable to adversarial examples. That is, a slightly modified example could be easily generated and fool a well-trained image classifier based on deep neural networks (DNNs) with high confidence. This makes it difficult to apply neural networks in security-critical areas.

To find such examples, we first introduce and define adversarial examples. In the first part, we then discuss how to build adversarial attacks in both image and discrete domains. For image classification, we introduce how to design an adversarial attacker in three different settings. Among them, we focus on the most practical setup for evaluating the adversarial robustness of a machine learning system with limited access: the hard-label black-box attack setting for generating adversarial examples, where limited model queries are allowed and only the decision is provided to a queried data input. For the discrete domain, we first talk about its difficulty and introduce how to conduct the adversarial attack on two applications.

While crafting adversarial examples is an important technique to evaluate the robustness of DNNs, there is a huge need for improving the model robustness as well. Enhancing model robustness under new and even adversarial environments is a crucial milestone toward building trustworthy machine learning systems. In the second part, we talk about the methods to strengthen the model's adversarial robustness. We first discuss attack-dependent defense. Specifically, we first discuss one of the most effective methods for improving the robustness of neural networks: adversarial training and its limitations. We introduce a variant to overcome its problem. Then we take a different perspective and introduce attack-independent defense. We summarize the current methods and introduce a framework-based vicinal risk minimization. Inspired by the framework, we introduce self-progressing robust training. Furthermore, we discuss the robustness trade-off problem and introduce a hypothesis and propose a new method to alleviate it.

Recently, Neural Architecture Search (NAS) has attracted lots of attention for its potential to democratize deep learning. For a practical end-to-end deep learning platform, NAS plays a crucial role in discovering task-specific architecture depending on users' configurations (e.g., dataset, evaluation metric, etc.). Among various search paradigms, Differentiable Neural Architecture Search is one of the most popular NAS methods for its search efficiency and simplicity, accomplished by jointly optimizing the model weight and architecture parameters in a weight-sharing supernet via gradient-based algorithms. At the end of the search phase, the operations with the largest architecture parameters will be selected to form the final architecture, with the implicit assumption that the values of architecture parameters reflect the operation strength. Despite the search efficiency, the weight-sharing supernet also shows a tendency towards non-parametric operations, resulting in shallow architectures with degenerated performance. We provide both theoretical and empirical analysis of the poor generalization observed in Differentiable NAS, which links this issue to the failure of the magnitude-based selection. Following this inspiration, we discuss two lines of methods that greatly improve the effectiveness and robustness of Differentiable NAS: The first line proposes an alternative perturbation-based architecture selection that is shown to identify better architectures in the search space, whereas the second line aligns the architecture parameter with the strength of underlying operations. To complete the picture, an alternative paradigm to the differential architecture search (predictor-based NAS) is also presented.