2021 年的期刊文章 · 第 34 页

共 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 Bayesian Methods · 发表于 2021

Mixing Time of Metropolis-Hastings for Bayesian Community Detection

Bumeng Zhuo, Chao Gao

摘要

We study the computational complexity of a Metropolis-Hastings algorithm for Bayesian community detection. We first establish a posterior strong consistency result for a natural prior distribution on stochastic block models under the optimal signal-to-noise ratio condition in the literature. We then give a set of conditions that guarantee rapidly mixing of a simple Metropolis-Hastings algorithm. The mixing time analysis is based on a careful study of posterior ratios and a canonical path argument to control the spectral gap of the Markov chain.

Econometrica Econometrics & Economics · 发表于 2021

Micro Data and Macro Technology

Ezra Oberfield, Devesh Raval

摘要

We develop a framework to estimate the aggregate capital‐labor elasticity of substitution by aggregating the actions of individual plants. The aggregate elasticity reflects substitution within plants and reallocation across plants; the extent of heterogeneity in capital intensities determines their relative importance. We use micro data on the cross‐section of plants to build up to the aggregate elasticity at a point in time. Interpreting our econometric estimates through the lens of several different models, we find that the aggregate elasticity for the U.S. manufacturing sector is in the range of 0.5–0.7, and has declined slightly since 1970. We use our estimates to measure the bias of technical change and assess the decline in labor's share of income in the U.S. manufacturing sector. Mechanisms that rely on changes in the relative supply of factors, such as an acceleration of capital accumulation, cannot account for the decline.

JMLR High-Dimensional · 发表于 2021

Method of Contraction-Expansion (MOCE) for Simultaneous Inference in Linear Models

Fei Wang, Ling Zhou, Lu Tang, Peter X.K. Song

摘要

Simultaneous inference after model selection is of critical importance to address scientific hypotheses involving a set of parameters. In this paper, we consider a high-dimensional linear regression model in which a regularization procedure such as LASSO is applied to yield a sparse model. To establish a simultaneous post-model selection inference, we propose a method of contraction and expansion (MOCE) along the line of debiasing estimation in that we investigate a desirable trade-off between model selection variability and sample variability by the means of forward screening. We establish key theoretical results for the inference from the proposed MOCE procedure. Once the expanded model is properly selected, the theoretical guarantees and simultaneous confidence regions can be constructed by the joint asymptotic normal distribution. In comparison with existing methods, our proposed method exhibits stable and reliable coverage at a nominal significance level and enjoys substantially less computational burden. Thus, our MOCE approach is trustworthy in solving real-world problems.

JMLR Other · 发表于 2021

MetaGrad: Adaptation using Multiple Learning Rates in Online Learning

Tim van Erven, Wouter M. Koolen, Dirk van der Hoeven

摘要

We provide a new adaptive method for online convex optimization, MetaGrad, that is robust to general convex losses but achieves faster rates for a broad class of special functions, including exp-concave and strongly convex functions, but also various types of stochastic and non-stochastic functions without any curvature. We prove this by drawing a connection to the Bernstein condition, which is known to imply fast rates in offline statistical learning. MetaGrad further adapts automatically to the size of the gradients. Its main feature is that it simultaneously considers multiple learning rates, which are weighted directly proportional to their empirical performance on the data using a new meta-algorithm. We provide three versions of MetaGrad. The full matrix version maintains a full covariance matrix and is applicable to learning tasks for which we can afford update time quadratic in the dimension. The other two versions provide speed-ups for high-dimensional learning tasks with an update time that is linear in the dimension: one is based on sketching, the other on running a separate copy of the basic algorithm per coordinate. We evaluate all versions of MetaGrad on benchmark online classification and regression tasks, on which they consistently outperform both online gradient descent and AdaGrad.

Econometrica Other · 发表于 2021

Media Capture Through Favor Exchange

Adam Szeidl, Ferenc Szucs

摘要

We use data from Hungary to establish two results about the relationship between the government and the media. (i) We document large advertising favors from the government to connected media, and large corruption coverage favors from connected media to the government. Our empirical strategy exploits sharp reallocations around changes in media ownership and other events to rule out market‐based explanations. (ii) Under the assumptions of a structural model, we distinguish between owner ideology and favor exchange as the mechanism driving favors. We estimate our model exploiting within‐owner changes in coverage for identification and find that both mechanisms are important. These results imply that targeted government advertising can meaningfully influence content. Counterfactuals show that targeted advertising can also influence owner ideology, by making media ownership more profitable to pro‐government connected investors. Our results are consistent with qualitative evidence from many democracies and suggest that government advertising affects media content worldwide.

JMLR Bayesian Methods · 发表于 2021

Matrix Product States for Inference in Discrete Probabilistic Models

Rasmus Bonnevie, Mikkel N. Schmidt

摘要

When faced with problems involving inference in discrete domains, solutions often involve appeals to conditional independence structure or mean-field approximations. We argue that this is insufficient for a number of interesting Bayesian problems, including mixture assignment posteriors and probabilistic relational models (e.g. the stochastic block model). These posteriors exhibit no conditional independence structure, precluding the use of graphical model methods, yet exhibit dependency between every single element of the posterior, making mean-field methods a poor fit. We propose using an expressive yet tractable approximation inspired by tensor factorization methods, alternately known as the tensor train or the matrix product state, and which can be construed of as a direct extension of the mean-field approximation to higher-order dependencies. We give a comprehensive introduction to the application of matrix product state in probabilistic inference, and illustrate how to efficiently perform marginalization, conditioning, sampling, normalization, some expectations, and approximate variational inference in our proposed model.

