query: I am currently working on a machine learning project in which I aim to train a model to solve a zero-sum game, such as two-player tic-tac-toe. The trained model will be designed to compete against either the system or a human player, and it could also potentially play against another version of itself. I want to utilize gradient descent to train my model. Therefore, the initial task is to formulate this zero-sum game in a manner that makes it differentiable and thus suitable for the application of gradient descent. Moreover, I am seeking to circumvent the potential pitfalls of gradient descent, specifically situations where the algorithm becomes trapped in a suboptimal local minimum and fails to locate the global optimum. I welcome any techniques that could enhance the efficiency of my gradient descent algorithm within this context. Ideally, my gradient learning algorithm should possess robust theoretical properties, ensuring convergence under mild conditions.

positive:
Recent applications that arise in machine learning have surged significant
interest in solving min-max saddle point games. This problem has been
extensively studied in the convex-concave regime for which a global equilibrium
solution can be computed efficiently. In this paper, we study the problem in
the non-convex regime and show that an \varepsilon--first order stationary
point of the game can be computed when one of the player's objective can be
optimized to global optimality efficiently. In particular, we first consider
the case where the objective of one of the players satisfies the
Polyak-{\L}ojasiewicz (PL) condition. For such a game, we show that a simple
multi-step gradient descent-ascent algorithm finds an \varepsilon--first order
stationary point of the problem in \widetilde{\mathcal{O}}(\varepsilon^{-2})
iterations. Then we show that our framework can also be applied to the case
where the objective of the "max-player" is concave. In this case, we propose a
multi-step gradient descent-ascent algorithm that finds an \varepsilon--first
order stationary point of the game in \widetilde{\cal O}(\varepsilon^{-3.5})
iterations, which is the best known rate in the literature. We applied our
algorithm to a fair classification problem of Fashion-MNIST dataset and
observed that the proposed algorithm results in smoother training and better
generalization.

positive:
We formulate a general framework for competitive gradient-based learning that
encompasses a wide breadth of multi-agent learning algorithms, and analyze the
limiting behavior of competitive gradient-based learning algorithms using
dynamical systems theory. For both general-sum and potential games, we
characterize a non-negligible subset of the local Nash equilibria that will be
avoided if each agent employs a gradient-based learning algorithm. We also shed
light on the issue of convergence to non-Nash strategies in general- and
zero-sum games, which may have no relevance to the underlying game, and arise
solely due to the choice of algorithm. The existence and frequency of such
strategies may explain some of the difficulties encountered when using gradient
descent in zero-sum games as, e.g., in the training of generative adversarial
networks. To reinforce the theoretical contributions, we provide empirical
results that highlight the frequency of linear quadratic dynamic games (a
benchmark for multi-agent reinforcement learning) that admit global Nash
equilibria that are almost surely avoided by policy gradient.

positive:
Stochastic gradient descent (\textsc{Sgd}) methods are the most powerful
optimization tools in training machine learning and deep learning models.
Moreover, acceleration (a.k.a. momentum) methods and diagonal scaling (a.k.a.
adaptive gradient) methods are the two main techniques to improve the slow
convergence of \textsc{Sgd}. While empirical studies have demonstrated
potential advantages of combining these two techniques, it remains unknown
whether these methods can achieve the optimal rate of convergence for
stochastic optimization. In this paper, we present a new class of adaptive and
accelerated stochastic gradient descent methods and show that they exhibit the
optimal sampling and iteration complexity for stochastic optimization. More
specifically, we show that diagonal scaling, initially designed to improve
vanilla stochastic gradient, can be incorporated into accelerated stochastic
gradient descent to achieve the optimal rate of convergence for smooth
stochastic optimization. We also show that momentum, apart from being known to
speed up the convergence rate of deterministic optimization, also provides us
new ways of designing non-uniform and aggressive moving average schemes in
stochastic optimization. Finally, we present some heuristics that help to
implement adaptive accelerated stochastic gradient descent methods and to
further improve their practical performance for machine learning and deep
learning.

positive:
Game-theoretic models of learning are a powerful set of models that optimize
multi-objective architectures. Among these models are zero-sum architectures
that have inspired adversarial learning frameworks. An important shortcoming of
these zeros-sum architectures is that gradient-based training leads to weak
convergence and cyclic dynamics.
  We propose a novel follow the leader training algorithm for zeros-sum
architectures that guarantees convergence to mixed Nash equilibrium without
cyclic behaviors. It is a special type of follow the perturbed leader algorithm
where perturbations are the result of a neural mediating agent.
  We validate our theoretical results by applying this training algorithm to
games with convex and non-convex loss as well as generative adversarial
architectures. Moreover, we customize the implementation of this algorithm for
adversarial imitation learning applications. At every step of the training, the
mediator agent perturbs the observations with generated codes. As a result of
these mediating codes, the proposed algorithm is also efficient for learning in
environments with various factors of variations. We validate our assertion by
using a procedurally generated game environment as well as synthetic data.
Github implementation is available.

positive:
We consider the maximum mean discrepancy ($\mathrm{MMD}$) GAN problem and
propose a parametric kernelized gradient flow that mimics the min-max game in
gradient regularized $\mathrm{MMD}$ GAN. We show that this flow provides a
descent direction minimizing the $\mathrm{MMD}$ on a statistical manifold of
probability distributions. We then derive an explicit condition which ensures
that gradient descent on the parameter space of the generator in gradient
regularized $\mathrm{MMD}$ GAN is globally convergent to the target
distribution. Under this condition, we give non asymptotic convergence results
of gradient descent in MMD GAN. Another contribution of this paper is the
introduction of a dynamic formulation of a regularization of $\mathrm{MMD}$ and
demonstrating that the parametric kernelized descent for $\mathrm{MMD}$ is the
gradient flow of this functional with respect to the new Riemannian structure.
Our obtained theoretical result allows ones to treat gradient flows for quite
general functionals and thus has potential applications to other types of
variational inferences on a statistical manifold beyond GANs. Finally,
numerical experiments suggest that our parametric kernelized gradient flow
stabilizes GAN training and guarantees convergence.

positive:
We introduce a new algorithm for the numerical computation of Nash equilibria
of competitive two-player games. Our method is a natural generalization of
gradient descent to the two-player setting where the update is given by the
Nash equilibrium of a regularized bilinear local approximation of the
underlying game. It avoids oscillatory and divergent behaviors seen in
alternating gradient descent. Using numerical experiments and rigorous
analysis, we provide a detailed comparison to methods based on \emph{optimism}
and \emph{consensus} and show that our method avoids making any unnecessary
changes to the gradient dynamics while achieving exponential (local)
convergence for (locally) convex-concave zero sum games. Convergence and
stability properties of our method are robust to strong interactions between
the players, without adapting the stepsize, which is not the case with previous
methods. In our numerical experiments on non-convex-concave problems, existing
methods are prone to divergence and instability due to their sensitivity to
interactions among the players, whereas we never observe divergence of our
algorithm. The ability to choose larger stepsizes furthermore allows our
algorithm to achieve faster convergence, as measured by the number of model
evaluations.

positive:
Existing analyses of optimization in deep learning are either continuous,
focusing on (variants of) gradient flow, or discrete, directly treating
(variants of) gradient descent. Gradient flow is amenable to theoretical
analysis, but is stylized and disregards computational efficiency. The extent
to which it represents gradient descent is an open question in the theory of
deep learning. The current paper studies this question. Viewing gradient
descent as an approximate numerical solution to the initial value problem of
gradient flow, we find that the degree of approximation depends on the
curvature around the gradient flow trajectory. We then show that over deep
neural networks with homogeneous activations, gradient flow trajectories enjoy
favorable curvature, suggesting they are well approximated by gradient descent.
This finding allows us to translate an analysis of gradient flow over deep
linear neural networks into a guarantee that gradient descent efficiently
converges to global minimum almost surely under random initialization.
Experiments suggest that over simple deep neural networks, gradient descent
with conventional step size is indeed close to gradient flow. We hypothesize
that the theory of gradient flows will unravel mysteries behind deep learning.

positive:
The cornerstone underpinning deep learning is the guarantee that gradient
descent on an objective converges to local minima. Unfortunately, this
guarantee fails in settings, such as generative adversarial nets, where there
are multiple interacting losses. The behavior of gradient-based methods in
games is not well understood -- and is becoming increasingly important as
adversarial and multi-objective architectures proliferate. In this paper, we
develop new techniques to understand and control the dynamics in general games.
The key result is to decompose the second-order dynamics into two components.
The first is related to potential games, which reduce to gradient descent on an
implicit function; the second relates to Hamiltonian games, a new class of
games that obey a conservation law, akin to conservation laws in classical
mechanical systems. The decomposition motivates Symplectic Gradient Adjustment
(SGA), a new algorithm for finding stable fixed points in general games. Basic
experiments show SGA is competitive with recently proposed algorithms for
finding stable fixed points in GANs -- whilst at the same time being applicable
to -- and having guarantees in -- much more general games.

positive:
We study the role that a finite timescale separation parameter $\tau$ has on
gradient descent-ascent in two-player non-convex, non-concave zero-sum games
where the learning rate of player 1 is denoted by $\gamma_1$ and the learning
rate of player 2 is defined to be $\gamma_2=\tau\gamma_1$. Existing work
analyzing the role of timescale separation in gradient descent-ascent has
primarily focused on the edge cases of players sharing a learning rate ($\tau
=1$) and the maximizing player approximately converging between each update of
the minimizing player ($\tau \rightarrow \infty$). For the parameter choice of
$\tau=1$, it is known that the learning dynamics are not guaranteed to converge
to a game-theoretically meaningful equilibria in general. In contrast, Jin et
al. (2020) showed that the stable critical points of gradient descent-ascent
coincide with the set of strict local minmax equilibria as
$\tau\rightarrow\infty$. In this work, we bridge the gap between past work by
showing there exists a finite timescale separation parameter $\tau^{\ast}$ such
that $x^{\ast}$ is a stable critical point of gradient descent-ascent for all
$\tau \in (\tau^{\ast}, \infty)$ if and only if it is a strict local minmax
equilibrium. Moreover, we provide an explicit construction for computing
$\tau^{\ast}$ along with corresponding convergence rates and results under
deterministic and stochastic gradient feedback. The convergence results we
present are complemented by a non-convergence result: given a critical point
$x^{\ast}$ that is not a strict local minmax equilibrium, then there exists a
finite timescale separation $\tau_0$ such that $x^{\ast}$ is unstable for all
$\tau\in (\tau_0, \infty)$. Finally, we empirically demonstrate on the CIFAR-10
and CelebA datasets the significant impact timescale separation has on training
performance.

positive:
Gradient descent ascent (GDA), the simplest single-loop algorithm for
nonconvex minimax optimization, is widely used in practical applications such
as generative adversarial networks (GANs) and adversarial training. Albeit its
desirable simplicity, recent work shows inferior convergence rates of GDA in
theory even assuming strong concavity of the objective on one side. This paper
establishes new convergence results for two alternative single-loop algorithms
-- alternating GDA and smoothed GDA -- under the mild assumption that the
objective satisfies the Polyak-Lojasiewicz (PL) condition about one variable.
We prove that, to find an $\epsilon$-stationary point, (i) alternating GDA and
its stochastic variant (without mini batch) respectively require $O(\kappa^{2}
\epsilon^{-2})$ and $O(\kappa^{4} \epsilon^{-4})$ iterations, while (ii)
smoothed GDA and its stochastic variant (without mini batch) respectively
require $O(\kappa \epsilon^{-2})$ and $O(\kappa^{2} \epsilon^{-4})$ iterations.
The latter greatly improves over the vanilla GDA and gives the hitherto best
known complexity results among single-loop algorithms under similar settings.
We further showcase the empirical efficiency of these algorithms in training
GANs and robust nonlinear regression.

positive:
In recent years, artificial neural networks have developed into a powerful
tool for dealing with a multitude of problems for which classical solution
approaches reach their limits. However, it is still unclear why randomly
initialized gradient descent optimization algorithms, such as the well-known
batch gradient descent, are able to achieve zero training loss in many
situations even though the objective function is non-convex and non-smooth. One
of the most promising approaches to solving this problem in the field of
supervised learning is the analysis of gradient descent optimization in the
so-called overparameterized regime. In this article we provide a further
contribution to this area of research by considering overparameterized
fully-connected rectified artificial neural networks with biases. Specifically,
we show that for a fixed number of training data the mean squared error using
batch gradient descent optimization applied to such a randomly initialized
artificial neural network converges to zero at a linear convergence rate as
long as the width of the artificial neural network is large enough, the
learning rate is small enough, and the training input data are pairwise
linearly independent.

positive:
Fictitious play with reinforcement learning is a general and effective
framework for zero-sum games. However, using the current deep neural network
models, the implementation of fictitious play faces crucial challenges. Neural
network model training employs gradient descent approaches to update all
connection weights, and thus is easy to forget the old opponents after training
to beat the new opponents. Existing approaches often maintain a pool of
historical policy models to avoid the forgetting. However, learning to beat a
pool in stochastic games, i.e., a wide distribution over policy models, is
either sample-consuming or insufficient to exploit all models with limited
amount of samples. In this paper, we propose a learning process with neural
fictitious play to alleviate the above issues. We train a single model as our
policy model, which consists of sub-models and a selector. Everytime facing a
new opponent, the model is expanded by adding a new sub-model, where only the
new sub-model is updated instead of the whole model. At the same time, the
selector is also updated to mix up the new sub-model with the previous ones at
the state-level, so that the model is maintained as a behavior strategy instead
of a wide distribution over policy models. Experiments on Kuhn poker, a
grid-world Treasure Hunting game, and Mini-RTS environments show that the
proposed approach alleviates the forgetting problem, and consequently improves
the learning efficiency and the robustness of neural fictitious play.

positive:
Stochastic convex optimization is a basic and well studied primitive in
machine learning. It is well known that convex and Lipschitz functions can be
minimized efficiently using Stochastic Gradient Descent (SGD). The Normalized
Gradient Descent (NGD) algorithm, is an adaptation of Gradient Descent, which
updates according to the direction of the gradients, rather than the gradients
themselves. In this paper we analyze a stochastic version of NGD and prove its
convergence to a global minimum for a wider class of functions: we require the
functions to be quasi-convex and locally-Lipschitz. Quasi-convexity broadens
the con- cept of unimodality to multidimensions and allows for certain types of
saddle points, which are a known hurdle for first-order optimization methods
such as gradient descent. Locally-Lipschitz functions are only required to be
Lipschitz in a small region around the optimum. This assumption circumvents
gradient explosion, which is another known hurdle for gradient descent
variants. Interestingly, unlike the vanilla SGD algorithm, the stochastic
normalized gradient descent algorithm provably requires a minimal minibatch
size.

