United States

To efficiently solve high-dimensional problems with complicated constraints, projection-free online learning has received ever-increasing research interest. However, previous studies either focused on static regret that is not suitable for dynamic environments, or only established the dynamic regret bound under the smoothness of losses. In this paper, without the condition of the smoothness, we propose a novel projection-free online algorithm, and achieve an O(max{T^{2/3}V_T^{1/3},T^{1/2}}) dynamic regret bound for convex functions and an O(max{(TV_Tlog T)^{1/2},log T}) dynamic regret bound for strongly convex functions, where T is the time horizon and V_T denotes the variation of loss functions. Specifically, we first improve an existing projection-free algorithm called online conditional gradient (OCG) to enjoy small dynamic regret bounds with the prior knowledge of V_T. To work with unknowable V_T, we maintain multiple instances of the improved OCG that can handle different functional variations, and combine them with a meta-algorithm that can track the best one. Experimental results validate the efficiency and effectiveness of our algorithm.

AAAI 2021

Projection-Free Online Learning in Dynamic Environments

We are pleased to announce the Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24), which will be held in Vancouver, British Columbia at the Vancouver Convention Centre – West Building from 20-27 February, 2024.

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-24 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.

We expect for AAAI-24 to be an in-person conference – one author of all accepted papers will be expected to present work in person unless there are exceptional circumstances that prevent this.<br><br><br><br>