Econometrica Econometrics & Economics · 发表于 2021

Market Selection and the Information Content of Prices

Alp E. Atakan, Mehmet Ekmekci

摘要

We study information aggregation when n bidders choose, based on their private information, between two concurrent common‐value auctions. There are k s identical objects on sale through a uniform‐price auction in market s and there are an additional k r objects on auction in market r, which is identical to market s except for a positive reserve price. The reserve price in market r implies that information is not aggregated in this market. Moreover, if the object‐to‐bidder ratio in market s exceeds a certain cutoff, then information is not aggregated in market s either. Conversely, if the object‐to‐bidder ratio is less than this cutoff, then information is aggregated in market s as the market grows arbitrarily large. Our results demonstrate how frictions in one market can disrupt information aggregation in a linked, frictionless market because of the pattern of market selection by imperfectly informed bidders.

Econometrica Econometrics & Economics · 发表于 2021

Lumpy Durable Consumption Demand and the Limited Ammunition of Monetary Policy

Alisdair McKay, Johannes F. Wieland

摘要

The prevailing neo‐Wicksellian view holds that the central bank's objective is to track the natural rate of interest ( r * ), which itself is largely exogenous to monetary policy. We challenge this view using a fixed‐cost model of durable consumption demand, in which expansionary monetary policy prompts households to accelerate purchases of durable goods. This yields an intertemporal trade‐off in aggregate demand as encouraging households to increase durable holdings today leaves fewer households acquiring durables going forward. Interest rates must be kept low to support demand going forward, so accommodative monetary policy today reduces r * in the future. We show that this mechanism is quantitatively important in explaining the persistently low level of real interest rates and r * after the Great Recession.

Econometrica Other · 发表于 2021

Long‐Term Contracting With Time‐Inconsistent Agents

Daniel Gottlieb, Xingtan Zhang

摘要

We study contracts between naive present‐biased consumers and risk‐neutral firms. We show that the welfare loss from present bias vanishes as the contracting horizon grows. This is true both when bargaining power is on the consumers' and on the firms' side, when consumers cannot commit to long‐term contracts, and when firms do not know the consumers' naiveté. However, the welfare loss from present bias does not vanish when firms do not know the consumers' present bias or when they cannot offer exclusive contracts.

Econometrica Econometrics & Economics · 发表于 2021

Location as an Asset

Adrien Bilal, Esteban Rossi-Hansberg

摘要

The location of individuals determines their job and schooling opportunities, amenities, and housing costs. We conceptualize the location choice of individuals as a decision to invest in a “location asset.” This asset has a current cost equal to the location's rent, and a future payoff through better job and schooling opportunities. As with any asset, savers in the location asset transfer resources into the future by going to expensive locations with high future returns. In contrast, borrowers transfer resources to the present by going to cheap locations that offer few other advantages. Holdings of the location asset depend on its comparison to other assets, with the distinction that the location asset is not subject to borrowing constraints. We propose a dynamic location model and derive an agent's mobility choices after experiencing income shocks. We document the investment dimension of location and confirm the core predictions of our theory using French individual panel data from tax returns.

JMLR Latent Variables & Mixtures · 发表于 2021

Locally Private k-Means Clustering

Uri Stemmer

摘要

We design a new algorithm for the Euclidean $k$-means problem that operates in the local model of differential privacy. Unlike in the non-private literature, differentially private algorithms for the $k$-means objective incur both additive and multiplicative errors. Our algorithm significantly reduces the additive error while keeping the multiplicative error the same as in previous state-of-the-art results. Specifically, on a database of size $n$, our algorithm guarantees $O(1)$ multiplicative error and $\approx n^{1/2+a}$ additive error for an arbitrarily small constant $a>0$. All previous algorithms in the local model had additive error $\approx n^{2/3+a}$. Our techniques extend to $k$-median clustering. We show that the additive error we obtain is almost optimal in terms of its dependency on the database size $n$. Specifically, we give a simple lower bound showing that every locally-private algorithm for the $k$-means objective must have additive error at least $\approx\sqrt{n}$.

JMLR Econometrics & Economics · 发表于 2021

Locally Differentially-Private Randomized Response for Discrete Distribution Learning

Adriano Pastore, Michael Gastpar

摘要

We consider a setup in which confidential i.i.d. samples $X_1,\dotsc,X_n$ from an unknown finite-support distribution $\boldsymbol{p}$ are passed through $n$ copies of a discrete privatization channel (a.k.a. mechanism) producing outputs $Y_1,\dotsc,Y_n$. The channel law guarantees a local differential privacy of $\epsilon$. Subject to a prescribed privacy level $\epsilon$, the optimal channel should be designed such that an estimate of the source distribution based on the channel outputs $Y_1,\dotsc,Y_n$ converges as fast as possible to the exact value $\boldsymbol{p}$. For this purpose we study the convergence to zero of three distribution distance metrics: $f$-divergence, mean-squared error and total variation. We derive the respective normalized first-order terms of convergence (as $n \to \infty$), which for a given target privacy $\epsilon$ represent a rule-of-thumb factor by which the sample size must be augmented so as to achieve the same estimation accuracy as that of a non-randomizing channel. We formulate the privacy-fidelity trade-off problem as being that of minimizing said first-order term under a privacy constraint $\epsilon$. We further identify a scalar quantity that captures the essence of this trade-off, and prove bounds and data-processing inequalities on this quantity. For some specific instances of the privacy-fidelity trade-off problem, we derive inner and outer bounds on the optimal trade-off curve.

