2019 年的期刊文章 · 第 30 页

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

按期刊、按主题看 →

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

Econometrica Econometrics & Economics · 发表于 2019

Equilibria Under Knightian Price Uncertainty

Patrick Beissner, Frank Riedel

摘要

We study economies in which agents face Knightian uncertainty about state prices. Knightian uncertainty leads naturally to nonlinear expectations. We introduce a corresponding equilibrium concept with sublinear prices and prove that equilibria exist under weak conditions. In general, such equilibria lead to Pareto inefficient allocations; the equilibria coincide with Arrow-Debreu equilibria only if the values of net trades are ambiguity-free in the mean. In economies without aggregate uncertainty, inefficiencies are generic. We introduce a constrained efficiency concept, uncertainty-neutral efficiency, equilibrium allocations under price uncertainty are efficient in this constrained sense. Arrow-Debreu equilibria turn out to be non-robust with respect to the introduction of Knightian uncertainty. *(abstract via OpenAlex)*

Econometrica Econometrics & Economics · 发表于 2019

Engel's Law in the Global Economy: Demand‐Induced Patterns of Structural Change, Innovation, and Trade

Kiminori Matsuyama

摘要

Endogenous demand composition across sectors due to income elasticity differences, or Engel's Law for brevity, affects (i) sectoral compositions in employment and in value‐added, (ii) variations in innovation rates and in productivity change across sectors, (iii) intersectoral patterns of trade across countries, and (iv) product cycles from rich to poor countries. Using a two‐country model of directed technical change with a continuum of sectors under nonhomothetic preferences, which is rich enough to capture all these effects as well as their interactions, this paper offers a unifying perspective on how economic growth and globalization affect the patterns of structural change, innovation, and trade across countries and across sectors in the presence of Engel's Law. Among the main messages is that globalization amplifies, instead of reducing, the power of endogenous domestic demand composition differences as a driver of structural change.

Econometrica Econometrics & Economics · 发表于 2019

Endowments, Exclusion, and Exchange

Ivan Balbuzanov, Maciej H. Kotowski

摘要

We propose a new solution for discrete exchange economies and resource‐allocation problems, the exclusion core. The exclusion core rests upon a foundational idea in the legal understanding of property, the right to exclude others. By reinterpreting endowments as a distribution of exclusion rights, rather than as bundles of goods, our analysis extends to economies with qualified property rights, joint ownership, and social hierarchies. The exclusion core is characterized by a generalized top trading cycle algorithm in a large class of economies, including those featuring private, public, and mixed ownership. It is neither weaker nor stronger than the strong core.

JMLR Latent Variables & Mixtures · 发表于 2019

Embarrassingly Parallel Inference for Gaussian Processes

Michael Minyi Zhang, Sinead A. Williamson

摘要

Training Gaussian process-based models typically involves an $O(N^3)$ computational bottleneck due to inverting the covariance matrix. Popular methods for overcoming this matrix inversion problem cannot adequately model all types of latent functions, and are often not parallelizable. However, judicious choice of model structure can ameliorate this problem. A mixture-of-experts model that uses a mixture of $K$ Gaussian processes offers modeling flexibility and opportunities for scalable inference. Our embarrassingly parallel algorithm combines low-dimensional matrix inversions with importance sampling to yield a flexible, scalable mixture-of-experts model that offers comparable performance to Gaussian process regression at a much lower computational cost.

JMLR Causal Inference · 发表于 2019

Efficient augmentation and relaxation learning for individualized treatment rules using observational data

Ying-Qi Zhao, Eric B. Laber, Yang Ning, Sumona Saha, Bruce E. Sands

摘要

Individualized treatment rules aim to identify if, when, which, and to whom treatment should be applied. A globally aging population, rising healthcare costs, and increased access to patient-level data have created an urgent need for high-quality estimators of individualized treatment rules that can be applied to observational data. A recent and promising line of research for estimating individualized treatment rules recasts the problem of estimating an optimal treatment rule as a weighted classification problem. We consider a class of estimators for optimal treatment rules that are analogous to convex large-margin classifiers. The proposed class applies to observational data and is doubly-robust in the sense that correct specification of either a propensity or outcome model leads to consistent estimation of the optimal individualized treatment rule. Using techniques from semiparametric efficiency theory, we derive rates of convergence for the proposed estimators and use these rates to characterize the bias-variance trade-off for estimating individualized treatment rules with classification-based methods. Simulation experiments informed by these results demonstrate that it is possible to construct new estimators within the proposed framework that significantly outperform existing ones. We illustrate the proposed methods using data from a labor training program and a study of inflammatory bowel syndrome.

Econometrica Other · 发表于 2019

Dynamic Random Utility

Mira Frick, Ryota Iijima, Tomasz Strzalecki

摘要

We provide an axiomatic analysis of dynamic random utility, characterizing the stochastic choice behavior of agents who solve dynamic decision problems by maximizing some stochastic process (Ut) of utilities. We show first that even when (Ut) is arbitrary, dynamic random utility imposes new testableacross‐periodrestrictions on behavior, over and above period‐by‐period analogs of the static random utility axioms. An important feature of dynamic random utility is that behavior may appearhistory‐dependent, because period‐tchoices reveal information aboutUt, which may be serially correlated; however, our key new axioms highlight that the model entails specific limits on the form of history dependence that can arise. Second, we show that imposing natural Bayesian rationality axioms restricts the form of randomness that (Ut) can display. By contrast, a specification of utility shocks that is widely used in empirical work violates these restrictions, leading to behavior that may display a negative option value and can produce biased parameter estimates. Finally, dynamic stochastic choice data allow us to characterize important special cases of random utility—in particular, learning and taste persistence—that on static domains are indistinguishable from the general model.

