2017 年的期刊文章 · 第 30 页

共 1233 篇,按发表时间排,新的在前,每页 40 篇。这一页是 2017 到 2017。

按期刊、按主题看 →

第 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 页

Econometrica Econometrics & Economics · 发表于 2017

First-Price Auctions With General Information Structures: Implications for Bidding and Revenue

Dirk Bergemann, Benjamin Brooks, Stephen Morris

摘要

We explore the impact of private information in sealed-bid first-price auctions. For a given symmetric and arbitrarily correlated prior distribution over values, we characterize the lowest winning-bid distribution that can arise across all information structures and equilibria. The information and equilibrium attaining this minimum leave bidders indifferent between their equilibrium bids and all higher bids. Our results provide lower bounds for bids and revenue with asymmetric distributions over values. We also report further characterizations of revenue and bidder surplus including upper bounds on revenue. Our work has implications for the identification of value distributions from data on winning bids and for the informationally robust comparison of alternative auction mechanisms. *(abstract via OpenAlex)*

JMLR Networks & Graphs · 发表于 2017

Faithfulness of Probability Distributions and Graphs

Kayvan Sadeghi

摘要

A main question in graphical models and causal inference is whether, given a probability distribution $P$ (which is usually an underlying distribution of data), there is a graph (or graphs) to which $P$ is faithful. The main goal of this paper is to provide a theoretical answer to this problem. We work with general independence models, which contain probabilistic independence models as a special case. We exploit a generalization of ordering, called preordering, of the nodes of (mixed) graphs. This allows us to provide sufficient conditions for a given independence model to be Markov to a graph with the minimum possible number of edges, and more importantly, necessary and sufficient conditions for a given probability distribution to be faithful to a graph. We present our results for the general case of mixed graphs, but specialize the definitions and results to the better-known subclasses of undirected (concentration) and bidirected (covariance) graphs as well as directed acyclic graphs.

JMLR Machine Learning · 发表于 2017

Explaining the Success of AdaBoost and Random Forests as Interpolating Classifiers

Abraham J. Wyner, Matthew Olson, Justin Bleich, David Mease

摘要

There is a large literature explaining why AdaBoost is a successful classifier. The literature on AdaBoost focuses on classifier margins and boosting's interpretation as the optimization of an exponential likelihood function. These existing explanations, however, have been pointed out to be incomplete. A random forest is another popular ensemble method for which there is substantially less explanation in the literature. We introduce a novel perspective on AdaBoost and random forests that proposes that the two algorithms work for similar reasons. While both classifiers achieve similar predictive accuracy, random forests cannot be conceived as a direct optimization procedure. Rather, random forests is a self- averaging, interpolating algorithm which creates what we denote as a spiked-smooth classifier, and we view AdaBoost in the same light. We conjecture that both AdaBoost and random forests succeed because of this mechanism. We provide a number of examples to support this explanation. In the process, we question the conventional wisdom that suggests that boosting algorithms for classification require regularization or early stopping and should be limited to low complexity classes of learners, such as decision stumps. We conclude that boosting should be used like random forests: with large decision trees, without regularization or early stopping.

JMLR Nonparametric & Semiparametric · 发表于 2017

Empirical Evaluation of Resampling Procedures for Optimising SVM Hyperparameters

Jacques Wainer, Gavin Cawley

摘要

Tuning the regularisation and kernel hyperparameters is a vital step in optimising the generalisation performance of kernel methods, such as the support vector machine (SVM). This is most often performed by minimising a resampling/cross-validation based model selection criterion, however there seems little practical guidance on the most suitable form of resampling. This paper presents the results of an extensive empirical evaluation of resampling procedures for SVM hyperparameter selection, designed to address this gap in the machine learning literature. We tested 15 different resampling procedures on 121 binary classification data sets in order to select the best SVM hyperparameters. We used three very different statistical procedures to analyse the results: the standard multi- classifier/multi-data set procedure proposed by Dem\v{s}ar, the confidence intervals on the excess loss of each procedure in relation to 5-fold cross validation, and the Bayes factor analysis proposed by Barber. We conclude that a 2-fold procedure is appropriate to select the hyperparameters of an SVM for data sets for 1000 or more datapoints, while a 3-fold procedure is appropriate for smaller data sets.

JMLR Other · 发表于 2017

Efficient Sampling from Time-Varying Log-Concave Distributions

Hariharan Narayanan, Alexer Rakhlin

摘要

We propose a computationally efficient random walk on a convex body which rapidly mixes with respect to a fixed log-concave distribution and closely tracks a time-varying log-concave distribution. We develop general theoretical guarantees on the required number of steps; this number can be calculated on the fly according to the distance from and the shape of the next distribution. We then illustrate the technique on several examples. Within the context of exponential families, the proposed method produces samples from a posterior distribution which is updated as data arrive in a streaming fashion. The sampling technique can be used to track time-varying truncated distributions, as well as to obtain samples from a changing mixture model, fitted in a streaming fashion to data. In the setting of linear optimization, the proposed method has oracle complexity with best known dependence on the dimension for certain geometries. In the context of online learning and repeated games, the algorithm is an efficient method for implementing no-regret mixture forecasting strategies. Remarkably, in some of these examples, only one step of the random walk is needed to track the next distribution.

Econometrica Longitudinal Data · 发表于 2017

Earnings and Consumption Dynamics: A Nonlinear Panel Data Framework

