Author name cluster

Yang Cai

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.

11 papers

1 author row

NeurIPS Conference 2025 Conference Paper

A Unified Approach to Submodular Maximization Under Noise

Kshipra Bhawalkar
Yang Cai
Zhe Feng
Christopher Liaw
Tao Lin

We consider the problem of maximizing a submodular function with access to a _noisy_ value oracle for the function instead of an exact value oracle. Similar to prior work, we assume that the noisy oracle is persistent in that multiple calls to the oracle for a specific set always return the same value. In this model, Hassidim and Singer (2017) design a $(1-1/e)$-approximation algorithm for monotone submodular maximization subject to a cardinality constraint, and Huang et al (2022) design a $(1-1/e)/2$-approximation algorithm for monotone submodular maximization subject to any arbitrary matroid constraint. In this paper, we design a meta-algorithm that allows us to take any "robust" algorithm for exact submodular maximization as a black box and transform it into an algorithm for the noisy setting while retaining the approximation guarantee. By using the meta-algorithm with the measured continuous greedy algorithm, we obtain a $(1-1/e)$-approximation (resp. $1/e$-approximation) for monotone (resp. non-monotone) submodular maximization subject to a matroid constraint under noise. Furthermore, by using the meta-algorithm with the double greedy algorithm, we obtain a $1/2$-approximation for unconstrained (non-monotone) submodular maximization under noise.

PDF Details

EAAI Journal 2025 Journal Article

Cognitive Digital Twins of the natural environment: Framework and application

Jun Feng
Hailin Tang
Siyuan Zhou
Yang Cai
Jianxin Zhang

Digital Twin (DT) technology offers a method of creating digital models of natural systems to enhance their ability to withstand natural disasters. Currently, DT of the natural environment is in its initial phases, lacking adaptive capabilities and relying on human-assisted modeling. The key to endowing DT of the natural environment with greater autonomy lies in the integration of expert knowledge. Knowledge graphs can efficiently arrange and structurally store expert knowledge, thereby supporting the autonomous functionality of DT. This paper introduces the concept of Cognitive Digital Twin(CDT) derived from the industrial domain and presents a framework for CDT of the natural environment. This framework is centered around knowledge graph technology, aiming to provide more insights and guidance for system development. This framework integrates human cognition by constructing knowledge graphs of objects, models, events, and scene modes. Moreover, these knowledge graphs support agents for the dynamic adjustment of processes, as well as the adaptation and parameter optimization of related models. As a use case, we utilize this framework to implement digital twin watersheds. We develop appropriate ontologies and agents to facilitate the construction of cognitive digital watersheds for various regions. Cognitive digital watersheds effectively fulfill the application needs of integrated flood forecasting and control scheduling. This application validates the framework’s effectiveness and provides a reference for constructing CDTs of other natural systems.

Details DOI

JBHI Journal 2025 Journal Article

Diffusion Tensor Magnetic Resonance Image Registration Based on Parallel Dual-Channel VoxelMorph

Yi Wang
Shufan Geng
Haopeng Jia
Yang Cai
Zhe Guo
Yilong Niu
Asoke K. Nandi

Diffusion Tensor Magnetic Resonance Imaging (DTI) is a non-invasive technique for studying brain structure in vivo by measuring the diffusion properties of water molecules. Unlike conventional medical imaging that captures scalar intensity data, DTI data is typically stored as a 4D volume, where each voxel in 3D space is a 3×3 Cartesian tensor. DTI characterizes tensor-based diffusion profiles and captures information about the orientation of fiber bundles. During the alignment process, voxels need to be spatially transformed while maintaining the correspondence of tensor orientations, which leads to complex computations. Traditional DTI registration methods often suffer from slow iteration speed and low accuracy, posing challenges for clinical applications. In this paper, a novel DTI Registration method Based on Parallel Dual-channel Voxel Morph (DTI-RBPDV) is proposed. The core of the method is a two-branch convolutional neural network architecture. With a view to enhancing the alignment performance, it processes two input patterns simultaneously: (1) fractional anisotropy (FA) images and (2) principal eigenvectors from to-be-aligned and fixed DTI volumes to enhance the accuracy of deformation field prediction. In the network decoder layer, integration of attention mechanisms has also been implemented. These channel space attention modules dynamically highlight salient anatomical features and orientation consistency, improving the model's sensitivity to key structural alignments. Experimental results show that DTI-RBPDV effectively addresses the limitations of slow iterative computation and the challenges of applying deep learning to high-dimensional DTI data by significantly improving the registration accuracy and computational speed.

Details DOI

NeurIPS Conference 2025 Conference Paper

From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications

Yang Cai
Haipeng Luo
Chen-Yu Wei
Weiqiang Zheng