positive:
Many economic games and machine learning approaches can be cast as
competitive optimization problems where multiple agents are minimizing their
respective objective function, which depends on all agents' actions. While
gradient descent is a reliable basic workhorse for single-agent optimization,
it often leads to oscillation in competitive optimization. In this work we
propose polymatrix competitive gradient descent (PCGD) as a method for solving
general sum competitive optimization involving arbitrary numbers of agents. The
updates of our method are obtained as the Nash equilibria of a local polymatrix
approximation with a quadratic regularization, and can be computed efficiently
by solving a linear system of equations. We prove local convergence of PCGD to
stable fixed points for $n$-player general-sum games, and show that it does not
require adapting the step size to the strength of the player-interactions. We
use PCGD to optimize policies in multi-agent reinforcement learning and
demonstrate its advantages in Snake, Markov soccer and an electricity market
game. Agents trained by PCGD outperform agents trained with simultaneous
gradient descent, symplectic gradient adjustment, and extragradient in Snake
and Markov soccer games and on the electricity market game, PCGD trains faster
than both simultaneous gradient descent and the extragradient method.

positive:
Over the last decade, a single algorithm has changed many facets of our lives
- Stochastic Gradient Descent (SGD). In the era of ever decreasing loss
functions, SGD and its various offspring have become the go-to optimization
tool in machine learning and are a key component of the success of deep neural
networks (DNNs). While SGD is guaranteed to converge to a local optimum (under
loose assumptions), in some cases it may matter which local optimum is found,
and this is often context-dependent. Examples frequently arise in machine
learning, from shape-versus-texture-features to ensemble methods and zero-shot
coordination. In these settings, there are desired solutions which SGD on
'standard' loss functions will not find, since it instead converges to the
'easy' solutions. In this paper, we present a different approach. Rather than
following the gradient, which corresponds to a locally greedy direction, we
instead follow the eigenvectors of the Hessian, which we call "ridges". By
iteratively following and branching amongst the ridges, we effectively span the
loss surface to find qualitatively different solutions. We show both
theoretically and experimentally that our method, called Ridge Rider (RR),
offers a promising direction for a variety of challenging problems.

positive:
This paper investigates the convergence of learning dynamics in Stackelberg
games. In the class of games we consider, there is a hierarchical game being
played between a leader and a follower with continuous action spaces. We
establish a number of connections between the Nash and Stackelberg equilibrium
concepts and characterize conditions under which attracting critical points of
simultaneous gradient descent are Stackelberg equilibria in zero-sum games.
Moreover, we show that the only stable critical points of the Stackelberg
gradient dynamics are Stackelberg equilibria in zero-sum games. Using this
insight, we develop a gradient-based update for the leader while the follower
employs a best response strategy for which each stable critical point is
guaranteed to be a Stackelberg equilibrium in zero-sum games. As a result, the
learning rule provably converges to a Stackelberg equilibria given an
initialization in the region of attraction of a stable critical point. We then
consider a follower employing a gradient-play update rule instead of a best
response strategy and propose a two-timescale algorithm with similar asymptotic
convergence guarantees. For this algorithm, we also provide finite-time high
probability bounds for local convergence to a neighborhood of a stable
Stackelberg equilibrium in general-sum games. Finally, we present extensive
numerical results that validate our theory, provide insights into the
optimization landscape of generative adversarial networks, and demonstrate that
the learning dynamics we propose can effectively train generative adversarial
networks.

positive:
Reinforcement learning from self-play has recently reported many successes.
Self-play, where the agents compete with themselves, is often used to generate
training data for iterative policy improvement. In previous work, heuristic
rules are designed to choose an opponent for the current learner. Typical rules
include choosing the latest agent, the best agent, or a random historical
agent. However, these rules may be inefficient in practice and sometimes do not
guarantee convergence even in the simplest matrix games. In this paper, we
propose a new algorithmic framework for competitive self-play reinforcement
learning in two-player zero-sum games. We recognize the fact that the Nash
equilibrium coincides with the saddle point of the stochastic payoff function,
which motivates us to borrow ideas from classical saddle point optimization
literature. Our method trains several agents simultaneously, and intelligently
takes each other as opponent based on simple adversarial rules derived from a
principled perturbation-based saddle optimization method. We prove
theoretically that our algorithm converges to an approximate equilibrium with
high probability in convex-concave games under standard assumptions. Beyond the
theory, we further show the empirical superiority of our method over baseline
methods relying on the aforementioned opponent-selection heuristics in matrix
games, grid-world soccer, Gomoku, and simulated robot sumo, with neural net
policy function approximators.

positive:
Many modern learning tasks involve fitting nonlinear models to data which are
trained in an overparameterized regime where the parameters of the model exceed
the size of the training dataset. Due to this overparameterization, the
training loss may have infinitely many global minima and it is critical to
understand the properties of the solutions found by first-order optimization
schemes such as (stochastic) gradient descent starting from different
initializations. In this paper we demonstrate that when the loss has certain
properties over a minimally small neighborhood of the initial point, first
order methods such as (stochastic) gradient descent have a few intriguing
properties: (1) the iterates converge at a geometric rate to a global optima
even when the loss is nonconvex, (2) among all global optima of the loss the
iterates converge to one with a near minimal distance to the initial point, (3)
the iterates take a near direct route from the initial point to this global
optima. As part of our proof technique, we introduce a new potential function
which captures the precise tradeoff between the loss function and the distance
to the initial point as the iterations progress. For Stochastic Gradient
Descent (SGD), we develop novel martingale techniques that guarantee SGD never
leaves a small neighborhood of the initialization, even with rather large
learning rates. We demonstrate the utility of our general theory for a variety
of problem domains spanning low-rank matrix recovery to neural network
training. Underlying our analysis are novel insights that may have implications
for training and generalization of more sophisticated learning problems
including those involving deep neural network architectures.

negative:
The development of machine learning is promoting the search for fast and
stable minimization algorithms. To this end, we suggest a change in the current
gradient descent methods that should speed up the motion in flat regions and
slow it down in steep directions of the function to minimize. It is based on a
"power gradient", in which each component of the gradient is replaced by its
versus-preserving $H$-th power, with $0<H<1$. We test three modern gradient
descent methods fed by such variant and by standard gradients, finding the new
version to achieve significantly better performances for the Nesterov
accelerated gradient and AMSGrad. We also propose an effective new take on the
ADAM algorithm, which includes power gradients with varying $H$.

negative:
Deep learning models are often successfully trained using gradient descent,
despite the worst case hardness of the underlying non-convex optimization
problem. The key question is then under what conditions can one prove that
optimization will succeed. Here we provide a strong result of this kind. We
consider a neural net with one hidden layer and a convolutional structure with
no overlap and a ReLU activation function. For this architecture we show that
learning is NP-complete in the general case, but that when the input
distribution is Gaussian, gradient descent converges to the global optimum in
polynomial time. To the best of our knowledge, this is the first global
optimality guarantee of gradient descent on a convolutional neural network with
ReLU activations.

negative:
Owing to their connection with generative adversarial networks (GANs),
saddle-point problems have recently attracted considerable interest in machine
learning and beyond. By necessity, most theoretical guarantees revolve around
convex-concave (or even linear) problems; however, making theoretical inroads
towards efficient GAN training depends crucially on moving beyond this classic
framework. To make piecemeal progress along these lines, we analyze the
behavior of mirror descent (MD) in a class of non-monotone problems whose
solutions coincide with those of a naturally associated variational inequality
- a property which we call coherence. We first show that ordinary, "vanilla" MD
converges under a strict version of this condition, but not otherwise; in
particular, it may fail to converge even in bilinear models with a unique
solution. We then show that this deficiency is mitigated by optimism: by taking
an "extra-gradient" step, optimistic mirror descent (OMD) converges in all
coherent problems. Our analysis generalizes and extends the results of
Daskalakis et al. (2018) for optimistic gradient descent (OGD) in bilinear
problems, and makes concrete headway for establishing convergence beyond
convex-concave games. We also provide stochastic analogues of these results,
and we validate our analysis by numerical experiments in a wide array of GAN
models (including Gaussian mixture models, as well as the CelebA and CIFAR-10
datasets).

negative:
Games generalize the single-objective optimization paradigm by introducing
different objective functions for different players. Differentiable games often
proceed by simultaneous or alternating gradient updates. In machine learning,
games are gaining new importance through formulations like generative
adversarial networks (GANs) and actor-critic systems. However, compared to
single-objective optimization, game dynamics are more complex and less
understood. In this paper, we analyze gradient-based methods with momentum on
simple games. We prove that alternating updates are more stable than
simultaneous updates. Next, we show both theoretically and empirically that
alternating gradient updates with a negative momentum term achieves convergence
in a difficult toy adversarial problem, but also on the notoriously difficult
to train saturating GANs.

