2021 年的期刊文章 · 第 32 页

共 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 Optimization & Learning Theory · 发表于 2021

Regulating Greed Over Time in Multi-Armed Bandits

Stefano Tracà, Cynthia Rudin, Weiyu Yan

摘要

In retail, there are predictable yet dramatic time-dependent patterns in customer behavior, such as periodic changes in the number of visitors, or increases in customers just before major holidays. The current paradigm of multi-armed bandit analysis does not take these known patterns into account. This means that for applications in retail, where prices are fixed for periods of time, current bandit algorithms will not suffice. This work provides a remedy that takes the time-dependent patterns into account, and we show how this remedy is implemented for the UCB, $\varepsilon$-greedy, and UCB-L algorithms, and also through a new policy called the variable arm pool algorithm. In the corrected methods, exploitation (greed) is regulated over time, so that more exploitation occurs during higher reward periods, and more exploration occurs in periods of low reward. In order to understand why regret is reduced with the corrected methods, we present a set of bounds that provide insight into why we would want to exploit during periods of high reward, and discuss the impact on regret. Our proposed methods perform well in experiments, and were inspired by a high-scoring entry in the Exploration and Exploitation 3 contest using data from Yahoo$!$ Front Page. That entry heavily used time-series methods to regulate greed over time, which was substantially more effective than other contextual bandit methods.

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

Regularized spectral methods for clustering signed networks

Mihai Cucuringu, Apoorv Vikram Singh, Déborah Sulem, Hemant Tyagi

摘要

We study the problem of k-way clustering in signed graphs. Considerable attention in recent years has been devoted to analyzing and modeling signed graphs, where the affinity measure between nodes takes either positive or negative values. Recently, Cucuringu et al. (2019) proposed a spectral method, namely SPONGE (Signed Positive over Negative Generalized Eigenproblem), which casts the clustering task as a generalized eigenvalue problem optimizing a suitably defined objective function. This approach is motivated by social balance theory, where the clustering task aims to decompose a given network into disjoint groups, such that individuals within the same group are connected by as many positive edges as possible, while individuals from different groups are mainly connected by negative edges. Through extensive numerical experiments, SPONGE was shown to achieve state-of-the-art empirical performance. On the theoretical front, Cucuringu et al. (2019) analyzed SPONGE, as well as the popular Signed Laplacian based spectral method under the setting of a Signed Stochastic Block Model, for k=2 equal-sized clusters, in the regime where the graph is moderately dense. In this work, we build on the results in Cucuringu et al. (2019) on two fronts for the normalized versions of SPONGE and the Signed Laplacian. Firstly, for both algorithms, we extend the theoretical analysis in Cucuringu et al. (2019) to the general setting of k >= 2 unequal-sized clusters in the moderately dense regime. Secondly, we introduce regularized versions of both methods to handle sparse graphs -- a regime where standard spectral methods are known to underperform -- and provide theoretical guarantees under the same setting of a Signed Stochastic Block Model. To the best of our knowledge, regularized spectral methods have so far not been considered in the setting of clustering signed graphs. We complement our theoretical results with an extensive set of numerical experiments on synthetic data, and three real world data sets standard in the signed networks literature.

JMLR Optimization & Learning Theory · 发表于 2021

Refined approachability algorithms and application to regret minimization with global costs

Joon Kwon

摘要