Manuel Arellano, Richard Blundell, Stéphane Bonhomme

摘要

We develop a new quantile-based panel data framework to study the nature of income persistence and the transmission of income shocks to consumption.Log-earnings are the sum of a general Markovian persistent component and a transitory innovation.The persistence of past shocks to earnings is allowed to vary according to the size and sign of the current shock.Consumption is modeled as an age-dependent nonlinear function of assets and the two earnings components.We establish the nonparametric identification of the nonlinear earnings process and the consumption policy rule.Exploiting the enhanced consumption and asset data in recent waves of the Panel Study of Income Dynamics, we find nonlinear persistence and conditional skewness to be key features of the earnings process.We show that the impact of earnings shocks varies substantially across earnings histories, and that this nonlinearity drives heterogeneous consumption responses.The transmission of shocks is found to vary systematically with assets. *(abstract via OpenAlex)*

Econometrica Econometrics & Economics · 发表于 2017

EXcess Idle Time

Federico M. Bandi, Davide Pirino, Roberto Renò

摘要

We introduce a novel economic indicator, named excess idle time (EXIT), measuring the extent of sluggishness in observed financial prices. Using a complete limit theory, we provide econometric support for the fact that high-frequency transaction prices are, coherently with liquidity and asymmetric information theories of price determination, generally stickier than implied by the ubiquitous semimartingale assumption. EXIT provides, for every asset and each trading day, a proxy for the extent of frictions (liquidity and asymmetric information) which is conceptually different from traditional price-impact measures. We relate it to existing measures and show its favorable performance under realistic data generating processes. We conclude by showing that EXIT uncovers an economically-meaningful short-term and long-term liquidity premium in market returns. *(abstract via OpenAlex)*

Econometrica Other · 发表于 2017

Dual-Donor Organ Exchange

Haluk Ergin, Tayfun Sönmez, M. Utku Ünver

摘要

Owing to the worldwide shortage of deceased-donor organs for transplantation, living donations have become a significant source of transplant organs.However, not all willing donors can donate to their intended recipients because of medical incompatibilities.These incompatibilities can be overcome by an exchange of donors between patients.For kidneys, such exchanges have become widespread in the last decade with the introduction of optimization and market design techniques to kidney exchange.A small but growing number of liver exchanges have also been conducted.Over the last two decades, a number of transplantation procedures emerged where organs from two living donors are transplanted to a single patient.Prominent examples include dual-graft liver transplantation, lobar lung transplantation, and simultaneous liver-kidney transplantation.Exchange, however, has been neither practiced nor introduced in this context.We introduce dual-donor organ exchange as a novel transplantation modality, and through simulations show that living-donor transplants can be significantly increased through such exchanges.We also provide a simple theoretical model for dual-donor organ exchange and introduce optimal exchange mechanisms under various logistical constraints. *(abstract via OpenAlex)*

JMLR Spatial & Time Series High-Dimensional · 发表于 2017

Document Neural Autoregressive Distribution Estimation

Stanislas Lauly, Yin Zheng, Alexandre Allauzen, Hugo Larochelle

摘要

We present an approach based on feed-forward neural networks for learning the distribution over textual documents. This approach is inspired by the Neural Autoregressive Distribution Estimator (NADE) model which has been shown to be a good estimator of the distribution over discrete-valued high-dimensional vectors. In this paper, we present how NADE can successfully be adapted to textual data, retaining the property that sampling or computing the probability of an observation can be done exactly and efficiently. The approach can also be used to learn deep representations of documents that are competitive to those learned by alternative topic modeling approaches. Finally, we describe how the approach can be combined with a regular neural network N-gram model and substantially improve its performance, by making its learned representation sensitive to the larger, document-level context.

JMLR Meta-Analysis & Data Integration · 发表于 2017

Distributed Stochastic Variance Reduced Gradient Methods by Sampling Extra Data with Replacement

Jason D. Lee, Qihang Lin, Tengyu Ma, Tianbao Yang

摘要

We study the round complexity of minimizing the average of convex functions under a new setting of distributed optimization where each machine can receive two subsets of functions. The first subset is from a random partition and the second subset is randomly sampled with replacement. Under this setting, we define a broad class of distributed algorithms whose local computation can utilize both subsets and design a distributed stochastic variance reduced gradient method belonging to in this class. When the condition number of the problem is small, our method achieves the optimal parallel runtime, amount of communication and rounds of communication among all distributed first-order methods up to constant factors. When the condition number is relatively large, a lower bound is provided for the number of rounds of communication needed by any algorithm in this class. Then, we present an accelerated version of our method whose the rounds of communication matches the lower bound up to logarithmic terms, which establishes that this accelerated algorithm has the lowest round complexity among all algorithms in our class under this new setting.

JMLR Networks & Graphs Meta-Analysis & Data Integration · 发表于 2017

Distributed Sequence Memory of Multidimensional Inputs in Recurrent Networks

Adam S. Charles, Dong Yin, Christopher J. Rozell

摘要

