2018 年的期刊文章 · 第 31 页

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

按期刊、按主题看 →

第 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 32 33 页

JMLR Other · 发表于 2018

In Search of Coherence and Consensus: Measuring the Interpretability of Statistical Topics

Fred Morstatter, Huan Liu

摘要

Topic modeling is an important tool in natural language processing. Topic models provide two forms of output. The first is a predictive model. This type of model has the ability to predict unseen documents (e.g., their categories). When topic models are used in this way, there are ample measures to assess their performance. The second output of these models is the topics themselves. Topics are lists of keywords that describe the top words pertaining to each topic. Often, these lists of keywords are presented to a human subject who then assesses the meaning of the topic, which is ultimately subjective. One of the fundamental problems of topic models lies in assessing the quality of the topics from the perspective of human interpretability. Naturally, human subjects need to be employed to evaluate interpretability of a topic. Lately, crowdsourcing approaches are widely used to serve the role of human subjects in evaluation. In this work we study measures of interpretability and propose to measure topic interpretability from two perspectives: topic coherence and topic consensus. We start with an existing measure for topic coherence---model precision. It evaluates coherence of a topic by introducing an intruded word and measuring how well a human subject or a crowdsourcing approach could identify the intruded word: if it is easy to identify, the topic is coherent. We then investigate how we can measure coherence comprehensively by examining dimensions of topic coherence. For the second perspective of topic interpretability, we suggest topic consensus that measures how well the results of a crowdsourcing approach matches those given categories of topics. Good topics should lead to good categories, thus, high topic consensus. Therefore, if there is low topic consensus in terms of categories, topics could be of low interpretability. We then further discuss how topic coherence and topic consensus assess different aspects of topic interpretability and hope that this work can pave way for comprehensive measures of topic interpretability.

JMLR Networks & Graphs · 发表于 2018

Improved spectral community detection in large heterogeneous networks

Hafiz TIOMOKO ALI, Romain COUILLET

摘要

In this article, we propose and study the performance of spectral community detection for a family of “$\alpha$-normalized” adjacency matrices $\bf A$, of the type $ {\bf D}^{-\alpha}{\bf A}{\bf D}^{-\alpha}$ with $\bf D$ the degree matrix, in heterogeneous dense graph models. We show that the previously used normalization methods based on ${\bf A}$ or $ {\bf D}^{-1}{\bf A}{\bf D}^{-1} $ are in general suboptimal in terms of correct recovery rates and, relying on advanced random matrix methods, we prove instead the existence of an optimal value $ \alpha_{\rm opt} $ of the parameter $ \alpha $ in our generic model; we further provide an online estimation of $ \alpha_{\rm opt} $ only based on the node degrees in the graph. Numerical simulations show that the proposed method outperforms state-of-the-art spectral approaches on moderately dense to dense heterogeneous graphs.

JMLR Optimization & Learning Theory · 发表于 2018

Improved Asynchronous Parallel Optimization Analysis for Stochastic Incremental Methods

Remi Leblond, Fabian Pedregosa, Simon Lacoste-Julien

摘要

As data sets continue to increase in size and multi-core computer architectures are developed, asynchronous parallel optimization algorithms become more and more essential to the field of Machine Learning. Unfortunately, conducting the theoretical analysis asynchronous methods is difficult, notably due to the introduction of delay and inconsistency in inherently sequential algorithms. Handling these issues often requires resorting to simplifying but unrealistic assumptions. Through a novel perspective, we revisit and clarify a subtle but important technical issue present in a large fraction of the recent convergence rate proofs for asynchronous parallel optimization algorithms, and propose a simplification of the recently introduced “perturbed iterate” framework that resolves it. We demonstrate the usefulness of our new framework by analyzing three distinct asynchronous parallel incremental optimization algorithms: Hogwild (asynchronous SGD), KROMAGNON (asynchronous SVRG) and ASAGA, a novel asynchronous parallel version of the incremental gradient algorithm SAGA that enjoys fast linear convergence rates. We are able to both remove problematic assumptions and obtain better theoretical results. Notably, we prove that ASAGA and KROMAGNON can obtain a theoretical linear speedup on multi-core systems even without sparsity assumptions. We present results of an implementation on a 40-core architecture illustrating the practical speedups as well as the hardware overhead. Finally, we investigate the overlap constant, an ill-understood but central quantity for the theoretical analysis of asynchronous parallel algorithms. We find that it encompasses much more complexity than suggested in previous work, and often is order-of-magnitude bigger than traditionally thought.

JMLR Other · 发表于 2018

Importance Sampling for Minibatches

Dominik Csiba, Peter Richtárik

摘要

Minibatching is a very well studied and highly popular technique in supervised learning, used by practitioners due to its ability to accelerate training through better utilization of parallel processing power and reduction of stochastic variance. Another popular technique is importance sampling–a strategy for preferential sampling of more important examples also capable of accelerating the training process. However, despite considerable effort by the community in these areas, and due to the inherent technical difficulty of the problem, there is virtually no existing work combining the power of importance sampling with the strength of minibatching. In this paper we propose the first practical importance sampling for minibatches and give simple and rigorous complexity analysis of its performance. We illustrate on synthetic problems that for training data of certain properties, our sampling can lead to several orders of magnitude improvement in training time. We then test the new sampling on several popular data sets, and show that the improvement can reach an order of magnitude.