Blackwell's approachability is a framework where two players, the Decision Maker and the Environment, play a repeated game with vector-valued payoffs. The goal of the Decision Maker is to make the average payoff converge to a given set called the target. When this is indeed possible, simple algorithms which guarantee the convergence are known. This abstract tool was successfully used for the construction of optimal strategies in various repeated games, but also found several applications in online learning. By extending an approach proposed by (Abernethy et al., 2011), we construct and analyze a class of Follow the Regularized Leader algorithms (FTRL) for Blackwell's approachability which are able to minimize not only the Euclidean distance to the target set (as it is often the case in the context of Blackwell's approachability) but a wide range of distance-like quantities. This flexibility enables us to apply these algorithms to closely minimize the quantity of interest in various online learning problems. In particular, for regret minimization with ℓp global costs, we obtain the first bounds with explicit dependence in p and the dimension d.

Econometrica Econometrics & Economics · 发表于 2021

Redistribution Through Markets

Piotr Dworczak, Scott Duke Kominers, Mohammad Akbarpour

摘要

Policymakers frequently use price regulations as a response to inequality in the markets they control. In this paper, we examine the optimal structure of such policies from the perspective of mechanism design. We study a buyer‐seller market in which agents have private information about both their valuations for an indivisible object and their marginal utilities for money. The planner seeks a mechanism that maximizes agents' total utilities, subject to incentive and market‐clearing constraints. We uncover the constrained Pareto frontier by identifying the optimal trade‐off between allocative efficiency and redistribution. We find that competitive‐equilibrium allocation is not always optimal. Instead, when there is inequality across sides of the market, the optimal design uses a tax‐like mechanism, introducing a wedge between the buyer and seller prices, and redistributing the resulting surplus to the poorer side of the market via lump‐sum payments. When there is significant same‐side inequality that can be uncovered by market behavior, it may be optimal to impose price controls even though doing so induces rationing.

Econometrica Econometrics & Economics · 发表于 2021

Recovering Preferences From Finite Data

Christopher P. Chambers, Federico Echenique, Nicolas S. Lambert

摘要

We study preferences estimated from finite choice experiments and provide sufficient conditions for convergence to a unique underlying “true” preference. Our conditions are weak and, therefore, valid in a wide range of economic environments. We develop applications to expected utility theory, choice over consumption bundles, and menu choice. Our framework unifies the revealed preference tradition with models that allow for errors.

Econometrica Other · 发表于 2021

Reconciling Models of Diffusion and Innovation: A Theory of the Productivity Distribution and Technology Frontier

Jess Benhabib, Jesse Perla, Christopher Tonetti

摘要

We study how endogenous innovation and technology diffusion interact to determine the shape of the productivity distribution and generate aggregate growth. We model firms that choose to innovate, adopt technology, or produce with their existing technology. Costly adoption creates a spread between the best and worst technologies concurrently used to produce similar goods. The balance of adoption and innovation determines the shape of the distribution; innovation stretches the distribution, while adoption compresses it. On the balanced growth path, the aggregate growth rate equals the maximum growth rate of innovators. While innovation drives long‐run growth, changes in the adoption environment can influence growth by affecting innovation incentives, either directly, through licensing of excludable technologies, or indirectly, via the option value of adoption.

Econometrica Econometrics & Economics · 发表于 2021

Reasonable Doubt: Experimental Detection of Job‐Level Employment Discrimination

Patrick Kline, Christopher Walters

摘要

This paper develops methods for detecting discrimination by individual employers using correspondence experiments that send fictitious resumes to real job openings. We establish identification of higher moments of the distribution of job‐level callback rates as a function of the number of resumes sent to each job and propose shape‐constrained estimators of these moments. Applying our methods to three experimental data sets, we find striking job‐level heterogeneity in the extent to which callback probabilities differ by race or sex. Estimates of higher moments reveal that while most jobs barely discriminate, a few discriminate heavily. These moment estimates are then used to bound the share of jobs that discriminate and the posterior probability that each individual job is engaged in discrimination. In a recent experiment manipulating racially distinctive names, we find that at least 85% of jobs that contact both of two white applications and neither of two black applications are engaged in discrimination. To assess the potential value of our methods for regulators, we consider the accuracy of decision rules for investigating suspicious callback behavior in various experimental designs under a simple two‐type model that rationalizes the experimental data. Though we estimate that only 17% of employers discriminate on the basis of race, we find that an experiment sending 10 applications to each job would enable detection of 7–10% of discriminatory jobs while yielding Type I error rates below 0.2%. A minimax decision rule acknowledging partial identification of the distribution of callback rates yields only slightly fewer investigations than a Bayes decision rule based on the two‐type model. These findings suggest illegal labor market discrimination can be reliably monitored with relatively small modifications to existing correspondence designs.

JMLR Other · 发表于 2021

Ranking and synchronization from pairwise measurements via SVD

Alexandre d'Aspremont, Mihai Cucuringu, Hemant Tyagi

摘要

Given a measurement graph $G= (V,E)$ and an unknown signal $r \in \mathbb{R}^n$, we investigate algorithms for recovering $r$ from pairwise measurements of the form $r_i - r_j$; $\{i,j\} \in E$. This problem arises in a variety of applications, such as ranking teams in sports data and time synchronization of distributed networks. Framed in the context of ranking, the task is to recover the ranking of $n$ teams (induced by $r$) given a small subset of noisy pairwise rank offsets. We propose a simple SVD-based algorithmic pipeline for both the problem of time synchronization and ranking. We provide a detailed theoretical analysis in terms of robustness against both sampling sparsity and noise perturbations with outliers, using results from matrix perturbation and random matrix theory. Our theoretical findings are complemented by a detailed set of numerical experiments on both synthetic and real data, showcasing the competitiveness of our proposed algorithms with other state-of-the-art methods.

Econometrica Other · 发表于 2021

Random Evolving Lotteries and Intrinsic Preference for Information

Faruk Gul, Paulo Natenzon, Wolfgang Pesendorfer

摘要

We introduce random evolving lotteries to study preference for non‐instrumental information. Each period, the agent enjoys a flow payoff from holding a lottery that will resolve at the terminal date. We provide a representation theorem for non‐separable risk consumption preferences and use it to characterize agents' attitude to non‐instrumental information. To address applications, we characterize peak‐trough utilities that aggregate trajectories of flow utilities linearly but, in addition, put weight on the best (peak) and worst (trough) lotteries along each path. We show that the model is consistent with recent experimental evidence on attitudes to information, including a preference for gradual arrival of good news and the ostrich effect, that is, decision makers' tendency to prefer information after good news to information after bad news.

JMLR Missing Data & Measurement Error · 发表于 2021

RaSE: Random Subspace Ensemble Classification

Ye Tian, Yang Feng

摘要

We propose a flexible ensemble classification framework, Random Subspace Ensemble (RaSE), for sparse classification. In the RaSE algorithm, we aggregate many weak learners, where each weak learner is a base classifier trained in a subspace optimally selected from a collection of random subspaces. To conduct subspace selection, we propose a new criterion, ratio information criterion (RIC), based on weighted Kullback-Leibler divergence. The theoretical analysis includes the risk and Monte-Carlo variance of the RaSE classifier, establishing the screening consistency and weak consistency of RIC, and providing an upper bound for the misclassification rate of the RaSE classifier. In addition, we show that in a high-dimensional framework, the number of random subspaces needs to be very large to guarantee that a subspace covering signals is selected. Therefore, we propose an iterative version of the RaSE algorithm and prove that under some specific conditions, a smaller number of generated random subspaces are needed to find a desirable subspace through iteration. An array of simulations under various models and real-data applications demonstrate the effectiveness and robustness of the RaSE classifier and its iterative version in terms of low misclassification rate and accurate feature ranking. The RaSE algorithm is implemented in the R package RaSEn on CRAN.

JMLR Other · 发表于 2021

ROOTS: Object-Centric Representation and Rendering of 3D Scenes

Chang Chen, Fei Deng, Sungjin Ahn

摘要

A crucial ability of human intelligence is to build up models of individual 3D objects from partial scene observations. Recent works either achieve object-centric generation but without the ability to infer the representation, or achieve 3D scene representation learning but without object-centric compositionality. Therefore, learning to both represent and render 3D scenes with object-centric compositionality remains elusive. In this paper, we propose a probabilistic generative model for learning to build modular and compositional 3D object models from partial observations of a multi-object scene. The proposed model can (i) infer the 3D object representations by learning to search and group object areas, and also (ii) render from an arbitrary viewpoint not only individual objects but also the full scene by compositing the objects. The entire learning process is unsupervised and end-to-end. In experiments, in addition to generation quality, we also demonstrate that the learned representation permits object-wise manipulation and novel scene generation, and generalizes to various settings. Results can be found on our project website: https://sites.google.com/view/roots3d

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

Quasi-Monte Carlo Quasi-Newton in Variational Bayes

Sifan Liu, Art B. Owen

摘要

Many machine learning problems optimize an objective that must be measured with noise. The primary method is a first order stochastic gradient descent using one or more Monte Carlo (MC) samples at each step. There are settings where ill-conditioning makes second order methods such as limited-memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) more effective. We study the use of randomized quasi-Monte Carlo (RQMC) sampling for such problems. When MC sampling has a root mean squared error (RMSE) of $O(n^{-1/2})$ then RQMC has an RMSE of $o(n^{-1/2})$ that can be close to $O(n^{-3/2})$ in favorable settings. We prove that improved sampling accuracy translates directly to improved optimization. In our empirical investigations for variational Bayes, using RQMC with stochastic quasi-Newton method greatly speeds up the optimization, and sometimes finds a better parameter value than MC does.