Econometrica Nonparametric & Semiparametric · 发表于 2019

Dynamic Quantile Models of Rational Behavior

Luciano Castro, Antonio F. Galvao

摘要

This paper develops a dynamic model of rational behavior under uncertainty, in which the agent maximizes the stream of future τ ‐quantile utilities, for τ ∈ (0,1). That is, the agent has a quantile utility preference instead of the standard expected utility. Quantile preferences have useful advantages, including the ability to capture heterogeneity and allowing the separation between risk aversion and elasticity of intertemporal substitution. Although quantiles do not share some of the helpful properties of expectations, such as linearity and the law of iterated expectations, we are able to establish all the standard results in dynamic models. Namely, we show that the quantile preferences are dynamically consistent, the corresponding dynamic problem yields a value function, via a fixed point argument, this value function is concave and differentiable, and the principle of optimality holds. Additionally, we derive the corresponding Euler equation, which is well suited for using well‐known quantile regression methods for estimating and testing the economic model. In this way, the parameters of the model can be interpreted as structural objects. Therefore, the proposed methods provide microeconomic foundations for quantile regression methods. To illustrate the developments, we construct an intertemporal consumption model and estimate the discount factor and elasticity of intertemporal substitution parameters across the quantiles. The results provide evidence of heterogeneity in these parameters.

JMLR High-Dimensional Optimization & Learning Theory Econometrics & Economics · 发表于 2019

Dynamic Pricing in High-dimensions

Adel Javanmard, Hamid Nazerzadeh

摘要

We study the pricing problem faced by a firm that sells a large number of products, described via a wide range of features, to customers that arrive over time. Customers independently make purchasing decisions according to a general choice model that includes products features and customers' characteristics, encoded as $d$-dimensional numerical vectors, as well as the price offered. The parameters of the choice model are a priori unknown to the firm, but can be learned as the (binary-valued) sales data accrues over time. The firm's objective is to maximize its revenue. We benchmark the performance using the classic regret minimization framework where the regret is defined as the expected revenue loss against a clairvoyant policy that knows the parameters of the choice model in advance, and always offers the revenue-maximizing price. This setting is motivated in part by the prevalence of online marketplaces that allow for real-time pricing. We assume a structured choice model, parameters of which depend on $s_0$ out of the $d$ product features. Assuming that the market noise distribution is known, we propose a dynamic policy, called Regularized Maximum Likelihood Pricing (RMLP) that leverages the (sparsity) structure of the high-dimensional model and obtains a logarithmic regret in $T$. More specifically, the regret of our algorithm is of $O(s_0 \log d \cdot \log T)$. Furthermore, we show that no policy can obtain regret better than $O(s_0 (\log d + \log T))$. {In addition, we propose a generalization of our policy to a setting that the market noise distribution is unknown but belongs to a parametrized family of distributions. This policy obtains regret of $O(\sqrt{(\log d)T})$. We further show that no policy can obtain regret better than $\Omega(\sqrt{T})$ in such environments.}

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

Distributed Inference for Linear Support Vector Machine

Xiaozhou Wang, Zhuoyi Yang, Xi Chen, Weidong Liu

摘要

The growing size of modern data brings many new challenges to existing statistical inference methodologies and theories, and calls for the development of distributed inferential approaches. This paper studies distributed inference for linear support vector machine (SVM) for the binary classification task. Despite a vast literature on SVM, much less is known about the inferential properties of SVM, especially in a distributed setting. In this paper, we propose a multi-round distributed linear-type (MDL) estimator for conducting inference for linear SVM. The proposed estimator is computationally efficient. In particular, it only requires an initial SVM estimator and then successively refines the estimator by solving simple weighted least squares problem. Theoretically, we establish the Bahadur representation of the estimator. Based on the representation, the asymptotic normality is further derived, which shows that the MDL estimator achieves the optimal statistical efficiency, i.e., the same efficiency as the classical linear SVM applying to the entire data set in a single machine setup. Moreover, our asymptotic result avoids the condition on the number of machines or data batches, which is commonly assumed in distributed estimation literature, and allows the case of diverging dimension. We provide simulation studies to demonstrate the performance of the proposed MDL estimator.

JMLR Other · 发表于 2019

Differentiable reservoir computing

Lyudmila Grigoryeva, Juan-Pablo Ortega

摘要

Numerous results in learning and approximation theory have evidenced the importance of differentiability at the time of countering the curse of dimensionality. In the context of reservoir computing, much effort has been devoted in the last two decades to characterize the situations in which systems of this type exhibit the so-called echo state (ESP) and fading memory (FMP) properties. These important features amount, in mathematical terms, to the existence and continuity of global reservoir system solutions. That research is complemented in this paper with the characterization of the differentiability of reservoir filters for very general classes of discrete-time deterministic inputs. This constitutes a novel strong contribution to the long line of research on the ESP and the FMP and, in particular, links to existing research on the input-dependence of the ESP. Differentiability has been shown in the literature to be a key feature in the learning of attractors of chaotic dynamical systems. A Volterra-type series representation for reservoir filters with semi-infinite discrete-time inputs is constructed in the analytic case using Taylor's theorem and corresponding approximation bounds are provided. Finally, it is shown as a corollary of these results that any fading memory filter can be uniformly approximated by a finite Volterra series with finite memory.