negative:
Deep neural networks (DNN) are typically optimized using stochastic gradient
descent (SGD). However, the estimation of the gradient using stochastic samples
tends to be noisy and unreliable, resulting in large gradient variance and bad
convergence. In this paper, we propose \textbf{Filter Gradient Decent}~(FGD),
an efficient stochastic optimization algorithm that makes the consistent
estimation of the local gradient by solving an adaptive filtering problem with
different design of filters. Our method reduces variance in stochastic gradient
descent by incorporating the historical states to enhance the current
estimation. It is able to correct noisy gradient direction as well as to
accelerate the convergence of learning. We demonstrate the effectiveness of the
proposed Filter Gradient Descent on numerical optimization and training neural
networks, where it achieves superior and robust performance compared with
traditional momentum-based methods. To the best of our knowledge, we are the
first to provide a practical solution that integrates filtering into gradient
estimation by making the analogy between gradient estimation and filtering
problems in signal processing. (The code is provided in
https://github.com/Adamdad/Filter-Gradient-Decent)

negative:
Loss functions with a large number of saddle points are one of the major
obstacles for training modern machine learning models efficiently. First-order
methods such as gradient descent are usually the methods of choice for training
machine learning models. However, these methods converge to saddle points for
certain choices of initial guesses. In this paper, we propose a modification of
the recently proposed Laplacian smoothing gradient descent [Osher et al.,
arXiv:1806.06317], called modified Laplacian smoothing gradient descent
(mLSGD), and demonstrate its potential to avoid saddle points without
sacrificing the convergence rate. Our analysis is based on the attraction
region, formed by all starting points for which the considered numerical scheme
converges to a saddle point. We investigate the attraction region's dimension
both analytically and numerically. For a canonical class of quadratic
functions, we show that the dimension of the attraction region for mLSGD is
floor((n-1)/2), and hence it is significantly smaller than that of the gradient
descent whose dimension is n-1.

negative:
Many machine learning and data science tasks require solving non-convex
optimization problems. When the loss function is a sum of multiple terms, a
popular method is the stochastic gradient descent. Viewed as a process for
sampling the loss function landscape, the stochastic gradient descent is known
to prefer flat minima. Though this is desired for certain optimization problems
such as in deep learning, it causes issues when the goal is to find the global
minimum, especially if the global minimum resides in a sharp valley.
  Illustrated with a simple motivating example, we show that the fundamental
reason is that the difference in the Lipschitz constants of multiple terms in
the loss function causes stochastic gradient descent to experience different
variances at different minima. In order to mitigate this effect and perform
faithful optimization, we propose a combined resampling-reweighting scheme to
balance the variance at local minima and extend to general loss functions. We
explain from the numerical stability perspective how the proposed scheme is
more likely to select the true global minimum, and the local convergence
analysis perspective how it converges to a minimum faster when compared with
the vanilla stochastic gradient descent. Experiments from robust statistics and
computational chemistry are provided to demonstrate the theoretical findings.

negative:
We study the properties of alignment, a form of implicit regularization, in
linear neural networks under gradient descent. We define alignment for fully
connected networks with multidimensional outputs and show that it is a natural
extension of alignment in networks with 1-dimensional outputs as defined by Ji
and Telgarsky, 2018. While in fully connected networks, there always exists a
global minimum corresponding to an aligned solution, we analyze alignment as it
relates to the training process. Namely, we characterize when alignment is an
invariant of training under gradient descent by providing necessary and
sufficient conditions for this invariant to hold. In such settings, the
dynamics of gradient descent simplify, thereby allowing us to provide an
explicit learning rate under which the network converges linearly to a global
minimum. We then analyze networks with layer constraints such as convolutional
networks. In this setting, we prove that gradient descent is equivalent to
projected gradient descent, and that alignment is impossible with sufficiently
large datasets.

negative:
One of the most important parts of Artificial Neural Networks is minimizing
the loss functions which tells us how good or bad our model is. To minimize
these losses we need to tune the weights and biases. Also to calculate the
minimum value of a function we need gradient. And to update our weights we need
gradient descent. But there are some problems with regular gradient descent ie.
it is quite slow and not that accurate. This article aims to give an
introduction to optimization strategies to gradient descent. In addition, we
shall also discuss the architecture of these algorithms and further
optimization of Neural Networks in general

negative:
We study the hardness of learning unitary transformations in $U(d)$ via
gradient descent on time parameters of alternating operator sequences. We
provide numerical evidence that, despite the non-convex nature of the loss
landscape, gradient descent always converges to the target unitary when the
sequence contains $d^2$ or more parameters. Rates of convergence indicate a
"computational phase transition." With less than $d^2$ parameters, gradient
descent converges to a sub-optimal solution, whereas with more than $d^2$
parameters, gradient descent converges exponentially to an optimal solution.

negative:
This paper considers the multi-agent linear least-squares problem in a
server-agent network. In this problem, the system comprises multiple agents,
each having a set of local data points, that are connected to a server. The
goal for the agents is to compute a linear mathematical model that optimally
fits the collective data points held by all the agents, without sharing their
individual local data points. This goal can be achieved, in principle, using
the server-agent variant of the traditional iterative gradient-descent method.
The gradient-descent method converges linearly to a solution, and its rate of
convergence is lower bounded by the conditioning of the agents' collective data
points. If the data points are ill-conditioned, the gradient-descent method may
require a large number of iterations to converge.
  We propose an iterative pre-conditioning technique that mitigates the
deleterious effect of the conditioning of data points on the rate of
convergence of the gradient-descent method. We rigorously show that the
resulting pre-conditioned gradient-descent method, with the proposed iterative
pre-conditioning, achieves superlinear convergence when the least-squares
problem has a unique solution. In general, the convergence is linear with
improved rate of convergence in comparison to the traditional gradient-descent
method and the state-of-the-art accelerated gradient-descent methods. We
further illustrate the improved rate of convergence of our proposed algorithm
through experiments on different real-world least-squares problems in both
noise-free and noisy computation environment.

negative:
In this paper, we propose a geometric framework to analyze the convergence
properties of gradient descent trajectories in the context of linear neural
networks. We translate a well-known empirical observation of linear neural nets
into a conjecture that we call the \emph{overfitting conjecture} which states
that, for almost all training data and initial conditions, the trajectory of
the corresponding gradient descent system converges to a global minimum. This
would imply that the solution achieved by vanilla gradient descent algorithms
is equivalent to that of the least-squares estimation, for linear neural
networks of an arbitrary number of hidden layers. Built upon a key invariance
property induced by the network structure, we first establish convergence of
gradient descent trajectories to critical points of the square loss function in
the case of linear networks of arbitrary depth. Our second result is the proof
of the \emph{overfitting conjecture} in the case of single-hidden-layer linear
networks with an argument based on the notion of normal hyperbolicity and under
a generic property on the training data (i.e., holding for almost all training
data).

negative:
In this paper we consider solving saddle point problems using two variants of
Gradient Descent-Ascent algorithms, Extra-gradient (EG) and Optimistic Gradient
Descent Ascent (OGDA) methods. We show that both of these algorithms admit a
unified analysis as approximations of the classical proximal point method for
solving saddle point problems. This viewpoint enables us to develop a new
framework for analyzing EG and OGDA for bilinear and strongly convex-strongly
concave settings. Moreover, we use the proximal point approximation
interpretation to generalize the results for OGDA for a wide range of
parameters.

negative:
We generalize gradient descent with momentum for optimization in
differentiable games to have complex-valued momentum. We give theoretical
motivation for our method by proving convergence on bilinear zero-sum games for
simultaneous and alternating updates. Our method gives real-valued parameter
updates, making it a drop-in replacement for standard optimizers. We
empirically demonstrate that complex-valued momentum can improve convergence in
realistic adversarial games - like generative adversarial networks - by showing
we can find better solutions with an almost identical computational cost. We
also show a practical generalization to a complex-valued Adam variant, which we
use to train BigGAN to better inception scores on CIFAR-10.

negative:
Several widely-used first-order saddle-point optimization methods yield an
identical continuous-time ordinary differential equation (ODE) that is
identical to that of Gradient Descent Ascent (GDA) method when derived naively.
However, the convergence properties of these methods are qualitatively
different even on simple bilinear games. Thus the ODE perspective, which has
proved powerful in analyzing single-objective optimization methods, has not
played a similar role in saddle-point optimization.
  We adopt a framework studied in fluid dynamics -- known as High-Resolution
Differential Equations (HRDEs) -- to design differential equation models for
several saddle-point optimization methods. Critically, these HRDEs are distinct
for various saddle-point optimization methods. Moreover, on bilinear games, the
convergence properties of the HRDEs match the qualitative features of the
corresponding discrete methods. Additionally, we show that the HRDE of
Optimistic Gradient Descent Ascent (OGDA) exhibits \emph{last-iterate
convergence} for general monotone variational inequalities. Finally, we provide
rates of convergence for the \emph{best-iterate convergence} of the OGDA
method, relying solely on the first-order smoothness of the monotone operator.

negative:
In optimization, the negative gradient of a function denotes the direction of
steepest descent. Furthermore, traveling in any direction orthogonal to the
gradient maintains the value of the function. In this work, we show that these
orthogonal directions that are ignored by gradient descent can be critical in
equilibrium problems. Equilibrium problems have drawn heightened attention in
machine learning due to the emergence of the Generative Adversarial Network
(GAN). We use the framework of Variational Inequalities to analyze popular
training algorithms for a fundamental GAN variant: the Wasserstein
Linear-Quadratic GAN. We show that the steepest descent direction causes
divergence from the equilibrium, and convergence to the equilibrium is achieved
through following a particular orthogonal direction. We call this successful
technique Crossing-the-Curl, named for its mathematical derivation as well as
its intuition: identify the game's axis of rotation and move "across" space in
the direction towards smaller "curling".

negative:
We develop provably efficient reinforcement learning algorithms for
two-player zero-sum finite-horizon Markov games with simultaneous moves. To
incorporate function approximation, we consider a family of Markov games where
the reward function and transition kernel possess a linear structure. Both the
offline and online settings of the problems are considered. In the offline
setting, we control both players and aim to find the Nash Equilibrium by
minimizing the duality gap. In the online setting, we control a single player
playing against an arbitrary opponent and aim to minimize the regret. For both
settings, we propose an optimistic variant of the least-squares minimax value
iteration algorithm. We show that our algorithm is computationally efficient
and provably achieves an $\tilde O(\sqrt{d^3 H^3 T} )$ upper bound on the
duality gap and regret, where $d$ is the linear dimension, $H$ the horizon and
$T$ the total number of timesteps. Our results do not require additional
assumptions on the sampling model.
  Our setting requires overcoming several new challenges that are absent in
Markov decision processes or turn-based Markov games. In particular, to achieve
optimism with simultaneous moves, we construct both upper and lower confidence
bounds of the value function, and then compute the optimistic policy by solving
a general-sum matrix game with these bounds as the payoff matrices. As finding
the Nash Equilibrium of a general-sum game is computationally hard, our
algorithm instead solves for a Coarse Correlated Equilibrium (CCE), which can
be obtained efficiently. To our best knowledge, such a CCE-based scheme for
optimism has not appeared in the literature and might be of interest in its own
right.

negative:
This paper studies a distributed multi-agent convex optimization problem. The
system comprises multiple agents in this problem, each with a set of local data
points and an associated local cost function. The agents are connected to a
server, and there is no inter-agent communication. The agents' goal is to learn
a parameter vector that optimizes the aggregate of their local costs without
revealing their local data points. In principle, the agents can solve this
problem by collaborating with the server using the traditional distributed
gradient-descent method. However, when the aggregate cost is ill-conditioned,
the gradient-descent method (i) requires a large number of iterations to
converge, and (ii) is highly unstable against process noise. We propose an
iterative pre-conditioning technique to mitigate the deleterious effects of the
cost function's conditioning on the convergence rate of distributed
gradient-descent. Unlike the conventional pre-conditioning techniques, the
pre-conditioner matrix in our proposed technique updates iteratively to
facilitate implementation on the distributed network. In the distributed
setting, we provably show that the proposed algorithm converges linearly with
an improved rate of convergence than the traditional and adaptive
gradient-descent methods. Additionally, for the special case when the minimizer
of the aggregate cost is unique, our algorithm converges superlinearly. We
demonstrate our algorithm's superior performance compared to prominent
distributed algorithms for solving real logistic regression problems and
emulating neural network training via a noisy quadratic model, thereby
signifying the proposed algorithm's efficiency for distributively solving
non-convex optimization. Moreover, we empirically show that the proposed
algorithm results in faster training without compromising the generalization
performance.

negative:
We provide the first convergence analysis of local gradient descent for
minimizing the average of smooth and convex but otherwise arbitrary functions.
Problems of this form and local gradient descent as a solution method are of
importance in federated learning, where each function is based on private data
stored by a user on a mobile device, and the data of different users can be
arbitrarily heterogeneous. We show that in a low accuracy regime, the method
has the same communication complexity as gradient descent.

negative:
The goal of policy gradient approaches is to find a policy in a given class
of policies which maximizes the expected return. Given a differentiable model
of the policy, we want to apply a gradient-ascent technique to reach a local
optimum. We mainly use gradient ascent, because it is theoretically well
researched. The main issue is that the policy gradient with respect to the
expected return is not available, thus we need to estimate it. As policy
gradient algorithms also tend to require on-policy data for the gradient
estimate, their biggest weakness is sample efficiency. For this reason, most
research is focused on finding algorithms with improved sample efficiency. This
paper provides a formal introduction to policy gradient that shows the
development of policy gradient approaches, and should enable the reader to
follow current research on the topic.

negative:
The multinomial logistic regression (MLR) model is widely used in statistics
and machine learning. Stochastic gradient descent (SGD) is the most common
approach for determining the parameters of a MLR model in big data scenarios.
However, SGD has slow sub-linear rates of convergence. A way to improve these
rates of convergence is to use manifold optimization. Along this line,
stochastic natural gradient descent (SNGD), proposed by Amari, was proven to be
Fisher efficient when it converged. However, SNGD is not guaranteed to converge
and it is computationally too expensive for MLR models with a large number of
parameters.
  Here, we propose a stochastic optimization method for MLR based on manifold
optimization concepts which (i) has per-iteration computational complexity is
linear in the number of parameters and (ii) can be proven to converge.
  To achieve (i) we establish that the family of joint distributions for MLR is
a dually flat manifold and we use that to speed up calculations.
S\'anchez-L\'opez and Cerquides have recently introduced convergent stochastic
natural gradient descent (CSNGD), a variant of SNGD whose convergence is
guaranteed. To obtain (ii) our algorithm uses the fundamental idea from CSNGD,
thus relying on an independent sequence to build a bounded approximation of the
natural gradient. We call the resulting algorithm dual stochastic natural
gradient descent (DNSGD). By generalizing a result from Sunehag et al., we
prove that DSNGD converges. Furthermore, we prove that the computational
complexity of DSNGD iterations are linear on the number of variables of the
model.

negative:
In this paper, we give explicit descriptions of versions of (Local-)
Backtracking Gradient Descent and New Q-Newton's method to the Riemannian
setting.Here are some easy to state consequences of results in this paper,
where X is a general Riemannian manifold of finite dimension and
$f:X\rightarrow \mathbb{R}$ a $C^2$ function which is Morse (that is, all its
critical points are non-degenerate).
  {\bf Theorem.} For random choices of the hyperparameters in the Riemanian
Local Backtracking Gradient Descent algorithm and for random choices of the
initial point $x_0$, the sequence $\{x_n\}$ constructed by the algorithm either
(i) converges to a local minimum of $f$ or (ii) eventually leaves every compact
subsets of $X$ (in other words, diverges to infinity on $X$). If $f$ has
compact sublevels, then only the former alternative happens. The convergence
rate is the same as in the classical paper by Armijo.
  {\bf Theorem.} Assume that $f$ is $C^3$. For random choices of the
hyperparametes in the Riemannian New Q-Newton's method, if the sequence
constructed by the algorithm converges, then the limit is a critical point of
$f$. We have a local Stable-Center manifold theorem, near saddle points of $f$,
for the dynamical system associated to the algorithm. If the limit point is a
non-degenerate minimum point, then the rate of convergence is quadratic. If
moreover $X$ is an open subset of a Lie group and the initial point $x_0$ is
chosen randomly, then we can globally avoid saddle points.
  As an application, we propose a general method using Riemannian Backtracking
GD to find minimum of a function on a bounded ball in a Euclidean space, and do
explicit calculations for calculating the smallest eigenvalue of a symmetric
square matrix.

negative:
Large-scale optimization problems require algorithms both effective and
efficient. One such popular and proven algorithm is Stochastic Gradient Descent
which uses first-order gradient information to solve these problems. This paper
studies almost-sure convergence rates of the Stochastic Gradient Descent method
when instead of deterministic, its learning rate becomes stochastic. In
particular, its learning rate is equipped with a multiplicative stochasticity,
producing a stochastic learning rate scheme. Theoretical results show
accelerated almost-sure convergence rates of Stochastic Gradient Descent in a
nonconvex setting when using an appropriate stochastic learning rate, compared
to a deterministic-learning-rate scheme. The theoretical results are verified
empirically.

negative:
We study the convergence properties of gradient descent for training deep
linear neural networks, i.e., deep matrix factorizations, by extending a
previous analysis for the related gradient flow. We show that under suitable
conditions on the step sizes gradient descent converges to a critical point of
the loss function, i.e., the square loss in this article. Furthermore, we
demonstrate that for almost all initializations gradient descent converges to a
global minimum in the case of two layers. In the case of three or more layers
we show that gradient descent converges to a global minimum on the manifold
matrices of some fixed rank, where the rank cannot be determined a priori.

negative:
Background: Recent developments have made it possible to accelerate neural
networks training significantly using large batch sizes and data parallelism.
Training in an asynchronous fashion, where delay occurs, can make training even
more scalable. However, asynchronous training has its pitfalls, mainly a
degradation in generalization, even after convergence of the algorithm. This
gap remains not well understood, as theoretical analysis so far mainly focused
on the convergence rate of asynchronous methods. Contributions: We examine
asynchronous training from the perspective of dynamical stability. We find that
the degree of delay interacts with the learning rate, to change the set of
minima accessible by an asynchronous stochastic gradient descent algorithm. We
derive closed-form rules on how the learning rate could be changed, while
keeping the accessible set the same. Specifically, for high delay values, we
find that the learning rate should be kept inversely proportional to the delay.
We then extend this analysis to include momentum. We find momentum should be
either turned off, or modified to improve training stability. We provide
empirical experiments to validate our theoretical findings.

negative:
With the rise of deep neural networks, the challenge of explaining the
predictions of these networks has become increasingly recognized. While many
methods for explaining the decisions of deep neural networks exist, there is
currently no consensus on how to evaluate them. On the other hand, robustness
is a popular topic for deep learning research; however, it is hardly talked
about in explainability until very recently. In this tutorial paper, we start
by presenting gradient-based interpretability methods. These techniques use
gradient signals to assign the burden of the decision on the input features.
Later, we discuss how gradient-based methods can be evaluated for their
robustness and the role that adversarial robustness plays in having meaningful
explanations. We also discuss the limitations of gradient-based methods.
Finally, we present the best practices and attributes that should be examined
before choosing an explainability method. We conclude with the future
directions for research in the area at the convergence of robustness and
explainability.

negative:
A main puzzle of deep networks revolves around the absence of overfitting
despite large overparametrization and despite the large capacity demonstrated
by zero training error on randomly labeled data. In this note, we show that the
dynamics associated to gradient descent minimization of nonlinear networks is
topologically equivalent, near the asymptotically stable minima of the
empirical error, to linear gradient system in a quadratic potential with a
degenerate (for square loss) or almost degenerate (for logistic or crossentropy
loss) Hessian. The proposition depends on the qualitative theory of dynamical
systems and is supported by numerical results. Our main propositions extend to
deep nonlinear networks two properties of gradient descent for linear networks,
that have been recently established (1) to be key to their generalization
properties: 1. Gradient descent enforces a form of implicit regularization
controlled by the number of iterations, and asymptotically converges to the
minimum norm solution for appropriate initial conditions of gradient descent.
This implies that there is usually an optimum early stopping that avoids
overfitting of the loss. This property, valid for the square loss and many
other loss functions, is relevant especially for regression. 2. For
classification, the asymptotic convergence to the minimum norm solution implies
convergence to the maximum margin solution which guarantees good classification
error for "low noise" datasets. This property holds for loss functions such as
the logistic and cross-entropy loss independently of the initial conditions.
The robustness to overparametrization has suggestive implications for the
robustness of the architecture of deep convolutional networks with respect to
the curse of dimensionality.

negative:
Generative adversarial networks have been very successful in generative
modeling, however they remain relatively challenging to train compared to
standard deep neural networks. In this paper, we propose new visualization
techniques for the optimization landscapes of GANs that enable us to study the
game vector field resulting from the concatenation of the gradient of both
players. Using these visualization techniques we try to bridge the gap between
theory and practice by showing empirically that the training of GANs exhibits
significant rotations around Local Stable Stationary Points (LSSP), similar to
the one predicted by theory on toy examples. Moreover, we provide empirical
evidence that GAN training converge to a stable stationary point which is a
saddle point for the generator loss, not a minimum, while still achieving
excellent performance.

negative:
Zero-sum stochastic games are easy to solve as they can be cast as simple
Markov decision processes. This is however not the case with general-sum
stochastic games. A fairly general optimization problem formulation is
available for general-sum stochastic games by Filar and Vrieze [2004]. However,
the optimization problem there has a non-linear objective and non-linear
constraints with special structure. Since gradients of both the objective as
well as constraints of this optimization problem are well defined, gradient
based schemes seem to be a natural choice. We discuss a gradient scheme tuned
for two-player stochastic games. We show in simulations that this scheme indeed
converges to a Nash equilibrium, for a simple terrain exploration problem
modelled as a general-sum stochastic game. However, it turns out that only
global minima of the optimization problem correspond to Nash equilibria of the
underlying general-sum stochastic game, while gradient schemes only guarantee
convergence to local minima. We then provide important necessary conditions for
gradient schemes to converge to Nash equilibria in general-sum stochastic
games.

negative:
Gradient descent can be surprisingly good at optimizing deep neural networks
without overfitting and without explicit regularization. We find that the
discrete steps of gradient descent implicitly regularize models by penalizing
gradient descent trajectories that have large loss gradients. We call this
Implicit Gradient Regularization (IGR) and we use backward error analysis to
calculate the size of this regularization. We confirm empirically that implicit
gradient regularization biases gradient descent toward flat minima, where test
errors are small and solutions are robust to noisy parameter perturbations.
Furthermore, we demonstrate that the implicit gradient regularization term can
be used as an explicit regularizer, allowing us to control this gradient
regularization directly. More broadly, our work indicates that backward error
analysis is a useful theoretical approach to the perennial question of how
learning rate, model size, and parameter regularization interact to determine
the properties of overparameterized models optimized with gradient descent.

negative:
There are much recent interests in solving noncovnex min-max optimization
problems due to its broad applications in many areas including machine
learning, networked resource allocations, and distributed optimization.
Perhaps, the most popular first-order method in solving min-max optimization is
the so-called simultaneous (or single-loop) gradient descent-ascent algorithm
due to its simplicity in implementation. However, theoretical guarantees on the
convergence of this algorithm is very sparse since it can diverge even in a
simple bilinear problem.
  In this paper, our focus is to characterize the finite-time performance (or
convergence rates) of the continuous-time variant of simultaneous gradient
descent-ascent algorithm. In particular, we derive the rates of convergence of
this method under a number of different conditions on the underlying objective
function, namely, two-sided Polyak-L ojasiewicz (PL), one-sided PL,
nonconvex-strongly concave, and strongly convex-nonconcave conditions. Our
convergence results improve the ones in prior works under the same conditions
of objective functions. The key idea in our analysis is to use the classic
singular perturbation theory and coupling Lyapunov functions to address the
time-scale difference and interactions between the gradient descent and ascent
dynamics. Our results on the behavior of continuous-time algorithm may be used
to enhance the convergence properties of its discrete-time counterpart.

negative:
We consider the behavior of gradient flow and of discrete and noisy gradient
descent. It is commonly noted that the addition of noise to the process of
discrete gradient descent can affect the trajectory of gradient descent. In
previous work, we observed such effects. There, we considered the case where
the minima had codimension 1. In this note, we do some computer experiments and
observe the behavior of noisy gradient descent in the more complex setting of
minima of higher codimension.

negative:
Deep learning is built on the foundational guarantee that gradient descent on
an objective function converges to local minima. Unfortunately, this guarantee
fails in settings, such as generative adversarial nets, that exhibit multiple
interacting losses. The behavior of gradient-based methods in games is not well
understood -- and is becoming increasingly important as adversarial and
multi-objective architectures proliferate. In this paper, we develop new tools
to understand and control the dynamics in n-player differentiable games.
  The key result is to decompose the game Jacobian into two components. The
first, symmetric component, is related to potential games, which reduce to
gradient descent on an implicit function. The second, antisymmetric component,
relates to Hamiltonian games, a new class of games that obey a conservation law
akin to conservation laws in classical mechanical systems. The decomposition
motivates Symplectic Gradient Adjustment (SGA), a new algorithm for finding
stable fixed points in differentiable games. Basic experiments show SGA is
competitive with recently proposed algorithms for finding stable fixed points
in GANs -- while at the same time being applicable to, and having guarantees
in, much more general cases.

negative:
Stochastic gradient descent is an optimisation method that combines classical
gradient descent with random subsampling within the target functional. In this
work, we introduce the stochastic gradient process as a continuous-time
representation of stochastic gradient descent. The stochastic gradient process
is a dynamical system that is coupled with a continuous-time Markov process
living on a finite state space. The dynamical system -- a gradient flow --
represents the gradient descent part, the process on the finite state space
represents the random subsampling. Processes of this type are, for instance,
used to model clonal populations in fluctuating environments. After introducing
it, we study theoretical properties of the stochastic gradient process: We show
that it converges weakly to the gradient flow with respect to the full target
function, as the learning rate approaches zero. We give conditions under which
the stochastic gradient process with constant learning rate is exponentially
ergodic in the Wasserstein sense. Then we study the case, where the learning
rate goes to zero sufficiently slowly and the single target functions are
strongly convex. In this case, the process converges weakly to the point mass
concentrated in the global minimum of the full target function; indicating
consistency of the method. We conclude after a discussion of discretisation
strategies for the stochastic gradient process and numerical experiments.

negative:
Generative adversarial networks (GANs) represent a zero-sum game between two
machine players, a generator and a discriminator, designed to learn the
distribution of data. While GANs have achieved state-of-the-art performance in
several benchmark learning tasks, GAN minimax optimization still poses great
theoretical and empirical challenges. GANs trained using first-order
optimization methods commonly fail to converge to a stable solution where the
players cannot improve their objective, i.e., the Nash equilibrium of the
underlying game. Such issues raise the question of the existence of Nash
equilibrium solutions in the GAN zero-sum game. In this work, we show through
several theoretical and numerical results that indeed GAN zero-sum games may
not have any local Nash equilibria. To characterize an equilibrium notion
applicable to GANs, we consider the equilibrium of a new zero-sum game with an
objective function given by a proximal operator applied to the original
objective, a solution we call the proximal equilibrium. Unlike the Nash
equilibrium, the proximal equilibrium captures the sequential nature of GANs,
in which the generator moves first followed by the discriminator. We prove that
the optimal generative model in Wasserstein GAN problems provides a proximal
equilibrium. Inspired by these results, we propose a new approach, which we
call proximal training, for solving GAN problems. We discuss several numerical
experiments demonstrating the existence of proximal equilibrium solutions in
GAN minimax problems.

negative:
The theory of integral quadratic constraints (IQCs) allows the certification
of exponential convergence of interconnected systems containing nonlinear or
uncertain elements. In this work, we adapt the IQC theory to study first-order
methods for smooth and strongly-monotone games and show how to design tailored
quadratic constraints to get tight upper bounds of convergence rates. Using
this framework, we recover the existing bound for the gradient method~(GD),
derive sharper bounds for the proximal point method~(PPM) and optimistic
gradient method~(OG), and provide \emph{for the first time} a global
convergence rate for the negative momentum method~(NM) with an iteration
complexity $\mathcal{O}(\kappa^{1.5})$, which matches its known lower bound. In
addition, for time-varying systems, we prove that the gradient method with
optimal step size achieves the fastest provable worst-case convergence rate
with quadratic Lyapunov functions. Finally, we further extend our analysis to
stochastic games and study the impact of multiplicative noise on different
algorithms. We show that it is impossible for an algorithm with one step of
memory to achieve acceleration if it only queries the gradient once per batch
(in contrast with the stochastic strongly-convex optimization setting, where
such acceleration has been demonstrated). However, we exhibit an algorithm
which achieves acceleration with two gradient queries per batch.

negative:
In this paper, we aim at providing an introduction to the gradient descent
based optimization algorithms for learning deep neural network models. Deep
learning models involving multiple nonlinear projection layers are very
challenging to train. Nowadays, most of the deep learning model training still
relies on the back propagation algorithm actually. In back propagation, the
model variables will be updated iteratively until convergence with gradient
descent based optimization algorithms. Besides the conventional vanilla
gradient descent algorithm, many gradient descent variants have also been
proposed in recent years to improve the learning performance, including
Momentum, Adagrad, Adam, Gadam, etc., which will all be introduced in this
paper respectively.

negative:
The objective of a reinforcement learning agent is to behave so as to
maximise the sum of a suitable scalar function of state: the reward. These
rewards are typically given and immutable. In this paper, we instead consider
the proposition that the reward function itself can be a good locus of learned
knowledge. To investigate this, we propose a scalable meta-gradient framework
for learning useful intrinsic reward functions across multiple lifetimes of
experience. Through several proof-of-concept experiments, we show that it is
feasible to learn and capture knowledge about long-term exploration and
exploitation into a reward function. Furthermore, we show that unlike policy
transfer methods that capture "how" the agent should behave, the learned reward
functions can generalise to other kinds of agents and to changes in the
dynamics of the environment by capturing "what" the agent should strive to do.

negative:
Physics-informed neural networks (PINNs) have lately received great attention
thanks to their flexibility in tackling a wide range of forward and inverse
problems involving partial differential equations. However, despite their
noticeable empirical success, little is known about how such constrained neural
networks behave during their training via gradient descent. More importantly,
even less is known about why such models sometimes fail to train at all. In
this work, we aim to investigate these questions through the lens of the Neural
Tangent Kernel (NTK); a kernel that captures the behavior of fully-connected
neural networks in the infinite width limit during training via gradient
descent. Specifically, we derive the NTK of PINNs and prove that, under
appropriate conditions, it converges to a deterministic kernel that stays
constant during training in the infinite-width limit. This allows us to analyze
the training dynamics of PINNs through the lens of their limiting NTK and find
a remarkable discrepancy in the convergence rate of the different loss
components contributing to the total training error. To address this
fundamental pathology, we propose a novel gradient descent algorithm that
utilizes the eigenvalues of the NTK to adaptively calibrate the convergence
rate of the total training error. Finally, we perform a series of numerical
experiments to verify the correctness of our theory and the practical
effectiveness of the proposed algorithms. The data and code accompanying this
manuscript are publicly available at
\url{https://github.com/PredictiveIntelligenceLab/PINNsNTK}.

negative:
We study the problem of training deep neural networks with Rectified Linear
Unit (ReLU) activation function using gradient descent and stochastic gradient
descent. In particular, we study the binary classification problem and show
that for a broad family of loss functions, with proper random weight
initialization, both gradient descent and stochastic gradient descent can find
the global minima of the training loss for an over-parameterized deep ReLU
network, under mild assumption on the training data. The key idea of our proof
is that Gaussian random initialization followed by (stochastic) gradient
descent produces a sequence of iterates that stay inside a small perturbation
region centering around the initial weights, in which the empirical loss
function of deep ReLU networks enjoys nice local curvature properties that
ensure the global convergence of (stochastic) gradient descent. Our theoretical
results shed light on understanding the optimization for deep learning, and
pave the way for studying the optimization dynamics of training modern deep
neural networks.

negative:
In this paper, we analyze the optimization landscape of gradient descent
methods for static output feedback (SOF) control of discrete-time linear
time-invariant systems with quadratic cost. The SOF setting can be quite
common, for example, when there are unmodeled hidden states in the underlying
process. We first establish several important properties of the SOF cost
function, including coercivity, L-smoothness, and M-Lipschitz continuous
Hessian. We then utilize these properties to show that the gradient descent is
able to converge to a stationary point at a dimension-free rate. Furthermore,
we prove that under some mild conditions, gradient descent converges linearly
to a local minimum if the starting point is close to one. These results not
only characterize the performance of gradient descent in optimizing the SOF
problem, but also shed light on the efficiency of general policy gradient
methods in reinforcement learning.

negative:
In this paper we investigate how gradient-based algorithms such as gradient
descent, (multi-pass) stochastic gradient descent, its persistent variant, and
the Langevin algorithm navigate non-convex loss-landscapes and which of them is
able to reach the best generalization error at limited sample complexity. We
consider the loss landscape of the high-dimensional phase retrieval problem as
a prototypical highly non-convex example. We observe that for phase retrieval
the stochastic variants of gradient descent are able to reach perfect
generalization for regions of control parameters where the gradient descent
algorithm is not. We apply dynamical mean-field theory from statistical physics
to characterize analytically the full trajectories of these algorithms in their
continuous-time limit, with a warm start, and for large system sizes. We
further unveil several intriguing properties of the landscape and the
algorithms such as that the gradient descent can obtain better generalization
properties from less informed initializations.

negative:
Alternating gradient-descent-ascent (AltGDA) is an optimization algorithm
that has been widely used for model training in various machine learning
applications, which aims to solve a nonconvex minimax optimization problem.
However, the existing studies show that it suffers from a high computation
complexity in nonconvex minimax optimization. In this paper, we develop a
single-loop and fast AltGDA-type algorithm that leverages proximal gradient
updates and momentum acceleration to solve regularized nonconvex minimax
optimization problems. By leveraging the momentum acceleration technique, we
prove that the algorithm converges to a critical point in nonconvex minimax
optimization and achieves a computation complexity in the order of
$\mathcal{O}(\kappa^{\frac{11}{6}}\epsilon^{-2})$, where $\epsilon$ is the
desired level of accuracy and $\kappa$ is the problem's condition number. {Such
a computation complexity improves the state-of-the-art complexities of
single-loop GDA and AltGDA algorithms (see the summary of comparison in
\Cref{table1})}. We demonstrate the effectiveness of our algorithm via an
experiment on adversarial deep learning.

negative:
The success of adversarial formulations in machine learning has brought
renewed motivation for smooth games. In this work, we focus on the class of
stochastic Hamiltonian methods and provide the first convergence guarantees for
certain classes of stochastic smooth games. We propose a novel unbiased
estimator for the stochastic Hamiltonian gradient descent (SHGD) and highlight
its benefits. Using tools from the optimization literature we show that SHGD
converges linearly to the neighbourhood of a stationary point. To guarantee
convergence to the exact solution, we analyze SHGD with a decreasing step-size
and we also present the first stochastic variance reduced Hamiltonian method.
Our results provide the first global non-asymptotic last-iterate convergence
guarantees for the class of stochastic unconstrained bilinear games and for the
more general class of stochastic games that satisfy a "sufficiently bilinear"
condition, notably including some non-convex non-concave problems. We
supplement our analysis with experiments on stochastic bilinear and
sufficiently bilinear games, where our theory is shown to be tight, and on
simple adversarial machine learning formulations.

negative:
Although recent work in AI has made great progress in solving large,
zero-sum, extensive-form games, the underlying assumption in most past work is
that the parameters of the game itself are known to the agents. This paper
deals with the relatively under-explored but equally important "inverse"
setting, where the parameters of the underlying game are not known to all
agents, but must be learned through observations. We propose a differentiable,
end-to-end learning framework for addressing this task. In particular, we
consider a regularized version of the game, equivalent to a particular form of
quantal response equilibrium, and develop 1) a primal-dual Newton method for
finding such equilibrium points in both normal and extensive form games; and 2)
a backpropagation method that lets us analytically compute gradients of all
relevant game parameters through the solution itself. This ultimately lets us
learn the game by training in an end-to-end fashion, effectively by integrating
a "differentiable game solver" into the loop of larger deep network
architectures. We demonstrate the effectiveness of the learning method in
several settings including poker and security game tasks.

