2018 年的期刊文章 · 第 29 页

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

按期刊、按主题看 →

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

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

Scalable Bayes via Barycenter in Wasserstein Space

Sanvesh Srivastava, Cheng Li, David B. Dunson

摘要

Divide-and-conquer based methods for Bayesian inference provide a general approach for tractable posterior inference when the sample size is large. These methods divide the data into smaller subsets, sample from the posterior distribution of parameters in parallel on all the subsets, and combine posterior samples from all the subsets to approximate the full data posterior distribution. The smaller size of any subset compared to the full data implies that posterior sampling on any subset is computationally more efficient than sampling from the true posterior distribution. Since the combination step takes negligible time relative to sampling, posterior computations can be scaled to massive data by dividing the full data into sufficiently large number of data subsets. One such approach relies on the geometry of posterior distributions estimated across different subsets and combines them through their barycenter in a Wasserstein space of probability measures. We provide theoretical guarantees on the accuracy of approximation that are valid in many applications. We show that the geometric method approximates the full data posterior distribution better than its competitors across diverse simulations and reproduces known results when applied to a movie ratings database.

Econometrica Econometrics & Economics · 发表于 2018

Saving and Dissaving With Hyperbolic Discounting

Dan Cao, Iván Werning

摘要

Is the standard hyperbolic-discounting model capable of robust qualitative predictions for savings behavior?Despite results suggesting a negative answer, we provide a positive one.We give conditions under which all Markov equilibria display either saving at all wealth levels or dissaving at all wealth levels.Moreover, saving versus dissaving is determined by a simple condition comparing the interest rate to a threshold made up of impatience parameters only.Our robustness results illustrate a well-behaved side of the model and imply that qualitative behavior is determinate, dissipating indeterminacy concerns to the contrary (Krusell and Smith, 2003).We prove by construction that equilibria always exist and that multiplicity is present in some cases, highlighting that our robust predictions are not due to uniqueness.Similar results may be obtainable in related dynamic games, such as political economy models of public spending. *(abstract via OpenAlex)*

JMLR Nonparametric & Semiparametric High-Dimensional · 发表于 2018

Saturating Splines and Feature Selection

Nicholas Boyd, Trevor Hastie, Stephen Boyd, Benjamin Recht, Michael I. Jordan

摘要

We extend the adaptive regression spline model by incorporating saturation, the natural requirement that a function extend as a constant outside a certain range. We fit saturating splines to data via a convex optimization problem over a space of measures, which we solve using an efficient algorithm based on the conditional gradient method. Unlike many existing approaches, our algorithm solves the original infinite- dimensional (for splines of degree at least two) optimization problem without pre-specified knot locations. We then adapt our algorithm to fit generalized additive models with saturating splines as coordinate functions and show that the saturation requirement allows our model to simultaneously perform feature selection and nonlinear function fitting. Finally, we briefly sketch how the method can be extended to higher order splines and to different requirements on the extension outside the data range.

JMLR Optimization & Learning Theory · 发表于 2018

SGDLibrary: A MATLAB library for stochastic optimization algorithms

Hiroyuki Kasai

摘要

We consider the problem of finding the minimizer of a function $f: \mathbb{R}^d \rightarrow \mathbb{R}$ of the finite-sum form $\min f(w) = 1/n\sum_{i}^n f_i(w)$. This problem has been studied intensively in recent years in the field of machine learning (ML). One promising approach for large-scale data is to use a stochastic optimization algorithm to solve the problem. SGDLibrary is a readable, flexible and extensible pure-MATLAB library of a collection of stochastic optimization algorithms. The purpose of the library is to provide researchers and implementers a comprehensive evaluation environment for the use of these algorithms on various ML problems.

JMLR Nonparametric & Semiparametric · 发表于 2018

Robust Topological Inference: Distance To a Measure and Kernel Distance

Frédéric Chazal, Brittany Fasy, Fabrizio Lecci, Bertrand Michel, Alessandro Rinaldo, Larry Wasserman

摘要

Let $P$ be a distribution with support $S$. The salient features of $S$ can be quantified with persistent homology, which summarizes topological features of the sublevel sets of the distance function (the distance of any point $x$ to $S$). Given a sample from $P$ we can infer the persistent homology using an empirical version of the distance function. However, the empirical distance function is highly non-robust to noise and outliers. Even one outlier is deadly. The distance-to-a-measure (DTM), introduced by \cite{chazal2011geometric}, and the kernel distance, introduced by \cite{phillips2014goemetric}, are smooth functions that provide useful topological information but are robust to noise and outliers. \cite{massart2014} derived concentration bounds for DTM. Building on these results, we derive limiting distributions and confidence sets, and we propose a method for choosing tuning parameters.

JMLR Causal Inference · 发表于 2018

Robust Synthetic Control

Muhammad Amjad, Devavrat Shah, Dennis Shen

摘要