JMLR Other · 发表于 2021

LocalGAN: Modeling Local Distributions for Adversarial Response Generation

Baoxun Wang, Zhen Xu, Huan Zhang, Kexin Qiu, Deyuan Zhang, Chengjie Sun

摘要

This paper presents a new methodology for modeling the local semantic distribution of responses to a given query in the human-conversation corpus, and on this basis, explores a specified adversarial learning mechanism for training Neural Response Generation (NRG) models to build conversational agents. Our investigation begins with the thorough discus- sions upon the objective function of general Generative Adversarial Nets (GAN) architectures, and the training instability problem is proved to be highly relative with the special local distributions of conversational corpora. Consequently, an energy function is employed to estimate the status of a local area restricted by the query and its responses in the semantic space, and the mathematical approximation of this energy-based distribution is finally found. Building on this foundation, a local distribution oriented objective is proposed and combined with the original objective, working as a hybrid loss for the adversarial training of response generation models, named as LocalGAN. Our experimental results demonstrate that the reasonable local distribution modeling of the query-response corpus is of great importance to adversarial NRG, and our proposed LocalGAN is promising for improving both the training stability and the quality of generated results.

Econometrica Other · 发表于 2021

Local Projections and VARs Estimate the Same Impulse Responses

Mikkel Plagborg-Møller, Christian K. Wolf

摘要

We prove that local projections (LPs) and Vector Autoregressions (VARs) estimate the same impulse responses. This nonparametric result only requires unrestricted lag structures. We discuss several implications: (i) LP and VAR estimators are not conceptually separate procedures; instead, they are simply two dimension reduction techniques with common estimand but different finite‐sample properties. (ii) VAR‐based structural identification—including short‐run, long‐run, or sign restrictions—can equivalently be performed using LPs, and vice versa. (iii) Structural estimation with an instrument (proxy) can be carried out by ordering the instrument first in a recursive VAR, even under noninvertibility. (iv) Linear VARs are as robust to nonlinearities as linear LPs.

Econometrica Other · 发表于 2021

Local Projection Inference Is Simpler and More Robust Than You Think

José Luis Montiel Olea, Mikkel Plagborg-Møller

摘要

Applied macroeconomists often compute confidence intervals for impulse responses using local projections, that is, direct linear regressions of future outcomes on current covariates. This paper proves that local projection inference robustly handles two issues that commonly arise in applications: highly persistent data and the estimation of impulse responses at long horizons. We consider local projections that control for lags of the variables in the regression. We show that lag‐augmented local projections with normal critical values are asymptotically valid uniformly over (i) both stationary and non‐stationary data, and also over (ii) a wide range of response horizons. Moreover, lag augmentation obviates the need to correct standard errors for serial correlation in the regression residuals. Hence, local projection inference is arguably both simpler than previously thought and more robust than standard autoregressive inference, whose validity is known to depend sensitively on the persistence of the data and on the length of the horizon.

JMLR Optimization & Learning Theory · 发表于 2021

Linear Bandits on Uniformly Convex Sets

Thomas Kerdreux, Christophe Roux, Alexandre d'Aspremont, Sebastian Pokutta

摘要

Linear bandit algorithms yield $\tilde{\mathcal{O}}(n\sqrt{T})$ pseudo-regret bounds on compact convex action sets $\mathcal{K}\subset\mathbb{R}^n$ and two types of structural assumptions lead to better pseudo-regret bounds. When $\mathcal{K}$ is the simplex or an $\ell_p$ ball with $p\in]1,2]$, there exist bandits algorithms with $\tilde{\mathcal{O}}(\sqrt{nT})$ pseudo-regret bounds. Here, we derive bandit algorithms for some strongly convex sets beyond $\ell_p$ balls that enjoy pseudo-regret bounds of $\tilde{\mathcal{O}}(\sqrt{nT})$. This result provides new elements for the open question in Bubeck and Cesa-Bianchi, 2012. When the action set is $q$-uniformly convex but not necessarily strongly convex ($q >2$), we obtain pseudo-regret bounds $\tilde{\mathcal{O}}(n^{1/q}T^{1/p})$ with $p$ s.t. $1/p + 1/q=1$. These pseudo-regret bounds are competitive with the general $\tilde{\mathcal{O}}(n\sqrt{T})$ for a time horizon range that depends on the degree $q>2$ of the set's uniform convexity and the dimension $n$ of the problem.

JMLR Networks & Graphs · 发表于 2021

Limit theorems for out-of-sample extensions of the adjacency and Laplacian spectral embeddings

Keith D. Levin, Fred Roosta, Minh Tang, Michael W. Mahoney, Carey E. Priebe

摘要

