Optimizing over Multiple Distributions under Generalized Quasar-Convexity Condition

Thank you for your comments and suggestions. We will respond to each of your comments individually in the following.

Algorithms Descriptions:

Thanks for your suggestion. We will use equations and sentences to introduce the algorithm. One randomly picks $t$ following probability means we output $x^t$ by uniformly sample from $(x^t)_{t=1}^T$.

Examples:

For minimization problems, we provide two examples of functions that simultaneously satisfy both the GQC condition and Assumption 3.3: a toy example (Example B.8 in Appendix B) and a simple neuron network over a simplex (Example 3.4 in Section 3.2). For minimax problems, In addition to infinite horizon two-player zero-sum Markov games, we have also demonstrated that general smooth convex-concave problems satisfy the GQCC condition and Assumption 4.2 (see Appendix C.3.2). Further examples await our future exploration.

Computational Costs:

Since the MD method requires computing a $\sum_{i=1}^d n_i$-dimensional gradient vector at each iteration, and Algorithm 1 also requires computing a $\sum_{i=1}^d n_i$-dimensional internal function at each iteration, so Algorithm 1 does not need more additional computational costs.

Response to confuse about line 62-65:

Sorry for the confusion. We mean that If $\{\gamma_i\}$ is known, then the update of our algorithm on each variable block will depend on $\gamma_iF_i$ rather than solely on $F_i$. However, in many applications, $\{\gamma_i\}$ is often related to the information of the optimal point (see Appendix B.3 for reinforcement learning problem, $\gamma_i$ depends on the optimal solutions). Therefore, the computational costs of estimating $\{\gamma_i\}$ may even exceed that to solve the optimization problems. This is our motivation to design adaptive algorithms without pre-known $\{\gamma_i\}$.

Thank you for your comments and suggestions. We will respond to each of your comments individually in the following.

Motivation:

In many non-convex optimization problems, the objective function often admits ''convexity-like'' properties, such as matrix completion, phase retrieval, and neural network under some settings (Bartlett et al., 2019; Ge et al., 2016). Therefore, exploring the structured sets of functions for which the problem can be efficiently solved is meaningful. This aligns with the ideas proposed by Hinder et al., (2020). Quasar convexity is a widely known condition in the field of optimization with two typical examples in machine learning: 1) the loss functions of neural networks satisfy the quasar convexity condition in large neighborhoods of the minimizers (Kleinberg et al., 2018; Zhou et al., 2019); 2) Under mild assumptions, the objective function for learning linear dynamical systems also admits to the quasar convexity condition (Hardt et al., 2018). Furthermore, generalized quasar convexity (GQC), as an extension of quasar convexity, encompasses not only quasar convexity but also the function structures of reinforcement learning and certain neural networks. This implies that the objective functions of more machine learning problems may satisfy the GQC condition. Our analysis provides a theoretical guarantee for the solvability of approximate global optima of these problems. As a supplement to the GQC condition, generalized quasar-convexity-concavity (GQCC) extends the concept of convexity-concavity. Based on this landscape characterization and appropriate assumptions, we propose an algorithm for solving minimax problems that have a better convergence rate in specific machine learning problems.

Theoretical analysis is not clear:

Thanks for your suggestions. We will add more intuitive discussions for our analysis. For Thm 3.5, the key idea is to reduce the impact of each variable block on the function error, which plays a crucial role in establishing global convergence. Concretely, we separate the upper bound of $\frac{1}{T}\sum_{t=1}^T(f(x^t)-f(x^{*}))$ into: a) an invariant lower order term and b) the weighted sum of variance of finite difference term $\frac{\mathcal{O}(1)}{T} \sum_{t=1}^TVar_{x_i^t}(F_i(x^t)-F_i(x^{t-1}))-\frac{\mathcal{O}(1)}{T} \sum_{t=1}^TVar_{x_i^t}(F_i(x^{t-1}))$. Furthermore, applying the property of sequence $(F_i(x^t))_{t=1}^T$ under ''polynomial-like'' structure condition, we bound (b) by a quantity that grows poly-logarithmically in $T$. For a more detailed proof sketch, please refer to the beginning of Appendix B.1. We will add more explanations for both Thm 3.5 and 4.4 in the revised version.

Relax Assumption 4.2:

Thanks for suggestion. Currently, to achieve the faster $\tilde{\mathcal{O}}(1/T)$ convergence rate, we do not find a clear way to have a good relaxation. The main challenges of multi-variable block optimization problems lie in its non-convex (non-convex-non-concave) structure and the coupling of multiple variable blocks. Therefore, a simple Lipschitz continuity assumption on internal function may not be helpful in obtaining a faster rate. However, for a slower rate, such as $\tilde{\mathcal{O}}(1/\sqrt{T})$, it is possible and we leave it as a future work. We will discuss it in the revised version.

