Research map / Optimization / Nonconvex and smooth optimization
Optimizing over Multiple Distributions under Generalized Quasar-Convexity Condition
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes generalized quasar-convexity (GQC) and GQCC for optimization over multiple probability distributions, with optimistic mirror descent achieving adaptive iteration complexity, and applies them to discounted MDPs and zero-sum Markov games.
Problem
Optimizing an objective whose variable is a product of multiple probability simplexes (and min-max versions), where global solutions are hard to find in the nonconvex setting; RL policy optimization and Markov games are key examples.
Approach
Generalizes quasar-convexity with an individual parameter gamma_i per distribution block and an internal function oracle, then runs block-wise optimistic mirror descent (KL divergence) whose complexity scales with sum_i 1/gamma_i rather than d times the max, adapting to unknown gamma_i for polynomial-like objectives.
Key results
- Algorithm 1 (OMD over distributions) achieves adaptive Õ((sum_i 1/gamma_i) ε^-1) iteration complexity for polynomial-like GQC objectives without knowing gamma_i.
- For infinite-horizon two-player zero-sum Markov games, the method finds an ε-approximate Nash equilibrium in Õ((1-θ)^-2.5 ε^-1) iterations, improving on Cen et al. by a factor of |S| up to logs.
- Infinite-horizon discounted MDP policy objective is shown to satisfy GQC with internal function Q^π(s_i,·), with iteration complexity independent of the number of states.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive OMD with internal functions under GQC and Assumption 3.3 | GQC minimization · GQC minimization | iteration complexity: O((Pd_i=1 1/γi)ε−1 log(N) log4.5(ε−1)) | Helped |
| Use OMD with action-value internal functions | Infinite-horizon discounted MDP policy optimization · Infinite-horizon discounted MDP | iteration complexity: O(max{1, log−1(θ−1)}(1−θ)−1ε−1 log4.5(ε−1) log(|A|)) | Helped |
| Use regularized OMD with the Markov-game internal operator | Infinite-horizon two-player zero-sum Markov games · Infinite-horizon two-player zero-sum Markov games | iteration complexity: ˜O((1 − θ)−2.5ε−1) | Helped |
| Use regularized OMD instead of Wei et al. [67] | Infinite-horizon two-player zero-sum Markov games · Infinite-horizon two-player zero-sum Markov games | iteration complexity: ˜O(ε−1); ˜O(|S|3ε−2) | Helped |
| Use regularized OMD instead of Cen et al. [10] | Infinite-horizon two-player zero-sum Markov games · Infinite-horizon two-player zero-sum Markov games | iteration complexity: ˜O(ε−1); ˜O(|S|ε−1) | Helped |
Surprising findings
- Iteration complexity does not explicitly depend on the number of states or distributions in the MDP and Markov game applications, since sum of discounted visitation weights equals 1.
Limitations
- Adaptive bound relies on polynomial-like assumption (Assumption 3.3) on the internal function, which is restrictive in general.
- Minimax complexity depends on an upper bound of sum of psi_i over the feasible region, which may scale with d in general.
Experimental setup
Metrics: iteration complexity suboptimality gap max-min gap
Baselines: Agarwal et al. natural policy gradient Wei et al. optimistic gradient descent/ascent Cen et al. entropy-regularized policy optimization for Markov games
Builds on: quasar-convexity mirror descent optimistic mirror descent natural policy gradient optimistic gradient descent/ascent for Markov games
Closest papers by meaning
- Mirror Descent-Ascent for mean-field min-max problems (NeurIPS 2026 · similarity 0.84)
- Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity (NeurIPS 2026 · similarity 0.84)
- How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization (ICML 2024 · similarity 0.84)
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.84)
- High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.84)
- Stability and Generalization for Stochastic Recursive Momentum-based Algorithms for (Strongly-)Convex One to $K$-Level Stochastic Optimizations (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.