2019 年的期刊文章 · 第 27 页

共 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 High-Dimensional · 发表于 2019

Scaling Up Sparse Support Vector Machines by Simultaneous Feature and Sample Reduction

Bin Hong, Weizhong Zhang, Wei Liu, Jieping Ye, Deng Cai, Xiaofei He, Jie Wang

摘要

Sparse support vector machine (SVM) is a popular classification technique that can simultaneously learn a small set of the most interpretable features and identify the support vectors. It has achieved great successes in many real-world applications. However, for large-scale problems involving a huge number of samples and ultra-high dimensional features, solving sparse SVMs remains challenging. By noting that sparse SVMs induce sparsities in both feature and sample spaces, we propose a novel approach, which is based on accurate estimations of the primal and dual optima of sparse SVMs, to simultaneously identify the inactive features and samples that are guaranteed to be irrelevant to the outputs. Thus, we can remove the identified inactive samples and features from the training phase, leading to substantial savings in the computational cost without sacrificing the accuracy. Moreover, we show that our method can be extended to multi-class sparse support vector machines. To the best of our knowledge, the proposed method is the first static feature and sample reduction method for sparse SVMs and multi-class sparse SVMs. Experiments on both synthetic and real data sets demonstrate that our approach significantly outperforms state-of-the-art methods and the speedup gained by our approach can be orders of magnitude.

JMLR Nonparametric & Semiparametric Latent Variables & Mixtures · 发表于 2019

Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds

Shusen Wang, Alex Gittens, Michael W. Mahoney

摘要

Kernel $k$-means clustering can correctly identify and extract a far more varied collection of cluster structures than the linear $k$-means clustering algorithm. However, kernel $k$-means clustering is computationally expensive when the non-linear feature map is high-dimensional and there are many input points. Kernel approximation, e.g., the Nystrom method, has been applied in previous works to approximately solve kernel learning problems when both of the above conditions are present. This work analyzes the application of this paradigm to kernel $k$-means clustering, and shows that applying the linear $k$-means clustering algorithm to $\frac{k}{\epsilon} (1 + o(1))$ features constructed using a so-called rank-restricted Nystrom approximation results in cluster assignments that satisfy a $1 + \epsilon$ approximation ratio in terms of the kernel $k$-means cost function, relative to the guarantee provided by the same algorithm without the use of the Nystrom method. As part of the analysis, this work establishes a novel $1 + \epsilon$ relative-error trace norm guarantee for low-rank approximation using the rank-restricted Nystrom approximation. Empirical evaluations on the $8.1$ million instance MNIST8M dataset demonstrate the scalability and usefulness of kernel $k$-means clustering with Nystrom approximation. This work argues that spectral clustering using Nystrom approximation---a popular and computationally efficient, but theoretically unsound approach to non-linear clustering---should be replaced with the efficient and theoretically sound combination of kernel $k$-means clustering with Nystrom approximation. The superior performance of the latter approach is empirically verified.

JMLR High-Dimensional · 发表于 2019

Scalable Interpretable Multi-Response Regression via SEED

Zemin Zheng, M. Taha Bahadori, Yan Liu, Jinchi Lv

摘要

Sparse reduced-rank regression is an important tool for uncovering meaningful dependence structure between large numbers of predictors and responses in many big data applications such as genome-wide association studies and social media analysis. Despite the recent theoretical and algorithmic advances, scalable estimation of sparse reduced-rank regression remains largely unexplored. In this paper, we suggest a scalable procedure called sequential estimation with eigen-decomposition (SEED) which needs only a single top-$r$ sparse singular value decomposition from a generalized eigenvalue problem to find the optimal low-rank and sparse matrix estimate. Our suggested method is not only scalable but also performs simultaneous dimensionality reduction and variable selection. Under some mild regularity conditions, we show that SEED enjoys nice sampling properties including consistency in estimation, rank selection, prediction, and model selection. Moreover, SEED employs only basic matrix operations that can be efficiently parallelized in high performance computing devices. Numerical studies on synthetic and real data sets show that SEED outperforms the state-of-the-art approaches for large-scale matrix estimation problem.

JMLR Optimization & Learning Theory · 发表于 2019

Scalable Approximations for Generalized Linear Problems

Murat Erdogdu, Mohsen Bayati, Lee H. Dicker

摘要

In stochastic optimization, the population risk is generally approximated by the empirical risk which is in turn minimized by an iterative algorithm. However, in the large-scale setting, empirical risk minimization may be computationally restrictive. In this paper, we design an efficient algorithm to approximate the population risk minimizer in generalized linear problems such as binary classification with surrogate losses and generalized linear regression models. We focus on large-scale problems where the iterative minimization of the empirical risk is computationally intractable, i.e., the number of observations $n$ is much larger than the dimension of the parameter $p$ ($n \gg p \gg 1$). We show that under random sub-Gaussian design, the true minimizer of the population risk is approximately proportional to the corresponding ordinary least squares (OLS) estimator. Using this relation, we design an algorithm that achieves the same accuracy as the empirical risk minimizer through iterations that attain up to a quadratic convergence rate, and that are computationally cheaper than any batch optimization algorithm by at least a factor of $\mathcal{O}(p)$. We provide theoretical guarantees for our algorithm, and analyze the convergence behavior in terms of data dimensions. Finally, we demonstrate the performance of our algorithm on well-known classification and regression problems, through extensive numerical studies on large-scale datasets, and show that it achieves the highest performance compared to several other widely used optimization algorithms.

