In bipartite networks, community structures are restricted to being disassortative, in that nodes of one type are grouped according to common patterns of connection with nodes of the other type. This makes the stochastic block model (SBM), a highly flexible generative model for networks with block structure, an intuitive choice for bipartite community detection. However, typical formulations of the SBM do not make use of the special structure of bipartite networks. In this work, we introduce a Bayesian nonparametric formulation of the SBM and a corresponding algorithm to efficiently find communities in bipartite networks without overfitting. The biSBM improves community detection results over general SBMs when data are noisy, improves the model resolution limit by a factor of $\sqrt{2}$, and expands our understanding of the complicated optimization landscape associated with community detection tasks. A direct comparison of certain terms of the prior distributions in the biSBM and a related high-resolution hierarchical SBM also reveals a counterintuitive regime of community detection problems, populated by smaller and sparser networks, where non-hierarchical models outperform their more flexible counterpart.

Recommender systems often face heterogeneous datasets containing highly personalized historical data of users, where no single model could give the best recommendation for every user. We observe this ubiquitous phenomenon on both public and private datasets and address the model selection problem in pursuit of optimizing the quality of recommendation for each user. We propose a meta-learning framework to facilitate user-level adaptive model selection in recommender systems. In this framework, a collection of recommenders is trained with data from all users, on top of which a model selector is trained via meta-learning to select the best single model for each user with the user-specific historical data. We conduct extensive experiments on two public datasets and a real-world production dataset, demonstrating that our proposed framework achieves improvements over single model baselines and sample-level model selector in terms of AUC and LogLoss. In particular, the improvements may lead to huge profit gain when deployed in online recommender systems.

Jing Dong and Xin T. Tong † January 24, 2020 Abstract Gradient descent (GD) is known to converge quickly for convex objective functions, but it can be trapped at local minimums. On the other hand, Langevin dynamics (LD) can explore the state space and find global minimums, but in order to give accurate estimates, LD needs to run with small discretization stepsize and weak stochastic force, which in general slow down its convergence. This paper shows that these two algorithms can "collaborate" through a simple exchange mechanism, in which they swap their current positions if LD yields a lower objective function. This idea can be seen as the singular limit of the replica exchange technique from the sampling literature. We show that this new algorithm converges to the global minimum linearly with high probability, assuming the objective function is strongly convex in a neighborhood of the unique global minimum. By replacing gradients with stochastic gradients, and adding a proper threshold to the exchange mechanism, our algorithm can also be used in online settings. We further verify our theoretical results through some numerical experiments, and observe superior performance of the proposed algorithm over running GD or LD alone. 1 Introduction Division of labor is the secret of any efficient enterprises. By collaborating with individuals with different skillsets, we can focus on tasks within our own expertise and produce better outcomes than working independently. This paper asks whether the same principle can be applied when designing an algorithm. Given a general smooth non-convex objective function F, we consider the unconstrained optimization problem min x R dF ( x). However, this local minimum may not be the global minimum, and GD will be trapped there afterwards. On the other hand, sampling-based algorithms, such as the Langevin dynamics (LD) can escape local minimums by their stochasticity, but the additional stochastic noise contaminates the optimization results and slows down the convergence when the iterate is near the global minimum. In general, deterministic algorithms are designed to finding local minimums quickly, but they can be terrible in exploration. Sampling-based algorithms are better suited for exploring the state space, but they are inefficient when pinpointing the local minimums. This paper investigates how they can "collaborate" to get the "best of the two worlds". The collaboration mechanism we introduced here comes from replica-exchange in the sampling literature. Its implementation is very simple: we run a copy of GD, denoted by X n; and a copy of LD, denoted by Y n. If F (X n) F (Y n), we swap their positions.

Throughout the course of the paper, we assume that y and X have been centered at 0 so there is no intercept in the model, where y is the n 1 vector of centered responses, X is the n p matrix of standardized regressors, β is the p 1 vector of coefficients to be estimated, and null is the n 1 vector of independent and identically distributed normal errors with mean 0 and variance σ 2 . Compared to traditional penalization functions that are usually symmetric about 0, continuous and nondecreasing in (0,), the rLASSO penalty functions are decreasing in (0,), discontinuous at 0, and converge to infinity when the coefficients approach zero. From a theoretical standpoint, rLASSO shares the same oracle property and same rate of estimation error with other LASSOtype penalty functions. An early reference to this class of models can be found in Song and Liang (2015), with more recent papers focusing on large sample asymptotics, along with computational strategies for frequentist estimation (Shin et al., 2018; Song, 2018). Our approach differs from this line of work in adopting a Bayesian perspective on rLASSO estimation. Ideally, a Bayesian solution can be obtained by placing appropriate priors on the regression coefficients that will mimic the effects of the rLASSO penalty. As apparent from (1), this arises in assuming a prior for β that decomposes as a product of independent inverse Laplace (double exponential) densities: π (β) p null j 1 λ 2β 2 j exp{ λ β j }I { β j null 0 }.