JMLR Other · 发表于 2019

Differentiable Game Mechanics

Alistair Letcher, David Balduzzi, Sébastien Racanière, James Martens, Jakob Foerster, Karl Tuyls, Thore Graepel

摘要

Deep learning is built on the foundational guarantee that gradient descent on an objective function converges to local minima. Unfortunately, this guarantee fails in settings, such as generative adversarial nets, that exhibit multiple interacting losses. The behavior of gradient-based methods in games is not well understood -- and is becoming increasingly important as adversarial and multi-objective architectures proliferate. In this paper, we develop new tools to understand and control the dynamics in $n$-player differentiable games. The key result is to decompose the game Jacobian into two components. The first, symmetric component, is related to potential games, which reduce to gradient descent on an implicit function. The second, antisymmetric component, relates to Hamiltonian games, a new class of games that obey a conservation law akin to conservation laws in classical mechanical systems. The decomposition motivates Symplectic Gradient Adjustment (SGA), a new algorithm for finding stable fixed points in differentiable games. Basic experiments show SGA is competitive with recently proposed algorithms for finding stable fixed points in GANs -- while at the same time being applicable to, and having guarantees in, much more general cases.

JMLR Latent Variables & Mixtures · 发表于 2019

Determining the Number of Latent Factors in Statistical Multi-Relational Learning

Chengchun Shi, Wenbin Lu, Rui Song

摘要

Statistical relational learning is primarily concerned with learning and inferring relationships between entities in large-scale knowledge graphs. Nickel et al. (2011) proposed a RESCAL tensor factorization model for statistical relational learning, which achieves better or at least comparable results on common benchmark data sets when compared to other state-of-the-art methods. Given a positive integer $s$, RESCAL computes an $s$-dimensional latent vector for each entity. The latent factors can be further used for solving relational learning tasks, such as collective classification, collective entity resolution and link-based clustering. The focus of this paper is to determine the number of latent factors in the RESCAL model. Due to the structure of the RESCAL model, its log-likelihood function is not concave. As a result, the corresponding maximum likelihood estimators (MLEs) may not be consistent. Nonetheless, we design a specific pseudometric, prove the consistency of the MLEs under this pseudometric and establish its rate of convergence. Based on these results, we propose a general class of information criteria and prove their model selection consistencies when the number of relations is either bounded or diverges at a proper rate of the number of entities. Simulations and real data examples show that our proposed information criteria have good finite sample properties.

JMLR Spatial & Time Series · 发表于 2019

Determinantal Point Processes for Coresets

Nicolas Tremblay, Simon Barthelmé, Pierre-Olivier Amblard

摘要

When faced with a data set too large to be processed all at once, an obvious solution is to retain only part of it. In practice this takes a wide variety of different forms, and among them “coresets” are especially appealing. A coreset is a (small) weighted sample of the original data that comes with the following guarantee: a cost function can be evaluated on the smaller set instead of the larger one, with low relative error. For some classes of problems, and via a careful choice of sampling distribution (based on the so-called “sensitivity” metric), iid random sampling has turned to be one of the most successful methods for building coresets efficiently. However, independent samples are sometimes overly redundant, and one could hope that enforcing diversity would lead to better performance. The difficulty lies in proving coreset properties in non-iid samples. We show that the coreset property holds for samples formed with determinantal point processes (DPP). DPPs are interesting because they are a rare example of repulsive point processes with tractable theoretical properties, enabling us to prove general coreset theorems. We apply our results to both the $k$-means and the linear regression problems, and give extensive empirical evidence that the small additional computational cost of DPP sampling comes with superior performance over its iid counterpart. Of independent interest, we also provide analytical formulas for the sensitivity in the linear regression and $1$-means cases.

JMLR High-Dimensional Bayesian Methods · 发表于 2019

Dependent relevance determination for smooth and structured sparse regression

Anqi Wu, Oluwasanmi Koyejo, Jonathan Pillow

摘要

In many problem settings, parameter vectors are not merely sparse but dependent in such a way that non-zero coefficients tend to cluster together. We refer to this form of dependency as “region sparsity.” Classical sparse regression methods, such as the lasso and automatic relevance determination (ARD), which model parameters as independent a priori, and therefore do not exploit such dependencies. Here we introduce a hierarchical model for smooth, region-sparse weight vectors and tensors in a linear regression setting. Our approach represents a hierarchical extension of the relevance determination framework, where we add a transformed Gaussian process to model the dependencies between the prior variances of regression weights. We combine this with a structured model of the prior variances of Fourier coefficients, which eliminates unnecessary high frequencies. The resulting prior encourages weights to be region-sparse in two different bases simultaneously. We develop Laplace approximation and Monte Carlo Markov Chain (MCMC) sampling to provide efficient inference for the posterior. Furthermore, a two-stage convex relaxation of the Laplace approximation approach is also provided to relax the inevitable non-convexity during the optimization. We finally show substantial improvements over comparable methods for both simulated and real datasets from brain imaging.

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