The convergence of online learning algorithms in games under self-play is a fundamental question in game theory and machine learning. Among various notions of convergence, last-iterate convergence is particularly desirable, as it reflects the actual decisions made by the learners and captures the day-to-day behavior of the learning dynamics. While many algorithms are known to converge in the average-iterate, achieving last-iterate convergence typically requires considerably more effort in both the design and the analysis of the algorithm. Somewhat surprisingly, we show in this paper that for a large family of games, there exists a simple black-box reduction that transforms the average iterates of an uncoupled learning dynamics into the last iterates of a new uncoupled learning dynamics, thus also providing a reduction from last-iterate convergence to average-iterate convergence. Our reduction applies to games where each player’s utility is linear in both their own strategy and the joint strategy of all opponents. This family includes two-player bimatrix games and generalizations such as multi-player polymatrix games. By applying our reduction to the Optimistic Multiplicative Weights Update algorithm, we obtain new state-of-the-art last-iterate convergence rates for uncoupled learning dynamics in multi-player zero-sum polymatrix games: (1) an $O(\frac{\log d}{T})$ last-iterate convergence rate under gradient feedback, representing an exponential improvement in the dependence on the dimension $d$ (i. e. , the maximum number of actions available to either player); and (2) an $\tilde{O}(d^{\frac{1}{5}}T^{-\frac{1}{5}})$ last-iterate convergence rate under bandit feedback, improving upon the previous best rates of $\tilde{O}(\sqrt{d}T^{-\frac{1}{8}})$ and $\tilde{O}(\sqrt{d}T^{-\frac{1}{6}})$.

PDF Details

NeurIPS Conference 2024 Conference Paper

Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms

Yang Cai
Gabriele Farina
Julien Grand-Clément
Christian Kroer
Chung-Wei Lee
Haipeng Luo
Weiqiang Zheng

Self play via online learning is one of the premier ways to solve large-scale zero-sum games, both in theory and practice. Particularly popular algorithms include optimistic multiplicative weights update (OMWU) and optimistic gradient-descent-ascent (OGDA). While both algorithms enjoy $O(1/T)$ ergodic convergence to Nash equilibrium in two-player zero-sum games, OMWU offers several advantages, including logarithmic dependence on the size of the payoff matrix and $\tilde{O}(1/T)$ convergence to coarse correlated equilibria even in general-sum games. However, in terms of last-iterate convergence in two-player zero-sum games, an increasingly popular topic in this area, OGDA guarantees that the duality gap shrinks at a rate of $(1/\sqrt{T})$, while the best existing last-iterate convergence for OMWU depends on some game-dependent constant that could be arbitrarily large. This begs the question: is this potentially slow last-iterate convergence an inherent disadvantage of OMWU, or is the current analysis too loose? Somewhat surprisingly, we show that the former is true. More generally, we prove that a broad class of algorithms that do not forget the past quickly all suffer the same issue: for any arbitrarily small $\delta>0$, there exists a $2\times 2$ matrix game such that the algorithm admits a constant duality gap even after $1/\delta$ rounds. This class of algorithms includes OMWU and other standard optimistic follow-the-regularized-leader algorithms.

PDF Details DOI

NeurIPS Conference 2024 Conference Paper

On Tractable $\Phi$-Equilibria in Non-Concave Games

Yang Cai
Constantinos Daskalakis
Haipeng Luo
Chen-Yu Wei
Weiqiang Zheng

While Online Gradient Descent and other no-regret learning procedures are known to efficiently converge to a coarse correlated equilibrium in games where each agent's utility is concave in their own strategy, this is not the case when utilities are non-concave -- a common scenario in machine learning applications involving strategies parameterized by deep neural networks, or when agents' utilities are computed by neural networks, or both. Non-concave games introduce significant game-theoretic and optimization challenges: (i) Nash equilibria may not exist; (ii) local Nash equilibria, though they exist, are intractable; and (iii) mixed Nash, correlated, and coarse correlated equilibria generally have infinite support and are intractable. To sidestep these challenges, we revisit the classical solution concept of $\Phi$-equilibria introduced by Greenwald and Jafari [GJ03], which is guaranteed to exist for an arbitrary set of strategy modifications $\Phi$ even in non-concave games [SL07]. However, the tractability of $\Phi$-equilibria in such games remains elusive. In this paper, we initiate the study of tractable $\Phi$-equilibria in non-concave games and examine several natural families of strategy modifications. We show that when $\Phi$ is finite, there exists an efficient uncoupled learning algorithm that approximates the corresponding $\Phi$-equilibria. Additionally, we explore cases where $\Phi$ is infinite but consists of local modifications, showing that Online Gradient Descent can efficiently approximate $\Phi$-equilibria in non-trivial regimes.

PDF Details DOI

NeurIPS Conference 2024 Conference Paper

Provable Partially Observable Reinforcement Learning with Privileged Information

Yang Cai
Xiangyu Liu
Argyris Oikonomou
Kaiqing Zhang

