United States

Motivated by the increasing concern about privacy in nowadays data-intensive online learning systems, we consider a black-box optimization in the nonparametric Gaussian process setting with local differential privacy (LDP) guarantee. Specifically, the rewards from each user are further corrupted to protect privacy and the learner only has access to the corrupted rewards to minimize the regret. We first derive the regret lower bounds for any LDP mechanism and any learning algorithm. Then, we present three almost optimal algorithms based on the GP-UCB framework and Laplace DP mechanism. In this process, we also propose a new Bayesian optimization (BO) method (called MoMA-GP-UCB) based on median-of-means techniques and kernel approximations, which complements previous BO algorithms under heavy-tailed payoffs with reduced complexity. Further, empirical comparisons of different algorithms on both synthetic and real-world datasets highlight the superior performance of MoMA-GP-UCB in both private and non-private scenarios.

AAAI 2021

Local Differential Privacy for Bayesian Optimization

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

Recently decentralized optimization attracts much attention in machine learning because it is more communication-efficient than the centralized fashion. Quantization is a promising method to reduce the communication cost via cutting down the budget of each single communication using the gradient compression. To further improve the communication efficiency, more recently, some quantized decentralized algorithms have been studied. However, the quantized decentralized algorithm for nonconvex constrained machine learning problems is still limited. Frank-Wolfe (a.k.a., conditional gradient or projection-free) method is very efficient to solve many constrained optimization tasks, such as low-rank or sparsity-constrained models training. In this paper, to fill the gap of decentralized quantized constrained optimization, we propose a novel communication-efficient Decentralized Quantized Stochastic Frank-Wolfe (DQSFW) algorithm for non-convex constrained learning models. We first design a new counterexample to show that the vanilla decentralized quantized stochastic Frank-Wolfe algorithm usually diverges. Thus, we propose DQSFW algorithm with the gradient tracking technique to guarantee the method will converge to the stationary point of non-convex optimization safely. In our theoretical analysis, we prove that to achieve the stationary point our DQSFW algorithm achieves the same gradient complexity as the standard stochastic Frank-Wolfe and centralized Frank-Wolfe algorithms, but has much less communication cost. Experiments on matrix completion and model compression applications demonstrate the efficiency of our new algorithm.

Communication-Efficient Projection-Free Algorithm for Nonconvex Constrained Learning Models

Core-guided techniques have revolutionized Boolean satisfiability
approaches to optimization problems (MaxSAT), but the process at
the heart of these methods, strengthening bounds on solutions by
repeatedly adding cardinality constraints, remains a bottleneck.
Cardinality constraints require significant work to be re-encoded to
SAT, and SAT solvers are notoriously weak at cardinality reasoning.

In this work, we lift core-guided search to pseudo-Boolean (PB)
solvers, which deal with more general PB optimization problems
and operate natively with cardinality constraints. The cutting planes
method used in such solvers allows us to derive stronger cardinality
constraints, which yield better updates to solution bounds, and the
increased efficiency of objective function reformulation also makes it
feasible to switch repeatedly between lower-bounding and upper-
bounding search. A thorough evaluation on applied and crafted
benchmarks shows that our core-guided PB solver significantly
improves on the state of the art in pseudo-Boolean optimization.

Cutting to the Core of Pseudo-Boolean Optimization: Combining Core-Guided Search with Cutting Planes Reasoning

Learning system dynamics directly from observations is a promising direction in machine learning due to its potential to significantly enhance our ability to understand physical systems. However, the dynamics of many real-world systems are challenging to learn due to the presence of nonlinear potentials and a number of interactions that scales quadratically with the number of particles N, as in the case of the N-body problem. In this work we introduce an approach that transforms a fully-connected interaction graph into a hierarchical one which reduces the number of edges to O(N). This results in a linear time and space complexity while the pre-computation of the hierarchical graph requires O(N log (N)) time and O(N) space. Using our approach, we are able to train models on much larger particle counts, even on a single GPU. We evaluate how the phase space position accuracy and energy conservation depend on the number of simulated particles. Our approach retains high accuracy and efficiency even on large-scale gravitational N-body simulations which are impossible to run on a single machine if a fully-connected graph is used. Similar results are also observed when simulating Coulomb interactions. Furthermore, we make several important observations regarding the performance of this new hierarchical model, including: i) its accuracy tends to improve with the number of particles in the simulation and ii) its generalisation to unseen particle counts is also much better than for models that use all O(N^2) interactions.

Scalable Graph Networks for Particle Simulations

Optical neural networks (ONNs) have demonstrated record-breaking potential in high-performance neuromorphic computing due to their ultra-high execution speed and low energy consumption. However, current learning protocols fail to provide scalable and efficient solutions to photonic circuit optimization in practical applications. In this work, we propose a novel on-chip learning framework to release the full potential of ONNs for power-efficient in situ training. Instead of deploying implementation-costly back-propagation, we directly optimize the device configurations with computation budgets and power constraints. We are the first to model the ONN on-chip learning as a resource-constrained stochastic noisy zeroth-order optimization problem, and propose a novel mixed-training strategy with two-level sparsity and power-aware dynamic pruning to offer a scalable on-chip training solution in practical ONN deployment. Compared with previous methods, we are the first to optimize over 2,500 optical components on chip. We can achieve much better optimization stability, 3.7x-7.6x higher efficiency, and save >90% power under practical device variations and thermal crosstalk.

Efficient On-Chip Learning for Optical Neural Networks through Power-Aware Sparse Zeroth-Order Optimization