Econometrica Other · 发表于 2021

Quantitative Analysis of Multiparty Tariff Negotiations

Kyle Bagwell, Robert W. Staiger, Ali Yurukoglu

摘要

We develop a model of international tariff negotiations to study the design of the institutional rules of the GATT/WTO. A key principle of the GATT/WTO is its most‐favored‐nation (MFN) requirement of nondiscrimination, a principle that has long been criticized for inviting free‐riding behavior. We embed a multisector model of international trade into a model of interconnected bilateral negotiations over tariffs and assess the value of the MFN principle. Using 1990 trade flows and tariff outcomes from the Uruguay Round of GATT/WTO negotiations, we estimate the model and use it to simulate what would happen if the MFN requirement were abandoned and countries negotiated over discriminatory tariffs. We find that if tariff bargaining in the Uruguay Round had proceeded without the MFN requirement, it would have wiped out the world real income gains that MFN tariff bargaining in the Uruguay Round produced and would have instead led to a small reduction in world real income relative to the 1990 status quo.

Econometrica Latent Variables & Mixtures · 发表于 2021

Quantile Factor Models

Liang Chen, Juan J. Dolado, Jesús Gonzalo

摘要

Quantile factor models (QFM) represent a new class of factor models for high‐dimensional panel data. Unlike approximate factor models (AFM), which only extract mean factors, QFM also allow unobserved factors to shift other relevant parts of the distributions of observables. We propose a quantile regression approach, labeled Quantile Factor Analysis (QFA), to consistently estimate all the quantile‐dependent factors and loadings. Their asymptotic distributions are established using a kernel‐smoothed version of the QFA estimators. Two consistent model selection criteria, based on information criteria and rank minimization, are developed to determine the number of factors at each quantile. QFA estimation remains valid even when the idiosyncratic errors exhibit heavy‐tailed distributions. An empirical application illustrates the usefulness of QFA by highlighting the role of extra factors in the forecasts of U.S. GDP growth and inflation rates using a large set of predictors.

JMLR Networks & Graphs · 发表于 2021

Pykg2vec: A Python Library for Knowledge Graph Embedding

Shih-Yuan Yu, Sujit Rokka Chhetri, Arquimedes Canedo, Palash Goyal, Mohammad Abdullah Al Faruque

摘要

Pykg2vec is a Python library for learning the representations of the entities and relations in knowledge graphs. Pykg2vec's flexible and modular software architecture currently implements 25 state-of-the-art knowledge graph embedding algorithms, and is designed to easily incorporate new algorithms.The goal of pykg2vec is to provide a practical and educational platform to accelerate research in knowledge graph representation learning. Pykg2vec is built on top of PyTorch and Python's multiprocessing framework and provides modules for batch generation, Bayesian hyperparameter optimization, evaluation of KGE tasks, embedding, and result visualization. Pykg2vec is released under the MIT License and is also available in the Python Package Index (PyPI). The source code of pykg2vec is available at https://github.com/Sujit-O/pykg2vec.

