2019 年的期刊文章 · 第 31 页

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

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

Bayesian Space-Time Partitioning by Sampling and Pruning Spanning Trees

Leonardo V. Teixeira, Renato M. Assunção, Rosangela H. Loschi

摘要

A typical problem in spatial data analysis is regionalization or spatially constrained clustering, which consists of aggregating small geographical areas into larger regions. A major challenge when partitioning a map is the huge number of possible partitions that compose the search space. This is compounded if we are partitioning spatio-temporal data rather than purely spatial data. We introduce a spatio-temporal product partition model that deals with the regionalization problem in a probabilistic way. Random spanning trees are used as a tool to tackle the problem of searching the space of possible partitions making feasible this exploration. Based on this framework, we propose an efficient Gibbs sampler algorithm to sample from the posterior distribution of the parameters, specially the random partition. The proposed Gibbs sampler scheme carries out a random walk on the space of the spanning trees and the partitions induced by deleting tree edges. In the purely spatial situation, we compare our proposed model with other state-of-art regionalization techniques to partition maps using simulated and real social and health data. To illustrate how the temporal component is handled by the algorithm and to show how the spatial clusters vary along the time we presented an application using human development index data. The analysis shows that our proposed model is better than state-of-art alternatives. Another appealing feature of the method is that the prior distribution for the partition is interpretable with a trivial coin flipping mechanism allowing its easy elicitation.

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

Bayesian Optimization for Policy Search via Online-Offline Experimentation

Benjamin Letham, Eytan Bakshy

摘要

Online field experiments are the gold-standard way of evaluating changes to real-world interactive machine learning systems. Yet our ability to explore complex, multi-dimensional policy spaces—such as those found in recommendation and ranking problems—is often constrained by the limited number of experiments that can be run simultaneously. To alleviate these constraints, we augment online experiments with an offline simulator and apply multi-task Bayesian optimization to tune live machine learning systems. We describe practical issues that arise in these types of applications, including biases that arise from using a simulator and assumptions for the multi-task kernel. We measure empirical learning curves which show substantial gains from including data from biased offline experiments, and show how these learning curves are consistent with theoretical results for multi-task Gaussian process generalization. We find that improved kernel inference is a significant driver of multi-task generalization. Finally, we show several examples of Bayesian optimization efficiently tuning a live machine learning system by combining offline and online experiments.

JMLR Bayesian Methods · 发表于 2019

Bayesian Combination of Probabilistic Classifiers using Multivariate Normal Mixtures

Gregor Pirš, Erik Štrumbelj

摘要

Ensemble methods are a powerful tool, often outperforming individual prediction models. Existing Bayesian ensembles either do not model the correlations between sources, or they are only capable of combining non-probabilistic predictions. We propose a new model, which overcomes these disadvantages. Transforming the probabilistic predictions with the inverse additive logistic transformation allows us to model the correlations with multivariate normal mixtures. We derive an efficient Gibbs sampler for the proposed model and implement a regularization method to make it more robust. We compare our method to related work and the classical linear opinion pool. Empirical evaluation on several toy and real-world data sets, including a case study on air-pollution forecasting, shows that the method outperforms other methods, while being robust and easy to use.

Econometrica Other · 发表于 2019

Bargaining Under Strategic Uncertainty: The Role of Second‐Order Optimism

Amanda Friedenberg

摘要

This paper shows that bargainers may reach delayed agreements even in environments where there is no uncertainty about payoffs or feasible actions. Under such conditions, delay may arise when bargainers face direct forms of strategic uncertainty—that is, uncertainty about the opponent's play. The paper restricts the nature of this uncertainty in two important ways. First, it assumes on‐path strategic certainty: Bargainers face uncertainty only after surprise moves. Second, it assumes Battigalli and Siniscalchi's (2002) rationality and common strong belief of rationality (RCSBR)—a requirement that bargainers are “strategically sophisticated.” The main result characterizes the set of outcomes consistent with on‐path strategic certainty and RCSBR. It shows that these assumptions allow for delayed agreement, despite the fact that the bargaining environment is one of complete information. The source of delay is second‐order optimism: Bargainers do not put forward “good” offers early in the negotiation process because they fear that doing so will cause the other party to become more optimistic about her future prospects.

