2021 年的期刊文章 · 第 31 页

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

按期刊、按主题看 →

第 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 34 35 36 37 38 39 页

JMLR Networks & Graphs · 发表于 2021

Structure Learning of Undirected Graphical Models for Count Data

Nguyen Thi Kim Hue, Monica Chiogna

摘要

Mainly motivated by the problem of modelling biological processes underlying the basic functions of a cell -that typically involve complex interactions between genes- we present a new algorithm, called PC-LPGM, for learning the structure of undirected graphical models over discrete variables. We prove theoretical consistency of PC-LPGM in the limit of infinite observations and discuss its robustness to model misspecification. To evaluate the performance of PC-LPGM in recovering the true structure of the graphs in situations where relatively moderate sample sizes are available, extensive simulation studies are conducted, that also allow to compare our proposal with its main competitors. A biological validation of the algorithm is presented through the analysis of two real data sets.

Econometrica Other · 发表于 2021

Structural Change With Long‐Run Income and Price Effects

Diego Comin, Danial Lashkari, Martí Mestieri

摘要

We present a new multi‐sector growth model that features nonhomothetic, constant elasticity of substitution preferences, and accommodates long‐run demand and supply drivers of structural change for an arbitrary number of sectors. The model is consistent with the decline in agriculture, the hump‐shaped evolution of manufacturing, and the rise of services over time. We estimate the demand system derived from the model using household‐level data from the United States and India, as well as historical aggregate‐level panel data for 39 countries during the postwar period. The estimated model parsimoniously accounts for the broad patterns of sectoral reallocation observed among rich, miracle, and developing economies. Our estimates support the presence of strong nonhomotheticity across time, income levels, and countries. We find that income effects account for the bulk of the within‐country evolution of sectoral reallocation.

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

Strong Consistency, Graph Laplacians, and the Stochastic Block Model

Shaofeng Deng, Shuyang Ling, Thomas Strohmer

摘要

Spectral clustering has become one of the most popular algorithms in data clustering and community detection. We study the performance of classical two-step spectral clustering via the graph Laplacian to learn the stochastic block model. Our aim is to answer the following question: when is spectral clustering via the graph Laplacian able to achieve strong consistency, i.e., the exact recovery of the underlying hidden communities? Our work provides an entrywise analysis (an $\ell_{\infty}$-norm perturbation bound) of the Fiedler eigenvector of both the unnormalized and the normalized Laplacian associated with the adjacency matrix sampled from the stochastic block model. We prove that spectral clustering is able to achieve exact recovery of the planted community structure under conditions that match the information-theoretic limits.

Econometrica Survival Analysis · 发表于 2021

Strategic Sample Selection

Alfredo Di Tillio, Marco Ottaviani, Peter Norman Sørensen

摘要

Are the highest sample realizations selected from a larger presample more or less informative than the same amount of random data? Developing multivariate accuracy for interval dominance ordered preferences, we show that sample selection always benefits (or always harms) a decision maker if the reverse hazard rate of the data distribution is log‐supermodular (or log‐submodular), as in location experiments with normal noise. We find nonpathological conditions under which the information contained in the winning bids of a symmetric auction decreases in the number of bidders. Exploiting extreme value theory, we quantify the limit amount of information revealed when the presample size (number of bidders) goes to infinity. In a model of equilibrium persuasion with costly information, we derive implications for the optimal design of selected experiments when selection is made by an examinee, a biased researcher, or contending sides with the peremptory challenge right to eliminate a number of jurors.

Econometrica Econometrics & Economics · 发表于 2021

Strategic Analysis of Auctions

Robert B. Wilson

摘要

In many markets, transaction prices are determined in auctions. In the most common form, prospective buyers compete by submitting bids to a seller. Each bid is an offer to buy that states a quantity and a maximum price. The seller then allocates the available supply among those offering the highest prices exceeding the seller's asking price. The actual price paid by a successful bidder depends on a pricing rule, usually selected by the seller: two common pricing rules are that each successful bidder pays the price bid; or they all pay the same price, usually the highest rejected bid or the lowest accepted bid. Auctions have been used for millennia, and remain the simplest and most famil-iar means of price determination for multilateral trading without intermediary `market makers ' such as brokers and specialists. Their trading procedures, which simply process bids and offers, are direct extensions of the usual forms of bilateral bargaining. Auctions also implement directly the demand submission procedures used in Walrasian models of markets. They therefore have prominent roles in the theory of exchange and in studies of the effects of economic institutions on the volume and terms of trade. Their allocative ef-®ciency in many contexts ensures their continued prominence in economic theory. They are also favored in experimental designs investigating the predictive power of economic theories. Auctions are apt subjects for applications of game theory because they present ex-plicit trading rules that largely ®x the `rules of the game'. Moreover, they present sub-stantive problems of strategic behavior of practical importance. They are particularly valuable as illustrations of games of incomplete information because bidders ' private information is the main factor affecting strategic behavior. The simpler forms of auctions induce normal-form games that are essentially `solved ' by applying directly the basic *(abstract via OpenAlex)*

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

Stochastic Proximal Methods for Non-Smooth Non-Convex Constrained Sparse Optimization

Michael R. Metel, Akiko Takeda

