Search

Social balance is a concept in sociology which states that if every three individuals in a population achieve certain structures of positive or negative interactions, then the whole population ends up in one faction of positive interactions or divided between two or more antagonistic factions. In this paper, we consider a group of interacting large language models (LLMs) and study how, after continuous interactions, they can achieve social balance. Across three different LLM models, we found that social balance depends on (i) whether interactions are updated based on "relationships", "appraisals", or "opinions"; (ii) whether agents update their interactions based on homophily or influence from their peers; and (iii) the number of simultaneous interactions the LLMs consider. When social balance is achieved, its particular structure of positive or negative interactions depends on these three conditions and are different across LLM models and sizes. The stability of interactions and the justification for their update also vary across models. Thus, social balance is driven by the pre-training and alignment particular to each LLM model.

Weight normalization (WeightNorm) is widely used in practice for the training of deep neural networks and modern deep learning libraries have built-in implementations of it. In this paper, we provide the first theoretical characterizations of both optimization and generalization of deep WeightNorm models with smooth activation functions. For optimization, from the form of the Hessian of the loss, we note that a small Hessian of the predictor leads to a tractable analysis. Thus, we bound the spectral norm of the Hessian of WeightNorm networks and show its dependence on the network width and weight normalization terms--the latter being unique to networks without WeightNorm. Then, we use this bound to establish training convergence guarantees under suitable assumptions for gradient decent. For generalization, we use WeightNorm to get a uniform convergence based generalization bound, which is independent from the width and depends sublinearly on the depth. Finally, we present experimental results which illustrate how the normalization terms and other quantities of theoretical interest relate to the training of WeightNorm networks.

We study the evolution of opinions inside a population of interacting large language models (LLMs). Every LLM needs to decide how much funding to allocate to an item with three initial possibilities: full, partial, or no funding. We identify biases that drive the exchange of opinions based on the LLM's tendency to find consensus with the other LLM's opinion, display caution when specifying funding, and consider ethical concerns in its opinion. We find these biases are affected by the perceived absence of compelling reasons for opinion change, the perceived willingness to engage in discussion, and the distribution of allocation values. Moreover, tensions among biases can lead to the survival of funding for items with negative connotations. We also find that the final distribution of full, partial, and no funding opinions is more diverse when an LLM freely forms its opinion after an interaction than when its opinion is a multiple-choice selection among the three allocation options. In the latter case, consensus is mostly attained. When agents are aware of past opinions, they seek to maintain consistency with them, changing the opinion dynamics. Our study is performed using Llama 3 and Mistral LLMs.

Nash Q-learning may be considered one of the first and most known algorithms in multi-agent reinforcement learning (MARL) for learning policies that constitute a Nash equilibrium of an underlying general-sum Markov game. Its original proof provided asymptotic guarantees and was for the tabular case. Recently, finite-sample guarantees have been provided using more modern RL techniques for the tabular case. Our work analyzes Nash Q-learning using linear function approximation -- a representation regime introduced when the state space is large or continuous -- and provides finite-sample guarantees that indicate its sample efficiency. We find that the obtained performance nearly matches an existing efficient result for single-agent RL under the same representation and has a polynomial gap when compared to the best-known result for the tabular case., Comment: 25 pages. arXiv admin note: text overlap with arXiv:2205.15891

We consider the problem of optimization of deep learning models with smooth activation functions. While there exist influential results on the problem from the ``near initialization'' perspective, we shed considerable new light on the problem. In particular, we make two key technical contributions for such models with $L$ layers, $m$ width, and $\sigma_0^2$ initialization variance. First, for suitable $\sigma_0^2$, we establish a $O(\frac{\text{poly}(L)}{\sqrt{m}})$ upper bound on the spectral norm of the Hessian of such models, considerably sharpening prior results. Second, we introduce a new analysis of optimization based on Restricted Strong Convexity (RSC) which holds as long as the squared norm of the average gradient of predictors is $\Omega(\frac{\text{poly}(L)}{\sqrt{m}})$ for the square loss. We also present results for more general losses. The RSC based analysis does not need the ``near initialization" perspective and guarantees geometric convergence for gradient descent (GD). To the best of our knowledge, ours is the first result on establishing geometric convergence of GD based on RSC for deep learning models, thus becoming an alternative sufficient condition for convergence that does not depend on the widely-used Neural Tangent Kernel (NTK). We share preliminary experimental results supporting our theoretical advances.