Graph embeddings, a class of dimensionality reduction techniques designed for relational data, have proven useful in exploring and modeling network structure. Most dimensionality reduction methods allow out-of-sample extensions, by which an embedding can be applied to observations not present in the training set. Applied to graphs, the out-of-sample extension problem concerns how to compute the embedding of a vertex that is added to the graph after an embedding has already been computed. In this paper, we consider the out-of-sample extension problem for two graph embedding procedures: the adjacency spectral embedding and the Laplacian spectral embedding. In both cases, we prove that when the underlying graph is generated according to a latent space model called the random dot product graph, which includes the popular stochastic block model as a special case, an out-of-sample extension based on a least-squares objective obeys a central limit theorem. In addition, we prove a concentration inequality for the out-of-sample extension of the adjacency spectral embedding based on a maximum-likelihood objective. Our results also yield a convenient framework in which to analyze trade-offs between estimation accuracy and computational expenses, which we explore briefly. Finally, we explore the performance of these out-of-sample extensions as applied to both simulated and real-world data. We observe significant computational savings with minimal losses to the quality of the learned embeddings, in keeping with our theoretical results.

Econometrica Econometrics & Economics · 发表于 2021

Limit Points of Endogenous Misspecified Learning

Drew Fudenberg, Giacomo Lanzani, Philipp Strack

摘要

We study how an agent learns from endogenous data when their prior belief is misspecified. We show that only uniform Berk–Nash equilibria can be long‐run outcomes, and that all uniformly strict Berk–Nash equilibria have an arbitrarily high probability of being the long‐run outcome for some initial beliefs. When the agent believes the outcome distribution is exogenous, every uniformly strict Berk–Nash equilibrium has positive probability of being the long‐run outcome for any initial belief. We generalize these results to settings where the agent observes a signal before acting.

JMLR Latent Variables & Mixtures · 发表于 2021

Learning with semi-definite programming: statistical bounds based on fixed point analysis and excess risk curvature

Stéphane Chrétien, Mihai Cucuringu, Guillaume Lecué, Lucie Neirac

摘要

Many statistical learning problems have recently been shown to be amenable to Semi-Definite Programming (SDP), with community detection and clustering in Gaussian mixture models as the most striking instances Javanmard et al. (2016). Given the growing range of applications of SDP-based techniques to machine learning problems, and the rapid progress in the design of efficient algorithms for solving SDPs, an intriguing question is to understand how the recent advances from empirical process theory and Statistical Learning Theory can be leveraged for providing a precise statistical analysis of SDP estimators. In the present paper, we borrow cutting edge techniques and concepts from the Learning Theory literature, such as fixed point equations and excess risk curvature arguments, which yield general estimation and prediction results for a wide class of SDP estimators. From this perspective, we revisit some classical results in community detection from Guédon and Vershynin (2016) and Fei and Chen (2019), and we obtain statistical guarantees for SDP estimators used in signed clustering, angular group synchronization (for both multiplicative and additive models) and MAX-CUT. Our theoretical findings are complemented by numerical experiments for each of the three problems considered, showcasing the competitiveness of the SDP estimators.

JMLR Networks & Graphs · 发表于 2021

Learning partial correlation graphs and graphical models by covariance queries

Gábor Lugosi, Jakub Truszkowski, Vasiliki Velona, Piotr Zwiernik

摘要

We study the problem of recovering the structure underlying large Gaussian graphical models or, more generally, partial correlation graphs. In high-dimensional problems it is often too costly to store the entire sample covariance matrix. We propose a new input model in which one can query single entries of the covariance matrix. We prove that it is possible to recover the support of the inverse covariance matrix with low query and computational complexity. Our algorithms work in a regime when this support is represented by tree-like graphs and, more generally, for graphs of small treewidth. Our results demonstrate that for large classes of graphs, the structure of the corresponding partial correlation graphs can be determined much faster than even computing the empirical covariance matrix.

JMLR Longitudinal Data Nonparametric & Semiparametric · 发表于 2021

Learning interaction kernels in heterogeneous systems of agents from multiple trajectories

Fei Lu, Mauro Maggioni, Sui Tang

摘要

Systems of interacting particles, or agents, have wide applications in many disciplines, including Physics, Chemistry, Biology and Economics. These systems are governed by interaction laws, which are often unknown: estimating them from observation data is a fundamental task that can provide meaningful insights and accurate predictions of the behaviour of the agents. In this paper, we consider the inverse problem of learning interaction laws given data from multiple trajectories, in a nonparametric fashion, when the interaction kernels depend on pairwise distances. We establish a condition for learnability of interaction kernels, and construct an estimator based on the minimization of a suitably regularized least squares functional, that is guaranteed to converge, in a suitable $L^2$ space, at the optimal min-max rate for 1-dimensional nonparametric regression. We propose an efficient learning algorithm to construct such estimator, which can be implemented in parallel for multiple trajectories and is therefore well-suited for the high dimensional, big data regime. Numerical simulations on a variety examples, including opinion dynamics, predator-prey and swarm dynamics and heterogeneous particle dynamics, suggest that the learnability condition is satisfied in models used in practice, and the rate of convergence of our estimator is consistent with the theory. These simulations also suggest that our estimators are robust to noise in the observations, and can produce accurate predictions of trajectories in large time intervals, even when they are learned from observations in short time intervals.

JMLR Optimization & Learning Theory · 发表于 2021