Econometrica Networks & Graphs · 发表于 2018

Identifying Preferences in Networks With Bounded Degree

Áureo Paula, Seth Richards-Shubik, Elie Tamer

摘要

This paper provides a framework for identifying preferences in a large network where links are pairwise stable. Network formation models present difficulties for identification, especially when links can be interdependent, for example, when indirect connections matter. We show how one can use the observed proportions of various local network structures to learn about the underlying preference parameters. The key assumption for our approach restricts individuals to have bounded degree in equilibrium, implying a finite number of payoff‐relevant local structures. Our main result provides necessary conditions for parameters to belong to the identified set. We then develop a quadratic programming algorithm that can be used to construct this set. With further restrictions on preferences, we show that our conditions are also sufficient for pairwise stability and therefore characterize the identified set precisely. Overall, the use of both the economic model along with pairwise stability allows us to obtain effective dimension reduction. *(abstract via OpenAlex)*

Econometrica Bayesian Methods Spatial & Time Series · 发表于 2018

Identifying Long-Run Risks: A Bayesian Mixed-Frequency Approach

Frank Schorfheide, Dongho Song, Amir Yaron

摘要

We develop a nonlinear state-space model that captures the joint dynamics of consumption, dividend growth, and asset returns. Building on Bansal and Yaron (2004), our model consists of an economy containing a common predictable component for consumption and dividend growth and multiple stochastic volatility processes. The estimation is based on annual consumption data from 1929 to 1959, monthly consumption data after 1959, and monthly asset return data throughout. We maximize the span of the sample to recover the predictable component and use high-frequency data, whenever available, to efficiently identify the volatility processes. Our Bayesian estimation provides strong evidence for a small predictable component in consumption growth (even if asset return data are omitted from the estimation). Three independent volatility processes capture different frequency dynamics; our measurement error specification implies that consumption is measured much more precisely at an annual than monthly frequency; and the estimated model is able to capture key asset-pricing facts of the data. *(abstract via OpenAlex)*

Econometrica Other · 发表于 2018

Identifying Effects of Multivalued Treatments

Sokbae Lee, Bernard Salanié

摘要

Multivalued treatment models have only been studied so far under restrictive assumptions: ordered choice, or more recently unordered monotonicity. We show how marginal treatment effects can be identified in a more general class of models. Our results rely on two main assumptions: treatment assignment must be a measurable function of threshold-crossing rules; and enough continuous instruments must be available. On the other hand, we do not require any kind of monotonicity condition. We illustrate our approach on several commonly used models; and we also discuss the identification power of discrete instruments. *(abstract via OpenAlex)*

Econometrica Causal Inference · 发表于 2018

Identification of Treatment Effects Under Conditional Partial Independence

Matthew A. Masten, Alexandre Poirier

摘要

Conditional independence of treatment assignment from potential outcomes is a commonly used but nonrefutable assumption.We derive identified sets for various treatment effect parameters under nonparametric deviations from this conditional independence assumption.These deviations are defined via a conditional treatment assignment probability, which makes it straightforward to interpret.Our results can be used to assess the robustness of empirical conclusions obtained under the baseline conditional independence assumption. *(abstract via OpenAlex)*

Econometrica Nonparametric & Semiparametric · 发表于 2018

Identification of Nonparametric Simultaneous Equations Models With a Residual Index Structure

Steven T. Berry, Philip A. Haile

摘要

We present new identification results for a class of nonseparable nonparametric simultaneous equations models introduced by Matzkin (2008). These models combine traditional exclusion restrictions with a requirement that each structural error enter through a “residual index.” Our identification results are constructive and encompass a range of special cases with varying demands on the exogenous variation provided by instruments and the shape of the joint density of the structural errors. The most important of these results demonstrate identification even when instruments have limited variation. A genericity result demonstrates a formal sense in which the associated density conditions may be viewed as mild, even when instruments vary only over a small open ball. *(abstract via OpenAlex)*

JMLR Optimization & Learning Theory Bayesian Methods · 发表于 2018

Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization

Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, Ameet Talwalkar

摘要

Performance of machine learning algorithms depends critically on identifying a good set of hyperparameters. While recent approaches use Bayesian optimization to adaptively select configurations, we focus on speeding up random search through adaptive resource allocation and early-stopping. We formulate hyperparameter optimization as a pure-exploration non-stochastic infinite-armed bandit problem where a predefined resource like iterations, data samples, or features is allocated to randomly sampled configurations. We introduce a novel algorithm, øuralg , for this framework and analyze its theoretical properties, providing several desirable guarantees. Furthermore, we compare øuralg with popular Bayesian optimization methods on a suite of hyperparameter optimization problems. We observe that øuralg can provide over an order-of-magnitude speedup over our competitor set on a variety of deep-learning and kernel-based learning problems.

JMLR High-Dimensional · 发表于 2018