While the difficulty of reinforcement learning problems is typically related to the complexity of their state spaces, Abstraction proposes that solutions often lie in simpler underlying latent spaces. Prior works have focused on learning either a continuous or dense abstraction, or require a human to provide one. Information-dense representations capture features irrelevant for solving tasks, and continuous spaces can struggle to represent discrete objects. In this work we automatically learn a sparse discrete abstraction of the underlying environment. We do so using a simple end-to-end trainable model based on the successor representation and max-entropy regularization. We describe an algorithm to apply our model, named Discrete State-Action Abstraction (DSAA), which computes an action abstraction in the form of temporally extended actions, i.e., Options, to transition between discrete abstract states. Empirically, we demonstrate the effects of different exploration schemes on our resulting abstraction, and show that it is efficient for solving downstream tasks.

Although parallelism has been extensively used in reinforcement learning (RL), the quantitative effects of parallel exploration are not well understood theoretically. We study the benefits of simple parallel exploration for reward-free RL in linear Markov decision processes (MDPs) and two-player zero-sum Markov games (MGs). In contrast to the existing literature, which focuses on approaches that encourage agents to explore a diverse set of policies, we show that using a single policy to guide exploration across all agents is sufficient to obtain an almost-linear speedup in all cases compared to their fully sequential counterpart. Furthermore, we demonstrate that this simple procedure is near-minimax optimal in the reward-free setting for linear MDPs. From a practical perspective, our paper shows that a single policy is sufficient and provably near-optimal for incorporating parallelism during the exploration phase., Comment: 50 pages

The design of fixed point algorithms is at the heart of monotone operator theory, convex analysis, and of many modern optimization problems arising in machine learning and control. This tutorial reviews recent advances in understanding the relationship between Demidovich conditions, one-sided Lipschitz conditions, and contractivity theorems. We review the standard contraction theory on Euclidean spaces as well as little-known results for Riemannian manifolds. Special emphasis is placed on the setting of non-Euclidean norms and the recently introduced weak pairings for the $\ell_1$ and $\ell_\infty$ norms. We highlight recent results on explicit and implicit fixed point schemes for non-Euclidean contracting systems., Comment: Paper in the invited tutorial session "Contraction Theory for Machine Learning" at 60th IEEE Conference on Decision and Control, 2021

Much recent interest has focused on the design of optimization algorithms from the discretization of an associated optimization flow, i.e., a system of differential equations (ODEs) whose trajectories solve an associated optimization problem. Such a design approach poses an important problem: how to find a principled methodology to design and discretize appropriate ODEs. This paper aims to provide a solution to this problem through the use of contraction theory. We first introduce general mathematical results that explain how contraction theory guarantees the stability of the implicit and explicit Euler integration methods. Then, we propose a novel system of ODEs, namely the Accelerated-Contracting-Nesterov flow, and use contraction theory to establish it is an optimization flow with exponential convergence rate, from which the linear convergence rate of its associated optimization algorithm is immediately established. Remarkably, a simple explicit Euler discretization of this flow corresponds to the Nesterov acceleration method. Finally, we present how our approach leads to performance guarantees in the design of optimization algorithms for time-varying optimization problems.

Consider a multi-agent system whereby each agent has an initial probability measure. In this paper, we propose a distributed algorithm based upon stochastic, asynchronous and pairwise exchange of information and displacement interpolation in the Wasserstein space. We characterize the evolution of this algorithm and prove it computes the Wasserstein barycenter of the initial measures under various conditions. One version of the algorithm computes a standard Wasserstein barycenter, i.e., a barycenter based upon equal weights; and the other version computes a randomized Wasserstein barycenter, i.e., a barycenter based upon random weights for the initial measures. Finally, we specialize our algorithm to Gaussian distributions and draw a connection with the modeling of opinion dynamics in mathematical sociology., Comment: 25 pages, 4 figures

