Author name cluster

Xiangrui Meng

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.

8 papers

2 author rows

AAAI Conference 2024 Conference Paper

PMAC: Personalized Multi-Agent Communication

Xiangrui Meng
Ying Tan

Communication plays a crucial role in information sharing within the field of multi-agent reinforcement learning (MARL). However, how to transmit information that meets individual needs remains a long-standing challenge. Some existing work focus on using a common channel for information transfer, which limits the capability for local communication. Meanwhile, other work attempt to establish peer-to-peer communication topologies but suffer from quadratic complexity. In this paper, we propose Personalized Multi-Agent Communication (PMAC), which enables the formation of peer-to-peer communication topologies, personalized message sending, and personalized message receiving. All these modules in PMAC are performed using only multilayer perceptrons (MLPs) with linear computational complexity. Empirically, we show the strength of personalized communication in a variety of cooperative scenarios. Our approach exhibits competitive performance compared to existing methods while maintaining notable computational efficiency.

PDF Details DOI

AAMAS Conference 2023 Conference Paper

Learning Group-Level Information Integration in Multi-Agent Communication

Xiangrui Meng
Ying Tan

In multi-agent systems, it’s hard to make proper decisions for agents due to the partial observability of the environment. Among categories of multi-agent reinforcement learning (MARL) algorithms, communication learning is a common approach to solving this problem. However, existing work focus on individual-level communication which usually leads to significant communication costs. Meanwhile, the group feature couldn’t be well captured at the individual level. To tackle these problems, this paper proposes a group-level information integration model called Double Channel Communication Network (DC2Net). In DC2Net, individual and group features are learned in two independent channels. Agents no longer interact with each other at the individual level and all information interaction is carried out in the group channel. This model ensures effective learning of group features while reducing individual-level communication costs. Empirically, we conducted experiments on several environments and tasks. The experimental results show that the DC2Net not only has a better performance compared to other state-of-the-art MARL communication models but also reduces the costs of communication. Furthermore, it’s a natural communication topology with the ability in balancing individual and communication learning.

PDF

JMLR Journal 2016 Journal Article

MLlib: Machine Learning in Apache Spark

Xiangrui Meng
Joseph Bradley
Burak Yavuz
Evan Sparks
Shivaram Venkataraman
Davies Liu
Jeremy Freeman
DB Tsai

Apache Spark is a popular open-source platform for large-scale data processing that is well-suited for iterative machine learning tasks. In this paper we present MLlib, Spark's open- source distributed machine learning library. MLlib provides efficient functionality for a wide range of learning settings and includes several underlying statistical, optimization, and linear algebra primitives. Shipped with Spark, MLlib supports several languages and provides a high-level API that leverages Spark's rich ecosystem to simplify the development of end-to-end machine learning pipelines. MLlib has experienced a rapid growth due to its vibrant open-source community of over 140 contributors, and includes extensive documentation to support further growth and to let users quickly get up to speed. [abs] [ pdf ][ bib ] [ code ] [ webpage ] &copy JMLR 2016. ( edit, beta )

PDF Details

STOC Conference 2013 Conference Paper

Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression

Xiangrui Meng
Michael W. Mahoney

Low-distortion embeddings are critical building blocks for developing random sampling and random projection algorithms for common linear algebra problems. We show that, given a matrix A ∈ R n x d with n >> d and a p ∈ [1, 2), with a constant probability, we can construct a low-distortion embedding matrix Π ∈ R O(poly(d)) x n that embeds A p , the l p subspace spanned by A's columns, into (R O(poly(d)) , |~cdot~| p ); the distortion of our embeddings is only O(poly(d)), and we can compute Π A in O(nnz(A)) time, i.e., input-sparsity time. Our result generalizes the input-sparsity time l 2 subspace embedding by Clarkson and Woodruff [STOC'13]; and for completeness, we present a simpler and improved analysis of their construction for l 2 . These input-sparsity time l p embeddings are optimal, up to constants, in terms of their running time; and the improved running time propagates to applications such as (1 pm ε)-distortion l p subspace embedding and relative-error l p regression. For l 2 , we show that a (1+ε)-approximate solution to the l 2 regression problem specified by the matrix A and a vector b ∈ R n can be computed in O(nnz(A) + d 3 log(d/ε) /ε^2) time; and for l p , via a subspace-preserving sampling procedure, we show that a (1 pm ε)-distortion embedding of A p into R O(poly(d)) can be computed in O(nnz(A) ⋅ log n) time, and we also show that a (1+ε)-approximate solution to the l p regression problem min x ∈ R d |A x - b| p can be computed in O(nnz(A) ⋅ log n + poly(d) log(1/ε)/ε 2 ) time. Moreover, we can also improve the embedding dimension or equivalently the sample size to O(d 3+p/2 log(1/ε) / ε 2 ) without increasing the complexity.

Details

ICML Conference 2013 Conference Paper

Quantile Regression for Large-scale Applications

Jiyan Yang
Xiangrui Meng
Michael W. Mahoney

