BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Jinlong Lei

Jinlong Lei appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCComputer Science and Game TheoryMachine LearningMultiagent Systems

Catalog footprint

What is connected

11works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2022arXiv

Distributed coordination for seeking the optimal Nash equilibrium of aggregative games

This paper aims to design a distributed coordination algorithm for solving a multi-agent decision problem with a hierarchical structure. The primary goal is to search the Nash equilibrium of a noncooperative game such that each player has no incentive to deviate from the equilibrium under its private objective. Meanwhile, the agents can coordinate to optimize the social cost within the set of Nash equilibria of the underlying game. Such an optimal Nash equilibrium problem can be modeled as a distributed optimization problem with variational inequality constraints. We consider the scenario where the objective functions of both the underlying game and social cost optimization problem have a special aggregation structure. Since each player only has access to its local objectives while cannot know all players' decisions, a distributed algorithm is highly desirable. By utilizing the Tikhonov regularization and dynamical averaging tracking technique, we propose a distributed coordination algorithm by introducing an incentive term in addition to the gradient-based Nash equilibrium seeking, so as to intervene players' decisions to improve the system efficiency. We prove its convergence to the optimal Nash equilibrium of a monotone aggregative game with simulation studies.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Distributed Variable Sample-size Stochastic Optimization with Fixed Step-sizes

The paper considers distributed stochastic optimization over randomly switching networks, where agents collaboratively minimize the average of all agents' local expectation-valued convex cost functions. Due to the stochasticity in gradient observations, distributedness of local functions, and randomness of communication topologies, distributed algorithms with a convergence guarantee under fixed step-sizes have not been achieved yet. This work incorporates variance reduction scheme into the distributed stochastic gradient tracking algorithm, where local gradients are estimated by averaging across a variable number of sampled gradients. With an identically and independently distributed (i.i.d.) random network, we show that all agents' iterates converge almost surely to the same optimal solution under fixed step-sizes. When the global cost function is strongly convex and the sample size increases at a geometric rate, we prove that the iterates geometrically converge to the unique optimal solution, and establish the iteration, oracle, and communication complexity. The algorithm performance including rate and complexity analysis are further investigated with constant step-sizes and a polynomially increasing sample size. Finally, the empirical algorithm performance are illustrated with numerical examples.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Dynamical Primal-Dual Accelerated Method with Applications to Network Optimization

This paper develops a continuous-time primal-dual accelerated method with an increasing damping coefficient for a class of convex optimization problems with affine equality constraints. This paper analyzes critical values for parameters in the proposed method and prove that the rate of convergence in terms of the duality gap function is $O(\tfrac{1}{t^2})$ by choosing suitable parameters. As far as we know, this is the first continuous-time primal-dual accelerated method that can obtain the optimal rate. Then this work applies the proposed method to two network optimization problems, a distributed optimization problem with consensus constraints and a distributed extended monotropic optimization problem, and obtains two variant distributed algorithms. Finally, numerical simulations are given to demonstrate the efficacy of the proposed method.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

No-regret learning for repeated non-cooperative games with lossy bandits

This paper considers no-regret learning for repeated continuous-kernel games with lossy bandit feedback. Since it is difficult to give the explicit model of the utility functions in dynamic environments, the players' action can only be learned with bandit feedback. Moreover, because of unreliable communication channels or privacy protection, the bandit feedback may be lost or dropped at random. Therefore, we study the asynchronous online learning strategy of the players to adaptively adjust the next actions for minimizing the long-term regret loss. The paper provides a novel no-regret learning algorithm, called Online Gradient Descent with lossy bandits (OGD-lb). We first give the regret analysis for concave games with differentiable and Lipschitz utilities. Then we show that the action profile converges to a Nash equilibrium with probability 1 when the game is also strictly monotone. We further provide the mean square convergence rate $\mathcal{O}\left(k^{-2\min\{β, 1/6\}}\right)$ when the game is $β-$ strongly monotone. In addition, we extend the algorithm to the case when the loss probability of the bandit feedback is unknown, and prove its almost sure convergence to Nash equilibrium for strictly monotone games. Finally, we take the resource management in fog computing as an application example, and carry out numerical experiments to empirically demonstrate the algorithm performance.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