Contraction theory for dynamical systems on Euclidean spaces is well-established. For contractive (resp. semi-contractive) systems, the distance (resp. semi-distance) between any two trajectories decreases exponentially fast. For partially contractive systems, each trajectory converges exponentially fast to an invariant subspace. In this note, we develop contraction theory on Hilbert spaces. First, we provide a novel integral condition for contractivity, and for time-invariant systems, we establish the existence of a unique globally exponentially stable equilibrium. Second, we introduce the notions of partial and semi-contraction and we provide various sufficient conditions for time-varying and time-invariant systems. Finally, we apply the theory on a classic reaction-diffusion system.

This paper analyzes a Susceptible-Infected-Susceptible (SIS) model of epidemic propagation over hypergraphs and, motivated by an important special case, we refer to the model as to the simplicial SIS model. Classically, the multi-group SIS model has assumed pairwise interactions of contagion across groups and thus has been vastly studied in the literature. It is only recently that a renewed special attention has been drawn to the study of contagion dynamics over higher-order interactions and over more general graph structures, like simplexes. Previous work on mean-field approximation scalar models of the simplicial SIS model has indicated that a new dynamical behavior domain, compared to the classical SIS model, appears due to the newly introduced higher order interaction terms: both a disease-free equilibrium and an endemic equilibrium co-exist and are both locally asymptotically stable. This paper formally establishes that bistability (as a new epidemiological behavior) also appears in the multi-group simplicial SIS model. We give sufficient conditions over the model's parameters for the appearance of this and the other behavioral domains present in the classical multi-group SIS model. We additionally provide an algorithm to compute the value of the endemic equilibrium and report numerical analysis of the transition from the disease-free domain to the bistable domain.

We develop two generalizations of contraction theory, namely, semi-contraction and weak-contraction theory. First, using the notion of semi-norm, we propose a geometric framework for semi-contraction theory. We introduce matrix semi-measures and characterize their properties. We show that the spectral abscissa of a matrix is the infimum over weighted semi-measures. For dynamical systems, we use the semi-measure of their Jacobian to characterize the contractivity properties of their trajectories. Second, for weakly contracting systems, we prove a dichotomy for the asymptotic behavior of their trajectories and novel sufficient conditions for convergence to an equilibrium. Third, we show that every trajectory of a doubly-contracting system, i.e., a system that is both weakly and semi-contracting, converges to an equilibrium point. Finally, we apply our results to various important network systems including affine averaging and affine flow systems, continuous-time distributed primal-dual algorithms, and networks of diffusively-coupled dynamical systems. For diffusively-coupled systems, the semi-contraction theory leads to a sufficient condition for synchronization that is sharper, in general, than previously-known tests.

In this note, we provide an overarching analysis of primal-dual dynamics associated to linear equality-constrained optimization problems using contraction analysis. For the well-known standard version of the problem: we establish convergence under convexity and the contracting rate under strong convexity. Then, for a canonical distributed optimization problem, we use partial contractivity to establish global exponential convergence of its primal-dual dynamics. As an application, we propose a new distributed solver for the least-squares problem with the same convergence guarantees. Finally, for time-varying versions of both centralized and distributed primal-dual dynamics, we exploit their contractive nature to establish bounds on their tracking error. To support our analyses, we introduce novel results on contraction theory.

We propose a novel network formation game that explains the emergence of various hierarchical structures in groups where self-interested or utility-maximizing individuals decide to establish or severe relationships of authority or collaboration among themselves. We consider two settings: we first consider individuals who do not seek the other party's consent when establishing a relationship and then individuals who do. For both settings, we formally relate the emerged hierarchical structures with the novel inclusion of well-motivated hierarchy promoting terms in the individuals' utility functions. We first analyze the game via a static analysis and characterize all the hierarchical structures that can be formed as its solutions. We then consider the game played dynamically under stochastic interactions among individuals implementing better-response dynamics and analyze the nature of the converged networks.