negative:
With the recent advances in solving large, zero-sum extensive form games,
there is a growing interest in the inverse problem of inferring underlying game
parameters given only access to agent actions. Although a recent work provides
a powerful differentiable end-to-end learning frameworks which embed a game
solver within a deep-learning framework, allowing unknown game parameters to be
learned via backpropagation, this framework faces significant limitations when
applied to boundedly rational human agents and large scale problems, leading to
poor practicality. In this paper, we address these limitations and propose a
framework that is applicable for more practical settings. First, seeking to
learn the rationality of human agents in complex two-player zero-sum games, we
draw upon well-known ideas in decision theory to obtain a concise and
interpretable agent behavior model, and derive solvers and gradients for
end-to-end learning. Second, to scale up to large, real-world scenarios, we
propose an efficient first-order primal-dual method which exploits the
structure of extensive-form games, yielding significantly faster computation
for both game solving and gradient computation. When tested on randomly
generated games, we report speedups of orders of magnitude over previous
approaches. We also demonstrate the effectiveness of our model on both
real-world one-player settings and synthetic data.

negative:
The advancement of artificial intelligence has cast a new light on the
development of optimization algorithm. This paper proposes to learn a two-phase
(including a minimization phase and an escaping phase) global optimization
algorithm for smooth non-convex functions. For the minimization phase, a
model-driven deep learning method is developed to learn the update rule of
descent direction, which is formalized as a nonlinear combination of historical
information, for convex functions. We prove that the resultant algorithm with
the proposed adaptive direction guarantees convergence for convex functions.
Empirical study shows that the learned algorithm significantly outperforms some
well-known classical optimization algorithms, such as gradient descent,
conjugate descent and BFGS, and performs well on ill-posed functions. The
escaping phase from local optimum is modeled as a Markov decision process with
a fixed escaping policy. We further propose to learn an optimal escaping policy
by reinforcement learning. The effectiveness of the escaping policies is
verified by optimizing synthesized functions and training a deep neural network
for CIFAR image classification. The learned two-phase global optimization
algorithm demonstrates a promising global search capability on some benchmark
functions and machine learning tasks.