摘要

This paper focuses on stochastic proximal gradient methods for optimizing a smooth non-convex loss function with a non-smooth non-convex regularizer and convex constraints. To the best of our knowledge we present the first non-asymptotic convergence bounds for this class of problem. We present two simple stochastic proximal gradient algorithms, for general stochastic and finite-sum optimization problems. In a numerical experiment we compare our algorithms with the current state-of-the-art deterministic algorithm and find our algorithms to exhibit superior convergence.

JMLR Diagnostics & Prediction · 发表于 2021

Stochastic Proximal AUC Maximization

Yunwen Lei, Yiming Ying

摘要

In this paper we consider the problem of maximizing the Area under the ROC curve (AUC) which is a widely used performance metric in imbalanced classification and anomaly detection. Due to the pairwise nonlinearity of the objective function, classical SGD algorithms do not apply to the task of AUC maximization. We propose a novel stochastic proximal algorithm for AUC maximization which is scalable to large scale streaming data. Our algorithm can accommodate general penalty terms and is easy to implement with favorable $O(d)$ space and per-iteration time complexities. We establish a high-probability convergence rate $O(1/\sqrt{T})$ for the general convex setting, and improve it to a fast convergence rate $O(1/T)$ for the cases of strongly convex regularizers and no regularization term (without strong convexity). Our proof does not need the uniform boundedness assumption on the loss function or the iterates which is more fidelity to the practice. Finally, we perform extensive experiments over various benchmark data sets from real-world application domains which show the superior performance of our algorithm over the existing AUC maximization algorithms.

JMLR Optimization & Learning Theory · 发表于 2021

Stochastic Online Optimization using Kalman Recursion

Joseph de Vilmarest, Olivier Wintenberger

摘要

We study the Extended Kalman Filter in constant dynamics, offering a bayesian perspective of stochastic optimization. For generalized linear models, we obtain high probability bounds on the cumulative excess risk in an unconstrained setting, under the assumption that the algorithm reaches a local phase. In order to avoid any projection step we propose a two-phase analysis. First, for linear and logistic regressions, we prove that the algorithm enters a local phase where the estimate stays in a small region around the optimum. We provide explicit bounds with high probability on this convergence time, slightly modifying the Extended Kalman Filter in the logistic setting. Second, for generalized linear regressions, we provide a martingale analysis of the excess risk in the local phase, improving existing ones in bounded stochastic optimization. The algorithm appears as a parameter-free online procedure that optimally solves some unconstrained optimization problems.

JMLR Spatial & Time Series · 发表于 2021

Statistically and Computationally Efficient Change Point Localization in Regression Settings

Daren Wang, Zifeng Zhao, Kevin Z. Lin, Rebecca Willett

摘要

Detecting when the underlying distribution changes for the observed time series is a fundamental problem arising in a broad spectrum of applications. In this paper, we study multiple change-point localization in the high-dimensional regression setting, which is particularly challenging as no direct observations of the parameter of interest is available. Specifically, we assume we observe $\{ x_t, y_t\}_{t=1}^n$ where $ \{ x_t\}_{t=1}^n $ are $p$-dimensional covariates, $\{y_t\}_{t=1}^n$ are the univariate responses satisfying $\mathbb{E}(y_t) = x_t^\top \beta_t^* \text{ for } 1\le t \le n $ and $\{\beta_t^*\}_{t=1}^n $ are the unobserved regression coefficients that change over time in a piecewise constant manner. We propose a novel projection-based algorithm, Variance Projected Wild Binary Segmentation~(VPWBS), which transforms the original (difficult) problem of change-point detection in $p$-dimensional regression to a simpler problem of change-point detection in mean of a one-dimensional time series. VPWBS is shown to achieve sharp localization rate $O_p(1/n)$ up to a log factor, a significant improvement from the best rate $O_p(1/\sqrt{n})$ known in the existing literature for multiple change-point localization in high-dimensional regression. Extensive numerical experiments are conducted to demonstrate the robust and favorable performance of VPWBS over two state-of-the-art algorithms, especially when the size of change in the regression coefficients $\{\beta_t^*\}_{t=1}^n $ is small.

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

Statistical guarantees for local graph clustering

Wooseok Ha, Kimon Fountoulakis, Michael W. Mahoney

摘要

Local graph clustering methods aim to find small clusters in very large graphs. These methods take as input a graph and a seed node, and they return as output a good cluster in a running time that depends on the size of the output cluster but that is independent of the size of the input graph. In this paper, we adopt a statistical perspective on local graph clustering, and we analyze the performance of the $\ell_1$-regularized PageRank method (Fountoulakis et al., 2019) for the recovery of a single target cluster, given a seed node inside the cluster. Assuming the target cluster has been generated by a random model, we present two results. In the first, we show that the optimal support of $\ell_1$-regularized PageRank recovers the full target cluster, with bounded false positives. In the second, we show that if the seed node is connected solely to the target cluster then the optimal support of $\ell_1$-regularized PageRank recovers exactly the target cluster. We also show empirically that $\ell_1$-regularized PageRank has a state-of-the-art performance on many real graphs, demonstrating the superiority of the method. From a computational perspective, we show that the solution path of $\ell_1$-regularized PageRank is monotonic. This allows for the application of the forward stagewise algorithm, which approximates the entire solution path in running time that does not depend on the size of the whole graph. Finally, we show that $\ell_1$-regularized PageRank and approximate personalized PageRank (APPR) (Andersen et al., 2006), another very popular method for local graph clustering, are equivalent in the sense that we can lower and upper bound the output of one with the output of the other. Based on this relation, we establish for APPR similar results to those we establish for $\ell_1$-regularized PageRank.

