UCLA

This thesis explores the development of efficient algorithms for managing partial information in complex systems, focusing on two key areas: Graph Neural Networks (GNNs) and Bandit Problems. In an era where the boundaries between physical and digital realms are rapidly blurring, these seemingly disparate fields have emerged as integral components in addressing the challenges of modern interconnected systems. The research journey begins with investigations into blind demixing for Internet-of-Things applications, naturally progressing to explorations in nonconvex optimization and high-dimensional statistical analysis. This foundation serves as a springboard for novel contributions in GNNs and Bandit Problems, addressing the pressing need for robust, scalable, and intelligent algorithms capable of handling the complexity of data-driven applications in our increasingly connected world.

The work introduces a Global Neighborhood Sampling algorithm for efficient GNN training on giant graphs, specifically optimized for mixed CPU-GPU hardware setups. This innovation significantly reduces data movement between CPU and GPU, leading to substantial performance improvements over existing state-of-the-art sampling methods. Building on this, the thesis presents G-RAG, a graph-based reranking approach for Retrieval Augmented Generation systems. GRAG leverages both the connections between retrieved documents and their semantic information, providing a context-informed reranker that outperforms current methods while maintaining a smaller computational footprint.

Delving into the realm of bandit problems, the thesis explores sparse bandit learning with misspecified linear features. This investigation provides valuable insights into how structural assumptions can aid in misspecified bandit learning, demonstrating that algorithms can obtain near-optimal actions by querying a number of actions that scale exponentially with the sparsity parameter rather than the ambient dimension. Furthermore, the research presents a novel featuremapping framework for solving Markov Decision Processes with delayed feedback, where the agent’s observations are delayed by multiple time steps. By carefully addressing the statistical challenges introduced by overlapping action sequences, this approach achieves a regret bound that is independent of the size of the state and action spaces.

The thesis also develops an online stochastic gradient descent (SGD)-based algorithm for stochastic bandit problems with general parametric reward functions. This method employs an action-elimination strategy and a uniform action-selection approach, providing high-probability regret guarantees and effectively handling the bias introduced by greedy action selection. This contribution extends the applicability of bandit algorithms to a broader class of problems with complex reward structures.

Throughout the research, a common thread emerges: the importance of understanding and leveraging the inherent structure in complex systems. This realization serves as a bridge between the work on GNNs and bandit problems, highlighting their complementary nature in modeling and decision-making within large-scale, interconnected systems. The synthesis of these areas leads to novel insights and methodologies with the potential to impact a wide range of applications, from improving recommendation systems and enhancing financial modeling to optimizing large-scale infrastructure networks and advancing human-AI interaction. This thesis stands at the intersection of several critical domains in computer science and applied mathematics, building upon foundational work in optimization, statistical learning, and network analysis while addressing the pressing needs of emerging technologies in AI and IoT. By bridging theoretical and empirical perspectives, the research advances the state-of-the-art in efficient algorithms for partial information management. The developed techniques not only push the boundaries of our understanding but also offer practical solutions to real-world challenges in managing and leveraging partial information in complex systems.

In conclusion, this work contributes to the development of more robust, scalable, and intelligent systems capable of navigating the complexities of our data-driven world. As we continue to face challenges in areas such as large-scale graph learning, decision-making under uncertainty, and human-AI interaction, the algorithms and insights presented in this thesis pave the way for future advancements in the field, offering a foundation for more adaptive and efficient approaches to partial information management in the ever-evolving landscape of interconnected systems.