24 citations · 86 across the 22 of their papers we have counts for
26 papers
A Resolution of the SS--RS--GD Inequalities
Binghui Peng
Yun, Sra, and Jadbabaie (COLT 2021, open question) conjectured the SS--RS--GD inequalities: for well-conditioned symmetric matrices , the operators , $W_{rs}…
The complexity of non-stationary reinforcement learning
Christos Papadimitriou, Binghui Peng
The problem of continual learning in the domain of reinforcement learning, often called non-stationary reinforcement learning, has been identified as an important challenge to the…
Memory-Query Tradeoffs for Randomized Convex Optimization
Xi Chen, Binghui Peng
We show that any randomized first-order algorithm which minimizes a -dimensional, -Lipschitz convex function over the unit ball must either use bits of memory or…
Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules
Xi Chen, Binghui Peng
We study the complexity of finding an approximate (pure) Bayesian Nash equilibrium in a first-price auction with common priors when the tie-breaking rule is part of the input. We s…
Near Optimal Memory-Regret Tradeoff for Online Learning
Binghui Peng, Aviad Rubinstein
In the experts problem, on each of days, an agent needs to follow the advice of one of ``experts''. After each day, the loss associated with each expert's advice is reveale…
Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window)
Binghui Peng, Aviad Rubinstein
Dynamic algorithms come in three main flavors: (insertions-only), (deletions-only), or (both inser…
Online Prediction in Sub-linear Space
Binghui Peng, Fred Zhang
We provide the first sub-linear space and sub-linear regret algorithm for online learning with expert advice (against an oblivious adversary), addressing an open question raised re…
Memory Bounds for Continual Learning
Xi Chen, Christos Papadimitriou, Binghui Peng
Continual learning, or lifelong learning, is a formidable current challenge to machine learning. It requires the learner to solve a sequence of different learning tasks, one af…
Continual learning: a feature extraction formalization, an efficient algorithm, and fundamental obstructions
Binghui Peng, Andrej Risteski
Continual learning is an emerging paradigm in machine learning, wherein a model is exposed in an online fashion to data from multiple different distributions (i.e. environments), a…
The Complexity of Dynamic Least-Squares Regression
Shunhua Jiang, Binghui Peng, Omri Weinstein
We settle the complexity of dynamic least-squares regression (LSR), where rows and labels can be adaptively inserted and/or deleted, and the…
On the Complexity of Dynamic Submodular Maximization
Xi Chen, Binghui Peng
We study dynamic algorithms for the problem of maximizing a monotone submodular function over a stream of insertions and deletions. We show that any algorithm that maintains a…
Dynamic Influence Maximization
Binghui Peng
We initiate a systematic study on (DIM). In the DIM problem, one maintains a seed set of at most nodes in a…
Public Goods Games in Directed Networks
Christos Papadimitriou, Binghui Peng
Public goods games in undirected networks are generally known to have pure Nash equilibria, which are easy to find. In contrast, we prove that, in directed networks, a broad range…
Computational Hardness of the Hylland-Zeckhauser Scheme
Thomas Chen, Xi Chen, Binghui Peng +1
We study the complexity of the classic Hylland-Zeckhauser scheme [HZ'79] for one-sided matching markets. We show that the problem of finding an -approximate equilibrium in the H…
Shuffle Private Stochastic Convex Optimization
Albert Cheu, Matthew Joseph, Jieming Mao +1
In shuffle privacy, each user sends a collection of randomized messages to a trusted shuffler, the shuffler randomly permutes these messages, and the resulting shuffled collection…
Self-Attention Networks Can Process Bounded Hierarchical Languages
Shunyu Yao, Binghui Peng, Christos Papadimitriou +1
Despite their impressive performance in NLP, self-attention networks were recently proved to be limited for processing formal languages with hierarchical structure, such as $\maths…
MixCon: Adjusting the Separability of Data Representations for Harder Data Recovery
Xiaoxiao Li, Yangsibo Huang, Binghui Peng +2
To address the issue that deep neural networks (DNNs) are vulnerable to model inversion attacks, we design an objective function, which adjusts the separability of the hidden data…
Training (Overparametrized) Neural Networks in Near-Linear Time
Jan van den Brand, Binghui Peng, Zhao Song +1
The slow convergence rate and pathological curvature issues of first-order gradient methods for training deep neural networks, initiated an ongoing effort for developing faster $\m…
Hedging in games: Faster convergence of external and swap regrets
Xi Chen, Binghui Peng
We consider the setting where players run the Hedge algorithm or its optimistic variant to play an -action game repeatedly for rounds. 1) For two-player games, we show that…
Adaptive Greedy versus Non-adaptive Greedy for Influence Maximization
Wei Chen, Binghui Peng, Grant Schoenebeck +1
We consider the *adaptive influence maximization problem*: given a network and a budget , iteratively select seeds in the network to maximize the expected number of adopters…
On Adaptivity Gaps of Influence Maximization under the Independent Cascade Model with Full Adoption Feedback
Wei Chen, Binghui Peng
In this paper, we study the adaptivity gap of the influence maximization problem under independent cascade model when full-adoption feedback is available. Our main results are to d…
Adaptive Influence Maximization with Myopic Feedback
Binghui Peng, Wei Chen
We study the adaptive influence maximization problem with myopic feedback under the independent cascade model: one sequentially selects k nodes as seeds one by one from a social ne…
Stochastic Online Metric Matching
Anupam Gupta, Guru Guruganesh, Binghui Peng +1
We study the minimum-cost metric perfect matching problem under online i.i.d arrivals. We are given a fixed metric with a server at each of the points, and then requests arrive onl…
Tight Bounds for Online Edge Coloring
Ilan Reuven Cohen, Binghui Peng, David Wajc
Vizing's celebrated theorem asserts that any graph of maximum degree admits an edge coloring using at most colors. In contrast, Bar-Noy, Naor and Motwani showed over a qu…