Yinyu Ye

TCS Journal 2026 Journal Article

Computations and complexities of Tarski’s fixed points and supermodular games

• Chuangyin Dang
• Qi Qi
• Yinyu Ye

We consider two models of computation for Tarski's order preserving function f related to fixed points in a complete lattice: the oracle function model and the polynomial function model. In both models, we find the first polynomial time algorithm for finding a Tarski's fixed point. In addition, we provide a matching oracle bound for determining the uniqueness in the oracle function model and prove it is Co-NP hard in the polynomial function model. The existence of the pure Nash equilibrium in supermodular games is proved by Tarski's fixed point theorem. Exploring the difference between supermodular games and Tarski's fixed point, we also develop the computational results for finding one pure Nash equilibrium and determining the uniqueness of the equilibrium in supermodular games.

NeurIPS Conference 2025 Conference Paper

Solver-Informed RL: Grounding Large Language Models for Authentic Optimization Modeling

• Yitian Chen
• Jingfan Xia
• Siyu Shao
• Dongdong Ge
• Yinyu Ye

Optimization modeling is fundamental to decision-making in fields such as supply chain management, logistics, and financial engineering, but its complexity presents a major barrier to adoption. Automating model creation from natural language is key to improving efficiency and access. However, while Large Language Models (LLMs) are a promising tool for this, they often produce flawed or infeasible results due to errors and hallucinations. To address this issue, we propose Solver-Informed Reinforcement Learning (SIRL), a framework that uses Reinforcement Learning with Verifiable Reward to improve LLMs’ ability to generate accurate and executable optimization models. Specifically, SIRL automatically assesses the executable code and the instance-level mathematical model represented by the associated. lp files. This process yields precise feedback on syntactic validity, feasibility, and solution quality, which serves as a direct reward signal to guide the reinforcement learning process. Furthermore, this verification mechanism also supports our instance-enhanced self-consistency method for creating high-quality training data. Extensive experiments on diverse public benchmarks demonstrate that models trained with our SIRL framework achieve state-of-the-art performance, substantially outperforming existing methods in generating accurate and executable optimization models. Specifically, our SIRL-32B model surpasses DeepSeek-V3 and OpenAI-o3 on the majority of these benchmarks. Our code is publicly available at https: //github. com/Cardinal-Operations/SIRL.

NeurIPS Conference 2024 Conference Paper

Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process

• Jiashuo Jiang
• Yinyu Ye

We consider the reinforcement learning problem for the constrained Markov decision process (CMDP), which plays a central role in satisfying safety or resource constraints in sequential learning and decision-making. In this problem, we are given finite resources and a MDP with unknown transition probabilities. At each stage, we take an action, collecting a reward and consuming some resources, all assumed to be unknown and need to be learned over time. In this work, we take the first step towards deriving optimal problem-dependent guarantees for the CMDP problems. We derive a logarithmic regret bound, which translates into a $O(\frac{1}{\Delta\cdot\epsilon}\cdot\log^2(1/\epsilon))$ sample complexity bound, with $\Delta$ being a problem-dependent parameter, yet independent of $\epsilon$. Our sample complexity bound improves upon the state-of-art $O(1/\epsilon^2)$ sample complexity for CMDP problems established in the previous literature, in terms of the dependency on $\epsilon$. To achieve this advance, we develop a new framework for analyzing CMDP problems. To be specific, our algorithm operates in the primal space and we resolve the primal LP for the CMDP problem at each period in an online manner, with \textit{adaptive} remaining resource capacities. The key elements of our algorithm are: i) a characterization of the instance hardness via LP basis, ii) an eliminating procedure that identifies one optimal basis of the primal LP, and; iii) a resolving procedure that is adaptive to the remaining resources and sticks to the characterized optimal basis.

AAAI Conference 2024 Conference Paper

Learning to Pivot as a Smart Expert

• Tianhao Liu
• Shanwen Pu
• Dongdong Ge
• Yinyu Ye

Linear programming has been practically solved mainly by simplex and interior point methods. Compared with the weakly polynomial complexity obtained by the interior point methods, the existence of strongly polynomial bounds for the length of the pivot path generated by the simplex methods remains a mystery. In this paper, we propose two novel pivot experts that leverage both global and local information of the linear programming instances for the primal simplex method and show their excellent performance numerically. The experts can be regarded as a benchmark to evaluate the performance of classical pivot rules, although they are hard to directly implement. To tackle this challenge, we employ a graph convolutional neural network model, trained via imitation learning, to mimic the behavior of the pivot expert. Our pivot rule, learned empirically, displays a significant advantage over conventional methods in various linear programming problems, as demonstrated through a series of rigorous experiments.