Learning and Planning for Time-Varying MDPs Using Maximum Likelihood Estimation

Melkior Ornik, Ufuk Topcu

摘要

This paper proposes a formal approach to online learning and planning for agents operating in a priori unknown, time-varying environments. The proposed method computes the maximally likely model of the environment, given the observations about the environment made by an agent earlier in the system run and assuming knowledge of a bound on the maximal rate of change of system dynamics. Such an approach generalizes the estimation method commonly used in learning algorithms for unknown Markov decision processes with time-invariant transition probabilities, but is also able to quickly and correctly identify the system dynamics following a change. Based on the proposed method, we generalize the exploration bonuses used in learning for time-invariant Markov decision processes by introducing a notion of uncertainty in a learned time-varying model, and develop a control policy for time-varying Markov decision processes based on the exploitation and exploration trade-off. We demonstrate the proposed methods on four numerical examples: a patrolling task with a change in system dynamics, a two-state MDP with periodically changing outcomes of actions, a wind flow estimation task, and a multi-armed bandit problem with periodically changing probabilities of different rewards.

JMLR High-Dimensional · 发表于 2021

Learning a High-dimensional Linear Structural Equation Model via l1-Regularized Regression

Gunwoong Park, Sang Jun Moon, Sion Park, Jong-June Jeon

摘要

This paper develops a new approach to learning high-dimensional linear structural equation models (SEMs) without the commonly assumed faithfulness, Gaussian error distribution, and equal error distribution conditions. A key component of the algorithm is component-wise ordering and parent estimations, where both problems can be efficiently addressed using l1-regularized regression. This paper proves that sample sizes n = Omega( d^{2} \log p) and n = \Omega( d^2 p^{2/m} ) are sufficient for the proposed algorithm to recover linear SEMs with sub-Gaussian and (4m)-th bounded-moment error distributions, respectively, where p is the number of nodes and d is the maximum degree of the moralized graph. Further shown is the worst-case computational complexity O(n (p^3 + p^2 d^2 ) ), and hence, the proposed algorithm is statistically consistent and computationally feasible for learning a high-dimensional linear SEM when its moralized graph is sparse. Through simulations, we verify that the proposed algorithm is statistically consistent and computationally feasible, and it performs well compared to the state-of-the-art US, GDS, LISTEN and TD algorithms with our settings. We also demonstrate through real COVID-19 data that the proposed algorithm is well-suited to estimating a virus-spread map in China.

Econometrica Other · 发表于 2021

Learning With Heterogeneous Misspecified Models: Characterization and Robustness

J. Aislinn Bohren, Daniel N. Hauser

摘要

This paper develops a general framework to study how misinterpreting information impacts learning. Our main result is a simple criterion to characterize long‐run beliefs based on the underlying form of misspecification. We present this characterization in the context of social learning, then highlight how it applies to other learning environments, including individual learning. A key contribution is that our characterization applies to settings with model heterogeneity and provides conditions for entrenched disagreement. Our characterization can be used to determine whether a representative agent approach is valid in the face of heterogeneity, study how differing levels of bias or unawareness of others' biases impact learning, and explore whether the impact of a bias is sensitive to parametric specification or the source of information. This unified framework synthesizes insights gleaned from previously studied forms of misspecification and provides novel insights in specific applications, as we demonstrate in settings with partisan bias, overreaction, naive learning, and level‐k reasoning.

JMLR Other · 发表于 2021

Learning Whenever Learning is Possible: Universal Learning under General Stochastic Processes

Steve Hanneke

摘要

This work initiates a general study of learning and generalization without the i.i.d. assumption, starting from first principles. While the traditional approach to statistical learning theory typically relies on standard assumptions from probability theory (e.g., i.i.d. or stationary ergodic), in this work we are interested in developing a theory of learning based only on the most fundamental and necessary assumptions implicit in the requirements of the learning problem itself. We specifically study universally consistent function learning, where the objective is to obtain low long-run average loss for any target function, when the data follow a given stochastic process. We are then interested in the question of whether there exist learning rules guaranteed to be universally consistent given only the assumption that universally consistent learning is possible for the given data process. The reasoning that motivates this criterion emanates from a kind of optimist's decision theory, and so we refer to such learning rules as being optimistically universal. We study this question in three natural learning settings: inductive, self-adaptive, and online. Remarkably, as our strongest positive result, we find that optimistically universal learning rules do indeed exist in the self-adaptive learning setting. Establishing this fact requires us to develop new approaches to the design of learning algorithms. Along the way, we also identify concise characterizations of the family of processes under which universally consistent learning is possible in the inductive and self-adaptive settings. We additionally pose a number of enticing open problems, particularly for the online learning setting.

JMLR Econometrics & Economics · 发表于 2021

Learning Strategies in Decentralized Matching Markets under Uncertain Preferences

Xiaowu Dai, Michael I. Jordan

摘要