JMLR Other · 发表于 2019

SMART: An Open Source Data Labeling Platform for Supervised Learning

Rob Chew, Michael Wenger, Caroline Kery, Jason Nance, Keith Richards, Emily Hadley, Peter Baumgartner

摘要

SMART is an open source web application designed to help data scientists and research teams efficiently build labeled training data sets for supervised machine learning tasks. SMART provides users with an intuitive interface for creating labeled data sets, supports active learning to help reduce the required amount of labeled data, and incorporates inter-rater reliability statistics to provide insight into label quality. SMART is designed to be platform agnostic and easily deployable to meet the needs of as many different research teams as possible. The project website https://rtiinternational.github.io/SMART/ contains links to the code repository and extensive user documentation.

JMLR Causal Inference · 发表于 2019

Robustifying Independent Component Analysis by Adjusting for Group-Wise Stationary Noise

Niklas Pfister, Sebastian Weichwald, Peter Bühlmann, Bernhard Schölkopf

摘要

We introduce coroICA, confounding-robust independent component analysis, a novel ICA algorithm which decomposes linearly mixed multivariate observations into independent components that are corrupted (and rendered dependent) by hidden group-wise stationary confounding. It extends the ordinary ICA model in a theoretically sound and explicit way to incorporate group-wise (or environment-wise) confounding. We show that our proposed general noise model allows to perform ICA in settings where other noisy ICA procedures fail. Additionally, it can be used for applications with grouped data by adjusting for different stationary noise within each group. Our proposed noise model has a natural relation to causality and we explain how it can be applied in the context of causal inference. In addition to our theoretical framework, we provide an efficient estimation procedure and prove identifiability of the unmixing matrix under mild assumptions. Finally, we illustrate the performance and robustness of our method on simulated data, provide audible and visual examples, and demonstrate the applicability to real-world scenarios by experiments on publicly available Antarctic ice core data as well as two EEG data sets. We provide a scikit-learn compatible pip-installable Python package coroICA as well as R and Matlab implementations accompanied by a documentation at https://sweichwald.de/coroICA/

Biometrics Clinical Trials · 发表于 2019

Robust inference for the stepped wedge design

James P. Hughes, Patrick J. Heagerty, Fan Xia, Yuqi Ren

摘要

Stepped wedge designed trials are a type of cluster‐randomized study in which the intervention is introduced to each cluster in a random order over time. This design is often used to assess the effect of a new intervention as it is rolled out across a series of clinics or communities. Based on a permutation argument, we derive a closed‐form expression for an estimate of the intervention effect, along with its standard error, for a stepped wedge design trial. We show that these estimates are robust to misspecification of both the mean and covariance structure of the underlying data‐generating mechanism, thereby providing a robust approach to inference for the intervention effect in stepped wedge designs. We use simulations to evaluate the type 1 error and power of the proposed estimate and to compare the performance of the proposed estimate to the optimal estimate when the correct model specification is known. The limitations, possible extensions, and open problems regarding the method are discussed.

JMLR Other · 发表于 2019

Robust Frequent Directions with Application in Online Learning

Luo Luo, Cheng Chen, Zhihua Zhang, Wu-Jun Li, Tong Zhang

摘要

The frequent directions (FD) technique is a deterministic approach for online sketching that has many applications in machine learning. The conventional FD is a heuristic procedure that often outputs rank deficient matrices. To overcome the rank deficiency problem, we propose a new sketching strategy called robust frequent directions (RFD) by introducing a regularization term. RFD can be derived from an optimization problem. It updates the sketch matrix and the regularization term adaptively and jointly. RFD reduces the approximation error of FD without increasing the computational cost. We also apply RFD to online learning and propose an effective hyperparameter-free online Newton algorithm. We derive a regret bound for our online Newton algorithm based on RFD, which guarantees the robustness of the algorithm. The experimental studies demonstrate that the proposed method outperforms state-of-the-art second order online learning algorithms.

JMLR Nonparametric & Semiparametric · 发表于 2019

Robust Estimation of Derivatives Using Locally Weighted Least Absolute Deviation Regression

WenWu Wang, Ping Yu, Lu Lin, Tiejun Tong

摘要

In nonparametric regression, the derivative estimation has attracted much attention in recent years due to its wide applications. In this paper, we propose a new method for the derivative estimation using the locally weighted least absolute deviation regression. Different from the local polynomial regression, the proposed method does not require a finite variance for the error term and so is robust to the presence of heavy-tailed errors. Meanwhile, it does not require a zero median or a positive density at zero for the error term in comparison with the local median regression. We further show that the proposed estimator with random difference is asymptotically equivalent to the (infinitely) composite quantile regression estimator. In other words, running one regression is equivalent to combining infinitely many quantile regressions. In addition, the proposed method is also extended to estimate the derivatives at the boundaries and to estimate higher-order derivatives. For the equidistant design, we derive theoretical results for the proposed estimators, including the asymptotic bias and variance, consistency, and asymptotic normality. Finally, we conduct simulation studies to demonstrate that the proposed method has better performance than the existing methods in the presence of outliers and heavy-tailed errors, and analyze the Chinese house price data for the past ten years to illustrate the usefulness of the proposed method.