JMLR Networks & Graphs · 发表于 2021

PyKEEN 1.0: A Python Library for Training and Evaluating Knowledge Graph Embeddings

Mehdi Ali, Max Berrendorf, Charles Tapley Hoyt, Laurent Vermue, Sahand Sharifzadeh, Volker Tresp, Jens Lehmann

摘要

Recently, knowledge graph embeddings (KGEs) have received significant attention, and several software libraries have been developed for training and evaluation. While each of them addresses specific needs, we report on a community effort to a re-design and re-implementation of PyKEEN, one of the early KGE libraries. PyKEEN 1.0 enables users to compose knowledge graph embedding models based on a wide range of interaction models, training approaches, loss functions, and permits the explicit modeling of inverse relations. It allows users to measure each component's influence individually on the model's performance. Besides, an automatic memory optimization has been realized in order to optimally exploit the provided hardware. Through the integration of Optuna, extensive hyper-parameter optimization (HPO) functionalities are provided.

JMLR Bayesian Methods · 发表于 2021

Pseudo-Marginal Hamiltonian Monte Carlo

Johan Alenlöv, Arnoud Doucet, Fredrik Lindsten

摘要

Bayesian inference in the presence of an intractable likelihood function is computationally challenging. When following a Markov chain Monte Carlo (MCMC) approach to approximate the posterior distribution in this context, one typically either uses MCMC schemes which target the joint posterior of the parameters and some auxiliary latent variables, or pseudo-marginal Metropolis-Hastings (MH) schemes. The latter mimic a MH algorithm targeting the marginal posterior of the parameters by approximating unbiasedly the intractable likelihood. However, in scenarios where the parameters and auxiliary variables are strongly correlated under the posterior and/or this posterior is multimodal, Gibbs sampling or Hamiltonian Monte Carlo (HMC) will perform poorly and the pseudo-marginal MH algorithm, as any other MH scheme, will be inefficient for high-dimensional parameters. We propose here an original MCMC algorithm, termed pseudo-marginal HMC, which combines the advantages of both HMC and pseudo-marginal schemes. Specifically, the PM-HMC method is controlled by a precision parameter $N$, controlling the approximation of the likelihood and, for any $N$, it samples the marginal posterior of the parameters. Additionally, as $N$ tends to infinity, its sample trajectories and acceptance probability converge to those of an ideal, but intractable, HMC algorithm which would have access to the intractable likelihood and its gradient. We demonstrate through experiments that PM-HMC can outperform significantly both standard HMC and pseudo-marginal MH schemes.

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

Projection-free Decentralized Online Learning for Submodular Maximization over Time-Varying Networks

Junlong Zhu, Qingtao Wu, Mingchuan Zhang, Ruijuan Zheng, Keqin Li

摘要

This paper considers a decentralized online submodular maximization problem over time-varying networks, where each agent only utilizes its own information and the received information from its neighbors. To address the problem, we propose a decentralized Meta-Frank-Wolfe online learning method in the adversarial online setting by using local communication and local computation. Moreover, we show that an expected regret bound of $O(\sqrt{T})$ is achieved with $(1-1/e)$ approximation guarantee, where $T$ is a time horizon. In addition, we also propose a decentralized one-shot Frank-Wolfe online learning method in the stochastic online setting. Furthermore, we also show that an expected regret bound $O(T^{2/3})$ is obtained with $(1-1/e)$ approximation guarantee. Finally, we confirm the theoretical results via various experiments on different datasets.

JMLR Other · 发表于 2021

Probabilistic Iterative Methods for Linear Systems

Jon Cockayne, Ilse C.F. Ipsen, Chris J. Oates, Tim W. Reid

摘要

This paper presents a probabilistic perspective on iterative methods for approximating the solution $\mathbf{x} \in \mathbb{R}^d$ of a nonsingular linear system $\mathbf{A} \mathbf{x} = \mathbf{b}$. Classically, an iterative method produces a sequence $\mathbf{x}_m$ of approximations that converge to $\mathbf{x}$ in $\mathbb{R}^d$. Our approach, instead, lifts a standard iterative method to act on the set of probability distributions, $\mathcal{P}(\mathbb{R}^d)$, outputting a sequence of probability distributions $\mu_m \in \mathcal{P}(\mathbb{R}^d)$. The output of a probabilistic iterative method can provide both a "best guess" for $\mathbf{x}$, for example by taking the mean of $\mu_m$, and also probabilistic uncertainty quantification for the value of $\mathbf{x}$ when it has not been exactly determined. A comprehensive theoretical treatment is presented in the case of a stationary linear iterative method, where we characterise both the rate of contraction of $\mu_m$ to an atomic measure on $\mathbf{x}$ and the nature of the uncertainty quantification being provided. We conclude with an empirical illustration that highlights the potential for probabilistic iterative methods to provide insight into solution uncertainty.

Econometrica Other · 发表于 2021

Present Bias

Anujit Chakraborty

摘要

