An Invex Relaxation Approach for Minimizing Polarization from Fully and Partially Observed Initial Opinions

Firstly, we thank the reviewer for taking their valuable time to provide feedback.

Running first-order optimization algorithms on non-convex problems only guarantees us a local minimum. Studying the properties of these local minima and proving an even stronger result that there exists a global minima improves our theoretical understanding of these problems. This, in turn, motivates the design of efficient algorithms for such problems. There is a wide range of non-convex practical problems which have been studied in this context. These include, but are not limited to, principal components analysis, canonical correlation analysis, orthogonal tensor decomposition, phase retrieval, dictionary learning, matrix sensing, matrix completion, and other nonconvex low-rank problems. A few references are provided below:

Lee, J.D., Simchowitz, M., Jordan, M.I. and Recht, B., 2016, June. Gradient descent only converges to minimizers. In Conference on learning theory (pp. 1246-1257). PMLR.

Ge, R., Huang, F., Jin, C. and Yuan, Y., 2015, June. Escaping from saddle points—online stochastic gradient for tensor decomposition. In Conference on learning theory (pp. 797-842). PMLR.

Our contribution here is similar in this aspect, where we theoretically demonstrate the characteristics of polarization function under the popular FJ dynamics, which is believed to be non-convex. By showing that polarization (and the general class of $M \rightarrow$ $s^TM^{-k}s$ functions) are invex, a special class of non-convex functions, we ensure there are no saddle points, and every local minimum is a global minimum for this class of functions. This information is valuable in algorithm design as it ensures that first-order methods are not stuck at local minima or saddle points. The objective function for $k=2$, $M \rightarrow$ $s^TM^{-2}s$, is conjectured to have only one local minimum [Citation: Xi Chen et.al., Page 10]. Ours is the first theoretical result that validates this conjecture.

Not only do we theoretically demonstrate the global optimality scenarios for various practical cases of polarization, including stubborn actors and multi-period polarization, but we also deal with scenarios where only partial information about initial opinions is available. Our relaxations provided in equations (5), (6), and (24) aim to identify the edges that provably minimize polarization.

Also, observe that most of the literature is focussed on minimizing convex objectives such as Polarization and Disagreement index or understanding Disagreement among users (references are provided in Section 3: Prior Work).

[Citation: Miklos Z. Rácz et al., page 12] studied this problem in a discrete setting and provided heuristics to minimize polarization. Ours is the first continuous optimization study that provides theoretical guarantees in this aspect and outperforms the existing approaches.

Thus, our contributions are multi-fold:

1. Rather than modelling the problem in a discrete setting, we provide a continuous relaxation backed up with theoretical guarantees for polarization under known initial opinions, including the realistic cases of stubborn actors and multi-period.
2. We also study a realistic problem setting that has not been previously studied, wherein the observer has access to only a subset of initial opinions. We show that in these cases, too, PGD can attain the global minimum. Note that this scenario can also be extended to stubborn actors and multi-period.

We hope to have addressed the reviewer's questions. We would be happy to answer any further questions.

Firstly, we thank the reviewer for taking their valuable time to provide feedback.

We are solving the problem (5), which is the relaxation of the problem (3). We have now mentioned this explicitly in our paper (page 7, below equation 6 in the rebuttal edition of the paper).

Regarding the distribution of unknown opinions: We have provided new proof in Appendix F where the invexity is attained without any assumptions on the distribution of initial opinions (in the rebuttal version of the paper). Thus, the global minimum guarantees are maintained even under the unknown distribution of initial opinions.

We are currently working on the suggested experimentation for the baseline coordinate descent approach where the unknown opinions are mean imputed. We will add a follow-up to this update soon.

We hope to have addressed the reviewer's questions. We would be happy to answer any further questions.

Dear Reviewer,

We have incorporated experiments on coordinate descent (by mean imputation of opinions) and compared the results with Trace and nonconvex relaxations. These experiments are detailed on page 19 of supplementary material under the section labeled "Additional experimentation for partially observable initial opinions."

Thank you for the clarifications and additional experiments.

I appreciate the expanded theoretical result showing that the expected objective is invex for arbitrary initial distributions of opinions, which I feel strengthens the paper. However, if I am understanding correctly, you would have to know what the initial distribution is in order to apply your method. In practice, this initial distribution is unlikely to be known precisely, and would be estimated somehow. How sensitive is your method to inaccuracies in estimating this initial distribution?

Dear reviewer,

Relevance to ICLR: The URL for the ICLR conference has a “general machine learning” track, which is where we submitted our paper. Also, the conference has non-convex optimization listed in the subject areas. The webpage also says, “A non-exhaustive list of relevant topics.” So, we believe the conference is open to other ML topics, such as ours, where we characterize the objective function followed by a non-convex relaxation pertinent to the problem under study.

We strongly believe that we addressed all the relevant state-of-the-art literature pertinent to the problem in the prior work section. We also provided an additional literature review in Appendix A of the paper that was submitted for review.

Motivation: The topic of polarization has been motivated in the introduction section of the paper. The formal Instance of the polarization minimization problem is provided on Page 2 of our paper. Also, we would like to point out that we are not the first to study the polarization minimization problem. This problem has been initially proposed in the [Citation: Xi Chen et al. on Page 10, Cameron Musco et al. on Page 11 of references].

Laplacian Learning: Note that the current literature on Laplacian Learning, such as the ones listed below, does not have the negative exponent of “-2” in their objective, unlike what we have for polarization minimization ($s^T(I+L)^{-2}s$). So, the current literature on Laplacian learning is not directly applicable.

Changhao Shi and Gal Mishne, 2023. Graph Laplacian Learning with Exponential Family Noise. Fourteenth International Conference on Sampling Theory and Applications.

Egilmez, H.E., Pavez, E. and Ortega, A., 2017. Graph learning from data under Laplacian and structural constraints. IEEE Journal of Selected Topics in Signal Processing, 11(6), pp.825-841.

Kumar, S., Ying, J., de Miranda Cardoso, J.V. and Palomar, D., 2019. Structured graph learning via Laplacian spectral constraints. Advances in neural information processing systems, 32.