研究园简易版 · 经典书籍 · 期刊文章 · 有原文 · 完整版(可多选筛选、搜索) · 首页
2018 年的期刊文章 · 第 28 页
共 1294 篇,按发表时间排,新的在前,每页 40 篇。这一页是 2018 到 2018。
按期刊、按主题看 →
Econometrica Other · 发表于 2018
Susanto Basu, Brent Bundick
摘要
de Groot, Richter, and Throckmorton, 2018 argue that the model in Basu and Bundick, 2017 can match the empirical evidence only because the model assumes an asymptote in the economy's response to an uncertainty shock. In this Reply, we provide new results showing that our model's ability to match the data does not rely either on assuming preferences that imply an asymptote nor on a particular value of the intertemporal elasticity of substitution. We demonstrate that shifting to preferences that are not vulnerable to the Comment's critique does not change our previous conclusions about the propagation of uncertainty shocks to macroeconomic outcomes. *(abstract via OpenAlex)*
Econometrica Other · 发表于 2018
Oliver de Groot, Alexander W. Richter, Nathaniel A. Throckmorton
摘要
Basu and Bundick, 2017 showed an intertemporal preference volatility shock has meaningful effects on real activity in a New Keynesian model with Epstein and Zin, 1991 preferences. We show that when the distributional weights on current and future utility in the Epstein–Zin time aggregator do not sum to 1, there is an asymptote in the responses to such a shock with unit intertemporal elasticity of substitution. In the Basu–Bundick model, the intertemporal elasticity of substitution is set near unity and the preference shock only hits current utility, so the sum of the weights differs from 1. We show that when we restrict the weights to sum to 1, the asymptote disappears and preference volatility shocks no longer have large effects. We examine several different calibrations and preferences as potential resolutions with varying degrees of success. *(abstract via OpenAlex)*
JMLR Latent Variables & Mixtures · 发表于 2018
Mario Lucic, Matthew Faulkner, Andreas Krause, Dan Feldman
摘要
How can we train a statistical mixture model on a massive data set? In this work we show how to construct \emph{coresets} for mixtures of Gaussians. A coreset is a weighted subset of the data, which guarantees that models fitting the coreset also provide a good fit for the original data set. We show that, perhaps surprisingly, Gaussian mixtures admit coresets of size polynomial in dimension and the number of mixture components, while being \emph{independent} of the data set size. Hence, one can harness computationally intensive algorithms to compute a good approximation on a significantly smaller data set. More importantly, such coresets can be efficiently constructed both in distributed and streaming settings and do not impose restrictions on the data generating process. Our results rely on a novel reduction of statistical estimation to problems in computational geometry and new combinatorial complexity results for mixtures of Gaussians. Empirical evaluation on several real- world data sets suggests that our coreset-based approach enables significant reduction in training-time with negligible approximation error.
Econometrica Econometrics & Economics · 发表于 2018
Ana Babus, Péter Kondor
摘要
We propose a model of trade in over-the-counter (OTC) markets in which each dealer with private information can engage in bilateral transactions with other dealers, as determined by her links in a network.Each dealer's strategy is represented as a quantity-price schedule.We analyze the effect of trade decentralization and adverse selection on information diffusion, expected profits, trading costs and welfare.Information diffusion through prices is not affected by dealers' strategic trading motives, and there is an informational externality that constrains the informativeness of prices.Trade decentralization can both increase or decrease welfare.A dealer's trading cost is driven by both her own and her counterparties' centrality.Central dealers tend to learn more, trade more at lower costs and earn higher expected profit. *(abstract via OpenAlex)*
JMLR Machine Learning · 发表于 2018
Philipp Probst, Anne-Laure Boulesteix
摘要
The number of trees $T$ in the random forest (RF) algorithm for supervised learning has to be set by the user. It is unclear whether $T$ should simply be set to the largest computationally manageable value or whether a smaller $T$ may be sufficient or in some cases even better. While the principle underlying bagging is that more trees are better, in practice the classification error rate sometimes reaches a minimum before increasing again for increasing number of trees. The goal of this paper is four-fold: (i) providing theoretical results showing that the expected error rate may be a non-monotonous function of the number of trees and explaining under which circumstances this happens; (ii) providing theoretical results showing that such non-monotonous patterns cannot be observed for other performance measures such as the Brier score and the logarithmic loss (for classification) and the mean squared error (for regression); (iii) illustrating the extent of the problem through an application to a large number (n = 306) of datasets from the public database OpenML; (iv) finally arguing in favor of setting $T$ to a computationally feasible large number as long as classical error measures based on average loss are considered.
Econometrica Econometrics & Economics · 发表于 2018
Sebastian Schweighofer-Kodritsch
摘要
This paper presents an analysis of general time preferences in the canonical Rubinstein (1982) model of bargaining, allowing for arbitrarily history-dependent strategies. I derive a simple sufficient structure for optimal punishments and thereby fully characterize (i) the set of equilibrium outcomes for any given preference profile, and (ii) the set of preference profiles for which equilibrium is unique. Based on this characterization, I establish that a weak notion of present bias - implied, e.g., by any hyperbolic or quasi-hyperbolic discounting - is sufficient for equilibrium to be unique, stationary and efficient. Conversely, I demonstrate how certain violations of present bias give rise to multiple (non-stationary) equilibria that feature delayed agreement under gradually increasing offers. *(abstract via OpenAlex)*
JMLR Other · 发表于 2018
Zeyi Wen, Jiashuai Shi, Qinbin Li, Bingsheng He, Jian Chen
摘要
Support Vector Machines (SVMs) are classic supervised learning models for classification, regression and distribution estimation. A survey conducted by Kaggle in 2017 shows that 26% of the data mining and machine learning practitioners are users of SVMs. However, SVM training and prediction are very expensive computationally for large and complex problems. This paper presents an efficient and open source SVM software toolkit called ThunderSVM which exploits the high-performance of Graphics Processing Units (GPUs) and multi-core CPUs. ThunderSVM supports all the functionalities–including classification (SVC), regression (SVR) and one-class SVMs–of LibSVM and uses identical command line options, such that existing LibSVM users can easily apply our toolkit. ThunderSVM can be used through multiple language interfaces including C/C++, Python, R and MATLAB. Our experimental results show that ThunderSVM is generally an order of magnitude faster than LibSVM while producing identical SVMs. In addition to the high efficiency, we design our convex optimization solver in a general way such that SVC, SVR, and one-class SVMs share the same solver for the ease of maintenance. Documentation, examples, and more about ThunderSVM are available at https://github.com/zeyiwen/thundersvm
JMLR Other · 发表于 2018
Alain Celisse, Tristan Mary-Huard
摘要
The present work aims at deriving theoretical guaranties on the behavior of some cross-validation procedures applied to the $k$-nearest neighbors ($k$NN) rule in the context of binary classification. Here we focus on the leave-$p$-out cross-validation (L$p$O) used to assess the performance of the $k$NN classifier. Remarkably this L$p$O estimator can be efficiently computed in this context using closed-form formulas derived by Celisse and Mary-Huard (2011). We describe a general strategy to derive moment and exponential concentration inequalities for the L$p$O estimator applied to the $k$NN classifier. Such results are obtained first by exploiting the connection between the L$p$O estimator and U-statistics, and second by making an intensive use of the generalized Efron-Stein inequality applied to the L$1$O estimator. One other important contribution is made by deriving new quantifications of the discrepancy between the L$p$O estimator and the classification error/risk of the $k$NN classifier. The optimality of these bounds is discussed by means of several lower bounds as well as simulation experiments.
JMLR High-Dimensional · 发表于 2018
Gian-Andrea Thanei, Nicolai Meinshausen, Rajen D. Shah
摘要
When performing regression on a data set with $p$ variables, it is often of interest to go beyond using main linear effects and include interactions as products between individual variables. For small-scale problems, these interactions can be computed explicitly but this leads to a computational complexity of at least $\mathcal{O}(p^2)$ if done naively. This cost can be prohibitive if $p$ is very large. We introduce a new randomised algorithm that is able to discover interactions with high probability and under mild conditions has a runtime that is subquadratic in $p$. We show that strong interactions can be discovered in almost linear time, whilst finding weaker interactions requires $\mathcal{O}(p^\alpha)$ operations for $1R. We demonstrate its efficiency for application to genome-wide association studies, where more than $10^{11}$ interactions can be screened in under $280$ seconds with a single-core $1.2$ GHz CPU.
Econometrica Econometrics & Economics · 发表于 2018
Gregory S. Crawford, Robin S. Lee, Michael D. Whinston, Ali Yurukoglu
摘要
We investigate the welfare effects of vertical integration of regional sports networks (RSNs) with programming distributors in U.S. multichannel television markets.Vertical integration can enhance efficiency by reducing double marginalization and increasing carriage of channels, but can also harm welfare due to foreclosure and incentives to raise rivals' costs.We estimate a structural model of viewership, subscription, distributor pricing, and affiliate fee bargaining using a rich data set on the U.S. cable and satellite television industry (2000-2010).We use these estimates to analyze the impact of simulated vertical mergers and divestitures of RSNs on competition and welfare, and examine the efficacy of regulatory policies introduced by the U.S. Federal Communications Commission to address competition concerns in this industry. *(abstract via OpenAlex)*
Econometrica Other · 发表于 2018
Esther Duflo, Michael Greenstone, Rohini Pande, Nicholas Ryan
摘要
High pollution persists in many developing countries despite strict environmental rules.We use a field experiment and a structural model to study how plant emission standards are enforced.In collaboration with an Indian environmental regulator, we experimentally doubled the rate of inspection for treatment plants and required that the extra inspections be assigned randomly.We find that treatment plants only slightly increased compliance.We hypothesize that this weak effect is due to poor targeting, since the random inspections in the treatment found fewer extreme violators than the regulator's own discretionary inspections.To unbundle the roles of extra inspections and the removal of discretion over what plants to target, we set out a model of environmental regulation where the regulator targets inspections, based on a signal of pollution, to maximize plant abatement.Using the experiment to identify key parameters of the model, we find that the regulator aggressively targets its discretionary inspections, to the degree that half of plants receive fewer than one inspection per year, while plants expected to be the dirtiest may receive ten.Counterfactual simulations show that discretion in targeting helps enforcement: inspections that the regulator assigns cause three times more abatement than would the same number of randomly-assigned inspections.Nonetheless, we find that the regulator's information on plant pollution is poor, and improvements in monitoring would reduce emissions. *(abstract via OpenAlex)*
Econometrica Causal Inference · 发表于 2018
Victor Chernozhukov, Iván Fernández-Val, Ye Luo
摘要
The partial (ceteris paribus) effects of interest in nonlinear and interactive linear models are heterogeneous as they can vary dramatically with the underlying observed or unobserved covariates. Despite the apparent importance of heterogeneity, a common practice in modern empirical work is to largely ignore it by reporting average partial effects (or, at best, average effects for some groups). While average effects provide very convenient scalar summaries of typical effects, by definition they fail to reflect the entire variety of the heterogeneous effects. In order to discover these effects much more fully, we propose to estimate and report sorted effects -- a collection of estimated partial effects sorted in increasing order and indexed by percentiles. By construction the sorted effect curves completely represent and help visualize the range of the heterogeneous effects in one plot. They are as convenient and easy to report in practice as the conventional average partial effects. They also serve as a basis for classification analysis, where we divide the observational units into most or least affected groups and summarize their characteristics. We provide a quantification of uncertainty (standard errors and confidence bands) for the estimated sorted effects and related classification analysis, and provide confidence sets for the most and least affected groups. The derived statistical results rely on establishing key, new mathematical results on Hadamard differentiability of a multivariate sorting operator and a related classification operator, which are of independent interest. We apply the sorted effects method and classification analysis to demonstrate several striking patterns in the gender wage gap. *(abstract via OpenAlex)*
JMLR Latent Variables & Mixtures · 发表于 2018
Avik Ray, Joe Neeman, Sujay Sanghavi, Sanjay Shakkottai
摘要
We consider the task of learning the parameters of a single component of a mixture model, for the case when we are given side information about that component; we call this the âsearch problem" in mixture models. We would like to solve this with computational and sample complexity lower than solving the overall original problem, where one learns parameters of all components. Our main contributions are the development of a simple but general model for the notion of side information, and a corresponding simple matrix-based algorithm for solving the search problem in this general setting. We then specialize this model and algorithm to four common scenarios: Gaussian mixture models, LDA topic models, subspace clustering, and mixed linear regression. For each one of these we show that if (and only if) the side information is informative, we obtain parameter estimates with greater accuracy, and also improved computation complexity than existing moment based mixture model algorithms (e.g. tensor methods). We also illustrate several natural ways one can obtain such side information, for specific problem instances. Our experiments on real data sets (NY Times, Yelp, BSDS500) further demonstrate the practicality of our algorithms showing significant improvement in runtime and accuracy.
JMLR Optimization & Learning Theory · 发表于 2018
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, Nathan Srebro
摘要
We examine gradient descent on unregularized logistic regression problems, with homogeneous linear predictors on linearly separable datasets. We show the predictor converges to the direction of the max-margin (hard margin SVM) solution. The result also generalizes to other monotone decreasing loss functions with an infimum at infinity, to multi-class problems, and to training a weight layer in a deep network in a certain restricted setting. Furthermore, we show this convergence is very slow, and only logarithmic in the convergence of the loss itself. This can help explain the benefit of continuing to optimize the logistic or cross-entropy loss even after the training error is zero and the training loss is extremely small, and, as we show, even if the validation loss increases. Our methodology can also aid in understanding implicit regularization in more complex models and with other optimization methods.
Econometrica Other · 发表于 2018
Georg Nöldeke, Larry Samuelson
摘要
Conjugate duality relationships are pervasive in matching and implementation problems and provide much of the structure essential for characterizing stable matches and implementable allocations in models with quasilinear (or transferable) utility. In the absence of quasilinearity, a more abstract duality relationship, known as a Galois connection, takes the role of (generalized) conjugate duality. While weaker, this duality relationship still induces substantial structure. We show that this structure can be used to extend existing results for, and gain new insights into, adverse-selection principal-agent problems and two-sided matching problems without quasilinearity. *(abstract via OpenAlex)*
Econometrica Econometrics & Economics · 发表于 2018
Melissa Dell, Nathan Lane, Pablo Querubin
摘要
This study examines how the historical state conditions long-run development, using Vietnam as a laboratory. Northern Vietnam (Dai Viet) was ruled by a strong centralized state in which the village was the fundamental administrative unit. Southern Vietnam was a peripheral tributary of the Khmer (Cambodian) Empire, which followed a patron-client model with weaker, more personalized power relations and no village intermediation. Using a regression discontinuity design across the Dai Viet-Khmer boundary, the study shows that areas historically under a strong state have higher living standards today and better economic outcomes over the past 150 years. Rich historical data document that in villages with a strong historical state, citizens have been better able to organize for public goods and redistribution through civil society and local government. This suggests that the strong historical state crowded in village-level collective action and that these norms persisted long after the original state disappeared. *(abstract via OpenAlex)*
Econometrica Econometrics & Economics · 发表于 2018
David C. Chan
摘要
Work schedules play an important role in utilizing labor in organizations.In this study of emergency department physicians in shift work, schedules induce two distortions: First, physicians "slack off" by accepting fewer patients near end of shift (EOS).Second, physicians distort patient care, incurring higher costs as they spend less time on patients accepted near EOS.Examining how these effects change with shift overlap reveals a tradeoff between the two.Within an hour after the normal time of work completion, physicians are willing to spend hospital resources eight times more than their market wage to preserve their leisure.Accounting for overall costs, I find that physicians slack off at approximately second-best optimal levels. *(abstract via OpenAlex)*
Econometrica Optimization & Learning Theory · 发表于 2018
Nicola Pavoni, Christopher Sleet, Matthias Messner
摘要
We bring together the theories of duality and dynamic programming. We show that the dual of a separable dynamic optimization problem can be recursively decomposed. We provide a dual version of the principle of optimality and give conditions under which the dual Bellman operator is a contraction with the optimal dual value function its unique fixed point. We relate primal and dual problems, address computational issues and give examples. *(abstract via OpenAlex)*
JMLR High-Dimensional Networks & Graphs · 发表于 2018
Oscar Hernan Madrid Padilla, James Sharpnack, James G. Scott, Ryan J. Tibshirani
摘要
The fused lasso, also known as (anisotropic) total variation denoising, is widely used for piecewise constant signal estimation with respect to a given undirected graph. The fused lasso estimate is highly nontrivial to compute when the underlying graph is large and has an arbitrary structure. But for a special graph structure, namely, the chain graph, the fused lasso---or simply, 1d fused lasso---can be computed in linear time. In this paper, we revisit a result recently established in the online classification literature (Herbster et al., 2009; Cesa-Bianchi et al., 2013) and show that it has important implications for signal denoising on graphs. The result can be translated to our setting as follows. Given a general graph, if we run the standard depth-first search (DFS) traversal algorithm, then the total variation of any signal over the chain graph induced by DFS is no more than twice its total variation over the original graph. This result leads to several interesting theoretical and computational conclusions. Letting $m$ and $n$ denote the number of edges and nodes, respectively, of the graph in consideration, it implies that for an underlying signal with total variation $t$ over the graph, the fused lasso (properly tuned) achieves a mean squared error rate of $t^{2/3} n^{-2/3}$. Moreover, precisely the same mean squared error rate is achieved by running the 1d fused lasso on the DFS-induced chain graph. Importantly, the latter estimator is simple and computationally cheap, requiring $O(m)$ operations to construct the DFS-induced chain and $O(n)$ operations to compute the 1d fused lasso solution over this chain. Further, for trees that have bounded maximum degree, the error rate of $t^{2/3} n^{-2/3}$ cannot be improved, in the sense that it is the minimax rate for signals that have total variation $t$ over the tree. Finally, several related results also hold---for example, the analogous result holds for a roughness measure defined by the $\ell_0$ norm of differences across edges in place of the total variation metric.
JMLR Networks & Graphs · 发表于 2018
David P. Helmbold, Philip M. Long
摘要
We analyze dropout in deep networks with rectified linear units and the quadratic loss. Our results expose surprising differences between the behavior of dropout and more traditional regularizers like weight decay. For example, on some simple data sets dropout training produces negative weights even though the output is the sum of the inputs. This provides a counterpoint to the suggestion that dropout discourages co-adaptation of weights. We also show that the dropout penalty can grow exponentially in the depth of the network while the weight-decay penalty remains essentially linear, and that dropout is insensitive to various re-scalings of the input features, outputs, and network weights. This last insensitivity implies that there are no isolated local minima of the dropout training criterion. Our work uncovers new properties of dropout, extends our understanding of why dropout succeeds, and lays the foundation for further progress.
Econometrica Other · 发表于 2018
Joshua B. Miller, Adam Sanjurjo
摘要
We prove that a subtle but substantial bias exists in a common measure of the conditional dependence of present outcomes on streaks of past outcomes in sequential data.The magnitude of this streak selection bias generally decreases as the sequence gets longer, but increases in streak length, and remains substantial for a range of sequence lengths often used in empirical work.We observe that the canonical study in the influential hot hand fallacy literature, along with replications, are vulnerable to the bias.Upon correcting for the bias, we find that the longstanding conclusions of the canonical study are reversed. KEYWORDS: Law of small *(abstract via OpenAlex)*
JMLR Other · 发表于 2018
Bruce Hajek, Yihong Wu, Jiaming Xu
摘要
The principal submatrix localization problem deals with recovering a $K\times K$ principal submatrix of elevated mean $\mu$ in a large $n\times n$ symmetric matrix subject to additive standard Gaussian noise, or more generally, mean zero, variance one, subgaussian noise. This problem serves as a prototypical example for community detection, in which the community corresponds to the support of the submatrix. The main result of this paper is that in the regime $\Omega(\sqrt{n}) \leq K \leq o(n)$, the support of the submatrix can be weakly recovered (with $o(K)$ misclassification errors on average) by an optimized message passing algorithm if $\lambda = \mu^2K^2/n$, the signal-to-noise ratio, exceeds $1/e$. This extends a result by Deshpande and Montanari previously obtained for $K=\Theta(\sqrt{n})$ and $\mu=\Theta(1).$ In addition, the algorithm can be combined with a voting procedure to achieve the information-theoretic limit of exact recovery with sharp constants for all $K \geq \frac{n}{\log n} (\frac{1}{8e} + o(1))$. The total running time of the algorithm is $O(n^2\log n)$. Another version of the submatrix localization problem, known as noisy biclustering, aims to recover a $K_1\times K_2$ submatrix of elevated mean $\mu$ in a large $n_1\times n_2$ Gaussian matrix. The optimized message passing algorithm and its analysis are adapted to the bicluster problem assuming $\Omega(\sqrt{n_i}) \leq K_i \leq o(n_i)$ and $K_1\asymp K_2.$ A sharp information-theoretic condition for the weak recovery of both clusters is also identified.
JMLR Nonparametric & Semiparametric · 发表于 2018
Audrey Durand, Odalric-Ambrym Maillard, Joelle Pineau
摘要
We consider the problem of streaming kernel regression, when the observations arrive sequentially and the goal is to recover the underlying mean function, assumed to belong to an RKHS. The variance of the noise is not assumed to be known. In this context, we tackle the problem of tuning the regularization parameter adaptively at each time step, while maintaining tight confidence bounds estimates on the value of the mean function at each point. To this end, we first generalize existing results for finite-dimensional linear regression with fixed regularization and known variance to the kernel setup with a regularization parameter allowed to be a measurable function of past observations. Then, using appropriate self-normalized inequalities we build upper and lower bound estimates for the variance, leading to Bernstein-like concentration bounds. The latter is used in order to define the adaptive regularization. The bounds resulting from our technique are valid uniformly over all observation points and all time steps, and are compared against the literature with numerical experiments. Finally, the potential of these tools is illustrated by an application to kernelized bandits, where we revisit the Kernel UCB and Kernel Thompson Sampling procedures, and show the benefits of the novel adaptive kernel tuning strategy.
JMLR Spatial & Time Series Networks & Graphs · 发表于 2018
Ali Zarezade, Abir De, Utkarsh Upadhyay, Hamid R. Rabiee, Manuel Gomez-Rodriguez
摘要
User engagement in online social networking depends critically on the level of social activity in the corresponding platform---the number of online actions, such as posts, shares or replies, taken by their users. Can we design data-driven algorithms to increase social activity? At a user level, such algorithms may increase activity by helping users decide when to take an action to be more likely to be noticed by their peers. At a network level, they may increase activity by incentivizing a few influential users to take more actions, which in turn will trigger additional actions by other users. In this paper, we model social activity using the framework of marked temporal point processes, derive an alternate representation of these processes using stochastic differential equations (SDEs) with jumps and, exploiting this alternate representation, develop two efficient online algorithms with provable guarantees to steer social activity both at a user and at a network level. In doing so, we establish a previously unexplored connection between optimal control of jump SDEs and doubly stochastic marked temporal point processes, which is of independent interest. Finally, we experiment both with synthetic and real data gathered from Twitter and show that our algorithms consistently steer social activity more effectively than the state of the art.
JMLR Networks & Graphs Survey & Sampling · 发表于 2018
Avanti Athreya, Donniell E. Fishkind, Minh Tang, Carey E. Priebe, Youngser Park, Joshua T. Vogelstein, Keith Levin, Vince Lyzinski, Yichen Qin, Daniel L Sussman
摘要
The random dot product graph (RDPG) is an independent-edge random graph that is analytically tractable and, simultaneously, either encompasses or can successfully approximate a wide range of random graphs, from relatively simple stochastic block models to complex latent position graphs. In this survey paper, we describe a comprehensive paradigm for statistical inference on random dot product graphs, a paradigm centered on spectral embeddings of adjacency and Laplacian matrices. We examine the graph-inferential analogues of several canonical tenets of classical Euclidean inference. In particular, we summarize a body of existing results on the consistency and asymptotic normality of the adjacency and Laplacian spectral embeddings, and the role these spectral embeddings can play in the construction of single- and multi-sample hypothesis tests for graph data. We investigate several real-world applications, including community detection and classification in large social networks and the determination of functional and biologically relevant network properties from an exploratory data analysis of the Drosophila connectome. We outline requisite background and current open problems in spectral graph inference.
JMLR Other · 发表于 2018
Mathieu Carrière, Bertrand Michel, Steve Oudot
摘要
In this article, we study the question of the statistical convergence of the 1-dimensional Mapper to its continuous analogue, the Reeb graph. We show that the Mapper is an optimal estimator of the Reeb graph, which gives, as a byproduct, a method to automatically tune its parameters and compute confidence regions on its topological features, such as its loops and flares. This allows to circumvent the issue of testing a large grid of parameters and keeping the most stable ones in the brute-force setting, which is widely used in visualization, clustering and feature selection with the Mapper.
JMLR Nonparametric & Semiparametric · 发表于 2018
Luc Lehéricy
摘要
In this paper, we introduce a new estimator for the emission densities of a nonparametric hidden Markov model. It is adaptive and minimax with respect to each state's regularity–as opposed to globally minimax estimators, which adapt to the worst regularity among the emission densities. Our method is based on Goldenshluger and Lepski's methodology. It is computationally efficient and only requires a family of preliminary estimators, without any restriction on the type of estimators considered. We present two such estimators that allow to reach minimax rates up to a logarithmic term: a spectral estimator and a least squares estimator. We show how to calibrate it in practice and assess its performance on simulations and on real data.
JMLR Networks & Graphs High-Dimensional Spatial & Time Series · 发表于 2018
Christian Borgs, Jennifer T. Chayes, Henry Cohn, Nina Holden
摘要
In a recent paper, Caron and Fox suggest a probabilistic model for sparse graphs which are exchangeable when associating each vertex with a time parameter in $\mathbb{R}_+$. Here we show that by generalizing the classical definition of graphons as functions over probability spaces to functions over $\sigma$-finite measure spaces, we can model a large family of exchangeable graphs, including the Caron-Fox graphs and the traditional exchangeable dense graphs as special cases. Explicitly, modelling the underlying space of features by a $\sigma$-finite measure space $(S,\mathcal{S},\mu)$ and the connection probabilities by an integrable function $W\colon S\times S\to [0,1]$, we construct a random family $(G_t)_{t\geq 0}$ of growing graphs such that the vertices of $G_t$ are given by a Poisson point process on $S$ with intensity $t\mu$, with two points $x,y$ of the point process connected with probability $W(x,y)$. We call such a random family a graphon process. We prove that a graphon process has convergent subgraph frequencies (with possibly infinite limits) and that, in the natural extension of the cut metric to our setting, the sequence converges to the generating graphon. We also show that the underlying graphon is identifiable only as an equivalence class over graphons with cut distance zero. More generally, we study metric convergence for arbitrary (not necessarily random) sequences of graphs, and show that a sequence of graphs has a convergent subsequence if and only if it has a subsequence satisfying a property we call uniform regularity of tails. Finally, we prove that every graphon is equivalent to a graphon on $\mathbb{R}_+$ equipped with Lebesgue measure.
JMLR High-Dimensional · 发表于 2018
Blazej Miasojedow, Wojciech Rejchel
摘要
We consider a model selection problem in high-dimensional binary Markov random fields. The usefulness of the Ising model in studying systems of complex interactions has been confirmed in many papers. The main drawback of this model is the intractable norming constant that makes estimation of parameters very challenging. In the paper we propose a Lasso penalized version of the Monte Carlo maximum likelihood method. We prove that our algorithm, under mild regularity conditions, recognizes the true dependence structure of the graph with high probability. The efficiency of the proposed method is also investigated via numerical studies.
JMLR High-Dimensional · 发表于 2018
Shuhan Liang, Wenbin Lu, Rui Song, Lan Wang
摘要
To find optimal decision rule, Fan et al. (2016) proposed an innovative concordance-assisted learning algorithm which is based on maximum rank correlation estimator. It makes better use of the available information through pairwise comparison. However the objective function is discontinuous and computationally hard to optimize. In this paper, we consider a convex surrogate loss function to solve this problem. In addition, our algorithm ensures sparsity of decision rule and renders easy interpretation. We derive the $L_2$ error bound of the estimated coefficients under ultra-high dimension. Simulation results of various settings and application to STAR*D both illustrate that the proposed method can still estimate optimal treatment regime successfully when the number of covariates is large.
Econometrica Other · 发表于 2018
Tangren Feng, Shaowei Ke
摘要
The most critical issue in evaluating policies and projects that affect generations of individuals is the choice of social discount rate. This paper shows that there exist social discount rates such that the planner can simultaneously be (i) an exponential discounting expected utility maximizer; (ii) intergenerationally Pareto—that is, if all individuals from all generations prefer one policy/project to another, the planner agrees; and (iii) strongly non-dictatorial—that is, no individual from any generation is ignored. Moreover, to satisfy (i)–(iii), if the time horizon is long enough, it is generically sufficient and necessary for social discounting to be more patient than the most patient individual’s long-run discounting, independent of the social risk attitude. *(abstract via OpenAlex)*
JMLR Optimization & Learning Theory · 发表于 2018
Shusen Wang, Alex Gittens, Michael W. Mahoney
摘要
We address the statistical and optimization impacts of the classical sketch and Hessian sketch used to approximately solve the Matrix Ridge Regression (MRR) problem. Prior research has quantified the effects of classical sketch on the strictly simpler least squares regression (LSR) problem. We establish that classical sketch has a similar effect upon the optimization properties of MRR as it does on those of LSR: namely, it recovers nearly optimal solutions. By contrast, Hessian sketch does not have this guarantee; instead, the approximation error is governed by a subtle interplay between the âmassâ in the responses and the optimal objective value. For both types of approximation, the regularization in the sketched MRR problem results in significantly different statistical properties from those of the sketched LSR problem. In particular, there is a bias-variance trade-off in sketched MRR that is not present in sketched LSR. We provide upper and lower bounds on the bias and variance of sketched MRR; these bounds show that classical sketch significantly increases the variance, while Hessian sketch significantly increases the bias. Empirically, sketched MRR solutions can have risks that are higher by an order-of- magnitude than those of the optimal MRR solutions. We establish theoretically and empirically that model averaging greatly decreases the gap between the risks of the true and sketched solutions to the MRR problem. Thus, in parallel or distributed settings, sketching combined with model averaging is a powerful technique that quickly obtains near-optimal solutions to the MRR problem while greatly mitigating the increased statistical risk incurred by sketching.
JMLR Networks & Graphs High-Dimensional Latent Variables & Mixtures · 发表于 2018
Botao Hao, Will Wei Sun, Yufeng Liu, Guang Cheng
摘要
We consider joint estimation of multiple graphical models arising from heterogeneous and high-dimensional observations. Unlike most previous approaches which assume that the cluster structure is given in advance, an appealing feature of our method is to learn cluster structure while estimating heterogeneous graphical models. This is achieved via a high dimensional version of Expectation Conditional Maximization (ECM) algorithm (Meng and Rubin, 1993). A joint graphical lasso penalty is imposed on the conditional maximization step to extract both homogeneity and heterogeneity components across all clusters. Our algorithm is computationally efficient due to fast sparse learning routines and can be implemented without unsupervised learning knowledge. The superior performance of our method is demonstrated by extensive experiments and its application to a Glioblastoma cancer dataset reveals some new insights in understanding the Glioblastoma cancer. In theory, a non-asymptotic error bound is established for the output directly from our high dimensional ECM algorithm, and it consists of two quantities: statistical error (statistical accuracy) and optimization error (computational complexity). Such a result gives a theoretical guideline in terminating our ECM iterations.
JMLR Other · 发表于 2018
Nihar B. Shah, Martin J. Wainwright
摘要
We consider data in the form of pairwise comparisons of $n$ items, with the goal of identifying the top $k$ items for some value of $k < n$, or alternatively, recovering a ranking of all the items. We analyze the Borda counting algorithm that ranks the items in order of the number of pairwise comparisons won, and show it has three attractive features: (a) it is an optimal method achieving the information-theoretic limits up to constant factors; (b) it is robust in that its optimality holds without imposing conditions on the underlying matrix of pairwise-comparison probabilities, in contrast to some prior work that applies only to the BTL parametric model; and (c) its computational efficiency leads to speed-ups of several orders of magnitude. We address the problem of exact recovery, and for the top-$k$ recovery problem we also extend our results to obtain sharp guarantees for approximate recovery under the Hamming distortion metric, and more generally, to any arbitrary error requirement that satisfies a simple and natural monotonicity condition. In doing so, we introduce a general framework that allows us to treat a variety of problems in the literature in an unified manner.
JMLR Other · 发表于 2018
Deanna Needell, Rayan Saab, Tina Woolf
摘要
Binary, or one-bit, representations of data arise naturally in many applications, and are appealing in both hardware implementations and algorithm design. In this work, we study the problem of data classification from binary data obtained from the sign pattern of low-dimensional projections and propose a framework with low computation and resource costs. We illustrate the utility of the proposed approach through stylized and realistic numerical experiments, and provide a theoretical analysis for a simple case. We hope that our framework and analysis will serve as a foundation for studying similar types of approaches.
JMLR Optimization & Learning Theory High-Dimensional Econometrics & Economics · 发表于 2018
Zhao-Rong Lai, Pei-Yi Yang, Liangda Fang, Xiaotian Wu
摘要
We propose a short-term sparse portfolio optimization (SSPO) system based on alternating direction method of multipliers (ADMM). Although some existing strategies have also exploited sparsity, they either constrain the quantity of the portfolio change or aim at the long-term portfolio optimization. Very few of them are dedicated to constructing sparse portfolios for the short-term portfolio optimization, which will be complemented by the proposed SSPO. SSPO concentrates wealth on a small proportion of assets that have good increasing potential according to some empirical financial principles, so as to maximize the cumulative wealth for the whole investment. We also propose a solving algorithm based on ADMM to handle the $\ell^1$-regularization term and the self-financing constraint simultaneously. As a significant improvement in the proposed ADMM, we have proven that its augmented Lagrangian has a saddle point, which is the foundation of the iterative formulae of ADMM but is seldom addressed by other sparsity strategies. Extensive experiments on $5$ benchmark data sets from real-world stock markets show that SSPO outperforms other state-of-the-art systems in thorough evaluations, withstands reasonable transaction costs and runs fast. Thus it is suitable for real-world financial environments.
JMLR Spatial & Time Series Machine Learning · 发表于 2018
David M. Burns, Cari M. Whyne
摘要
seglearn is an open-source Python package for performing machine learning on time series or sequences. The implementation provides a flexible pipeline for tackling classification, regression, and forecasting problems with multivariate sequence and contextual data. Sequences and series may be learned directly with deep learning models or via feature representation with classical machine learning estimators. This package is compatible with scikit-learn and is listed under scikit-learn Related Projects. The package depends on numpy, scipy, and scikit-learn. seglearn is distributed under the BSD 3-Clause License. Documentation includes a detailed API description, user guide, and examples. Unit tests provide a high degree of code coverage. Source code and documentation can be downloaded from https://github.com/dmbee/seglearn.
JMLR Other · 发表于 2018
Jacob Montiel, Jesse Read, Albert Bifet, Talel Abdessalem
摘要
scikit-multiflow is a framework for learning from data streams and multi-output learning in Python. Conceived to serve as a platform to encourage the democratization of stream learning research, it provides multiple state-of-the-art learning methods, data generators and evaluators for different stream learning problems, including single-output, multi-output and multi-label. scikit-multiflow builds upon popular open source frameworks including scikit-learn, MOA and MEKA. Development follows the FOSS principles. Quality is enforced by complying with PEP8 guidelines, using continuous integration and functional testing.
JMLR Bayesian Methods Diagnostics & Prediction · 发表于 2018
Leo L. Duan, James E. Johndrow, David B. Dunson
摘要
There has been considerable interest in making Bayesian inference more scalable. In big data settings, most of the focus has been on reducing the computing time per iteration rather than reducing the number of iterations needed in Markov chain Monte Carlo (MCMC). This article considers data augmentation MCMC (DA-MCMC), a widely used technique. DA-MCMC samples tend to become highly autocorrelated in large samples, due to a mis-calibration problem in which conditional posterior distributions given augmented data are too concentrated. This makes it necessary to collect very long MCMC paths to obtain acceptably low MC error. To combat this inefficiency, we propose a family of calibrated data augmentation algorithms, which appropriately adjust the variance of conditional posterior distributions. A Metropolis-Hastings step is used to eliminate bias in the stationary distribution of the resulting sampler. Compared to existing alternatives, this approach can dramatically reduce MC error by reducing autocorrelation and increasing the effective number of DA-MCMC samples per unit of computing time. The approach is simple and applicable to a broad variety of existing data augmentation algorithms. We focus on three popular generalized linear models: probit, logistic and Poisson log-linear. Dramatic gains in computational efficiency are shown in applications.