Author name cluster

Yu Cheng 0002

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.

7 papers

1 author row

ICML Conference 2023 Conference Paper

Hiding Data Helps: On the Benefits of Masking for Sparse Coding

Muthu Chidambaram
Chenwei Wu 0002
Yu Cheng 0002
Rong Ge 0001

Sparse coding, which refers to modeling a signal as sparse linear combinations of the elements of a learned dictionary, has proven to be a successful (and interpretable) approach in applications such as signal processing, computer vision, and medical imaging. While this success has spurred much work on provable guarantees for dictionary recovery when the learned dictionary is the same size as the ground-truth dictionary, work on the setting where the learned dictionary is larger (or $\textit{over-realized}$) with respect to the ground truth is comparatively nascent. Existing theoretical results in this setting have been constrained to the case of noise-less data. We show in this work that, in the presence of noise, minimizing the standard dictionary learning objective can fail to recover the elements of the ground-truth dictionary in the over-realized regime, regardless of the magnitude of the signal in the data-generating process. Furthermore, drawing from the growing body of work on self-supervised learning, we propose a novel masking objective for which recovering the ground-truth dictionary is in fact optimal as the signal increases for a large class of data-generating processes. We corroborate our theoretical results with experiments across several parameter regimes showing that our proposed objective also enjoys better empirical performance than the standard reconstruction objective.

Details

ICLR Conference 2021 Conference Paper

Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time

Yu Cheng 0002
Honghao Lin

We study the problem of learning Bayesian networks where an $\epsilon$-fraction of the samples are adversarially corrupted. We focus on the fully-observable case where the underlying graph structure is known. In this work, we present the first nearly-linear time algorithm for this problem with a dimension-independent error guarantee. Previous robust algorithms with comparable error guarantees are slower by at least a factor of $(d/\epsilon)$, where $d$ is the number of variables in the Bayesian network and $\epsilon$ is the fraction of corrupted samples. Our algorithm and analysis are considerably simpler than those in previous work. We achieve this by establishing a direct connection between robust learning of Bayesian networks and robust mean estimation. As a subroutine in our algorithm, we develop a robust mean estimation algorithm whose runtime is nearly-linear in the number of nonzeros in the input samples, which may be of independent interest.

Details

ICML Conference 2020 Conference Paper

High-dimensional Robust Mean Estimation via Gradient Descent

Yu Cheng 0002
Ilias Diakonikolas
Rong Ge 0001
Mahdi Soltanolkotabi

We study the problem of high-dimensional robust mean estimation in the presence of a constant fraction of adversarial outliers. A recent line of work has provided sophisticated polynomial-time algorithms for this problem with dimension-independent error guarantees for a range of natural distribution families. In this work, we show that a natural non-convex formulation of the problem can be solved directly by gradient descent. Our approach leverages a novel structural lemma, roughly showing that any approximate stationary point of our non-convex objective gives a near-optimal solution to the underlying robust estimation task. Our work establishes an intriguing connection between algorithmic high-dimensional robust statistics and non-convex optimization, which may have broader applications to other robust estimation tasks.

Details

SODA Conference 2019 Conference Paper

High-Dimensional Robust Mean Estimation in Nearly-Linear Time

Yu Cheng 0002
Ilias Diakonikolas
Rong Ge 0001

We study the fundamental problem of high-dimensional mean estimation in a robust model where a constant fraction of the samples are adversarially corrupted. Recent work gave the first polynomial time algorithms for this problem with dimension-independent error guarantees for several families of structured distributions. In this work, we give the first nearly-linear time algorithms for high-dimensional robust mean estimation. Specifically, we focus on distributions with (i) known covariance and sub-gaussian tails, and (ii) unknown bounded covariance. Given N samples on ℝ d, an ∊ -fraction of which may be arbitrarily corrupted, our algorithms run in time Õ ( Nd )/poly( ∊ ) and approximate the true mean within the information-theoretically optimal error, up to constant factors. Previous robust algorithms with comparable error guarantees have running times, for ∊ = Ω(1). Our algorithms rely on a natural family of SDPs parameterized by our current guess v for the unknown mean µ *. We give a win-win analysis establishing the following: either a near-optimal solution to the primal SDP yields a good candidate for µ * — independent of our current guess v — or a near-optimal solution to the dual SDP yields a new guess v’ whose distance from µ * is smaller by a constant factor. We exploit the special structure of the corresponding SDPs to show that they are approximately solvable in nearly-linear time. Our approach is quite general, and we believe it can also be applied to obtain nearly-linear time algorithms for other high-dimensional robust learning problems.