JMLR Optimization & Learning Theory · 发表于 2021

Statistical Query Lower Bounds for Tensor PCA

Rishabh Dudeja, Daniel Hsu

摘要

In the Tensor PCA problem introduced by Richard and Montanari (2014), one is given a dataset consisting of $n$ samples $\mathbf{T}_{1:n}$ of i.i.d. Gaussian tensors of order $k$ with the promise that $\mathbb{E}\mathbf{T}_1$ is a rank-1 tensor and $\|\mathbb{E} \mathbf{T}_1\| = 1$. The goal is to estimate $\mathbb{E} \mathbf{T}_1$. This problem exhibits a large conjectured hard phase when $k>2$: When $d \lesssim n \ll d^{\frac{k}{2}}$ it is information theoretically possible to estimate $\mathbb{E} \mathbf{T}_1$, but no polynomial time estimator is known. We provide a sharp analysis of the optimal sample complexity in the Statistical Query (SQ) model and show that SQ algorithms with polynomial query complexity not only fail to solve Tensor PCA in the conjectured hard phase, but also have a strictly sub-optimal sample complexity compared to some polynomial time estimators such as the Richard-Montanari spectral estimator. Our analysis reveals that the optimal sample complexity in the SQ model depends on whether $\mathbb{E} \mathbf{T}_1$ is symmetric or not. For symmetric, even order tensors, we also isolate a sample size regime in which it is possible to test if $\mathbb{E} \mathbf{T}_1 = \mathbf{0}$ or $\mathbb{E}\mathbf{T}_1 \neq \mathbf{0}$ with polynomially many queries but not estimate $\mathbb{E}\mathbf{T}_1$. Our proofs rely on the Fourier analytic approach of Feldman, Perkins and Vempala (2018) to prove sharp SQ lower bounds.

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

Statistical Guarantees for Local Spectral Clustering on Random Neighborhood Graphs

Alden Green, Sivaraman Balakrishnan, Ryan J. Tibshirani

摘要

We study the Personalized PageRank (PPR) algorithm, a local spectral method for clustering, which extracts clusters using locally-biased random walks around a given seed node. In contrast to previous work, we adopt a classical statistical learning setup, where we obtain samples from an unknown nonparametric distribution, and aim to identify sufficiently salient clusters. We introduce a trio of population-level functionals---the normalized cut, conductance, and local spread, analogous to graph-based functionals of the same name---and prove that PPR, run on a neighborhood graph, recovers clusters with small population normalized cut and large conductance and local spread. We apply our general theory to establish that PPR identifies connected regions of high density (density clusters) that satisfy a set of natural geometric conditions. We also show a converse result, that PPR can fail to recover geometrically poorly-conditioned density clusters, even asymptotically. Finally, we provide empirical support for our theory.

JMLR Machine Learning · 发表于 2021

Stable-Baselines3: Reliable Reinforcement Learning Implementations

Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, Noah Dormann

摘要

Stable-Baselines3 provides open-source implementations of deep reinforcement learning (RL) algorithms in Python. The implementations have been benchmarked against reference codebases, and automated unit tests cover 95% of the code. The algorithms follow a consistent interface and are accompanied by extensive documentation, making it simple to train and compare different RL algorithms. Our documentation, examples, and source-code are available at https://github.com/DLR-RM/stable-baselines3.

Econometrica Latent Variables & Mixtures · 发表于 2021

Spurious Factor Analysis

Alexei Onatski, Chen Wang

摘要

This paper draws parallels between the principal components analysis of factorless high‐dimensional nonstationary data and the classical spurious regression. We show that a few of the principal components of such data absorb nearly all the data variation. The corresponding scree plot suggests that the data contain a few factors, which is corroborated by the standard panel information criteria. Furthermore, the Dickey–Fuller tests of the unit root hypothesis applied to the estimated “idiosyncratic terms” often reject, creating an impression that a few factors are responsible for most of the nonstationarity in the data. We warn empirical researchers of these peculiar effects and suggest to always compare the analysis in levels with that in differences.

JMLR Machine Learning High-Dimensional Networks & Graphs · 发表于 2021

Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networks

Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, Alexandra Peste

摘要

The growing energy and performance costs of deep learning have driven the community to reduce the size of neural networks by selectively pruning components. Similarly to their biological counterparts, sparse networks generalize just as well, sometimes even better than, the original dense networks. Sparsity promises to reduce the memory footprint of regular networks to fit mobile devices, as well as shorten training time for ever growing networks. In this paper, we survey prior work on sparsity in deep learning and provide an extensive tutorial of sparsification for both inference and training. We describe approaches to remove and add elements of neural networks, different training strategies to achieve model sparsity, and mechanisms to exploit sparsity in practice. Our work distills ideas from more than 300 research papers and provides guidance to practitioners who wish to utilize sparsity today, as well as to researchers whose goal is to push the frontier forward. We include the necessary background on mathematical methods in sparsification, describe phenomena such as early structure adaptation, the intricate relations between sparsity and the training process, and show techniques for achieving acceleration on real hardware. We also define a metric of pruned parameter efficiency that could serve as a baseline for comparison of different sparse networks. We close by speculating on how sparsity can improve future workloads and outline major open problems in the field.

