Author name cluster

Shouyuan Chen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

UAI Conference 2015 Conference Paper

Fast Relative-Error Approximation Algorithm for Ridge Regression

Shouyuan Chen
Yang Liu 0003
Michael R. Lyu
Irwin King
Shengyu Zhang 0002

Ridge regression is one of the most popular and effective regularized regression methods, and one case of particular interest is that the number of features p is much larger than the number of samples n, i. e. p n. In this case, the standard optimization algorithm for ridge regression computes the optimal solution x⇤ in O(n2 p + n3 ) time. In this paper, we propose a fast relativeerror approximation algorithm for ridge regression. More specifically, our algorithm outputs a solution x̃ satisfying kx̃ x⇤ k2  ✏kx⇤ k2 with high probability and runs in Õ(nnz(A) + n3 /✏2 ) time, where nnz(A) is the number of non-zero entries of matrix A. To the best of our knowledge, this is the first algorithm for ridge regression that runs in o(n2 p) time with provable relative-error approximation bound on the output vector. In addition, we analyze the risk inflation bound of our algorithm and apply our techniques to two generalizations of ridge regression, including multiple response ridge regression and a non-linear ridge regression problem. Finally, we show empirical results on both synthetic and real datasets.

Details

NeurIPS Conference 2014 Conference Paper

Combinatorial Pure Exploration of Multi-Armed Bandits

Shouyuan Chen
Tian Lin
Irwin King
Michael Lyu
Wei Chen

We study the {\em combinatorial pure exploration (CPE)} problem in the stochastic multi-armed bandit setting, where a learner explores a set of arms with the objective of identifying the optimal member of a \emph{decision class}, which is a collection of subsets of arms with certain combinatorial structures such as size-$K$ subsets, matchings, spanning trees or paths, etc. The CPE problem represents a rich class of pure exploration tasks which covers not only many existing models but also novel cases where the object of interest has a non-trivial combinatorial structure. In this paper, we provide a series of results for the general CPE problem. We present general learning algorithms which work for all decision classes that admit offline maximization oracles in both fixed confidence and fixed budget settings. We prove problem-dependent upper bounds of our algorithms. Our analysis exploits the combinatorial structures of the decision classes and introduces a new analytic tool. We also establish a general problem-dependent lower bound for the CPE problem. Our results show that the proposed algorithms achieve the optimal sample complexity (within logarithmic factors) for many decision classes. In addition, applying our results back to the problems of top-$K$ arms identification and multiple bandit best arms identification, we recover the best available upper bounds up to constant factors and partially resolve a conjecture on the lower bounds.

PDF Details

NeurIPS Conference 2013 Conference Paper

Exact and Stable Recovery of Pairwise Interaction Tensors

Shouyuan Chen
Michael Lyu
Irwin King
Zenglin Xu

Tensor completion from incomplete observations is a problem of significant practical interest. However, it is unlikely that there exists an efficient algorithm with provable guarantee to recover a general tensor from a limited number of observations. In this paper, we study the recovery algorithm for pairwise interaction tensors, which has recently gained considerable attention for modeling multiple attribute data due to its simplicity and effectiveness. Specifically, in the absence of noise, we show that one can exactly recover a pairwise interaction tensor by solving a constrained convex program which minimizes the weighted sum of nuclear norms of matrices from $O(nr\log^2(n))$ observations. For the noisy cases, we also prove error bounds for a constrained convex program for recovering the tensors. Our experiments on the synthetic dataset demonstrate that the recovery performance of our algorithm agrees well with the theory. In addition, we apply our algorithm on a temporal collaborative filtering task and obtain state-of-the-art results.

PDF Details