AAAI Conference 2024 Conference Paper

Sketched Newton Value Iteration for Large-Scale Markov Decision Processes

• Jinsong Liu
• Chenghan Xie
• Qi Deng
• Dongdong Ge
• Yinyu Ye

Value Iteration (VI) is one of the most classic algorithms for solving Markov Decision Processes (MDPs), which lays the foundations for various more advanced reinforcement learning algorithms, such as Q-learning. VI may take a large number of iterations to converge as it is a first-order method. In this paper, we introduce the Newton Value Iteration (NVI) algorithm, which eliminates the impact of action space dimension compared to some previous second-order methods. Consequently, NVI can efficiently handle MDPs with large action spaces. Building upon NVI, we propose a novel approach called Sketched Newton Value Iteration (SNVI) to tackle MDPs with both large state and action spaces. SNVI not only inherits the stability and fast convergence advantages of second-order algorithms, but also significantly reduces computational complexity, making it highly scalable. Extensive experiments demonstrate the superiority of our algorithms over traditional VI and previously proposed second-order VI algorithms.

AAAI Conference 2024 Conference Paper

Trust Region Methods for Nonconvex Stochastic Optimization beyond Lipschitz Smoothness

• Chenghan Xie
• Chenxi Li
• Chuwen Zhang
• Qi Deng
• Dongdong Ge
• Yinyu Ye

In many important machine learning applications, the standard assumption of having a globally Lipschitz continuous gradient may fail to hold. This paper delves into a more general (L0, L1)-smoothness setting, which gains particular significance within the realms of deep neural networks and distributionally robust optimization (DRO). We demonstrate the significant advantage of trust region methods for stochastic nonconvex optimization under such generalized smoothness assumption. We show that first-order trust region methods can recover the normalized and clipped stochastic gradient as special cases and then provide a unified analysis to show their convergence to first-order stationary conditions. Motivated by the important application of DRO, we propose a generalized high-order smoothness condition, under which second-order trust region methods can achieve a complexity of O(epsilon(-3.5)) for convergence to second-order stationary points. By incorporating variance reduction, the second-order trust region method obtains an even better complexity of O(epsilon(-3)), matching the optimal bound for standard smooth optimization. To our best knowledge, this is the first work to show convergence beyond the first-order stationary condition for generalized smooth optimization. Preliminary experiments show that our proposed algorithms perform favorably compared with existing methods.

NeurIPS Conference 2020 Conference Paper

Conic Descent and its Application to Memory-efficient Optimization over Positive Semidefinite Matrices

• John C. Duchi
• Oliver Hinder
• Andrew Naber
• Yinyu Ye

We present an extension of the conditional gradient method to problems whose feasible sets are convex cones. We provide a convergence analysis for the method and for variants with nonconvex objectives, and we extend the analysis to practical cases with effective line search strategies. For the specific case of the positive semidefinite cone, we present a memory-efficient version based on randomized matrix sketches and advocate a heuristic greedy step that greatly improves its practical performance. Numerical results on phase retrieval and matrix completion problems indicate that our method can offer substantial advantages over traditional conditional gradient and Burer-Monteiro approaches.

NeurIPS Conference 2020 Conference Paper

Distributionally Robust Local Non-parametric Conditional Estimation

• Viet Anh Nguyen
• Fan Zhang
• Jose Blanchet
• Erick Delage
• Yinyu Ye

Conditional estimation given specific covariate values (i. e. , local conditional estimation or functional estimation) is ubiquitously useful with applications in engineering, social and natural sciences. Existing data-driven non-parametric estimators mostly focus on structured homogeneous data (e. g. , weakly independently and stationary data), thus they are sensitive to adversarial noise and may perform poorly under a low sample size. To alleviate these issues, we propose a new distributionally robust estimator that generates non-parametric local estimates by minimizing the worst-case conditional expected loss over all adversarial distributions in a Wasserstein ambiguity set. We show that despite being generally intractable, the local estimator can be efficiently found via convex optimization under broadly applicable settings, and it is robust to the corruption and heterogeneity of the data. Various experiments show the competitive performance of this new class of estimator.

TCS Journal 2020 Journal Article