Econometrica Econometrics & Economics · 发表于 2019

Retirement Financing: An Optimal Reform Approach

Roozbeh Hosseini, Ali Shourideh

摘要

We study Pareto optimal policy reforms aimed at overhauling retirement financing as an integral part of the tax and transfer system. Our framework for policy analysis is a heterogeneous‐agent overlapping‐generations model that performs well in matching the aggregate and distributional features of the U.S. economy. We present a test of Pareto optimality that identifies the main source of inefficiency in the status quo policies. Our test suggests that lack of asset subsidies late in life is the main source of inefficiency when annuity markets are incomplete. We solve for Pareto optimal policy reforms and show that progressive asset subsidies provide a powerful tool for Pareto optimal reforms. On the other hand, earnings tax reforms do not always yield efficiency gains. We implement our Pareto optimal policy reform in an economy that features demographic change. The reform reduces the present discounted value of net resources consumed by each generation by about 7 to 11 percent in the steady state. These gains amount to a one‐time lump‐sum transfer to the initial generation equal to 10.5 percent of GDP.

JMLR Other · 发表于 2019

Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion

Lijun Zhang, Tianbao Yang, Rong Jin, Zhi-Hua Zhou

摘要

In this paper, we develop a relative error bound for nuclear norm regularized matrix completion, with the focus on the completion of full-rank matrices. Under the assumption that the top eigenspaces of the target matrix are incoherent, we derive a relative upper bound for recovering the best low-rank approximation of the unknown matrix. Although multiple works have been devoted to analyzing the recovery error of full-rank matrix completion, their error bounds are usually additive, making it impossible to obtain the perfect recovery case and more generally difficult to leverage the skewed distribution of eigenvalues. Our analysis is built upon the optimality condition of the regularized formulation and existing guarantees for low-rank matrix completion. To the best of our knowledge, this is the first relative bound that has been proved for the regularized formulation of matrix completion.

JMLR Optimization & Learning Theory · 发表于 2019

Regularization via Mass Transportation

Soroosh Shafieezadeh-Abadeh, Daniel Kuhn, Peyman Mohajerin Esfahani

摘要

The goal of regression and classification methods in supervised learning is to minimize the empirical risk, that is, the expectation of some loss function quantifying the prediction error under the empirical distribution. When facing scarce training data, overfitting is typically mitigated by adding regularization terms to the objective that penalize hypothesis complexity. In this paper we introduce new regularization techniques using ideas from distributionally robust optimization, and we give new probabilistic interpretations to existing techniques. Specifically, we propose to minimize the worst-case expected loss, where the worst case is taken over the ball of all (continuous or discrete) distributions that have a bounded transportation distance from the (discrete) empirical distribution. By choosing the radius of this ball judiciously, we can guarantee that the worst-case expected loss provides an upper confidence bound on the loss on test data, thus offering new generalization bounds. We prove that the resulting regularized learning problems are tractable and can be tractably kernelized for many popular loss functions. The proposed approach to regluarization is also extended to neural networks. We validate our theoretical out-of-sample guarantees through simulated and empirical experiments.

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

Redundancy Techniques for Straggler Mitigation in Distributed Optimization and Learning

Can Karakus, Yifan Sun, Suhas Diggavi, Wotao Yin

摘要

Performance of distributed optimization and learning systems is bottlenecked by “straggler” nodes and slow communication links, which significantly delay computation. We propose a distributed optimization framework where the dataset is “encoded” to have an over-complete representation with built-in redundancy, and the straggling nodes in the system are dynamically treated as missing, or as “erasures” at every iteration, whose loss is compensated by the embedded redundancy. For quadratic loss functions, we show that under a simple encoding scheme, many optimization algorithms (gradient descent, L-BFGS, and proximal gradient) operating under data parallelism converge to an approximate solution even when stragglers are ignored. Furthermore, we show a similar result for a wider class of convex loss functions when operating under model parallelism. The applicable classes of objectives covers several popular learning problems such as linear regression, LASSO, support vector machine, collaborative filtering, and generalized linear models including logistic regression. These convergence results are deterministic, i.e., they establish sample path convergence for arbitrary sequences of delay patterns or distributions on the nodes, and are independent of the tail behavior of the delay distribution. We demonstrate that equiangular tight frames have desirable properties as encoding matrices, and propose efficient mechanisms for encoding large-scale data. We implement the proposed technique on Amazon EC2 clusters, and demonstrate its performance over several learning problems, including matrix factorization, LASSO, ridge regression and logistic regression, and compare the proposed method with uncoded, asynchronous, and data replication strategies.

Econometrica Econometrics & Economics · 发表于 2019

Recursive Contracts

Albert Marcet, Ramon Marimon

摘要