Delay and Cooperation in Nonstochastic Bandits

Nicolò Cesa-Bianchi, Claudio Gentile, Yishay Mansour

摘要

We study networks of communicating learning agents that cooperate to solve a common nonstochastic bandit problem. Agents use an underlying communication network to get messages about actions selected by other agents, and drop messages that took more than $d$ hops to arrive, where $d$ is a delay parameter. We introduce Exp3-Coop, a cooperative version of the Exp3 algorithm and prove that with $K$ actions and $N$ agents the average per-agent regret after $T$ rounds is at most of order $\sqrt{\bigl(d+1 + \tfrac{K}{N}\alpha_{\le d}\bigr)(T\ln K)}$, where $\alpha_{\le d}$ is the independence number of the $d$-th power of the communication graph $G$. We then show that for any connected graph, for $d=\sqrt{K}$ the regret bound is $K^{1/4}\sqrt{T}$, strictly better than the minimax regret $\sqrt{KT}$ for noncooperating agents. More informed choices of $d$ lead to bounds which are arbitrarily close to the full information minimax regret $\sqrt{T\ln K}$ when $G$ is dense. When $G$ has sparse components, we show that a variant of Exp3-Coop, allowing agents to choose their parameters according to their centrality in $G$, strictly improves the regret. Finally, as a by-product of our analysis, we provide the first characterization of the minimax regret for bandit learning with delay.

JMLR Machine Learning · 发表于 2019

Deep Reinforcement Learning for Swarm Systems

Maximilian Hüttenrauch, Adrian Šošić, Gerhard Neumann

摘要

Recently, deep reinforcement learning (RL) methods have been applied successfully to multi-agent scenarios. Typically, the observation vector for decentralized decision making is represented by a concatenation of the (local) information an agent gathers about other agents. However, concatenation scales poorly to swarm systems with a large number of homogeneous agents as it does not exploit the fundamental properties inherent to these systems: (i) the agents in the swarm are interchangeable and (ii) the exact number of agents in the swarm is irrelevant. Therefore, we propose a new state representation for deep multi-agent RL based on mean embeddings of distributions, where we treat the agents as samples and use the empirical mean embedding as input for a decentralized policy. We define different feature spaces of the mean embedding using histograms, radial basis functions and neural networks trained end-to-end. We evaluate the representation on two well-known problems from the swarm literature in a globally and locally observable setup. For the local setup we furthermore introduce simple communication protocols. Of all approaches, the mean embedding representation using neural network features enables the richest information exchange between neighboring agents, facilitating the development of complex collective strategies.

JMLR High-Dimensional Machine Learning · 发表于 2019

Deep Optimal Stopping

Sebastian Becker, Patrick Cheridito, Arnulf Jentzen

摘要

In this paper we develop a deep learning method for optimal stopping problems which directly learns the optimal stopping rule from Monte Carlo samples. As such, it is broadly applicable in situations where the underlying randomness can efficiently be simulated. We test the approach on three problems: the pricing of a Bermudan max-call option, the pricing of a callable multi barrier reverse convertible and the problem of optimally stopping a fractional Brownian motion. In all three cases it produces very accurate results in high-dimensional situations with short computing times.

JMLR Machine Learning Optimization & Learning Theory · 发表于 2019

Deep Exploration via Randomized Value Functions

Ian Osband, Benjamin Van Roy, Daniel J. Russo, Zheng Wen

摘要

We study the use of randomized value functions to guide deep exploration in reinforcement learning. This offers an elegant means for synthesizing statistically and computationally efficient exploration with common practical approaches to value function learning. We present several reinforcement learning algorithms that leverage randomized value functions and demonstrate their efficacy through computational studies. We also prove a regret bound that establishes statistical efficiency with a tabular representation.

JMLR High-Dimensional · 发表于 2019

Decoupling Sparsity and Smoothness in the Dirichlet Variational Autoencoder Topic Model

Sophie Burkhardt, Stefan Kramer

摘要

Recent work on variational autoencoders (VAEs) has enabled the development of generative topic models using neural networks. Topic models based on latent Dirichlet allocation (LDA) successfully use the Dirichlet distribution as a prior for the topic and word distributions to enforce sparseness. However, there is a trade-off between sparsity and smoothness in Dirichlet distributions. Sparsity is important for a low reconstruction error during training of the autoencoder, whereas smoothness enables generalization and leads to a better log-likelihood of the test data. Both of these properties are encoded in the Dirichlet parameter vector. By rewriting this parameter vector into a product of a sparse binary vector and a smoothness vector, we decouple the two properties, leading to a model that features both a competitive topic coherence and a high log-likelihood. Efficient training is enabled using rejection sampling variational inference for the reparameterization of the Dirichlet distribution. Our experiments show that our method is competitive with other recent VAE topic models.

JMLR Other · 发表于 2019

Decontamination of Mutual Contamination Models

Julian Katz-Samuels, Gilles Blanchard, Clayton Scott

摘要

Many machine learning problems can be characterized by \emph{mutual contamination models}. In these problems, one observes several random samples from different convex combinations of a set of unknown base distributions and the goal is to infer these base distributions. This paper considers the general setting where the base distributions are defined on arbitrary probability spaces. We examine three popular machine learning problems that arise in this general setting: multiclass classification with label noise, demixing of mixed membership models, and classification with partial labels. In each case, we give sufficient conditions for identifiability and present algorithms for the infinite and finite sample settings, with associated performance guarantees.