We present a robust generalization of the synthetic control method for comparative case studies. Like the classical method cf. \cite{abadie3}, we present an algorithm to estimate the unobservable counterfactual of a treatment unit. A distinguishing feature of our algorithm is that of de-noising the data matrix via singular value thresholding, which renders our approach robust in multiple facets: it automatically identifies a good subset of donors for the synthetic control, overcomes the challenges of missing data, and continues to work well in settings where covariate information may not be provided. We posit that the setting can be viewed as an instance of the Latent Variable Model and provide the first finite sample analysis (coupled with asymptotic results) for the estimation of the counterfactual. Our algorithm accurately imputes missing entries and filters corrupted observations in producing a consistent estimator of the underlying signal matrix, provided $p = \Omega( T^{-1 + \zeta})$ for some $\zeta > 0$; here, $p$ is the fraction of observed data and $T$ is the time interval of interest. Under the same proportion of observations, we demonstrate that the mean-squared error in our counterfactual estimation scales as $\mathcal{O}(\sigma^2/p + 1/\sqrt{T})$, where $\sigma^2$ is the variance of the inherent noise. Additionally, we introduce a Bayesian framework to quantify the estimation uncertainty. Our experiments, using both synthetic and real-world datasets, demonstrate that our robust generalization yields an improvement over the classical synthetic control method.

JMLR Optimization & Learning Theory · 发表于 2018

Robust PCA by Manifold Optimization

Teng Zhang, Yi Yang

摘要

Robust PCA is a widely used statistical procedure to recover an underlying low-rank matrix with grossly corrupted observations. This work considers the problem of robust PCA as a nonconvex optimization problem on the manifold of low-rank matrices and proposes two algorithms based on manifold optimization. It is shown that, with a properly designed initialization, the proposed algorithms are guaranteed to converge to the underlying low-rank matrix linearly. Compared with a previous work based on the factorization of low-rank matrices Yi et al. (2016), the proposed algorithms reduce the dependence on the condition number of the underlying low-rank matrix theoretically. Simulations and real data examples confirm the competitive performance of our method.

Econometrica Econometrics & Economics · 发表于 2018

Robust Mechanisms Under Common Valuation

Songzi Du

摘要

I construct an informationally robust auction to sell a common‐value good. I examine the revenue guarantee of an auction over all information structures of bidders and all equilibria. As the number of bidders gets large, the revenue guarantee of my auction converges to the full surplus, regardless of how information changes as more bidders are added. My auction also maximizes the revenue guarantee when there is a single bidder. *(abstract via OpenAlex)*

JMLR Machine Learning · 发表于 2018

Risk-Constrained Reinforcement Learning with Percentile Risk Criteria

Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, Marco Pavone

摘要

In many sequential decision-making problems one is interested in minimizing an expected cumulative cost while taking into account risk, i.e., increased awareness of events of small probability and high consequences. Accordingly, the objective of this paper is to present efficient reinforcement learning algorithms for risk-constrained Markov decision processes (MDPs), where risk is represented via a chance constraint or a constraint on the conditional value-at-risk (CVaR) of the cumulative cost. We collectively refer to such problems as percentile risk-constrained MDPs. Specifically, we first derive a formula for computing the gradient of the Lagrangian function for percentile risk-constrained MDPs. Then, we devise policy gradient and actor-critic algorithms that (1) estimate such gradient, (2) update the policy in the descent direction, and (3) update the Lagrange multiplier in the ascent direction. For these algorithms we prove convergence to locally optimal policies. Finally, we demonstrate the effectiveness of our algorithms in an optimal stopping problem and an online marketing application.

Econometrica Econometrics & Economics · 发表于 2018

Risk Preferences and the Macroeconomic Announcement Premium

Hengjie Ai, Ravi Bansal

摘要

Empirical evidence shows that a large fraction of equity premium is realized on a relatively small number of trading days with significant macroeconomic news announcements. In the 1961-2014 period, for example, about 55% of the entire equity premium is earned on about 30 trading days per year with significant macroeconomic announcements. In addition, the market equity premium typically rises prior to the announcement and falls immediately afterwards. In this paper, we develop an abstract theory and a quantitative model for the equity premium associated with macroeconomic news announcements. We demonstrate that the announcement premium identifies the compensation for investors’ uncertainty aversion on capital markets. We present a dynamic model to account for the evolution of equity premium around macroeconomic announcements. *(abstract via OpenAlex)*

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

Reward Maximization Under Uncertainty: Leveraging Side-Observations on Networks

Swapna Buccapatnam, Fang Liu, Atilla Eryilmaz, Ness B. Shroff

摘要

We study the stochastic multi-armed bandit (MAB) problem in the presence of side-observations across actions that occur as a result of an underlying network structure. In our model, a bipartite graph captures the relationship between actions and a common set of unknowns such that choosing an action reveals observations for the unknowns that it is connected to. This models a common scenario in online social networks where users respond to their friends' activity, thus providing side information about each other's preferences. Our contributions are as follows: 1) We derive an asymptotic lower bound (with respect to time) as a function of the bi-partite network structure on the regret of any uniformly good policy that achieves the maximum long-term average reward. 2) We propose two policies - a randomized policy; and a policy based on the well- known upper confidence bound (UCB) policies - both of which explore each action at a rate that is a function of its network position. We show, under mild assumptions, that these policies achieve the asymptotic lower bound on the regret up to a multiplicative factor, independent of the network structure. Finally, we use numerical examples on a real-world social network and a routing example network to demonstrate the benefits obtained by our policies over other existing policies.

JMLR Other · 发表于 2018

Reverse Iterative Volume Sampling for Linear Regression

Michał Dereziński, Manfred K. Warmuth

摘要