Erratum/Correction to “On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering” [Theor. Comput. Sci. 732 (2018) 26–45]

• Chuangyin Dang
• Yinyu Ye

NeurIPS Conference 2020 Conference Paper

Simple and Fast Algorithm for Binary Integer and Online Linear Programming

• Xiaocheng Li
• Chunlin Sun
• Yinyu Ye

In this paper, we develop a simple and fast online algorithm for solving a class of binary integer linear programs (LPs) arisen in the general resource allocation problem. The algorithm requires only one single pass through the input data and is free of doing any matrix inversion. It can be viewed as both an approximate algorithm for solving binary integer LPs and a fast algorithm for solving online LP problems. The algorithm is inspired by an equivalent form of the dual problem of the relaxed LP and it essentially performs (one-pass) projected stochastic subgradient descent in the dual space. We analyze the algorithm under two different models, stochastic input and random permutation, with minimal technical assumptions on the input data. The algorithm achieves $O\left(m \sqrt{n}\right)$ expected regret under the stochastic input model and $O\left((m+\log n)\sqrt{n}\right)$ expected regret under the random permutation model, and it achieves $O(m \sqrt{n})$ expected constraint violation under both models, where $n$ is the number of decision variables and $m$ is the number of constraints. In addition, we employ the notion of permutational Rademacher complexity and derive regret bounds for two earlier online LP algorithms for comparison. Both algorithms improve the regret bound with a factor of $\sqrt{m}$ by paying more computational cost. Furthermore, we demonstrate how to convert the possibly infeasible solution to a feasible one through a randomized procedure. Numerical experiments illustrate the general applicability and effectiveness of the algorithms.

JMLR Journal 2019 Journal Article

Approximation Hardness for A Class of Sparse Optimization Problems

• Yichen Chen
• Yinyu Ye
• Mengdi Wang

In this paper, we consider three typical optimization problems with a convex loss function and a nonconvex sparse penalty or constraint. For the sparse penalized problem, we prove that finding an $\mathcal{O}(n^{c_1}d^{c_2})$-optimal solution to an $n\times d$ problem is strongly NP-hard for any $c_1, c_2\in [0,1)$ such that $c_1+c_2 [abs] [ pdf ][ bib ] &copy JMLR 2019. ( edit, beta )

NeurIPS Conference 2019 Conference Paper

Interior-Point Methods Strike Back: Solving the Wasserstein Barycenter Problem

• Dongdong Ge
• Haoyue Wang
• Zikai Xiong
• Yinyu Ye

Computing the Wasserstein barycenter of a set of probability measures under the optimal transport metric can quickly become prohibitive for traditional second-order algorithms, such as interior-point methods, as the support size of the measures increases. In this paper, we overcome the difficulty by developing a new adapted interior-point method that fully exploits the problem's special matrix structure to reduce the iteration complexity and speed up the Newton procedure. Different from regularization approaches, our method achieves a well-balanced tradeoff between accuracy and speed. A numerical comparison on various distributions with existing algorithms exhibits the computational advantages of our approach. Moreover, we demonstrate the practicality of our algorithm on image benchmark problems including MNIST and Fashion-MNIST.

NeurIPS Conference 2018 Conference Paper

Learning in Games with Lossy Feedback

• Zhengyuan Zhou
• Panayotis Mertikopoulos
• Susan Athey
• Nicholas Bambos
• Peter Glynn
• Yinyu Ye

We consider a game-theoretical multi-agent learning problem where the feedback information can be lost during the learning process and rewards are given by a broad class of games known as variationally stable games. We propose a simple variant of the classical online gradient descent algorithm, called reweighted online gradient descent (ROGD) and show that in variationally stable games, if each agent adopts ROGD, then almost sure convergence to the set of Nash equilibria is guaranteed, even when the feedback loss is asynchronous and arbitrarily corrrelated among agents. We then extend the framework to deal with unknown feedback loss probabilities by using an estimator (constructed from past data) in its replacement. Finally, we further extend the framework to accomodate both asynchronous loss and stochastic rewards and establish that multi-agent ROGD learning still converges to the set of Nash equilibria in such settings. Together, these results contribute to the broad lanscape of multi-agent online learning by significantly relaxing the feedback information that is required to achieve desirable outcomes.

NeurIPS Conference 2018 Conference Paper

Near-Optimal Time and Sample Complexities for Solving Markov Decision Processes with a Generative Model

• Aaron Sidford
• Mengdi Wang
• Xian Wu
• Lin Yang
• Yinyu Ye