We obtain a recursive formulation for a general class of optimization problems with forward‐looking constraints which often arise in economic dynamic models, for example, in contracting problems with incentive constraints or in models of optimal policy. In this case, the solution does not satisfy the Bellman equation. Our approach consists of studying a recursive Lagrangian. Under standard general conditions, there is a recursive saddle‐point functional equation (analogous to a Bellman equation) that characterizes a recursive solution to the planner's problem. The recursive formulation is obtained after adding a co‐state variable μ t summarizing previous commitments reflected in past Lagrange multipliers. The continuation problem is obtained with μ t playing the role of weights in the objective function. Our approach is applicable to characterizing and computing solutions to a large class of dynamic contracting problems.

JMLR Nonparametric & Semiparametric · 发表于 2019

Random Feature-based Online Multi-kernel Learning in Environments with Unknown Dynamics

Yanning Shen, Tianyi Chen, Georgios B. Giannakis

JMLR Other · 发表于 2019

Quantifying Uncertainty in Online Regression Forests

Theodore Vasiloudis, Gianmarco De Francisci Morales, Henrik Boström

摘要

Accurately quantifying uncertainty in predictions is essential for the deployment of machine learning algorithms in critical applications where mistakes are costly. Most approaches to quantifying prediction uncertainty have focused on settings where the data is static, or bounded. In this paper, we investigate methods that quantify the prediction uncertainty in a streaming setting, where the data is potentially unbounded. We propose two meta-algorithms that produce prediction intervals for online regression forests of arbitrary tree models; one based on conformal prediction, and the other based on quantile regression. We show that the approaches are able to maintain specified error rates, with constant computational cost per example and bounded memory usage. We provide empirical evidence that the methods outperform the state-of-the-art in terms of maintaining error guarantees, while being an order of magnitude faster. We also investigate how the algorithms are able to recover from concept drift.

JMLR Bayesian Methods · 发表于 2019

Quantification Under Prior Probability Shift: the Ratio Estimator and its Extensions

Afonso Fernandes Vaz, Rafael Izbicki, Rafael Bassi Stern

摘要

The quantification problem consists of determining the prevalence of a given label in a target population. However, one often has access to the labels in a sample from the training population but not in the target population. A common assumption in this situation is that of prior probability shift, that is, once the labels are known, the distribution of the features is the same in the training and target populations. In this paper, we derive a new lower bound for the risk of the quantification problem under the prior shift assumption. Complementing this lower bound, we present a new approximately minimax class of estimators, ratio estimators, which generalize several previous proposals in the literature. Using a weaker version of the prior shift assumption, which can be tested, we show that ratio estimators can be used to build confidence intervals for the quantification problem. We also extend the ratio estimator so that it can: (i) incorporate labels from the target population, when they are available and (ii) estimate how the prevalence of positive labels varies according to a function of certain covariates.

JMLR Other · 发表于 2019

Pyro: Deep Universal Probabilistic Programming

Eli Bingham, Jonathan P. Chen, Martin Jankowiak, Fritz Obermeyer, Neeraj Pradhan, Theofanis Karaletsos, Rohit Singh, Paul Szerlip, Paul Horsfall, Noah D. Goodman

摘要

Pyro is a probabilistic programming language built on Python as a platform for developing advanced probabilistic models in AI research. To scale to large data sets and high-dimensional models, Pyro uses stochastic variational inference algorithms and probability distributions built on top of PyTorch, a modern GPU-accelerated deep learning framework. To accommodate complex or model-specific algorithmic behavior, Pyro leverages Poutine, a library of composable building blocks for modifying the behavior of probabilistic programs.

JMLR Other · 发表于 2019

PyOD: A Python Toolbox for Scalable Outlier Detection

Yue Zhao, Zain Nasrullah, Zheng Li

摘要

PyOD is an open-source Python toolbox for performing scalable outlier detection on multivariate data. Uniquely, it provides access to a wide range of outlier detection algorithms, including established outlier ensembles and more recent neural network-based approaches, under a single, well-documented API designed for use by both practitioners and researchers. With robustness and scalability in mind, best practices such as unit testing, continuous integration, code coverage, maintainability checks, interactive examples and parallelization are emphasized as core components in the toolbox's development. PyOD is compatible with both Python 2 and 3 and can be installed through Python Package Index (PyPI) or https://github.com/yzhao062/pyod.

JMLR High-Dimensional · 发表于 2019

Proximal Distance Algorithms: Theory and Practice

Kevin L. Keys, Hua Zhou, Kenneth Lange

摘要