We study the following basic machine learning task: Given a fixed set of input points in $\mathbb{R}^d$ for a linear regression problem, we wish to predict a hidden response value for each of the points. We can only afford to attain the responses for a small subset of the points that are then used to construct linear predictions for all points in the dataset. The performance of the predictions is evaluated by the total square loss on all responses (the attained as well as the remaining hidden ones). We show that a good approximate solution to this least squares problem can be obtained from just dimension $d$ many responses by using a joint sampling technique called volume sampling. Moreover, the least squares solution obtained for the volume sampled subproblem is an unbiased estimator of optimal solution based on all $n$ responses. This unbiasedness is a desirable property that is not shared by other common subset selection techniques. Motivated by these basic properties, we develop a theoretical framework for studying volume sampling, resulting in a number of new matrix expectation equalities and statistical guarantees which are of importance not only to least squares regression but also to numerical linear algebra in general. Our methods also lead to a regularized variant of volume sampling, and we propose the first efficient algorithm for volume sampling which makes this technique a practical tool in the machine learning toolbox. Finally, we provide experimental evidence which confirms our theoretical findings.

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

Regularized Optimal Transport and the Rot Mover's Distance

Arnaud Dessein, Nicolas Papadakis, Jean-Luc Rouas

摘要

This paper presents a unified framework for smooth convex regularization of discrete optimal transport problems. In this context, the regularized optimal transport turns out to be equivalent to a matrix nearness problem with respect to Bregman divergences. Our framework thus naturally generalizes a previously proposed regularization based on the Boltzmann-Shannon entropy related to the Kullback-Leibler divergence, and solved with the Sinkhorn-Knopp algorithm. We call the regularized optimal transport distance the rot mover's distance in reference to the classical earth mover's distance. By exploiting alternate Bregman projections, we develop the alternate scaling algorithm and non-negative alternate scaling algorithm, to compute efficiently the regularized optimal plans depending on whether the domain of the regularizer lies within the non-negative orthant or not. We further enhance the separable case with a sparse extension to deal with high data dimensions. We also instantiate our framework and discuss the inherent specificities for well-known regularizers and statistical divergences in the machine learning and information geometry communities. Finally, we demonstrate the merits of our methods with experiments using synthetic data to illustrate the effect of different regularizers, penalties and dimensions, as well as real-world data for a pattern recognition application to audio scene classification.

JMLR Optimization & Learning Theory · 发表于 2018

Refining the Confidence Level for Optimistic Bandit Strategies

Tor Lattimore

摘要

This paper introduces the first strategy for stochastic bandits with unit variance Gaussian noise that is simultaneously minimax optimal up to constant factors, asymptotically optimal, and never worse than the classical upper confidence bound strategy up to universal constant factors. Preliminary empirical evidence is also promising. Besides this, a conjecture on the optimal form of the regret is shown to be false and a finite-time lower bound on the regret of any strategy is presented that very nearly matches the finite-time upper bound of the newly proposed strategy.

JMLR Other · 发表于 2018

Rate of Convergence of $k$-Nearest-Neighbor Classification Rule

Maik Döring, László Györfi, Harro Walk

摘要

A binary classification problem is considered. The excess error probability of the $k$-nearest-neighbor classification rule according to the error probability of the Bayes decision is revisited by a decomposition of the excess error probability into approximation and estimation errors. Under a weak margin condition and under a modified Lipschitz condition or a local Lipschitz condition, tight upper bounds are presented such that one avoids the condition that the feature vector is bounded. The concept of modified Lipschitz condition is applied for discrete distributions, too. As a consequence of both concepts, we present the rate of convergence of $L_2$ error for the corresponding nearest neighbor regression estimate.

JMLR Machine Learning · 发表于 2018

Random Forests, Decision Trees, and Categorical Predictors: The "Absent Levels" Problem

Timothy C. Au

摘要

One advantage of decision tree based methods like random forests is their ability to natively handle categorical predictors without having to first transform them (e.g., by using feature engineering techniques). However, in this paper, we show how this capability can lead to an inherent “absent levels” problem for decision tree based methods that has never been thoroughly discussed, and whose consequences have never been carefully explored. This problem occurs whenever there is an indeterminacy over how to handle an observation that has reached a categorical split which was determined when the observation in question's level was absent during training. Although these incidents may appear to be innocuous, by using Leo Breiman and Adele Cutler's random forests FORTRAN code and the randomForest R package (Liaw and Wiener, 2002) as motivating case studies, we examine how overlooking the absent levels problem can systematically bias a model. Furthermore, by using three real data examples, we illustrate how absent levels can dramatically alter a model's performance in practice, and we empirically demonstrate how some simple heuristics can be used to help mitigate the effects of the absent levels problem until a more robust theoretical solution is found.

JMLR Other · 发表于 2018

RSG: Beating Subgradient Method without Smoothness and Strong Convexity

Tianbao Yang, Qihang Lin

摘要