JMLR Bayesian Methods · 发表于 2019

Automated Scalable Bayesian Inference via Hilbert Coresets

Trevor Campbell, Tamara Broderick

摘要

The automation of posterior inference in Bayesian data analysis has enabled experts and nonexperts alike to use more sophisticated models, engage in faster exploratory modeling and analysis, and ensure experimental reproducibility. However, standard automated posterior inference algorithms are not tractable at the scale of massive modern data sets, and modifications to make them so are typically model-specific, require expert tuning, and can break theoretical guarantees on inferential quality. Building on the Bayesian coresets framework, this work instead takes advantage of data redundancy to shrink the data set itself as a preprocessing step, providing fully-automated, scalable Bayesian inference with theoretical guarantees. We begin with an intuitive reformulation of Bayesian coreset construction as sparse vector sum approximation, and demonstrate that its automation and performance-based shortcomings arise from the use of the supremum norm. To address these shortcomings we develop Hilbert coresets, i.e., Bayesian coresets constructed under a norm induced by an inner-product on the log-likelihood function space. We propose two Hilbert coreset construction algorithms---one based on importance sampling, and one based on the Frank-Wolfe algorithm---along with theoretical guarantees on approximation quality as a function of coreset size. Since the exact computation of the proposed inner-products is model-specific, we automate the construction with a random finite-dimensional projection of the log-likelihood functions. The resulting automated coreset construction algorithm is simple to implement, and experiments on a variety of models with real and synthetic data sets show that it provides high-quality posterior approximations and a significant reduction in the computational cost of inference.

JMLR Optimization & Learning Theory · 发表于 2019

Approximations of the Restless Bandit Problem

Steffen Grünewälder, Azadeh Khaleghi

摘要

The multi-armed restless bandit problem is studied in the case where the pay-off distributions are stationary $\varphi$-mixing. This version of the problem provides a more realistic model for most real-world applications, but cannot be optimally solved in practice, since it is known to be PSPACE-hard. The objective of this paper is to characterize a sub-class of the problem where good approximate solutions can be found using tractable approaches. Specifically, it is shown that under some conditions on the $\varphi$-mixing coefficients, a modified version of UCB can prove effective. The main challenge is that, unlike in the i.i.d. setting, the distributions of the sampled pay-offs may not have the same characteristics as those of the original bandit arms. In particular, the $\varphi$-mixing property does not necessarily carry over. This is overcome by carefully controlling the effect of a sampling policy on the pay-off distributions. Some of the proof techniques developed in this paper can be more generally used in the context of online sampling under dependence. Proposed algorithms are accompanied with corresponding regret analysis.

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

Approximation Hardness for A Class of Sparse Optimization Problems

Yichen Chen, Yinyu Ye, Mengdi Wang

摘要

In this paper, we consider three typical optimization problems with a convex loss function and a nonconvex sparse penalty or constraint. For the sparse penalized problem, we prove that finding an $\mathcal{O}(n^{c_1}d^{c_2})$-optimal solution to an $n\times d$ problem is strongly NP-hard for any $c_1, c_2\in [0,1)$ such that $c_1+c_2<1$. For two constrained versions of the sparse optimization problem, we show that it is intractable to approximately compute a solution path associated with increasing values of some tuning parameter. The hardness results apply to a broad class of loss functions and sparse penalties. They suggest that one cannot even approximately solve these three problems in polynomial time, unless P $=$ NP.

JMLR Latent Variables & Mixtures · 发表于 2019

Approximation Algorithms for Stochastic Clustering

David G. Harris, Shi Li, Thomas Pensyl, Aravind Srinivasan, Khoa Trinh

摘要

We consider stochastic settings for clustering, and develop provably-good approximation algorithms for a number of these notions. These algorithms yield better approximation ratios compared to the usual deterministic clustering setting. Additionally, they offer a number of advantages including clustering which is fairer and has better long-term behavior for each user. In particular, they ensure that every user is guaranteed to get good service (on average). We also complement some of these with impossibility results.