negative:
In this work, we propose an optimization algorithm which we call norm-adapted
gradient descent. This algorithm is similar to other gradient-based
optimization algorithms like Adam or Adagrad in that it adapts the learning
rate of stochastic gradient descent at each iteration. However, rather than
using statistical properties of observed gradients, norm-adapted gradient
descent relies on a first-order estimate of the effect of a standard gradient
descent update step, much like the Newton-Raphson method in many dimensions.
Our algorithm can also be compared to quasi-Newton methods, but we seek roots
rather than stationary points. Seeking roots can be justified by the fact that
for models with sufficient capacity measured by nonnegative loss functions,
roots coincide with global optima. This work presents several experiments where
we have used our algorithm; in these results, it appears norm-adapted descent
is particularly strong in regression settings but is also capable of training
classifiers.

negative:
Understanding the implicit bias of training algorithms is of crucial
importance in order to explain the success of overparametrised neural networks.
In this paper, we study the dynamics of stochastic gradient descent over
diagonal linear networks through its continuous time version, namely stochastic
gradient flow. We explicitly characterise the solution chosen by the stochastic
flow and prove that it always enjoys better generalisation properties than that
of gradient flow. Quite surprisingly, we show that the convergence speed of the
training loss controls the magnitude of the biasing effect: the slower the
convergence, the better the bias. To fully complete our analysis, we provide
convergence guarantees for the dynamics. We also give experimental results
which support our theoretical claims. Our findings highlight the fact that
structured noise can induce better generalisation and they help explain the
greater performances observed in practice of stochastic gradient descent over
gradient descent.

negative:
Natural gradient descent is an optimization method traditionally motivated
from the perspective of information geometry, and works well for many
applications as an alternative to stochastic gradient descent. In this paper we
critically analyze this method and its properties, and show how it can be
viewed as a type of 2nd-order optimization method, with the Fisher information
matrix acting as a substitute for the Hessian. In many important cases, the
Fisher information matrix is shown to be equivalent to the Generalized
Gauss-Newton matrix, which both approximates the Hessian, but also has certain
properties that favor its use over the Hessian. This perspective turns out to
have significant implications for the design of a practical and robust natural
gradient optimizer, as it motivates the use of techniques like trust regions
and Tikhonov regularization. Additionally, we make a series of contributions to
the understanding of natural gradient and 2nd-order methods, including: a
thorough analysis of the convergence speed of stochastic natural gradient
descent (and more general stochastic 2nd-order methods) as applied to convex
quadratics, a critical examination of the oft-used "empirical" approximation of
the Fisher matrix, and an analysis of the (approximate) parameterization
invariance property possessed by natural gradient methods (which we show also
holds for certain other curvature, but notably not the Hessian).

negative:
We consider the problem of two-player zero-sum games. This problem is
formulated as a min-max Markov game in the literature. The solution of this
game, which is the min-max payoff, starting from a given state is called the
min-max value of the state. In this work, we compute the solution of the
two-player zero-sum game utilizing the technique of successive relaxation that
has been successfully applied in the literature to compute a faster value
iteration algorithm in the context of Markov Decision Processes. We extend the
concept of successive relaxation to the setting of two-player zero-sum games.
We show that, under a special structure on the game, this technique facilitates
faster computation of the min-max value of the states. We then derive a
generalized minimax Q-learning algorithm that computes the optimal policy when
the model information is not known. Finally, we prove the convergence of the
proposed generalized minimax Q-learning algorithm utilizing stochastic
approximation techniques, under an assumption on the boundedness of iterates.
Through experiments, we demonstrate the effectiveness of our proposed
algorithm.

negative:
Minimax optimization has found extensive applications in modern machine
learning, in settings such as generative adversarial networks (GANs),
adversarial training and multi-agent reinforcement learning. As most of these
applications involve continuous nonconvex-nonconcave formulations, a very basic
question arises---"what is a proper definition of local optima?"
  Most previous work answers this question using classical notions of
equilibria from simultaneous games, where the min-player and the max-player act
simultaneously. In contrast, most applications in machine learning, including
GANs and adversarial training, correspond to sequential games, where the order
of which player acts first is crucial (since minimax is in general not equal to
maximin due to the nonconvex-nonconcave nature of the problems). The main
contribution of this paper is to propose a proper mathematical definition of
local optimality for this sequential setting---local minimax, as well as to
present its properties and existence results. Finally, we establish a strong
connection to a basic local search algorithm---gradient descent ascent (GDA):
under mild conditions, all stable limit points of GDA are exactly local minimax
points up to some degenerate points.

negative:
Gradient descent algorithms have been used in countless applications since
the inception of Newton's method. The explosion in the number of applications
of neural networks has re-energized efforts in recent years to improve the
standard gradient descent method in both efficiency and accuracy. These methods
modify the effect of the gradient in updating the values of the parameters.
These modifications often incorporate hyperparameters: additional variables
whose values must be specified at the outset of the program. We provide, below,
a novel gradient descent algorithm, called Gravilon, that uses the geometry of
the hypersurface to modify the length of the step in the direction of the
gradient. Using neural networks, we provide promising experimental results
comparing the accuracy and efficiency of the Gravilon method against commonly
used gradient descent algorithms on MNIST digit classification.

negative:
Machine learning has become successful in solving wireless interference
management problems. Different kinds of deep neural networks (DNNs) have been
trained to accomplish key tasks such as power control, beamforming and
admission control. There are two popular training paradigms for such DNNs-based
interference management models: supervised learning (i.e., fitting labels
generated by an optimization algorithm) and unsupervised learning (i.e.,
directly optimizing some system performance measure). Although both of these
paradigms have been extensively applied in practice, due to the lack of any
theoretical understanding about these methods, it is not clear how to
systematically understand and compare their performance.
  In this work, we conduct theoretical studies to provide some in-depth
understanding about these two training paradigms. First, we show a somewhat
surprising result, that for some special power control problem, the
unsupervised learning can perform much worse than its supervised counterpart,
because it is more likely to stuck at some low-quality local solutions. We then
provide a series of theoretical results to further understand the properties of
the two approaches. Generally speaking, we show that when high-quality labels
are available, then the supervised learning is less likely to be stuck at a
solution than its unsupervised counterpart. Additionally, we develop a
semi-supervised learning approach which properly integrates these two training
paradigms, and can effectively utilize limited number of labels to find
high-quality solutions. To our knowledge, these are the first set of
theoretical results trying to understand different training approaches in
learning-based wireless communication system design.

negative:
Batch Normalization (BN) has become a cornerstone of deep learning across
diverse architectures, appearing to help optimization as well as
generalization. While the idea makes intuitive sense, theoretical analysis of
its effectiveness has been lacking. Here theoretical support is provided for
one of its conjectured properties, namely, the ability to allow gradient
descent to succeed with less tuning of learning rates. It is shown that even if
we fix the learning rate of scale-invariant parameters (e.g., weights of each
layer with BN) to a constant (say, $0.3$), gradient descent still approaches a
stationary point (i.e., a solution where gradient is zero) in the rate of
$T^{-1/2}$ in $T$ iterations, asymptotically matching the best bound for
gradient descent with well-tuned learning rates. A similar result with
convergence rate $T^{-1/4}$ is also shown for stochastic gradient descent.