Proximal distance algorithms combine the classical penalty method of constrained minimization with distance majorization. If $f(x)$ is the loss function, and $C$ is the constraint set in a constrained minimization problem, then the proximal distance principle mandates minimizing the penalized loss $f(x)+\frac{\rho}{2}dist(x,C)^2$ and following the solution $x_{\rho}$ to its limit as $\rho$ tends to $\infty$. At each iteration the squared Euclidean distance $dist(x,C)^2$ is majorized by the spherical quadratic $\|x-P_C(x_k)\|^2$, where $P_C(x_k)$ denotes the projection of the current iterate $x_k$ onto $C$. The minimum of the surrogate function $f(x)+\frac{\rho}{2}\|x-P_C(x_k)\|^2$ is given by the proximal map $prox_{\rho^{-1}f}[P_C(x_k)]$. The next iterate $x_{k+1}$ automatically decreases the original penalized loss for fixed $\rho$. Since many explicit projections and proximal maps are known, it is straightforward to derive and implement novel optimization algorithms in this setting. These algorithms can take hundreds if not thousands of iterations to converge, but the simple nature of each iteration makes proximal distance algorithms competitive with traditional algorithms. For convex problems, proximal distance algorithms reduce to proximal gradient algorithms and therefore enjoy well understood convergence properties. For nonconvex problems, one can attack convergence by invoking Zangwill's theorem. Our numerical examples demonstrate the utility of proximal distance algorithms in various high-dimensional settings, including a) linear programming, b) constrained least squares, c) projection to the closest kinship matrix, d) projection onto a second-order cone constraint, e) calculation of Horn's copositive matrix index, f) linear complementarity programming, and g) sparse principal components analysis. The proximal distance algorithm in each case is competitive or superior in speed to traditional methods such as the interior point method and the alternating direction method of multipliers (ADMM). Source code for the numerical examples can be found at https://github.com/klkeys/proxdist.

JMLR High-Dimensional · 发表于 2019

Provably Accurate Double-Sparse Coding

Thanh V. Nguyen, Raymond K. W. Wong, Chinmay Hegde

摘要

Sparse coding is a crucial subroutine in algorithms for various signal processing, deep learning, and other machine learning applications. The central goal is to learn an overcomplete dictionary that can sparsely represent a given input dataset. However, a key challenge is that storage, transmission, and processing of the learned dictionary can be untenably high if the data dimension is high. In this paper, we consider the double-sparsity model introduced by Rubinstein et al. (2010b) where the dictionary itself is the product of a fixed, known basis and a data-adaptive sparse component. First, we introduce a simple algorithm for double-sparse coding that can be amenable to efficient implementation via neural architectures. Second, we theoretically analyze its performance and demonstrate asymptotic sample complexity and running time benefits over existing (provable) approaches for sparse coding. To our knowledge, our work introduces the first computationally efficient algorithm for double-sparse coding that enjoys rigorous statistical guarantees. Finally, we corroborate our theory with several numerical experiments on simulated data, suggesting that our method may be useful for problem sizes encountered in practice.

Econometrica Econometrics & Economics Causal Inference · 发表于 2019

Pricing and Liquidity in Decentralized Asset Markets

Semih Üslü

摘要

I develop a search‐and‐bargaining model of endogenous intermediation in over‐the‐counter markets. Unlike the existing work, my model allows for rich investor heterogeneity in three simultaneous dimensions: preferences, inventories, and meeting rates. By comparing trading‐volume patterns that arise in my model and are observed in practice, I argue that the heterogeneity in meeting rates is the main driver of intermediation patterns. I find that investors with higher meeting rates (i.e., fast investors) are less averse to holding inventories and more attracted to cash earnings, which makes the model corroborate a number of stylized facts that do not emerge from existing models: (i) fast investors provide intermediation by charging aspeed premium, and (ii) fast investors hold more extreme inventories. Then, I use the model to study the effect of trading frictions on the supply and price of liquidity. On social welfare, I show that the interaction of meeting rate heterogeneity with optimal inventory management makes the equilibrium inefficient. I provide a financial transaction tax/subsidy scheme that corrects this inefficiency, in which fast investors cross‐subsidize slow investors.

Econometrica Econometrics & Economics · 发表于 2019

Preferences for Truth‐Telling

Johannes Abeler, Daniele Nosenzo, Collin Raymond

摘要

Private information is at the heart of many economic activities. For decades, economists have assumed that individuals are willing to misreport private information if this maximizes their material payoff. We combine data from 90 experimental studies in economics, psychology, and sociology, and show that, in fact, people lie surprisingly little. We then formalize a wide range of potential explanations for the observed behavior, identify testable predictions that can distinguish between the models, and conduct new experiments to do so. Our empirical evidence suggests that a preference for being seen as honest and a preference for being honest are the main motivations for truth‐telling.

JMLR Other · 发表于 2019

Prediction Risk for the Horseshoe Regression

Anindya Bhadra, Jyotishka Datta, Yunfan Li, Nicholas G. Polson, Brandon Willard

摘要

We show that prediction performance for global-local shrinkage regression can overcome two major difficulties of global shrinkage regression: (i) the amount of relative shrinkage is monotone in the singular values of the design matrix and (ii) the shrinkage is determined by a single tuning parameter. Specifically, we show that the horseshoe regression, with heavy-tailed component-specific local shrinkage parameters, in conjunction with a global parameter providing shrinkage towards zero, alleviates both these difficulties and consequently, results in an improved risk for prediction. Numerical demonstrations of improved prediction over competing approaches in simulations and in a pharmacogenomics data set confirm our theoretical findings.

Econometrica Other · 发表于 2019

Precautionary Savings, Illiquid Assets, and the Aggregate Consequences of Shocks to Household Income Risk

Christian Bayer, Ralph Luetticke, Lien Pham-Dao, Volker Tjaden

摘要

