United States

We provide new adaptive first-order methods for constrained convex optimization. Our main algorithms AdaACSA and AdaAGD+ are accelerated methods, which are universal in the sense that they achieve nearly-optimal convergence rates for both smooth and non-smooth functions, even when they only have access to stochastic gradients. In addition, they do not require any prior knowledge on how the objective function is parametrized, since they automatically adjust their per-coordinate learning rate. These can be seen as truly accelerated Adagrad methods for constrained optimization. We complement them with a simpler algorithm AdaGrad+ which enjoys the same features, and achieves the standard non-accelerated convergence rate. We also present a set of new results involving adaptive methods for unconstrained optimization and variational inequalities arising from monotone operators.

AAAI 2021

Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalities

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. 

AAAI 2022

technical paper

Decision trees of low depth are beneficial for understanding and interpreting the data they represent. 
Unfortunately, finding a decision tree of lowest depth that correctly represents given data is NP-hard. 
Hence known algorithms either (i) utilize heuristics that do not optimize the depth or (ii) are exact but scale only to small or medium-sized instances. 
We propose a new hybrid approach to decision tree learning, combining heuristic and exact methods in a novel way. 
More specifically, we employ SAT encodings repeatedly to local parts of a decision tree provided by a standard heuristic, leading to a global depth improvement. 
This allows us to scale the power of exact SAT-based methods to almost arbitrarily large data sets. 
We evaluate our new approach experimentally on a range of real-world instances that contain up to several thousand samples. 
In almost all cases, our method successfully decreases the depth of the initial decision tree; often, the decrease is significant.

SAT-Based Decision Tree Learning for Large Data Sets

As an interesting and challenging task, story ending generation aims at generating a reasonable and coherent ending for a given story context. The key challenge of the task is to comprehend the context sufficiently and capture the hidden logic information effectively, which has not been well explored by most existing generative models. To tackle this issue, we propose a context-aware Multi-level Graph Convolutional Networks over Dependency Parse (MGCN-DP) trees to capture dependency relations and context clues more effectively. We utilize dependency parse trees to facilitate capturing relations and events in the context implicitly, and Multi-level Graph Convolutional Networks to update and deliver the representation crossing levels to obtain richer contextual information. Both automatic and manual evaluations show that our MGCN-DP can achieve comparable performance with state-of-the-art models. Our source code is available at https://github.com/VISLANG-Lab/MLGCN-DP.

Story Ending Generation with Multi-Level Graph Convolutional Networks over Dependency Trees

While the stock movement prediction has been intensively studied, existing work suffers from weak generalization because of the uncertainty in both data and modeling. On one hand, training a stock representation on stochastic stock data in an end-to-end manner may lead to excessive modeling, which involves model uncertainty. On the other, the analysis of correlating stock data with its relevant factors involves data uncertainty. To simultaneously address such uncertainty both from data and modeling perspectives, a fundamental yet challenging task is to learn a better stock representation with less uncertainty by considering hierarchical couplings from the macro-level to the sector-and micro-level. Accordingly, we propose a copula-based contrastive predictive coding (Co-CPC) method. Co-CPC first models the dependence between a certain stock sector and relevant macroeconomic variables that are sequential and heterogeneous, e.g., macro-variables are associated with different time intervals, scales, and distributions.  Then, by involving a macro-sector context, stock representations are learned in a self-supervised way that can further be used for downstream tasks like stock movement prediction. Extensive experiments on two typical stock datasets verify the effectiveness of our Co-CPC method.

Coupling Macro-Sector-Micro Financial Indicators for Learning Stock Representations with Less Uncertainty

Because learning sometimes involves sensitive data, machine learning algorithms have been extended to offer differential privacy for training data. In practice, this has been mostly an afterthought, with privacy-preserving models obtained by re-running training with a different optimizer, but using the model architectures that already performed well in a non-privacy-preserving setting. This approach leads to less than ideal privacy/utility tradeoffs, as we show here. To improve these tradeoffs, prior work introduces variants of differential privacy that weaken the privacy guarantee proved to increase model utility. We show this is not necessary and instead propose that utility be improved by choosing activation functions designed explicitly for privacy-preserving training. 