Written more Section 4.3:

Thanks for suggestion. We will introduce more background about Markov games, including its problem formulation, relation to convex and concave optimization, and current results.

Dear reviewer,

Thank you for your efforts in the review process. We have tried our best to address your concerns and answer the insightful questions. Please let us know if you have any other questions regarding our paper or response. If we have successfully addressed your questions, we would greatly appreciate if you can reevaluate the score.

Best,

Authors

Thanks for your comments and suggestions. We will respond to each of your comments individually in the following.

Discuss the applicability of these assumptions in broader contexts:

Thanks for your suggestion. We will add more discussions on the applicability of the assumption and our framework. For minimization problems under the GQC condition, we begin with a convergence result relying on the general Lipschitz continuous condition of internal function $F$. However, under this condition, we need to additionally assume that $\max_{i\in[1:d]}\gamma_i<+\infty$. Based on the aforementioned assumption merely, according to our knowledge, it appears impossible to eliminate the coupling effects between different variable blocks without a consistent upper-bounded assumption of $\{\gamma_i\}$. In certain applications, $\max_{i\in[1:d]}\gamma_i$ can indeed approach $+\infty$. For instance, in the infinite horizon reinforcement learning problems, the discounted state visitation distribution $d_{\rho_0}^{\pi}(s)$ for a particular state $s$ may approach zero, implying that $1/\gamma_s=0$. Therefore, to address this uncertainty of unknown $\{\gamma_i\}$, we introduce the Assumption 3.3. Assumption 3.3 is not hard to achieve. In Proposition B.2 of Appendix B, we demonstrate that if the absolute value of the higher-order derivatives of a vector-valued function $F$ grows exponentially with its order, then $F$ admits Assumption 3.3. Furthermore, since the feasible domain of the functions considered in this paper is a bounded closed region, the conditions of Proposition B.2 are easily satisfied by smooth $F$, making Assumption 3.3 hold easily. Additionally, we provide two examples of functions that simultaneously satisfy both the GQC condition and Assumption 3.3: a toy example (Example B.8 in Appendix B) and a simple neuron network over a simplex (Example 3.4 in Section 3.2). For minimax problems, most algorithms that guarantee global convergence are based on a convex-concave structure. Our assumptions not only encompass the assumption of Lipschitz continuous gradients for the objective function $f$ in the convex-concave case (refer to Section C.3.2 in Appendix C) but also provide a unified landscape description for infinite horizon two-player zero-sum Markov games. It is worth noting that Algorithm 2 in this paper achieves a better convergence rate in infinite horizon two-player zero-sum Markov games compared to the results in Wei et al., (2021).

Experiments:

Please refer to response Author Rebuttal:$**Experiments**$.

Potential relaxations or alternative conditions:

Thanks for your concerns about the generality of our conditions and the request to relax the assumptions. The GQC condition include quasar convexity (QC) condition. Actually, our algorithm can achieve $\tilde{\mathcal{O}}(1/T)$ convergence rate under QC condition with Lipschitz continuous internal function $\nabla f$. Currently, to achieve the faster $\tilde{\mathcal{O}}(1/T)$ convergence rate, we do not find a clear way to have a good relaxation. The main challenges of multi-variable block optimization problems lie in its non-convex (non-convex-non-concave) structure and the coupling of multiple variable blocks. Therefore, a simple Lipschitz continuity assumption on internal function may not be helpful in obtaining a faster rate. However, for a slower rate, such as $\tilde{\mathcal{O}}(1/\sqrt{T})$, it is possible and we leave it as a future work.

Detailed insights or examples of real-world problems where the proposed GQC and GQCC conditions are particularly beneficial?

We prove that for reinforcement learning (RL) problem, GQC can be achieved. For the infinite horizon reinforcement learning problems, the discounted state visitation distribution $d_{\rho_0}^{\pi}(s)$ satisfies $\sum_{s\in S}d_{\rho_0}^{\pi}(s)=1$, implying that $\sum_{s\in S}1/\gamma_s=1$, therefore our algorithmic complexity does not rely on $|S|$. However, if we describe the properties of the function using the worst $1/\gamma_s$ (similar to the QC condition), then the complexity might be $|S|\max_{s\in S}1/\gamma_s$. Similarly, we prove that infinite horizon two-player zero-sum Markov games satisfies GQCC condition. For infinite horizon two-player zero-sum Markov games, $\sum_{s\in S}\psi_s(z)\leq 2$ for any $z\in \mathcal{Z}$. Therefore, the convergence rate of Algorithm 2 does not depend on $|S|$.

We thank you for dedicating your time and effort to reviewing our manuscript. We appreciate that you acknowledge our paper. We will also carefully revise the paper to enhance its readability.