104 research outputs found
Analyzing the opinion dynamics models discrete & continuous
No full textIn this thesis we analyze some of the opinion dynamics in both discrete and continuous
cases. In the discrete case, we will find some criteria under which we can say more about
the behavior of the dynamics such as convergence of the agents to the same opinion, or
consensus. For this purpose, we first consider the agent-based bounded confidence model of
the Hegselmann-Krause where multiple agents want to agree on a common scalar, or they
can be divided in several subgroups, with each subgroup having its own agreement value.
In this model, we restrict ourselves to the case when all the agents have the same bound of
confidence, often referred to as homogeneous case. We are interested to study the number
of iterations which is enough for the termination of the Hegselmann-Krause algorithm. In
other words, we want to give an upper bound on the number of iterations which guarantees
the termination of the algorithm independently of reaching a consensus or not. Assuming
the consensus is achieved in the Hegselmann-Krause model, we first give an upper bound on
the number of iterations and then we provide another upper bound without any assumption.
In chapter 3 we use some analysis based on Lyapunov function theory to improve our
upper bound substantially. In our analysis we use two differnt type of Lyapunov functions
which each of them gives us a polynomial upper bound for the termination time. In chapter
4 we consider the Hegselmann-Krause model in higher dimensions. We will see that in higher
dimensions we don’t have lots of nice properties which exist in the scalar case. Then, we
will find some upper bounds for the termination time. Also, at the end we will consider
an extension of the Hegselmann-Krause model to continuous case such that the time is
discrete but the density of the agents is continuous over the real line. In chapter 5 we use
the matrix representation for the discrete dynamics and we provide some conditions on a
chain of stochastic matrices based on their decomposition by permutation matrices such
that it can guarantee the convergence of the chain to a consensus matrix. Also, we provide
some examples and one necessary condition for finite time convergence of an especial case
of averaging gossip algorithms.Item withdrawn by Mark Zulauf ([email protected]) on 2012-04-27T20:03:48Z
Item was in collections:
University of Illinois Theses & Dissertations (ID: 1)
No. of bitstreams: 2
Etesami_Seyed Rasoul.pdf.pdf: 1703555 bytes, checksum: 3269c8b435d5742d75c71a0283e5678e (MD5)
Etesami_Seyed Rasoul.pdf: 1703555 bytes, checksum: 3269c8b435d5742d75c71a0283e5678e (MD5)Made available in DSpace on 2012-05-22T00:29:26Z (GMT). No. of bitstreams: 2
Etesami_SeyedRasoul.pdf: 1703555 bytes, checksum: 3269c8b435d5742d75c71a0283e5678e (MD5)
license.txt: 4063 bytes, checksum: 8c446c9b94acf8e07ed29e07f39815ba (MD5
Subgradient methods for convex minimization
No full textThesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002.Includes bibliographical references (p. 169-174).This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.Many optimization problems arising in various applications require minimization of an objective cost function that is convex but not differentiable. Such a minimization arises, for example, in model construction, system identification, neural networks, pattern classification, and various assignment, scheduling, and allocation problems. To solve convex but not differentiable problems, we have to employ special methods that can work in the absence of differentiability, while taking the advantage of convexity and possibly other special structures that our minimization problem may possess. In this thesis, we propose and analyze some new methods that can solve convex (not necessarily differentiable) problems. In particular, we consider two classes of methods: incremental and variable metric.by Angelia NediÄ.Ph.D
Stochastic approximation schemes for stochastic optimization and variational problems: adaptive steplengths, smoothing, and regularization
No full textStochastic approximation (SA) methods, first proposed by Robbins and Monro in 1951 for root- finding problems,
have been widely used in the literature to solve problems arising from stochastic convex optimization,
stochastic Nash games and more recently stochastic variational inequalities. Several challenges arise in the
development of SA schemes. First, little guidance is provided on the choice of the steplength sequence.
Second, most variants of these schemes in optimization require differentiability of the objective function and
Lipschitz continuity of the gradient. Finally, strong convexity of the objective function is another requirement
that is a strong assumption to hold. Motivated by these challenges, this thesis focuses on studying
research challenges related to the SA methods in three different areas: (i) steplengths, (ii) smoothing, and
(iii) regularization.
The first part of this thesis pertains to solving strongly convex differentiable stochastic optimization
problems using SA methods. The performance of standard SA implementations can vary significantly based
on the choice of the steplength sequence, and in general, little guidance is provided about good choices.
Motivated by this gap, we present two adaptive steplength schemes equipped with convergence theory that
aim to overcome some of the reliance on user-specefi c parameters. Of these, the first scheme, referred to
as a recursive steplength stochastic approximation (RSA) scheme, minimizes the error bounds to derive a
rule that expresses the steplength at a given iteration as a simple function of the steplength at the previous
iteration and certain problem parameters. The second scheme, termed as a cascading steplength stochastic
approximation (CSA) scheme, maintains the steplength sequence as a piecewise-constant decreasing function
with the reduction in the steplength occurring when a suitable error threshold is met. We then allow for
nondiff erentiable objectives but with bounded subgradients over a certain domain. In such a regime, we
propose a local smoothing technique, based on random local perturbations of the objective function that
leads to a differentiable approximation of the function and a Lipschitzian property for the gradient of
the approximation. This facilitates the development of an adaptive steplength stochastic approximation
framework, which now requires sampling in the product space of the original measure and the artifi cally
introduced distribution. Motivated by problems arising in decentralized control problems and non-cooperative Nash games, in
the second part of this thesis, we consider a class of strongly monotone Cartesian variational inequality
problems, where the mappings either contain expectations or their evaluations are corrupted by error. Such
complications are captured under the umbrella of Cartesian stochastic variational inequality (CSVI) problems
and we consider solving such problems via SA schemes. Spece fically, along similar directions to the RSA
scheme, a stepsize rule is constructed for strongly monotone stochastic variational inequality problems. The
proposed scheme is seen to produce sequences that are guaranteed to converge almost surely to the unique
solution of the problem. To cope with networked multi-agent generalizations, we provide requirements under
which independently chosen steplength rules still possess desirable almost-sure convergence properties. To
address non-smoothness, we consider a regime where Lipschitz constants on the map are either unavailable or
di fficult to derive. Here, we generalize the aforementioned smoothing scheme for deriving an approximation
of the original mapping, which is then shown to be Lipschitz continuous with a prescribed constant. Using
this technique, we introduce a locally randomized SA algorithm and provide almost sure convergence theory
for the resulting sequence of iterates to an approximate solution of the original CSVI problem.
In the third part of this thesis, we consider a stochastic variational inequality (SVI) problem with a
continuous and monotone mapping over a compact and convex set. Traditionally, stochastic approximation
schemes for SVIs have relied on strong monotonicity and Lipschitzian properties of the underlying map. We
present a regularized smoothed SA (RSSA) scheme wherein stepsize, smoothing, and regularization parameters
are updated after every iteration. Under suitable assumptions on the sequences, we show that the
algorithm generates iterates that converge to a solution the SVI problem in an almost-sure sense. Additionally,
we provide rate estimates that relate iterates to their counterparts derived from the Tikhonov trajectory
associated with a deterministic problem.Item withdrawn by Mark Zulauf ([email protected]) on 2013-07-12T17:43:31Z
Item was in collections:
University of Illinois Theses & Dissertations (ID: 1)
No. of bitstreams: 1
Yousefian_Seyed Farzad.pdf: 2917761 bytes, checksum: 9f0742a5df5f02e27406bb4a39e753b3 (MD5)Made available in DSpace on 2013-08-22T16:38:34Z (GMT). No. of bitstreams: 2
Seyed Farzad_Yousefian.pdf: 2749924 bytes, checksum: fd8c041edf20b7b6d2dc746128bc573f (MD5)
license.txt: 4072 bytes, checksum: 1ada8fcaac5476b47a53dbf2cc01efce (MD5
Value function approximation architectures for neuro-dynamic programming
No full textNeuro-dynamic programming is a class of powerful techniques for approximating the solution to dynamic programming equations. In their most computationally attractive formulations, these techniques provide the approximate solution only within a prescribed finite-dimensional function class. Thus, the question that always arises is how should the function class be chosen?
In this dissertation, we first propose an approach using the solutions to associated fluid and diffusion approximations. In order to evaluate this approach, we establish bounds on the approximation errors.
Next, we propose a novel parameterized Q-learning algorithm. Q-learning is a model-free method to compute the Q-function
associated with an optimal policy, based on
observations of states and actions. If the size of a state or a policy space is too large, Q-learning is often not very practical because there are too many Q-function values to update. One way to address this problem is to approximate the Q-function within a function class. However, such methods often require an explicit model of the system, such as the split sampling method introduced by Borkar. The proposed algorithm is a reinforcement learning (RL) method, in which case the system dynamics are not known. This method is designed based on using approximations of the transition kernel of the Markov decision process (MDP).
Lastly, we apply the proposed results of value function approximation techniques to several applications. In the power management model, we focus on the processor speed control problem to balance the performance and energy usage. Then we extend the results to the load balancing and the power management problem of geographically distributed data centers with grid regulation. In the cross-layer wireless control problem, the network utility maximization (NUM) and adaptive modulation (AM) are combined to balance the network performance and transmission power. In these applications, we show how to model the real problems by using the MDP model with reasonable assumptions and necessary approximations. Approximations of the value function are obtained for specific models, and evaluated by getting bounds for the errors. These approximate solutions are then used to construct basis functions for learning algorithms in the simulations.Item withdrawn by Laura Spradlin ([email protected]) on 2013-12-02T14:33:51Z
Item was in collections:
University of Illinois Theses & Dissertations (ID: 1)
No. of bitstreams: 1
Chen_Wei.pdf: 7488417 bytes, checksum: 8821f75e096c84203444be0e87ffaed1 (MD5)Made available in DSpace on 2014-01-16T18:26:02Z (GMT). No. of bitstreams: 2
Wei_Chen.pdf: 7488417 bytes, checksum: 8821f75e096c84203444be0e87ffaed1 (MD5)
license.txt: 4058 bytes, checksum: a1abb7c4bbdb0836afe5bb4e3873ae50 (MD5)Item marked as restricted to the 'Administrator' Group (id=1) by Seth Robbins ([email protected]) on 2014-01-16T18:27:35Z
Item is restricted until 2016-01-16T18:27:27ZRestriction data tranferred 2014-07-01T11:36:47-05:00
Original Data
Group with Access Administrator
Release Date: 2016-01-16 12:27:27 UTC
Reason: Author requested closed access (OA after 2yrs) in Vireo ETD systemLimited Restriction Lifted for Item 46928 on 2016-01-16T11:02:04Z
Accelerating Distributed Nash Equilibrium Seeking
No full textThis work proposes a novel distributed approach for computing a Nash
equilibrium in convex games with restricted strongly monotone pseudo-gradients.
By leveraging the idea of the centralized operator extrapolation method
presented in [4] to solve variational inequalities, we develop the algorithm
converging to Nash equilibria in games, where players have no access to the
full information but are able to communicate with neighbors over some
communication graph. The convergence rate is demonstrated to be geometric and
improves the rates obtained by the previously presented procedures seeking Nash
equilibria in the class of games under consideration
New model-based methods for non-differentiable optimization
No full textModel-based optimization methods are effective for solving optimization problems with little structure, such as convexity and differentiability. Such algorithms iteratively find candidate solutions by generating samples from a parameterized probabilistic model on the solution space, and update the parameter of the probabilistic model based on the objective function evaluations. This dissertation explores new model-based optimization methods, and mainly consists of three topics.
The first topic of the dissertation proposes two new model-based algorithms for discrete optimization, discrete gradient-based adaptive stochastic search (discrete-GASS) and annealing gradient-based adaptive stochastic search (annealing-GASS), under the framework of gradient-based adaptive stochastic search (GASS), where the parameter of the probabilistic model is updated based on a direct gradient method. The first algorithm, discrete-GASS, converts the discrete optimization problem to a continuous problem on the parameter space of a family of independent discrete distributions, and applies a gradient-based method to find the optimal parameter such that the corresponding distribution has the best capability to generate optimal solution(s) to the original discrete problem. The second algorithm, annealing-GASS, uses Boltzmann distribution as the parameterized probabilistic model, and derives a gradient-based temperature schedule, which changes adaptively with respect to the current performance of the algorithm, for updating the Boltzmann distribution. We prove the convergence of the two proposed methods, and conduct numerical experiments to compare these two methods as well as some other existing methods.
The second topic of the dissertation proposes a framework of population model-based optimization (PMO) in order to better capture the multi-modality of the objective functions than the traditional model-based methods which use only a single model at every iteration. This PMO framework uses a population of models at every iteration with an adaptive mechanism to propagate the population over iterations. The adaptive mechanism is derived from estimating the optimal parameter of the probabilistic model in a Bayesian manner, and thus provides a proper way to determine the diversity in the population of the models. We provide theoretical justification on the convergence of this framework by showing that the posterior distribution of the parameter asymptotically converges to a degenerate distribution concentrating on the optimal parameter. Under this framework, we develop two practical algorithms by incorporating sequential Monte Carlo methods, and carry out numerical experiments to illustrate their performance.
The last topic of the dissertation considers simulation optimization, where the objective function cannot be evaluated exactly and must be estimated by stochastic simulation. The idea of model-based methods for deterministic optimization is extended to stochastic optimization. We propose two algorithms: approximate Bayesian computation simulation optimization (ABC-SO) and its extension approximate Bayesian computation simulation optimization with multiple function evaluations (ABCM-SO). These algorithms view the simulation optimization problem as an estimation problem, and use the approximate Bayesian computation (ABC) technique to estimate the optimal solution. We carry out numerical experiments of the proposed algorithms, and compare them with gradient-based adaptive stochastic search for simulation optimization (GASSO), and cross-entropy method with optimal computing budget allocation (CE-OCBA).Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2015-07-22 without embargo termsThe student, Xi Chen, accepted the attached license on 2015-04-11 at 17:27.The student, Xi Chen, submitted this Dissertation for approval on 2015-04-11 at 17:35.This Dissertation was approved for publication on 2015-04-14 at 11:38.DSpace SAF Submission Ingestion Package generated from Vireo submission #7827 on 2015-07-22 at 10:31:46Made available in DSpace on 2015-07-22T22:16:38Z (GMT). No. of bitstreams: 2
CHEN-DISSERTATION-2015.pdf: 3691806 bytes, checksum: 7c19e63d512bbe4745ea50a5c04b2b33 (MD5)
LICENSE.txt: 4204 bytes, checksum: 1c562c69b328a60d3c9c43c3f8074e88 (MD5)
Previous issue date: 2015-04-1
On the resolution of misspecification in stochastic optimization, variational inequality, and game-theoretic problems
No full textTraditionally, much of the research in the field of optimization algorithms has assumed that problem parameters are correctly specified. Recent efforts under the robust optimization framework have relaxed this assumption by allowing unknown parameters to vary in a prescribed uncertainty set and by subsequently solving for a worst-case solution. This dissertation considers a rather different approach in which the unknown or misspecified parameter is a solution to a suitably defined (stochastic) learning problem based on
having access to a set of samples. Practical approaches in resolving such a set of coupled problems have been either sequential or direct variational approaches. In the case of the former, this entails the following steps: (i) a solution to the learning problem for parameters is first obtained; and (ii) a solution is obtained to the associated parametrized computational problem by using (i). Such avenues prove difficult to adopt particularly since the learning process has to be terminated finitely and consequently, in large-scale or stochastic instances, sequential approaches may often be corrupted by error. On the other hand, a variational approach requires that the problem may be recast as a possibly non-monotone stochastic variational inequality problem; but there are no known first-order (stochastic) schemes currently available for the solution of such
problems. Motivated by these challenges, this thesis focuses on studying joint schemes of optimization and learning in three settings: (i) misspecified stochastic optimization and variational inequality problems, (ii)
misspecified stochastic Nash games, (iii) misspecified Markov decision processes.
In the first part of this thesis, we present a coupled stochastic approximation scheme which simultaneously solves both the optimization and the learning problems. The obtained schemes are shown to be equipped with almost sure convergence properties in regimes when the function is either strongly convex as well as merely convex. Importantly, the scheme displays the optimal rate for strongly convex problems while in merely convex regimes, through an averaging approach, we quantify the degradation associated with learning
by noting that the error in function value after steps is , rather than when is available. Notably, when the averaging window is modified suitably, it can be see that the original rate
of is recovered. Additionally, we consider an online counterpart of the misspecified optimization problem and provide a non-asymptotic bound on the average regret with respect to an offline counterpart. We also extend these statements to a class of stochastic variational inequality problems, an object that unifies stochastic convex optimization problems and a range of stochastic equilibrium problems. Analogous almost-sure convergence statements are provided in strongly monotone and merely monotone regimes, the latter facilitated by using an iterative Tikhonov regularization. In the merely monotone regime, under a
weak-sharpness requirement, we quantify the degradation associated with learning and show that expected
error associated with is .
In the second part of this thesis, we present schemes for computing equilibria to two classes of convex
stochastic Nash games complicated by a parametric misspecification, a natural concern in the control of large-
scale networked engineered system. In both schemes, players learn the equilibrium strategy while resolving
the misspecification: (1) Stochastic Nash games: We present a set of coupled stochastic approximation
distributed schemes distributed across agents in which the first scheme updates each agent’s strategy via a projected (stochastic) gradient step while the second scheme updates every agent’s belief regarding its misspecified parameter using an independently specified learning problem. We proceed to show that the produced sequences converge to the true equilibrium strategy and the true parameter in an almost sure sense. Surprisingly, convergence in the equilibrium strategy achieves the optimal rate of convergence in a mean-squared sense with a quantifiable degradation in the rate constant; (2) Stochastic Nash-Cournot games with unobservable aggregate output: We refine (1) to a Cournot setting where we assume that the tuple of strategies is unobservable while payoff functions and strategy sets are public knowledge through a common knowledge assumption. By utilizing observations of noise-corrupted prices, iterative fixed-point schemes are developed, allowing for simultaneously learning the equilibrium strategies and the misspecified parameter in an almost-sure sense.
In the third part of this thesis, we consider the solution of a finite-state infinite horizon Markov Decision Process (MDP) in which both the transition matrix and the cost function are misspecified, the latter in a parametric sense. We consider a data-driven regime in which the learning problem is a stochastic
convex optimization problem that resolves misspecification. Via such a framework, we make the following
contributions: (1) We first show that a misspecified value iteration scheme converges almost surely to its
true counterpart and the mean-squared error after iterations is ; (2) An analogous asymptotic almost-sure convergence statement is provided for misspecified policy iteration; and (3) Finally, we present a constant steplength misspecified Q-learning scheme and show that a suitable error metric is + after K iterations where δ is a bound on the steplength.Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-03-02 without embargo termsThe student, Hao Jiang, accepted the attached license on 2015-12-01 at 13:09.The student, Hao Jiang, submitted this Dissertation for approval on 2015-12-01 at 13:51.This Dissertation was approved for publication on 2015-12-02 at 08:56.DSpace SAF Submission Ingestion Package generated from Vireo submission #8892 on 2016-03-02 at 12:50:50Made available in DSpace on 2016-03-02T19:34:08Z (GMT). No. of bitstreams: 2
JIANG-DISSERTATION-2015.pdf: 1534485 bytes, checksum: b101bcaca6d486faf0105fc0e2313e12 (MD5)
LICENSE.txt: 4206 bytes, checksum: 38cf4e95a2c476e69bdfbcbaa5a7dbd6 (MD5)
Previous issue date: 2015-12-0
Potential-based analysis of social, communication, and distributed networks
No full textIn recent years, there has been a wide range of studies on the role of social and distributed networks in various disciplinary areas. In particular, availability of large amounts of data from online social networks and advances in control of distributed systems have drawn the attention of many researchers to exploit the connection between evolutionary behaviors in social, communication and distributed networks. In this thesis, we first revisit several well-known types of social and distributed networks and review some relevant results from the literature. Building on this, we present a set of new results related to four different types of problems, and identify several directions for future research. The study undertaken and the approaches adopted allow us to analyze the evolution of certain types of social and distributed networks and also to identify local and global patterns of their dynamics using some novel potential-theoretic techniques.
Following the introduction and preliminaries, we focus on analyzing a specific type of distributed algorithm for quantized consensus known as an unbiased quantized algorithm where a set of agents interact locally in a network in order to reach a consensus. We provide tight expressions for the expected convergence time of such dynamics over general static and time-varying networks. Following this, we introduce new protocols using a special class of Markov chains known as Metropolis chains and obtain the fastest (as of today) randomized quantized consensus protocol. The bounds provided here considerably improve the state of the art over static and dynamic networks.
We make a bridge between two classes of problems, namely distributed control problems and game problems. We analyze a class of distributed averaging dynamics known as Hegselmann-Krause opinion dynamics. Modeling such dynamics as a non-cooperative game problem, we elaborate on some of the evolutionary properties of such dynamics. In particular, we answer an open question related to the termination time of such dynamics by connecting the convergence time to the spectral gap of the adjacency matrices of underlying dynamics. This not only allows us to improve the best known upper bound, but also removes the dependency of termination time from the dimension of the ambient space. The approach adopted here can also be leveraged to connect the rate of increase of a so-called kinetic-s-energy associated with multi-agent systems to the spectral gap of their underlying dynamics.
We describe a richer class of distributed systems where the agents involved in the network act in a more strategic manner. More specifically, we consider a class of resource allocation games over networks and study their evolution to some final outcomes such as Nash equilibria. We devise some simple distributed algorithms which drive the entire network to a Nash equilibrium in polynomial time for dense and hierarchical networks. In particular, we show that such games benefit from having low price of anarchy, and hence, can be used to model allocation systems which suffer from lack of coordination. This fact allows us to devise a distributed approximation algorithm within a constant gap of any pure-strategy Nash equilibrium over general networks.
Subsequently we turn our attention to an important problem related to competition over social networks. We establish a hardness result for searching an equilibrium over a class of games known as competitive diffusion games, and provide some necessary conditions for existence of a pure-strategy Nash equilibrium in such games. In particular, we provide some concentration results related to the expected utility of the players over random graphs.
Finally, we discuss some future directions by identifying several interesting problems and justify the importance of the underlying problems.Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-03-02 without embargo termsThe student, Seyed Rasoul Etesami, accepted the attached license on 2015-11-30 at 17:12.The student, Seyed Rasoul Etesami, submitted this Dissertation for approval on 2015-11-30 at 17:31.This Dissertation was approved for publication on 2015-12-02 at 08:07.DSpace SAF Submission Ingestion Package generated from Vireo submission #8881 on 2016-03-02 at 12:50:47Made available in DSpace on 2016-03-02T19:34:05Z (GMT). No. of bitstreams: 2
ETESAMI-DISSERTATION-2015.pdf: 3241013 bytes, checksum: ba0ca7233004c5a960f583a48f244f50 (MD5)
LICENSE.txt: 4217 bytes, checksum: cb541990d6b775d712d143dffcf7d4cd (MD5)
Previous issue date: 2015-12-0
Differentially-private Distributed Algorithms for Aggregative Games with Guaranteed Convergence
No full textThe distributed computation of a Nash equilibrium in aggregative games is
gaining increased traction in recent years. Of particular interest is the
mediator-free scenario where individual players only access or observe the
decisions of their neighbors due to practical constraints. Given the
competitive rivalry among participating players, protecting the privacy of
individual players becomes imperative when sensitive information is involved.
We propose a fully distributed equilibrium-computation approach for aggregative
games that can achieve both rigorous differential privacy and guaranteed
computation accuracy of the Nash equilibrium. This is in sharp contrast to
existing differential-privacy solutions for aggregative games that have to
either sacrifice the accuracy of equilibrium computation to gain rigorous
privacy guarantees, or allow the cumulative privacy budget to grow unbounded,
hence losing privacy guarantees, as iteration proceeds. Our approach uses
independent noises across players, thus making it effective even when
adversaries have access to all shared messages as well as the underlying
algorithm structure. The encryption-free nature of the proposed approach, also
ensures efficiency in computation and communication. The approach is also
applicable in stochastic aggregative games, able to ensure both rigorous
differential privacy and guaranteed computation accuracy of the Nash
equilibrium when individual players only have stochastic estimates of their
pseudo-gradient mappings. Numerical comparisons with existing counterparts
confirm the effectiveness of the proposed approach.Comment: arXiv admin note: text overlap with arXiv:2202.0111
- …