A crucial operation in differentially private SGD is gradient clipping, which along with modifying the optimization path (at times resulting in not-optimizing a single objective function), may also introduce both significant bias and variance to the learning process. We empirically identify exploding gradients arising from ReLU may be one of the main sources of this. We demonstrate analytically and experimentally how a general family of bounded activation functions, the tempered sigmoids, consistently outperform the currently established choice: unbounded activation functions like ReLU. Using this paradigm, we achieve new state-of-the-art accuracy on MNIST, FashionMNIST, and CIFAR10 without any modification of the learning procedure fundamentals or differential privacy analysis. While the changes we make are simple in retrospect, the simplicity of our approach facilitates its implementation and adoption to meaningfully improve state-of-the-art machine learning while still providing strong guarantees in the original framework of differential privacy.

Tempered Sigmoid Activations for Deep Learning with Differential Privacy

Reservoir classification is an essential step for the exploration and production process in the oil and gas industry. An appropriate automatic reservoir classification will not only reduce the manual workloads of experts, but also help petroleum companies to make optimal decisions efficiently, which in turn will dramatically reduce the costs. Existing methods mainly focused on generating reservoir classification in a single geological block but failed to work well on a new oilfield block. Indeed, how to transfer the subsurface characteristics and make accurate reservoir classification across the geological oilfields is a very important but challenging problem. To that end, in this paper, we present a focused study on the cross-oilfield reservoir classification task. Specifically, we first propose a Multi-scale Sensor Extraction (MSE) to extract the multi-scale feature representations of geological characteristics from multivariate well logs. Furthermore, we design an encoder-decoder module, Specific Feature Learning (SFL), to take advantage of specific information of both oilfields. Then, we develop a Knowledge-Attentive Transfer (KAT) module to learn the feature-invariant representation and transfer the geological knowledge from a source oilfield to a target oilfield. Finally, we evaluate our approaches by conducting extensive experiments with real-world industrial datasets. The experimental results clearly demonstrate the effectiveness of our proposed approaches to transfer the geological knowledge and generate the cross-oilfield reservoir classifications.

Cross-Oilfield Reservoir Classification via Multi-Scale Sensor Knowledge Transfer

Large model size and high computational complexity prevent the neural machine translation (NMT) models from being deployed to low resource devices (e.g. mobile phones). Due to the large vocabulary, a large storage memory is required for the word embedding matrix in NMT models, in the meantime, high latency is introduced when constructing the word probability distribution. Based on reusing the word embedding matrix in the softmax layer, it is possible to handle the two problems brought by large vocabulary at the same time. In this paper, we propose Partial Vector Quantization (P-VQ) for NMT models, which can both compress the word embedding matrix and accelerate word probability prediction in the softmax layer. With P-VQ, the word embedding matrix is split into two low dimensional matrices, namely the shared part and the exclusive part. We compress the shared part by vector quantization and leave the exclusive part unchanged to maintain the uniqueness of each word. For acceleration, in the softmax layer, we replace most of the multiplication operations with the efficient looking-up operations based on our compression to reduce the computational complexity. Furthermore, we adopt curriculum learning and compact the word embedding matrix gradually to improve the compression quality. Experimental results on the Chinese-to-English translation task show that our method can reduce 74.35% of parameters of the word embedding and 74.42% of the FLOPs of the softmax layer. Meanwhile, the average BLEU score on the WMT test sets only drops 0.04.

Accelerating Neural Machine Translation with Partial Word Embedding Compression

