United States

This paper studies a function fitting problem which we coin  first-order convex fitting (FCF): given any two vector sequences x1, ..., xT and p1, ..., pT, when is it possible to  efficiently construct  a convex function f(x) that ``fits&#39;&#39; the two sequences in the first-order sense, i.e,   the (sub)gradient of f(xi) equals precisely pi, for all i = 1, ..., T? Despite a  basic question of convex analysis,  FCF has surprisingly been overlooked in the past literature. With an efficient constructive proof, we provide a clean answer to this question:  FCF   is possible  if and only if the two sequences are permutation stable: p1 * x1 + ... + pT * xT is greater than or equal to p1 * x&#39;1 + ... + pT * x&#39;T where x&#39;1, ..., x&#39;T is any permutation of x1, ..., xT.
 
We  demonstrate the usefulness of FCF in  two  applications. First, we study how it can be used as an empirical risk minimization procedure to learn the original convex function. We provide  efficient PAC-learnability bounds for special classes of convex functions  learned via FCF, and demonstrate its application to multiple economic problems where only function gradients (as opposed to function values)  can be observed. Second,  we empirically show how it can be used as a surrogate to significantly accelerate the minimization of the original convex function.

AAAI 2022

First-Order Convex Fitting and Its Application to Economics and Optimization

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! 
<br>
<br>Cassio de Campos and Marloes Maathuis
<br>UAI 2021 Program Chairs
<br>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

UAI 2021

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/)

This paper studies a function fitting problem which we coin  first-order convex fitting (FCF): given any two vector sequences x1, ..., xT and p1, ..., pT, when is it possible to  efficiently construct  a convex function f(x) that ``fits'' the two sequences in the first-order sense, i.e,   the (sub)gradient of f(xi) equals precisely pi, for all i = 1, ..., T? Despite a  basic question of convex analysis,  FCF has surprisingly been overlooked in the past literature. With an efficient constructive proof, we provide a clean answer to this question:  FCF   is possible  if and only if the two sequences are permutation stable: p1 * x1 + ... + pT * xT is greater than or equal to p1 * x'1 + ... + pT * x'T where x'1, ..., x'T is any permutation of x1, ..., xT.
 
We  demonstrate the usefulness of FCF in  two  applications. First, we study how it can be used as an empirical risk minimization procedure to learn the original convex function. We provide  efficient PAC-learnability bounds for special classes of convex functions  learned via FCF, and demonstrate its application to multiple economic problems where only function gradients (as opposed to function values)  can be observed. Second,  we empirically show how it can be used as a surrogate to significantly accelerate the minimization of the original convex function.

technical paper

The purpose of the AAAI conference is to promote research in artificial intelligence (AI) and scientific exchange among AI researchers, practitioners, scientists, and engineers in affiliated disciplines. 

Strategy synthesis for multi-agent systems has proved to be a hard task, even when limited to two-player games with safety objectives. Generalized strategy synthesis, an extension of generalized planning which aims to produce a single solution for multiple (possibly infinitely many) planning instances, is a promising direction to deal with the state-space explosion problem. In this paper, we formalize the problem of generalized strategy synthesis in the situation calculus. The synthesis task involves second-order theorem proving generally. Thus we consider strategies aiming to maintain invariants; such strategies can be verified with first-order theorem proving. We propose a sound but incomplete approach to synthesize invariant strategies by adapting the framework of counterexample-guided refinement. The key idea for refinement is to generate a strategy using a model checker for a game constructed from the counterexample, and use it to refine the candidate general strategy. We implemented our method and did experiments with a number of game problems. Our system can successfully synthesize solutions for most of the domains within a reasonable amount of time.

Automated Synthesis of Generalized Invariant Strategies via Counterexample-Guided Strategy Refinement

Rotating savings and credit associations (roscas) are informal financial organizations common in settings where communities have reduced access to formal financial institutions. In a rosca, a fixed group of participants regularly contribute sums of money to a pot. This pot is then allocated periodically using lottery, aftermarket, or auction mechanisms. Roscas are empirically well-studied in economics. They are, however, challenging to study theoretically due to their dynamic nature. Typical economic analyses of roscas stop at coarse ordinal welfare comparisons to other credit allocation mechanisms, leaving much of roscas' ubiquity unexplained. In this work, we take an algorithmic perspective on the study of roscas. Building on techniques from the price of anarchy literature, we present worst-case welfare approximation guarantees. We further experimentally compare the welfare of outcomes as key features of the environment vary. These cardinal welfare analyses further rationalize the prevalence of roscas. We conclude by discussing several other promising avenues.