JMLR Other · 发表于 2019

Approximate Profile Maximum Likelihood

Dmitri S. Pavlichin, Jiantao Jiao, Tsachy Weissman

摘要

We propose an efficient algorithm for approximate computation of the profile maximum likelihood (PML), a variant of maximum likelihood maximizing the probability of observing a sufficient statistic rather than the empirical sample. The PML has appealing theoretical properties, but is difficult to compute exactly. Inspired by observations gleaned from exactly solvable cases, we look for an approximate PML solution, which, intuitively, clumps comparably frequent symbols into one symbol. This amounts to lower-bounding a certain matrix permanent by summing over a subgroup of the symmetric group rather than the whole group during the computation. We extensively experiment with the approximate solution, and the empirical performance of our approach is competitive and sometimes significantly better than state-of-the-art performances for various estimation problems.

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

Analysis of spectral clustering algorithms for community detection: the general bipartite setting

Zhixin Zhou, Arash A.Amini

摘要

We consider spectral clustering algorithms for community detection under a general bipartite stochastic block model (SBM). A modern spectral clustering algorithm consists of three steps: (1) regularization of an appropriate adjacency or Laplacian matrix (2) a form of spectral truncation and (3) a kmeans type algorithm in the reduced spectral domain. We focus on the adjacency-based spectral clustering and for the first step, propose a new data-driven regularization that can restore the concentration of the adjacency matrix even for the sparse networks. This result is based on recent work on regularization of random binary matrices, but avoids using unknown population level parameters, and instead estimates the necessary quantities from the data. We also propose and study a novel variation of the spectral truncation step and show how this variation changes the nature of the misclassification rate in a general SBM. We then show how the consistency results can be extended to models beyond SBMs, such as inhomogeneous random graph models with approximate clusters, including a graphon clustering problem, as well as general sub-Gaussian biclustering. A theme of the paper is providing a better understanding of the analysis of spectral methods for community detection and establishing consistency results, under fairly general clustering models and for a wide regime of degree growths, including sparse cases where the average expected degree grows arbitrarily slowly.

JMLR Optimization & Learning Theory · 发表于 2019

Analysis of Langevin Monte Carlo via Convex Optimization

Alain Durmus, Szymon Majewski, Błażej Miasojedow

摘要

In this paper, we provide new insights on the Unadjusted Langevin Algorithm. We show that this method can be formulated as the first order optimization algorithm for an objective functional defined on the Wasserstein space of order $2$. Using this interpretation and techniques borrowed from convex optimization, we give a non-asymptotic analysis of this method to sample from log-concave smooth target distribution on $\mathbb{R}^d$. Based on this interpretation, we propose two new methods for sampling from a non-smooth target distribution. These new algorithms are natural extensions of the Stochastic Gradient Langevin Dynamics (SGLD) algorithm, which is a popular extension of the Unadjusted Langevin Algorithm for largescale Bayesian inference. Using the optimization perspective, we provide non-asymptotic convergence analysis for the newly proposed methods.

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

An asymptotic analysis of distributed nonparametric methods

Botond Szabó, Harry van Zanten

摘要

We investigate and compare the fundamental performance of several distributed learning methods that have been proposed recently. We do this in the context of a distributed version of the classical signal-in-Gaussian-white-noise model, which serves as a benchmark model for studying performance in this setting. The results show how the design and tuning of a distributed method can have great impact on convergence rates and validity of uncertainty quantification. Moreover, we highlight the difficulty of designing nonparametric distributed procedures that automatically adapt to smoothness.

Econometrica Econometrics & Economics · 发表于 2019

An Equilibrium Model of the African HIV/AIDS Epidemic

Jeremy Greenwood, Philipp Kircher, Cezar Santos, Michèle Tertilt

摘要