During Multi-Agent Path Finding (MAPF) problems, agentscan  be  delayed  by  unexpected  events.  To  address  suchsituations  recent  work  describes k-Robust  Conflict-BasedSearch (k-CBS): an algorithm that produces coordinated andcollision-free plan that is robust for up tokdelays. In thiswork we introducing a variety of pairwise symmetry break-ing  constraints,  specific  tok-robust  planning,  that  can  effi-ciently find compatible and optimal paths for pairs of con-flicting  agents.  We  give  a  thorough  description  of  the  newconstraints and report large improvements to success rate ina range of domains including: (i) classic MAPF benchmarks;(ii)  automated  warehouse  domains  and;  (iii)  on  maps  fromthe  2019  Flatland  Challenge,  a  recently  introduced  railwaydomain wherek-robust planning can be fruitfully applied toschedule trains.

Symmetry Breaking for k-Robust Multi-Agent Path Finding

Recent deep-learning based Super-Resolution (SR) methods have achieved remarkable performance on images with known degradation. However, these methods always fail in real-world scene, since the Low-Resolution (LR) images after the ideal degradation (e.g., bicubic down-sampling) deviate from real source domain. The domain gap between the LR images and the real-world images can be observed clearly on frequency density, which inspires us to explicitly narrow the undesired gap caused by incorrect degradation. From this point of view, we design a novel Frequency Consistent Adaptation (FCA) that ensures the frequency domain consistency when applying existing SR methods to the real scene. We estimate degradation kernels from unsupervised images and generate the corresponding LR images. To provide useful gradient information for kernel estimation, we propose Frequency Density Comparator (FDC) by distinguishing the frequency density of images on different scales. Based on the domain-consistent LR-HR pairs, we train easy-implemented Convolutional Neural Network (CNN) SR models. Extensive experiments show that the proposed FCA improves the performance of the SR model under real-world setting achieving state-of-the-art results with high fidelity and plausible perception, thus providing a novel effective framework for real-world SR application.

Frequency Consistent Adaptation for Real World Super Resolution

BERT has set a new state-of-the-art performance on entity resolution (ER) task, largely owed to fine-tuning pre-trained language models and the deep pair-wise interaction. Albeit being remarkably effective, it comes with a steep increase in computational cost, as the deep-interaction requires to exhaustively compute every tuple pair to search for co-references. For ER task, it is often prohibitively expensive due to the large cardinality to be matched. To tackle this, we introduce a siamese network structure that independently encodes tuples using BERT but delays the pair-wise interaction via an enhanced alignment network. This siamese structure enables a dedicated blocking module to quickly filter out obviously dissimilar tuple pairs, and thus drastically reduces the cardinality of fine-grained matching. Further, the blocking and entity matching are integrated into a multi-task learning framework for facilitating both tasks. Extensive experiments on multiple datasets demonstrate that our model significantly outperforms state-of-the-art models (including BERT) in both efficiency and effectiveness.

Improving the Efficiency and Effectiveness for Bert-Based Entity Resolution

Dialogue policy learning based on reinforcement learning is difficult to be applied to real users to train dialogue agents from scratch because of the high cost. User simulators, which choose random user goals for the dialogue agent to train on, have been considered as an affordable substitute for real users. However, this random sampling method ignores the law of human learning, making the learned dialogue policy inefficient and unstable. We propose a novel framework, Automatic Curriculum Learning-based Deep Q-Network (ACL-DQN), which replaces the traditional random sampling method with a teacher policy model to realize the dialogue policy for automatic curriculum learning. The teacher model arranges a meaningful ordered curriculum and automatically adjusts it by monitoring the learning progress of the dialogue agent and the over-repetition penalty without any requirement of prior knowledge. The learning progress of the dialogue agent reflects the relationship between the dialogue agent's ability and the sampled goals' difficulty for sample efficiency. The over-repetition penalty guarantees the sampled diversity. Experiments show that the ACL-DQN significantly improves the effectiveness and stability of dialogue tasks with a statistically significant margin. Furthermore, the framework can be further improved by equipping with different curriculum schedules, which demonstrates that the framework has strong generalizability.

Downloads

Next from AAAI 2021

SAT-Based Decision Tree Learning for Large Data Sets

Similar lecture

Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence

.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 2021

SAT-Based Decision Tree Learning for Large Data Sets

Similar lecture

Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence

Downloads