This paper studies the unsupervised cross-domain translation problem by proposing a generative framework, in which the probability distribution of each domain is represented by a generative cooperative network that consists of an energy-based model and a latent variable model. The use of generative cooperative network enables maximum likelihood learning of the domain model by MCMC teaching, where the energy-based model seeks to fit the data distribution of domain and distills its knowledge to the latent variable model via MCMC. Specifically, in the MCMC teaching process, the latent variable model parameterized by an encoder-decoder maps examples from the source domain to the target domain, while the energy-based model further refines the mapped results by Langevin revision such that the revised results match to the examples in the target domain in terms of the statistical properties, which are defined by the learned energy function. For the purpose of building up a correspondence between two unpaired domains, the proposed framework simultaneously learns a pair of cooperative networks with cycle consistency, accounting for a two-way translation between two domains, by alternating MCMC teaching. Experiments show that the proposed framework is useful for unsupervised image-to-image translation and unpaired image sequence translation.

Learning Cycle-Consistent Cooperative Networks via Alternating MCMC Teaching for Unsupervised Cross-Domain Translation

Description logics (DLs) are knowledge representation languages that are used in the field of artificial intelligence (AI).
A common technique is to query DL knowledge bases, e.g., by Boolean Datalog queries, and ask for entailment. 
But real world knowledge-bases are often obtained by combining data from various sources. 
This, inherently, might result in certain inconsistencies (with respect to a given query) and requires to estimate a degree of inconsistency before using a knowledge-base.
In this paper, we provide a complexity analysis of fixed-domain non-entailment (NE) on Datalog programs for well-established families of knowledge bases (KBs).
We exhibit a detailed complexity map for the decision cases, counting and projected counting, which may serve as a quantitative measure for inconsistency of a KB with respect to a query.
Our results show that NE is natural for the second, third, and fourth level of the polynomial (counting) hierarchy depending on the type of the studied query (stratified, normal, disjunctive) and one level higher for the projected versions.
Further, we show fixed-parameter tractability by bounding the treewidth, provide a constructive algorithm, and show its theoretical limitation in terms of conditional lower bounds.

Knowledge-Base Degrees of Inconsistency: Complexity and Counting

We study approval-based committee elections for the case where the voters' preferences come from a 2D-Euclidean model. We consider two main issues: First, we ask for the complexity of computing election results. Second, we evaluate election outcomes experimentally, following the visualization technique of Elkind et al., (AAAI-2017).  Regarding the first issue, we find that many NP-hard rules remain intractable for 2D-Euclidean elections. For the second one, we observe that the behavior and nature of many rules strongly depends on the exact protocol for choosing the approved candidates.

An Analysis of Approval-Based Committee Rules for 2D-Euclidean Elections

Bayesian optimization (BO) is an efficient framework for solving black-box optimization problems with expensive function evaluations. This paper addresses the BO problem setting for combinatorial spaces (e.g., sequences and graphs) that occurs naturally in science and engineering applications. A prototypical example is molecular optimization guided by expensive experiments. The key challenge is to balance the complexity of statistical models and tractability of search to select combinatorial structures for evaluation. In this paper, we propose an efficient approach referred as Mercer Features for Combinatorial Bayesian Optimization (MerCBO). The key idea behind MerCBO is to provide explicit feature maps for diffusion kernels over discrete objects by exploiting the structure of their combinatorial graph representation. These Mercer features combined with Thompson sampling as the acquisition function allows us to employ efficient solvers for finding the next structure for evaluation. Experimental evaluation on diverse real-world benchmarks demonstrates that MerCBO performs similarly or better than prior methods.

Mercer Features for Efficient Combinatorial Bayesian Optimization

We propose a market-inspired bidding scheme for the assignment of paper reviews in large academic conferences. We provide an analysis of the incentives of reviewers during the bidding phase, when reviewers have both private costs and some information about the demand for each paper; and their  goal is to obtain the best possible k papers for a predetermined k. 

We show that by assigning `budgets' to reviewers and a `price' for every paper that is (roughly) proportional to its  demand, the best response of a reviewer is to bid sincerely, i.e., on her most favorite papers, and match the budget even when it is not enforced.  This game-theoretic analysis is based on a simple, prototypical assignment algorithm.
We show via extensive simulations on bidding data from real conferences, that our  bidding scheme would substantially improve both the bid distribution and the resulting assignment.

A Market-Inspired Bidding Scheme for Peer Review Paper Assignment

Interpretable machine learning has gained much attention recently. Briefness and comprehensiveness are necessary in order to provide a large amount of information concisely when explaining a black-box decision system. However, existing interpretable machine learning methods fail to consider briefness and comprehensiveness simultaneously, leading to redundant explanations. We propose the variational information bottleneck for interpretation, VIBI, a system-agnostic interpretable method that provides a brief but comprehensive explanation. VIBI adopts an information theoretic principle, information bottleneck principle, as a criterion for finding such explanations. For each instance, VIBI selects key features that are maximally compressed about an input (briefness), and informative about a decision made by a black-box system on that input (comprehensive). We evaluate VIBI on three datasets and compare with state-of-the-art interpretable machine learning methods in terms of both interpretability and fidelity evaluated by human and quantitative metrics.

Downloads

Next from AAAI 2021

Communication-Efficient Projection-Free Algorithm for Nonconvex Constrained Learning Models

Similar lecture

Differentially Private Regret Minimization in Episodic Markov Decision Processes

.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

Communication-Efficient Projection-Free Algorithm for Nonconvex Constrained Learning Models

Similar lecture

Differentially Private Regret Minimization in Episodic Markov Decision Processes

Downloads