Structural balance is a classic property of signed graphs satisfying Heider's seminal axioms. Mathematical sociologists have studied balance theory since its inception in the 1040s. Recent research has focused on the development of dynamic models explaining the emergence of structural balance. In this paper, we introduce a novel class of parsimonious dynamic models for structural balance based on an interpersonal influence process. Our proposed models are gradient flows of an energy function, called the dissonance function, which captures the cognitive dissonance arising from violations of Heider's axioms. Thus, we build a new connection with the literature on energy landscape minimization. This gradient flow characterization allows us to study the transient and asymptotic behaviors of our model. We provide mathematical and numerical results describing the critical points of the dissonance function.

Building on a recent framework for distributionally robust optimization, we consider estimation of the inverse covariance matrix for multivariate data. We provide a novel notion of a Wasserstein ambiguity set specifically tailored to this estimation problem, leading to a tractable class of regularized estimators. Special cases include penalized likelihood estimators for Gaussian data, specifically the graphical lasso estimator. As a consequence of this formulation, the radius of the Wasserstein ambiguity set is directly related to the regularization parameter in the estimation problem. Using this relationship, the level of robustness of the estimation procedure can be shown to correspond to the level of confidence with which the ambiguity set contains a distribution with the population covariance. Furthermore, a unique feature of our formulation is that the radius can be expressed in closed-form as a function of the ordinary sample covariance matrix. Taking advantage of this finding, we develop a simple algorithm to determine a regularization parameter for graphical lasso, using only the bootstrapped sample covariance matrices, meaning that computationally expensive repeated evaluation of the graphical lasso algorithm is not necessary. Alternatively, the distributionally robust formulation can also quantify the robustness of the corresponding estimator if one uses an off-the-shelf method such as cross-validation. Finally, we numerically study the obtained regularization criterion and analyze the robustness of other automated tuning procedures used in practice.

We propose a signed network formation game, in which pairs of individuals strategically change the signs of the edges in a complete network. These individuals are members of a social network who strategically reduce cognitive dissonances by changing their interpersonal appraisals. We characterize the best-response dynamics for this game and prove that its implementation \pc{can} dynamically drive the network to a sociologically meaningful sign configuration called clustering balance. In this configuration, agents in the social network form one or more clusters that have positive relationships among their members but negative relationships among members of other clusters. In the past, various researchers in the fields of psycho-sociology, political science, and physics have looked at models that explain the generation of up to two clusters. Our work contributes to these fields by proposing a simple model that generates a broader class of signed networks., Comment: 15 pages, 3 figures

Much recent research on social networks has focused on the modeling and analysis of how opinions evolve as a function of interpersonal relationships. It is also of great interest to model and understand the implications of friendly and antagonistic relationships. In this paper, we propose a new, simple and intuitive model that incorporates the socio-psychological phenomenon of the boomerang effect in opinion dynamics. We establish that, under certain conditions on the structure of the signed network that corresponds to the so-called structural balance property, the opinions in the network polarize. Compared to other models in the literature, our model displays a richer and perhaps more intuitive behavior of the opinions when the social network does not satisfy structural balance. In particular, we analyze signed networks in which the opinions show persistent fluctuations (including the case of the so-called clustering balance)., Comment: 15 pages, 9 figures

Social balance theory describes allowable and forbidden configurations of the topologies of signed directed social appraisal networks. In this paper, we propose two discrete-time dynamical systems that explain how an appraisal network \textcolor{blue}{converges to} social balance from an initially unbalanced configuration. These two models are based on two different socio-psychological mechanisms respectively: the homophily mechanism and the influence mechanism. Our main theoretical contribution is a comprehensive analysis for both models in three steps. First, we establish the well-posedness and bounded evolution of the interpersonal appraisals. Second, we fully characterize the set of equilibrium points; for both models, each equilibrium network is composed by an arbitrary number of complete subgraphs satisfying structural balance. Third, we establish the equivalence among three distinct properties: non-vanishing appraisals, convergence to all-to-all appraisal networks, and finite-time achievement of social balance. In addition to theoretical analysis, Monte Carlo validations illustrates how the non-vanishing appraisal condition holds for generic initial conditions in both models. Moreover, numerical comparison between the two models indicate that the homophily-based model might be a more universal explanation for the formation of social balance. Finally, adopting the homophily-based model, we present numerical results on the mediation and globalization of local conflicts, the competition for allies, and the asymptotic formation of a single versus two factions.