Author name cluster

Mingyang Deng

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.

6 papers

2 author rows

NeurIPS Conference 2025 Conference Paper

Mean Flows for One-step Generative Modeling

Zhengyang Geng
Mingyang Deng
Xingjian Bai
Zico Kolter
Kaiming He

We propose a principled and effective framework for one-step generative modeling. We introduce the notion of average velocity to characterize flow fields, in contrast to instantaneous velocity modeled by Flow Matching methods. A well-defined identity between average and instantaneous velocities is derived and used to guide neural network training. Our method, termed the \textit{MeanFlow} model, is self-contained and requires no pre-training, distillation, or curriculum learning. MeanFlow demonstrates strong empirical performance: it achieves an FID of 3. 43 with a single function evaluation (1-NFE) on ImageNet 256$\times$256 trained from scratch, significantly outperforming previous state-of-the-art one-step diffusion/flow models. Our study substantially narrows the gap between one-step diffusion/flow models and their multi-step predecessors, and we hope it will motivate future research to revisit the foundations of these powerful models.

PDF Details

NeurIPS Conference 2024 Conference Paper

Autoregressive Image Generation without Vector Quantization

Tianhong Li
Yonglong Tian
He Li
Mingyang Deng
Kaiming He

Conventional wisdom holds that autoregressive models for image generation are typically accompanied by vector-quantized tokens. We observe that while a discrete-valued space can facilitate representing a categorical distribution, it is not a necessity for autoregressive modeling. In this work, we propose to model the per-token probability distribution using a diffusion procedure, which allows us to apply autoregressive models in a continuous-valued space. Rather than using categorical cross-entropy loss, we define a Diffusion Loss function to model the per-token probability. This approach eliminates the need for discrete-valued tokenizers. We evaluate its effectiveness across a wide range of cases, including standard autoregressive models and generalized masked autoregressive (MAR) variants. By removing vector quantization, our image generator achieves strong results while enjoying the speed advantage of sequence modeling. We hope this work will motivate the use of autoregressive generation in other continuous-valued domains and applications. Code is available at https: //github. com/LTH14/mar.

PDF Details DOI

SODA Conference 2023 Conference Paper

Approximating Knapsack and Partition via Dense Subset Sums

Mingyang Deng
Ce Jin 0001
Xiao Mao

Knapsack and Partition are two important additive problems whose fine-grained complexities in the (1 — ε)-approximation setting are not yet settled. In this work, we make progress on both problems by giving improved algorithms. • Knapsack can be (1 — ε)-approximated in Õ ( n + (1/ε) 2. 2 ) time, improving the previous Õ ( n + (1/ε) 2. 25 ) by Jin (ICALP'19). There is a known conditional lower bound of ( n + 1/ε) 2- ο (1) based on (min, +)- convolution hypothesis. • Partition can be (1 — ε)-approximated in Õ ( n + (1/ε) 1. 25 ) time, improving the previous Õ ( n + (1/ε) 1. 5 ) by Bringmann and Nakos (SODA'21). There is a known conditional lower bound of (1/ε) 1- ο (1) based on Strong Exponential Time Hypothesis. Both of our new algorithms apply the additive combinatorial results on dense subset sums by Galil and Margalit (SICOMP'91), Bringmann and Wellnitz (SODA'21). Such techniques have not been explored in the context of Knapsack prior to our work. In addition, we design several new methods to speed up the divide-and-conquer steps which naturally arise in solving additive problems.

Details

SODA Conference 2023 Conference Paper

On Problems Related to Unbounded SubsetSum: A Unified Combinatorial Approach

Mingyang Deng
Xiao Mao
Ziqian Zhong

Unbounded SubsetSum is a classical textbook problem: given integers w 1, w 2, …, w n ∈[1, u ], c, u, we need to find if there exists m 1, m 2, …, m n ∈ ℕ satisfying c =Σ n i=1 w i m i. In its all-target version, t ∈ ℤ + is given and the answers for all integers c ∈ [0, t ] are required. In this paper, we study three generalizations of this simple problem: All-Target Unbounded Knapsack, All-Target CoinChange and Residue Table. With new combinatorial insights into the structures of solutions, we present a novel two-phase approach. As a result, we show that: • All-Target CoinChange can be solved in Õ ( u + t ) time deterministically, improving the previous Õ ( t 4/3 ) time algorithm [Chan and He, ESA 2020]. • Residue Table can be solved in Õ ( u ) time deterministically, improving the previous Õ ( u 3/2 ) time algorithm [Klein, 2021]. •All-Target Unbounded Knapsack can be solved in Õ(T(u) + t) time, where is the running time for (min, +) convolution for length- n arrays, improving the previous O ( u 2 log u + t ) time algorithm [Chan and He, ESA 2020].

Details

NeurIPS Conference 2023 Conference Paper

Restart Sampling for Improving Generative Processes

Yilun Xu
Mingyang Deng
Xiang Cheng
Yonglong Tian
Ziming Liu
Tommi Jaakkola

Generative processes that involve solving differential equations, such as diffusion models, frequently necessitate balancing speed and quality. ODE-based samplers are fast but plateau in performance while SDE-based samplers deliver higher sample quality at the cost of increased sampling time. We attribute this difference to sampling errors: ODE-samplers involve smaller discretization errors while stochasticity in SDE contracts accumulated errors. Based on these findings, we propose a novel sampling algorithm called \textit{Restart} in order to better balance discretization errors and contraction. The sampling method alternates between adding substantial noise in additional forward steps and strictly following a backward ODE. Empirically, Restart sampler surpasses previous SDE and ODE samplers in both speed and accuracy. Restart not only outperforms the previous best SDE results, but also accelerates the sampling speed by 10-fold / 2-fold on CIFAR-10 / ImageNet $64{\times} 64$. In addition, it attains significantly better sample quality than ODE samplers within comparable sampling times. Moreover, Restart better balances text-image alignment/visual quality versus diversity than previous samplers in the large-scale text-to-image Stable Diffusion model pre-trained on LAION $512{\times} 512$. Code is available at https: //github. com/Newbeeer/diffusion_restart_sampling

PDF Details

MFCS Conference 2022 Conference Paper

New Lower Bounds and Upper Bounds for Listing Avoidable Vertices

Mingyang Deng
Virginia Vassilevska Williams
Ziqian Zhong

We consider the problem of listing all avoidable vertices in a given n vertex graph. A vertex is avoidable if every pair of its neighbors is connected by a path whose internal vertices are not neighbors of the vertex or the vertex itself. Recently, Papadopolous and Zisis showed that one can list all avoidable vertices in O(n^{ω+1}) time, where ω < 2. 373 is the square matrix multiplication exponent, and conjectured that a faster algorithm is not possible. In this paper we show that under the 3-OV Hypothesis, and thus the Strong Exponential Time Hypothesis, n^{3-o(1)} time is needed to list all avoidable vertices, and thus the current best algorithm is conditionally optimal if ω = 2. We then show that if ω > 2, one can obtain an improved algorithm that for the current value of ω runs in O(n^3. 32) time. We also show that our conditional lower bound is actually higher and supercubic, under a natural High Dimensional 3-OV hypothesis, implying that for our current knowledge of rectangular matrix multiplication, the avoidable vertex listing problem likely requires Ω(n^3. 25) time. We obtain further algorithmic improvements for sparse graphs and bounded degree graphs.

Details