No-Regret Learning in Network Stochastic Zero-Sum Games

No-regret learning has been widely used to compute a Nash equilibrium in two-person zero-sum games. However, there is still a lack of regret analysis for network stochastic zero-sum games, where players competing in two subnetworks only have access to some local information, and the cost functions include uncertainty. Such a game model can be found in security games, when a group of inspectors work together to detect a group of evaders. In this paper, we propose a distributed stochastic mirror descent (D-SMD) method, and establish the regret bounds $O(\sqrt{T})$ and $O(\log T)$ in the expected sense for convex-concave and strongly convex-strongly concave costs, respectively. Our bounds match those of the best known first-order online optimization algorithms. We then prove the convergence of the time-averaged iterates of D-SMD to the set of Nash equilibria. Finally, we show that the actual iterates of D-SMD almost surely converge to the Nash equilibrium in the strictly convex-strictly concave setting.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Asynchronous Variance-reduced Block Schemes for Composite Nonconvex Stochastic Optimization: Block-specific Steplengths and Adapted Batch-sizes

We consider the minimization of a sum of an expectation-valued coordinate-wise $L_i$-smooth nonconvex function and a nonsmooth block-separable convex regularizer. We propose an asynchronous variance-reduced algorithm, where in each iteration, a single block is randomly chosen to update its estimates by a proximal variable sample-size stochastic gradient scheme, while the remaining blocks are kept invariant. Notably, each block employs a steplength that is in accordance with its block-specific Lipschitz constant while block-specific batch-sizes are random variables updated at a rate that grows either at a geometric or polynomial rate with the (random) number of times that block is selected. We show that every limit point for almost every sample path is a stationary point and establish the ergodic non-asymptotic rate $\mathcal{O}(1/K) $. Iteration and oracle complexity to obtain an $ε$-stationary point are shown to be $\mathcal{O}(1/ε)$ and $\mathcal{O}(1/ε^2)$, respectively. Furthermore, under a $ μ$-proximal Polyak-Łojasiewicz (PL) condition with the batch size increasing at a geometric rate, we prove that the suboptimality diminishes at a {\em geometric} rate, the {\em optimal} deterministic rate while iteration and oracle complexity to obtain an $ε$-optimal solution are proven to be $\mathcal{O}( (L_{\rm max}/μ) \ln(1/ε))$ and $\mathcal{O}\left((L_{\rm ave}/μ) (1/ε)^{1+c} \right)$ with $c\geq 0$, respectively. In pursuit of less aggressive sampling rates, when the batch sizes increase at a polynomial rate of degree $v \geq 1$, suboptimality decays at a corresponding polynomial rate while the iteration and oracle complexity to obtain an $ε-$optimal solution are provably $\mathcal{O} ( v(1/ε)^{1/v})$ and $\mathcal{O} \left(e^v v^{2v+1}(1/ε)^{1+1/v}\right)$, respectively.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Distributed Variable Sample-Size Gradient-response and Best-response Schemes for Stochastic Nash Equilibrium Problems over Graphs

This paper considers a stochastic Nash game in which each player minimizes an expectation valued composite objective. We make the following contributions. (I) Under suitable monotonicity assumptions on the concatenated gradient map, we derive optimal rate statements and oracle complexity bounds for the proposed variable sample-size proximal stochastic gradient-response (VS-PGR) scheme when the sample-size increases at a geometric rate. If the sample-size increases at a polynomial rate of degree $v > 0$, the mean-squared errordecays at a corresponding polynomial rate while the iteration and oracle complexities to obtain an $ε$-NE are $\mathcal{O}(1/ε^{1/v})$ and $\mathcal{O}(1/ε^{1+1/v})$, respectively. (II) We then overlay (VS-PGR) with a consensus phase with a view towards developing distributed protocols for aggregative stochastic Nash games. In the resulting scheme, when the sample-size and the consensus steps grow at a geometric and linear rate, computing an $ε$-NE requires similar iteration and oracle complexities to (VS-PGR) with a communication complexity of $\mathcal{O}(\ln^2(1/ε))$; (III) Under a suitable contractive property associated with the proximal best-response (BR) map, we design a variable sample-size proximal BR (VS-PBR) scheme, where each player solves a sample-average BR problem. Akin to (I), we also give the rate statements, oracle and iteration complexity bounds. (IV) Akin to (II), the distributed variant achieves similar iteration and oracle complexities to the centralized (VS-PBR) with a communication complexity of $\mathcal{O}(\ln^2(1/ε))$ when the communication rounds per iteration increase at a linear rate. Finally, we present some preliminary numerics to provide empirical support for the rate and complexity statements.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Linearly Convergent Algorithm with Variance Reduction for Distributed Stochastic Optimization