JMLR High-Dimensional · 发表于 2021

Sparse and Smooth Signal Estimation: Convexification of L0-Formulations

Alper Atamturk, Andres Gomez, Shaoning Han

摘要

Signal estimation problems with smoothness and sparsity priors can be naturally modeled as quadratic optimization with $\ell_0$-“norm” constraints. Since such problems are non-convex and hard-to-solve, the standard approach is, instead, to tackle their convex surrogates based on $\ell_1$-norm relaxations. In this paper, we propose new iterative (convex) conic quadratic relaxations that exploit not only the $\ell_0$-“norm” terms, but also the fitness and smoothness functions. The iterative convexification approach substantially closes the gap between the $\ell_0$-“norm” and its $\ell_1$ surrogate. These stronger relaxations lead to significantly better estimators than $\ell_1$-norm approaches and also allow one to utilize affine sparsity priors. In addition, the parameters of the model and the resulting estimators are easily interpretable. Experiments with a tailored Lagrangian decomposition method indicate that the proposed iterative convex relaxations yield solutions within 1\% of the exact $\ell_0$-approach, and can tackle instances with up to 100,000 variables under one minute.

JMLR High-Dimensional · 发表于 2021

Sparse Tensor Additive Regression

Botao Hao, Boxiang Wang, Pengyuan Wang, Jingfei Zhang, Jian Yang, Will Wei Sun

摘要

Tensors are becoming prevalent in modern applications such as medical imaging and digital marketing. In this paper, we propose a sparse tensor additive regression (STAR) that models a scalar response as a flexible nonparametric function of tensor covariates. The proposed model effectively exploits the sparse and low-rank structures in the tensor additive regression. We formulate the parameter estimation as a non-convex optimization problem, and propose an efficient penalized alternating minimization algorithm. We establish a non-asymptotic error bound for the estimator obtained from each iteration of the proposed algorithm, which reveals an interplay between the optimization error and the statistical rate of convergence. We demonstrate the efficacy of STAR through extensive comparative simulation studies, and an application to the click-through-rate prediction in online advertising.

JMLR High-Dimensional Networks & Graphs · 发表于 2021

Sparse Popularity Adjusted Stochastic Block Model

Majid Noroozi, Marianna Pensky, Ramchandra Rimal

摘要

In the present paper we study a sparse stochastic network enabled with a block structure. The popular Stochastic Block Model (SBM) and the Degree Corrected Block Model (DCBM) address sparsity by placing an upper bound on the maximum probability of connections between any pair of nodes. As a result, sparsity describes only the behavior of network as a whole, without distinguishing between the block-dependent sparsity patterns. To the best of our knowledge, the recently introduced Popularity Adjusted Block Model (PABM) is the only block model that allows to introduce a structural sparsity where some probabilities of connections are identically equal to zero while the rest of them remain above a certain threshold. The latter presents a more nuanced view of the network.

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

Sparse Convex Optimization via Adaptively Regularized Hard Thresholding

Kyriakos Axiotis, Maxim Sviridenko

摘要

The goal of Sparse Convex Optimization is to optimize a convex function f under a sparsity constraint s = 1 is an approximation factor. There has been a lot of work to analyze the sparsity guarantees of various algorithms (LASSO, Orthogonal Matching Pursuit (OMP), Iterative Hard Thresholding (IHT)) in terms of the Restricted Condition Number κ. The best known algorithms guarantee to find an approximate solution of value f(x*)+ε with the sparsity bound of γ = O(κ min{log ((f(x0)-f(x*)) / ε), κ}), where x* is the target solution. We present a new Adaptively Regularized Hard Thresholding (ARHT) algorithm that makes significant progress on this problem by bringing the bound down to γ=O(κ), which has been shown to be tight for a general class of algorithms including LASSO, OMP, and IHT. This is achieved without significant sacrifice in the runtime efficiency compared to the fastest known algorithms. We also provide a new analysis of OMP with Replacement (OMPR) for general f, under the condition s > s* κ^2 / 4, which yields compressed sensing bounds under the Restricted Isometry Property (RIP). When compared to other compressed sensing approaches, it has the advantage of providing a strong tradeoff between the RIP condition and the solution sparsity, while working for any general function f that meets the RIP condition.

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

Some Theoretical Insights into Wasserstein GANs

Gérard Biau, Maxime Sangnier, Ugo Tanielian

摘要