Households face large income uncertainty that varies substantially over the business cycle. We examine the macroeconomic consequences of these variations in a model with incomplete markets, liquid and illiquid assets, and a nominal rigidity. Heightened uncertainty depresses aggregate demand as households respond by hoarding liquid ``paper'' assets for precautionary motives, thereby reducing both illiquid physical investment and consumption demand. This translates into output losses, which a central bank can prevent by providing liquidity. We show that the welfare consequences of uncertainty shocks crucially depend on a household's asset position. Households with little human capital but high illiquid wealth lose the most from an uncertainty shock and gain the most from stabilization policy. *(abstract via OpenAlex)*

Econometrica Clinical Trials · 发表于 2019

Power in High‐Dimensional Testing Problems

Anders Bredahl Kock, David Preinerstorfer

摘要

Fan, Liao, and Yao (2015) recently introduced a remarkable method for increasing the asymptotic power of tests in high‐dimensional testing problems. If applicable to a given test, theirpower enhancement principleleads to an improved test that has the same asymptotic size, has uniformly non‐inferior asymptotic power, and is consistent against a strictly broader range of alternatives than the initially given test. We study under which conditions this method can be applied and show the following: In asymptotic regimes where the dimensionality of the parameter space is fixed as sample size increases, there often exist tests that cannot be further improved with the power enhancement principle. However, when the dimensionality of the parameter space increases sufficiently slowly with sample size and a marginal local asymptotic normality (LAN) condition is satisfied,everytest with asymptotic size smaller than 1 can be improved with the power enhancement principle. While the marginal LAN condition alone does not allow one to extend the latter statement to all rates at which the dimensionality increases with sample size, we give sufficient conditions under which this is the case.

JMLR High-Dimensional · 发表于 2019

Picasso: A Sparse Learning Library for High Dimensional Data Analysis in R and Python

Jason Ge, Xingguo Li, Haoming Jiang, Han Liu, Tong Zhang, Mengdi Wang, Tuo Zhao

摘要

We describe a new library named picasso, which implements a unified framework of pathwise coordinate optimization for a variety of sparse learning problems (e.g., sparse linear regression, sparse logistic regression, sparse Poisson regression and scaled sparse linear regression) combined with efficient active set selection strategies. Besides, the library allows users to choose different sparsity-inducing regularizers, including the convex $\ell_1$, nonvoncex MCP and SCAD regularizers. The library is coded in \texttt{C++} and has user-friendly R and Python wrappers. Numerical experiments demonstrate that picasso can scale up to large problems efficiently.

Econometrica Econometrics & Economics Networks & Graphs · 发表于 2019

Peer‐Confirming Equilibrium

Elliot Lipnowski, Evan Sadler

摘要

We can often predict the behavior of those closest to us more accurately than that of complete strangers, yet we routinely engage in strategic situations with both: our social network impacts our strategic knowledge. Peer‐confirming equilibrium describes the behavioral consequences of this intuition in a noncooperative game. We augment a game with a network to represent strategic information: if two players are linked in the network, they have correct conjectures about each others' strategies. In peer‐confirming equilibrium, there is common belief that players (i) behave rationally and (ii) correctly anticipate neighbors' play. In simultaneous‐move games, adding links to the network always restricts the set of outcomes. In dynamic games, the outcome set may vary non‐monotonically with the network because the actions of well‐connected players help poorly‐connected players coordinate. This solution concept provides a useful language for studying public good provision, highlights a new channel through which central individuals facilitate coordination, and delineates possible sources of miscoordination in protests and coups.

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

Parsimonious Online Learning with Kernels via Sparse Projections in Function Space

Alec Koppel, Garrett Warnell, Ethan Stump, Alejandro Ribeiro

摘要

Despite their attractiveness, popular perception is that techniques for nonparametric function approximation do not scale to streaming data due to an intractable growth in the amount of storage they require. To solve this problem in a memory-affordable way, we propose an online technique based on functional stochastic gradient descent in tandem with supervised sparsification based on greedy function subspace projections. The method, called parsimonious online learning with kernels (POLK), provides a controllable tradeoff between its solution accuracy and the amount of memory it requires. We derive conditions under which the generated function sequence converges almost surely to the optimal function, and we establish that the memory requirement remains finite. We evaluate POLK for kernel multi-class logistic regression and kernel hinge-loss classification on three canonical data sets: a synthetic Gaussian mixture model, the MNIST hand-written digits, and the Brodatz texture database. On all three tasks, we observe a favorable trade-off of objective function evaluation, classification performance, and complexity of the nonparametric regressor extracted by the proposed method.

JMLR Optimization & Learning Theory · 发表于 2019

Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals

Andrew Cotter, Heinrich Jiang, Maya Gupta, Serena Wang, Taman Narayan, Seungil You, Karthik Sridharan

摘要

We show that many machine learning goals can be expressed as “rate constraints” on a model's predictions. We study the problem of training non-convex models subject to these rate constraints (or other non-convex or non-differentiable constraints). In the non-convex setting, the standard approach of Lagrange multipliers may fail. Furthermore, if the constraints are non-differentiable, then one cannot optimize the Lagrangian with gradient-based methods. To solve these issues, we introduce a new “proxy-Lagrangian” formulation. This leads to an algorithm that, assuming access to an optimization oracle, produces a stochastic classifier by playing a two-player non-zero-sum game solving for what we call a semi-coarse correlated equilibrium, which in turn corresponds to an approximately optimal and feasible solution to the constrained optimization problem. We then give a procedure that shrinks the randomized solution down to a mixture of at most $m+1$ deterministic solutions, given $m$ constraints. This culminates in a procedure that can solve non-convex constrained optimization problems with possibly non-differentiable and non-convex constraints, and enjoys theoretical guarantees. We provide extensive experimental results covering a broad range of policy goals, including various fairness metrics, accuracy, coverage, recall, and churn.