Recurrent neural networks (RNNs) have drawn interest from machine learning researchers because of their effectiveness at preserving past inputs for time-varying data processing tasks. To understand the success and limitations of RNNs, it is critical that we advance our analysis of their fundamental memory properties. We focus on echo state networks (ESNs), which are RNNs with simple memoryless nodes and random connectivity. In most existing analyses, the short-term memory (STM) capacity results conclude that the ESN network size must scale linearly with the input size for unstructured inputs. The main contribution of this paper is to provide general results characterizing the STM capacity for linear ESNs with multidimensional input streams when the inputs have common low- dimensional structure: sparsity in a basis or significant statistical dependence between inputs. In both cases, we show that the number of nodes in the network must scale linearly with the information rate and poly-logarithmically with the input dimension. The analysis relies on advanced applications of random matrix theory and results in explicit non-asymptotic bounds on the recovery error. Taken together, this analysis provides a significant step forward in our understanding of the STM properties in RNNs.

JMLR Meta-Analysis & Data Integration Nonparametric & Semiparametric · 发表于 2017

Distributed Semi-supervised Learning with Kernel Ridge Regression

Xiangyu Chang, Shao-Bo Lin, Ding-Xuan Zhou

摘要

This paper provides error analysis for distributed semi- supervised learning with kernel ridge regression (DSKRR) based on a divide-and-conquer strategy. DSKRR applies kernel ridge regression (KRR) to data subsets that are distributively stored on multiple servers to produce individual output functions, and then takes a weighted average of the individual output functions as a final estimator. Using a novel error decomposition which divides the generalization error of DSKRR into the approximation error, sample error and distributed error, we find that the sample error and distributed error reflect the power and limitation of DSKRR, compared with KRR processing the whole data. Thus a small distributed error provides a large range of the number of data subsets to guarantee a small generalization error. Our results show that unlabeled data play important roles in reducing the distributed error and enlarging the number of data subsets in DSKRR. Our analysis also applies to the case when the regression function is out of the reproducing kernel Hilbert space. Numerical experiments including toy simulations and a music-prediction task are employed to demonstrate our theoretical statements and show the power of unlabeled data in distributed learning.

JMLR Meta-Analysis & Data Integration · 发表于 2017

Distributed Learning with Regularized Least Squares

Shao-Bo Lin, Xin Guo, Ding-Xuan Zhou

摘要

We study distributed learning with the least squares regularization scheme in a reproducing kernel Hilbert space (RKHS). By a divide-and-conquer approach, the algorithm partitions a data set into disjoint data subsets, applies the least squares regularization scheme to each data subset to produce an output function, and then takes an average of the individual output functions as a final global estimator or predictor. We show with error bounds and learning rates in expectation in both the $L^2$-metric and RKHS-metric that the global output function of this distributed learning is a good approximation to the algorithm processing the whole data in one single machine. Our derived learning rates in expectation are optimal and stated in a general setting without any eigenfunction assumption. The analysis is achieved by a novel second order decomposition of operator differences in our integral operator approach. Even for the classical least squares regularization scheme in the RKHS associated with a general kernel, we give the best learning rate in expectation in the literature.

JMLR Bayesian Methods Meta-Analysis & Data Integration · 发表于 2017

Distributed Bayesian Learning with Stochastic Natural Gradient Expectation Propagation and the Posterior Server

Leonard Hasenclever, Stefan Webb, Thibaut Lienart, Sebastian Vollmer, Balaji Lakshminarayanan, Charles Blundell, Yee Whye Teh

摘要

This paper makes two contributions to Bayesian machine learning algorithms. Firstly, we propose stochastic natural gradient expectation propagation (SNEP), a novel alternative to expectation propagation (EP), a popular variational inference algorithm. SNEP is a black box variational algorithm, in that it does not require any simplifying assumptions on the distribution of interest, beyond the existence of some Monte Carlo sampler for estimating the moments of the EP tilted distributions. Further, as opposed to EP which has no guarantee of convergence, SNEP can be shown to be convergent, even when using Monte Carlo moment estimates. Secondly, we propose a novel architecture for distributed Bayesian learning which we call the posterior server. The posterior server allows scalable and robust Bayesian learning in cases where a data set is stored in a distributed manner across a cluster, with each compute node containing a disjoint subset of data. An independent Monte Carlo sampler is run on each compute node, with direct access only to the local data subset, but which targets an approximation to the global posterior distribution given all data across the whole cluster. This is achieved by using a distributed asynchronous implementation of SNEP to pass messages across the cluster. We demonstrate SNEP and the posterior server on distributed Bayesian learning of logistic regression and neural networks.

JMLR Other · 发表于 2017

Dimension Estimation Using Random Connection Models

Paulo Serra, Michel Mandjes

摘要

Information about intrinsic dimension is crucial to perform dimensionality reduction, compress information, design efficient algorithms, and do statistical adaptation. In this paper we propose an estimator for the intrinsic dimension of a data set. The estimator is based on binary neighbourhood information about the observations in the form of two adjacency matrices, and does not require any explicit distance information. The underlying graph is modelled according to a subset of a specific random connection model, sometimes referred to as the Poisson blob model. Computationally the estimator scales like $n\log n$, and we specify its asymptotic distribution and rate of convergence. A simulation study on both real and simulated data shows that our approach compares favourably with some competing methods from the literature, including approaches that rely on distance information.

JMLR Bayesian Methods · 发表于 2017

Differential Privacy for Bayesian Inference through Posterior Sampling

Christos Dimitrakakis, Blaine Nelson, Zuhe Zhang, Aikaterini Mitrokotsa, Benjamin I. P. Rubinstein

摘要