Twelve percent of the Malawian population is HIV infected. Eighteen percent of sexual encounters are casual. A condom is used a third of the time. To analyze the Malawian epidemic, a choice‐theoretic general equilibrium search model is constructed. In the developed framework, people select between different sexual practices while knowing the inherent risk. The calibrated model is used to study several policy interventions, namely, ART, circumcision, better condoms, and the treatment of other STDs. The efficacy of public policy depends upon the induced behavioral changes and equilibrium effects. The framework complements the insights from epidemiological studies and small‐scale field experiments.

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

An Efficient Two Step Algorithm for High Dimensional Change Point Regression Models Without Grid Search

Abhishek Kaul, Venkata K. Jandhyala, Stergios B. Fotopoulos

摘要

We propose a two step algorithm based on $\ell_1/\ell_0$ regularization for the detection and estimation of parameters of a high dimensional change point regression model and provide the corresponding rates of convergence for the change point as well as the regression parameter estimates. Importantly, the computational cost of our estimator is only $2\cdotp$Lasso$(n,p)$, where Lasso$(n,p)$ represents the computational burden of one Lasso optimization in a model of size $(n,p)$. In comparison, existing grid search based approaches to this problem require a computational cost of at least $n\cdot Lasso(n,p)$ optimizations. Additionally, the proposed method is shown to be able to consistently detect the case of 'no change', i.e., where no finite change point exists in the model. We allow the true change point parameter $\tau_0$ to possibly move to the boundaries of its parametric space, and the jump size $\|b_0-g_0\|_2$ to possibly diverge as $n$ increases. We then characterize the corresponding effects on the rates of convergence of the change point and regression estimates. In particular, we show that, while an increasing jump size may have a beneficial effect on the change point estimate, however the optimal rate of regression parameter estimates are preserved only upto a certain rate of the increasing jump size. This behavior in the rate of regression parameter estimates is unique to high dimensional change point regression models only. Simulations are performed to empirically evaluate performance of the proposed estimators. The methodology is applied to community level socio-economic data of the U.S., collected from the 1990 U.S. census and other sources.

JMLR High-Dimensional · 发表于 2019

An Approach to One-Bit Compressed Sensing Based on Probably Approximately Correct Learning Theory

Mehmet Eren Ahsen, Mathukumalli Vidyasagar

摘要

In this paper, the problem of one-bit compressed sensing (OBCS) is formulated as a problem in probably approximately correct (PAC) learning. It is shown that the Vapnik-Chervonenkis (VC-) dimension of the set of half-spaces in $\R^n$ generated by $k$-sparse vectors is bounded below by $k ( \lfloor\lg (n/k) \rfloor +1 )$ and above by $\lfloor 2k \lg (en) \rfloor $. By coupling this estimate with well-established results in PAC learning theory, we show that a consistent algorithm can recover a $k$-sparse vector with $O(k \lg n)$ measurements, given only the signs of the measurement vector. This result holds for \textit{all} probability measures on $\R^n$. The theory is also applicable to the case of noisy labels, where the signs of the measurements are flipped with some unknown probability.

JMLR Diagnostics & Prediction · 发表于 2019

All Models are Wrong, but Many are Useful: Learning a Variable's Importance by Studying an Entire Class of Prediction Models Simultaneously

Aaron Fisher, Cynthia Rudin, Francesca Dominici

摘要

Variable importance (VI) tools describe how much covariates contribute to a prediction model's accuracy. However, important variables for one well-performing model (for example, a linear model $f(\mathbf{x})=\mathbf{x}^{T}\beta$ with a fixed coefficient vector $\beta$) may be unimportant for another model. In this paper, we propose model class reliance (MCR) as the range of VI values across all well-performing model in a prespecified class. Thus, MCR gives a more comprehensive description of importance by accounting for the fact that many prediction models, possibly of different parametric forms, may fit the data well. In the process of deriving MCR, we show several informative results for permutation-based VI estimates, based on the VI measures used in Random Forests. Specifically, we derive connections between permutation importance estimates for a single prediction model, U-statistics, conditional variable importance, conditional causal effects, and linear model coefficients. We then give probabilistic bounds for MCR, using a novel, generalizable technique. We apply MCR to a public data set of Broward County criminal records to study the reliance of recidivism prediction models on sex and race. In this application, MCR can be used to help inform VI for unknown, proprietary models.