Generative Adversarial Networks (GANs) have been successful in producing outstanding results in areas as diverse as image, video, and text generation. Building on these successes, a large number of empirical studies have validated the benefits of the cousin approach called Wasserstein GANs (WGANs), which brings stabilization in the training process. In the present paper, we add a new stone to the edifice by proposing some theoretical advances in the properties of WGANs. First, we properly define the architecture of WGANs in the context of integral probability metrics parameterized by neural networks and highlight some of their basic mathematical features. We stress in particular interesting optimization properties arising from the use of a parametric 1-Lipschitz discriminator. Then, in a statistically-driven approach, we study the convergence of empirical WGANs as the sample size tends to infinity, and clarify the adversarial effects of the generator and the discriminator by underlining some trade-off properties. These features are finally illustrated with experiments using both synthetic and real-world datasets.

JMLR Other · 发表于 2021

Soft Tensor Regression

Georgia Papadogeorgou, Zhengwu Zhang, David B. Dunson

摘要

Statistical methods relating tensor predictors to scalar outcomes in a regression model generally vectorize the tensor predictor and estimate the coefficients of its entries employing some form of regularization, use summaries of the tensor covariate, or use a low dimensional approximation of the coefficient tensor. However, low rank approximations of the coefficient tensor can suffer if the true rank is not small. We propose a tensor regression framework which assumes a soft version of the parallel factors (PARAFAC) approximation. In contrast to classic PARAFAC where each entry of the coefficient tensor is the sum of products of row-specific contributions across the tensor modes, the soft tensor regression (Softer) framework allows the row-specific contributions to vary around an overall mean. We follow a Bayesian approach to inference, and show that softening the PARAFAC increases model flexibility, leads to improved estimation of coefficient tensors, more accurate identification of important predictor entries, and more precise predictions, even for a low approximation rank. From a theoretical perspective, we show that employing Softer leads to a weakly consistent posterior distribution of the coefficient tensor, irrespective of the true or approximation tensor rank, a result that is not true when employing the classic PARAFAC for tensor regression. In the context of our motivating application, we adapt Softer to symmetric and semi-symmetric tensor predictors and analyze the relationship between brain network characteristics and human traits.

JMLR Spatial & Time Series · 发表于 2021

Single and Multiple Change-Point Detection with Differential Privacy

Wanrong Zhang, Sara Krehbiel, Rui Tuo, Yajun Mei, Rachel Cummings

摘要

The change-point detection problem seeks to identify distributional changes at an unknown change-point $k^*$ in a stream of data. This problem appears in many important practical settings involving personal data, including biosurveillance, fault detection, finance, signal detection, and security systems. The field of differential privacy offers data analysis tools that provide powerful worst-case privacy guarantees. We study the statistical problem of change-point detection through the lens of differential privacy. We give private algorithms for both online and offline change-point detection, analyze these algorithms theoretically, and provide empirical validation of our results.

JMLR Spatial & Time Series Networks & Graphs High-Dimensional · 发表于 2021

Simultaneous Change Point Inference and Structure Recovery for High Dimensional Gaussian Graphical Models

Bin Liu, Xinsheng Zhang, Yufeng Liu

摘要

In this article, we investigate the problem of simultaneous change point inference and structure recovery in the context of high dimensional Gaussian graphical models with possible abrupt changes. In particular, motivated by neighborhood selection, we incorporate a threshold variable and an unknown threshold parameter into a joint sparse regression model which combines p l1-regularized node-wise regression problems together. The change point estimator and the corresponding estimated coefficients of precision matrices are obtained together. Based on that, a classifier is introduced to distinguish whether a change point exists. To recover the graphical structure correctly, a data-driven thresholding procedure is proposed. In theory, under some sparsity conditions and regularity assumptions, our method can correctly choose a homogeneous or heterogeneous model with high accuracy. Furthermore, in the latter case with a change point, we establish estimation consistency of the change point estimator, by allowing the number of nodes being much larger than the sample size. Moreover, it is shown that, in terms of structure recovery of Gaussian graphical models, the proposed thresholding procedure achieves model selection consistency and controls the number of false positives. The validity of our proposed method is justified via extensive numerical studies. Finally, we apply our proposed method to the S&P 500 dataset to show its empirical usefulness.

JMLR Machine Learning · 发表于 2021

Simple and Fast Algorithms for Interactive Machine Learning with Random Counter-examples

Jagdeep Singh Bhatia

摘要

This work describes simple and efficient algorithms for interactively learning non-binary concepts in the learning from random counter-examples (LRC) model. Here, learning takes place from random counter-examples that the learner receives in response to their proper equivalence queries, and the learning time is the number of counter-examples needed by the learner to identify the target concept. Such learning is particularly suited for online ranking, classification, clustering, etc., where machine learning models must be used before they are fully trained. We provide two simple LRC algorithms, deterministic and randomized, for exactly learning concepts from any concept class $H$. We show that both these algorithms have an $\mathcal{O}(\log{}|H|)$ asymptotically optimal average learning time. This solves an open problem on the existence of an efficient LRC randomized algorithm while also simplifying previous results and improving their computational efficiency. We also show that the expected learning time of any Arbitrary LRC algorithm can be upper bounded by $\mathcal{O}(\frac{1}{\epsilon}\log{\frac{|H|}{\delta}})$, where $\epsilon$ and $\delta$ are the allowed learning error and failure probability respectively. This shows that LRC interactive learning is at least as efficient as non-interactive Probably Approximately Correct (PAC) learning. Our simulations also show that these algorithms outperform their theoretical bounds.