An Algorithmic Introduction to Savings Circles

Transformers achieve state-of-the-art performance for natural language processing tasks by pre-training on large-scale text corpora. They are extremely compute-intensive and have very high sample complexity. Memory replay is a mechanism that remembers and reuses past examples by saving to and replaying from a memory buffer. It has been successfully used in reinforcement learning and GANs due to better sample efficiency. In this paper, we propose Transformer with Memory Replay, which integrates memory replay with transformer, making transformer more sample efficient. Experiments on GLUE and SQuAD benchmark datasets showed that Transformer with Memory Replay can achieve at least 1% point increase compared to the baseline transformer model when pre-trained with the same number of examples. Further, by adopting a careful design that reduces the wall-clock time overhead of memory replay, we also empirically achieve a better runtime efficiency.

Transformer with Memory Replay

Question answering over semi-structured tables has attracted significant attention in the NLP community.
 However, most of the existing work focus on questions that can be answered with short-form answer, i.e. the answer is often a table cell or aggregation of multiple cells. 
 This can mismatch with the intents of users who want to ask more complex questions that require free-form answers such as explanations. 
 To bridge the gap, most recently, pre-trained sequence-to-sequence language models such as T5 are used for generating free-form answers based on the question and table inputs. 
 However, these pre-trained language models have weaker encoding abilities over table cells and schema. 
 To mitigate this issue, in this work, we present an intermediate pre-training framework, Generation-focused Table-based Intermediate Pre-training (GENTAP), that jointly learns representations of natural language questions and tables.
 GENTAP learns to generate via two training objectives to enhance the question understanding and table representation abilities for complex questions. 
 Based on experimental results, models that leverage GENTAP framework outperform the existing baselines on FETAQA benchmark. 
 The pre-trained models are not only useful for free-form question answering, but also for few-shot data-to-text generation task, thus showing good transfer ability by obtaining new state-of-the-art results.

Generation-Focused Table-Based Intermediate Pre-Training for Free-Form Question Answering

Adversarial attacks on graphs have attracted considerable research interests. Existing works assume the attacker is either (partly) aware of the victim model, or able to send queries to it. These assumptions are, however, unrealistic. To bridge the gap between theoretical graph attacks and real-world scenarios, in this work, we propose a novel and more realistic setting: strict black-box graph attack, in which the attacker has no knowledge about the victim model at all and is not allowed to send any queries. To design such an attack strategy, we first propose a generic graph filter to unify different families of graph-based models. The strength of attacks can then be quantified by the change in the graph filter before and after attack. By maximizing this change, we are able to find an effective attack strategy, regardless of the underlying model. To solve this optimization problem, we also propose a relaxation technique and approximation theories to reduce the difficulty as well as the computational expense. Experiments demonstrate that, even with no exposure to the model, the Macro-F1 drops 6.4% in node classification and 29.5% in graph classification, which is a significant result compared with existent works.

Blindfolded Attackers Still Threatening: Strict Black-Box Adversarial Attacks on Graphs

Tensor optimization is crucial to massive machine learning and signal processing tasks. In this paper, we consider tensor optimization with a convex and well-conditioned objective function and reformulate it into a nonconvex optimization using the Burer-Monteiro type parameterization. We analyze the local convergence of applying vanilla gradient descent to the factored formulation and establish a local regularity condition under mild assumptions. We also provide a linear convergence analysis of the gradient descent algorithm started in a neighborhood of the true tensor factors.  Complementary to the local analysis, this work also characterizes the global geometry of the best rank-one tensor approximation problem and demonstrates that for orthogonally decomposable tensors the problem has no spurious local minima and all saddle points are strict except for the one at zero which is a third-order saddle point.

Local and Global Convergence of General Burer-Monteiro Tensor Optimizations