JMLR Optimization & Learning Theory · 发表于 2019

Optimal Transport: Fast Probabilistic Approximation with Exact Solvers

Max Sommerfeld, Jörn Schrieber, Yoav Zemel, Axel Munk

摘要

We propose a simple subsampling scheme for fast randomized approximate computation of optimal transport distances on finite spaces. This scheme operates on a random subset of the full data and can use any exact algorithm as a black-box back-end, including state-of-the-art solvers and entropically penalized versions. It is based on averaging the exact distances between empirical measures generated from independent samples from the original measures and can easily be tuned towards higher accuracy or shorter computation times. To this end, we give non-asymptotic deviation bounds for its accuracy in the case of discrete optimal transport problems. In particular, we show that in many important instances, including images (2D-histograms), the approximation error is independent of the size of the full problem. We present numerical experiments that demonstrate that a very good approximation in typical applications can be obtained in a computation time that is several orders of magnitude smaller than what is required for exact computation of the full problem.

Econometrica Econometrics & Economics · 发表于 2019

Optimal Taxation, Marriage, Home Production, and Family Labor Supply

George-Levi Gayle, Andrew Shephard

摘要

An empirical approach to optimal income taxation design is developed within an equilibrium collective marriage market model with imperfectly transferable utility. Taxes distort labour supply and time allocation decisions, as well as marriage market outcomes, and the within household decision process. Using data from the American Community Survey and American Time Use Survey, we structurally estimate our model and explore empirical design problems. We consider the optimal design problem when the planner is able to condition taxes on marital status, as in the U.S. tax code, but we allow the schedule for married couples to have an arbitrary form of tax jointness. Our results suggest that the optimal tax system for married couples is characterized by negative jointness, although the welfare gains from this jointness are shown to be quite modest. *(abstract via OpenAlex)*

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

Optimal Policies for Observing Time Series and Related Restless Bandit Problems

Christopher R. Dance, Tomi Silander

摘要

The trade-off between the cost of acquiring and processing data, and uncertainty due to a lack of data is fundamental in machine learning. A basic instance of this trade-off is the problem of deciding when to make noisy and costly observations of a discrete-time Gaussian random walk, so as to minimise the posterior variance plus observation costs. We present the first proof that a simple policy, which observes when the posterior variance exceeds a threshold, is optimal for this problem. The proof generalises to a wide range of cost functions other than the posterior variance. It is based on a new verification theorem by Nino-Mora that guarantees threshold structure for Markov decision processes, and on the relation between binary sequences known as Christoffel words and the dynamics of discontinuous nonlinear maps, which frequently arise in physics, control and biology. This result implies that optimal policies for linear-quadratic-Gaussian control with costly observations have a threshold structure. It also implies that the restless bandit problem of observing multiple such time series, has a well-defined Whittle index policy. We discuss computation of that index, give closed-form formulae for it, and compare the performance of the associated index policy with heuristic policies.

Econometrica Econometrics & Economics · 发表于 2019

Optimal Development Policies With Financial Frictions

Oleg Itskhoki, Benjamin Moll

摘要

We study optimal dynamic Ramsey policies in a standard growth model with financial frictions.For developing countries with low financial wealth, the optimal policy intervention increases labor supply and lowers wages, resulting in higher entrepreneurial profits and faster wealth accumulation.This in turn relaxes borrowing constraints in the future, leading to higher labor productivity and wages.The use of additional policy instruments, such as subsidized credit, may be optimal as well.In the long run, the optimal policy reverses sign.Taking advantage of the tractability of our framework, we extend the model to study its implications for optimal exchange rate and sectoral industrial policies. *(abstract via OpenAlex)*

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

Optimal Convergence Rates for Convex Distributed Optimization in Networks

Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, Laurent Massoulié

摘要

This work proposes a theoretical analysis of distributed optimization of convex functions using a network of computing units. We investigate this problem under two communication schemes (centralized and decentralized) and four classical regularity assumptions: Lipschitz continuity, strong convexity, smoothness, and a combination of strong convexity and smoothness. Under the decentralized communication scheme, we provide matching upper and lower bounds of complexity along with algorithms achieving this rate up to logarithmic constants. For non-smooth objective functions, while the dominant term of the error is in $O(1/\sqrt{t})$, the structure of the communication network only impacts a second-order term in $O(1/t)$, where $t$ is time. In other words, the error due to limits in communication resources decreases at a fast rate even in the case of non-strongly convex objective functions. Such a convergence rate is achieved by the novel multi-step primal-dual (MSPD) algorithm. Under the centralized communication scheme, we show that the naive distribution of standard optimization algorithms is optimal for smooth objective functions, and provide a simple yet efficient algorithm called distributed randomized smoothing (DRS) based on a local smoothing of the objective function for non-smooth functions. We then show that DRS is within a $d^{1/4}$ multiplicative factor of the optimal convergence rate, where $d$ is the underlying dimension.

