Optimizing over Multiple Distributions under Generalized Quasar-Convexity Condition

Summary

The paper considers a minimization problem, where the optimizing variable is composed of $d$ probability distributions. The notion of quasar convexity is generalized by allowing for different quasar-convexity parameters $\gamma_i, i=1,...,d$ for the $d$ distributions. Instead of using the gradient function for the oracle term, more generic functions $F_i, i=1,...,d$ ("internal functions") are allowed. Convergence guarantees are established for the situations where the interval functions are either Lipschitz continuous of "polynomial-like". Infinite horizon reinforcement learning is shown two be a special case of this setting. Similar results are derived for the minimax setting.

Strengths

* thorough theoretical analysis * method requires strictly less iterations than mirror descent * algorithm also works for unknown $\gamma_i$ * reinforcement learning application is an important one * extensive overview of related work

Weaknesses

* Algorithm 1 and Algorithm 2 are never actually described in the text, they are only provided as pseudocode. It think it would be nice to add 2-3 sentences to point out how exactly it differs from basic mirror descent. Example given, I don't understand why one randomly picks t following probability $\mathbb{P}[t] =1/T$. * There is "only" one example (the reinforcement application) for the new structure the paper introduces. I am not sure if one example is enough to justify speaking of a new structure. (But I also understand that such examples are complex and it might go beyond the scope of the paper to come up with several such examples) * the paper does not mention the computational costs of the algorithm. Is it $d$ times as much as basic mirror descent? Is this still feasible in praxis? Typos: * Headline Algorithm 1: Mirior -> Mirror * line 206: depends -> depend

Questions

* I am confused about the following part in the introduction (line 62-65): "We then study designing efficient algorithms to solve (1). One simple case is when $\gamma_i, i=1...m$ is pre-known by the algorithms. The possible direction is to impose a $\gamma_i$-dependent update rule, such as by non-uniform sampling. However, in general cases, $\gamma_i, i=1...m$ is not known and determining $\gamma_i, i=1...m$ require non-negligible costs." Can you elaborate on this?

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

I don't see that the authors explicitly mention limitations of their work, but it is also a theoretical paper, so everyone can just read the assumptions at the beginning of the theorems to see where the results apply and where not. The assumptions made for the theoretical analysis are stated clearly.

Summary

The authors study a typical optimization model where the optimization variable is composed of multiple probability distributions. For this optimization problem, they propose a new structural condition/landscape description named generalized quasar-convexity (GQC) beyond the realms of convexity.

Strengths

It looks like the authors propose a new theoretical analysis for the quasar-convex optimization.

Weaknesses

It would be better if the authors added more motivation for why they focus on quasar optimization. Another point: the theoretical analysis demonstrated is not very clear. If they can show it clearer, it will be better,

Questions

Does the assumption 4.2 can be relaxed? Can the Section 4.3 be written more?

Rating

4

Confidence

4

Soundness

2

Presentation

2

Contribution

2

Limitations

No

Summary

This paper introduces a novel optimization model for addressing problems involving multiple probability distributions, a common scenario in fields such as policy optimization and reinforcement learning. The authors present a new structural condition called Generalized Quasar-Convexity (GQC), which extends the original quasar-convexity concept by allowing individual quasar-convex parameters for each variable block. This flexibility accommodates varying degrees of block convexity. The paper proposes an Optimistic Mirror Descent (OMD) algorithm tailored to this framework and demonstrates its efficiency in achieving an ε-suboptimal global solution. Furthermore, the paper extends the GQC concept to minimax optimization problems by introducing the Generalized Quasar-Convexity-Concavity (GQCC) condition. The theoretical findings are supported by applications in discounted Markov Decision Processes (MDPs) and Markov games, showing improved iteration complexity bounds over existing methods.

Strengths

- The introduction of GQC and GQCC conditions provides a fresh perspective on optimization problems involving multiple distributions, extending beyond traditional convexity assumptions. - The paper offers rigorous theoretical analysis, including complexity bounds for the proposed OMD algorithm, and demonstrates that these bounds are tighter than those for existing methods. - The application of the proposed framework to reinforcement learning and Markov games showcases its practical relevance and potential impact on real-world problems.

Weaknesses

- The assumptions made for the GQC and GQCC conditions, such as polynomial-like structures and specific Lipschitz continuity requirements, may limit the generality of the results. It would be beneficial to discuss the applicability of these assumptions in broader contexts. - While the theoretical contributions are robust, the paper lacks empirical validation through extensive experiments. Including experimental results on synthetic and real-world datasets would strengthen the paper by demonstrating the practical performance of the proposed algorithms.

Questions

Yes

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

- How do the assumptions made for the GQC and GQCC conditions compare to those in other optimization frameworks? Are there potential relaxations or alternative conditions that could be explored to broaden the applicability of the proposed methods? - Can you provide more detailed insights or examples of real-world problems where the proposed GQC and GQCC conditions are particularly beneficial? How do these conditions improve the solution quality or computational efficiency in such scenarios?

Summary

The paper studies the optimization of generalized quasar convex (GQC) functions, a new global structure introduced in this paper. This definition relaxes the quasar convexity (QC) condition, in a way that different components of the optimization variable satisfy the QC like condition with different parameters. The key idea is that if we simply treat a GQC function as a QC function, one needs to take d times the maximum value of these paramters which can be large. Applying GQC allows one to deal with the sum instead which could be significantly smaller than d. Leveraging this insight, the authors adapt the well-known optimistic mirror descent algorithm. The main use case appears to be in policy optimization in MDPs, where the authors show that the GQC condition is shown to be satisfied by the expected value function. The authors also define a similar condition for minimax optimization problems, and apply their framework to find the Nash equilibrium of a two-player zero sum Markov game. Overall my evaluation of the paper is quite positive. Even as a non-expert, I was able to appreciate the ideas and the contributions of the authors. The paper is also well-written and easy to follow. I have given a positive score to reflect my current assessment. However, as this is not my area, I am unable to evaluate the technical merit and novelty of proot techniques in the paper, and I did not dive into the proofs in the appendix. So I will also wait to hear from more expert reviewers.

Strengths

See above

Weaknesses

See above

Questions

See above

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

See above