We study the problem of decision-making in the setting of a scarcity of shared resources when the preferences of agents are unknown a priori and must be learned from data. Taking the two-sided matching market as a running example, we focus on the decentralized setting, where agents do not share their learned preferences with a central authority. Our approach is based on the representation of preferences in a reproducing kernel Hilbert space, and a learning algorithm for preferences that accounts for uncertainty due to the competition among the agents in the market. Under regularity conditions, we show that our estimator of preferences converges at a minimax optimal rate. Given this result, we derive optimal strategies that maximize agents' expected payoffs and we calibrate the uncertain state by taking opportunity costs into account. We also derive an incentive-compatibility property and show that the outcome from the learned strategies has a stability property. Finally, we prove a fairness property that asserts that there exists no justified envy according to the learned strategies.

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

Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives

Antoine Dedieu, Hussein Hazimeh, Rahul Mazumder

摘要

We consider a discrete optimization formulation for learning sparse classifiers, where the outcome depends upon a linear combination of a small subset of features. Recent work has shown that mixed integer programming (MIP) can be used to solve (to optimality) $\ell_0$-regularized regression problems at scales much larger than what was conventionally considered possible. Despite their usefulness, MIP-based global optimization approaches are significantly slower than the relatively mature algorithms for $\ell_1$-regularization and heuristics for nonconvex regularized problems. We aim to bridge this gap in computation times by developing new MIP-based algorithms for $\ell_0$-regularized classification. We propose two classes of scalable algorithms: an exact algorithm that can handle $p\approx 50,000$ features in a few minutes, and approximate algorithms that can address instances with $p\approx 10^6$ in times comparable to the fast $\ell_1$-based algorithms. Our exact algorithm is based on the novel idea of \textsl{integrality generation}, which solves the original problem (with $p$ binary variables) via a sequence of mixed integer programs that involve a small number of binary variables. Our approximate algorithms are based on coordinate descent and local combinatorial search. In addition, we present new estimation error bounds for a class of $\ell_0$-regularized estimators. Experiments on real and synthetic data demonstrate that our approach leads to models with considerably improved statistical performance (especially variable selection) compared to competing methods.

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

Learning Laplacian Matrix from Graph Signals with Sparse Spectral Representation

Pierre Humbert, Batiste Le Bars, Laurent Oudre, Argyris Kalogeratos, Nicolas Vayatis

摘要

In this paper, we consider the problem of learning a graph structure from multivariate signals, known as graph signals. Such signals are multivariate observations carrying measurements corresponding to the nodes of an unknown graph, which we desire to infer. They are assumed to enjoy a sparse representation in the graph spectral domain, a feature which is known to carry information related to the cluster structure of a graph. The signals are also assumed to behave smoothly with respect to the underlying graph structure. For the graph learning problem, we propose a new optimization program to learn the Laplacian of this graph and provide two algorithms to solve it, called IGL-3SR and FGL-3SR. Based on a 3-step alternating procedure, both algorithms rely on standard minimization methods --such as manifold gradient descent or linear programming-- and have lower complexity compared to state-of-the-art algorithms. While IGL-3SR ensures convergence, FGL-3SR acts as a relaxation and is significantly faster since its alternating process relies on multiple closed-form solutions. Both algorithms are evaluated on synthetic and real data. They are shown to perform as good or better than their competitors in terms of both numerical performance and scalability. Finally, we present a probabilistic interpretation of the proposed optimization program as a Factor Analysis Model.

Econometrica Econometrics & Economics · 发表于 2021

Learning From Coworkers

Gregor Jarosch, Ezra Oberfield, Esteban Rossi-Hansberg

摘要

We investigate learning at the workplace. To do so, we use German administrative data that contain information on the entire workforce of a sample of establishments. We document that having more‐highly‐paid coworkers is strongly associated with future wage growth, particularly if those workers earn more. Motivated by this fact, we propose a dynamic theory of a competitive labor market where firms produce using teams of heterogeneous workers that learn from each other. We develop a methodology to structurally estimate knowledge flows using the full‐richness of the German employer‐employee matched data. The methodology builds on the observation that a competitive labor market prices coworker learning. Our quantitative approach imposes minimal restrictions on firms' production functions, can be implemented on a very short panel, and allows for potentially rich and flexible coworker learning functions. In line with our reduced‐form results, learning from coworkers is significant, particularly from more knowledgeable coworkers. We show that between 4 and 9% of total worker compensation is in the form of learning and that inequality in total compensation is significantly lower than inequality in wages.

Econometrica Networks & Graphs · 发表于 2021

Learning Dynamics in Social Networks

Simon Board, Moritz Meyer-ter-Vehn

摘要

This paper proposes a tractable model of Bayesian learning on large random networks where agents choose whether to adopt an innovation. We study the impact of the network structure on learning dynamics and product diffusion. In directed networks, all direct and indirect links contribute to agents' learning. In comparison, learning and welfare are lower in undirected networks and networks with cliques. In a rich class of networks, behavior is described by a small number of differential equations, making the model useful for empirical work.

JMLR Bayesian Methods Networks & Graphs · 发表于 2021

Learning Bayesian Networks from Ordinal Data

Xiang Ge Luo, Giusi Moffa, Jack Kuipers

摘要