In this paper, we study the efficiency of a Restarted SubGradient (RSG) method that periodically restarts the standard subgradient method (SG). We show that, when applied to a broad class of convex optimization problems, RSG method can find an $\epsilon$-optimal solution with a lower complexity than the SG method. In particular, we first show that RSG can reduce the dependence of SG's iteration complexity on the distance between the initial solution and the optimal set to that between the $\epsilon$-level set and the optimal set {multiplied by a logarithmic factor}. Moreover, we show the advantages of RSG over SG in solving a broad family of problems that satisfy a local error bound condition, and also demonstrate its advantages for three specific families of convex optimization problems with different power constants in the local error bound condition. (a) For the problems whose epigraph is a polyhedron, RSG is shown to converge linearly. (b) For the problems with local quadratic growth property in the $\epsilon$-sublevel set, RSG has an $O(\frac{1}{\epsilon}\log(\frac{1}{\epsilon}))$ iteration complexity. (c) For the problems that admit a local Kurdyka-Łojasiewicz property with a power constant of $\beta\in[0,1)$, RSG has an $O(\frac{1}{\epsilon^{2\beta}}\log(\frac{1}{\epsilon}))$ iteration complexity. The novelty of our analysis lies at exploiting the lower bound of the first-order optimality residual at the $\epsilon$-level set. It is this novelty that allows us to explore the local properties of functions (e.g., local quadratic growth property, local Kurdyka-\L ojasiewicz property, more generally local error bound conditions) to develop the improved convergence of RSG. We also develop a practical variant of RSG enjoying faster convergence than the SG method, which can be run without knowing the involved parameters in the local error bound condition. We demonstrate the effectiveness of the proposed algorithms on several machine learning tasks including regression, classification and matrix completion.

JMLR Machine Learning Networks & Graphs · 发表于 2018

Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations

Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, Yoshua Bengio

摘要

We introduce a method to train Quantized Neural Networks (QNNs) --- neural networks with extremely low precision (e.g., 1-bit) weights and activations, at run-time. At train-time the quantized weights and activations are used for computing the parameter gradients. During the forward pass, QNNs drastically reduce memory size and accesses, and replace most arithmetic operations with bit-wise operations. As a result, power consumption is expected to be drastically reduced. We trained QNNs over the MNIST, CIFAR-10, SVHN and ImageNet datasets. The resulting QNNs achieve prediction accuracy comparable to their 32-bit counterparts. For example, our quantized version of AlexNet with 1-bit weights and 2-bit activations achieves $51\%$ top-1 accuracy. Moreover, we quantize the parameter gradients to 6-bits as well which enables gradients computation using only bit-wise operation. Quantized recurrent neural networks were tested over the Penn Treebank dataset, and achieved comparable accuracy as their 32-bit counterparts using only 4-bits. Last but not least, we programmed a binary matrix multiplication GPU kernel with which it is possible to run our MNIST QNN 7 times faster than with an unoptimized GPU kernel, without suffering any loss in classification accuracy. The QNN code is available online.

JMLR Other · 发表于 2018

Pycobra: A Python Toolbox for Ensemble Learning and Visualisation

Benjamin Guedj, Bhargav Srinivasa Desikan

摘要

We introduce pycobra, a Python library devoted to ensemble learning (regression and classification) and visualisation. Its main assets are the implementation of several ensemble learning algorithms, a flexible and generic interface to compare and blend any existing machine learning algorithm available in Python libraries (as long as a predict method is given), and visualisation tools such as Voronoi tessellations. pycobra is fully scikit-learn compatible and is released under the MIT open-source license. pycobra can be downloaded from the Python Package Index (PyPi) and Machine Learning Open Source Software (MLOSS). The current version (along with Jupyter notebooks, extensive documentation, and continuous integration tests) is available at https://github.com/bhargavvader/pycobra and official documentation website is https://modal.lille.inria.fr/pycobra.

Econometrica Econometrics & Economics · 发表于 2018

Provider Incentives and Healthcare Costs: Evidence From Long-Term Care Hospitals

Liran Einav, Amy Finkelstein, Neale Mahoney

摘要

We study the design of provider incentives in the post-acute care setting - a high-stakes but under-studied segment of the healthcare system. We focus on long-term care hospitals (LTCHs) and the large (approximately $13,500) jump in Medicare payments they receive when a patient s stay reaches a threshold number of days. Discharges increase substantially after the threshold, with the marginal discharged patient in relatively better health. Despite the large financial incentives and behavioral response in a high mortality population, we are unable to detect any compelling evidence of an impact on patient mortality. To assess provider behavior under counterfactual payment schedules, we estimate a simple dynamic discrete choice model of LTCH discharge decisions. When we conservatively limit ourselves to alternative contracts that hold the LTCH harmless, we find that an alternative contract can generate Medicare savings of about $2,100 per admission, or about 5% of total payments. More aggressive payment reforms can generate substantially greater savings, but the accompanying reduction in LTCH profits has potential out-of-sample consequences. Our results highlight how improved financial incentives may be able to reduce healthcare spending, without negative consequences for industry profits or patient health. *(abstract via PubMed)*

JMLR Other · 发表于 2018

Provably Correct Algorithms for Matrix Column Subset Selection with Selectively Sampled Data

Yining Wang, Aarti Singh

摘要