HyperTools: a Python Toolbox for Gaining Geometric Insights into High-Dimensional Data

Andrew C. Heusser, Kirsten Ziman, Lucy L. W. Owen, Jeremy R. Manning

摘要

Dimensionality reduction algorithms have played a foundational role in facilitating the deep understanding of complex high- dimensional data. One particularly useful application of dimensionality reduction techniques is in data visualization. Low-dimensional visualizations can help practitioners understand where machine learning algorithms might leverage the geometric properties of a dataset to improve performance. Another challenge is to generalize insights across datasets [e.g. data from multiple modalities describing the same system (Haxby et al., 2011), artwork or photographs of similar content in different styles (Zhu et al., 2017), etc.]. Several recently developed techniques(e.g. Haxby et al., 2011; Chen et al., 2015) use the procrustean transformation (Schonemann, 1966) to align the geometries of two or more spaces so that data with different axes may be plotted in a common space. We propose that each of these techniques (dimensionality reduction, alignment, and visualization) applied in sequence should be cast as a single conceptual hyperplot operation for gaining geometric insights into high-dimensional data. Our Python toolbox enables this operation in a single (highly flexible) function call.

JMLR Other · 发表于 2018

How Deep Are Deep Gaussian Processes?

Matthew M. Dunlop, Mark A. Girolami, Andrew M. Stuart, Aretha L. Teckentrup

摘要

Recent research has shown the potential utility of deep Gaussian processes. These deep structures are probability distributions, designed through hierarchical construction, which are conditionally Gaussian. In this paper, the current published body of work is placed in a common framework and, through recursion, several classes of deep Gaussian processes are defined. The resulting samples generated from a deep Gaussian process have a Markovian structure with respect to the depth parameter, and the effective depth of the resulting process is interpreted in terms of the ergodicity, or non-ergodicity, of the resulting Markov chain. For the classes of deep Gaussian processes introduced, we provide results concerning their ergodicity and hence their effective depth. We also demonstrate how these processes may be used for inference; in particular we show how a Metropolis-within-Gibbs construction across the levels of the hierarchy can be used to derive sampling tools which are robust to the level of resolution used to represent the functions on a computer. For illustration, we consider the effect of ergodicity in some simple numerical examples.

JMLR Other · 发表于 2018

Hinge-Minimax Learner for the Ensemble of Hyperplanes

Dolev Raviv, Tamir Hazan, Margarita Osadchy

摘要

In this work we consider non-linear classifiers that comprise intersections of hyperplanes. We learn these classifiers by minimizing the “minimax” bound over the negative training examples and the hinge type loss of the positive training examples. These classifiers fit typical real-life datasets that consist of a small number of positive data points and a large number of negative data points. Such an approach is computationally appealing since the majority of training examples (belonging to the negative class) are represented by the statistics of their distribution, which is used in a single constraint on the empirical risk, as opposed to SVM, in which the number of variables is equal to the size of the training set. We first focus on intersection of $K$ hyperplanes, for which we provide empirical risk bounds. We show that these bounds are dimensionally independent and decay as $K/\sqrt{m}$ for $m$ samples. We then extend the K-hyperplane mixed risk to the latent mixed risk for training a union of $C$ $K$-hyperplane models, which can form an arbitrary complex, piecewise linear boundaries. We propose efficient algorithms for training the proposed models. Finally, we show how to combine hinge-minimax training with deep architectures and extend it to multi-class settings using transfer learning. The empirical evaluation of the proposed models shows their advantage over the existing methods in a small training labeled data regime.

JMLR Other · 发表于 2018

Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery

Christian Kümmerle, Juliane Sigl

摘要

We propose a new iteratively reweighted least squares (IRLS) algorithm for the recovery of a matrix $X \in \mathbb{C}^{d_1\times d_2}$ of rank $r \ll\min(d_1,d_2)$ from incomplete linear observations, solving a sequence of low complexity linear problems. The easily implementable algorithm, which we call harmonic mean iteratively reweighted least squares (HM-IRLS), optimizes a non-convex Schatten-$p$ quasi-norm penalization to promote low-rankness and carries three major strengths, in particular for the matrix completion setting. First, we observe a remarkable {global convergence behavior} of the algorithm's iterates to the low-rank matrix for relevant, interesting cases, for which any other state-of-the-art optimization approach fails the recovery. Secondly, HM-IRLS exhibits an empirical recovery probability close to $1$ even for a number of measurements very close to the theoretical lower bound $r (d_1 +d_2 -r)$, i.e., already for significantly fewer linear observations than any other tractable approach in the literature. Thirdly, HM-IRLS exhibits a locally superlinear rate of convergence (of order $2-p$) if the linear observations fulfill a suitable null space property. While for the first two properties we have so far only strong empirical evidence, we prove the third property as our main theoretical result.

Econometrica Econometrics & Economics · 发表于 2018

Growth, Trade, and Inequality

Gene M. Grossman, Elhanan Helpman

摘要