Bayesian networks are a powerful framework for studying the dependency structure of variables in a complex system. The problem of learning Bayesian networks is tightly associated with the given data type. Ordinal data, such as stages of cancer, rating scale survey questions, and letter grades for exams, are ubiquitous in applied research. However, existing solutions are mainly for continuous and nominal data. In this work, we propose an iterative score-and-search method - called the Ordinal Structural EM (OSEM) algorithm - for learning Bayesian networks from ordinal data. Unlike traditional approaches designed for nominal data, we explicitly respect the ordering amongst the categories. More precisely, we assume that the ordinal variables originate from marginally discretizing a set of Gaussian variables, whose structural dependence in the latent space follows a directed acyclic graph. Then, we adopt the Structural EM algorithm and derive closed-form scoring functions for efficient graph searching. Through simulation studies, we illustrate the superior performance of the OSEM algorithm compared to the alternatives and analyze various factors that may influence the learning accuracy. Finally, we demonstrate the practicality of our method with a real-world application on psychological survey data from 408 patients with co-morbid symptoms of obsessive-compulsive disorder and depression.

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

LassoNet: A Neural Network with Feature Sparsity

Ismael Lemhadri, Feng Ruan, Louis Abraham, Robert Tibshirani

摘要

Much work has been done recently to make neural networks more interpretable, and one approach is to arrange for the network to use only a subset of the available features. In linear models, Lasso (or $\ell_1$-regularized) regression assigns zero weights to the most irrelevant or redundant features, and is widely used in data science. However the Lasso only applies to linear models. Here we introduce LassoNet, a neural network framework with global feature selection. Our approach achieves feature sparsity by adding a skip (residual) layer and allowing a feature to participate in any hidden layer only if its skip-layer representative is active. Unlike other approaches to feature selection for neural nets, our method uses a modified objective function with constraints, and so integrates feature selection with the parameter learning directly. As a result, it delivers an entire regularization path of solutions with a range of feature sparsity. We apply LassoNet to a number of real-data problems and find that it significantly outperforms state-of-the-art methods for feature selection and regression. LassoNet uses projected proximal gradient descent, and generalizes directly to deep networks. It can be implemented by adding just a few lines of code to a standard neural network.

JMLR Other · 发表于 2021

Langevin Monte Carlo: random coordinate descent and variance reduction

Zhiyan Ding, Qin Li

摘要

Langevin Monte Carlo (LMC) is a popular Bayesian sampling method. For the log-concave distribution function, the method converges exponentially fast, up to a controllable discretization error. However, the method requires the evaluation of a full gradient in each iteration, and for a problem on $\mathbb{R}^d$, this amounts to $d$ times partial derivative evaluations per iteration. The cost is high when $d\gg1$. In this paper, we investigate how to enhance computational efficiency through the application of RCD (random coordinate descent) on LMC. There are two sides of the theory: 1. By blindly applying RCD to LMC, one surrogates the full gradient by a randomly selected directional derivative per iteration. Although the cost is reduced per iteration, the total number of iteration is increased to achieve a preset error tolerance. Ultimately there is no computational gain; 2. We then incorporate variance reduction techniques, such as SAGA (stochastic average gradient) and SVRG (stochastic variance reduced gradient), into RCD-LMC. It will be proved that the cost is reduced compared with the classical LMC, and in the underdamped case, convergence is achieved with the same number of iterations, while each iteration requires merely one-directional derivative. This means we obtain the best possible computational cost in the underdamped-LMC framework.

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

Langevin Dynamics for Adaptive Inverse Reinforcement Learning of Stochastic Gradient Algorithms

Vikram Krishnamurthy, George Yin

摘要

Inverse reinforcement learning (IRL) aims to estimate the reward function of optimizing agents by observing their response (estimates or actions). This paper considers IRL when noisy estimates of the gradient of a reward function generated by multiple stochastic gradient agents are observed. We present a generalized Langevin dynamics algorithm to estimate the reward function $R(\theta)$; specifically, the resulting Langevin algorithm asymptotically generates samples from the distribution proportional to $\exp(R(\theta))$. The proposed adaptive IRL algorithms use kernel-based passive learning schemes. We also construct multi-kernel passive Langevin algorithms for IRL which are suitable for high dimensional data. The performance of the proposed IRL algorithms are illustrated on examples in adaptive Bayesian learning, logistic regression (high dimensional problem) and constrained Markov decision processes. We prove weak convergence of the proposed IRL algorithms using martingale averaging methods. We also analyze the tracking performance of the IRL algorithms in non-stationary environments where the utility function $R(\theta)$ has a hyper-parameter that jump changes over time as a slow Markov chain which is not known to the inverse learner. In this case, martingale averaging yields a Markov switched diffusion limit as the asymptotic behavior of the IRL algorithm.

JMLR High-Dimensional · 发表于 2021

LDLE: Low Distortion Local Eigenmaps

Dhruv Kohli, Alexander Cloninger, Gal Mishne

摘要

We present Low Distortion Local Eigenmaps (LDLE), a manifold learning technique which constructs a set of low distortion local views of a data set in lower dimension and registers them to obtain a global embedding. The local views are constructed using the global eigenvectors of the graph Laplacian and are registered using Procrustes analysis. The choice of these eigenvectors may vary across the regions. In contrast to existing techniques, LDLE can embed closed and non-orientable manifolds into their intrinsic dimension by tearing them apart. It also provides gluing instruction on the boundary of the torn embedding to help identify the topology of the original manifold. Our experimental results will show that LDLE largely preserved distances up to a constant scale while other techniques produced higher distortion. We also demonstrate that LDLE produces high quality embeddings even when the data is noisy or sparse.

JMLR Optimization & Learning Theory · 发表于 2021