Differential privacy formalises privacy-preserving mechanisms that provide access to a database. Can Bayesian inference be used directly to provide private access to data? The answer is yes: under certain conditions on the prior, sampling from the posterior distribution can lead to a desired level of privacy and utility. For a uniform treatment, we define differential privacy over arbitrary data set metrics, outcome spaces and distribution families. This allows us to also deal with non-i.i.d or non-tabular data sets. We then prove bounds on the sensitivity of the posterior to the data, which delivers a measure of robustness. We also show how to use posterior sampling to provide differentially private responses to queries, within a decision-theoretic framework. Finally, we provide bounds on the utility of answers to queries and on the ability of an adversary to distinguish between data sets. The latter are complemented by a novel use of Le Cam's method to obtain lower bounds on distinguishability. Our results hold for arbitrary metrics, including those for the common definition of differential privacy. For specific choices of the metric, we give a number of examples satisfying our assumptions.

JMLR Other · 发表于 2017

Density Estimation in Infinite Dimensional Exponential Families

Bharath Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Aapo Hyvärinen, Revant Kumar

摘要

In this paper, we consider an infinite dimensional exponential family $\mathcal{P}$ of probability densities, which are parametrized by functions in a reproducing kernel Hilbert space $\mathcal{H}$, and show it to be quite rich in the sense that a broad class of densities on $\mathbb{R}^d$ can be approximated arbitrarily well in Kullback-Leibler (KL) divergence by elements in $\mathcal{P}$. Motivated by this approximation property, the paper addresses the question of estimating an unknown density $p_0$ through an element in $\mathcal{P}$. Standard techniques like maximum likelihood estimation (MLE) or pseudo MLE (based on the method of sieves), which are based on minimizing the KL divergence between $p_0$ and $\mathcal{P}$, do not yield practically useful estimators because of their inability to efficiently handle the log-partition function. We propose an estimator $\hat{p}_n$ based on minimizing the Fisher divergence, $J(p_0\Vert p)$ between $p_0$ and $p\in \mathcal{P}$, which involves solving a simple finite-dimensional linear system. When $p_0\in\mathcal{P}$, we show that the proposed estimator is consistent, and provide a convergence rate of $n^{-\min\left\{\frac{2}{3},\frac{2\beta+1}{2\beta+2}\right\}}$ in Fisher divergence under the smoothness assumption that $\log p_0\in\mathcal{R}(C^\beta)$ for some $\beta\ge 0$, where $C$ is a certain Hilbert-Schmidt operator on $\mathcal{H}$ and $\mathcal{R}(C^\beta)$ denotes the image of $C^\beta$. We also investigate the misspecified case of $p_0\notin\mathcal{P}$ and show that $J(p_0\Vert\hat{p}_n)\rightarrow \inf_{p\in\mathcal{P}}J(p_0\Vert p)$ as $n\rightarrow \infty$, and provide a rate for this convergence under a similar smoothness condition as above. Through numerical simulations we demonstrate that the proposed estimator outperforms the non- parametric kernel density estimator, and that the advantage of the proposed estimator grows as $d$ increases.

JMLR Bayesian Methods High-Dimensional Latent Variables & Mixtures · 发表于 2017

Dense Distributions from Sparse Samples: Improved Gibbs Sampling Parameter Estimators for LDA

Yannis Papanikolaou, James R. Foulds, Timothy N. Rubin, Grigorios Tsoumakas

摘要

We introduce a novel approach for estimating Latent Dirichlet Allocation (LDA) parameters from collapsed Gibbs samples (CGS), by leveraging the full conditional distributions over the latent variable assignments to efficiently average over multiple samples, for little more computational cost than drawing a single additional collapsed Gibbs sample. Our approach can be understood as adapting the soft clustering methodology of Collapsed Variational Bayes (CVB0) to CGS parameter estimation, in order to get the best of both techniques. Our estimators can straightforwardly be applied to the output of any existing implementation of CGS, including modern accelerated variants. We perform extensive empirical comparisons of our estimators with those of standard collapsed inference algorithms on real-world data for both unsupervised LDA and Prior-LDA, a supervised variant of LDA for multi-label classification. Our results show a consistent advantage of our approach over traditional CGS under all experimental conditions, and over CVB0 inference in the majority of conditions. More broadly, our results highlight the importance of averaging over multiple samples in LDA parameter estimation, and the use of efficient computational techniques to do so.

JMLR Networks & Graphs High-Dimensional Machine Learning · 发表于 2017

Convolutional Neural Networks Analyzed via Convolutional Sparse Coding

Vardan Papyan, Yaniv Romano, Michael Elad

摘要

Convolutional neural networks (CNN) have led to many state-of- the-art results spanning through various fields. However, a clear and profound theoretical understanding of the forward pass, the core algorithm of CNN, is still lacking. In parallel, within the wide field of sparse approximation, Convolutional Sparse Coding (CSC) has gained increasing attention in recent years. A theoretical study of this model was recently conducted, establishing it as a reliable and stable alternative to the commonly practiced patch-based processing. Herein, we propose a novel multi-layer model, ML-CSC, in which signals are assumed to emerge from a cascade of CSC layers. This is shown to be tightly connected to CNN, so much so that the forward pass of the CNN is in fact the thresholding pursuit serving the ML-CSC model. This connection brings a fresh view to CNN, as we are able to attribute to this architecture theoretical claims such as uniqueness of the representations throughout the network, and their stable estimation, all guaranteed under simple local sparsity conditions. Lastly, identifying the weaknesses in the above pursuit scheme, we propose an alternative to the forward pass, which is connected to deconvolutional and recurrent networks, and also has better theoretical guarantees.