Quantile regression is a method to estimate the quantiles of the conditional distribution of a response variable, and as such it permits a much more accurate portrayal of the relationship between the response variable and observed covariates than methods such as Least-squares or Least Absolute Deviations regression. It can be expressed as a linear program, and interior-point methods can be used to find a solution for moderately large problems. Dealing with very large problems, \emphe. g. , involving data up to and beyond the terabyte regime, remains a challenge. Here, we present a randomized algorithm that runs in time that is nearly linear in the size of the input and that, with constant probability, computes a (1+ε) approximate solution to an arbitrary quantile regression problem. Our algorithm computes a low-distortion subspace-preserving embedding with respect to the loss function of quantile regression. Our empirical evaluation illustrates that our algorithm is competitive with the best previous work on small to medium-sized problems, and that it can be implemented in MapReduce-like environments and applied to terabyte-sized problems.

Details

ICML Conference 2013 Conference Paper

Robust Regression on MapReduce

Xiangrui Meng
Michael W. Mahoney

Although the MapReduce framework is now the \emphde facto standard for analyzing massive data sets, many algorithms (in particular, many iterative algorithms popular in machine learning, optimization, and linear algebra) are hard to fit into MapReduce. Consider, \emphe. g. , the \ell_p regression problem: given a matrix A ∈\mathbbR^m \times n and a vector b ∈\mathbbR^m, find a vector x^* ∈\mathbbR^n that minimizes f(x) = \|A x - b\|_p. The widely-used \ell_2 regression, \emphi. e. , linear least-squares, is known to be highly sensitive to outliers; and choosing p ∈[1, 2) can help improve robustness. In this work, we propose an efficient algorithm for solving strongly over-determined (m ≫n) robust \ell_p regression problems to moderate precision on MapReduce. Our empirical results on data up to the terabyte scale demonstrate that our algorithm is a significant improvement over traditional iterative algorithms on MapReduce for \ell_1 regression, even for a fairly small number of iterations. In addition, our proposed interior-point cutting-plane method can also be extended to solving more general convex problems on MapReduce.

Details

ICML Conference 2013 Conference Paper

Scalable Simple Random Sampling and Stratified Sampling

Xiangrui Meng

Analyzing data sets of billions of records has now become a regular task in many companies and institutions. In the statistical analysis of those massive data sets, sampling generally plays a very important role. In this work, we describe a scalable simple random sampling algorithm, named ScaSRS, which uses probabilistic thresholds to decide on the fly whether to accept, reject, or wait-list an item independently of others. We prove, with high probability, it succeeds and needs only O(\sqrtk) storage, where k is the sample size. ScaSRS extends naturally to a scalable stratified sampling algorithm, which is favorable for heterogeneous data sets. The proposed algorithms, when implemented in MapReduce, can effectively reduce the size of intermediate output and greatly improve load balancing. Empirical evaluation on large-scale data sets clearly demonstrates their superiority.

Details

SODA Conference 2013 Conference Paper

The Fast Cauchy Transform and Faster Robust Linear Regression

Kenneth L. Clarkson
Petros Drineas
Malik Magdon-Ismail
Michael W. Mahoney
Xiangrui Meng
David P. Woodruff

We provide fast algorithms for overconstrained ℓ p regression and related problems: for an n × d input matrix A and vector b ∊ ℝ n, in O ( nd log n ) time we reduce the problem min x ∊ ℝ d ‖ A x − b ‖ p to the same problem with input matrix A of dimension s × d and corresponding b of dimension s × 1. Here, Ã and are a coreset for the problem, consisting of sampled and rescaled rows of A and b; and s is independent of n and polynomial in d. Our results improve on the best previous algorithms when n ≫ d, for all p ∊ [1, ∞) except p = 2; in particular, they improve the O ( nd 1. 376+ ) running time of Sohler and Woodruff (STOC, 2011) for p = 1, that uses asymptotically fast matrix multiplication, and the O ( nd 5 log n ) time of Dasgupta et al. (SICOMP, 2009) for general p, that uses ellipsoidal rounding. We also provide a suite of improved results for finding well-conditioned bases via ellipsoidal rounding, illustrating tradeoffs between running time and conditioning quality, including a one-pass conditioning algorithm for general ℓ p problems. To complement this theory, we provide a detailed empirical evaluation of implementations of our algorithms for p = 1, comparing them with several related algorithms. Among other things, our empirical results clearly show that, in the asymptotic regime, the theory is a very good guide to the practical performance of these algorithms. Our algorithms use our faster constructions of well-conditioned bases for ℓ p spaces and, for p = 1, a fast subspace embedding of independent interest that we call the Fast Cauchy Transform: a matrix Π: ℝ n → ℝ O ( d log d ), found obliviously to A, that approximately preserves the ℓ 1 norms: that is, ‖ Ax ‖ 1 ≈ ‖Π A x ‖ 1, for all x, with distortion O ( d 2 + η log d ), for an arbitrarily small constant η > 0; and, moreover, ΠA can be computed in O ( nd log d ) time. The techniques underlying our Fast Cauchy Transform include fast Johnson-Lindenstrauss transforms, low-coherence matrices, and rescaling by Cauchy random variables.

Details