6 papers
Decoder-only Clustering in Attributed Graphs
Yik Lun Kei, Oscar Hernan Madrid Padilla, Rebecca Killick +3
This manuscript studies nodal clustering in graphs having multivariate attributes at each node. The framework includes node-specific priors for low-dimensional representations, cou…
Quadratic Speedup for Computing Contraction Fixed Points
Xi Chen, Yuhao Li, Mihalis Yannakakis
We study the problem of finding an -fixed point of a contraction map under both the -norm and the -norm. For both norms, we give…
Constant Inapproximability of Pacing Equilibria in Second-Price Auctions
Xi Chen, Yuhao Li
In this paper, we revisit the problem of approximating a pacing equilibrium in second-price auctions, introduced by Conitzer, Kroer, Sodomka, and Moses [Oper. Res. 2022]. We show t…
Topological Federated Clustering via Gravitational Potential Fields under Local Differential Privacy
Yunbo Long, Jiaquan Zhang, Xi Chen +1
Clustering non-independent and identically distributed (non-IID) data under local differential privacy (LDP) in federated settings presents a critical challenge: preserving privacy…
A Unified Zeroth-Order Optimization Framework via Oblivious Randomized Sketching
Haishan Ye, Xiangyu Chang, Xi Chen
We propose a new framework for analyzing zeroth-order optimization (ZOO) from the perspective of \emph{oblivious randomized sketching}.In this framework, commonly used gradient est…
Computing a Fixed Point of Contraction Maps in Polynomial Queries
Xi Chen, Yuhao Li, Mihalis Yannakakis
We give an algorithm for finding an -fixed point of a contraction map under the -norm with query complexity .