Econometrica Other · 发表于 2017

Contract Negotiation and the Coase Conjecture: A Strategic Foundation for Renegotiation-Proof Contracts

Bruno Strulovici

摘要

What does contract negotiation look like when some parties hold private information and negotiation frictions are negligible? This paper analyzes the above question and provides a foundation for renegotiation-proof contracts in a related environment. The model extends the framework of the Coase conjecture to situations in which the quantity or quality of the good is endogenously determined and to more general environments in which the traded goods are complements or substitutes. All equilibria converge to a unique outcome as frictions become negligible, which is separating, efficient, and straightforward to characterize. *(abstract via OpenAlex)*

Econometrica Econometrics & Economics · 发表于 2017

Continuity, Inertia, and Strategic Uncertainty: A Test of the Theory of Continuous Time Games

Evan Calford, Ryan Oprea

摘要

The theory of continuous time games (Simon and Stinchcombe (1989), Bergin and MacLeod (1993)) shows that continuous time interactions can generate very different equilibrium behavior than conventional discrete time interactions. We introduce new laboratory methods that allow us to eliminate natural inertia in subjects' decisions in continuous time experiments, thereby satisfying critical premises of the theory and enabling a first-time direct test. Applying these new methods to a simple timing game, we find strikingly large gaps in behavior between discrete and continuous time as the theory suggests. Reintroducing natural inertia into these games causes continuous time behavior to collapse to discrete time-like levels in some settings as predicted by subgame perfect Nash equilibrium. However, contra this prediction, the strength of this effect is fundamentally shaped by the severity of inertia: behavior tends towards discrete time benchmarks as inertia grows large and perfectly continuous time benchmarks as it falls towards zero. We provide evidence that these results are due to changes in the nature of strategic uncertainty as inertia approaches the continuous limit. *(abstract via OpenAlex)*

JMLR Latent Variables & Mixtures · 发表于 2017

Consistency, Breakdown Robustness, and Algorithms for Robust Improper Maximum Likelihood Clustering

Pietro Coretto, Christian Hennig

摘要

The robust improper maximum likelihood estimator (RIMLE) is a new method for robust multivariate clustering finding approximately Gaussian clusters. It maximizes a pseudo- likelihood defined by adding a component with improper constant density for accommodating outliers to a Gaussian mixture. A special case of the RIMLE is MLE for multivariate finite Gaussian mixture models. In this paper we treat existence, consistency, and breakdown theory for the RIMLE comprehensively. RIMLE's existence is proved under non-smooth covariance matrix constraints. It is shown that these can be implemented via a computationally feasible Expectation-Conditional Maximization algorithm.

JMLR Testing & Uncertainty · 发表于 2017

Confidence Sets with Expected Sizes for Multiclass Classification

Christophe Denis, Mohamed Hebiri

摘要

Multiclass classification problems such as image annotation can involve a large number of classes. In this context, confusion between classes can occur, and single label classification may be misleading. We provide in the present paper a general device that, given an unlabeled dataset and a score function defined as the minimizer of some empirical and convex risk, outputs a set of class labels, instead of a single one. Interestingly, this procedure does not require that the unlabeled dataset explores the whole classes. Even more, the method is calibrated to control the expected size of the output set while minimizing the classification risk. We show the statistical optimality of the procedure and establish rates of convergence under the Tsybakov margin condition. It turns out that these rates are linear on the number of labels. We apply our methodology to convex aggregation of confidence sets based on the $V$-fold cross validation principle also known as the superlearning principle (van der Laan et al., 2007). We illustrate the numerical performance of the procedure on real data and demonstrate in particular that with moderate expected size, w.r.t. the number of labels, the procedure provides significant improvement of the classification risk.

JMLR Meta-Analysis & Data Integration Nonparametric & Semiparametric · 发表于 2017

Computational Limits of A Distributed Algorithm for Smoothing Spline

Zuofeng Shang, Guang Cheng

摘要

In this paper, we explore statistical versus computational trade-off to address a basic question in the application of a distributed algorithm: what is the minimal computational cost in obtaining statistical optimality? In smoothing spline setup, we observe a phase transition phenomenon for the number of deployed machines that ends up being a simple proxy for computing cost. Specifically, a sharp upper bound for the number of machines is established: when the number is below this bound, statistical optimality (in terms of nonparametric estimation or testing) is achievable; otherwise, statistical optimality becomes impossible. These sharp bounds partly capture intrinsic computational limits of the distributed algorithm considered in this paper, and turn out to be fully determined by the smoothness of the regression function. We name the asymptotic analysis on such split-and-aggregation estimation/inference as splitotic theory. As a side remark, we argue that sample splitting may be viewed as an alternative form of regularization, playing a similar role as smoothing parameter.

Econometrica Other · 发表于 2017

Competitive Division of a Mixed Manna

Anna Bogomolnaia, Hervé Moulin, Fedor Sandomirskiy, Elena Yanovskaya

摘要