We consider the problem of matrix column subset selection, which selects a subset of columns from an input matrix such that the input can be well approximated by the span of the selected columns. Column subset selection has been applied to numerous real-world data applications such as population genetics summarization, electronic circuits testing and recommendation systems. In many applications the complete data matrix is unavailable and one needs to select representative columns by inspecting only a small portion of the input matrix. In this paper we propose the first provably correct column subset selection algorithms for partially observed data matrices. Our proposed algorithms exhibit different merits and limitations in terms of statistical accuracy, computational efficiency, sample complexity and sampling schemes, which provides a nice exploration of the tradeoff between these desired properties for column subset selection. The proposed methods employ the idea of feedback driven sampling and are inspired by several sampling schemes previously introduced for low-rank matrix approximation tasks (Drineas et al., 2008; Frieze et al., 2004; Deshpande and Vempala, 2006; Krishnamurthy and Singh, 2014). Our analysis shows that, under the assumption that the input data matrix has incoherent rows but possibly coherent columns, all algorithms provably converge to the best low-rank approximation of the original data as number of selected columns increases. Furthermore, two of the proposed algorithms enjoy a relative error bound, which is preferred for column subset selection and matrix approximation purposes. We also demonstrate through both theoretical and empirical analysis the power of feedback driven sampling compared to uniform random sampling on input matrices with highly correlated columns.

JMLR Optimization & Learning Theory · 发表于 2018

Profile-Based Bandit with Unknown Profiles

Sylvain Lamprier, Thibault Gisselbrecht, Patrick Gallinari

摘要

Stochastic bandits have been widely studied since decades. A very large panel of settings have been introduced, some of them for the inclusion of some structure between actions. If actions are associated with feature vectors that underlie their usefulness, the discovery of a mapping parameter between such profiles and rewards can help the exploration process of the bandit strategies. This is the setting studied in this paper, but in our case the action profiles (constant feature vectors) are unknown beforehand. Instead, the agent is only given sample vectors, with mean centered on the true profiles, for a subset of actions at each step of the process. In this new bandit instance, policies have thus to deal with a doubled uncertainty, both on the profile estimators and the reward mapping parameters learned so far. We propose a new algorithm, called \textit{SampLinUCB}, specifically designed for this case. Theoretical convergence guarantees are given for this strategy, according to various profile samples delivery scenarios. Finally, experiments are conducted on both artificial data and a task of focused data capture from online social networks. Obtained results demonstrate the relevance of the approach in various settings.

JMLR Other · 发表于 2018

Probabilistic preference learning with the Mallows rank model

Valeria Vitelli, Øystein Sørensen, Marta Crispino, Arnoldo Frigessi, Elja Arjas

摘要

Ranking and comparing items is crucial for collecting information about preferences in many areas, from marketing to politics. The Mallows rank model is among the most successful approaches to analyse rank data, but its computational complexity has limited its use to a particular form based on Kendall distance. We develop new computationally tractable methods for Bayesian inference in Mallows models that work with any right-invariant distance. Our method performs inference on the consensus ranking of the items, also when based on partial rankings, such as top-$k$ items or pairwise comparisons. We prove that items that none of the assessors has ranked do not influence the maximum a posteriori consensus ranking, and can therefore be ignored. When assessors are many or heterogeneous, we propose a mixture model for clustering them in homogeneous subgroups, with cluster-specific consensus rankings. We develop approximate stochastic algorithms that allow a fully probabilistic analysis, leading to coherent quantifications of uncertainties. We make probabilistic predictions on the class membership of assessors based on their ranking of just some items, and predict missing individual preferences, as needed in recommendation systems. We test our approach using several experimental and benchmark datasets.

JMLR Latent Variables & Mixtures Bayesian Methods · 发表于 2018

Principled Selection of Hyperparameters in the Latent Dirichlet Allocation Model

Clint P. George, Hani Doss

摘要

Latent Dirichlet Allocation (LDA) is a well known topic model that is often used to make inference regarding the properties of collections of text documents. LDA is a hierarchical Bayesian model, and involves a prior distribution on a set of latent topic variables. The prior is indexed by certain hyperparameters, and even though these have a large impact on inference, they are usually chosen either in an ad-hoc manner, or by applying an algorithm whose theoretical basis has not been firmly established. We present a method, based on a combination of Markov chain Monte Carlo and importance sampling, for estimating the maximum likelihood estimate of the hyperparameters. The method may be viewed as a computational scheme for implementation of an empirical Bayes analysis. It comes with theoretical guarantees, and a key feature of our approach is that we provide theoretically-valid error margins for our estimates. Experiments on both synthetic and real data show good performance of our methodology.

JMLR Networks & Graphs High-Dimensional Nonparametric & Semiparametric · 发表于 2018

Post-Regularization Inference for Time-Varying Nonparanormal Graphical Models

Junwei Lu, Mladen Kolar, Han Liu

摘要

We propose a novel class of time-varying nonparanormal graphical models, which allows us to model high dimensional heavy-tailed systems and the evolution of their latent network structures. Under this model we develop statistical tests for presence of edges both locally at a fixed index value and globally over a range of values. The tests are developed for a high-dimensional regime, are robust to model selection mistakes and do not require commonly assumed minimum signal strength. The testing procedures are based on a high dimensional, debiasing-free moment estimator, which uses a novel kernel smoothed Kendall's tau correlation matrix as an input statistic. The estimator consistently estimates the latent inverse Pearson correlation matrix uniformly in both the index variable and kernel bandwidth. Its rate of convergence is shown to be minimax optimal. Our method is supported by thorough numerical simulations and an application to a neural imaging data set.

JMLR Bayesian Methods · 发表于 2018

Permuted and Augmented Stick-Breaking Bayesian Multinomial Regression

Quan Zhang, Mingyuan Zhou