We introduce …rm and worker heterogeneity into a model of innovation-driven endogenous growth.Individuals who di¤er in ability sort into either a research sector or a manufacturing sector that produces di¤erentiated goods.Each research project generates a new variety of the di¤erentiated product and a random technology for producing it.Technologies di¤er in complexity and productivity, and technological sophistication is complementary to worker ability.We study the co-determination of growth and income inequality in both the closed and open economy, as well as the spillover e¤ects of policy and conditions in one country to outcomes in others. *(abstract via OpenAlex)*

JMLR High-Dimensional · 发表于 2018

Gradient Hard Thresholding Pursuit

Xiao-Tong Yuan, Ping Li, Tong Zhang

摘要

Hard Thresholding Pursuit (HTP) is an iterative greedy selection procedure for finding sparse solutions of underdetermined linear systems. This method has been shown to have strong theoretical guarantee and impressive numerical performance. In this article, we generalize HTP from compressed sensing to a generic problem setup of sparsity-constrained convex optimization. The proposed algorithm iterates between a standard gradient descent step and a hard-thresholding step with or without debiasing. We analyze the parameter estimation and sparsity recovery performance of the proposed method. Extensive numerical results confirm our theoretical predictions and demonstrate the superiority of our method to the state-of-the-art greedy selection methods in sparse linear regression, sparse logistic regression and sparse precision matrix estimation problems.\footnote{A conference version of this work appeared in ICML 2014 \citep{Yuan- ICML-2014}.}

JMLR High-Dimensional · 发表于 2018

Gradient Estimation with Simultaneous Perturbation and Compressive Sensing

Vivek S. Borkar, Vikranth R. Dwaracherla, Neeraja Sahasrabudhe

摘要

We propose a scheme for finding a "good" estimator for the gradient of a function on a high-dimensional space with few function evaluations, for applications where function evaluations are expensive and the function under consideration is not sensitive in all coordinates locally, making its gradient almost sparse. Exploiting the latter aspect, our method combines ideas from Spall's Simultaneous Perturbation Stochastic Approximation with compressive sensing. We theoretically justify its computational advantages and illustrate them empirically by numerical experiments. In particular, applications to estimating gradient outer product matrix as well as standard optimization problems are illustrated via simulations.

JMLR Optimization & Learning Theory · 发表于 2018

Gradient Descent Learns Linear Dynamical Systems

Moritz Hardt, Tengyu Ma, Benjamin Recht

摘要

We prove that stochastic gradient descent efficiently converges to the global optimizer of the maximum likelihood objective of an unknown linear time-invariant dynamical system from a sequence of noisy observations generated by the system. Even though the objective function is non-convex, we provide polynomial running time and sample complexity bounds under strong but natural assumptions. Linear systems identification has been studied for many decades, yet, to the best of our knowledge, these are the first polynomial guarantees for the problem we consider.

JMLR Other · 发表于 2018

Goodness-of-Fit Tests for Random Partitions via Symmetric Polynomials

Chao Gao

摘要

We consider goodness-of-fit tests with i.i.d. samples generated from a categorical distribution $(p_1,...,p_k)$. For a given $(q_1,...,q_k)$, we test the null hypothesis whether $p_j=q_{\pi(j)}$ for some label permutation $\pi$. The uncertainty of label permutation implies that the null hypothesis is composite instead of being singular. In this paper, we construct a testing procedure using statistics that are defined as indefinite integrals of some symmetric polynomials. This method is aimed directly at the invariance of the problem, and avoids the need of matching the unknown labels. The asymptotic distribution of the testing statistic is shown to be chi-squared, and its power is proved to be nearly optimal under a local alternative hypothesis. Various degenerate structures of the null hypothesis are carefully analyzed in the paper. A two-sample version of the test is also studied.

JMLR Other · 发表于 2018

Generalized Rank-Breaking: Computational and Statistical Tradeoffs

Ashish Khetan, Sewoong Oh

摘要

For massive and heterogeneous modern datasets, it is of fundamental interest to provide guarantees on the accuracy of estimation when computational resources are limited. In the application of rank aggregation, for the Plackett-Luce model, we provide a hierarchy of rank-breaking mechanisms ordered by the complexity in thus generated sketch of the data. This allows the number of data points collected to be gracefully traded off against computational resources available, while guaranteeing the desired level of accuracy. Theoretical guarantees on the proposed generalized rank-breaking implicitly provide such trade-offs, which can be explicitly characterized under certain canonical scenarios on the structure of the data. Further, the proposed generalized rank-breaking algorithm involves set-wise comparisons as opposed to traditional pairwise comparisons. The maximum likelihood estimate of pairwise comparisons is computed efficiently using the celebrated minorization maximization algorithm (Hunter, 2004). To compute the pseudo-maximum likelihood estimate of the set-wise comparisons, we provide a generalization of the minorization maximization algorithm and give guarantees on its convergence.

Econometrica Econometrics & Economics · 发表于 2018

General Equilibrium With Uncertainty Loving Preferences

Aloisio Araujo, Alain Chateauneuf, Juan Pablo Gama, Rodrigo Novinski

摘要