Present bias is the inclination to prefer a smaller present reward to a larger later reward, but reversing this preference when both rewards are equally delayed. Such behavior violates stationarity of temporal choices, and hence exponential discounting. This paper provides a weakening of the stationarity axiom that can accommodate present‐biased choice reversals. We call this new behavioral postulate Weak Present Bias and characterize the general class of utility functions that is consistent with it. We show that present‐biased preferences can be represented as those of a decision maker who makes her choices according to conservative present‐equivalents, in the face of uncertainty about future tastes.

JMLR Optimization & Learning Theory Survey & Sampling · 发表于 2021

Preference-based Online Learning with Dueling Bandits: A Survey

Viktor Bengs, Róbert Busa-Fekete, Adil El Mesaoudi-Paul, Eyke Hüllermeier

摘要

In machine learning, the notion of multi-armed bandits refers to a class of online learning problems, in which an agent is supposed to simultaneously explore and exploit a given set of choice alternatives in the course of a sequential decision process. In the standard setting, the agent learns from stochastic feedback in the form of real-valued rewards. In many applications, however, numerical reward signals are not readily available---instead, only weaker information is provided, in particular relative preferences in the form of qualitative comparisons between pairs of alternatives. This observation has motivated the study of variants of the multi-armed bandit problem, in which more general representations are used both for the type of feedback to learn from and the target of prediction. The aim of this paper is to provide a survey of the state of the art in this field, referred to as preference-based multi-armed bandits or dueling bandits. To this end, we provide an overview of problems that have been considered in the literature as well as methods for tackling them. Our taxonomy is mainly based on the assumptions made by these methods about the data-generating process and, related to this, the properties of the preference-based feedback.

JMLR Other · 发表于 2021

Predictive Learning on Hidden Tree-Structured Ising Models

Konstantinos E. Nikolakakis, Dionysios S. Kalogerias, Anand D. Sarwate

摘要

We provide high-probability sample complexity guarantees for exact structure recovery and accurate predictive learning using noise-corrupted samples from an acyclic (tree-shaped) graphical model. The hidden variables follow a tree-structured Ising model distribution, whereas the observable variables are generated by a binary symmetric channel taking the hidden variables as its input (flipping each bit independently with some constant probability $q\in [0,1/2)$). In the absence of noise, predictive learning on Ising models was recently studied by Bresler and Karzand (2020); this paper quantifies how noise in the hidden model impacts the tasks of structure recovery and marginal distribution estimation by proving upper and lower bounds on the sample complexity. Our results generalize state-of-the-art bounds reported in prior work, and they exactly recover the noiseless case ($q=0$). In fact, for any tree with $p$ vertices and probability of incorrect recovery $\delta>0$, the sufficient number of samples remains logarithmic as in the noiseless case, i.e., $\mathcal{O}(\log(p/\delta))$, while the dependence on $q$ is $\mathcal{O}\big( 1/(1-2q)^{4} \big)$, for both aforementioned tasks. We also present a new equivalent of Isserlis' Theorem for sign-valued tree-structured distributions, yielding a new low-complexity algorithm for higher-order moment estimation.

JMLR Other · 发表于 2021

Prediction against a limited adversary

Erhan Bayraktar, Ibrahim Ekren, Xin Zhang

摘要

We study the problem of prediction with expert advice with adversarial corruption where the adversary can at most corrupt one expert. Using tools from viscosity theory, we characterize the long-time behavior of the value function of the game between the forecaster and the adversary. We provide lower and upper bounds for the growth rate of regret without relying on a comparison result. We show that depending on the description of regret, the limiting behavior of the game can significantly differ.

JMLR Latent Variables & Mixtures · 发表于 2021

Prediction Under Latent Factor Regression: Adaptive PCR, Interpolating Predictors and Beyond

Xin Bing, Florentina Bunea, Seth Strimas-Mackey, Marten Wegkamp

摘要

This work is devoted to the finite sample prediction risk analysis of a class of linear predictors of a response $Y\in \mathbb{R}$ from a high-dimensional random vector $X\in \mathbb{R}^p$ when $(X,Y)$ follows a latent factor regression model generated by a unobservable latent vector $Z$ of dimension less than $p$. Our primary contribution is in establishing finite sample risk bounds for prediction with the ubiquitous Principal Component Regression (PCR) method, under the factor regression model, with the number of principal components adaptively selected from the data---a form of theoretical guarantee that is surprisingly lacking from the PCR literature. To accomplish this, we prove a master theorem that establishes a risk bound for a large class of predictors, including the PCR predictor as a special case. This approach has the benefit of providing a unified framework for the analysis of a wide range of linear prediction methods, under the factor regression setting. In particular, we use our main theorem to recover known risk bounds for the minimum-norm interpolating predictor, which has received renewed attention in the past two years, and a prediction method tailored to a subclass of factor regression models with identifiable parameters. This model-tailored method can be interpreted as prediction via clusters with latent centers. To address the problem of selecting among a set of candidate predictors, we analyze a simple model selection procedure based on data-splitting, providing an oracle inequality under the factor model to prove that the performance of the selected predictor is close to the optimal candidate. We conclude with a detailed simulation study to support and complement our theoretical results.

JMLR Machine Learning · 发表于 2021

Policy Teaching in Reinforcement Learning via Environment Poisoning Attacks

Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, Adish Singla

摘要

