Efficient Learning in Graphs and in Combinatorial Multi-Armed Bandits

QC 20241107

Abstract

Graphs have rich structures at both local and global scales. By exploiting structural properties in certain graph problems, it is possible to design computationally efficient algorithms or refine performance analysis. This thesis is divided into two parts: (i) designing new methods for discovering structure from graphs and (ii) studying the interplay between graphs and combinatorial multi-arm bandits. They differ in how structures are defined, discovered, and utilized. In part (i), we start with a graph-mining problem on signed networks [TOG20], where the graph patterns we aim to detect are groups with mostly positive intragroup edges and mostly negative inter-group edges. We design our objective such that, given a solution, it reflects how well that solution matches the desired pattern. Our proposed algorithm makes no assumptions about the graph. It demonstrates competitive empirical performance in real-world graphs and synthetic graphs. The performance evaluation is conducted through a worst-case analysis, approximating the optimal solution. Moreover, we extend our conflicting group detection [BGG+19, TOG20] as well as other graph-mining tasks (such as fair densest-subgraph detection [ABF+20], two-community detection [New06]) to a memory-limited and pass-limited setting. Under such a setting, Randomized SVD, which has been proposed by [HMT11], is the most preferable method in the memory-limited and pass-limited setting. However, for an input matrix of size n °ø n, it has no guarantee in the o(ln n)-pass regime, which is of most interest to practitioners. We hence derive a tighter analysis [TWA+22] for Randomized SVD for positive semi-definite matrices in any number of passes and for indefinite matrices under certain conditions. Furthermore, we initiate the study of a mixture of Johnson-Lindenstrauss distribution and the 0/1 Bernoulli distribution. We show that this mixture helps make the detection of 2-conflicting groups [BGG+19]

more efficient. In part (ii), we study combinatorial multi-arm bandits problems, where the graph properties play important roles but are somewhat hidden in the optimization problem. Instead, one derives the fundamental limit bounds on either the expected sample complexity or the expected cumulative regret, typically in the informationtheoretical sense, and then explores the abstract properties associated with those bounds to solve the problem satisfactorily, either statistically or computationally.

We focus on combiantorial semi-bandits where the learner observes individual feedbacks for each arm part of the selection. This formulation models many real-world problems, including online ranking [DKC21] in recommendation systems, network routing [CLK+14] in internet service providers, loan assignment [KWA+14], path planning [JMKK21], and influence marketing [Per22]. For best arm identification with fixed confidence, we propose the first polynomial-time algorithm whose sample complexity is instance-specifically optimal in high confidence regime and has polynomial dependency on the number of arms in moderate confidence regime. For regret minimization, we propose the first algorithm whose per-round time complexity is sublinear in the number of arms while matching the instance-specifically gap-dependent lower bound asymptotically.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-355999