A mixed manna contains goods (that everyone likes) and bads (that everyone dislikes), \nas well as items that are goods to some agents, but bads or satiated to others. \nIf all items are goods and utility functions are homogeneous of degree 1 and concave \n(and monotone), the competitive division maximizes the Nash product of utilities \n(Gale–Eisenberg): hence it is welfarist (determined by the set of feasible utility profiles), \nunique, continuous, and easy to compute. \nWe show that the competitive division of a mixed manna is still welfarist. If the zero \nutility profile is Pareto dominated, the competitive profile is strictly positive and still \nuniquely maximizes the product of utilities. If the zero profile is unfeasible (for instance, \nif all items are bads), the competitive profiles are strictly negative and are the \ncritical points of the product of disutilities on the efficiency frontier. The latter allows \nfor multiple competitive utility profiles, from which no single-valued selection can be \ncontinuous or resource monotonic. \nThus the implementation of competitive fairness under linear preferences in interactive \nplatforms like SPLIDDIT will be more difficult when the manna contains bads \nthat overwhelm the goods. *(abstract via OpenAlex)*

Econometrica Econometrics & Economics · 发表于 2017

Competitive Bundling

Jidong Zhou

摘要

This paper proposes a model of competitive bundling with an arbitrary number of firms. In the regime of pure bundling, we find that relative to separate sales pure bundling tends to raise market prices, benefit firms, and harm consumers when the number of firms is above a threshold. This is in contrast to the findings in the duopoly case on which the existing literature often focuses. Our analysis also sheds new light on how consumer valuation dispersion affects price competition more generally. In the regime of mixed bundling, having more than two firms raises new challenges in solving the model. We derive the equilibrium pricing conditions and show that when the number of firms is large, the equilibrium prices have simple approximations and mixed bundling is generally pro-competitive relative to separate sales. Firms' incentives to bundle are also investigated. *(abstract via OpenAlex)*

JMLR Networks & Graphs · 发表于 2017

Community Extraction in Multilayer Networks with Heterogeneous Community Structure

James D. Wilson, John Palowitch, Shankar Bhamidi, Andrew B. Nobel

摘要

Multilayer networks are a useful way to capture and model multiple, binary or weighted relationships among a fixed group of objects. While community detection has proven to be a useful exploratory technique for the analysis of single-layer networks, the development of community detection methods for multilayer networks is still in its infancy. We propose and investigate a procedure, called Multilayer Extraction, that identifies densely connected vertex-layer sets in multilayer networks. Multilayer Extraction makes use of a significance based score that quantifies the connectivity of an observed vertex-layer set through comparison with a fixed degree random graph model. Multilayer Extraction directly handles networks with heterogeneous layers where community structure may be different from layer to layer. The procedure can capture overlapping communities, as well as background vertex-layer pairs that do not belong to any community. We establish consistency of the vertex-layer set optimizer of our proposed multilayer score under the multilayer stochastic block model. We investigate the performance of Multilayer Extraction on three applications and a test bed of simulations. Our theoretical and numerical evaluations suggest that Multilayer Extraction is an effective exploratory tool for analyzing complex multilayer networks. Publicly available code is available at github.com/jdwilson4/Multila yerExtraction.

JMLR High-Dimensional Meta-Analysis & Data Integration · 发表于 2017

Communication-efficient Sparse Regression

Jason D. Lee, Qiang Liu, Yuekai Sun, Jonathan E. Taylor

摘要

We devise a communication-efficient approach to distributed sparse regression in the high-dimensional setting. The key idea is to average debiased or desparsified lasso estimators. We show the approach converges at the same rate as the lasso as long as the dataset is not split across too many machines, and consistently estimates the support under weaker conditions than the lasso. On the computational side, we propose a new parallel and computationally-efficient algorithm to compute the approximate inverse covariance required in the debiasing approach, when the dataset is split across samples. We further extend the approach to generalized linear models.

JMLR Latent Variables & Mixtures · 发表于 2017

Clustering with Hidden Markov Model on Variable Blocks

Lin Lin, Jia Li

摘要

Large-scale data containing multiple important rare clusters, even at moderately high dimensions, pose challenges for existing clustering methods. To address this issue, we propose a new mixture model called Hidden Markov Model on Variable Blocks (HMM-VB) and a new mode search algorithm called Modal Baum-Welch (MBW) for mode-association clustering. HMM-VB leverages prior information about chain-like dependence among groups of variables to achieve the effect of dimension reduction. In case such a dependence structure is unknown or assumed merely for the sake of parsimonious modeling, we develop a recursive search algorithm based on BIC to optimize the formation of ordered variable blocks. The MBW algorithm ensures the feasibility of clustering via mode association, achieving linear complexity in terms of the number of variable blocks despite the exponentially growing number of possible state sequences in HMM-VB. In addition, we provide theoretical investigations about the identifiability of HMM-VB as well as the consistency of our approach to search for the block partition of variables in a special case. Experiments on simulated and real data show that our proposed method outperforms other widely used methods.

JMLR Networks & Graphs Latent Variables & Mixtures · 发表于 2017

Clustering from General Pairwise Observations with Applications to Time-varying Graphs

Shiau Hong Lim, Yudong Chen, Huan Xu

摘要

We present a general framework for graph clustering and bi- clustering where we are given a general observation (called a label) between each pair of nodes. This framework allows a rich encoding of various types of pairwise interactions between nodes. We propose a new tractable and robust approach to this problem based on convex optimization and maximum likelihood estimators. We analyze our algorithms under a general statistical model extending the planted partition and stochastic block models. Both sufficient and necessary conditions are provided for successful recovery of the underlying clusters. Our theoretical results subsume many existing graph clustering results for a wide range of settings, including planted partition, weighted clustering, submatrix localization and partially observed graphs. Furthermore, our results are applicable to novel settings including time-varying graphs, providing new insights to solutions of these problems. We provide empirical results on both synthetic and real data that corroborate with our theoretical findings.

