Search

We establish an equivalence between a family of adversarial training problems for non-parametric binary classification and a family of regularized risk minimization problems where the regularizer is a nonlocal perimeter functional. The resulting regularized risk minimization problems admit exact convex relaxations of the type $L^1+\text{(nonlocal)}\operatorname{TV}$, a form frequently studied in image analysis and graph-based learning. A rich geometric structure is revealed by this reformulation which in turn allows us to establish a series of properties of optimal solutions of the original problem, including the existence of minimal and maximal solutions (interpreted in a suitable sense) and the existence of regular solutions (also interpreted in a suitable sense). In addition, we highlight how the connection between adversarial training and perimeter minimization problems provides a novel, directly interpretable, statistical motivation for a family of regularized risk minimization problems involving perimeter/total variation. The majority of our theoretical results are independent of the distance used to define adversarial attacks.

The paper considers distributed gradient flow (DGF) for multi-agent nonconvex optimization. DGF is a continuous-time approximation of distributed gradient descent that is often easier to study than its discrete-time counterpart. The paper has two main contributions. First, the paper considers optimization of nonsmooth, nonconvex objective functions. It is shown that DGF converges to critical points in this setting. The paper then considers the problem of avoiding saddle points. It is shown that if agents' objective functions are assumed to be smooth and nonconvex, then DGF can only converge to a saddle point from a zero-measure set of initial conditions. To establish this result, the paper proves a stable manifold theorem for DGF, which is a fundamental contribution of independent interest. In a companion paper, analogous results are derived for discrete-time algorithms.

This work provides a rigorous framework for studying continuous-time control problems in uncertain environments. The framework models uncertainty in state dynamics as a probability measure on the space of functions. Such a probability measure is permitted to change over time as agents learn about their environment. This model can be seen as a variant of either Bayesian reinforcement learning (RL) or adaptive optimal control. We study conditions for locally optimal trajectories within this model, in particular deriving an appropriate dynamic programming principle and Hamilton–Jacobi equations. Some discussion of variants of the model are also provided, including one potential framework for studying the tradeoff between exploration and exploitation in RL.

The paper studies the convergence properties of (continuous) best-response dynamics from game theory. Despite their fundamental role in game theory, best-response dynamics are poorly understood in many games of interest due to the discontinuous, set-valued nature of the best-response map. The paper focuses on elucidating several important properties of best-response dynamics in the class of multi-agent games known as potential games---a class of games with fundamental importance in multi-agent systems and distributed control. It is shown that in almost every potential game and for almost every initial condition, the best-response dynamics (i) have a unique solution, (ii) converge to pure-strategy Nash equilibria, and (iii) converge at an exponential rate.

The note considers normalized gradient descent (NGD), a natural modification of classical gradient descent (GD) in optimization problems. A serious shortcoming of GD in non-convex problems is that GD may take arbitrarily long to escape from the neighborhood of a saddle point. This issue can make the convergence of GD arbitrarily slow, particularly in high-dimensional non-convex problems where the relative number of saddle points is often large. The paper focuses on continuous-time descent. It is shown that, contrary to standard GD, NGD escapes saddle points `quickly.' In particular, it is shown that (i) NGD `almost never' converges to saddle points and (ii) the time required for NGD to escape from a ball of radius $r$ about a saddle point $x^*$ is at most $5\sqrt{\kappa}r$, where $\kappa$ is the condition number of the Hessian of $f$ at $x^*$. As an application of this result, a global convergence-time bound is established for NGD under mild assumptions.

A fundamental problem with the Nash equilibrium concept is the existence of certain “structurally deficient” equilibria that (i) lack fundamental robustness properties, and (ii) are difficult to analyze. The notion of a “regular” Nash equilibrium was introduced by Harsanyi. Such equilibria are isolated, highly robust, and relatively simple to analyze. A game is said to be regular if all equilibria in the game are regular. In this paper it is shown that almost all potential games are regular. That is, except for a closed subset with Lebesgue measure zero, all potential games are regular. As an immediate consequence of this, the paper also proves an oddness result for potential games: In almost all potential games, the number of Nash equilibrium strategies is finite and odd. Specialized results are given for weighted potential games, exact potential games, and games with identical payoffs. Applications of the results to game-theoretic learning are discussed.

This work considers the problem of binary classification: given training data x1, . . ., xn from a certain population, together with associated labels y1,. . ., yn ∈ {0,1}, determine the best label for an element x not among the training data. More specifically, this work considers a variant of the regularized empirical risk functional which is defined intrinsically to the observed data and does not depend on the underlying population. Tools from modern analysis are used to obtain a concise proof of asymptotic consistency as regularization parameters are taken to zero at rates related to the size of the sample. These analytical tools give a new framework for understanding overfitting and underfitting, and rigorously connect the notion of overfitting with a loss of compactness.

Two types of solute-solute interactions are investigated in this work. Quadrupole interactions caused by nearby Ag-solute atoms were measured at nuclei of 111In/Cd solute probe atoms in the binary compound GdAl2 using the method of perturbed angular correlation of gamma rays (PAC). Locations of In-probes and Ag-solutes on both Gd- and Al-sublattices were identified by comparing site fractions in Gd-poor and Gd-rich GdAl2(Ag) samples. Interaction enthalpies between solute-atom pairs were determined from temperature dependences of observed site fractions. Repulsive interactions were observed for close-neighbor complexes In/Gd/+Ag/Gd/ and In/Gd/+Ag/Al/ pairs, whereas a slightly attractive interaction was observed for In/Al/+Ag/Al/. Interaction enthalpies were all in the range +/- 0.15 eV. Temperature dependences of site fractions of In-probes on locally defect-free Gd- and Al-sites yields a transfer enthalpy that was found to be 0.343 eV in a previous study of undoped GdAl2. The corresponding values in GdAl2(Ag) samples are much smaller. This is attributed to competition of In- and Ag-solutes to occupy sites of the same sublattice. While the difference in site-enthalpies of In-solutes on Gd- and Al-sites is temperature independent, it is proposed that the transfer of Ag-solutes from Gd- to Al-sites leads to a large temperature dependence of degeneracies of levels available to In-solutes, resulting in an effective transfer enthalpy that is much smaller than the difference in site-enthalpies., Comment: 17 pages, 6 figures, 2 tables. To be presented at the International Conference on Hyperfine Interactions and Their Applications, July 3-8, 2016, Leuven, Belgium; www.hyperfine2016.be/