We study a security threat to reinforcement learning where an attacker poisons the learning environment to force the agent into executing a target policy chosen by the attacker. As a victim, we consider RL agents whose objective is to find a policy that maximizes reward in infinite-horizon problem settings. The attacker can manipulate the rewards and the transition dynamics in the learning environment at training-time, and is interested in doing so in a stealthy manner. We propose an optimization framework for finding an optimal stealthy attack for different measures of attack cost. We provide lower/upper bounds on the attack cost, and instantiate our attacks in two settings: (i) an offline setting where the agent is doing planning in the poisoned environment, and (ii) an online setting where the agent is learning a policy with poisoned feedback. Our results show that the attacker can easily succeed in teaching any target policy to the victim under mild conditions and highlight a significant security threat to reinforcement learning agents in practice.

Econometrica Other · 发表于 2021

Policy Persistence and Drift in Organizations

Germán Gieczewski

摘要

This paper models the evolution of organizations that allow free entry and exit of members, such as cities and trade unions. In each period, current members choose a policy for the organization. Policy changes attract newcomers and drive away dissatisfied members, altering the set of future policymakers. The resulting feedback effects take the organization down a “slippery slope” that converges to a myopically stable policy, even if the agents are forward‐looking, but convergence becomes slower the more patient they are. The model yields a tractable characterization of the steady state and the transition dynamics. The analysis is also extended to situations in which the organization can exclude members, such as enfranchisement and immigration.

Econometrica Causal Inference · 发表于 2021

Policy Learning With Observational Data

Susan Athey, Stefan Wager

摘要

In many areas, practitioners seek to use observational data to learn a treatment assignment policy that satisfies application‐specific constraints, such as budget, fairness, simplicity, or other functional form constraints. For example, policies may be restricted to take the form of decision trees based on a limited set of easily observable individual characteristics. We propose a new approach to this problem motivated by the theory of semiparametrically efficient estimation. Our method can be used to optimize either binary treatments or infinitesimal nudges to continuous treatments, and can leverage observational data where causal effects are identified using a variety of strategies, including selection on observables and instrumental variables. Given a doubly robust estimator of the causal effect of assigning everyone to treatment, we develop an algorithm for choosing whom to treat, and establish strong guarantees for the asymptotic utilitarian regret of the resulting policy.

JMLR Machine Learning Networks & Graphs · 发表于 2021

Phase Diagram for Two-layer ReLU Neural Networks at Infinite-width Limit

Tao Luo, Zhi-Qin John Xu, Zheng Ma, Yaoyu Zhang

摘要

How neural network behaves during the training over different choices of hyperparameters is an important question in the study of neural networks. In this work, inspired by the phase diagram in statistical mechanics, we draw the phase diagram for the two-layer ReLU neural network at the infinite-width limit for a complete characterization of its dynamical regimes and their dependence on hyperparameters related to initialization. Through both experimental and theoretical approaches, we identify three regimes in the phase diagram, i.e., linear regime, critical regime and condensed regime, based on the relative change of input weights as the width approaches infinity, which tends to $0$, $O(1)$ and $+\infty$, respectively. In the linear regime, NN training dynamics is approximately linear similar to a random feature model with an exponential loss decay. In the condensed regime, we demonstrate through experiments that active neurons are condensed at several discrete orientations. The critical regime serves as the boundary between above two regimes, which exhibits an intermediate nonlinear behavior with the mean-field model as a typical example. Overall, our phase diagram for the two-layer ReLU NN serves as a map for the future studies and is a first step towards a more systematical investigation of the training behavior and the implicit regularization of NNs of different structures.

JMLR Other · 发表于 2021

PeerReview4All: Fair and Accurate Reviewer Assignment in Peer Review

Ivan Stelmakh, Nihar Shah, Aarti Singh

摘要

We consider the problem of automated assignment of papers to reviewers in conference peer review, with a focus on fairness and statistical accuracy. Our fairness objective is to maximize the review quality of the most disadvantaged paper, in contrast to the commonly used objective of maximizing the total quality over all papers. We design an assignment algorithm based on an incremental max-flow procedure that we prove is near-optimally fair. Our statistical accuracy objective is to ensure correct recovery of the papers that should be accepted. We provide a sharp minimax analysis of the accuracy of the peer-review process for a popular objective-score model as well as for a novel subjective-score model that we propose in the paper. Our analysis proves that our proposed assignment algorithm also leads to a near-optimal statistical accuracy. Finally, we design a novel experiment that allows for an objective comparison of various assignment algorithms, and overcomes the inherent difficulty posed by the absence of a ground truth in experiments on peer-review. The results of this experiment as well as of other experiments on synthetic and real data corroborate the theoretical guarantees of our algorithm.

JMLR High-Dimensional · 发表于 2021

Pathwise Conditioning of Gaussian Processes

James T. Wilson, Viacheslav Borovitskiy, Alexander Terenin, Peter Mostowsky, Marc Peter Deisenroth

摘要