Density estimation is a widely used method to perform unsupervised anomaly detection. By learning the density function, data points with relatively low densities are classified as anomalies. Unfortunately, the presence of anomalies in training data may significantly impact the density estimation process, thereby imposing significant challenges to the use of more sophisticated density estimation methods such as those based on deep neural networks. In this work, we propose RobustRealNVP, a deep density estimation framework that enhances the robustness of flow-based density estimation methods, enabling their application to unsupervised anomaly detection. 
 RobustRealNVP differs from existing flow-based models from two perspectives. First, RobustRealNVP discards data points with low estimated densities during optimization to prevent them from corrupting the density estimation process. Furthermore, it imposes Lipschitz regularization to the flow-based model to enforce smoothness in the estimated density function. We demonstrate the robustness of our algorithm against anomalies in training data from both theoretical and empirical perspectives. The results show that our algorithm achieves competitive results as compared to state-of-the-art unsupervised anomaly detection methods.

Unsupervised Anomaly Detection by Robust Density Estimation

We study the second-price auction in which bidders have asymmetric information regarding the item's value. Each bidder's value for the item depends on a private component and a public component. While each bidder observes their own private component, they hold different and asymmetric information about the public component. We characterize the equilibrium of this auction game and study how the asymmetric bidder information affects their equilibrium bidding strategies. We also discover multiple surprisingly counter-intuitive equilibrium phenomena. For instance, a bidder may be better off if she is less informed regarding the public component. Conversely, a bidder may sometimes be worse off if she obtains more accurate estimation about the auctioned item. Our results suggest that efforts devoted by bidders to improve their value estimations, as widely seen in today's online advertising auctions, may not always be to their benefit.

The Strange Role of Information Asymmetry in Auctions --- Does More Accurate Value Estimation Benefit A Bidder?

Strategic classification, i.e. classification under possible strategic manipulations of features, has received a lot of attention from both the machine learning and the game theory community. Most works focus on analysing properties of the optimal decision rule under such manipulations. In our work we take a learning theoretic perspective, focusing on the sample complexity needed to learn a good decision rule which is robust to strategic manipulation. We perform this analysis by introducing a novel loss function, the strategic manipulation loss, which takes into account both the accuracy of the final decision rule and its vulnerability to manipulation. We analyse the sample complexity for a known graph of possible manipulations in terms of the complexity of the function class and the manipulation graph. Additionally, we initialize the study of learning under unknown manipulation capabilities of the involved agents. Using techniques from transfer learning theory, we define a similarity measure for manipulation graphs and show that learning outcomes are robust with respect to small changes in the manipulation graph. Lastly, we analyse the (sample complexity of) learning of the manipulation capability of agents with respect to this similarity measure, providing novel guarantees for strategic classification with respect to an unknown manipulation graph.

Learning Losses for Strategic Classification

The core of self-supervised learning for pre-training language models includes pre-training task design as well as appropriate data augmentation. Most data augmentations in language model pre-training are context-independent. A seminal contextualized augmentation was recently proposed in ELECTRA and achieved state-of-the-art performance by introducing an auxiliary generation network (generator) to produce contextualized data augmentation for the training of a main discrimination network (discriminator). This design, however, introduces extra computation cost of the generator and a need to adjust the relative capability between the generator and the discriminator. In this paper, we propose a self-augmentation strategy (SAS) where a single network is utilized for both regular pre-training and contextualized data augmentation for the training in later epochs. Essentially, this strategy eliminates a separate generator and uses the single network to jointly conduct two pre-training tasks with MLM (Masked Language Modeling) and RTD (Replaced Token Detection) heads. It avoids the challenge to search for an appropriate size of the generator, which is critical to the performance as evidenced in ELECTRA and its subsequent variant models. In addition, SAS is a general strategy that can be seamlessly combined with many new techniques emerging recently or in the future, such as the disentangled attention mechanism from DeBERTa. Our experiments show that SAS is able to outperform ELECTRA and other state-of-the-art models in the GLUE tasks with similar or less computation cost.

Downloads

Next from AAAI 2022

Automated Synthesis of Generalized Invariant Strategies via Counterexample-Guided Strategy Refinement

Similar lecture

Dynamic visualization for L1 fusion convex clustering in near-linear time

.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 AAAI 2022

Automated Synthesis of Generalized Invariant Strategies via Counterexample-Guided Strategy Refinement

Similar lecture

Dynamic visualization for L1 fusion convex clustering in near-linear time

Downloads