JMLR Networks & Graphs · 发表于 2019

Decentralized Dictionary Learning Over Time-Varying Digraphs

Amir Daneshmand, Ying Sun, Gesualdo Scutari, Francisco Facchinei, Brian M. Sadler

摘要

This paper studies Dictionary Learning problems wherein the learning task is distributed over a multi-agent network, modeled as a time-varying directed graph. This formulation is relevant, for instance, in Big Data scenarios where massive amounts of data are collected/stored in different locations (e.g., sensors, clouds) and aggregating and/or processing all data in a fusion center might be inefficient or unfeasible, due to resource limitations, communication overheads or privacy issues. We develop a unified decentralized algorithmic framework for this class of nonconvex problems, which is proved to converge to stationary solutions at a sublinear rate. The new method hinges on Successive Convex Approximation techniques, coupled with a decentralized tracking mechanism aiming at locally estimating the gradient of the smooth part of the sum-utility. To the best of our knowledge, this is the first provably convergent decentralized algorithm for Dictionary Learning and, more generally, bi-convex problems over (time-varying) (di)graphs.

JMLR Missing Data & Measurement Error Machine Learning · 发表于 2019

DataWig: Missing Value Imputation for Tables

Felix Biessmann, Tammo Rukat, Phillipp Schmidt, Prathik Naidu, Sebastian Schelter, Andrey Taptunov, Dustin Lange, David Salinas

摘要

With the growing importance of machine learning (ML) algorithms for practical applications, reducing data quality problems in ML pipelines has become a major focus of research. In many cases missing values can break data pipelines which makes completeness one of the most impactful data quality challenges. Current missing value imputation methods are focusing on numerical or categorical data and can be difficult to scale to datasets with millions of rows. We release DataWig, a robust and scalable approach for missing value imputation that can be applied to tables with heterogeneous data types, including unstructured text. DataWig combines deep learning feature extractors with automatic hyperparameter tuning. This enables users without a machine learning background, such as data engineers, to impute missing values with minimal effort in tables with more heterogeneous data types than supported in existing libraries, while requiring less glue code for feature engineering and offering more flexible modelling options. We demonstrate that DataWig compares favourably to existing imputation packages. Source code, documentation, and unit tests for this package are available at: https://github.com/awslabs/datawig

JMLR Meta-Analysis & Data Integration Optimization & Learning Theory · 发表于 2019

DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimization

Lin Xiao, Adams Wei Yu, Qihang Lin, Weizhu Chen

摘要

Machine learning with big data often involves large optimization models. For distributed optimization over a cluster of machines, frequent communication and synchronization of all model parameters (optimization variables) can be very costly. A promising solution is to use parameter servers to store different subsets of the model parameters, and update them asynchronously at different machines using local datasets. In this paper, we focus on distributed optimization of large linear models with convex loss functions, and propose a family of randomized primal-dual block coordinate algorithms that are especially suitable for asynchronous distributed implementation with parameter servers. In particular, we work with the saddle-point formulation of such problems which allows simultaneous data and model partitioning, and exploit its structure by doubly stochastic coordinate optimization with variance reduction (DSCOVR). Compared with other first-order distributed algorithms, we show that DSCOVR may require less amount of overall computation and communication, and less or no synchronization. We discuss the implementation details of the DSCOVR algorithms, and present numerical experiments on an industrial distributed computing system.

JMLR Other · 发表于 2019

DPPy: DPP Sampling with Python

Guillaume Gautier, Guillermo Polito, Rémi Bardenet, Michal Valko

摘要

Determinantal point processes (DPPs) are specific probability distributions over clouds of points that are used as models and computational tools across physics, probability, statistics, and more recently machine learning. Sampling from DPPs is a challenge and therefore we present DPPy, a Python toolbox that gathers known exact and approximate sampling algorithms for both finite and continuous DPPs. The project is hosted on GitHub, and equipped with an extensive documentation.

JMLR Other · 发表于 2019

DBSCAN: Optimal Rates For Density-Based Cluster Estimation

Daren Wang, Xinyang Lu, Alessandro Rinaldo

摘要

We study the problem of optimal estimation of the density cluster tree under various smoothness assumptions on the underlying density. Inspired by the seminal work of Chaudhuri et al. (2014), we formulate a new notion of clustering consistency which is better suited to smooth densities, and derive minimax rates for cluster tree estimation under Hölder smooth densities of arbitrary degree. We present a computationally efficient, rate optimal cluster tree estimator based on simple extensions of the popular DBSCAN algorithm of Ester et al. (1996). Our procedure relies on kernel density estimators and returns a sequence of nested random geometric graphs whose connected components form a hierarchy of clusters. The resulting optimal rates for cluster tree estimation depend on the degree of smoothness of the underlying density and, interestingly, match the minimax rates for density estimation under the sup-norm loss. Our results complement and extend the analysis of the DBSCAN algorithm in Sriperumbudur and Steinwart (2012). Finally, we consider level set estimation and cluster consistency for densities with jump discontinuities. We demonstrate that the DBSCAN algorithm attains the minimax rate in terms of the jump size and sample size in this setting as well.

JMLR Other · 发表于 2019

Convergence of Gaussian Belief Propagation Under General Pairwise Factorization: Connecting Gaussian MRF with Pairwise Linear Gaussian Model