As Gaussian processes are used to answer increasingly complex questions, analytic solutions become scarcer and scarcer. Monte Carlo methods act as a convenient bridge for connecting intractable mathematical expressions with actionable estimates via sampling. Conventional approaches for simulating Gaussian process posteriors view samples as draws from marginal distributions of process values at finite sets of input locations. This distribution-centric characterization leads to generative strategies that scale cubically in the size of the desired random vector. These methods are prohibitively expensive in cases where we would, ideally, like to draw high-dimensional vectors or even continuous sample paths. In this work, we investigate a different line of reasoning: rather than focusing on distributions, we articulate Gaussian conditionals at the level of random variables. We show how this pathwise interpretation of conditioning gives rise to a general family of approximations that lend themselves to efficiently sampling Gaussian process posteriors. Starting from first principles, we derive these methods and analyze the approximation errors they introduce. We, then, ground these results by exploring the practical implications of pathwise conditioning in various applied settings, such as global optimization and reinforcement learning.

JMLR Optimization & Learning Theory · 发表于 2021

Path Length Bounds for Gradient Descent and Flow

Chirag Gupta, Sivaraman Balakrishnan, Aaditya Ramdas

摘要

We derive bounds on the path length $\zeta$ of gradient descent (GD) and gradient flow (GF) curves for various classes of smooth convex and nonconvex functions. Among other results, we prove that: (a) if the iterates are linearly convergent with factor $(1-c)$, then $\zeta$ is at most $\mathcal{O}(1/c)$; (b) under the Polyak-Kurdyka-\L ojasiewicz (PKL) condition, $\zeta$ is at most $\mathcal{O}(\sqrt{\kappa})$, where $\kappa$ is the condition number, and at least $\widetilde\Omega(\sqrt{d} \wedge \kappa^{1/4})$; (c) for quadratics, $\zeta$ is $\Theta(\min\{\sqrt{d},\sqrt{\log \kappa}\})$ and in some cases can be independent of $\kappa$; (d) assuming just convexity, $\zeta$ can be at most $2^{4d\log d}$; (e) for separable quasiconvex functions, $\zeta$ is ${\Theta}(\sqrt{d})$. Thus, we advance current understanding of the properties of GD and GF curves beyond rates of convergence. We expect our techniques to facilitate future studies for other algorithms.

JMLR Bayesian Methods · 发表于 2021

Particle-Gibbs Sampling for Bayesian Feature Allocation Models

Alexandre Bouchard-Côté, Andrew Roth

摘要

Bayesian feature allocation models are a popular tool for modelling data with a combinatorial latent structure. Exact inference in these models is generally intractable and so practitioners typically apply Markov Chain Monte Carlo (MCMC) methods for posterior inference. The most widely used MCMC strategies rely on a single variable Gibbs update of the feature allocation matrix. These updates can be inefficient as features are typically strongly correlated. To overcome this problem we have developed a block sampler that can update an entire row of the feature allocation matrix in a single move. In the context of feature allocation models, naive block Gibbs sampling is impractical for models with a large number of features as the computational complexity scales exponentially in the number of features. We develop a Particle Gibbs (PG) sampler that targets the same distribution as the row wise Gibbs updates, but has computational complexity that only grows linearly in the number of features. We compare the performance of our proposed methods to the standard Gibbs sampler using synthetic and real data from a range of feature allocation models. Our results suggest that row wise updates using the PG methodology can significantly improve the performance of samplers for feature allocation models.

JMLR Optimization & Learning Theory · 发表于 2021

Partial Policy Iteration for L1-Robust Markov Decision Processes

Chin Pang Ho, Marek Petrik, Wolfram Wiesemann

摘要

Robust Markov decision processes (MDPs) compute reliable solutions for dynamic decision problems with partially-known transition probabilities. Unfortunately, accounting for uncertainty in the transition probabilities significantly increases the computational complexity of solving robust MDPs, which limits their scalability. This paper describes new, efficient algorithms for solving the common class of robust MDPs with s- and sa-rectangular ambiguity sets defined by weighted L1 norms. We propose partial policy iteration, a new, efficient, flexible, and general policy iteration scheme for robust MDPs. We also propose fast methods for computing the robust Bellman operator in quasi-linear time, nearly matching the ordinary Bellman operator's linear complexity. Our experimental results indicate that the proposed methods are many orders of magnitude faster than the state-of-the-art approach, which uses linear programming solvers combined with a robust value iteration.

Econometrica Econometrics & Economics · 发表于 2021

Pairwise Stable Matching in Large Economies

Michael Greinecker, Christopher Kah

摘要

We formulate a stability notion for two‐sided pairwise matching problems with individually insignificant agents in distributional form. Matchings are formulated as joint distributions over the characteristics of the populations to be matched. Spaces of characteristics can be high‐dimensional and need not be compact. Stable matchings exist with and without transfers, and stable matchings correspond precisely to limits of stable matchings for finite‐agent models. We can embed existing continuum matching models and stability notions with transferable utility as special cases of our model and stability notion. In contrast to finite‐agent matching models, stable matchings exist under a general class of externalities.

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

POT: Python Optimal Transport

Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, Ievgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, Titouan Vayer

摘要

Optimal transport has recently been reintroduced to the machine learning community thanks in part to novel efficient optimization procedures allowing for medium to large scale applications. We propose a Python toolbox that implements several key optimal transport ideas for the machine learning community. The toolbox contains implementations of a number of founding works of OT for machine learning such as Sinkhorn algorithm and Wasserstein barycenters, but also provides generic solvers that can be used for conducting novel fundamental research. This toolbox, named POT for Python Optimal Transport, is open source with an MIT license.

JMLR Machine Learning · 发表于 2021

Optimized Score Transformation for Consistent Fair Classification