Partial observability of the underlying states generally presents significant challenges for reinforcement learning (RL). In practice, certain privileged information, e. g. , the access to states from simulators, has been exploited in training and achieved prominent empirical successes. To better understand the benefits of privileged information, we revisit and examine several simple and practically used paradigms in this setting, with both computation and sample efficiency analyses. Specifically, we first formalize the empirical paradigm of expert distillation (also known as teacher-student learning), demonstrating its pitfall in finding near-optimal policies. We then identify a condition of the partially observable environment, the deterministic filter condition, under which expert distillation achieves sample and computational complexities that are both polynomial. Furthermore, we investigate another successful empirical paradigm of asymmetric actor-critic, and focus on the more challenging setting of observable partially observable Markov decision processes. We develop a belief-weighted optimistic asymmetric actor-critic algorithm with polynomial sample and quasi-polynomial computational complexities, where one key component is a new provable oracle for learning belief states that preserve filter stability under a misspecified model, which may be of independent interest. Finally, we also investigate the provable efficiency of partially observable multi-agent RL (MARL) with privileged information. We develop algorithms with the feature of centralized-training-with-decentralized-execution, a popular framework in empirical MARL, with polynomial sample and (quasi-)polynomial computational complexity in both paradigms above. Compared with a few recent related theoretical studies, our focus is on understanding practically inspired algorithmic paradigms, without computationally intractable oracles.

PDF Details DOI

NeurIPS Conference 2023 Conference Paper

Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback

Yang Cai
Haipeng Luo
Chen-Yu Wei
Weiqiang Zheng

We revisit the problem of learning in two-player zero-sum Markov games, focusing on developing an algorithm that is *uncoupled*, *convergent*, and *rational*, with non-asymptotic convergence rates to Nash equilibrium. We start from the case of stateless matrix game with bandit feedback as a warm-up, showing an $\tilde{\mathcal{O}}(t^{-\frac{1}{8}})$ last-iterate convergence rate. To the best of our knowledge, this is the first result that obtains finite last-iterate convergence rate given access to only bandit feedback. We extend our result to the case of irreducible Markov games, providing a last-iterate convergence rate of $\tilde{\mathcal{O}}(t^{-\frac{1}{9+\varepsilon}})$ for any $\varepsilon>0$. Finally, we study Markov games without any assumptions on the dynamics, and show a *path convergence* rate, a new notion of convergence we defined, of $\tilde{\mathcal{O}}(t^{-\frac{1}{10}})$. Our algorithm removes the synchronization and prior knowledge requirement of Wei et al. (2021), which pursued the same goals as us for irreducible Markov games. Our algorithm is related to Chen et al. (2021) and Cen et al. (2021)'s and also builds on the entropy regularization technique. However, we remove their requirement of communications on the entropy values, making our algorithm entirely uncoupled.

PDF Details

NeurIPS Conference 2022 Conference Paper

Finite-Time Last-Iterate Convergence for Learning in Multi-Player Games

Yang Cai
Argyris Oikonomou
Weiqiang Zheng

We study the question of last-iterate convergence rate of the extragradient algorithm by Korpelevich [1976] and the optimistic gradient algorithm by Popov [1980] in multi-player games. We show that both algorithms with constant step-size have last-iterate convergence rate of $O(\frac{1}{\sqrt{T}})$ to a Nash equilibrium in terms of the gap function in smooth monotone games, where each player's action set is an arbitrary convex set. Previous results only study the unconstrained setting, where each player's action set is the entire Euclidean space. Our results address an open question raised in several recent work by Hsieh et al. [2019], Golowich et al. [2020a, b], who ask for last-iterate convergence rate of either the extragradient or the optimistic gradient algorithm in the constrained setting. Our convergence rates for both algorithms are tight and match the lower bounds by Golowich et al. [2020a, b]. At the core of our results lies a new notion -- the tangent residual, which we use to measure the proximity to equilibrium. We use the tangent residual (or a slight variation of the tangent residual) as the the potential function in our analysis of the extragradient algorithm (or the optimistic gradient algorithm) and prove that it is non-increasing between two consecutive iterates.

PDF Details

NeurIPS Conference 2018 Conference Paper

Learning Safe Policies with Expert Guidance

Jessie Huang
Fa Wu
Doina Precup
Yang Cai

We propose a framework for ensuring safe behavior of a reinforcement learning agent when the reward function may be difficult to specify. In order to do this, we rely on the existence of demonstrations from expert policies, and we provide a theoretical framework for the agent to optimize in the space of rewards consistent with its existing knowledge. We propose two methods to solve the resulting optimization: an exact ellipsoid-based method and a method in the spirit of the "follow-the-perturbed-leader" algorithm. Our experiments demonstrate the behavior of our algorithm in both discrete and continuous problems. The trained agent safely avoids states with potential negative effects while imitating the behavior of the expert in the other states.

PDF Details

GandALF Workshop 2012 Workshop Paper

Can Nondeterminism Help Complementation?

Yang Cai
Ting Zhang

Complementation and determinization are two fundamental notions in automata theory. The close relationship between the two has been well observed in the literature. In the case of nondeterministic finite automata on finite words (NFA), complementation and determinization have the same state complexity, namely Theta(2^n) where n is the state size. The same similarity between determinization and complementation was found for Buchi automata, where both operations were shown to have 2^Θ(n lg n) state complexity. An intriguing question is whether there exists a type of omega-automata whose determinization is considerably harder than its complementation. In this paper, we show that for all common types of omega-automata, the determinization problem has the same state complexity as the corresponding complementation problem at the granularity of 2^Θ(. ).

PDF Details DOI