Bin Li, Yik-Chung Wu

摘要

Gaussian belief propagation (BP) is a low-complexity and distributed method for computing the marginal distributions of a high-dimensional joint Gaussian distribution. However, Gaussian BP is only guaranteed to converge in singly connected graphs and may fail to converge in loopy graphs. Therefore, convergence analysis is a core topic in Gaussian BP. Existing conditions for verifying the convergence of Gaussian BP are all tailored for one particular pairwise factorization of the distribution in Gaussian Markov random field (MRF) and may not be valid for another pairwise factorization. On the other hand, convergence conditions of Gaussian BP in pairwise linear Gaussian model are developed independently from those in Gaussian MRF, making the convergence results highly scattered with diverse settings. In this paper, the convergence condition of Gaussian BP is investigated under a general pairwise factorization, which includes Gaussian MRF and pairwise linear Gaussian model as special cases. Upon this, existing convergence conditions in Gaussian MRF are extended to any pairwise factorization. Moreover, the newly established link between Gaussian MRF and pairwise linear Gaussian model reveals an easily verifiable sufficient convergence condition in pairwise linear Gaussian model, which provides a unified criterion for assessing the convergence of Gaussian BP in multiple applications. Numerical examples are presented to corroborate the theoretical results of this paper.

JMLR Other · 发表于 2019

Convergence Rate of a Simulated Annealing Algorithm with Noisy Observations

Clément Bouttier, Ioana Gavra

摘要

In this paper we propose a modified version of the simulated annealing algorithm for solving a stochastic global optimization problem. More precisely, we address the problem of finding a global minimizer of a function with noisy evaluations. We provide a rate of convergence and its optimized parametrization to ensure a minimal number of evaluations for a given accuracy and a confidence level close to 1. This work is completed with a set of numerical experimentations and assesses the practical performance both on benchmark test cases and on real world examples.

JMLR Optimization & Learning Theory · 发表于 2019

Convergence Guarantees for a Class of Non-convex and Non-smooth Optimization Problems

Koulik Khamaru, Martin J. Wainwright

摘要

We consider the problem of finding critical points of functions that are non-convex and non-smooth. Studying a fairly broad class of such problems, we analyze the behavior of three gradient-based methods (gradient descent, proximal update, and Frank-Wolfe update). For each of these methods, we establish rates of convergence for general problems, and also prove faster rates for continuous sub-analytic functions. We also show that our algorithms can escape strict saddle points for a class of non-smooth functions, thereby generalizing known results for smooth functions. Our analysis leads to a simplification of the popular CCCP algorithm, used for optimizing functions that can be written as a difference of two convex functions. Our simplified algorithm retains all the convergence properties of CCCP, along with a significantly lower cost per iteration. We illustrate our methods and theory via applications to the problems of best subset selection, robust estimation, mixture density estimation, and shape-from-shading reconstruction.

Econometrica Other · 发表于 2019

Consistent Pseudo-Maximum Likelihood Estimators and Groups of Transformations

C. Gouriéroux, A. Monfort, J-M. Zakoïan

摘要

In a transformation model y t = c[a(x t , β), u t ], where the errors u t are i.i.d and independent of the explanatory variables x t , the parameters can be estimated by a pseudo-maximum likelihood (PML) method, that is, by using a misspecified distribution of the errors, but the PML estimator of β is in general not consistent.We explain in this paper how to nest the initial model in an identified augmented model with more parameters in order to derive consistent PML estimators of appropriate functions of parameter β.The usefulness of the consistency result is illustrated by examples of systems of nonlinear equations, conditionally heteroskedastic models, stochastic volatility, or models with spatial interactions. *(abstract via OpenAlex)*

Econometrica Testing & Uncertainty · 发表于 2019

Confidence Intervals for Projections of Partially Identified Parameters

Hiroaki Kaido, Francesca Molinari, Jörg Stoye

摘要

We propose a bootstrap‐based calibrated projection procedure to build confidence intervals for single components and for smooth functions of a partially identified parameter vector in moment (in)equality models. The method controls asymptotic coverage uniformly over a large class of data generating processes. The extreme points of the calibrated projection confidence interval are obtained by extremizing the value of the function of interest subject to a proper relaxation of studentized sample analogs of the moment (in)equality conditions. The degree of relaxation, or critical level, is calibrated so that the function of θ , not θ itself, is uniformly asymptotically covered with prespecified probability. This calibration is based on repeatedly checking feasibility of linear programming problems, rendering it computationally attractive. Nonetheless, the program defining an extreme point of the confidence interval is generally nonlinear and potentially intricate. We provide an algorithm, based on the response surface method for global optimization, that approximates the solution rapidly and accurately, and we establish its rate of convergence. The algorithm is of independent interest for optimization problems with simple objectives and complicated constraints. An empirical application estimating an entry game illustrates the usefulness of the method. Monte Carlo simulations confirm the accuracy of the solution algorithm, the good statistical as well as computational performance of calibrated projection (including in comparison to other methods), and the algorithm's potential to greatly accelerate computation of other confidence intervals.

JMLR High-Dimensional · 发表于 2019

Complete Search for Feature Selection in Decision Trees

Salvatore Ruggieri

摘要