More and more economists are finding both empirical and experimental evidence of economic behavior that is well beyond classical economics. In particular, empirical evidence ( Jullien and Salanié (2000)) and experimental evidence ( Kahneman and Tversky (1979)) supported the importance of risk loving, ambiguity loving, and related behavior in economics. However, these types of preferences have not been analyzed in the general equilibrium literature with a finite number of agents because non-convexity of preferences creates difficulty in proving existence of equilibrium. The main result in this paper provides a set of conditions under which equilibrium exists in such economies.We show that uncertainty of aggregate wealth, as well as some dominance of the endowment of the risk averters in the economy, play a role in the existence of Arrow–Debreu equilibria. This result can be extended to ambiguity in the sense of CEU, Smooth Ambiguity, and Variational Preference. *(abstract via OpenAlex)*

JMLR Other · 发表于 2018

Gaussian Lower Bound for the Information Bottleneck Limit

Amichai Painsky, Naftali Tishby

摘要

The Information Bottleneck (IB) is a conceptual method for extracting the most compact, yet informative, representation of a set of variables, with respect to the target. It generalizes the notion of minimal sufficient statistics from classical parametric statistics to a broader information-theoretic sense. The IB curve defines the optimal trade-off between representation complexity and its predictive power. Specifically, it is achieved by minimizing the level of mutual information (MI) between the representation and the original variables, subject to a minimal level of MI between the representation and the target. This problem is shown to be in general NP hard. One important exception is the multivariate Gaussian case, for which the Gaussian IB (GIB) is known to obtain an analytical closed form solution, similar to Canonical Correlation Analysis (CCA). In this work we introduce a Gaussian lower bound to the IB curve; we find an embedding of the data which maximizes its “Gaussian part", on which we apply the GIB. This embedding provides an efficient (and practical) representation of any arbitrary data-set (in the IB sense), which in addition holds the favorable properties of a Gaussian distribution. Importantly, we show that the optimal Gaussian embedding is bounded from above by non-linear CCA. This allows a fundamental limit for our ability to Gaussianize arbitrary data- sets and solve complex problems by linear methods.

JMLR Missing Data & Measurement Error Optimization & Learning Theory · 发表于 2018

From Predictive Methods to Missing Data Imputation: An Optimization Approach

Dimitris Bertsimas, Colin Pawlowski, Ying Daisy Zhuo

摘要

Missing data is a common problem in real-world settings and for this reason has attracted significant attention in the statistical literature. We propose a flexible framework based on formal optimization to impute missing data with mixed continuous and categorical variables. This framework can readily incorporate various predictive models including $K$-nearest neighbors, support vector machines, and decision tree based methods, and can be adapted for multiple imputation. We derive fast first-order methods that obtain high quality solutions in seconds following a general imputation algorithm opt.impute presented in this paper. We demonstrate that our proposed method improves out-of-sample accuracy in large-scale computational experiments across a sample of 84 data sets taken from the UCI Machine Learning Repository. In all scenarios of missing at random mechanisms and various missing percentages, opt.impute produces the best overall imputation in most data sets benchmarked against five other methods: mean impute, $K$-nearest neighbors, iterative knn, Bayesian PCA, and predictive-mean matching, with an average reduction in mean absolute error of 8.3$\%$ against the best cross-validated benchmark method. Moreover, opt.impute leads to improved out-of-sample performance of learning algorithms trained using the imputed data, demonstrated by computational experiments on 10 downstream tasks. For models trained using opt.impute single imputations with 50$\%$ data missing, the average out-of- sample $R^2$ is 0.339 in the regression tasks and the average out-of-sample accuracy is 86.1$\%$ in the classification tasks, compared to 0.315 and 84.4$\%$ for the best cross-validated benchmark method. In the multiple imputation setting, downstream models trained using opt.impute obtain a statistically significant improvement over models trained using multivariate imputation by chained equations (mice) in 8/10 missing data scenarios considered.

JMLR Bayesian Methods · 发表于 2018

Fast MCMC Sampling Algorithms on Polytopes

Yuansi Chen, Raaz Dwivedi, Martin J. Wainwright, Bin Yu

摘要

We propose and analyze two new MCMC sampling algorithms, the Vaidya walk and the John walk, for generating samples from the uniform distribution over a polytope. Both random walks are sampling algorithms derived from interior point methods. The former is based on volumetric-logarithmic barrier introduced by Vaidya whereas the latter uses John's ellipsoids. We show that the Vaidya walk mixes in significantly fewer steps than the logarithmic-barrier based Dikin walk studied in past work. For a polytope in $\mathbb{R}^d$ defined by $n > d$ linear constraints, we show that the mixing time from a warm start is bounded as $\mathcal{O}(n^{0.5}d^{1.5})$, compared to the $\mathcal{O}(nd)$ mixing time bound for the Dikin walk. The cost of each step of the Vaidya walk is of the same order as the Dikin walk, and at most twice as large in terms of constant pre-factors. For the John walk, we prove an $\mathcal{O}(d^{2.5}\cdot\log^4(n/d))$ bound on its mixing time and conjecture that an improved variant of it could achieve a mixing time of $\mathcal{O}(d^{2}\cdot\text{poly-log}(n/d))$. Additionally, we propose variants of the Vaidya and John walks that mix in polynomial time from a deterministic starting point. The speed-up of the Vaidya walk over the Dikin walk are illustrated in numerical examples.