摘要

To model categorical response variables given their covariates, we propose a permuted and augmented stick-breaking (paSB) construction that one-to-one maps the observed categories to randomly permuted latent sticks. This new construction transforms multinomial regression into regression analysis of stick-specific binary random variables that are mutually independent given their covariate-dependent stick success probabilities, which are parameterized by the regression coefficients of their corresponding categories. The paSB construction allows transforming an arbitrary cross-entropy-loss binary classifier into a Bayesian multinomial one. Specifically, we parameterize the negative logarithms of the stick failure probabilities with a family of covariate-dependent softplus functions to construct nonparametric Bayesian multinomial softplus regression, and transform Bayesian support vector machine (SVM) into Bayesian multinomial SVM. These Bayesian multinomial regression models are not only capable of providing probability estimates, quantifying uncertainty, increasing robustness, and producing nonlinear classification decision boundaries, but also amenable to posterior simulation. Example results demonstrate their attractive properties and performance.

JMLR Other · 发表于 2018

Patchwork Kriging for Large-scale Gaussian Process Regression

Chiwoo Park, Daniel Apley

摘要

This paper presents a new approach for Gaussian process (GP) regression for large datasets. The approach involves partitioning the regression input domain into multiple local regions with a different local GP model fitted in each region. Unlike existing local partitioned GP approaches, we introduce a technique for patching together the local GP models nearly seamlessly to ensure that the local GP models for two neighboring regions produce nearly the same response prediction and prediction error variance on the boundary between the two regions. This largely mitigates the well-known discontinuity problem that degrades the prediction accuracy of existing local partitioned GP methods over regional boundaries. Our main innovation is to represent the continuity conditions as additional pseudo-observations that the differences between neighboring GP responses are identically zero at an appropriately chosen set of boundary input locations. To predict the response at any input location, we simply augment the actual response observations with the pseudo-observations and apply standard GP prediction methods to the augmented data. In contrast to heuristic continuity adjustments, this has an advantage of working within a formal GP framework, so that the GP-based predictive uncertainty quantification remains valid. Our approach also inherits a sparse block-like structure for the sample covariance matrix, which results in computationally efficient closed-form expressions for the predictive mean and variance. In addition, we provide a new spatial partitioning scheme based on a recursive space partitioning along local principal component directions, which makes the proposed approach applicable for regression domains having more than two dimensions. Using three spatial datasets and three higher dimensional datasets, we investigate the numerical performance of the approach and compare it to several state-of-the-art approaches.

JMLR Optimization & Learning Theory · 发表于 2018

Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification

Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Aaron Sidford

摘要

This work characterizes the benefits of averaging techniques widely used in conjunction with stochastic gradient descent (SGD). In particular, this work presents a sharp analysis of: (1) mini-batching, a method of averaging many samples of a stochastic gradient to both reduce the variance of a stochastic gradient estimate and for parallelizing SGD and (2) tail- averaging, a method involving averaging the final few iterates of SGD in order to decrease the variance in SGD's final iterate. This work presents sharp finite sample generalization error bounds for these schemes for the stochastic approximation problem of least squares regression.

JMLR Nonparametric & Semiparametric · 发表于 2018

Parallelizing Spectrally Regularized Kernel Algorithms

Nicole Mücke, Gilles Blanchard

摘要

We consider a distributed learning approach in supervised learning for a large class of spectral regularization methods in an reproducing kernel Hilbert space (RKHS) framework. The data set of size $n$ is partitioned into $m=O(n^\alpha)$, $\alpha < \frac{1}{2}$, disjoint subsamples. On each subsample, some spectral regularization method (belonging to a large class, including in particular Kernel Ridge Regression, $L^2$-boosting and spectral cut-off) is applied. The regression function $f$ is then estimated via simple averaging, leading to a substantial reduction in computation time. We show that minimax optimal rates of convergence are preserved if $m$ grows sufficiently slowly (corresponding to an upper bound for $\alpha$) as $n \to \infty$, depending on the smoothness assumptions on $f$ and the intrinsic dimensionality. In spirit, the analysis relies on a classical bias/stochastic error analysis.

Econometrica Nonparametric & Semiparametric · 发表于 2018

Overidentification in Regular Models

Xiaohong Chen, Andres Santos

摘要

In the unconditional moment restriction model of Hansen (), specification tests and more efficient estimators are both available whenever the number of moment restrictions exceeds the number of parameters of interest. We show that a similar relationship between potential refutability of a model and existence of more efficient estimators is present in much broader settings. Specifically, a condition we name local overidentification is shown to be equivalent to both the existence of specification tests with nontrivial local power and the existence of more efficient estimators of some “smooth” parameters in general semi/nonparametric models. Under our notion of local overidentification, various locally nontrivial specification tests such as Hausman tests, incremental Sargan tests (or optimally weighted quasi likelihood ratio tests) naturally extend to general semi/nonparametric settings. We further obtain simple characterizations of local overidentification for general models of nonparametric conditional moment restrictions with possibly different conditioning sets. The results are applied to determining when semi/nonparametric models with endogeneity are locally testable, and when nonparametric plug‐in and semiparametric two‐step GMM estimators are semiparametrically efficient. Examples of empirically relevant semi/nonparametric structural models are presented. *(abstract via OpenAlex)*