L-SVRG and L-Katyusha with Arbitrary Sampling

Xun Qian, Zheng Qu, Peter Richtárik

摘要

We develop and analyze a new family of nonaccelerated and accelerated loopless variance-reduced methods for finite-sum optimization problems. Our convergence analysis relies on a novel expected smoothness condition which upper bounds the variance of the stochastic gradient estimation by a constant times a distance-like function. This allows us to handle with ease arbitrary sampling schemes as well as the nonconvex case. We perform an in-depth estimation of these expected smoothness parameters and propose new importance samplings which allow linear speedup when the expected minibatch size is in a certain range. Furthermore, a connection between these expected smoothness parameters and expected separable overapproximation (ESO) is established, which allows us to exploit data sparsity as well. Our general methods and results recover as special cases the loopless SVRG and loopless Katyusha methods.

JMLR Testing & Uncertainty · 发表于 2021

Knowing what You Know: valid and validated confidence sets in multiclass and multilabel prediction

Maxime Cauchois, Suyash Gupta, John C. Duchi

摘要

We develop conformal prediction methods for constructing valid predictive confidence sets in multiclass and multilabel problems without assumptions on the data generating distribution. A challenge here is that typical conformal prediction methods---which give marginal validity (coverage) guarantees---provide uneven coverage, in that they address easy examples at the expense of essentially ignoring difficult examples. By leveraging ideas from quantile regression, we build methods that always guarantee correct coverage but additionally provide (asymptotically consistent) conditional coverage for both multiclass and multilabel prediction problems. To address the potential challenge of exponentially large confidence sets in multilabel prediction, we build tree-structured classifiers that efficiently account for interactions between labels. Our methods can be bolted on top of any classification model---neural network, random forest, boosted tree---to guarantee its validity. We also provide an empirical evaluation, simultaneously providing new validation methods, that suggests the more robust coverage of our confidence sets.

JMLR Nonparametric & Semiparametric · 发表于 2021

Kernel Smoothing, Mean Shift, and Their Learning Theory with Directional Data

Yikun Zhang, Yen-Chi Chen

摘要

Directional data consist of observations distributed on a (hyper)sphere, and appear in many applied fields, such as astronomy, ecology, and environmental science. This paper studies both statistical and computational problems of kernel smoothing for directional data. We generalize the classical mean shift algorithm to directional data, which allows us to identify local modes of the directional kernel density estimator (KDE). The statistical convergence rates of the directional KDE and its derivatives are derived, and the problem of mode estimation is examined. We also prove the ascending property of the directional mean shift algorithm and investigate a general problem of gradient ascent on the unit hypersphere. To demonstrate the applicability of the algorithm, we evaluate it as a mode clustering method on both simulated and real-world data sets.

JMLR Nonparametric & Semiparametric · 发表于 2021

Kernel Operations on the GPU, with Autodiff, without Memory Overflows

Benjamin Charlier, Jean Feydy, Joan Alexis Glaunès, François-David Collin, Ghislain Durif

摘要

The KeOps library provides a fast and memory-efficient GPU support for tensors whose entries are given by a mathematical formula, such as kernel and distance matrices. KeOps alleviates the main bottleneck of tensor-centric libraries for kernel and geometric applications: memory consumption. It also supports automatic differentiation and outperforms standard GPU baselines, including PyTorch CUDA tensors or the Halide and TVM libraries. KeOps combines optimized C++/CUDA schemes with binders for high-level languages: Python (Numpy and PyTorch), Matlab and GNU R. As a result, high-level “quadratic” codes can now scale up to large data sets with millions of samples processed in seconds. KeOps brings graphics-like performances for kernel methods and is freely available on standard repositories (PyPi, CRAN). To showcase its versatility, we provide tutorials in a wide range of settings online at www.kernel-operations.io.

Biometrics Longitudinal Data Genetics & Omics Survival Analysis · 发表于 2021

Joint modeling of zero‐inflated longitudinal proportions and time‐to‐event data with application to a gut microbiome study

Jiyuan Hu, Chan Wang, Martin J. Blaser, Huilin Li

摘要

Recent studies have suggested that the temporal dynamics of the human microbiome may have associations with human health and disease. An increasing number of longitudinal microbiome studies, which record time to disease onset, aim to identify candidate microbes as biomarkers for prognosis. Owing to the ultra‐skewness and sparsity of microbiome proportion (relative abundance) data, directly applying traditional statistical methods may result in substantial power loss or spurious inferences. We propose a novel joint modeling framework [JointMM], which is comprised of two sub‐models: a longitudinal sub‐model called zero‐inflated scaled‐beta generalized linear mixed‐effects regression to depict the temporal structure of microbial proportions among subjects; and a survival sub‐model to characterize the occurrence of an event and its relationship with the longitudinal microbiome proportions. JointMM is specifically designed to handle the zero‐inflated and highly skewed longitudinal microbial proportion data and examine whether the temporal pattern of microbial presence and/or the nonzero microbial proportions are associated with differences in the time to an event. The longitudinal sub‐model of JointMM also provides the capacity to investigate how the (time‐varying) covariates are related to the temporal microbial presence/absence patterns and/or the changing trend in nonzero proportions. Comprehensive simulations and real data analyses are used to assess the statistical efficiency and interpretability of JointMM.

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