This paper considers a distributed stochastic strongly convex optimization, where agents connected over a network aim to cooperatively minimize the average of all agents' local cost functions. Due to the stochasticity of gradient estimation and distributedness of local objective, fast linearly convergent distributed algorithms have not been achieved yet. This work proposes a novel distributed stochastic gradient tracking algorithm with variance reduction, where the local gradients are estimated by an increasing batch-size of sampled gradients. With an undirected connected communication graph and a geometrically increasing batch-size, the iterates are shown to converge in mean to the optimal solution at a geometric rate (achieving linear convergence). The iteration, communication, and oracle complexity for obtaining an $ε$-optimal solution are established as well. Particulary, the communication complexity is $\mathcal{O}(\ln (1/ε))$ while the oracle complexity (number of sampled gradients) is $\mathcal{O}(1/ε^2)$, which is of the same order as that of centralized approaches. Hence, the proposed scheme is communication-efficient without requiring extra sampled gradients. Numerical simulations are given to demonstrate the theoretic results.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Asymptotic Properties of Primal-Dual Algorithm for Distributed Stochastic Optimization Over Random Networks

This paper studies a distributed stochastic optimization problem over random networks with imperfect communications subject to a global constraint, which is the intersection of local constraint sets assigned to agents. The global cost function is the sum of local cost functions, each of which is the expectation of a random cost function. By incorporating the augmented Lagrange technique with the projection method, a stochastic approximation based distributed primal-dual algorithm is proposed to solve the problem. Each agent updates its estimate by using the local observations and the information derived from neighbors. For the constrained problem, the estimates are first shown to be bounded almost surely (a.s.), and then are proved to converge to the optimal solution set a.s. Furthermore, the asymptotic normality and efficiency of the algorithm are addressed for the unconstrained case. The results demonstrate the influence of random networks, communication noises, and gradient errors on the performance of the algorithm. Finally, numerical simulations demonstrate the theoretic results.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Distributed Resource Allocation Over Random Networks Based on Stochastic Approximation

In this paper, a stochastic approximation (SA) based distributed algorithm is proposed to solve the resource allocation (RA) with uncertainties. In this problem, a group of agents cooperatively optimize a separable optimization problem with a linear network resource constraint and allocation feasibility constraints, where the global objective function is the sum of agents' local objective functions. Each agent can only get noisy observations of its local function's gradient and its local resource, which cannot be shared by other agents or transmitted to a center. Moreover, there are communication uncertainties such as time-varying topologies (described by random graphs) and additive channel noises. To solve the RA, we propose an SA-based distributed algorithm, and prove that agents can collaboratively achieve the optimal allocation with probability one by virtue of ordinary differential equation (ODE) method for SA. Finally, simulations related to the demand response management in power systems verify the effectiveness of the proposed algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Primal-Dual Algorithm for Distributed Constrained Optimization

The paper studies a distributed constrained optimization problem, where multiple agents connected in a network collectively minimize the sum of individual objective functions subject to a global constraint being an intersection of the local constraint sets assigned to the agents. Based on the augmented Lagrange method, a distributed primal-dual algorithm with a projection operation included is proposed to solve the problem. It is shown that with appropriately chosen constant step size, the local estimates derived at all agents asymptotically reach a consensus at an optimal solution. In addition, the value of the cost function at the time-averaged estimate converges with rate $O(\frac{1}{k})$ to the optimal value for the unconstrained problem. By these properties the proposed primal-dual algorithm is distinguished from the existing algorithms for distributed constrained optimization. The theoretical analysis is justified by numerical simulations.

0 citations0 reviewsNo code linkedOpen access