negative:
We study the iteration complexity of the optimistic gradient descent-ascent
(OGDA) method and the extra-gradient (EG) method for finding a saddle point of
a convex-concave unconstrained min-max problem. To do so, we first show that
both OGDA and EG can be interpreted as approximate variants of the proximal
point method. This is similar to the approach taken in [Nemirovski, 2004] which
analyzes EG as an approximation of the `conceptual mirror prox'. In this paper,
we highlight how gradients used in OGDA and EG try to approximate the gradient
of the Proximal Point method. We then exploit this interpretation to show that
both algorithms produce iterates that remain within a bounded set. We further
show that the primal dual gap of the averaged iterates generated by both of
these algorithms converge with a rate of $\mathcal{O}(1/k)$. Our theoretical
analysis is of interest as it provides a the first convergence rate estimate
for OGDA in the general convex-concave setting. Moreover, it provides a simple
convergence analysis for the EG algorithm in terms of function value without
using compactness assumption.

negative:
We design and analyze minimax-optimal algorithms for online linear
optimization games where the player's choice is unconstrained. The player
strives to minimize regret, the difference between his loss and the loss of a
post-hoc benchmark strategy. The standard benchmark is the loss of the best
strategy chosen from a bounded comparator set. When the the comparison set and
the adversary's gradients satisfy L_infinity bounds, we give the value of the
game in closed form and prove it approaches sqrt(2T/pi) as T -> infinity.
  Interesting algorithms result when we consider soft constraints on the
comparator, rather than restricting it to a bounded set. As a warmup, we
analyze the game with a quadratic penalty. The value of this game is exactly
T/2, and this value is achieved by perhaps the simplest online algorithm of
all: unprojected gradient descent with a constant learning rate.
  We then derive a minimax-optimal algorithm for a much softer penalty
function. This algorithm achieves good bounds under the standard notion of
regret for any comparator point, without needing to specify the comparator set
in advance. The value of this game converges to sqrt{e} as T ->infinity; we
give a closed-form for the exact value as a function of T. The resulting
algorithm is natural in unconstrained investment or betting scenarios, since it
guarantees at worst constant loss, while allowing for exponential reward
against an "easy" adversary.

negative:
Bayesian optimization has demonstrated impressive success in finding the
optimum input x* and output f* = f(x*) = max f(x) of a black-box function f. In
some applications, however, the optimum output f* is known in advance and the
goal is to find the corresponding optimum input x*. In this paper, we consider
a new setting in BO in which the knowledge of the optimum output f* is
available. Our goal is to exploit the knowledge about f* to search for the
input x* efficiently. To achieve this goal, we first transform the Gaussian
process surrogate using the information about the optimum output. Then, we
propose two acquisition functions, called confidence bound minimization and
expected regret minimization. We show that our approaches work intuitively and
give quantitatively better performance against standard BO methods. We
demonstrate real applications in tuning a deep reinforcement learning algorithm
on the CartPole problem and XGBoost on Skin Segmentation dataset in which the
optimum values are publicly available.

negative:
The plain stochastic gradient descent and momentum stochastic gradient
descent have extremely wide applications in deep learning due to their simple
settings and low computational complexity. The momentum stochastic gradient
descent uses the accumulated gradient as the updated direction of the current
parameters, which has a faster training speed. Because the direction of the
plain stochastic gradient descent has not been corrected by the accumulated
gradient. For the parameters that currently need to be updated, it is the
optimal direction, and its update is more accurate. We combine the advantages
of the momentum stochastic gradient descent with fast training speed and the
plain stochastic gradient descent with high accuracy, and propose a scaling
transition from momentum stochastic gradient descent to plain stochastic
gradient descent(TSGD) method. At the same time, a learning rate that decreases
linearly with the iterations is used instead of a constant learning rate. The
TSGD algorithm has a larger step size in the early stage to speed up the
training, and training with a smaller step size in the later stage can steadily
converge. Our experimental results show that the TSGD algorithm has faster
training speed, higher accuracy and better stability. Our implementation is
available at: https://github.com/kunzeng/TSGD.

negative:
In this paper, we study the implicit regularization of the gradient descent
algorithm in homogeneous neural networks, including fully-connected and
convolutional neural networks with ReLU or LeakyReLU activations. In
particular, we study the gradient descent or gradient flow (i.e., gradient
descent with infinitesimal step size) optimizing the logistic loss or
cross-entropy loss of any homogeneous model (possibly non-smooth), and show
that if the training loss decreases below a certain threshold, then we can
define a smoothed version of the normalized margin which increases over time.
We also formulate a natural constrained optimization problem related to margin
maximization, and prove that both the normalized margin and its smoothed
version converge to the objective value at a KKT point of the optimization
problem. Our results generalize the previous results for logistic regression
with one-layer or multi-layer linear networks, and provide more quantitative
convergence results with weaker assumptions than previous results for
homogeneous smooth neural networks. We conduct several experiments to justify
our theoretical finding on MNIST and CIFAR-10 datasets. Finally, as margin is
closely related to robustness, we discuss potential benefits of training longer
for improving the robustness of the model.

negative:
The goal of multi-task learning is to enable more efficient learning than
single task learning by sharing model structures for a diverse set of tasks. A
standard multi-task learning objective is to minimize the average loss across
all tasks. While straightforward, using this objective often results in much
worse final performance for each task than learning them independently. A major
challenge in optimizing a multi-task model is the conflicting gradients, where
gradients of different task objectives are not well aligned so that following
the average gradient direction can be detrimental to specific tasks'
performance. Previous work has proposed several heuristics to manipulate the
task gradients for mitigating this problem. But most of them lack convergence
guarantee and/or could converge to any Pareto-stationary point. In this paper,
we introduce Conflict-Averse Gradient descent (CAGrad) which minimizes the
average loss function, while leveraging the worst local improvement of
individual tasks to regularize the algorithm trajectory. CAGrad balances the
objectives automatically and still provably converges to a minimum over the
average loss. It includes the regular gradient descent (GD) and the multiple
gradient descent algorithm (MGDA) in the multi-objective optimization (MOO)
literature as special cases. On a series of challenging multi-task supervised
learning and reinforcement learning tasks, CAGrad achieves improved performance
over prior state-of-the-art multi-objective gradient manipulation methods.

negative:
Given that in practice training data is scarce for all but a small set of
problems, a core question is how to incorporate prior knowledge into a model.
In this paper, we consider the case of prior procedural knowledge for neural
networks, such as knowing how a program should traverse a sequence, but not
what local actions should be performed at each step. To this end, we present an
end-to-end differentiable interpreter for the programming language Forth which
enables programmers to write program sketches with slots that can be filled
with behaviour trained from program input-output data. We can optimise this
behaviour directly through gradient descent techniques on user-specified
objectives, and also integrate the program into any larger neural computation
graph. We show empirically that our interpreter is able to effectively leverage
different levels of prior program structure and learn complex behaviours such
as sequence sorting and addition. When connected to outputs of an LSTM and
trained jointly, our interpreter achieves state-of-the-art accuracy for
end-to-end reasoning about quantities expressed in natural language stories.

negative:
We analyze stochastic gradient descent for optimizing non-convex functions.
In many cases for non-convex functions the goal is to find a reasonable local
minimum, and the main concern is that gradient updates are trapped in saddle
points. In this paper we identify strict saddle property for non-convex problem
that allows for efficient optimization. Using this property we show that
stochastic gradient descent converges to a local minimum in a polynomial number
of iterations. To the best of our knowledge this is the first work that gives
global convergence guarantees for stochastic gradient descent on non-convex
functions with exponentially many local minima and saddle points. Our analysis
can be applied to orthogonal tensor decomposition, which is widely used in
learning a rich class of latent variable models. We propose a new optimization
formulation for the tensor decomposition problem that has strict saddle
property. As a result we get the first online algorithm for orthogonal tensor
decomposition with global convergence guarantee.

negative:
Applications of machine learning inform human decision makers in a broad
range of tasks. The resulting problem is usually formulated in terms of a
single decision maker. We argue that it should rather be described as a
two-player learning problem where one player is the machine and the other the
human. While both players try to optimize the final decision, the setup is
often characterized by (1) the presence of private information and (2) opacity,
that is imperfect understanding between the decision makers. We prove that both
properties can complicate decision making considerably. A lower bound
quantifies the worst-case hardness of optimally advising a decision maker who
is opaque or has access to private information. An upper bound shows that a
simple coordination strategy is nearly minimax optimal. More efficient learning
is possible under certain assumptions on the problem, for example that both
players learn to take actions independently. Such assumptions are implicit in
existing literature, for example in medical applications of machine learning,
but have not been described or justified theoretically.

negative:
With the vigorous development of artificial intelligence technology, various
engineering technology applications have been implemented one after another.
The gradient descent method plays an important role in solving various
optimization problems, due to its simple structure, good stability and easy
implementation. In multi-node machine learning system, the gradients usually
need to be shared. Shared gradients are generally unsafe. Attackers can obtain
training data simply by knowing the gradient information. In this paper, to
prevent gradient leakage while keeping the accuracy of model, we propose the
super stochastic gradient descent approach to update parameters by concealing
the modulus length of gradient vectors and converting it or them into a unit
vector. Furthermore, we analyze the security of super stochastic gradient
descent approach. Our algorithm can defend against attacks on the gradient.
Experiment results show that our approach is obviously superior to prevalent
gradient descent approaches in terms of accuracy, robustness, and adaptability
to large-scale batches.

negative:
Gradient descent optimization algorithms are the standard ingredients that
are used to train artificial neural networks (ANNs). Even though a huge number
of numerical simulations indicate that gradient descent optimization methods do
indeed convergence in the training of ANNs, until today there is no rigorous
theoretical analysis which proves (or disproves) this conjecture. In
particular, even in the case of the most basic variant of gradient descent
optimization algorithms, the plain vanilla gradient descent method, it remains
an open problem to prove or disprove the conjecture that gradient descent
converges in the training of ANNs. In this article we solve this problem in the
special situation where the target function under consideration is a constant
function. More specifically, in the case of constant target functions we prove
in the training of rectified fully-connected feedforward ANNs with one-hidden
layer that the risk function of the gradient descent method does indeed
converge to zero. Our mathematical analysis strongly exploits the property that
the rectifier function is the activation function used in the considered ANNs.
A key contribution of this work is to explicitly specify a Lyapunov function
for the gradient flow system of the ANN parameters. This Lyapunov function is
the central tool in our convergence proof of the gradient descent method.

negative:
The rise in machine learning-assisted decision-making has led to concerns
about the fairness of the decisions and techniques to mitigate problems of
discrimination. If a negative decision is made about an individual (denying a
loan, rejecting an application for housing, and so on) justice dictates that we
be able to ask how we might change circumstances to get a favorable decision
the next time. Moreover, the ability to change circumstances (a better
education, improved credentials) should not be limited to only those with
access to expensive resources. In other words, \emph{recourse} for negative
decisions should be considered a desirable value that can be equalized across
(demographically defined) groups. This paper describes how to build models that
make accurate predictions while still ensuring that the penalties for a
negative outcome do not disadvantage different groups disproportionately. We
measure recourse as the distance of an individual from the decision boundary of
a classifier. We then introduce a regularized objective to minimize the
difference in recourse across groups. We explore linear settings and further
extend recourse to non-linear settings as well as model-agnostic settings where
the exact distance from boundary cannot be calculated. Our results show that we
can successfully decrease the unfairness in recourse while maintaining
classifier performance.

negative:
We review the theory of, and develop algorithms for transforming a finite
point set in ${\bf R}^d$ into a set in \emph{radial isotropic position} by a
nonsingular linear transformation followed by rescaling each image point to the
unit sphere. This problem arises in a wide spectrum of applications in computer
science and mathematics.
  Our algorithms use gradient descent methods for a particular convex function
$f$ whose minimum defines the transformation, and our main focus is on
analyzing their performance. Although the minimum can be computed exactly, by
expensive symbolic algebra techniques, gradient descent only approximates the
desired minimum to any desired level of accuracy. We show that computing the
gradient of $f$ amounts to computing the Singular Value Decomposition (SVD) of
a certain matrix associated with the input set, making it simple to implement.
We believe it to be superior to other approximate techniques (mainly the
ellipsoid algorithm) used previously to find this transformation, and it should
run much faster in practice.
  We prove that $f$ is smooth, which yields convergence rate proportional to
$1/\epsilon$, where $\epsilon$ is the desired approximation accuracy. To
complete the analysis, we provide upper bounds on the norm of the optimal
solution which depend on new parameters measuring "the degeneracy" in our
input. We believe that our parameters capture degeneracy better than other,
seemingly weaker, parameters used in previous works.
  We next analyze the strong convexity of $f$, and present two worst-case lower
bounds on the smallest eigenvalue of its Hessian. This gives another worst-case
bound on the convergence rate of another variant of gradient decent that
depends only logarithmically on $1/\epsilon$.

negative:
Many binary classification problems minimize misclassification above (or
below) a threshold. We show that instances of ranking problems, accuracy at the
top or hypothesis testing may be written in this form. We propose a general
framework to handle these classes of problems and show which known methods
(both known and newly proposed) fall into this framework. We provide a
theoretical analysis of this framework and mention selected possible pitfalls
the methods may encounter. We suggest several numerical improvements including
the implicit derivative and stochastic gradient descent. We provide an
extensive numerical study. Based both on the theoretical properties and
numerical experiments, we conclude the paper by suggesting which method should
be used in which situation.

negative:
Learning to learn is a powerful paradigm for enabling models to learn from
data more effectively and efficiently. A popular approach to meta-learning is
to train a recurrent model to read in a training dataset as input and output
the parameters of a learned model, or output predictions for new test inputs.
Alternatively, a more recent approach to meta-learning aims to acquire deep
representations that can be effectively fine-tuned, via standard gradient
descent, to new tasks. In this paper, we consider the meta-learning problem
from the perspective of universality, formalizing the notion of learning
algorithm approximation and comparing the expressive power of the
aforementioned recurrent models to the more recent approaches that embed
gradient descent into the meta-learner. In particular, we seek to answer the
following question: does deep representation combined with standard gradient
descent have sufficient capacity to approximate any learning algorithm? We find
that this is indeed true, and further find, in our experiments, that
gradient-based meta-learning consistently leads to learning strategies that
generalize more widely compared to those represented by recurrent models.

negative:
We propose gradient adversarial training, an auxiliary deep learning
framework applicable to different machine learning problems. In gradient
adversarial training, we leverage a prior belief that in many contexts,
simultaneous gradient updates should be statistically indistinguishable from
each other. We enforce this consistency using an auxiliary network that
classifies the origin of the gradient tensor, and the main network serves as an
adversary to the auxiliary network in addition to performing standard
task-based training. We demonstrate gradient adversarial training for three
different scenarios: (1) as a defense to adversarial examples we classify
gradient tensors and tune them to be agnostic to the class of their
corresponding example, (2) for knowledge distillation, we do binary
classification of gradient tensors derived from the student or teacher network
and tune the student gradient tensor to mimic the teacher's gradient tensor;
and (3) for multi-task learning we classify the gradient tensors derived from
different task loss functions and tune them to be statistically
indistinguishable. For each of the three scenarios we show the potential of
gradient adversarial training procedure. Specifically, gradient adversarial
training increases the robustness of a network to adversarial attacks, is able
to better distill the knowledge from a teacher network to a student network
compared to soft targets, and boosts multi-task learning by aligning the
gradient tensors derived from the task specific loss functions. Overall, our
experiments demonstrate that gradient tensors contain latent information about
whatever tasks are being trained, and can support diverse machine learning
problems when intelligently guided through adversarialization using a auxiliary
network.

negative:
The backpropagation algorithm, which had been originally introduced in the
1970s, is the workhorse of learning in neural networks. This backpropagation
algorithm makes use of the famous machine learning algorithm known as Gradient
Descent, which is a first-order iterative optimization algorithm for finding
the minimum of a function. To find a local minimum of a function using gradient
descent, one takes steps proportional to the negative of the gradient (or of
the approximate gradient) of the function at the current point. In this paper,
we develop an alternative to the backpropagation without the use of the
Gradient Descent Algorithm, but instead we are going to devise a new algorithm
to find the error in the weights and biases of an artificial neuron using
Moore-Penrose Pseudo Inverse. The numerical studies and the experiments
performed on various datasets are used to verify the working of this
alternative algorithm.

negative:
Tensors are multidimensional arrays of numerical values and therefore
generalize matrices to multiple dimensions. While tensors first emerged in the
psychometrics community in the $20^{\text{th}}$ century, they have since then
spread to numerous other disciplines, including machine learning. Tensors and
their decompositions are especially beneficial in unsupervised learning
settings, but are gaining popularity in other sub-disciplines like temporal and
multi-relational data analysis, too.
  The scope of this paper is to give a broad overview of tensors, their
decompositions, and how they are used in machine learning. As part of this, we
are going to introduce basic tensor concepts, discuss why tensors can be
considered more rigid than matrices with respect to the uniqueness of their
decomposition, explain the most important factorization algorithms and their
properties, provide concrete examples of tensor decomposition applications in
machine learning, conduct a case study on tensor-based estimation of mixture
models, talk about the current state of research, and provide references to
available software libraries.

negative:
Domain knowledge is crucial for effective performance in autonomous control
systems. Typically, human effort is required to encode this knowledge into a
control algorithm. In this paper, we present an approach to language grounding
which automatically interprets text in the context of a complex control
application, such as a game, and uses domain knowledge extracted from the text
to improve control performance. Both text analysis and control strategies are
learned jointly using only a feedback signal inherent to the application. To
effectively leverage textual information, our method automatically extracts the
text segment most relevant to the current game state, and labels it with a
task-centric predicate structure. This labeled text is then used to bias an
action selection policy for the game, guiding it towards promising regions of
the action space. We encode our model for text analysis and game playing in a
multi-layer neural network, representing linguistic decisions via latent
variables in the hidden layers, and game action quality via the output layer.
Operating within the Monte-Carlo Search framework, we estimate model parameters
using feedback from simulated games. We apply our approach to the complex
strategy game Civilization II using the official game manual as the text guide.
Our results show that a linguistically-informed game-playing agent
significantly outperforms its language-unaware counterpart, yielding a 34%
absolute improvement and winning over 65% of games when playing against the
built-in AI of Civilization.

negative:
In this note, we observe the behavior of gradient flow and discrete and noisy
gradient descent in some simple settings. It is commonly noted that addition of
noise to gradient descent can affect the trajectory of gradient descent. Here,
we run some computer experiments for gradient descent on some simple functions,
and observe this principle in some concrete examples.

negative:
We derive a simple and model-independent formula for the change in the
generalization gap due to a gradient descent update. We then compare the change
in the test error for stochastic gradient descent to the change in test error
from an equivalent number of gradient descent updates and show explicitly that
stochastic gradient descent acts to regularize generalization error by
decorrelating nearby updates. These calculations depends on the details of the
model only through the mean and covariance of the gradient distribution, which
may be readily measured for particular models of interest. We discuss further
improvements to these calculations and comment on possible implications for
stochastic optimization.

negative:
Playing board games is considered a major challenge for both humans and AI
researchers. Because some complicated board games are quite hard to learn,
humans usually begin with playing on smaller boards and incrementally advance
to master larger board strategies. Most neural network frameworks that are
currently tasked with playing board games neither perform such incremental
learning nor possess capabilities to automatically scale up. In this work, we
look at the board as a graph and combine a graph neural network architecture
inside the AlphaZero framework, along with some other innovative improvements.
Our ScalableAlphaZero is capable of learning to play incrementally on small
boards, and advancing to play on large ones. Our model can be trained quickly
to play different challenging board games on multiple board sizes, without
using any domain knowledge. We demonstrate the effectiveness of
ScalableAlphaZero and show, for example, that by training it for only three
days on small Othello boards, it can defeat the AlphaZero model on a large
board, which was trained to play the large board for $30$ days.

negative:
Machine learning relies on the assumption that unseen test instances of a
classification problem follow the same distribution as observed training data.
However, this principle can break down when machine learning is used to make
important decisions about the welfare (employment, education, health) of
strategic individuals. Knowing information about the classifier, such
individuals may manipulate their attributes in order to obtain a better
classification outcome. As a result of this behavior---often referred to as
gaming---the performance of the classifier may deteriorate sharply. Indeed,
gaming is a well-known obstacle for using machine learning methods in practice;
in financial policy-making, the problem is widely known as Goodhart's law. In
this paper, we formalize the problem, and pursue algorithms for learning
classifiers that are robust to gaming.
  We model classification as a sequential game between a player named "Jury"
and a player named "Contestant." Jury designs a classifier, and Contestant
receives an input to the classifier, which he may change at some cost. Jury's
goal is to achieve high classification accuracy with respect to Contestant's
original input and some underlying target classification function. Contestant's
goal is to achieve a favorable classification outcome while taking into account
the cost of achieving it.
  For a natural class of cost functions, we obtain computationally efficient
learning algorithms which are near-optimal. Surprisingly, our algorithms are
efficient even on concept classes that are computationally hard to learn. For
general cost functions, designing an approximately optimal strategy-proof
classifier, for inverse-polynomial approximation, is NP-hard.

negative:
Nonlinear embedding manifold learning methods provide invaluable visual
insights into the structure of high-dimensional data. However, due to a
complicated nonconvex objective function, these methods can easily get stuck in
local minima and their embedding quality can be poor. We propose a natural
extension to several manifold learning methods aimed at identifying pressured
points, i.e. points stuck in poor local minima and have poor embedding quality.
We show that the objective function can be decreased by temporarily allowing
these points to make use of an extra dimension in the embedding space. Our
method is able to improve the objective function value of existing methods even
after they get stuck in a poor local minimum.

negative:
As the size and complexity of models and datasets grow, so does the need for
communication-efficient variants of stochastic gradient descent that can be
deployed to perform parallel model training. One popular
communication-compression method for data-parallel SGD is QSGD (Alistarh et
al., 2017), which quantizes and encodes gradients to reduce communication
costs. The baseline variant of QSGD provides strong theoretical guarantees,
however, for practical purposes, the authors proposed a heuristic variant which
we call QSGDinf, which demonstrated impressive empirical gains for distributed
training of large neural networks. In this paper, we build on this work to
propose a new gradient quantization scheme, and show that it has both stronger
theoretical guarantees than QSGD, and matches and exceeds the empirical
performance of the QSGDinf heuristic and of other compression methods.

negative:
When training the parameters of a linear dynamical model, the gradient
descent algorithm is likely to fail to converge if the squared-error loss is
used as the training loss function. Restricting the parameter space to a
smaller subset and running the gradient descent algorithm within this subset
can allow learning stable dynamical systems, but this strategy does not work
for unstable systems. In this work, we look into the dynamics of the gradient
descent algorithm and pinpoint what causes the difficulty of learning unstable
systems. We show that observations taken at different times from the system to
be learned influence the dynamics of the gradient descent algorithm in
substantially different degrees. We introduce a time-weighted logarithmic loss
function to fix this imbalance and demonstrate its effectiveness in learning
unstable systems.

negative:
Machine learning methods have gained a great deal of popularity in recent
years among public administration scholars and practitioners. These techniques
open the door to the analysis of text, image and other types of data that allow
us to test foundational theories of public administration and to develop new
theories. Despite the excitement surrounding machine learning methods, clarity
regarding their proper use and potential pitfalls is lacking. This paper
attempts to fill this gap in the literature through providing a machine
learning "guide to practice" for public administration scholars and
practitioners. Here, we take a foundational view of machine learning and
describe how these methods can enrich public administration research and
practice through their ability develop new measures, tap into new sources of
data and conduct statistical inference and causal inference in a principled
manner. We then turn our attention to the pitfalls of using these methods such
as unvalidated measures and lack of interpretability. Finally, we demonstrate
how machine learning techniques can help us learn about organizational
reputation in federal agencies through an illustrated example using tweets from
13 executive federal agencies.

negative:
Game theory provides essential analysis in many applications of strategic
interactions. However, the question of how to construct a game model and what
is its fidelity is seldom addressed. In this work, we consider learning in a
class of repeated zero-sum games with unknown, time-varying payoff matrix, and
noisy feedbacks, by making use of an ensemble of benchmark game models. These
models can be pre-trained and collected dynamically during sequential plays.
They serve as prior side information and imperfectly underpin the unknown true
game model. We propose OFULinMat, an episodic learning algorithm that
integrates the adaptive estimation of game models and the learning of the
strategies. The proposed algorithm is shown to achieve a sublinear bound on the
saddle-point regret. We show that this algorithm is provably efficient through
both theoretical analysis and numerical examples. We use a dynamic honeypot
allocation game as a case study to illustrate and corroborate our results. We
also discuss the relationship and highlight the difference between our
framework and the classical adversarial multi-armed bandit framework.

negative:
Recently, researchers have discovered that the state-of-the-art object
classifiers can be fooled easily by small perturbations in the input
unnoticeable to human eyes. It is also known that an attacker can generate
strong adversarial examples if she knows the classifier parameters. Conversely,
a defender can robustify the classifier by retraining if she has access to the
adversarial examples. We explain and formulate this adversarial example problem
as a two-player continuous zero-sum game, and demonstrate the fallacy of
evaluating a defense or an attack as a static problem. To find the best
worst-case defense against whitebox attacks, we propose a continuous minimax
optimization algorithm. We demonstrate the minimax defense with two types of
attack classes -- gradient-based and neural network-based attacks. Experiments
with the MNIST and the CIFAR-10 datasets demonstrate that the defense found by
numerical minimax optimization is indeed more robust than non-minimax defenses.
We discuss directions for improving the result toward achieving robustness
against multiple types of attack classes.

negative:
Spectral learning recently generated lots of excitement in machine learning,
largely because it is the first known method to produce consistent estimates
(under suitable conditions) for several latent variable models. In contrast,
maximum likelihood estimates may get trapped in local optima due to the
non-convex nature of the likelihood function of latent variable models. In this
paper, we do an empirical evaluation of spectral learning (SL) and expectation
maximization (EM), which reveals an important gap between the theory and the
practice. First, SL often leads to negative probabilities. Second, EM often
yields better estimates than spectral learning and it does not seem to get
stuck in local optima. We discuss how the rank of the model parameters and the
amount of training data can yield negative probabilities. We also question the
common belief that maximum likelihood estimators are necessarily inconsistent.

negative:
We describe an alternative learning method for neural networks, which we call
Blind Descent. By design, Blind Descent does not face problems like exploding
or vanishing gradients. In Blind Descent, gradients are not used to guide the
learning process. In this paper, we present Blind Descent as a more fundamental
learning process compared to gradient descent. We also show that gradient
descent can be seen as a specific case of the Blind Descent algorithm. We also
train two neural network architectures, a multilayer perceptron and a
convolutional neural network, using the most general Blind Descent algorithm to
demonstrate a proof of concept.

negative:
Predicting and modeling human behavior and finding trends within human
decision-making processes is a major problem of social science. Rock Paper
Scissors (RPS) is the fundamental strategic question in many game theory
problems and real-world competitions. Finding the right approach to beat a
particular human opponent is challenging. Here we use an AI (artificial
intelligence) algorithm based on Markov Models of one fixed memory length
(abbreviated as "single AI") to compete against humans in an iterated RPS game.
We model and predict human competition behavior by combining many Markov Models
with different fixed memory lengths (abbreviated as "multi-AI"), and develop an
architecture of multi-AI with changeable parameters to adapt to different
competition strategies. We introduce a parameter called "focus length" (a
positive number such as 5 or 10) to control the speed and sensitivity for our
multi-AI to adapt to the opponent's strategy change. The focus length is the
number of previous rounds that the multi-AI should look at when determining
which Single-AI has the best performance and should choose to play for the next
game. We experimented with 52 different people, each playing 300 rounds
continuously against one specific multi-AI model, and demonstrated that our
strategy could win against more than 95% of human opponents.

negative:
Machine unlearning is the process through which a deployed machine learning
model is made to forget about some of its training data points. While naively
retraining the model from scratch is an option, it is almost always associated
with large computational overheads for deep learning models. Thus, several
approaches to approximately unlearn have been proposed along with corresponding
metrics that formalize what it means for a model to forget about a data point.
In this work, we first taxonomize approaches and metrics of approximate
unlearning. As a result, we identify verification error, i.e., the L2
difference between the weights of an approximately unlearned and a naively
retrained model, as an approximate unlearning metric that should be optimized
for as it subsumes a large class of other metrics. We theoretically analyze the
canonical training algorithm, stochastic gradient descent (SGD), to surface the
variables which are relevant to reducing the verification error of approximate
unlearning for SGD. From this analysis, we first derive an easy-to-compute
proxy for verification error (termed unlearning error). The analysis also
informs the design of a new training objective penalty that limits the overall
change in weights during SGD and as a result facilitates approximate unlearning
with lower verification error. We validate our theoretical work through an
empirical evaluation on learning with CIFAR-10, CIFAR-100, and IMDB sentiment
analysis.

negative:
Machine learning has now become an integral part of research and innovation.
The field of machine learning density functional theory has continuously
expanded over the years while making several noticeable advances. We briefly
discuss the status of this field and point out some current and future
challenges. We also talk about how state-of-the-art science and technology
tools can help overcome these challenges. This draft is a part of the "Roadmap
on Machine Learning in Electronic Structure" to be published in Electronic
Structure (EST).

negative:
In the last two years, more than 200 papers have been written on how machine
learning (ML) systems can fail because of adversarial attacks on the algorithms
and data; this number balloons if we were to incorporate papers covering
non-adversarial failure modes. The spate of papers has made it difficult for ML
practitioners, let alone engineers, lawyers, and policymakers, to keep up with
the attacks against and defenses of ML systems. However, as these systems
become more pervasive, the need to understand how they fail, whether by the
hand of an adversary or due to the inherent design of a system, will only
become more pressing. In order to equip software developers, security incident
responders, lawyers, and policy makers with a common vernacular to talk about
this problem, we developed a framework to classify failures into "Intentional
failures" where the failure is caused by an active adversary attempting to
subvert the system to attain her goals; and "Unintentional failures" where the
failure is because an ML system produces an inherently unsafe outcome. After
developing the initial version of the taxonomy last year, we worked with
security and ML teams across Microsoft, 23 external partners, standards
organization, and governments to understand how stakeholders would use our
framework. Throughout the paper, we attempt to highlight how machine learning
failure modes are meaningfully different from traditional software failures
from a technology and policy perspective.

negative:
Machine learning is often used in competitive scenarios: Participants learn
and fit static models, and those models compete in a shared platform. The
common assumption is that in order to win a competition one has to have the
best predictive model, i.e., the model with the smallest out-sample error. Is
that necessarily true? Does the best theoretical predictive model for a target
always yield the best reward in a competition? If not, can one take the best
model and purposefully change it into a theoretically inferior model which in
practice results in a higher competitive edge? How does that modification look
like? And finally, if all participants modify their prediction models towards
the best practical performance, who benefits the most? players with inferior
models, or those with theoretical superiority? The main theme of this paper is
to raise these important questions and propose a theoretical model to answer
them. We consider a study case where two linear predictive models compete over
a shared target. The model with the closest estimate gets the whole reward,
which is equal to the absolute value of the target. We characterize the reward
function of each model, and using a basic game theoretic approach, demonstrate
that the inferior competitor can significantly improve his performance by
choosing optimal model coefficients that are different from the best
theoretical prediction. This is a preliminary study that emphasizes the fact
that in many applications where predictive machine learning is at the service
of competition, much can be gained from practical (back-testing) optimization
of the model compared to static prediction improvement.

negative:
Success in the quest for artificial intelligence has the potential to bring
unprecedented benefits to humanity, and it is therefore worthwhile to
investigate how to maximize these benefits while avoiding potential pitfalls.
This article gives numerous examples (which should by no means be construed as
an exhaustive list) of such worthwhile research aimed at ensuring that AI
remains robust and beneficial.

negative:
In this paper, a new sequential surrogate-based optimization (SSBO) algorithm
is developed, which aims to improve the global search ability and local search
efficiency for the global optimization of expensive black-box models. The
proposed method involves three basic sub-criteria to infill new samples
asynchronously to balance the global exploration and local exploitation. First,
to capture the promising possible global optimal region, searching for the
global optimum with genetic algorithm (GA) based on the current surrogate
models of the objective and constraint functions. Second, to infill samples in
the region with sparse samples to improve the global accuracy of the surrogate
models, a grid searching with Latin hypercube sampling (LHS) with the current
surrogate model is adopted to explore the sample space. Third, to accelerate
the local searching efficiency, searching for a local optimum with sequential
quadratic programming (SQP) based on the local surrogate models in the reduced
interval, which involves some samples near the current optimum. When the new
sample is too close to the existing ones, the new sample should be abandoned,
due to the poor additional information. According to the three sub-criteria,
the new samples are placed in the regions which have not been fully explored
and includes the possible global optimum point. When a possible global optimum
point is found, the local searching sub-criterion captures the local optimum
around it rapidly. Numerical and engineering examples are used to verify the
efficiency of the proposed method. The statistical results show that the
proposed method has good global searching ability and efficiency.

negative:
We consider a formulation of a non zero-sum n players game by an n+1 players
zero-sum game. We suppose the existence of the n+1-th player in addition to n
players in the main game, and virtual subsidies to the n players which is
provided by the n+1-th player. Its strategic variable affects only the
subsidies, and does not affect choice of strategies by the n players in the
main game. His objective function is the opposite of the sum of the payoffs of
the n players. We will show 1) The minimax theorem by Sion (Sion(1958)) implies
the existence of Nash equilibrium in the n players non zero-sum game. 2) The
maximin strategy of each player in {1, 2, \dots, n} with the minimax strategy
of the n+1-th player is equivalent to the Nash equilibrium strategy of the n
players non zero-sum game. 3) The existence of Nash equilibrium in the n
players non zero-sum game implies Sion's minimax theorem for pairs of each of
the n players and the n+1-th player.

negative:
Our ability to know when to trust the decisions made by machine learning
systems has not kept up with the staggering improvements in their performance,
limiting their applicability in high-stakes domains. We introduce
Prover-Verifier Games (PVGs), a game-theoretic framework to encourage learning
agents to solve decision problems in a verifiable manner. The PVG consists of
two learners with competing objectives: a trusted verifier network tries to
choose the correct answer, and a more powerful but untrusted prover network
attempts to persuade the verifier of a particular answer, regardless of its
correctness. The goal is for a reliable justification protocol to emerge from
this game. We analyze variants of the framework, including simultaneous and
sequential games, and narrow the space down to a subset of games which provably
have the desired equilibria. We develop instantiations of the PVG for two
algorithmic tasks, and show that in practice, the verifier learns a robust
decision rule that is able to receive useful and reliable information from an
untrusted prover. Importantly, the protocol still works even when the verifier
is frozen and the prover's messages are directly optimized to convince the
verifier.

negative:
Prior work on training generative Visual Dialog models with reinforcement
learning(Das et al.) has explored a Qbot-Abot image-guessing game and shown
that this 'self-talk' approach can lead to improved performance at the
downstream dialog-conditioned image-guessing task. However, this improvement
saturates and starts degrading after a few rounds of interaction, and does not
lead to a better Visual Dialog model. We find that this is due in part to
repeated interactions between Qbot and Abot during self-talk, which are not
informative with respect to the image. To improve this, we devise a simple
auxiliary objective that incentivizes Qbot to ask diverse questions, thus
reducing repetitions and in turn enabling Abot to explore a larger state space
during RL ie. be exposed to more visual concepts to talk about, and varied
questions to answer. We evaluate our approach via a host of automatic metrics
and human studies, and demonstrate that it leads to better dialog, ie. dialog
that is more diverse (ie. less repetitive), consistent (ie. has fewer
conflicting exchanges), fluent (ie. more human-like),and detailed, while still
being comparably image-relevant as prior work and ablations.

negative:
Recent work in reinforcement learning demonstrated that learning solely
through self-play is not only possible, but could also result in novel
strategies that humans never would have thought of. However, optimization
methods cast as a game between two players require careful tuning to prevent
suboptimal results. Hence, we look at random play as an alternative method. In
this paper, we train a DQN agent to play Sungka, a two-player turn-based board
game wherein the players compete to obtain more stones than the other. We show
that even with purely random play, our training algorithm converges very fast
and is stable. Moreover, we test our trained agent against several baselines
and show its ability to consistently win against these.

negative:
In autonomous vehicle (AV) control, allowing mistakes can be quite dangerous
and costly in the real world. For this reason we investigate methods of
training an AV without allowing the agent to explore and instead having a human
explorer collect the data. Supervised learning has been explored for AV
control, but it encounters the issue of the covariate shift. That is, training
data collected from an optimal demonstration consists only of the states
induced by the optimal control policy, but at runtime, the trained agent may
encounter a vastly different state distribution with little relevant training
data. To mitigate this issue, we have our human explorer make sub-optimal
decisions. In order to have our agent not replicate these sub-optimal
decisions, supervised learning requires that we either erase these actions, or
replace these action with the correct action. Erasing is wasteful and replacing
is difficult, since it is not easy to know the correct action without driving.
We propose an alternate framework that includes continuous scalar feedback for
each action, marking which actions we should replicate, which we should avoid,
and how sure we are. Our framework learns continuous control from sub-optimal
demonstration and evaluative feedback collected before training. We find that a
human demonstrator can explore sub-optimal states in a safe manner, while still
getting enough gradation to benefit learning. The collection method for data
and feedback we call "Backseat Driver." We call the more general learning
framework ReNeg, since it learns a regression from states to actions given
negative as well as positive examples. We empirically validate several models
in the ReNeg framework, testing on lane-following with limited data. We find
that the best solution is a generalization of mean-squared error and
outperforms supervised learning on the positive examples alone.

negative:
Resampling is a key component of sample-based recursive state estimation in
particle filters. Recent work explores differentiable particle filters for
end-to-end learning. However, resampling remains a challenge in these works, as
it is inherently non-differentiable. We address this challenge by replacing
traditional resampling with a learned neural network resampler. We present a
novel network architecture, the particle transformer, and train it for particle
resampling using a likelihood-based loss function over sets of particles.
Incorporated into a differentiable particle filter, our model can be end-to-end
optimized jointly with the other particle filter components via gradient
descent. Our results show that our learned resampler outperforms traditional
resampling techniques on synthetic data and in a simulated robot localization
task.

negative:
This paper presents an acoustic echo canceler based on a U-Net convolutional
neural network for single-talk and double-talk scenarios. U-Net networks have
previously been used in the audio processing area for source separation
problems because of their ability to reproduce the finest details of audio
signals, but to our knowledge, this is the first time they have been used for
acoustic echo cancellation (AEC). The U-Net hyperparameters have been optimized
to obtain the best AEC performance, but using a reduced number of parameters to
meet a latency restriction of 40 ms. The training and testing of our model have
been carried out within the framework of the 'ICASSP 2021 AEC Challenge'
organized by Microsoft. We have trained the optimized U-Net model with a
synthetic dataset only (S-U-Net) and with a synthetic dataset and the
single-talk set of a real dataset (SR-U-Net), both datasets were released for
the challenge. The S-U-Net model presented better results for double-talk
scenarios, thus their inferred near-end signals from the blind testset were
submitted to the challenge. Our canceler ranked 12th among 17 teams, and 5th
among 10 academia teams, obtaining an overall mean opinion score of 3.57.

negative:
An approach for game bot detection in MMORPGs is proposed based on the
analysis of game playing behavior. Since MMORPGs are large scale games, users
can play in various ways. This variety in playing behavior makes it hard to
detect game bots based on play behaviors. In order to cope with this problem,
the proposed approach observes game playing behaviors of users and groups them
by their behavioral similarities. Then, it develops a local bot detection model
for each player group. Since the locally optimized models can more accurately
detect game bots within each player group, the combination of those models
brings about overall improvement. For a practical purpose of reducing the
workloads of the game servers in service, the game data is collected at a low
resolution in time. Behavioral features are selected and developed to
accurately detect game bots with the low resolution data, considering common
aspects of MMORPG playing. Through the experiment with the real data from a
game currently in service, it is shown that the proposed local model approach
yields more accurate results.

negative:
Scientific experiments are usually expensive due to complex experimental
preparation and processing. Experimental design is therefore involved with the
task of finding the optimal experimental input that results in the desirable
output by using as few experiments as possible. Experimenters can often acquire
the knowledge about the location of the global optimum. However, they do not
know how to exploit this knowledge to accelerate experimental design. In this
paper, we adopt the technique of Bayesian optimization for experimental design
since Bayesian optimization has established itself as an efficient tool for
optimizing expensive black-box functions. Again, it is unknown how to
incorporate the expert prior knowledge about the global optimum into Bayesian
optimization process. To address it, we represent the expert knowledge about
the global optimum via placing a prior distribution on it and we then derive
its posterior distribution. An efficient Bayesian optimization approach has
been proposed via posterior sampling on the posterior distribution of the
global optimum. We theoretically analyze the convergence of the proposed
algorithm and discuss the robustness of incorporating expert prior. We evaluate
the efficiency of our algorithm by optimizing synthetic functions and tuning
hyperparameters of classifiers along with a real-world experiment on the
synthesis of short polymer fiber. The results clearly demonstrate the
advantages of our proposed method.

negative:
Multi-agent reinforcement learning offers a way to study how communication
could emerge in communities of agents needing to solve specific problems. In
this paper, we study the emergence of communication in the negotiation
environment, a semi-cooperative model of agent interaction. We introduce two
communication protocols -- one grounded in the semantics of the game, and one
which is \textit{a priori} ungrounded and is a form of cheap talk. We show that
self-interested agents can use the pre-grounded communication channel to
negotiate fairly, but are unable to effectively use the ungrounded channel.
However, prosocial agents do learn to use cheap talk to find an optimal
negotiating strategy, suggesting that cooperation is necessary for language to
emerge. We also study communication behaviour in a setting where one agent
interacts with agents in a community with different levels of prosociality and
show how agent identifiability can aid negotiation.

negative:
When a channel model is not available, the end-to-end training of encoder and
decoder on a fading noisy channel generally requires the repeated use of the
channel and of a feedback link. An important limitation of the approach is that
training should be generally carried out from scratch for each new channel. To
cope with this problem, prior works considered joint training over multiple
channels with the aim of finding a single pair of encoder and decoder that
works well on a class of channels. In this paper, we propose to obviate the
limitations of joint training via meta-learning. The proposed approach is based
on a meta-training phase in which the online gradient-based meta-learning of
the decoder is coupled with the joint training of the encoder via the
transmission of pilots and the use of a feedback link. Accounting for channel
variations during the meta-training phase, this work demonstrates the
advantages of meta-learning in terms of number of pilots as compared to
conventional methods when the feedback link is only available for meta-training
and not at run time.

negative:
The game of baccarat has evolved from a parlor game played by French
aristocrats in the first half of the 19th century to a casino game that
generated over US\$41 billion in revenue for the casinos of Macau in 2013. The
parlor game was originally a three-person zero-sum game. Later in the 19th
century it was simplified to a two-person zero-sum game. Early in the 20th
century the parlor game became a casino game, no longer zero-sum. In the mid
20th century, the strategic casino game became a nonstrategic game, with
players competing against the house instead of against each other. We argue
that this evolution was motivated by both economic and game-theoretic
considerations.

negative:
The primary objective is to teach a machine about human emotions, which has
become an essential requirement in the field of social intelligence, also
expedites the progress of human-machine interactions. The ability of a machine
to understand human emotion and act accordingly has been a choice of great
interest in today's world. The future generations of computers thus must be
able to interact with a human being just like another. For example, people who
have Autism often find it difficult to talk to someone about their state of
mind. This model explicitly targets the userbase who are troubled and fail to
express it. Also, this model's speech processing techniques provide an estimate
of the emotion in the case of poor video quality and vice-versa.

negative:
Recently we see a rising number of methods in the field of eXplainable
Artificial Intelligence. To our surprise, their development is driven by model
developers rather than a study of needs for human end users. The analysis of
needs, if done, takes the form of an A/B test rather than a study of open
questions. To answer the question "What would a human operator like to ask the
ML model?" we propose a conversational system explaining decisions of the
predictive model. In this experiment, we developed a chatbot called dr_ant to
talk about machine learning model trained to predict survival odds on Titanic.
People can talk with dr_ant about different aspects of the model to understand
the rationale behind its predictions. Having collected a corpus of 1000+
dialogues, we analyse the most common types of questions that users would like
to ask. To our knowledge, it is the first study which uses a conversational
system to collect the needs of human operators from the interactive and
iterative dialogue explorations of a predictive model.

negative:
With the growing technology of photon-counting detectors (PCD), spectral CT
is a widely concerned topic which has the potential of material
differentiation. However, due to some non-ideal factors such as cross talk and
pulse pile-up of the detectors, direct reconstruction from detected spectrum
without any corrections will get a wrong result. Conventional methods try to
model these factors using calibration and make corrections accordingly, but
depend on the preciseness of the model. To solve this problem, in this paper,
we proposed a novel deep learning-based monochromatic image synthesis method
working in sinogram domain. Different from previous deep learning-based methods
aimed at this problem, we designed a novel network architecture according to
the physical model of cross talk, and it can solve this problem better in an
ingenious way. Our method was tested on a cone-beam CT (CBCT) system equipped
with a PCD. After using FDK algorithm on the corrected projection, we got quite
more accurate results with less noise, which showed the feasibility of
monochromatic image synthesis by our method.