The search space for the feature selection problem in decision tree learning is the lattice of subsets of the available features. We design an exact enumeration procedure of the subsets of features that lead to all and only the distinct decision trees built by a greedy top-down decision tree induction algorithm. The procedure stores, in the worst case, a number of trees linear in the number of features. By exploiting a further pruning of the search space, we design a complete procedure for finding $\delta$-acceptable feature subsets, which depart by at most $\delta$ from the best estimated error over any feature subset. Feature subsets with the best estimated error are called best feature subsets. Our results apply to any error estimator function, but experiments are mainly conducted under the wrapper model, in which the misclassification error over a search set is used as an estimator. The approach is also adapted to the design of a computational optimization of the sequential backward elimination heuristic, extending its applicability to large dimensional datasets. The procedures of this paper are implemented in a multi-core data parallel C++ system. We investigate experimentally the properties and limitations of the procedures on a collection of 20 benchmark datasets, showing that oversearching increases both overfitting and instability.

JMLR Other · 发表于 2019

Collective Matrix Completion

Mokhtar Z. Alaya, Olga Klopp

摘要

Matrix completion aims to reconstruct a data matrix based on observations of a small number of its entries. Usually in matrix completion a single matrix is considered, which can be, for example, a rating matrix in recommendation system. However, in practical situations, data is often obtained from multiple sources which results in a collection of matrices rather than a single one. In this work, we consider the problem of collective matrix completion with multiple and heterogeneous matrices, which can be count, binary, continuous, etc. We first investigate the setting where, for each source, the matrix entries are sampled from an exponential family distribution. Then, we relax the assumption of exponential family distribution for the noise. In this setting, we do not assume any specific model for the observations. The estimation procedures are based on minimizing the sum of a goodness-of-fit term and the nuclear norm penalization of the whole collective matrix. We prove that the proposed estimators achieve fast rates of convergence under the two considered settings and we corroborate our results with numerical experiments.

Econometrica Other · 发表于 2019

Coalitional Expected Multi‐Utility Theory

Kazuhiro Hara, Efe A. Ok, Gil Riella

摘要

This paper begins by observing that any reflexive binary (preference) relation (over risky prospects) that satisfies the independence axiom admits a form of expected utility representation. We refer to this representation notion as the coalitional minmax expected utility representation. By adding the remaining properties of the expected utility theorem, namely, continuity, completeness, and transitivity, one by one, we find how this representation gets sharper and sharper, thereby deducing the versions of this classical theorem in which any combination of these properties is dropped from its statement. This approach also allows us to weaken transitivity in this theorem, rather than eliminate it entirely, say, to quasitransitivity or acyclicity. Apart from providing a unified dissection of the expected utility theorem, these results are relevant for the growing literature on boundedly rational choice in which revealed preference relations often lack the properties of completeness and/or transitivity (but often satisfy the independence axiom). They are also especially suitable for the (yet overlooked) case in which the decision‐maker is made up of distinct individuals and, consequently, transitivity is routinely violated. Finally, and perhaps more importantly, we show that our representation theorems allow us to answer many economic questions that are posed in terms of nontransitive/incomplete preferences, say, about the maximization of preferences, the existence of Nash equilibrium, the preference for portfolio diversification, and the possibility of the preference reversal phenomenon.

JMLR Optimization & Learning Theory · 发表于 2019

Characterizing the Sample Complexity of Pure Private Learners

Amos Beimel, Kobbi Nissim, Uri Stemmer

摘要

Kasiviswanathan et al. (FOCS 2008) defined private learning as a combination of PAC learning and differential privacy. Informally, a private learner is applied to a collection of labeled individual information and outputs a hypothesis while preserving the privacy of each individual. Kasiviswanathan et al. left open the question of characterizing the sample complexity of private learners. We give a combinatorial characterization of the sample size sufficient and necessary to learn a class of concepts under pure differential privacy. This characterization is analogous to the well known characterization of the sample complexity of non-private learning in terms of the VC dimension of the concept class. We introduce the notion of probabilistic representation of a concept class, and our new complexity measure $RepDim$ corresponds to the size of the smallest probabilistic representation of the concept class. We show that any private learning algorithm for a concept class $C$ with sample complexity $m$ implies $RepDim(C)=O(m)$, and that there exists a private learning algorithm with sample complexity $m=O(RepDim(C))$. We further demonstrate that a similar characterization holds for the database size needed for computing a large class of optimization problems under pure differential privacy, and also for the well studied problem of private data release.

JMLR Causal Inference · 发表于 2019

Change Surfaces for Expressive Multidimensional Changepoints and Counterfactual Prediction

William Herlands, Daniel B. Neill, Hannes Nickisch, Andrew Gordon Wilson

摘要

Identifying changes in model parameters is fundamental in machine learning and statistics. However, standard changepoint models are limited in expressiveness, often addressing unidimensional problems and assuming instantaneous changes. We introduce change surfaces as a multidimensional and highly expressive generalization of changepoints. We provide a model-agnostic formalization of change surfaces, illustrating how they can provide variable, heterogeneous, and non-monotonic rates of change across multiple dimensions. Additionally, we show how change surfaces can be used for counterfactual prediction. As a concrete instantiation of the change surface framework, we develop Gaussian Process Change Surfaces (GPCS). We demonstrate counterfactual prediction with Bayesian posterior mean and credible sets, as well as massive scalability by introducing novel methods for additive non-separable kernels. Using two large spatio-temporal datasets we employ GPCS to discover and characterize complex changes that can provide scientific and policy relevant insights. Specifically, we analyze twentieth century measles incidence across the United States and discover previously unknown heterogeneous changes after the introduction of the measles vaccine. Additionally, we apply the model to requests for lead testing kits in New York City, discovering distinct spatial and demographic patterns.