Details

ICML Conference 2019 Conference Paper

When Samples Are Strategically Selected

Hanrui Zhang 0001
Yu Cheng 0002
Vincent Conitzer

In standard classification problems, the assumption is that the entity making the decision (the principal ) has access to all the samples. However, in many contexts, she either does not have direct access to the samples, or can inspect only a limited set of samples and does not know which are the most relevant ones. In such cases, she must rely on another party (the agent ) to either provide the samples or point out the most relevant ones. If the agent has a different objective, then the principal cannot trust the submitted samples to be representative. She must set a policy for how she makes decisions, keeping in mind the agent’s incentives. In this paper, we introduce a theoretical framework for this problem and provide key structural and computational results.

Details

SODA Conference 2017 Conference Paper

Playing Anonymous Games using Simple Strategies

Yu Cheng 0002
Ilias Diakonikolas
Alistair Stewart

We investigate the complexity of computing approximate Nash equilibria in anonymous games. Our main algorithmic result is the following: For any n -player anonymous game with a bounded number of strategies and any constant δ > 0, an Ο(1/ n 1-δ )-approximate Nash equilibrium can be computed in polynomial time. Complementing this positive result, we show that if there exists any constant δ > 0 such that an Ο(1/ n 1+δ )- approximate equilibrium can be computed in polynomial time, then there is a fully polynomial-time approximation scheme (FPTAS) for this problem. We also present a faster algorithm that, for any n -player k -strategy anonymous game, runs in time Õ (( n + k ) kn k } and computes an Õ( n −1/3 k 11/3 )- approximate equilibrium. This algorithm follows from the existence of simple approximate equilibria of anonymous games, where each player plays one strategy with probability 1 — δ, for some small δ, and plays uniformly at random with probability δ. Our approach exploits the connection between Nash equilibria in anonymous games and Poisson multinomial distributions (PMDs). Specifically, we prove a new probabilistic lemma establishing the following: Two PMDs, with large variance in each direction, whose first few moments are approximately matching are close in total variation distance. Our structural result strengthens previous work by providing a smooth tradeoff between the variance bound and the number of matching moments.

Details

FOCS Conference 2015 Conference Paper

Mixture Selection, Mechanism Design, and Signaling

Yu Cheng 0002
Ho Yee Cheung
Shaddin Dughmi
Ehsan Emamjomeh-Zadeh
Li Han
Shang-Hua Teng

We pose and study a fundamental algorithmic problem which we term mixture selection, arising as a building block in a number of game-theoretic applications: Given a function g from the n-dimensional hypercube to the bounded interval [-1, 1], and an n × rn matrix A with bounded entries, maximize g(Ax) over x in the m-dimensional simplex. This problem arises naturally when one seeks to design a lottery over items for sale in an auction, or craft the posterior beliefs for agents in a Bayesian game through the provision of information (a. k. a. signaling). We present an approximation algorithm for this problem when g simultaneously satisfies two “smoothness” properties: Lipschitz continuity with respect to the L ∞ norm, and noise stability. The latter notion, which we define and cater to our setting, controls the degree to which low-probability - and possibly correlated - errors in the inputs of g can impact its output. The approximation guarantee of our algorithm degrades gracefully as a function of the Lipschitz continuity and noise stability of g. In particular, when g is both 0(1)-Lipschitz continuous and 0(1)-stable, we obtain an (additive) polynomial-time approximation scheme (PTAS) for mixture selection. We also show that neither assumption suffices by itself for an additive PTAS, and both assumptions together do not suffice for an additive fully polynomial-time approximation scheme (FPTAS). We apply our algorithm for mixture selection to a number of different game-theoretic applications, focusing on problems from mechanism design and optimal signaling. In particular, we make progress on a number of open problems suggested in prior work by easily reducing them to mixture selection: we resolve an important special case of the small-menu lottery design problem posed by Dughmi, Han, and Nisan [10]; we resolve the problem of revenue-maximizing signaling in Bayesian secondprice auctions posed by Emek et al. [12] and Miltersen and Sheffet [5]; we design a quasipolynomial-time approximation scheme for the optimal signaling problem in normal form games suggested by Dughmi [9]; and we design an approximation algorithm for the optimal signaling problem in the voting model of Alonso and Camara [3].

Details