JMLR Other · 发表于 2019

On the optimality of the Hedge algorithm in the stochastic regime

Jaouad Mourtada, Stéphane Gaïffas

摘要

In this paper, we study the behavior of the Hedge algorithm in the online stochastic setting. We prove that anytime Hedge with decreasing learning rate, which is one of the simplest algorithm for the problem of prediction with expert advice, is remarkably both worst-case optimal and adaptive to the easier stochastic and adversarial with a gap problems. This shows that, in spite of its small, non-adaptive learning rate, Hedge possesses the same optimal regret guarantee in the stochastic case as recently introduced adaptive algorithms. Moreover, our analysis exhibits qualitative differences with other versions of the Hedge algorithm, such as the fixed-horizon variant (with constant learning rate) and the one based on the so-called “doubling trick”, both of which fail to adapt to the easier stochastic setting. Finally, we determine the intrinsic limitations of anytime Hedge in the stochastic case, and discuss the improvements provided by more adaptive algorithms.

Econometrica Other · 发表于 2019

On the Efficiency of Social Learning

Dinah Rosenberg, Nicolas Vieille

摘要

We revisit prominent learning models in which a sequence of agents make a binary decision on the basis of both a private signal and information related to past choices. We analyze the efficiency of learning in these models, measured in terms of the expected welfare. We show that, irrespective of the distribution of private signals, learning efficiency is the same whether each agent observes the entire sequence of earlier decisions or only the previous decision. In addition, we provide a simple condition on the signal distributions that is necessary and sufficient for learning efficiency. This condition fails to hold in many cases of interest. We discuss a number of extensions and variants.

JMLR Other · 发表于 2019

On the Convergence of Gaussian Belief Propagation with Nodes of Arbitrary Size

Francois Kamper, Sarel J. Steel, Johan A. du Preez

摘要

This paper is concerned with a multivariate extension of Gaussian message passing applied to pairwise Markov graphs (MGs). Gaussian message passing applied to pairwise MGs is often labeled Gaussian belief propagation (GaBP) and can be used to approximate the marginal of each variable contained in the pairwise MG. We propose a multivariate extension of GaBP (we label this GaBP-m) that can be used to estimate higher-dimensional marginals. Beyond the ability to estimate higher-dimensional marginals, GaBP-m exhibits better convergence behavior than GaBP, and can also provide more accurate univariate marginals. The theoretical results of this paper are based on an extension of the computation tree analysis conducted on univariate nodes to the multivariate case. The main contribution of this paper is the development of a convergence condition for GaBP-m that moves beyond the walk-summability of the precision matrix. Based on this convergence condition, we derived an upper bound for the number of iterations required for convergence of the GaBP-m algorithm. An upper bound on the dissimilarity between the approximate and exact marginal covariance matrices was established. We argue that GaBP-m is robust towards a certain change in variables, a property not shared by iterative solvers of linear systems, such as the conjugate gradient (CG) and preconditioned conjugate gradient (PCG) methods. The advantages of using GaBP-m over GaBP are also illustrated empirically.

Econometrica Causal Inference Econometrics & Economics · 发表于 2019

On Heckits, LATE, and Numerical Equivalence

Patrick Kline, Christopher R. Walters

摘要

Structural econometric methods are often criticized for being sensitive to functional form assumptions. We study parametric estimators of the local average treatment effect (LATE) derived from a widely used class of latent threshold crossing models and show they yield LATE estimates algebraically equivalent to the instrumental variables (IV) estimator. Our leading example is Heckman's (1979) two‐step (“Heckit”) control function estimator which, with two‐sided non‐compliance, can be used to compute estimates of a variety of causal parameters. Equivalence with IV is established for a semiparametric family of control function estimators and shown to hold at interior solutions for a class of maximum likelihood estimators. Our results suggest differences between structural and IV estimates often stem from disagreements about the target parameter rather than from functional form assumptions per se. In cases where equivalence fails, reporting structural estimates of LATE alongside IV provides a simple means of assessing the credibility of structural extrapolation exercises.

JMLR Networks & Graphs · 发表于 2019

On Consistent Vertex Nomination Schemes

Vince Lyzinski, Keith Levin, Carey E. Priebe

摘要

Given a vertex of interest in a network $G_1$, the vertex nomination problem seeks to find the corresponding vertex of interest (if it exists) in a second network $G_2$. A vertex nomination scheme produces a list of the vertices in $G_2$, ranked according to how likely they are judged to be the corresponding vertex of interest in $G_2$. The vertex nomination problem and related information retrieval tasks have attracted much attention in the machine learning literature, with numerous applications to social and biological networks. However, the current framework has often been confined to a comparatively small class of network models, and the concept of statistically consistent vertex nomination schemes has been only shallowly explored. In this paper, we extend the vertex nomination problem to a very general statistical model of graphs. Further, drawing inspiration from the long-established classification framework in the pattern recognition literature, we provide definitions for the key notions of Bayes optimality and consistency in our extended vertex nomination framework, including a derivation of the Bayes optimal vertex nomination scheme. In addition, we prove that no universally consistent vertex nomination schemes exist. Illustrative examples are provided throughout.

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