Optimizing over Multiple Distributions under Generalized Quasar-Convexity Condition
Authors: Ding Shihong, Long Yang, Luo Luo, Cong Fang
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study a typical optimization model where the optimization variable is composed of multiple probability distributions. Though the model appears frequently in practice, such as for policy problems, it lacks specific analysis in the general setting. For this optimization problem, we propose a new structural condition/landscape description named generalized quasar-convexity (GQC) beyond the realms of convexity. [...] We provide optimistic mirror descent (OMD) for multiple distributions and prove that the algorithm can achieve an adaptive O((Pd i=1 1/γi)ε 1) iteration complexity to find an ε-suboptimal global solution without pre-known the exact values of γi when the objective admits polynomial-like structural. Notably, it achieves iteration complexity that does not explicitly depend on the number of distributions and strictly faster (Pd i=1 1/γi v.s. d maxi [1:d] 1/γi) than mirror decent methods. We also extend GQC to the minimax optimization problem proposing the generalized quasar-convexity-concavity (GQCC) condition and a decentralized variant of OMD with regularization. Finally, we show the applications of our algorithmic framework on discounted Markov Decision Processes problem and Markov games, which bring new insights on the landscape analysis of reinforcement learning. |
| Researcher Affiliation | Academia | Shihong Ding1 dingshihong@stu.pku.edu.cn Long Yang1 YANGLONG001@pku.edu.cn Luo Luo2,4 luoluo@fudan.edu.cn Cong Fang1,3 fangcong@pku.edu.cn 1 State Key Lab of General AI, School of Intelligence Science and Technology, Peking University 2 School of Data Science, Fudan University 3 Institute for Artificial Intelligence, Peking University 4 Shanghai Key Laboratory for Contemporary Applied Mathematics |
| Pseudocode | Yes | Algorithm 1 Optimistic Mirror Descent for Multi-Distributions ... Algorithm 2 Optimistic Mirror Descent with Regularization for Multiple Distributions |
| Open Source Code | No | The paper is theoretical and does not provide any information about open-sourcing code for the described methodology. The NeurIPS checklist confirms 'NA' for code-related questions, stating 'The paper does not include experiments'. |
| Open Datasets | No | The paper is theoretical and does not conduct empirical studies with datasets. The NeurIPS checklist confirms 'NA' for experimental reproducibility questions, stating 'The paper does not include experiments'. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical studies, thus there are no training/test/validation splits described. The NeurIPS checklist confirms 'NA' for experimental reproducibility questions, stating 'The paper does not include experiments'. |
| Hardware Specification | No | The paper is theoretical and does not include experiments, thus no hardware specifications are mentioned. The NeurIPS checklist confirms 'NA' for experimental reproducibility questions, stating 'The paper does not include experiments'. |
| Software Dependencies | No | The paper is theoretical and does not include experiments, thus no software dependencies with version numbers are listed. The NeurIPS checklist confirms 'NA' for experimental reproducibility questions, stating 'The paper does not include experiments'. |
| Experiment Setup | No | The paper is theoretical and does not include experiments, thus no experimental setup details like hyperparameters or training settings are provided. The NeurIPS checklist confirms 'NA' for experimental reproducibility questions, stating 'The paper does not include experiments'. |