JMLR Other · 发表于 2018

Extrapolating Expected Accuracies for Large Multi-Class Problems

Charles Zheng, Rakesh Achanta, Yuval Benjamini

摘要

The difficulty of multi-class classification generally increases with the number of classes. Using data for a small set of the classes, can we predict how well the classifier scales as the number of classes increases? We propose a framework for studying this question, assuming that classes in both sets are sampled from the same population and that the classifier is based on independently learned scoring functions. Under this framework, we can express the classification accuracy on a set of $k$ classes as the $(k - 1)$st moment of a discriminability function; the discriminability function itself does not depend on $k$. We leverage this result to develop a non-parametric regression estimator for the discriminability function, which can extrapolate accuracy results to larger unobserved sets. We also formalize an alternative approach that extrapolates accuracy separately for each class, and identify tradeoffs between the two methods. We show that both methods can accurately predict classifier performance on label sets up to ten times the size of the original set, both in simulations as well as in realistic face recognition or character recognition tasks.

Econometrica Other · 发表于 2018

Expressive Voting and Its Cost: Evidence From Runoffs With Two or Three Candidates

Vincent Pons, Clémence Tricaud

摘要

In French parliamentary and local elections, candidates ranked first and second in the first round automatically qualify for the second round, while a third candidate qualifies only when selected by more than 12.5 percent of registered citizens. Using a fuzzy RDD around this threshold, we find that the third candidate’s presence substantially increases the share of registered citizens who vote for any candidate and reduces the vote share of the top two candidates. It disproportionately harms the candidate ideologically closest to the third and causes her defeat in one fifth of the races. Additional evidence suggests that these results are driven by voters who value voting expressively over voting strategically for the top-two candidate they dislike the least to ensure her victory; and by third candidates who, absent party-level agreements leading to their dropping out, value the benefits associated with competing in the second round more than influencing its outcome. *(abstract via OpenAlex)*

JMLR Machine Learning · 发表于 2018

Experience Selection in Deep Reinforcement Learning for Control

Tim de Bruin, Jens Kober, Karl Tuyls, Robert Babuška

摘要

Experience replay is a technique that allows off-policy reinforcement-learning methods to reuse past experiences. The stability and speed of convergence of reinforcement learning, as well as the eventual performance of the learned policy, are strongly dependent on the experiences being replayed. Which experiences are replayed depends on two important choices. The first is which and how many experiences to retain in the experience replay buffer. The second choice is how to sample the experiences that are to be replayed from that buffer. We propose new methods for the combined problem of experience retention and experience sampling. We refer to the combination as experience selection. We focus our investigation specifically on the control of physical systems, such as robots, where exploration is costly. To determine which experiences to keep and which to replay, we investigate different proxies for their immediate and long-term utility. These proxies include age, temporal difference error and the strength of the applied exploration noise. Since no currently available method works in all situations, we propose guidelines for using prior knowledge about the characteristics of the control problem at hand to choose the appropriate experience replay strategy.

JMLR Other · 发表于 2018

Exact Learning of Lightweight Description Logic Ontologies

Boris Konev, Carsten Lutz, Ana Ozaki, Frank Wolter

摘要

We study the problem of learning description logic (DL) ontologies in Angluin et al.'s framework of exact learning via queries. We admit membership queries (“is a given subsumption entailed by the target ontology?”) and equivalence queries (“is a given ontology equivalent to the target ontology?”). We present three main results: (1) ontologies formulated in (two relevant versions of) the description logic DL-Lite can be learned with polynomially many queries of polynomial size; (2) this is not the case for ontologies formulated in the description logic $\mathcal{E}\mathcal{L}$, even when only acyclic ontologies are admitted; and (3) ontologies formulated in a fragment of $\mathcal{E}\mathcal{L}$ related to the web ontology language OWL 2 RL can be learned in polynomial time. We also show that neither membership nor equivalence queries alone are sufficient in cases (1) and (3).

JMLR High-Dimensional Networks & Graphs Optimization & Learning Theory · 发表于 2018

Estimation of Graphical Models through Structured Norm Minimization

Davoud Ataee Tarzanagh, George Michailidis

摘要

Estimation of Markov Random Field and covariance models from high-dimensional data represents a canonical problem that has received a lot of attention in the literature. A key assumption, widely employed, is that of sparsity of the underlying model. In this paper, we study the problem of estimating such models exhibiting a more intricate structure comprising simultaneously of sparse, structured sparse and dense components. Such structures naturally arise in several scientific fields, including molecular biology, finance and political science. We introduce a general framework based on a novel structured norm that enables us to estimate such complex structures from high-dimensional data. The resulting optimization problem is convex and we introduce a linearized multi-block alternating direction method of multipliers (ADMM) algorithm to solve it efficiently. We illustrate the superior performance of the proposed framework on a number of synthetic data sets generated from both random and structured networks. Further, we apply the method to a number of real data sets and discuss the results.

Econometrica Other · 发表于 2018

Estimating Semi-Parametric Panel Multinomial Choice Models Using Cyclic Monotonicity

