Novel Methodologies in Network Analysis, Adversarial Learning, and Bandit Problems

Statistics and machine learning are extensively utilized and widely favored across numerous domains for their ability to offer valuable insights into relationships between objects of interest and to make accurate predictions. This dissertation focuses on three key areas within statistics and machine learning: network analysis, adversarial learning, and bandit problems, exploring fundamental challenges and proposing novel solutions in each domain. Firstly, we introduce NetOTC (Network Optimal Transition Coupling), a transport-based method for the comparison and alignment of two networks. Given two networks and a cost function relating their vertices, NetOTC finds a transition coupling of their associated random walks having minimum expected cost. The minimizing cost quantifies the difference between the networks, while the optimal transport plan itself provides alignments of both the vertices and the edges of the two networks. We investigate a number of theoretical properties of NetOTC and present experiments establishing its empirical performance. The second part of this dissertation focuses on adversarial learning, exploring the geometry of the data manifold. While adversarial training has proven effective in improving the robustness of deep neural networks against adversarial attacks, it often leads to a substantial drop in accuracy on clean data. To address this trade-off, we propose a novel approach called Tangent Direction Guided Adversarial Training (TART). We argue that training with adversarial examples with large normal components significantly distorts the decision boundary, resulting in reduced accuracy. TART overcomes this challenge by estimating the tangent direction of adversarial examples and adaptively adjusting the perturbation limit based on the norm of their tangential component. Lastly, bandit problems are a fundamental setting in online learning, where a learner makes sequential decisions to maximize cumulative rewards. This dissertation explores two previously unaddressed bandit problems. The first is the dueling bandit problem with stochastic delayed feedback. Real-world applications frequently face unavoidable stochastic delays in feedback, presenting significant challenges for existing dueling bandit algorithms. To address this, we propose two delay-resilient algorithms. The second is the Quantum Lipschitz Bandit problem, where the expected reward function satisfies a Lipschitz condition over an arm metric space. Motivated by advances in quantum computing and the success of quantum Monte Carlo methods, we introduce the first quantum Lipschitz bandit algorithms. Extensive experiments validate our theoretical improvements, showcasing the superior performance of our methods.