United States

This paper studies the complexity for finding approximate stationary points of nonconvex-strongly-concave (NC-SC) smooth minimax problems, in both general and averaged smooth finite-sum settings. We establish nontrivial lower complexity bounds of $\Omega(\sqrt{\kappa}\Delta L\epsilon^{-2})$ and $\Omega(n+\sqrt{n\kappa}\Delta L\epsilon^{-2})$ for the two settings, respectively, where $\kappa$ is the condition number, $L$ is the smoothness constant, and $\Delta$ is the initial gap. Our result reveals substantial gaps between these limits and best-known upper bounds in the literature. To close these gaps, we introduce a generic acceleration scheme that deploys existing gradient-based methods to solve a sequence of crafted strongly-convex-strongly-concave subproblems. In the general setting, the complexity of our proposed algorithm nearly matches the lower bound; in particular, it removes an additional poly-logarithmic dependence on accuracy present in previous works. In the averaged smooth finite-sum setting, our proposed algorithm improves over previous algorithms by providing a nearly-tight dependence on the condition number.

UAI 2021

The Complexity of Nonconvex-Strongly-Concave Minimax Optimization

saddle point problem

lower complexity bound

minimax optimization

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-23 is the Thirty-Seventh AAAI Conference on Artificial Intelligence. The theme of this conference is to create collaborative bridges within and beyond AI. Like previous AAAI conferences, AAAI-23 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and two new activities: a Bridge Program and a Lab Program. Many of these activities are tailored to the theme of bridges and all are selected according to the highest standards, with additional programs for students and young researchers. 
AAAI is providing you with a conference planner, which you can use to help organize your itinerary of activities. This includes talks to attend in person, talks to attend remotely, breaks with colleagues and your site seeing activities. To access this conference planner, please go to [https://aaai-2023.takemobi.io](https://aaai-2023.takemobi.io).

In order to access this site, you need to register. If you haven't already, please register [here](https://aaai.org/Conferences/AAAI-23/registration/).


AAAI 2023

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines.

lightning talk

The Conference on Uncertainty in Artificial Intelligence (UAI) is one of the premier international conferences on research related to knowledge representation, learning, and reasoning in the presence of uncertainty. It is supported by the [Association for Uncertainty in Artificial Intelligence (AUAI).](https://www.auai.org/)

The 37th Conference on Uncertainty in Artificial Intelligence (UAI 2021) is held fully online. We have an exciting program consisting of keynote talks by [Susan Murphy](https://www.auai.org/uai2021/program?block=A), [Eric Horvitz](https://www.auai.org/uai2021/program?block=B), [Lenka Zdeborová](https://www.auai.org/uai2021/program?block=C), [Judea Pearl](https://www.auai.org/uai2021/program?block=D) and [Ankur Moitra](https://www.auai.org/uai2021/program?block=E), a town hall meeting, peer-reviewed papers, and three workshops. The main conference is single-track and each paper is show-cased with a live component (either a live discussion and Q&A, or a live lightning talk). All papers are also featured in video presentations and in poster sessions in gather.town. The three parallel workshops on Friday allow for smaller meetings on current topics.

The walkthrough video below shows how you can navigate this site and use the different possibilities for interaction: UAIsland2021 on gather.town for posters and social interactions, the mementor platform for virtual mentoring sessions, and the chat and Q&A systems for discussions about talks and posters.

Have a great UAI 2021! 
 
 Cassio de Campos and Marloes Maathuis
 UAI 2021 Program Chairs
 uai2021programchairs@gmail.com

<figure class="video_container">
 <iframe src="https://screencast-o-matic.com/watch/cri0lsViAGK?v=6&ff=1&title=0&controls=1" width=526 height=226 frameborder="0" allowfullscreen="true"> </iframe>
</figure>

A ticket is required to access this conference. Please use the provided link to register for the event.

https://auai.org/uai2021/registration

The Conference on Uncertainty in Artificial Intelligence (UAI) is one of the premier international conferences on research related to knowledge representation, learning, and reasoning in the presence of uncertainty. It is supported by the [Association for Uncertainty in Artificial Intelligence (AUAI).](https://www.auai.org/)

The development of Variational Inference (VI) and Bayesian Deep Neural Networks has increasingly led to the uncertainty estimation in deep models, critical to many real-world applications. Recent evidence suggests that existing solutions dependent on simple Gaussian formulations may not be sufficient. However, moving to other distributions necessitates Monte Carlo (MC) sampling to estimate statistical values such as the KL divergence: ultimately expensive and scaling poorly as the dimensions of both the input data and the model grow. This is directly related to the structure of the computation graph, which can grow linearly as a function of the number of MC samples needed. Here, we construct a framework to describe these computation graphs, and identify probability families where the graph size can be independent or only weakly dependent on the number of MC samples. These nice probability families correspond directly to large classes of distributions common in practice. Empirically, we find that we can run a much larger number of iterations for MC approximations for larger architectures widely used in vision with gains in performance measured in confident accuracy, stability of training, memory and training time.

Graph Reparametrizations for Enabling 1000+ Monte Carlo Iterations In Bayesian Deep Neural Networks

Most recent few-shot learning (FSL) methods are based on meta-learning with episodic training. In each meta-training episode, a discriminative feature embedding and/or classifier are first constructed from a support set in an inner loop, and then evaluated in an outer loop using a query set for model updating. This query set sample centered learning objective is however intrinsically limited in addressing the lack of training data problem in the support set. In this paper, a novel contrastive prototype learning with augmented embeddings (CPLAE) model is proposed to overcome this limitation. First, data augmentations are introduced to both the support and query sets with each sample now being represented as an augmented embedding (AE) composed of concatenated embeddings of both the original and augmented versions. Second, a novel support set class prototype centered contrastive loss is proposed for contrastive prototype learning (CPL). With a class prototype as an anchor, CPL aims to pull the query samples of the same class closer and those of different classes further away. This support set sample centered loss is highly complementary to the existing query centered loss, fully exploiting the limited training data in each episode. Extensive experiments on several benchmarks demonstrate that our proposed CPLAE achieves new state-of-the-art.

Contrastive Prototype Learning with Augmented Embeddings for Few-Shot Learning

Generating succinct summaries or \textit{sketches} of massive data streams is becoming increasingly important. Such a task typically requires fast, accurate, and small space algorithms in order to support the downstream applications, mainly in areas such as data analysis, machine learning, and data mining. A fundamental and well-studied problem in this context is that of estimating the frequencies of the items appearing in a data stream. The Count-Min-Sketch~\cite{CMS} and Count-Sketch~\cite{count_sketch} are two known classical algorithms for this purpose. However, a limitation of these techniques is that the variance of their estimate tends to be large. In this work, we address this problem and suggest a technique that reduces the variance in their respective estimates, at the cost of little computational overhead. Our technique relies on the classical Control-Variate trick~\cite{Lavenberg} used for reducing variance in Monte-Carlo simulation. We present a theoretical analysis of our proposal by carefully choosing the control variates and complement them with experiments on synthetic as well as real-world datasets.

Variance Reduction in Frequency Estimators via Control Variates Method

On playing video games, different players usually have their own playstyles.

An Unsupervised Video Game Playstyle Metric via State Discretization

Multi-source domain adaptation (DA) is more challenging than conventional DA because the knowledge is transferred from several source domains to a target domain. To this end, we propose in this paper a novel model for multi-source DA using the theory of optimal transport and imitation learning. More specifically, our approach consists of two cooperative agents: a teacher classifier and a student classifier. The teacher classifier is a combined expert that leverages knowledge of domain experts that can be theoretically guaranteed to handle perfectly source examples, while the student classifier acting on the target domain tries to imitate the teacher classifier acting on the source domains. Our rigorous theory developed based on optimal transport makes this cross-domain imitation possible and also helps to mitigate not only the data shift but also the label shift, which are inherently thorny issues in DA research. We conduct comprehensive experiments on real-world datasets to demonstrate the merit of our approach and its optimal transport based imitation learning viewpoint. Experimental results show that our proposed method achieves state-of-the-art performance on benchmark datasets for multi-source domain adaptation including Digits-five, Office-Caltech10, and Office-31 to the best of our knowledge.

Multi-Source Domain Adaptation via Optimal Transport for Student-Teacher Learning

Adversarial machine learning has attracted a great amount of attention in recent years.

Defending SVMs Against Poisoning Attacks: The Hardness and DBSCAN Approach

We present a novel blind source separation (BSS) method, called information geometric blind source separation (IGBSS). Our formulation is based on the log-linear model equipped with a hierarchically structured sample space, which has theoretical guarantees to uniquely recover a set of source signals by minimizing the KL divergence from a set of mixed signals. Source signals, received signals, and mixing matrices are realized as different layers in our hierarchical sample space. Our empirical results have demonstrated on images and time series data that our approach is superior to well established techniques and is able to separate signals with complex interactions.

Hierarchical Probabilistic Model for Blind Source Separation via Legendre Transformation

Leveraging the framework of Optimal Transport, we introduce a new family of generative autoencoders with a learnable prior, called Symmetric Wasserstein Autoencoders (SWAEs). We propose to symmetrically match the joint distributions of the observed data and the latent representation induced by the encoder and the decoder. The resulting algorithm jointly optimizes the modelling losses in both the data and the latent spaces with the loss in the data space leading to the denoising effect. With the symmetric treatment of the data and the latent representation, the algorithm implicitly preserves the local structure of the data in the latent space.

Symmetric Wasserstein Autoencoders

Adaptive gradient methods have achieved remarkable success in training deep neural networks on a wide variety of tasks. However, not much is known about the mathematical and statistical properties of this family of methods. This work aims at providing a series of theoretical analyses of its statistical properties justified by experiments. In particular, we show that when the underlying gradient obeys a normal distribution, the variance of the magnitude of the \textit{update} is an increasing and bounded function of time and does not diverge. This work suggests that the divergence of variance is not the cause of the need for warm-up of the Adam optimizer, contrary to what is believed in the current literature.

On the Distributional Properties of Adaptive Gradients

Recent advances in convolutional neural networks (CNNs) usually come with the expense of excessive computational overhead and memory footprint. Network compression aims to alleviate this issue by training compact models with comparable performance. However, existing compression techniques either entail dedicated expert design or compromise with a moderate performance drop. In this paper, we propose a novel structured sparsification method for efficient network compression. The proposed method automatically induces structured sparsity on the convolutional weights, thereby facilitating the implementation of the compressed model with the highly-optimized group convolution. We further address the problem of inter-group communication with a learnable channel shuffle mechanism. The proposed approach can be easily applied to compress many network architectures with a negligible performance drop. Extensive experimental results and analysis demonstrate that our approach gives a competitive performance against the recent network compression counterparts with a sound accuracy-complexity trade-off.

The Complexity of Nonconvex-Strongly-Concave Minimax Optimization

Downloads

Next from UAI 2021

Graph Reparametrizations for Enabling 1000+ Monte Carlo Iterations In Bayesian Deep Neural Networks

Similar lecture

Decentralized Riemannian Algorithm for Nonconvex Minimax Problems

The Complexity of Nonconvex-Strongly-Concave Minimax Optimization

.css-70qvj9{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;}Downloads

Next from UAI 2021

Graph Reparametrizations for Enabling 1000+ Monte Carlo Iterations In Bayesian Deep Neural Networks

Similar lecture

Decentralized Riemannian Algorithm for Nonconvex Minimax Problems

Downloads