Xiaoxia Shi, Matthew Shum, Wei Song

摘要

This paper proposes a new semi‐parametric identification and estimation approach to multinomial choice models in a panel data setting with individual fixed effects. Our approach is based on cyclic monotonicity, which is a defining convex‐analytic feature of the random utility framework underlying multinomial choice models. From the cyclic monotonicity property, we derive identifying inequalities without requiring any shape restrictions for the distribution of the random utility shocks. These inequalities point identify model parameters under straightforward assumptions on the covariates. We propose a consistent estimator based on these inequalities. *(abstract via OpenAlex)*

Econometrica Econometrics & Economics · 发表于 2018

Estimating Both Supply and Demand Elasticities Using Variation in a Single Tax Rate

Floris T. Zoutman, Evelina Gavrilova, Arnt O. Hopland

摘要

We show how an insight from taxation theory allows identification of both the supply and demand elasticities using only one instrument. Most models of taxation since Ramsey (1927) assume that a tax levied on the demand side only affects demand through the price after taxation. Econometrically, we show that this assumption acts as an exclusion restriction. Under the Ramsey Exclusion Restriction (RER), a single tax reform can serve to simultaneously identify the demand and supply elasticity. We develop an estimation method, which includes 2SLS estimators for the elasticities, and a test for strength of the instrument. We discuss possible applications. *(abstract via OpenAlex)*

Econometrica Econometrics & Economics · 发表于 2018

Equilibrium Selection in Auctions and High Stakes Games

Paul Milgrom, Joshua Mollner

摘要

We introduce the test†set equilibrium refinement of Nash equilibrium to formalize the idea that players contemplate only deviations from equilibrium play in which a single competitor plays a non†equilibrium best response. We then apply this refinement to three well†known auction games, comparing our findings to similar ones previously obtained by specialized equilibrium selections. We also introduce a theory of high stakes versions of games, in which strategies are first proposed and then subjected to a potentially costly review†and†revise process. We demonstrate a sense in which the test†set equilibria emerge from such processes when the cost of revision is small. *(abstract via OpenAlex)*

JMLR Causal Inference · 发表于 2018

Enhancing Identification of Causal Effects by Pruning

Santtu Tikka, Juha Karvanen

摘要

Causal models communicate our assumptions about causes and effects in real-world phenomena. Often the interest lies in the identification of the effect of an action which means deriving an expression from the observed probability distribution for the interventional distribution resulting from the action. In many cases an identifiability algorithm may return a complicated expression that contains variables that are in fact unnecessary. In practice this can lead to additional computational burden and increased bias or inefficiency of estimates when dealing with measurement error or missing data. We present graphical criteria to detect variables which are redundant in identifying causal effects. We also provide an improved version of a well-known identifiability algorithm that implements these criteria.

JMLR Networks & Graphs Optimization & Learning Theory · 发表于 2018

Emergence of Invariance and Disentanglement in Deep Representations

Alessandro Achille, Stefano Soatto

摘要

Using established principles from Statistics and Information Theory, we show that invariance to nuisance factors in a deep neural network is equivalent to information minimality of the learned representation, and that stacking layers and injecting noise during training naturally bias the network towards learning invariant representations. We then decompose the cross-entropy loss used during training and highlight the presence of an inherent overfitting term. We propose regularizing the loss by bounding such a term in two equivalent ways: One with a Kullbach-Leibler term, which relates to a PAC-Bayes perspective; the other using the information in the weights as a measure of complexity of a learned model, yielding a novel Information Bottleneck for the weights. Finally, we show that invariance and independence of the components of the representation learned by the network are bounded above and below by the information in the weights, and therefore are implicitly optimized during training. The theory enables us to quantify and predict sharp phase transitions between underfitting and overfitting of random labels when using our regularized loss, which we verify in experiments, and sheds light on the relation between the geometry of the loss function, invariance properties of the learned representation, and generalization error.

Econometrica Other · 发表于 2018

Eliciting Temptation and Self-Control Through Menu Choices: A Lab Experiment

Séverine Toussaert

摘要

This is a lab experiment studying whether people might want to avoid temptation not because they expect to succumb to it but because they want to avoid the self-control costs of resisting it. *(abstract via OpenAlex)*

JMLR High-Dimensional Optimization & Learning Theory · 发表于 2018

Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity

Quanming Yao, James T. Kwok

摘要

The use of convex regularizers allows for easy optimization, though they often produce biased estimation and inferior prediction performance. Recently, nonconvex regularizers have attracted a lot of attention and outperformed convex ones. However, the resultant optimization problem is much harder. In this paper, a popular subclass of $\ell_1$-based nonconvex sparsity-inducing and low-rank regularizers is considered. This includes nonconvex variants of lasso, sparse group lasso, tree- structured lasso, nuclear norm and total variation regularizers. We propose to move the nonconvexity from the regularizer to the loss. The nonconvex regularizer is then transformed to a familiar convex one, while the resultant loss function can still be guaranteed to be smooth. Learning with the convexified regularizer can be performed by existing efficient algorithms originally designed for convex regularizers (such as the proximal algorithm, Frank-Wolfe algorithm, alternating direction method of multipliers and stochastic gradient descent). This is further extended to consider cases where the convexified regularizer does not have a closed-form proximal step, and when the loss function is nonconvex nonsmooth. Extensive experiments on a variety of machine learning application scenarios show that optimizing the transformed problem is much faster than running the state-of-the-art on the original problem.