In order to access the AAAI-24 event page you need to register [here](https://aaai.org/aaai-conference/registration/)

AAAI 2024

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. 

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. 

We introduce and study a novel majority based opinion diffusion model. Consider a graph G, which represents a social network. Assume that initially a subset of nodes, called seed nodes or early adopters, are colored either black or white, which correspond to positive or negative opinion regarding a consumer product or a technological innovation. Then, in each round an uncolored node, which is adjacent to at least one colored node, chooses the most frequent color among its neighbors.

Consider a marketing campaign which advertises a product of poor quality and its ultimate goal is that more than half of the population believe in the quality of the product at the end of the opinion diffusion process. We focus on three types of attackers which can select the seed nodes in a deterministic or random fashion and manipulate almost half of them to adopt a positive opinion toward the product (that is, to choose black color). We say that an attacker succeeds if a majority of nodes are black at the end of the process. Our main purpose is to characterize classes of graphs where an attacker cannot succeed. In particular, we prove that if the maximum degree of the underlying graph is not too large or if it has strong expansion properties, then it is fairly resilient to such attacks.

Furthermore, we prove tight bounds on the stabilization time of the process (that is, the number of rounds it needs to end) in both settings of choosing the seed nodes deterministically and randomly. We also provide several hardness results for some optimization problems regarding stabilization time and choice of seed nodes.

Majority Opinion Diffusion in Social Networks: An Adversarial Approach

Explainability is a key requirement for text classification in many application domains ranging from sentiment analysis to medical diagnosis or legal reviews. Existing methods often rely on "attention" mechanisms for explaining classification results by estimating the relative importance of input units. However, recent studies have shown that such mechanisms tend to mis-identify irrelevant input units in their explanation. In this work, we propose a hybrid human-AI approach that incorporates human rationales into attention-based text classification models to improve the explainability of classification results. Specifically, we ask workers to provide rationales for their annotation by selecting relevant pieces of text. We introduce MARTA, a Bayesian framework that jointly learns an attention-based model and the reliability of workers while injecting human rationales into model training. We derive a principled optimization algorithm based on variational inference with efficient updating rules for learning MARTA parameters. Extensive validation on real-world datasets shows that our framework significantly improves the state of the art both in terms of classification explainability and accuracy.

MARTA: Leveraging Human Rationales for Explainable Text Classification

The Test Laboratory Scheduling Problem (TLSP) and its subproblem TLSP-S are real-world industrial scheduling problems that are extensions of the Resource-Constrained Project Scheduling Problem (RCPSP). Besides several additional constraints, TLSP includes a grouping phase where the jobs to be scheduled have to be assembled from smaller tasks and derive their properties from this grouping. For TLSP-S such a grouping is already part of the input.

In this work, we show how TLSP-S can be solved by Answer-set Programming extended with ideas from other constraint solving paradigms. We propose a novel and efficient encoding and apply an answer-set solver for constraint logic programs called clingcon. Additionally, we utilize our encoding in a Very Large Neighborhood Search framework and compare our methods with the state of the art approaches. Our approach provides new upper bounds and optimality proofs for several existing benchmark instances in the literature.

Constraint Logic Programming for Real-World Test Laboratory Scheduling

To efficiently solve online problems with complicated constraints, projection-free algorithms including online frank-wolfe (OFW) and its variants have received significant interest recently. However, in the general case, existing efficient projection-free algorithms only achieved the regret bound of O(T^{3/4}), which is worse than the regret of projection-based algorithms, where T is the number of decision rounds. In this paper, we study the special case of online learning over strongly convex sets, for which we first prove that OFW can enjoy a better regret bound of O(T^{2/3}) for general convex losses. The key idea is to refine the decaying step-size in the original OFW by a simple line search rule. Furthermore, for strongly convex losses, we propose a strongly convex variant of OFW by redefining the surrogate loss function in OFW. We show that it achieves a regret bound of O(T^{2/3}) over general convex sets and a better regret bound of O(T^{1/2}) over strongly convex sets.

Projection-Free Online Learning over Strongly Convex Sets

Stackelberg planning is a recent framework where a leader and a follower each choose a plan in the same planning task, the leader's objective being to maximize plan cost for the follower. This formulation naturally captures security-related (leader=defender, follower=attacker) as well as robustness-related (leader=adversarial event, follower=agent) scenarios. Solving Stackelberg planning tasks requires solving many related planning tasks at the follower level (in the worst case, one for every possible leader plan). Here we introduce new methods to tackle this source of complexity, through sharing information across follower tasks. Our evaluation shows that these methods can significantly reduce both the time needed to solve follower tasks and the number of follower tasks that need to be solved in the first place.

Faster Stackelberg Planning via Symbolic Search and Information Sharing

Heterogeneous information networks (HINs) are ideal for describing real-world data with different types of entities and relationships. To carry out machine learning on HINs, meta-paths are widely utilized to extract semantics with pre-defined patterns, and models such as graph convolutional networks (GCNs) are thus enabled. However, previous works generally assume a fixed set of meta-paths, which is unrealistic as real-world data are overwhelmingly diverse. Therefore, it is appealing if meta-paths can be automatically selected given an HIN, yet existing works aiming at such problem possess drawbacks, such as poor efficiency and ignoring feature heterogeneity. To address these drawbacks, we propose GraphMSE, an efficient heterogeneous GCN combined with automatic meta-path selection. Specifically, we design highly efficient meta-path sampling techniques, and then injectively project sampled meta-path instances to vectors. We then design a novel semantic feature space alignment, aiming to align the meta-path instance vectors and hence facilitate meta-path selection. Extensive experiments on real-world datasets demonstrate that GraphMSE outperforms state-of-the-art counterparts, figures out important meta-paths, and is dramatically (e.g. 200 times) more efficient.

GraphMSE: Efficient Meta-Path Selection in Semantically Aligned Feature Space for Graph Neural Networks

Understanding the dynamics of complex biological and physiological systems has been explored  for many years in the form of physically-based mathematical simulators. The behavior of a physical system is often described via ordinary differential equations (ODE), referred to as the dynamics. In the standard case, the dynamics are derived from purely physical considerations. By contrast, in this work we study how the dynamics can be learned by a generative adversarial network which combines both physical and data considerations. As a use case, we focus on the dynamics of the heart signal electrocardiogram (ECG). We begin by introducing a new GAN framework, dubbed ODE-GAN, in which the generator learns the dynamics of a physical system in the form of an ordinary differential equation. Specifically, the generator network receives as input a value at a specific time step, and produces the derivative of the system at that time step. Thus, the ODE-GAN learns purely data-driven dynamics. We then show how to incorporate physical considerations into ODE-GAN. We achieve this through the introduction of an additional input to the ODE-GAN generator: physical parameters, which partially characterize the signal of interest. As we focus on ECG signals, we refer to this new framework as ECG-ODE-GAN. We perform an empirical evaluation and show that generating ECG heartbeats from our learned dynamics improves ECG heartbeat classification.

ECG ODE-GAN: Learning Ordinary Differential Equations of ECG Dynamics via Generative Adversarial Learning

This paper considers a linear Fisher market with n buyers and a continuum of items. In order to compute market equilibria, we introduce (infinite-dimensional) convex programs over Banach spaces, thereby generalizing the Eisenberg-Gale convex program and its dual. Regarding the new convex programs, we establish existence of optimal solutions, KKT conditions, as well as strong duality. All these properties are established via non-standard arguments, which circumvent the limitations of duality theory in optimization over infinite-dimensional vector spaces. Furthermore, we show that there exists a pure equilibrium allocation, i.e., a division of the item space. Similar to the finite-dimensional case, a market equilibrium under the infinite-dimensional Fisher market is Pareto optimal, envy-free and proportional. We also show how to obtain the (a.e. unique) equilibrium prices and a pure equilibrium allocation from the (unique) equilibrium utility prices. When the item space is the unit interval [0,1] and buyers have piecewise linear utilities, we show that approximate equilibrium prices can be computed in polynomial time. This is achieved by solving a finite-dimensional convex program using the ellipsoid method. To this end, we give nontrivial and efficient subgradient and separation oracles. For general buyer valuations, we propose computing market equilibrium using stochastic dual averaging, which finds approximate equilibrium prices with high probability.

Infinite-Dimensional Fisher Markets: Equilibrium, Duality and Optimization

Sequential recommender systems aim to model usersâ€™ evolving interests from their historical behaviors, and hence make customized time-relevant recommendations. Compared with traditional models, deep learning approaches such as CNN and RNN have achieved remarkable advancements in recommendation tasks. Recently, the BERT framework also emerges as a promising method, benefited from its self-attention mechanism in processing sequential data. However, one limitation of the original BERT framework is that it only considers one input source of the natural language tokens. It is still an open question to leverage various types of information under the BERT framework. Nonetheless, it is intuitively appealing to utilize other side information, such as item category or tag, for more comprehensive depictions and better recommendations. In our pilot experiments, we found naive approaches, which directly fuse types of side information into the item embeddings, usually bring very little or even negative effects. Therefore, in this paper, we propose the NOn-inVasive self-Attention mechanism (NOVA) to leverage side information effectively under the BERT framework. NOVA makes use of side information to generate better attention distribution, rather than directly altering the item embeddings, which may cause information overwhelming. We validate the NOVA-BERT model on both public and commercial datasets, and our method can stably outperform the state-of-the-art models with negligible computational overheads.

Noninvasive Self-Attention for Side Information Fusion in Sequential Recommendation

The synthesis of materials using the principle of thermogravimetric analysis to discover new anticorrosive paints requires several costly experiments. This paper presents an approach combining empirical data and domain analytical models to reduce the number of real experiments required to obtain the desired synthesis. The main idea is to predict the behavior of the synthesis of two materials with well-defined mass proportions as a function of temperature. As no exact equational model exists to predict the new material, we integrate a machine learning approach circumscribed by existing domain analytical models such as heating and kinetics equations in order to derive a generative model of augmented experiments. Extensive empirical evaluation shows that using machine learning approach guided by analytic models, it is possible to substantially reduce the number of needed physical experiments without losing the approximation quality.

Downloads

Next from AAAI 2021

Majority Opinion Diffusion in Social Networks: An Adversarial Approach

Similar lecture

Non-stationary Projection-Free Online Learning with Dynamic and Adaptive Regret Guarantees

.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

Majority Opinion Diffusion in Social Networks: An Adversarial Approach

Similar lecture

Non-stationary Projection-Free Online Learning with Dynamic and Adaptive Regret Guarantees

Downloads