JMLR Other · 发表于 2021

Shape-Enforcing Operators for Generic Point and Interval Estimators of Functions

Xi Chen, Victor Chernozhukov, Ivan Fernandez-Val, Scott Kostyshak, Ye Luo

摘要

A common problem in econometrics, statistics, and machine learning is to estimate and make inference on functions that satisfy shape restrictions. For example, distribution functions are nondecreasing and range between zero and one, height growth charts are nondecreasing in age, and production functions are nondecreasing and quasi-concave in input quantities. We propose a method to enforce these restrictions ex post on generic unconstrained point and interval estimates of the target function by applying functional operators. The interval estimates could be either frequentist confidence bands or Bayesian credible regions. If an operator has reshaping, invariance, order-preserving, and distance-reducing properties, the shape-enforced point estimates are closer to the target function than the original point estimates and the shape-enforced interval estimates have greater coverage and shorter length than the original interval estimates. We show that these properties hold for six different operators that cover commonly used shape restrictions in practice: range, convexity, monotonicity, monotone convexity, quasi-convexity, and monotone quasi-convexity, with the latter two restrictions being of paramount importance. The main attractive property of the post-processing approach is that it works in conjunction with any generic initial point or interval estimate, obtained using any of parametric, semi-parametric or nonparametric learning methods, including recent methods that are able to exploit either smoothness, sparsity, or other forms of structured parsimony of target functions. The post-processed point and interval estimates automatically inherit and provably improve these properties in finite samples, while also enforcing qualitative shape restrictions brought by scientific reasoning. We illustrate the results with two empirical applications to the estimation of a height growth chart for infants in India and a production function for chemical firms in China.

Econometrica Other · 发表于 2021

Selecting Applicants

Alex Frankel

摘要

A firm selects applicants to hire based on hard information, such as a test result, and soft information, such as a manager's evaluation of an interview. The contract that the firm offers to the manager can be thought of as a restriction on acceptance rates as a function of test results. I characterize optimal acceptance rate functions both when the firm knows the manager's mix of information and biases and when the firm is uncertain. These contracts may admit a simple implementation in which the manager can accept any set of applicants with a sufficiently high average test score.

Econometrica Econometrics & Economics · 发表于 2021

Screening in Vertical Oligopolies

Hector Chade, Jeroen Swinkels

摘要

A finite number of vertically differentiated firms simultaneously compete for and screen agents with private information about their payoffs. In equilibrium, higher firms serve higher types. Each firm distorts the allocation downward from the efficient level on types below a threshold, but upward above. While payoffs in this game are neither quasi‐concave nor continuous, if firms are sufficiently differentiated, then any strategy profile that satisfies a simple set of necessary conditions is a pure‐stategy equilibrium, and an equilibrium exists. A mixed‐strategy equilibrium exists even when firms are less differentiated. The welfare effects of private information are drastically different than under monopoly. The equilibrium approaches the competitive limit quickly as entry costs grow small. We solve the problem of a multi‐plant firm facing a type‐dependent outside option and use this to study the effect of mergers.

Econometrica Causal Inference · 发表于 2021

Salvaging Falsified Instrumental Variable Models

Matthew A. Masten, Alexandre Poirier

摘要

What should researchers do when their baseline model is falsified? We recommend reporting the set of parameters that are consistent with minimally nonfalsified models. We call this thefalsification adaptive set(FAS). This set generalizes the standard baseline estimand to account for possible falsification. Importantly, it does not require the researcher to select or calibrate sensitivity parameters. In the classical linear IV model with multiple instruments, we show that the FAS has a simple closed‐form expression that only depends on a few 2SLS coefficients. We apply our results to an empirical study of roads and trade. We show how the FAS complements traditional overidentification tests by summarizing the variation in estimates obtained from alternative nonfalsified models.

Econometrica Other · 发表于 2021

Sales and Markup Dispersion: Theory and Empirics

Monika Mrázová, J. Peter Neary, Mathieu Parenti

摘要

We characterize the relationship between the distributions of two variables linked by a structural model. We then show that, in models of heterogeneous firms in monopolistic competition, this relationship implies a new demand function that we call “CREMR” (Constant Revenue Elasticity of Marginal Revenue). This demand function is the only one that is consistent with productivity and sales distributions having the same form (whether Pareto, lognormal, or Fréchet) in the cross section, and it is necessary and sufficient for Gibrat's Law to hold over time. Among the applications we consider, we use our methodology to characterize misallocation across firms; we derive the distribution of markups implied by any assumptions on demand and productivity; and we show empirically that CREMR‐based markup distributions provide an excellent parsimonious fit to Indian firm‐level data, which in turn allows us to calculate the proportion of firms that are of suboptimal size in the market equilibrium.

JMLR Other · 发表于 2021

Safe Policy Iteration: A Monotonically Improving Approximate Policy Iteration Approach

Alberto Maria Metelli, Matteo Pirotta, Daniele Calandriello, Marcello Restelli

摘要