JMLR Other · 发表于 2019

AffectiveTweets: a Weka Package for Analyzing Affect in Tweets

Felipe Bravo-Marquez, Eibe Frank, Bernhard Pfahringer, Saif M. Mohammad

摘要

AffectiveTweets is a set of programs for analyzing emotion and sentiment of social media messages such as tweets. It is implemented as a package for the Weka machine learning workbench and provides methods for calculating state-of-the-art affect analysis features from tweets that can be fed into machine learning algorithms implemented in Weka. It also implements methods for building affective lexicons and distant supervision methods for training affective models from unlabeled tweets. The package was used by several teams in the shared tasks: EmoInt 2017 and Affect in Tweets SemEval 2018 Task 1.

JMLR Other · 发表于 2019

Adaptive Geometric Multiscale Approximations for Intrinsically Low-dimensional Data

Wenjing Liao, Mauro Maggioni

摘要

We consider the problem of efficiently approximating and encoding high-dimensional data sampled from a probability distribution $\rho$ in $\mathbb{R}^D$, that is nearly supported on a $d$-dimensional set $\mathcal{M}$ - for example supported on a $d$-dimensional manifold. Geometric Multi-Resolution Analysis (GMRA) provides a robust and computationally efficient procedure to construct low-dimensional geometric approximations of $\mathcal{M}$ at varying resolutions. We introduce GMRA approximations that adapt to the unknown regularity of $\mathcal{M}$, by introducing a thresholding algorithm on the geometric wavelet coefficients. We show that these data-driven, empirical geometric approximations perform well, when the threshold is chosen as a suitable universal function of the number of samples $n$, on a large class of measures $\rho$, that are allowed to exhibit different regularity at different scales and locations, thereby efficiently encoding data from more complex measures than those supported on manifolds. These GMRA approximations are associated to a dictionary, together with a fast transform mapping data to $d$-dimensional coefficients, and an inverse of such a map, all of which are data-driven. The algorithms for both the dictionary construction and the transforms have complexity $C D n \log n$ with the constant $C$ exponential in $d$. Our work therefore establishes Adaptive GMRA as a fast dictionary learning algorithm, with approximation guarantees, for intrinsically low-dimensional data. We include several numerical experiments on both synthetic and real data, confirming our theoretical results and demonstrating the effectiveness of Adaptive GMRA.

JMLR Optimization & Learning Theory · 发表于 2019

Adaptation Based on Generalized Discrepancy

Corinna Cortes, Mehryar Mohri, Andrés Muñoz Medina

摘要

We present a new algorithm for domain adaptation improving upon a discrepancy minimization algorithm, (DM), previously shown to outperform a number of algorithms for this problem. Unlike many previously proposed solutions for domain adaptation, our algorithm does not consist of a fixed reweighting of the losses over the training sample. Instead, the reweighting depends on the hypothesis sought. The algorithm is derived from a less conservative notion of discrepancy than the DM algorithm called generalized discrepancy. We present a detailed description of our algorithm and show that it can be formulated as a convex optimization problem. We also give a detailed theoretical analysis of its learning guarantees which helps us select its parameters. Finally, we report the results of experiments demonstrating that it improves upon discrepancy minimization.

JMLR Optimization & Learning Theory · 发表于 2019

Active Learning for Cost-Sensitive Classification

Akshay Krishnamurthy, Alekh Agarwal, Tzu-Kuo Huang, Hal Daumé III, John Langford

摘要

We design an active learning algorithm for cost-sensitive multiclass classification: problems where different errors have different costs. Our algorithm, COAL, makes predictions by regressing to each label's cost and predicting the smallest. On a new example, it uses a set of regressors that perform well on past data to estimate possible costs for each label. It queries only the labels that could be the best, ignoring the sure losers. We prove COAL can be efficiently implemented for any regression family that admits squared loss optimization; it also enjoys strong guarantees with respect to predictive performance and labeling effort. We empirically compare COAL to passive learning and several active learning baselines, showing significant improvements in labeling effort and test cost on real-world datasets.