JMLR Networks & Graphs · 发表于 2017

Classification of Time Sequences using Graphs of Temporal Constraints

Mathieu Guillame-Bert, Artur Dubrawski

摘要

We introduce two algorithms that learn to classify Symbolic and Scalar Time Sequences (SSTS); an extension of multivariate time series. An SSTS is a set of \emph{events} and a set of scalars. An event is defined by a symbol and a time-stamp. A scalar is defined by a symbol and a function mapping a number for each possible time stamp of the data. The proposed algorithms rely on temporal patterns called Graph of Temporal Constraints (GTC). A GTC is a directed graph in which vertices express occurrences of specific events, and edges express temporal constraints between occurrences of pairs of events. Additionally, each vertex of a GTC can be augmented with numeric constraints on scalar values. We allow GTCs to be cyclic and/or disconnected. The first of the introduced algorithms extracts sets of co-dependent GTCs to be used in a voting mechanism. The second algorithm builds decision forest like representations where each node is a GTC. In both algorithms, extraction of GTCs and model building are interleaved. Both algorithms are closely related to each other and they exhibit complementary properties including complexity, performance, and interpretability. The main novelties of this work reside in direct building of the model and efficient learning of GTC structures. We explain the proposed algorithms and evaluate their performance against a diverse collection of 59 benchmark data sets. In these experiments, our algorithms come across as highly competitive and in most cases closely match or outperform state-of-the-art alternatives in terms of the computational speed while dominating in terms of the accuracy of classification of time sequences.

JMLR Latent Variables & Mixtures Optimization & Learning Theory · 发表于 2017

Certifiably Optimal Low Rank Factor Analysis

Dimitris Bertsimas, Martin S. Copenhaver, Rahul Mazumder

摘要

Factor Analysis (FA) is a technique of fundamental importance that is widely used in classical and modern multivariate statistics, psychometrics, and econometrics. In this paper, we revisit the classical rank-constrained FA problem which seeks to approximate an observed covariance matrix ($\B\Sigma$) by the sum of a Positive Semidefinite (PSD) low-rank component ($\B\Theta$) and a diagonal matrix ($\B\Phi$) (with nonnegative entries) subject to $\B\Sigma - \B\Phi$ being PSD. We propose a flexible family of rank-constrained, nonlinear Semidefinite Optimization based formulations for this task. We introduce a reformulation of the problem as a smooth optimization problem with convex, compact constraints and propose a unified algorithmic framework, utilizing state of the art techniques in nonlinear optimization to obtain high-quality feasible solutions for our proposed formulation. At the same time, by using a variety of techniques from discrete and global optimization, we show that these solutions are certifiably optimal in many cases, even for problems with thousands of variables. Our techniques are general and make no assumption on the underlying problem data. The estimator proposed herein aids statistical interpretability and provides computational scalability and significantly improved accuracy when compared to current, publicly available popular methods for rank-constrained FA. We demonstrate the effectiveness of our proposal on an array of synthetic and real-life datasets. To our knowledge, this is the first paper that demonstrates how a previously intractable rank-constrained optimization problem can be solved to provable optimality by coupling developments in convex analysis and in global and discrete optimization.

JMLR Networks & Graphs Spatial & Time Series · 发表于 2017

COEVOLVE: A Joint Point Process Model for Information Diffusion and Network Evolution

Mehrdad Farajtabar, Yichen Wang, Manuel Gomez-Rodriguez, Shuang Li, Hongyuan Zha, Le Song

摘要

Information diffusion in online social networks is affected by the underlying network topology, but it also has the power to change it. Online users are constantly creating new links when exposed to new information sources, and in turn these links are alternating the way information spreads. However, these two highly intertwined stochastic processes, information diffusion and network evolution, have been predominantly studied separately, ignoring their co-evolutionary dynamics.

JMLR Optimization & Learning Theory · 发表于 2017

Bridging Supervised Learning and Test-Based Co-optimization

Elena Popovici

摘要

This paper takes a close look at the important commonalities and subtle differences between the well-established field of supervised learning and the much younger one of co-optimization. It explains the relationships between the problems, algorithms and views on cost and performance of the two fields, all throughout providing a two-way dictionary for the respective terminologies used to describe these concepts. The intent is to facilitate advancement of both fields through transfer and cross-pollination of ideas, techniques and results. As a proof of concept, a theoretical study is presented on the connection between existence / lack of free lunch in the two fields, showcasing a few ideas for improving computational complexity of certain supervised learning approaches.

JMLR Optimization & Learning Theory Machine Learning Networks & Graphs · 发表于 2017

Breaking the Curse of Dimensionality with Convex Neural Networks

Francis Bach

摘要