In this paper we consider the problem of computing an $\epsilon$-optimal policy of a discounted Markov Decision Process (DMDP) provided we can only access its transition function through a generative sampling model that given any state-action pair samples from the transition function in $O(1)$ time. Given such a DMDP with states $\states$, actions $\actions$, discount factor $\gamma\in(0, 1)$, and rewards in range $[0, 1]$ we provide an algorithm which computes an $\epsilon$-optimal policy with probability $1 - \delta$ where {\it both} the run time spent and number of sample taken is upper bounded by \[ O\left[\frac{|\cS||\cA|}{(1-\gamma)^3 \epsilon^2} \log \left(\frac{|\cS||\cA|}{(1-\gamma)\delta \epsilon} \right) \log\left(\frac{1}{(1-\gamma)\epsilon}\right)\right] ~. \] For fixed values of $\epsilon$, this improves upon the previous best known bounds by a factor of $(1 - \gamma)^{-1}$ and matches the sample complexity lower bounds proved in \cite{azar2013minimax} up to logarithmic factors. We also extend our method to computing $\epsilon$-optimal policies for finite-horizon MDP with a generative model and provide a nearly matching sample complexity lower bound.

TCS Journal 2018 Journal Article

On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering

• Chuangyin Dang
• Yinyu Ye

Let Π be a finite lattice of integer points in a box of R n and f an increasing mapping in terms of the componentwise ordering from Π to itself. The well-known Tarski's fixed point theorem asserts that f has a fixed point in Π. A simple expansion of f from Π to a larger lattice C of integer points in a box of R n yields that the smallest point in C is always a fixed point of f (an expanded Tarski's fixed point problem). By introducing an integer labeling rule and applying a cubic triangulation of the Euclidean space, we prove in this paper that the expanded Tarski's fixed point problem is in the class PPA when f is given as an oracle. It is shown in this paper that Nash equilibria of a bimatrix game can be reformulated as fixed points different from the smallest point in C of an increasing mapping from C to itself. This implies that the expanded Tarski's fixed point problem has at least the same complexity as that of the Nash equilibrium problem. As a byproduct, we also present a homotopy-like simplicial method to compute a Tarski fixed point of f. The method starts from an arbitrary lattice point and follows a finite simplicial path to a fixed point of f.

TCS Journal 2008 Journal Article

The complexity of equilibria: Hardness results for economies via a correspondence with games

• Bruno Codenotti
• Amin Saberi
• Kasturi Varadarajan
• Yinyu Ye

We give a reduction from any two-player game to a special case of the Leontief exchange economy, with the property that the Nash equilibria of the game and the equilibria of the market are in one-to-one correspondence. Our reduction exposes a computational hurdle inherent in solving certain families of market equilibrium problems: finding an equilibrium for Leontief economies is at least as hard as finding a Nash equilibrium for two-player nonzero sum games, a problem recently proven to be P P A D -complete. As a corollary of the one-to-one correspondence, we obtain a number of hardness results for questions related to the computation of market equilibria, using results already established for games [I. Gilboa, E. Zemel, Nash and correlated equilibria: Some complexity considerations, Games and Economic Behavior 1 (1989) 80–93]. In particular, among other results, we show that it is N P -hard to say whether a particular family of Leontief exchange economies, that is guaranteed to have at least one equilibrium, has more than one equilibrium. Perhaps more importantly, we also prove that it is N P -hard to decide whether a Leontief exchange economy has an equilibrium. This fact should be contrasted against the known P P A D -completeness result of [C. H. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, Journal of Computer and System Sciences 48 (1994) 498–532], which holds when the problem satisfies some standard sufficient conditions that make it equivalent to the computational version of Brouwer’s Fixed Point Theorem.

TCS Journal 2007 Journal Article

Exchange market equilibria with Leontief’s utility: Freedom of pricing leads to rationality

• Yinyu Ye

This paper studies the equilibrium property and algorithmic complexity of the exchange market equilibrium problem with concave piecewise linear functions, which include linear and Leontief’s utility functions as special cases. We show that the Fisher model again reduces to the weighted analytic center problem, and the same linear programming complexity bound applies to computing its equilibrium. However, the story for the Arrow–Debreu model with Leontief’s utility becomes quite different. We show that, for the first time, solving this class of Leontief exchange economies is equivalent to solving a linear complementarity problem whose algorithmic complexity is finite but not polynomially bounded.