JMLR Causal Inference Machine Learning · 发表于 2019

Causal Learning via Manifold Regularization

Steven M. Hill, Chris J. Oates, Duncan A. Blythe, Sach Mukherjee

摘要

This paper frames causal structure estimation as a machine learning task. The idea is to treat indicators of causal relationships between variables as `labels' and to exploit available data on the variables of interest to provide features for the labelling task. Background scientific knowledge or any available interventional data provide labels on some causal relationships and the remainder are treated as unlabelled. To illustrate the key ideas, we develop a distance-based approach (based on bivariate histograms) within a manifold regularization framework. We present empirical results on three different biological data sets (including examples where causal effects can be verified by experimental intervention), that together demonstrate the efficacy and general nature of the approach as well as its simplicity from a user's point of view.

Econometrica Econometrics & Economics · 发表于 2019

Career and Family Decisions: Cohorts Born 1935-1975

Zvi Eckstein, Michael Keane, Osnat Lifshitz

摘要

Comparing the 1935 and 1975 U.S. birth cohorts, wages of married women grew twice as fast as for married men, and the wage gap between married and single women turned from negative to positive. The employment rate of married women also increased sharply, while that of other groups remained quite stable. To better understand these diverse patterns, we develop a life-cycle model incorporating individual and household decisions about education, employment, marriage/divorce, and fertility. The model provides an excellent fit to wage and employment patterns, along with changes in education, marriage/divorce rates, and fertility. We assume fixed preferences, but allow for four exogenously changing factors: (i) mother's education, health, and taxes/transfers; (ii) marriage market opportunities and divorce costs; (iii) the wage structure and job offers; (iv) contraception technology. We quantify how each factor contributed to changes across cohorts. We find that factor (iii) was the most important force driving the increase in relative wages of married women, but that all four factors are important for explaining the many socio-economic changes that occurred in the past 50 years. Finally, we use the model to simulate a shift from joint to individual taxation. In a revenue-neutral simulation, we predict this would increase employment of married women by 9% and the marriage rate by 8.1%. *(abstract via OpenAlex)*

JMLR Nonparametric & Semiparametric Econometrics & Economics · 发表于 2019

Boosted Kernel Ridge Regression: Optimal Learning Rates and Early Stopping

Shao-Bo Lin, Yunwen Lei, Ding-Xuan Zhou

摘要

In this paper, we introduce a learning algorithm, boosted kernel ridge regression (BKRR), that combines $L_2$-Boosting with the kernel ridge regression (KRR). We analyze the learning performance of this algorithm in the framework of learning theory. We show that BKRR provides a new bias-variance trade-off via tuning the number of boosting iterations, which is different from KRR via adjusting the regularization parameter. A (semi-)exponential bias-variance trade-off is derived for BKRR, exhibiting a stable relationship between the generalization error and the number of iterations. Furthermore, an adaptive stopping rule is proposed, with which BKRR achieves the optimal learning rate without saturation.

JMLR Other · 发表于 2019

Binarsity: a penalization for one-hot encoded features in linear supervised learning

Mokhtar Z. Alaya, Simon Bussy, Stéphane Gaïffas, Agathe Guilloux

摘要

This paper deals with the problem of large-scale linear supervised learning in settings where a large number of continuous features are available. We propose to combine the well-known trick of one-hot encoding of continuous features with a new penalization called binarsity. In each group of binary features coming from the one-hot encoding of a single raw continuous feature, this penalization uses total-variation regularization together with an extra linear constraint. This induces two interesting properties on the model weights of the one-hot encoded features: they are piecewise constant, and are eventually block sparse. Non-asymptotic oracle inequalities for generalized linear models are proposed. Moreover, under a sparse additive model assumption, we prove that our procedure matches the state-of-the-art in this setting. Numerical experiments illustrate the good performances of our approach on several datasets. It is also noteworthy that our method has a numerical complexity comparable to standard $\ell_1$ penalization.

JMLR Optimization & Learning Theory · 发表于 2019

Best Arm Identification for Contaminated Bandits

Jason Altschuler, Victor-Emmanuel Brunel, Alan Malek

摘要

This paper studies active learning in the context of robust statistics. Specifically, we propose a variant of the Best Arm Identification problem for contaminated bandits, where each arm pull has probability epsilon of generating a sample from an arbitrary contamination distribution instead of the true underlying distribution. The goal is to identify the best (or approximately best) true distribution with high probability, with a secondary goal of providing guarantees on the quality of this distribution. The primary challenge of the contaminated bandit setting is that the true distributions are only partially identifiable, even with infinite samples. To address this, we develop tight, non-asymptotic sample complexity bounds for high-probability estimation of the first two robust moments (median and median absolute deviation) from contaminated samples. These concentration inequalities are the main technical contributions of the paper and may be of independent interest. Using these results, we adapt several classical Best Arm Identification algorithms to the contaminated bandit setting and derive sample complexity upper bounds for our problem. Finally, we provide matching information-theoretic lower bounds on the sample complexity (up to a small logarithmic factor).

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