JMLR Bayesian Methods Survival Analysis · 发表于 2018

Efficient Bayesian Inference of Sigmoidal Gaussian Cox Processes

Christian Donner, Manfred Opper

摘要

We present an approximate Bayesian inference approach for estimating the intensity of a inhomogeneous Poisson process, where the intensity function is modelled using a Gaussian process (GP) prior via a sigmoid link function. Augmenting the model using a latent marked Poisson process and Polya--Gamma random variables we obtain a representation of the likelihood which is conjugate to the GP prior. We estimate the posterior using a variational free--form mean field optimisation together with the framework of sparse GPs. Furthermore, as alternative approximation we suggest a sparse Laplace's method for the posterior, for which an efficient expectation--maximisation algorithm is derived to find the posterior's mode. Both algorithms compare well against exact inference obtained by a Markov Chain Monte Carlo sampler and standard variational Gauss approach solving the same model, while being one order of magnitude faster. Furthermore, the performance and speed of our method is competitive with that of another recently proposed Poisson process model based on a quadratic link function, while not being limited to GPs with squared exponential kernels and rectangular domains.

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

ELFI: Engine for Likelihood-Free Inference

Jarno Lintusaari, Henri Vuollekoski, Antti Kangasrääsiö, Kusti Skytén, Marko Järvenpää, Pekka Marttinen, Michael U. Gutmann, Aki Vehtari, Jukka Corander, Samuel Kaski

摘要

Engine for Likelihood-Free Inference (ELFI) is a Python software library for performing likelihood-free inference (LFI). ELFI provides a convenient syntax for arranging components in LFI, such as priors, simulators, summaries or distances, to a network called ELFI graph. The components can be implemented in a wide variety of languages. The stand-alone ELFI graph can be used with any of the available inference methods without modifications. A central method implemented in ELFI is Bayesian Optimization for Likelihood-Free Inference (BOLFI), which has recently been shown to accelerate likelihood-free inference up to several orders of magnitude by surrogate-modelling the distance. ELFI also has an inbuilt support for output data storing for reuse and analysis, and supports parallelization of computation from multiple cores up to a cluster environment. ELFI is designed to be extensible and provides interfaces for widening its functionality. This makes the adding of new inference methods to ELFI straightforward and automatically compatible with the inbuilt features.

Econometrica Other · 发表于 2018

Dynamic Mixture-Averse Preferences

Todd Sarver

摘要

To study intertemporal decisions under risk, we develop a new recursive model of non‐expected‐utility preferences. The main axiom of our analysis is called mixture aversion, as it captures a dislike of probabilistic mixtures of lotteries. Our representation for mixture‐averse preferences can be interpreted as if an individual optimally selects her risk attitude from some feasible set. We describe some useful parametric examples of our representation and provide comparative statics that tightly link decreases in risk aversion to larger sets of feasible risk attitudes. We then present several applications of the model. In an insurance problem, mixture‐averse preferences can produce a marginal willingness to pay for insurance coverage that increases in the level of existing coverage. In investment decisions, our model can generate endogenous heterogeneity in equilibrium stock market participation, even when consumers have identical preferences. Finally, we demonstrate that our model can address the Rabin paradox even in the presence of reasonable levels of background risk. *(abstract via OpenAlex)*

JMLR Other · 发表于 2018

Dual Principal Component Pursuit

Manolis C. Tsakiris, René Vidal

摘要

We consider the problem of learning a linear subspace from data corrupted by outliers. Classical approaches are typically designed for the case in which the subspace dimension is small relative to the ambient dimension. Our approach works with a dual representation of the subspace and hence aims to find its orthogonal complement; as such, it is particularly suitable for subspaces whose dimension is close to the ambient dimension (subspaces of high relative dimension). We pose the problem of computing normal vectors to the inlier subspace as a non-convex $\ell_1$ minimization problem on the sphere, which we call Dual Principal Component Pursuit (DPCP) problem. We provide theoretical guarantees under which every global solution to DPCP is a vector in the orthogonal complement of the inlier subspace. Moreover, we relax the non-convex DPCP problem to a recursion of linear programs whose solutions are shown to converge in a finite number of steps to a vector orthogonal to the subspace. In particular, when the inlier subspace is a hyperplane, the solutions to the recursion of linear programs converge to the global minimum of the non-convex DPCP problem in a finite number of steps. We also propose algorithms based on alternating minimization and iteratively re-weighted least squares, which are suitable for dealing with large-scale data. Experiments on synthetic data show that the proposed methods are able to handle more outliers and higher relative dimensions than current state-of-the-art methods, while experiments in the context of the three-view geometry problem in computer vision suggest that the proposed methods can be a useful or even superior alternative to traditional RANSAC-based approaches for computer vision and other applications.

第 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 32 33 页