Federated Learning is a powerful machine learning paradigm to cooperatively train a global model with highly distributed data. A major bottleneck on the performance of distributed Stochastic Gradient Descent (SGD) algorithm for large-scale Federated Learning is the communication overhead on pushing local gradients and pulling global model. In this paper, to reduce the communication complexity of Federated Learning, a novel approach named Pulling Reduction with Local Compensation (PRLC) is proposed. Specifically, each training node intermittently pulls the global model from the server in SGD iterations, resulting in that it is sometimes unsynchronized with the server. In such a case, it will use its local update to compensate the gap between the local model and the global model. Our rigorous theoretical analysis of PRLC achieves two important findings. First, we prove that the convergence rate of PRLC preserves the same order as the classical synchronous SGD for both strongly-convex and non-convex cases with good scalability due to the linear speedup with respect to the number of training nodes. Second, we show that PRLC admits lower pulling frequency than the existing pulling reduction method without local compensation. We also conduct extensive experiments on various machine learning models to validate our theoretical results. Experimental results show that our approach achieves a significant pulling reduction over the state-of-the-art methods, e.g., PRLC requiring only half of the pulling operations of LAG.

Uncertainty quantification for deep learning is a challenging open problem. Bayesian statistics offer a mathematically grounded framework to reason about uncertainties; however, approximate posteriors for modern neural networks still require prohibitive computational costs. We propose a family of algorithms which split the classification task into two stages: representation learning and uncertainty estimation. We compare four specific instances, where uncertainty estimation is performed via either an ensemble of Stochastic Gradient Descent or Stochastic Gradient Langevin Dynamics snapshots, an ensemble of bootstrapped logistic regressions, or via a number of Monte Carlo Dropout passes. We evaluate their performance in terms of \emph{selective} classification (risk-coverage), and their ability to detect out-of-distribution samples. Our experiments suggest there is limited value in adding multiple uncertainty layers to deep classifiers, and we observe that these simple methods strongly outperform a vanilla point-estimate SGD in some complex benchmarks like ImageNet.

January 23, 2020 Abstract The optimal binning is the optimal discretization of a variable into bins given a discrete or continuous numeric target. We present a rigorous and extensible mathematical programming formulation to solving the optimal binning problem for a binary, continuous and multi-class target type, incorporating constraints not previously addressed. For all three target types, we introduce a convex mixed-integer programming formulation. Several algorithmic enhancements such as automatic determination of the most suitable monotonic trend via a Machine-Learning-based classifier and implementation aspects are thoughtfully discussed. The new mathematical programming formulations are carefully implemented in the open-source python library OptBinning. 1 Introduction Binning (grouping or bucketing) is a technique to discretize the values of a continuous variable into bins (groups or buckets). From a modeling perspective, the binning technique may address prevalent data issues such as the handling of missing values, the presence of outliers and statistical noise, and data scaling. Furthermore, the binning process is a valuable interpretable tool to enhance the understanding of the nonlinear dependence between a variable and a given target while reducing the model complexity. Ultimately, resulting bins can be used to perform data transformations. Binning techniques are extensively used in machine learning applications, exploratory data analysis and as an algorithm to speed up learning tasks; recently, binning has been applied to accelerate learning in gradient boosting decision tree [12].

In this paper, we propose an adaptive group lasso procedure to efficiently estimate structural breaks in cointegrating regressions. It is well-known that the group lasso estimator is not simultaneously estimation consistent and model selection consistent in structural break settings. Hence, we use a first step group lasso estimation of a diverging number of breakpoint candidates to produce weights for a second adaptive group lasso estimation. We prove that parameter changes are estimated consistently by group lasso if it is tuned correctly and show that the number of estimated breaks is greater than the true number but still sufficiently close to it. Then, we use these results and prove that the adaptive group lasso has oracle properties if weights are obtained from our first step estimation and the tuning parameter satisfies some further restrictions. Simulation results show that the proposed estimator delivers the expected results. An economic application to the long-run US money demand function demonstrates the practical importance of this methodology.

It has been demonstrated that adversarial graphs, i.e., graphs with imperceptible perturbations added, can cause deep graph models to fail on node/graph classification tasks. In this paper, we extend adversarial graphs to the problem of community detection which is much more difficult. We focus on black-box attack and aim to hide targeted individuals from the detection of deep graph community detection models, which has many applications in real-world scenarios, for example, protecting personal privacy in social networks and understanding camouflage patterns in transaction networks. We propose an iterative learning framework that takes turns to update two modules: one working as the constrained graph generator and the other as the surrogate community detection model. We also find that the adversarial graphs generated by our method can be transferred to other learning based community detection models.

Many functions of interest are in a high-dimensional space but exhibit low-dimensional structures. This paper studies regression of a $s$-H\"{o}lder function $f$ in $\mathds{R}^D$ which varies along an active subspace of dimension $d$ while $d\ll D$. A direct approximation of $f$ in $\mathds{R}^D$ with an $\varepsilon$ accuracy requires the number of samples $n$ in the order of $\varepsilon^{-(2s+D)/s}$. %by the well-known curse of dimensionality. In this paper, we modify the Generalized Contour Regression (GCR) algorithm to estimate the active subspace and use piecewise polynomials for function approximation. GCR is among the best estimators for the active subspace, but its sample complexity is an open question. Our modified GCR improves the efficiency over the original GCR and leads to an mean squared estimation error of $O(n^{-1})$ for the active subspace, when $n$ is sufficiently large. The mean squared regression error of $f$ is proved to be in the order of $\left(n/\log n\right)^{-\frac{2s}{2s+d}}$ where the exponent depends on the dimension of the active subspace $d$ instead of the ambient space $D$. This result demonstrates that GCR is effective in learning low-dimensional active subspaces. The convergence rate is validated through several numerical experiments.