JMLR Optimization & Learning Theory · 发表于 2018

Optimal Quantum Sample Complexity of Learning Algorithms

Srinivasan Arunachalam, Ronald de Wolf

摘要

In learning theory, the VC dimension of a concept class $C$ is the most common way to measure its “richness.” A fundamental result says that the number of examples needed to learn an unknown target concept $c\in C$ under an unknown distribution $D$, is tightly determined by the VC dimension $d$ of the concept class $C$. Specifically, in the PAC model $$ \Theta\Big(\frac{d}{\epsilon} + \frac{\log(1/\delta)}{\epsilon}\Big) $$ examples are necessary and sufficient for a learner to output, with probability $1-\delta$, a hypothesis $h$ that is $\epsilon$-close to the target concept $c$ (measured under $D$). In the related agnostic model, where the samples need not come from a $c\in C$, we know that $$ \Theta\Big(\frac{d}{\epsilon^2} + \frac{\log(1/\delta)}{\epsilon^2}\Big) $$ examples are necessary and sufficient to output an hypothesis $h\in C$ whose error is at most $\epsilon$ worse than the error of the best concept in $C$. Here we analyze quantum sample complexity, where each example is a coherent quantum state. This model was introduced by Bshouty and Jackson (1999), who showed that quantum examples are more powerful than classical examples in some fixed-distribution settings. However, Atıcı and Servedio (2005), improved by Zhang (2010), showed that in the PAC setting (where the learner has to succeed for every distribution), quantum examples cannot be much more powerful: the required number of quantum examples is $$ \Omega\Big(\frac{d^{1-\eta}}{\epsilon} + d + \frac{\log(1/\delta)}{\epsilon}\Big)\mbox{ for arbitrarily small constant }\eta>0. $$ Our main result is that quantum and classical sample complexity are in fact equal up to constant factors in both the PAC and agnostic models. We give two proof approaches. The first is a fairly simple information-theoretic argument that yields the above two classical bounds and yields the same bounds for quantum sample complexity up to a $\log(d/\epsilon)$ factor. We then give a second approach that avoids the log-factor loss, based on analyzing the behavior of the “Pretty Good Measurement” on the quantum state-identification problems that correspond to learning. This shows classical and quantum sample complexity are equal up to constant factors for every concept class $C$.

Econometrica Other · 发表于 2018

Optimal Inference in a Class of Regression Models

Timothy B. Armstrong, Michal Kolesár

摘要

We consider the problem of constructing confidence intervals (CIs) for a linear functional of a regression function, such as its value at a point, the regression discontinuity parameter, or a regression coefficient in a linear or partly linear regression. Our main assumption is that the regression function is known to lie in a convex function class, which covers most smoothness and/or shape assumptions used in econometrics. We derive finite-sample optimal CIs and sharp efficiency bounds under normal errors with known variance. We show that these results translate to uniform (over the function class) asymptotic results when the error distribution is not known. When the function class is centrosymmetric, these efficiency bounds imply that minimax CIs are close to efficient at smooth regression functions. This implies, in particular, that it is impossible to form CIs that are tighter using data-dependent tuning parameters, and maintain coverage over the whole function class. We specialize our results to inference on the regression discontinuity parameter, and illustrate them in simulations and an empirical application. *(abstract via OpenAlex)*

JMLR High-Dimensional · 发表于 2018

Optimal Bounds for Johnson-Lindenstrauss Transformations

Michael Burr, Shuhong Gao, Fiona Knoll

摘要

In 1984, Johnson and Lindenstrauss proved that any finite set of data in a high-dimensional space can be projected to a lower-dimensional space while preserving the pairwise Euclidean distances between points up to a bounded relative error. If the desired dimension of the image is too small, however, Kane, Meka, and Nelson (2011) and Jayram and Woodruff (2013) proved that such a projection does not exist. In this paper, we provide a precise asymptotic threshold for the dimension of the image, above which, there exists a projection preserving the Euclidean distance, but, below which, there does not exist such a projection.

JMLR Latent Variables & Mixtures · 发表于 2018

OpenEnsembles: A Python Resource for Ensemble Clustering

Tom Ronan, Shawn Anastasio, Zhijie Qi, Pedro Henrique S. Vieira Tavares, Roman Sloutsky, Kristen M. Naegle

摘要

In this paper we introduce OpenEnsembles, a Python toolkit for performing and analyzing ensemble clustering. Ensemble clustering is the process of creating many clustering solutions for a given dataset and utilizing the relationships observed across the ensemble to identify final solutions, which are more robust, stable or better than the individual solutions within the ensemble. The OpenEnsembles library provides a unified interface for applying transformations to data, clustering data, visualizing individual clustering solutions, visualizing and finishing the ensemble, and calculating validation metrics for a clustering solution for any given partitioning of the data. We have documented examples of using OpenEnsembles to create, analyze, and visualize a number of different types of ensemble approaches on toy and example datasets. OpenEnsembles is released under the GNU General Public License version 3, can be installed via Conda or the Python Package Index (pip), and is available at https://github.com/NaegleLab/OpenEnsembles.

JMLR Testing & Uncertainty Optimization & Learning Theory · 发表于 2018

Online Bootstrap Confidence Intervals for the Stochastic Gradient Descent Estimator

Yixin Fang, Jinfeng Xu, Lei Yang

摘要