JMLR Other · 发表于 2019

Accelerated Alternating Projections for Robust Principal Component Analysis

HanQin Cai, Jian-Feng Cai, Ke Wei

摘要

We study robust PCA for the fully observed setting, which is about separating a low rank matrix $\BL$ and a sparse matrix $\BS$ from their sum $\BD=\BL+\BS$. In this paper, a new algorithm, dubbed accelerated alternating projections, is introduced for robust PCA which significantly improves the computational efficiency of the existing alternating projections proposed in (Netrapalli et al., 2014) when updating the low rank factor. The acceleration is achieved by first projecting a matrix onto some low dimensional subspace before obtaining a new estimate of the low rank matrix via truncated SVD. Exact recovery guarantee has been established which shows linear convergence of the proposed algorithm. Empirical performance evaluations establish the advantage of our algorithm over other state-of-the-art algorithms for robust PCA.

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

ADMMBO: Bayesian Optimization with Unknown Constraints using ADMM

Setareh Ariafar, Jaume Coll-Font, Dana Brooks, Jennifer Dy

摘要

There exist many problems in science and engineering that involve optimization of an unknown or partially unknown objective function. Recently, Bayesian Optimization (BO) has emerged as a powerful tool for solving optimization problems whose objective functions are only available as a black box and are expensive to evaluate. Many practical problems, however, involve optimization of an unknown objective function subject to unknown constraints. This is an important yet challenging problem for which, unlike optimizing an unknown function, existing methods face several limitations. In this paper, we present a novel constrained Bayesian optimization framework to optimize an unknown objective function subject to unknown constraints. We introduce an equivalent optimization by augmenting the objective function with constraints, introducing auxiliary variables for each constraint, and forcing the new variables to be equal to the main variable. Building on the Alternating Direction Method of Multipliers (ADMM) algorithm, we propose ADMM-Bayesian Optimization (ADMMBO) to solve the problem in an iterative fashion. Our framework leads to multiple unconstrained subproblems with unknown objective functions, which we then solve via BO. Our method resolves several challenges of state-of-the-art techniques: it can start from infeasible points, is insensitive to initialization, can efficiently handle `decoupled problems' and has a concrete stopping criterion. Extensive experiments on a number of challenging BO benchmark problems show that our proposed approach outperforms the state-of-the-art methods in terms of the speed of obtaining a feasible solution and convergence to the global optimum as well as minimizing the number of total evaluations of unknown objective and constraints functions.

JMLR Other · 发表于 2019

A Well-Tempered Landscape for Non-convex Robust Subspace Recovery

Tyler Maunu, Teng Zhang, Gilad Lerman

摘要

We present a mathematical analysis of a non-convex energy landscape for robust subspace recovery. We prove that an underlying subspace is the only stationary point and local minimizer in a specified neighborhood under a deterministic condition on a dataset. If the deterministic condition is satisfied, we further show that a geodesic gradient descent method over the Grassmannian manifold can exactly recover the underlying subspace when the method is properly initialized. Proper initialization by principal component analysis is guaranteed with a simple deterministic condition. Under slightly stronger assumptions, the gradient descent method with a piecewise constant step-size scheme achieves linear convergence. The practicality of the deterministic condition is demonstrated on some statistical models of data, and the method achieves almost state-of-the-art recovery guarantees on the Haystack Model for different regimes of sample size and ambient dimension. In particular, when the ambient dimension is fixed and the sample size is large enough, we show that our gradient method can exactly recover the underlying subspace for any fixed fraction of outliers (less than 1).

JMLR Networks & Graphs Machine Learning Nonparametric & Semiparametric · 发表于 2019

A Representer Theorem for Deep Neural Networks

Michael Unser

摘要

We propose to optimize the activation functions of a deep neural network by adding a corresponding functional regularization to the cost function. We justify the use of a second-order total-variation criterion. This allows us to derive a general representer theorem for deep neural networks that makes a direct connection with splines and sparsity. Specifically, we show that the optimal network configuration can be achieved with activation functions that are nonuniform linear splines with adaptive knots. The bottom line is that the action of each neuron is encoded by a spline whose parameters (including the number of knots) are optimized during the training procedure. The scheme results in a computational structure that is compatible with existing deep-ReLU, parametric ReLU, APL (adaptive piecewise-linear) and MaxOut architectures. It also suggests novel optimization challenges and makes an explicit link with $\ell_1$ minimization and sparsity-promoting techniques.

JMLR Nonparametric & Semiparametric Machine Learning Networks & Graphs · 发表于 2019

A Representer Theorem for Deep Kernel Learning

Bastian Bohn, Michael Griebel, Christian Rieger

摘要

In this paper we provide a finite-sample and an infinite-sample representer theorem for the concatenation of (linear combinations of) kernel functions of reproducing kernel Hilbert spaces. These results serve as mathematical foundation for the analysis of machine learning algorithms based on compositions of functions. As a direct consequence in the finite-sample case, the corresponding infinite-dimensional minimization problems can be recast into (nonlinear) finite-dimensional minimization problems, which can be tackled with nonlinear optimization algorithms. Moreover, we show how concatenated machine learning problems can be reformulated as neural networks and how our representer theorem applies to a broad class of state-of-the-art deep learning methods.

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

A Particle-Based Variational Approach to Bayesian Non-negative Matrix Factorization

Muhammad A Masood, Finale Doshi-Velez

摘要

Bayesian Non-negative Matrix Factorization (BNMF) is a promising approach for understanding uncertainty and structure in matrix data. However, a large volume of applied work optimizes traditional non-Bayesian NMF objectives that fail to provide a principled understanding of the non-identifiability inherent in NMF---an issue ideally addressed by a Bayesian approach. Despite their suitability, current BNMF approaches have failed to gain popularity in an applied setting; they sacrifice flexibility in modeling for tractable computation, tend to get stuck in local modes, and can require many thousands of samples for meaningful uncertainty estimates. We address these issues through a particle-based variational approach to BNMF that only requires the joint likelihood to be differentiable for computational tractability, uses a novel transfer-based initialization technique to identify multiple modes in the posterior, and thus allows domain experts to inspect a small set of factorizations that faithfully represent the posterior. On several real datasets, we obtain better particle approximations to the BNMF posterior in less time than baselines and demonstrate the significant role that multimodality plays in NMF-related tasks.

Econometrica Other · 发表于 2019

A Note on Arrow-Enthoven's Sufficiency Theorem on Quasi-Concave Programming: Corrigendum to: Quasi-Concave Programming

Ludovic A. Julien

摘要

In this note, we reconsider Arrow–Enthoven’s (1961) Sufficiency Theorem 1 onquasi-concave programming [Econometrica, 29(4), p. 783]. One example illustrates thefact that condition (c) of their Theorem 1 should include the twice continuous differen-tiability of the quasi-concave objective function so that the conditions of the theoremare sufficient to identify global optima. *(abstract via OpenAlex)*

Econometrica Bayesian Methods · 发表于 2019

A Non‐Bayesian Theory of State‐Dependent Utility

Brian Hill

摘要

Many decision situations involve two or more of the following divergences from subjective expected utility: imprecision of beliefs (or ambiguity), imprecision of tastes (or multi‐utility), and state dependence of utility. This paper proposes and characterizes a model of uncertainty averse preferences that can simultaneously incorporate all three phenomena. The representation supports a principled separation of (imprecise) beliefs and (potentially state‐dependent, imprecise) tastes. Moreover, the representation permits comparative statics separating the roles of beliefs and tastes, and is modular: it easily delivers special cases involving various combinations of the phenomena, as well as state‐dependent multi‐utility generalizations covering popular ambiguity models.

JMLR Networks & Graphs · 发表于 2019

A New Approach to Laplacian Solvers and Flow Problems

Patrick Rebeschini, Sekhar Tatikonda

摘要

This paper investigates the behavior of the Min-Sum message passing scheme to solve systems of linear equations in the Laplacian matrices of graphs and to compute electric flows. Voltage and flow problems involve the minimization of quadratic functions and are fundamental primitives that arise in several domains. Algorithms that have been proposed are typically centralized and involve multiple graph-theoretic constructions or sampling mechanisms that make them difficult to implement and analyze. On the other hand, message passing routines are distributed, simple, and easy to implement. In this paper we establish a framework to analyze Min-Sum to solve voltage and flow problems. We characterize the error committed by the algorithm on general weighted graphs in terms of hitting times of random walks defined on the computation trees that support the operations of the algorithms with time. For $d$-regular graphs with equal weights, we show that the convergence of the algorithms is controlled by the total variation distance between the distributions of non-backtracking random walks defined on the original graph that start from neighboring nodes. The framework that we introduce extends the analysis of Min-Sum to settings where the contraction arguments previously considered in the literature (based on the assumption of walk summability or scaled diagonal dominance) can not be used, possibly in the presence of constraints.

JMLR Spatial & Time Series Nonparametric & Semiparametric · 发表于 2019

A Kernel Multiple Change-point Algorithm via Model Selection

Sylvain Arlot, Alain Celisse, Zaid Harchaoui

摘要

We consider a general formulation of the multiple change-point problem, in which the data is assumed to belong to a set equipped with a positive semidefinite kernel. We propose a model-selection penalty allowing to select the number of change points in Harchaoui and Cappé's kernel-based change-point detection method. The model-selection penalty generalizes non-asymptotic model-selection penalties for the change-in-mean problem with univariate data. We prove a non-asymptotic oracle inequality for the resulting kernel-based change-point detection method, whatever the unknown number of change points, thanks to a concentration result for Hilbert-space valued random variables which may be of independent interest. Experiments on synthetic and real data illustrate the proposed method, demonstrating its ability to detect subtle changes in the distribution of data.

Econometrica Other · 发表于 2019

A Distributional Framework for Matched Employer Employee Data

Stéphane Bonhomme, Thibaut Lamadon, Elena Manresa

摘要

We propose a framework to identify and estimate earnings distributions and worker composition on matched panel data, allowing for two‐sided worker‐firm unobserved heterogeneity and complementarities in earnings. We introduce two models: a static model that allows for nonlinear interactions between workers and firms, and a dynamic model that allows, in addition, for Markovian earnings dynamics and endogenous mobility. We show that this framework nests a number of structural models of wages and worker mobility. We establish identification in short panels, and develop tractable two‐step estimators where firms are classified in a first step. Applying our method to Swedish administrative data, we find that log‐earnings are approximately additive in worker and firm heterogeneity. Our estimates imply the presence of strong sorting patterns between workers and firms, and a small contribution of firms—net of worker composition—to earnings dispersion. In addition, we document that wages have a direct effect on mobility, and that, beyond their dependence on the current firm, earnings after a job move also depend on the previous employer.

JMLR Testing & Uncertainty · 发表于 2019

A Bootstrap Method for Error Estimation in Randomized Matrix Multiplication

Miles E. Lopes, Shusen Wang, Michael W. Mahoney

摘要

In recent years, randomized methods for numerical linear algebra have received growing interest as a general approach to large-scale problems. Typically, the essential ingredient of these methods is some form of randomized dimension reduction, which accelerates computations, but also creates random approximation error. In this way, the dimension reduction step encodes a tradeoff between cost and accuracy. However, the exact numerical relationship between cost and accuracy is typically unknown, and consequently, it may be difficult for the user to precisely know (1) how accurate a given solution is, or (2) how much computation is needed to achieve a given level of accuracy. In the current paper, we study randomized matrix multiplication (sketching) as a prototype setting for addressing these general problems. As a solution, we develop a bootstrap method for directly estimating the accuracy as a function of the reduced dimension (as opposed to deriving worst-case bounds on the accuracy in terms of the reduced dimension). From a computational standpoint, the proposed method does not substantially increase the cost of standard sketching methods, and this is made possible by an “extrapolation” technique. In addition, we provide both theoretical and empirical results to demonstrate the effectiveness of the proposed method.

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