Publications

Matroid Semi-Bandits in Sublinear Time

Ruo-Chun Tzeng, Naoto Ohsaka, Kaito Ariu
International Conference on Machine Learning (ICML), 2024
paper
Summary: Existing algorithms have per-round time complexity at least $\Omega(K)$. We propose FasterCUCB whose sampling rule takes time sublinear in $K$ for common classes of matroids: $\mathcal{O}(D\,\text{polylog}(K,T))$ for uniform matroids, partition matroids, and graphical matroids, and $\mathcal{O}(D\sqrt{K}\text{polylog}(T))$ for transversal matroids, where $D$ is the rank of the matroid, and $T$ is the horizon. Our technique is based on dynamic maintenance of an approximate maximum-weight basis over inner-product weights.

Ruo-Chun Tzeng, Po-An Wang, Alexandre Proutiere, Chi-Jen Lu
Advances in Neural Information Processing Systems (NeurIPS), 2023
paper, code, poster, 5-min slides, 5-min talk
Summary: The proposed algorithm (P-FWS) is the first polynomial-time algorithm that achieves minimal sample complexity in high confidence regime and has polynomial sample complexity in moderate confidence regime. Its designed is based on:
$\,\,$ (i) A structural property discovered in the Lagrangian dual function associated with the sample complexity lowerbound $T^{\star}(\mu)$;
$\,\,$ (ii) Such structural property allows us to design an efficient but non-standard two-player algorithm (MCP) to solve the inner optimization of $T^{\star}(\mu)$;
$\,\,$ (iii) The outer optimization of $T^{\star}(\mu)$ is solved by stochastic smoothed FW-based algorithm whose required gradients are estimated only by using the linear maximization.

Ruo-Chun Tzeng, Po-An Wang, Florian Adriaens, Aristides Gionis, and Chi-Jen Lu
International Conference on Artificial Intelligence and Statistics (AISTATS), 2022
paper, code, slides, poster, video
Summary: (i) sharpened analysis of Randomized SVD for top-1 eigenvector (especially under $o(\ln n)$ passes) for PSD matrices and for indefinite matrices (under some additional assumptions); (ii) found that mixing 0/1 Bernoulli with Gaussian distribution in random projection is useful for conflicting group detection
Typo: On Page 6 (the 2nd-last line), $S \sim Bernoulli(p)^{n\times d}$ should be $S \sim \mathcal{N}(0,1)^{n\times d}$
Presented on Conference on the Mathematics of Complex Data 2022 and KTH ML Day 2023

Po-An Wang, Ruo-Chun Tzeng, and Alexandre Proutiere
Advances in Neural Information Processing Systems (NeurIPS), 2021
paper, code, slides
Summary: (i) proposed a simple algorithm (Frank-Wolfe Sampling) achieving minimal sample complexity asymptotically ($\delta\to0$) for many pure exploration tasks under various structures; (ii) derived the first non-asymptotic sample complexity upper bound with explict dependence on task-specific parameters
Presented by Po-An on Conference on the Mathematics of Complex Data 2022

Ruo-Chun Tzeng, Bruno Ordozgoiti, and Aristides Gionis
Advances in Neural Information Processing Systems (NeurIPS), 2020
paper, code, slides, poster, 2min talk
Summary: (i) decomposed the task of $k$-conflicting group detection into subproblems of QP-Ratio variants (by spectral graph theory); (ii) designed a provable eigenvector-based algorithm for a QP-Ratio variant
Presented on KTH ML Day 2022

Ruo-Chun Tzeng, and Shan-Hung Wu
International Conference on Machine Learning (ICML), 2019
paper, code, slides
Summary: (i) designed an interpretable model for graph supervised learning; (ii) empirically showed that weight-tying technique helps detect scale-free patterns