Search ResultsShowing 1-20 of 29
-
arXiv:2412.02682 (Published 2024-12-03)
The Asymptotic Behavior of Attention in Transformers
A key component of transformers is the attention mechanism orchestrating how each token influences the propagation of every other token through a transformer. In this paper we provide a rigorous, mathematical analysis of the asymptotic properties of attention in transformers. Although we present several results based on different assumptions, all of them point to the same conclusion, all tokens asymptotically converge to each other, a phenomenon that has been empirically reported in the literature. Our findings are carefully compared with existing theoretical results and illustrated by simulations and experimental studies using the GPT-2 model.
-
arXiv:2411.17656 (Published 2024-11-26)
Asymptotic behavior of the Arrow-Hurwicz differential system with Tikhonov regularization
Categories: math.OCIn a real Hilbert space setting, we investigate the asymptotic behavior of the solutions of the classical Arrow-Hurwicz differential system combined with Tikhonov regularizing terms. Under some newly proposed conditions on the Tikhonov terms involved, we show that the solutions of the regularized Arrow-Hurwicz differential system strongly converge toward the element of least norm within its set of zeros. Moreover, we provide fast asymptotic decay rate estimates for the so-called ``primal-dual gap function'' and the norm of the solutions' velocity. If, in addition, the Tikhonov regularizing terms are decreasing, we provide some refined estimates in the sense of an exponentially weighted moving average. Under the additional assumption that the governing operator of the Arrow-Hurwicz differential system satisfies a reverse Lipschitz condition, we further provide a fast rate of strong convergence of the solutions toward the unique zero. We conclude our study by deriving the corresponding decay rate estimates with respect to the so-called ``viscosity curve''. Numerical experiments illustrate our theoretical findings.
-
arXiv:2410.06073 (Published 2024-10-08)
A note on existence and asymptotic behavior of Lagrangian equilibria for first-order optimal-exit mean field games
Categories: math.OCIn this paper, we consider a first-order mean field game model motivated by crowd motion in which agents evolve in a (not necessarily compact) metric space and wish to reach a given target set. Each agent aims to minimize the sum of their travel time and an exit cost which depends on their exit position on the target set. Agents interact through their dynamics, the maximal speed of an agent being assumed to be a function of their position and the distribution of other agents. This interaction may model, in particular, congestion phenomena. Under suitable assumptions on the model, we prove existence of Lagrangian equilibria, analyze the asymptotic behavior for large time of the distribution of agents, and study the dependence of equilibria and asymptotic limits on the initial distribution of the agents.
-
arXiv:2407.18868 (Published 2024-07-26)
Asymptotic behavior of a diffused interface volume-preserving mean curvature flow
Comments: 51 pagesWe consider a diffused interface version of the volume-preserving mean curvature flow in the Euclidean space, and prove, in every dimension and under natural assumptions on the initial datum, exponential convergence towards single "diffused balls".
-
arXiv:2311.13092 (Published 2023-11-22)
State-Dependent Sweeping Processes: Asymptotic Behavior and Algorithmic Approaches
Categories: math.OCIn this paper, we investigate the asymptotic properties of a particular class of state-dependent sweeping processes. While extensive research has been conducted on the existence and uniqueness of solutions for sweeping processes, there is a scarcity of studies addressing their behavior in the limit of large time. Additionally, we introduce novel algorithms designed for the resolution of quasi-variational inequalities. As a result, we introduce a new derivative-free algorithm to find zeros of nonsmooth Lipschitz continuous mappings with a linear convergence rate. This algorithm can be effectively used in nonsmooth and nonconvex optimization problems that do not possess necessarily second-order differentiability conditions of the data.
-
Asymptotic behavior of constrained local minimizers in finite elasticity
We provide an approximation result for the pure traction problem of linearized elasticity in terms of local minimizers of finite elasticity, under the constraint of vanishing average curl for admissible deformation maps. When suitable rotations are included in the constraint, the limit is shown to be the linear elastic equilibrium associated to rotated loads.
-
arXiv:2109.10668 (Published 2021-09-22)
Distributed optimal control problems for a class of elliptic hemivariational inequalities with a parameter and its asymptotic behavior
Comments: arXiv admin note: substantial text overlap with arXiv:2106.04702Journal: Communications in Nonlinear Science and Numerical Simulation-104 No.106027 (2021), 1-9Categories: math.OCKeywords: distributed optimal control problems, elliptic hemivariational inequalities, asymptotic behavior, multivalued subdifferential boundary conditionTags: journal articleIn this paper, we study optimal control problems on the internal energy for a system governed by a class of elliptic boundary hemivariational inequalities with a parameter. The system has been originated by a steady-state heat conduction problem with non-monotone multivalued subdifferential boundary condition on a portion of the boundary of the domain described by the Clarke generalized gradient of a locally Lipschitz function. We prove an existence result for the optimal controls and we show an asymptotic result for the optimal controls and the system states, when the parameter, like a heat transfer coefficient, tends to infinity on a portion of the boundary.
-
arXiv:2107.04161 (Published 2021-07-09)
Multi-agent system for target tracking on a sphere and its asymptotic behavior
We propose a second-order multi-agent system for target tracking on a sphere. The model contains a centripetal force, a bonding force, a velocity alignment operator to the target, and cooperative control between flocking agents. We propose an appropriate regularized rotation operator instead of Rodrigues' rotation operator to derive the velocity alignment operator for target tracking. By the regularized rotation operator, we can decompose the phase of agents into translational and structural parts. By analyzing the translational part of this reference frame decomposition, we can obtain rendezvous results to the given target. If the multi-agent system can obtain the target's position, velocity, and acceleration vectors, then the complete rendezvous occurs. Even in the absence of the target's acceleration information, if the coefficients are sufficiently large enough, then the practical rendezvous occurs.
-
arXiv:2011.01067 (Published 2020-11-02)
Asymptotic behavior of Integer Programming and the stability of the Castelnuovo-Mumford regularity
Comments: 33 pages; submitted to Math. ProgrammingThe paper provides a connection between Commutative Algebra and Integer Programming and contains two parts. The first one is devoted to the asymptotic behavior of integer programs with a fixed cost linear functional and the constraint sets consisting of a finite system of linear equations or inequalities with integer coefficients depending linearly on $n$. An integer $N_*$ is determined such that the optima of these integer programs are a quasi-linear function of $n$ for all $n\ge N_*$. Using results in the first part, one can bound in the second part the indices of stability of the Castelnuovo-Mumford regularities of integral closures of powers of a monomial ideal and that of symbolic powers of a square-free monomial ideal.
-
arXiv:2010.14706 (Published 2020-10-28)
Data-driven prediction of multistable systems from sparse measurements
We develop a data-driven method, based on semi-supervised classification, to predict the asymptotic state of multistable systems when only sparse spatial measurements of the system are feasible. Our method predicts the asymptotic behavior of an observed state by quantifying its proximity to the states in a precomputed library of data. To quantify this proximity, we introduce a sparsity-promoting metric-learning (SPML) optimization, which learns a metric directly from the precomputed data. The resulting metric has two important properties: (i) It is compatible with the precomputed library, and (ii) It is computable from sparse measurements. We demonstrate the application of this method on a multistable reaction-diffusion equation which has four asymptotically stable steady states. Classifications based on SPML predict the asymptotic behavior of initial conditions, based on two-point measurements, with over $89\%$ accuracy. The learned optimal metric also determines where these measurements need to be made to ensure accurate predictions.
-
arXiv:2004.14459 (Published 2020-04-29)
On the Asymptotic Behavior of the Douglas-Rachford and Proximal-Point Algorithms for Convex Optimization
Categories: math.OCThe authors in (Banjac et al., 2019) recently showed that the Douglas-Rachford algorithm provides certificates of infeasibility for a class of convex optimization problems. In particular, they showed that the difference between consecutive iterates generated by the algorithm converges to certificates of primal and dual strong infeasibility. Their result was shown in a finite dimensional Euclidean setting and for a particular structure of the constraint set. In this paper, we extend the result to Hilbert spaces and a general nonempty closed convex set. Moreover, we show that the proximal-point algorithm applied to the set of optimality conditions of the problem generates similar infeasibility certificates.
-
arXiv:1911.01133 (Published 2019-11-04)
Asymptotic behavior and control of a "guidance by repulsion" model
Comments: 33 pages, 19 figuresCategories: math.OCWe model and analyze a herding problem, where the drivers try to steer the evaders' trajectories while the evaders always move away from the drivers. This problem is motivated by the guidance-by-repulsion model [Escobedo, R., Iba\~nez, A. and Zuazua, E. COMMUN NONLINEAR SCI 39 (2016) 58-72], where the authors answer how to control the evaders' positions and what is the optimal maneuver of the drivers. First, we obtain the well-posedness and the long-time behavior of the one-driver and one-evader model, assuming of the same friction coefficients. In this case, the exact controllability is proved in a long enough time horizon. We extend the model to the multi-driver and multi-evader case, and develop numerical simulations to systematically explore the nature of controlled dynamics in various scenarios. The optimal strategies turn out to share a common pattern to the one-driver and one-evader case: the drivers rapidly occupy the position behind the target, and want to pursuit evaders in a straight line for most of the time. Inspired by this, we build a feedback strategy which stabilizes the direction of evaders.
-
arXiv:1812.10420 (Published 2018-12-13)
Asymptotic behavior of the transmission Euler-Bernoulli plate and wave equation with a localized Kelvin-Voigt damping
Comments: 20 pages, 1 figure; 2016, 21 (6) : 1757-1774Keywords: transmission euler-bernoulli plate, localized kelvin-voigt damping, asymptotic behavior, wave equation, smooth solutions decayTags: journal articleLet a fourth and a second order evolution equations be coupled via the interface by transmission conditions, and suppose that the first one is stabilized by a localized distributed feedback. What will then be the effect of such a partial stabilization on the decay of solutions at infinity? Is the behavior of the first component sufficient to stabilize the second one? The answer given in this paper is that sufficiently smooth solutions decay logarithmically at infinity even the feedback dissipation affects an arbitrarily small open subset of the interior. The method used, in this case, is based on a frequency method, and this by combining a contradiction argument with the Carleman estimates technique to carry out a special analysis for the resolvent.
-
arXiv:1710.00145 (Published 2017-09-30)
A Game-Theoretic Method for Multi-Period Demand Response: Revenue Maximization, Power Allocation, and Asymptotic Behavior
Categories: math.OCWe study a multi-period demand response management problem in the smart grid with multiple utility companies and consumers. The user-utility interactions are modeled by a Stackelberg game where the interactions among the utility companies are captured through a Nash price selection game. It is shown that this game has a unique Stackelberg equilibrium at which the utility companies set prices to maximize their revenues (within a Nash game) while the users respond accordingly to maximize their utilities subject to their budget constraints. Closed-form expressions are provided for the corresponding strategies of the users and the utility companies. It is shown, both analytically and numerically, that the multi-period scheme, compared with the single-period one, provides more incentives for energy consumers to participate in demand response programs. Based on closed-form solutions, a power allocation game for utility companies has been formulated, and it is shown to admit a unique pure-strategy Nash equilibrium, for which a full expression is obtained. We study the asymptotic behavior of the equilibrium strategies when the number of periods and users are large. We find an appropriate company-to-user ratio for the large population regime. For privacy, we provide a distributed algorithm for the computation of all optimal strategies.
-
arXiv:1709.00291 (Published 2017-08-30)
Asymptotic Bias of Stochastic Gradient Search
Comments: arXiv admin note: text overlap with arXiv:0907.1020The asymptotic behavior of the stochastic gradient algorithm with a biased gradient estimator is analyzed. Relying on arguments based on the dynamic system theory (chain-recurrence) and the differential geometry (Yomdin theorem and Lojasiewicz inequality), tight bounds on the asymptotic bias of the iterates generated by such an algorithm are derived. The obtained results hold under mild conditions and cover a broad class of high-dimensional nonlinear algorithms. Using these results, the asymptotic properties of the policy-gradient (reinforcement) learning and adaptive population Monte Carlo sampling are studied. Relying on the same results, the asymptotic behavior of the recursive maximum split-likelihood estimation in hidden Markov models is analyzed, too.
-
arXiv:1704.05721 (Published 2017-04-19)
The proximal point algorithm in geodesic spaces with curvature bounded above
Comments: Accepted for publication in the journal Linear and Nonlinear Analysis (Submitted on 4 August 2016; Revised on 29 September 2016). arXiv admin note: text overlap with arXiv:1704.01360We investigate the asymptotic behavior of sequences generated by the proximal point algorithm for convex functions in complete geodesic spaces with curvature bounded above. Using the notion of resolvents of such functions, which was recently introduced by the authors, we show the existence of minimizers of convex functions under the boundedness assumptions on such sequences as well as the convergence of such sequences to minimizers of given functions.
-
arXiv:1703.00927 (Published 2017-03-02)
On the asymptotic behavior of the price of anarchy: Is selfish routing bad in highly congested networks?
Comments: 24 pages, 4 figuresThis paper examines the asymptotic behavior of the price of anarchy as a function of the total traffic inflow in nonatomic congestion games with multiple origin-destination pairs. We first show that the price of anarchy may remain bounded away from 1, even in simple three-link parallel networks with convex cost functions. On the other hand, empirical studies show that the price of anarchy is close to 1 in highly congested real-world networks, thus begging the question: under what assumptions can this behavior be justified analytically? To that end, we prove a general result showing that for a large class of cost functions (defined in terms of regular variation and including all polynomials), the price of anarchy converges to 1 in the high congestion limit. In particular, specializing to networks with polynomial costs, we show that this convergence follows a power law whose degree can be computed explicitly.
-
arXiv:1702.02113 (Published 2017-02-07)
Rare Nash Equilibria and the Price of Anarchy in Large Static Games
We study a static game played by a finite number of agents, in which agents are assigned independent and identically distributed random types and each agent minimizes its objective function by choosing from a set of admissible actions that depends on its type. The game is anonymous in the sense that the objective function of each agent depends on the actions of other agents only through the empirical distribution of their type-action pairs. We study the asymptotic behavior of Nash equilibria, as the number of agents tends to infinity, first by deriving laws of large numbers characterizes almost sure limit points of Nash equilibria in terms of so-called Cournot-Nash equilibria of an associated nonatomic game. Our main results are large deviation principles that characterize the probability of rare Nash equilibria and associated conditional limit theorems describing the behavior of equilibria conditioned on a rare event. The results cover situations when neither the finite-player game nor the associated nonatomic game has a unique equilibrium. In addition, we study the asymptotic behavior of the price of anarchy, complementing existing worst-case bounds with new probabilistic bounds in the context of congestion games, which are used to model traffic routing in networks.
-
arXiv:1605.03081 (Published 2016-05-10)
On the Price of Anarchy of Highly Congested Nonatomic Network Games
Comments: 26 pages, 6 figuresWe consider nonatomic network games with one source and one destination. We examine the asymptotic behavior of the price of anarchy as the inflow increases. In accordance with some empirical observations, we show that, under suitable conditions, the price of anarchy is asymptotic to one. We show with some counterexamples that this is not always the case. The counterexamples occur in very simple parallel graphs.
-
arXiv:1602.00232 (Published 2016-01-31)
Asymptotic behavior of gradient-like dynamical systems involving inertia and multiscale aspects
Categories: math.OCIn a Hilbert space $\mathcal H$, we study the asymptotic behaviour, as time variable $t$ goes to $+\infty$, of nonautonomous gradient-like dynamical systems involving inertia and multiscale features. Given $\mathcal H$ a general Hilbert space, $\Phi: \mathcal H \rightarrow \mathbb R$ and $\Psi: \mathcal H \rightarrow \mathbb R$ two convex differentiable functions, $\gamma$ a positive damping parameter, and $\epsilon (t)$ a function of $t$ which tends to zero as $t$ goes to $+\infty$, we consider the second-order differential equation $$\ddot{x}(t) + \gamma \dot{x}(t) + \nabla \Phi (x(t)) + \epsilon (t) \nabla \Psi (x(t)) = 0. $$ This system models the emergence of various collective behaviors in game theory, as well as the asymptotic control of coupled nonlinear oscillators. Assuming that $\epsilon(t)$ tends to zero moderately slowly as $t$ goes to infinity, we show that the trajectories converge weakly in $\mathcal H$. The limiting equilibria are solutions of the hierarchical minimization problem which consists in minimizing $\Psi$ over the set $C$ of minimizers of $\Phi$. As key assumptions, we suppose that $ \int_{0}^{+\infty}\epsilon (t) dt = + \infty $ and that, for every $p$ belonging to a convex cone $\mathcal C$ depending on the data $\Phi$ and $\Psi$ $$ \int_{0}^{+\infty} \left[\Phi^* \left(\epsilon (t)p\right) -\sigma_C \left(\epsilon (t)p\right)\right]dt < + \infty $$ where $\Phi^*$ is the Fenchel conjugate of $\Phi$, and $\sigma_C $ is the support function of $C$. An application is given to coupled oscillators.