In many applications involving large dataset or online learning, stochastic gradient descent (SGD) is a scalable algorithm to compute parameter estimates and has gained increasing popularity due to its numerical convenience and memory efficiency. While the asymptotic properties of SGD-based estimators have been well established, statistical inference such as interval estimation remains much unexplored. The classical bootstrap is not directly applicable if the data are not stored in memory. The plug-in method is not applicable when there is no explicit formula for the covariance matrix of the estimator. In this paper, we propose an online bootstrap procedure for the estimation of confidence intervals, which, upon the arrival of each observation, updates the SGD estimate as well as a number of randomly perturbed SGD estimates. The proposed method is easy to implement in practice. We establish its theoretical properties for a general class of models that includes linear regressions, generalized linear models, M-estimators and quantile regressions as special cases. The finite-sample performance and numerical utility is evaluated by simulation studies and real data applications.

JMLR High-Dimensional Testing & Uncertainty · 发表于 2018

On the Stability of Feature Selection Algorithms

Sarah Nogueira, Konstantinos Sechidis, Gavin Brown

摘要

Feature Selection is central to modern data science, from exploratory data analysis to predictive model-building. The “stability” of a feature selection algorithm refers to the robustness of its feature preferences, with respect to data sampling and to its stochastic nature. An algorithm is `unstable' if a small change in data leads to large changes in the chosen feature subset. Whilst the idea is simple, quantifying this has proven more challenging---we note numerous proposals in the literature, each with different motivation and justification. We present a rigorous statistical treatment for this issue. In particular, with this work we consolidate the literature and provide (1) a deeper understanding of existing work based on a small set of properties, and (2) a clearly justified statistical approach with several novel benefits. This approach serves to identify a stability measure obeying all desirable properties, and (for the first time in the literature) allowing confidence intervals and hypothesis tests on the stability, enabling rigorous experimental comparison of feature selection algorithms.

JMLR High-Dimensional · 发表于 2018

On the Behavior of Intrinsically High-Dimensional Spaces: Distances, Direct and Reverse Nearest Neighbors, and Hubness

Fabrizio Angiulli

摘要

Over the years, different characterizations of the curse of dimensionality have been provided, usually stating the conditions under which, in the limit of the infinite dimensionality, distances become indistinguishable. However, these characterizations almost never address the form of associated distributions in the finite, although high- dimensional, case. This work aims to contribute in this respect by investigating the distribution of distances, and of direct and reverse nearest neighbors, in intrinsically high-dimensional spaces. Indeed, we derive a closed form for the distribution of distances from a given point, for the expected distance from a given point to its $k$th nearest neighbor, and for the expected size of the approximate set of neighbors of a given point in finite high-dimensional spaces. Additionally, the hubness problem is considered, which is related to the form of the function $N_k$ representing the number of points that have a given point as one of their $k$ nearest neighbors, which is also called the number of $k$-occurrences. Despite the extensive use of this function, the precise characterization of its form is a longstanding problem. We derive a closed form for the number of $k$-occurrences associated with a given point in finite high- dimensional spaces, together with the associated limiting probability distribution. By investigating the relationships with the hubness phenomenon emerging in network science, we find that the distribution of node (in-)degrees of some real-life, large-scale networks has connections with the distribution of $k$-occurrences described herein.

JMLR High-Dimensional · 发表于 2018

On Tight Bounds for the Lasso

Sara van de Geer

摘要

We present upper and lower bounds for the prediction error of the Lasso. For the case of random Gaussian design, we show that under mild conditions the prediction error of the Lasso is up to smaller order terms dominated by the prediction error of its noiseless counterpart. We then provide exact expressions for the prediction error of the latter, in terms of compatibility constants. Here, we assume the active components of the underlying regression function satisfy some “betamin" condition. For the case of fixed design, we provide upper and lower bounds, again in terms of compatibility constants. As an example, we give an up to a logarithmic term tight bound for the least squares estimator with total variation penalty.

JMLR Networks & Graphs Nonparametric & Semiparametric · 发表于 2018

On Semiparametric Exponential Family Graphical Models

Zhuoran Yang, Yang Ning, Han Liu

摘要

We propose a new class of semiparametric exponential family graphical models for the analysis of high dimensional mixed data. Different from the existing mixed graphical models, we allow the nodewise conditional distributions to be semiparametric generalized linear models with unspecified base measure functions. Thus, one advantage of our method is that it is unnecessary to specify the type of each node and the method is more convenient to apply in practice. Under the proposed model, we consider both problems of parameter estimation and hypothesis testing in high dimensions. In particular, we propose a symmetric pairwise score test for the presence of a single edge in the graph. Compared to the existing methods for hypothesis tests, our approach takes into account of the symmetry of the parameters, such that the inferential results are invariant with respect to the different parametrizations of the same edge. Thorough numerical simulations and a real data example are provided to back up our theoretical results.

Econometrica Other · 发表于 2018

On Multiple Discount Rates

Christopher P. Chambers, Federico Echenique

摘要

We propose a theory of intertemporal choice that is robust to specific assumptions on the discount rate. One class of models requires that one utility stream be chosen over another if and only if its discounted value is higher for all discount factors in a set. Another model focuses on an average discount factor. Yet another model is pessimistic, and evaluates a flow by the lowest available discounted value. *(abstract via OpenAlex)*

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