Dennis Wei, Karthikeyan Natesan Ramamurthy, Flavio P. Calmon

摘要

This paper considers fair probabilistic binary classification where the outputs of primary interest are predicted probabilities, commonly referred to as scores. We formulate the problem of transforming scores to satisfy fairness constraints that are linear in conditional means of scores while minimizing a cross-entropy objective. The formulation can be applied directly to post-process classifier outputs and we also explore a pre-processing extension, thus allowing maximum freedom in selecting a classification algorithm. We derive a closed-form expression for the optimal transformed scores and a convex optimization problem for the transformation parameters. In the population limit, the transformed score function is the fairness-constrained minimizer of cross-entropy with respect to the true conditional probability of the outcome. In the finite sample setting, we propose a method called FairScoreTransformer to approach this solution using a combination of standard probabilistic classifiers and ADMM. We provide several consistency and finite-sample guarantees for FairScoreTransformer, relating to the transformation parameters and transformed score function that it obtains. Comprehensive experiments comparing to 10 existing methods show that FairScoreTransformer has advantages for score-based metrics such as Brier score and AUC while remaining competitive for binary label-based metrics such as accuracy.

JMLR Optimization & Learning Theory · 发表于 2021

Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives

Michael Muehlebach, Michael I. Jordan

摘要

We analyze the convergence rate of various momentum-based optimization algorithms from a dynamical systems point of view. Our analysis exploits fundamental topological properties, such as the continuous dependence of iterates on their initial conditions, to provide a simple characterization of convergence rates. In many cases, closed-form expressions are obtained that relate algorithm parameters to the convergence rate. The analysis encompasses discrete time and continuous time, as well as time-invariant and time-variant formulations, and is not limited to a convex or Euclidean setting. In addition, the article rigorously establishes why symplectic discretization schemes are important for momentum-based optimization algorithms, and provides a characterization of algorithms that exhibit accelerated convergence.

JMLR Other · 发表于 2021

Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates

Tony Cai, Hongzhe Li, Rong Ma

摘要

Driven by a wide range of applications, several principal subspace estimation problems have been studied individually under different structural constraints. This paper presents a unified framework for the statistical analysis of a general structured principal subspace estimation problem which includes as special cases sparse PCA/SVD, non-negative PCA/SVD, subspace constrained PCA/SVD, and spectral clustering. General minimax lower and upper bounds are established to characterize the interplay between the information-geometric complexity of the constraint set for the principal subspaces, the signal-to-noise ratio (SNR), and the dimensionality. The results yield interesting phase transition phenomena concerning the rates of convergence as a function of the SNRs and the fundamental limit for consistent estimation. Applying the general results to the specific settings yields the minimax rates of convergence for those problems, including the previous unknown optimal rates for sparse SVD, non-negative PCA/SVD and subspace constrained PCA/SVD.

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

Optimal Rates of Distributed Regression with Imperfect Kernels

Hongwei Sun, Qiang Wu

摘要

Distributed machine learning systems have been receiving increasing attentions for their efficiency to process large scale data. Many distributed frameworks have been proposed for different machine learning tasks. In this paper, we study the distributed kernel regression via the divide and conquer approach. The learning process consists of three stages. Firstly, the data is partitioned into multiple subsets. Then a base kernel regression algorithm is applied to each subset to learn a local regression model. Finally the local models are averaged to generate the final regression model for the purpose of predictive analytics or statistical inference. This approach has been proved asymptotically minimax optimal if the kernel is perfectly selected so that the true regression function lies in the associated reproducing kernel Hilbert space. However, this is usually, if not always, impractical because kernels that can only be selected via prior knowledge or a tuning process are hardly perfect. Instead it is more common that the kernel is good enough but imperfect in the sense that the true regression can be well approximated by but does not lie exactly in the kernel space. We show distributed kernel regression can still achieve capacity independent optimal rate in this case. To this end, we first establish a general framework that allows to analyze distributed regression with response weighted base algorithms by bounding the error of such algorithms on a single data set, provided that the error bounds have factored the impact of unexplained variance of the response variable. Then we perform a leave one out analysis of the kernel ridge regression and bias corrected kernel ridge regression, which in combination with the aforementioned framework allows us to derive sharp error bounds and capacity independent optimal rates for the associated distributed kernel regression algorithms. As a byproduct of the thorough analysis, we also prove the kernel ridge regression can achieve rates faster than $O(N^{-1})$ (where $N$ is the sample size) in the noise free setting which, to our best knowledge, are first observed and novel in regression learning.

JMLR High-Dimensional · 发表于 2021

Optimal Minimax Variable Selection for Large-Scale Matrix Linear Regression Model

Meiling Hao, Lianqiang Qu, Dehan Kong, Liuquan Sun, Hongtu Zhu

摘要

Large-scale matrix linear regression models with high-dimensional responses and high-dimensional variables have been widely employed in various large-scale biomedical studies. In this article, we propose an optimal minimax variable selection approach for the matrix linear regression model when the dimensions of both the response matrix and predictors diverge at the exponential rate of the sample size. We develop an iterative hard-thresholding algorithm for fast computation and establish an optimal minimax theory for the parameter estimates. The finite sample performance of the method is examined via extensive simulation studies and a real data application from the Alzheimer's Disease Neuroimaging Initiative study is provided.

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