This paper presents a study of the policy improvement step that can be usefully exploited by approximate policy-iteration algorithms. When either the policy evaluation step or the policy improvement step returns an approximated result, the sequence of policies produced by policy iteration may not be monotonically increasing, and oscillations may occur. To address this issue, we consider safe policy improvements, i.e., at each iteration, we search for a policy that maximizes a lower bound to the policy improvement w.r.t. the current policy, until no improving policy can be found. We propose three safe policy-iteration schemas that differ in the way the next policy is chosen w.r.t. the estimated greedy policy. Besides being theoretically derived and discussed, the proposed algorithms are empirically evaluated and compared on some chain-walk domains, the prison domain, and on the Blackjack card game.

Econometrica Bayesian Methods · 发表于 2021

Robust Bayesian Inference for Set‐Identified Models

Raffaella Giacomini, Toru Kitagawa

摘要

This paper reconciles the asymptotic disagreement between Bayesian and frequentist inference in set‐identified models by adopting a multiple‐prior (robust) Bayesian approach. We propose new tools for Bayesian inference in set‐identified models and show that they have a well‐defined posterior interpretation in finite samples and are asymptotically valid from the frequentist perspective. The main idea is to construct a prior class that removes the source of the disagreement: the need to specify an unrevisable prior for the structural parameter given the reduced‐form parameter. The corresponding class of posteriors can be summarized by reporting the ‘posterior lower and upper probabilities’ of a given event and/or the ‘set of posterior means’ and the associated ‘robust credible region’. We show that the set of posterior means is a consistent estimator of the true identified set and the robust credible region has the correct frequentist asymptotic coverage for the true identified set if it is convex. Otherwise, the method provides posterior inference about the convex hull of the identified set. For impulse‐response analysis in set‐identified Structural Vector Autoregressions, the new tools can be used to overcome or quantify the sensitivity of standard Bayesian inference to the choice of an unrevisable prior.

JMLR Machine Learning · 发表于 2021

River: machine learning for streaming data in Python

Jacob Montiel, Max Halford, Saulo Martiello Mastelini, Geoffrey Bolmier, Raphael Sourty, Robin Vaysse, Adil Zouitine, Heitor Murilo Gomes, Jesse Read, Talel Abdessalem, Albert Bifet

摘要

River is a machine learning library for dynamic data streams and continual learning. It provides multiple state-of-the-art learning methods, data generators/transformers, performance metrics and evaluators for different stream learning problems. It is the result from the merger of two popular packages for stream learning in Python: Creme and scikit-multiflow. River introduces a revamped architecture based on the lessons learnt from the seminal packages. River's ambition is to be the go-to library for doing machine learning on streaming data. Additionally, this open source package brings under the same umbrella a large community of practitioners and researchers. The source code is available at https://github.com/online-ml/river.

JMLR Other · 发表于 2021

Risk-Averse Learning by Temporal Difference Methods with Markov Risk Measures

Umit Köse, Andrzej Ruszczyński

摘要

We propose a novel reinforcement learning methodology where the system performance is evaluated by a Markov coherent dynamic risk measure with the use of linear value function approximations. We construct projected risk-averse dynamic programming equations and study their properties. We propose new risk-averse counterparts of the basic and multi-step methods of temporal differences and we prove their convergence with probability one. We also perform an empirical study on a complex transportation problem.

JMLR Other · 发表于 2021

Risk Bounds for Unsupervised Cross-Domain Mapping with IPMs

Tomer Galanti, Sagie Benaim, Lior Wolf

摘要

The recent empirical success of unsupervised cross-domain mapping algorithms, in mapping between two domains that share common characteristics, is not well-supported by theoretical justifications. This lacuna is especially troubling, given the clear ambiguity in such mappings. We work with adversarial training methods based on integral probability metrics (IPMs) and derive a novel risk bound, which upper bounds the risk between the learned mapping $h$ and the target mapping $y$, by a sum of three terms: (i) the risk between $h$ and the most distant alternative mapping that was learned by the same cross-domain mapping algorithm, (ii) the minimal discrepancy between the target domain and the domain obtained by applying a hypothesis $h^*$ on the samples of the source domain, where $h^*$ is a hypothesis selectable by the same algorithm, and (iii) an approximation error term that decreases as the capacity of the class of discriminators increases and is empirically shown to be small. The bound is directly related to Occam's razor and encourages the selection of the minimal architecture that supports a small mapping discrepancy. The bound leads to multiple algorithmic consequences, including a method for hyperparameter selection and early stopping in cross-domain mapping.

JMLR Other · 发表于 2021

Revisiting Model-Agnostic Private Learning: Faster Rates and Active Learning

Chong Liu, Yuqing Zhu, Kamalika Chaudhuri, Yu-Xiang Wang

摘要

The Private Aggregation of Teacher Ensembles (PATE) framework is one of the most promising recent approaches in differentially private learning. Existing theoretical analysis shows that PATE consistently learns any VC-classes in the realizable setting, but falls short in explaining its success in more general cases where the error rate of the optimal classifier is bounded away from zero. We fill in this gap by introducing the Tsybakov Noise Condition (TNC) and establish stronger and more interpretable learning bounds. These bounds provide new insights into when PATE works and improve over existing results even in the narrower realizable setting. We also investigate the compelling idea of using active learning for saving privacy budget, and empirical studies show the effectiveness of this new idea. The novel components in the proofs include a more refined analysis of the majority voting classifier --- which could be of independent interest --- and an observation that the synthetic "student" learning problem is nearly realizable by construction under the Tsybakov noise condition.