We consider neural networks with a single hidden layer and non- decreasing positively homogeneous activation functions like the rectified linear units. By letting the number of hidden units grow unbounded and using classical non-Euclidean regularization tools on the output weights, they lead to a convex optimization problem and we provide a detailed theoretical analysis of their generalization performance, with a study of both the approximation and the estimation errors. We show in particular that they are adaptive to unknown underlying linear structures, such as the dependence on the projection of the input variables onto a low-dimensional subspace. Moreover, when using sparsity- inducing norms on the input weights, we show that high- dimensional non-linear variable selection may be achieved, without any strong assumption regarding the data and with a total number of variables potentially exponential in the number of observations. However, solving this convex optimization problem in infinite dimensions is only possible if the non- convex subproblem of addition of a new unit can be solved efficiently. We provide a simple geometric interpretation for our choice of activation functions and describe simple conditions for convex relaxations of the finite-dimensional non- convex subproblem to achieve the same generalization error bounds, even when constant-factor approximations cannot be found. We were not able to find strong enough convex relaxations to obtain provably polynomial-time algorithms and leave open the existence or non-existence of such tractable algorithms with non-exponential sample complexities.

JMLR Bayesian Methods · 发表于 2017

Bayesian Tensor Regression

Rajarshi Guhaniyogi, Shaan Qamar, David B. Dunson

摘要

We propose a Bayesian approach to regression with a scalar response on vector and tensor covariates. Vectorization of the tensor prior to analysis fails to exploit the structure, often leading to poor estimation and predictive performance. We introduce a novel class of multiway shrinkage priors for tensor coefficients in the regression setting and present posterior consistency results under mild conditions. A computationally efficient Markov chain Monte Carlo algorithm is developed for posterior computation. Simulation studies illustrate substantial gains over existing tensor regression methods in terms of estimation and parameter inference. Our approach is further illustrated in a neuroimaging application.

JMLR Networks & Graphs Bayesian Methods Optimization & Learning Theory · 发表于 2017

Bayesian Network Learning via Topological Order

Young Woong Park, Diego Klabjan

摘要

We propose a mixed integer programming (MIP) model and iterative algorithms based on topological orders to solve optimization problems with acyclic constraints on a directed graph. The proposed MIP model has a significantly lower number of constraints compared to popular MIP models based on cycle elimination constraints and triangular inequalities. The proposed iterative algorithms use gradient descent and iterative reordering approaches, respectively, for searching topological orders. A computational experiment is presented for the Gaussian Bayesian network learning problem, an optimization problem minimizing the sum of squared errors of regression models with L1 penalty over a feature network with application of gene network inference in bioinformatics.

JMLR Networks & Graphs Bayesian Methods Latent Variables & Mixtures · 发表于 2017

Bayesian Learning of Dynamic Multilayer Networks

Daniele Durante, Nabanita Mukherjee, Rebecca C. Steorts

摘要

A plethora of networks is being collected in a growing number of fields, including disease transmission, international relations, social interactions, and others. As data streams continue to grow, the complexity associated with these highly multidimensional connectivity data presents novel challenges. In this paper, we focus on the time-varying interconnections among a set of actors in multiple contexts, called layers. Current literature lacks flexible statistical models for dynamic multilayer networks, which can enhance quality in inference and prediction by efficiently borrowing information within each network, across time, and between layers. Motivated by this gap, we develop a Bayesian nonparametric model leveraging latent space representations. Our formulation characterizes the edge probabilities as a function of shared and layer-specific actors positions in a latent space, with these positions changing in time via Gaussian processes. This representation facilitates dimensionality reduction and incorporates different sources of information in the observed data. In addition, we obtain tractable procedures for posterior computation, inference, and prediction. We provide theoretical results on the flexibility of our model. Our methods are tested on simulations and infection studies monitoring dynamic face-to-face contacts among individuals in multiple days, where we perform better than current methods in inference and prediction.

JMLR Bayesian Methods Spatial & Time Series · 发表于 2017

Bayesian Inference for Spatio-temporal Spike-and-Slab Priors

Michael Riis Andersen, Aki Vehtari, Ole Winther, Lars Kai Hansen

摘要

In this work, we address the problem of solving a series of underdetermined linear inverse problemblems subject to a sparsity constraint. We generalize the spike-and-slab prior distribution to encode a priori correlation of the support of the solution in both space and time by imposing a transformed Gaussian process on the spike-and-slab probabilities. An expectation propagation (EP) algorithm for posterior inference under the proposed model is derived. For large scale problems, the standard EP algorithm can be prohibitively slow. We therefore introduce three different approximation schemes to reduce the computational complexity. Finally, we demonstrate the proposed model using numerical experiments based on both synthetic and real data sets.

Econometrica Other · 发表于 2017

Bargaining With Asymmetric Information: An Empirical Study of Plea Negotiations

Bernardo S. Silveira

摘要

This paper empirically investigates how sentences to be assigned at trial impact plea bargaining. The analysis is based on a variation of a bargaining model with asymmetric information due to Bebchuk (1984). I provide conditions for the non-parametric identification of the model, propose a consistent non-parametric estimator, and implement it using data on criminal cases from North Carolina. I find that the majority of cases settle for a sentence that is roughly 50 percent of the one that would be assigned in the event of a trial conviction. Employing the estimated model, I evaluate how different sentencing reforms affect the outcome of criminal cases. My results indicate that lowering mandatory minimum sentences has the potential to greatly reduce the total amount of jail time assigned by the justice system, but may increase conviction rates. In contrast, the broader use of non-jail sentences for less serious crimes reduces the number of jail convictions, but has a negligible effect over the total assigned jail time. 1. *(abstract via OpenAlex)*

第 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 页