JMLR Other · 发表于 2021

Residual Energy-Based Models for Text

Anton Bakhtin, Yuntian Deng, Sam Gross, Myle Ott, Marc'Aurelio Ranzato, Arthur Szlam

摘要

Current large-scale auto-regressive language models display impressive fluency and can generate convincing text. In this work we start by asking the question: Can the generations of these models be reliably distinguished from real text by statistical discriminators? We find experimentally that the answer is affirmative when we have access to the training data for the model, and guardedly affirmative even if we do not. This suggests that the auto-regressive models can be improved by incorporating the (globally normalized) discriminators into the generative process. We give a formalism for this using the Energy-Based Model framework, and show that it indeed improves the results of the generative models, measured both in terms of perplexity and in terms of human evaluation.

Econometrica Other · 发表于 2021

Reputation and Sovereign Default

Manuel Amador, Christopher Phelan

摘要

This paper presents a continuous‐time model of sovereign debt. In it, a relatively impatient sovereign government's hidden type switches back and forth between a commitment type, which cannot default, and an opportunistic type, which can, and where we assume outside lenders have particular beliefs regarding how a commitment type should borrow for any given level of debt and bond price. In any Markov equilibrium, the opportunistic type mimics the commitment type when borrowing, revealing its type only by defaulting on its debt at random times. The equilibrium features a “graduation date”: a finite amount of time since the last default, after which time reputation reaches its highest level and is unaffected by not defaulting. Before such date, not defaulting always increases the country's reputation. For countries that have recently defaulted, bond prices and the total amount of debt are increasing functions of the amount of time since the country's last default. For countries that have not recently defaulted (i.e., those that have graduated), bond prices are constant.

JMLR Nonparametric & Semiparametric · 发表于 2021

Reproducing kernel Hilbert C*-module and kernel mean embeddings

Yuka Hashimoto, Isao Ishikawa, Masahiro Ikeda, Fuyuta Komura, Takeshi Katsura, Yoshinobu Kawahara

摘要

Kernel methods have been among the most popular techniques in machine learning, where learning tasks are solved using the property of reproducing kernel Hilbert space (RKHS). In this paper, we propose a novel data analysis framework with reproducing kernel Hilbert $C^*$-module (RKHM) and kernel mean embedding (KME) in RKHM. Since RKHM contains richer information than RKHS or vector-valued RKHS (vvRKHS), analysis with RKHM enables us to capture and extract structural properties in such as functional data. We show a branch of theories for RKHM to apply to data analysis, including the representer theorem, and the injectivity and universality of the proposed KME. We also show RKHM generalizes RKHS and vvRKHS. Then, we provide concrete procedures for employing RKHM and the proposed KME to data analysis.

JMLR Other · 发表于 2021

Representer Theorems in Banach Spaces: Minimum Norm Interpolation, Regularized Learning and Semi-Discrete Inverse Problems

Rui Wang, Yuesheng Xu

摘要

Learning a function from a finite number of sampled data points (measurements) is a fundamental problem in science and engineering. This is often formulated as a minimum norm interpolation (MNI) problem, a regularized learning problem or, in general, a semi-discrete inverse problem (SDIP), in either Hilbert spaces or Banach spaces. The goal of this paper is to systematically study solutions of these problems in Banach spaces. We aim at obtaining explicit representer theorems for their solutions, on which convenient solution methods can then be developed. For the MNI problem, the explicit representer theorems enable us to express the infimum in terms of the norm of the linear combination of the interpolation functionals. For the purpose of developing efficient computational algorithms, we establish the fixed-point equation formulation of solutions of these problems. We reveal that unlike in a Hilbert space, in general, solutions of these problems in a Banach space may not be able to be reduced to truly finite dimensional problems (with certain infinite dimensional components hidden). We demonstrate how this obstacle can be removed, reducing the original problem to a truly finite dimensional one, in the special case when the Banach space is $\ell_1(\mathbb{N})$.

JMLR Optimization & Learning Theory · 发表于 2021

Replica Exchange for Non-Convex Optimization

Jing Dong, Xin T. Tong

摘要

Gradient descent (GD) is known to converge quickly for convex objective functions, but it can be trapped at local minima. On the other hand, Langevin dynamics (LD) can explore the state space and find global minima, but in order to give accurate estimates, LD needs to run with a small discretization step size and weak stochastic force, which in general slow down its convergence. This paper shows that these two algorithms can “collaborate" through a simple exchange mechanism, in which they swap their current positions if LD yields a lower objective function. This idea can be seen as the singular limit of the replica-exchange technique from the sampling literature. We show that this new algorithm converges to the global minimum linearly with high probability, assuming the objective function is strongly convex in a neighborhood of the unique global minimum. By replacing gradients with stochastic gradients, and adding a proper threshold to the exchange mechanism, our algorithm can also be used in online settings. We also study non-swapping variants of the algorithm, which achieve similar performance. We further verify our theoretical results through some numerical experiments and observe superior performances of the proposed algorithm over running GD or LD alone.

第 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 34 35 36 37 38 39 页