研究园简易版 · 经典书籍 · 期刊文章 · 有原文 · 完整版(可多选筛选、搜索) · 首页
2020 年的期刊文章 · 第 30 页
共 1467 篇,按发表时间排,新的在前,每页 40 篇。这一页是 2020 到 2020。
按期刊、按主题看 →
JMLR Machine Learning Networks & Graphs · 发表于 2020
Gregory Naitzat, Andrey Zhitnikov, Lek-Heng Lim
摘要
We study how the topology of a data set $M = M_a \cup M_b \subseteq \mathbb{R}^d$, representing two classes $a$ and $b$ in a binary classification problem, changes as it passes through the layers of a well-trained neural network, i.e., one with perfect accuracy on training set and near-zero generalization error ($\approx 0.01\%$). The goal is to shed light on two mysteries in deep neural networks: (i) a nonsmooth activation function like ReLU outperforms a smooth one like hyperbolic tangent; (ii) successful neural network architectures rely on having many layers, even though a shallow network can approximate any function arbitrarily well. We performed extensive experiments on the persistent homology of a wide range of point cloud data sets, both real and simulated. The results consistently demonstrate the following: (1) Neural networks operate by changing topology, transforming a topologically complicated data set into a topologically simple one as it passes through the layers. No matter how complicated the topology of $M$ we begin with, when passed through a well-trained neural network $f : \mathbb{R}^d \to \mathbb{R}^p$, there is a vast reduction in the Betti numbers of both components $M_a$ and $M_b$; in fact they nearly always reduce to their lowest possible values: $\beta_k\bigl(f(M_i)\bigr) = 0$ for $k \ge 1$ and $\beta_0\bigl(f(M_i)\bigr) = 1$, $i =a, b$. (2) The reduction in Betti numbers is significantly faster for ReLU activation than for hyperbolic tangent activation as the former defines nonhomeomorphic maps that change topology, whereas the latter defines homeomorphic maps that preserve topology. (3) Shallow and deep networks transform data sets differently --- a shallow network operates mainly through changing geometry and changes topology only in its final layers, a deep one spreads topological changes more evenly across all layers.
Econometrica Other · 发表于 2020
Patrick DeJarnette, David Dillenberger, Daniel Gottlieb, Pietro Ortoleva
摘要
We study preferences over lotteries in which both the prize and the payment date are uncertain. In particular, atime lotteryis one in which the prize is fixed but the date is random. With Expected Discounted Utility, individuals must be riskseekingover time lotteries (RSTL). In an incentivized experiment, however, we find that almost all subjects violate this property. Our main contributions are theoretical. We first show that within a very broad class of models, which includes many forms of nonexpected utility and time discounting, it is impossible to accommodate even a single violation of RSTL without also violating a property we termed Stochastic Impatience, a risky counterpart of standard Impatience. We then present two positive results. If one wishes to maintain Stochastic Impatience, violations of RSTL can be accommodated by keeping Independence within periods while relaxing it across periods. If, instead, one is willing to forego Stochastic Impatience, violations of RSTL can be accommodated with a simple generalization of Expected Discounted Utility, obtained by imposing only the behavioral postulates of Discounted Utility and Expected Utility.
JMLR Machine Learning · 发表于 2020
Zeyi Wen, Hanfeng Liu, Jiashuai Shi, Qinbin Li, Bingsheng He, Jian Chen
摘要
Gradient Boosting Decision Trees (GBDTs) and Random Forests (RFs) have been used in many real-world applications. They are often a standard recipe for building state-of-the-art solutions to machine learning and data mining problems. However, training and prediction are very expensive computationally for large and high dimensional problems. This article presents an efficient and open source software toolkit called ThunderGBM which exploits the high-performance Graphics Processing Units (GPUs) for GBDTs and RFs. ThunderGBM supports classification, regression and ranking, and can run on single or multiple GPUs of a machine. Our experimental results show that ThunderGBM outperforms the existing libraries while producing similar models, and can handle high dimensional problems where existing GPU-based libraries fail. Documentation, examples, and more details about ThunderGBM are available at https://github.com/xtra-computing/thundergbm.
JMLR Optimization & Learning Theory · 发表于 2020
Daphna Weinshall, Dan Amir
摘要
Curriculum Learning is motivated by human cognition, where teaching often involves gradually exposing the learner to examples in a meaningful order, from easy to hard. Although methods based on this concept have been empirically shown to improve performance of several machine learning algorithms, no theoretical analysis has been provided even for simple cases. To address this shortfall, we start by formulating an ideal definition of difficulty score - the loss of the optimal hypothesis at a given datapoint. We analyze the possible contribution of curriculum learning based on this score in two convex problems - linear regression, and binary classification by hinge loss minimization. We show that in both cases, the convergence rate of SGD optimization decreases monotonically with the difficulty score, in accordance with earlier empirical results. We also prove that when the difficulty score is fixed, the convergence rate of SGD optimization is monotonically increasing with respect to the loss of the current hypothesis at each point. We discuss how these results settle some confusion in the literature where two apparently opposing heuristics are reported to improve performance: curriculum learning in which easier points are given priority, vs hard data mining where the more difficult points are sought out.
JMLR Nonparametric & Semiparametric · 发表于 2020
Romain Azaïs, Florian Ingels
摘要
Tree data are ubiquitous because they model a large variety of situations, e.g., the architecture of plants, the secondary structure of RNA, or the hierarchy of XML files. Nevertheless, the analysis of these non-Euclidean data is difficult per se. In this paper, we focus on the subtree kernel that is a convolution kernel for tree data introduced by Vishwanathan and Smola in the early 2000's. More precisely, we investigate the influence of the weight function from a theoretical perspective and in real data applications. We establish on a 2-classes stochastic model that the performance of the subtree kernel is improved when the weight of leaves vanishes, which motivates the definition of a new weight function, learned from the data and not fixed by the user as usually done. To this end, we define a unified framework for computing the subtree kernel from ordered or unordered trees, that is particularly suitable for tuning parameters. We show through eight real data classification problems the great efficiency of our approach, in particular for small data sets, which also states the high importance of the weight function. Finally, a visualization tool of the significant features is derived.
Econometrica Networks & Graphs · 发表于 2020
Itai Arieli, Yakov Babichenko, Ron Peretz, H. Peyton Young
摘要
New ways of doing things often get started through the actions of a few innovators, then diffuse rapidly as more and more people come into contact with prior adopters in their social network. Much of the literature focuses on the speed of diffusion as a function of the network topology. In practice, the topology may not be known with any precision, and it is constantly in flux as links are formed and severed. Here, we establish an upper bound on the expected waiting time until a given proportion of the population has adopted that holds independently of the network structure. Kreindler and Young (2014) demonstrated such a bound for regular networks when agents choose between two options: the innovation and the status quo. Our bound holds for directed and undirected networks of arbitrary size and degree distribution, and for multiple competing innovations with different payoffs.
JMLR High-Dimensional · 发表于 2020
Dmitry Kobak, Jonathan Lomond, Benoit Sanchez
摘要
A conventional wisdom in statistical learning is that large models require strong regularization to prevent overfitting. Here we show that this rule can be violated by linear regression in the underdetermined $n\ll p$ situation under realistic conditions. Using simulations and real-life high-dimensional datasets, we demonstrate that an explicit positive ridge penalty can fail to provide any improvement over the minimum-norm least squares estimator. Moreover, the optimal value of ridge penalty in this situation can be negative. This happens when the high-variance directions in the predictor space can predict the response variable, which is often the case in the real-world high-dimensional data. In this regime, low-variance directions provide an implicit ridge regularization and can make any further positive ridge penalty detrimental. We prove that augmenting any linear model with random covariates and using minimum-norm estimator is asymptotically equivalent to adding the ridge penalty. We use a spiked covariance model as an analytically tractable example and prove that the optimal ridge penalty in this case is negative when $n\ll p$.
JMLR Other · 发表于 2020
Xin Zhang, Qing Mai, Hui Zou
摘要
Sufficient dimension reduction (SDR) is a very useful concept for exploratory analysis and data visualization in regression, especially when the number of covariates is large. Many SDR methods have been proposed for regression with a continuous response, where the central subspace (CS) is the target of estimation. Various conditions, such as the linearity condition and the constant covariance condition, are imposed so that these methods can estimate at least a portion of the CS. In this paper we study SDR for regression and discriminant analysis with categorical response. Motivated by the exploratory analysis and data visualization aspects of SDR, we propose a new geometric framework to reformulate the SDR problem in terms of manifold optimization and introduce a new concept called Maximum Separation Subspace (MASES). The MASES naturally preserves the “sufficiency” in SDR without imposing additional conditions on the predictor distribution, and directly inspires a semi-parametric estimator. Numerical studies show MASES exhibits superior performance as compared with competing SDR methods in specific settings.
JMLR Bayesian Methods Optimization & Learning Theory · 发表于 2020
Mickael Binois, Victor Picheny, Patrick Taillandier, Abderrahmane Habbal
摘要
An ongoing aim of research in multiobjective Bayesian optimization is to extend its applicability to a large number of objectives. While coping with a limited budget of evaluations, recovering the set of optimal compromise solutions generally requires numerous observations and is less interpretable since this set tends to grow larger with the number of objectives. We thus propose to focus on a specific solution originating from game theory, the Kalai-Smorodinsky solution, which possesses attractive properties. In particular, it ensures equal marginal gains over all objectives. We further make it insensitive to a monotonic transformation of the objectives by considering the objectives in the copula space. A novel tailored algorithm is proposed to search for the solution, in the form of a Bayesian optimization algorithm: sequential sampling decisions are made based on acquisition functions that derive from an instrumental Gaussian process prior. Our approach is tested on four problems with respectively four, six, eight, and nine objectives. The method is available in the R package GPGame.
Econometrica Econometrics & Economics · 发表于 2020
Francisco J. Buera, Ezra Oberfield
摘要
We provide a tractable, quantitatively‐oriented theory of innovation and technology diffusion to explore the role of international trade in the process of development. We model innovation and diffusion as a process involving the combination of new ideas with insights from other industries or countries. We provide conditions under which each country's equilibrium frontier of knowledge converges to a Fréchet distribution, and derive a system of differential equations describing the evolution of the scale parameters of these distributions, that is, countries' stocks of knowledge. The model remains tractable with many asymmetric countries and generates a rich set of predictions about how the level and composition of trade affect countries' frontiers of knowledge. We use the framework to quantify the contribution of bilateral trade costs to long‐run changes in TFP and individual post‐war growth miracles. For our preferred calibration, we find that both gains from trade and the fraction of variation of TFP growth accounted for by changes in trade more than double relative to a model without diffusion.
Econometrica Other · 发表于 2020
Joyee Deb, Takuo Sugaya, Alexander Wolitzky
摘要
We prove the folk theorem for discounted repeated games with anonymous random matching. We allow non‐uniform matching, include asymmetric payoffs, and place no restrictions on the stage game other than full dimensionality. No record‐keeping or communication devices—including cheap talk communication and public randomization—are necessary.
JMLR Optimization & Learning Theory · 发表于 2020
Sebastian U. Stich, Sai Praneeth Karimireddy
摘要
We analyze (stochastic) gradient descent (SGD) with delayed updates on smooth quasi-convex and non-convex functions and derive concise, non-asymptotic, convergence rates. We show that the rate of convergence in all cases consists of two terms: (i) a stochastic term which is not affected by the delay, and (ii) a higher order deterministic term which is only linearly slowed down by the delay. Thus, in the presence of noise, the effects of the delay become negligible after a few iterations and the algorithm converges at the same optimal rate as standard SGD. This result extends a line of research that showed similar results in the asymptotic regime or for strongly-convex quadratic functions only. We further show similar results for SGD with more intricate form of delayed gradients---compressed gradients under error compensation and for local~SGD where multiple workers perform local steps before communicating with each other. In all of these settings, we improve upon the best known rates. These results show that SGD is robust to compressed and/or delayed stochastic gradient updates. This is in particular important for distributed parallel implementations, where asynchronous and communication efficient methods are the key to achieve linear speedups for optimization with multiple devices.
Econometrica Econometrics & Economics · 发表于 2020
Stephan Lauermann, Georg Nöldeke, Thomas Tröger
摘要
Most of the literature that studies frictional search‐and‐matching models with heterogeneous agents and random search investigates steady state equilibria. Steady state equilibrium requires, in particular, that the flows of agents into and out of the population of unmatched agents balance. We investigate the structure of this balance condition, taking agents' matching behavior as given. Building on the “fundamental matching lemma” for quadratic search technologies in Shimer and Smith (2000), we establish existence, uniqueness, and comparative statics properties of the solution to the balance condition for any search technology satisfying minimal regularity conditions. Implications for the existence and structure of steady state equilibria in the Shimer–Smith model and extensions thereof are noted. These reinforce the point that much of the structure of search‐and‐matching models with quadratic search technologies carries over to more general search technologies.
Econometrica Networks & Graphs · 发表于 2020
Arun G. Chandrasekhar, Horacio Larreguy, Juan Pablo Xandri
摘要
We theoretically and empirically study an incomplete information model of social learning. Agents initially guess the binary state of the world after observing a private signal. In subsequent rounds, agents observe their network neighbors' previous guesses before guessing again. Agents are drawn from a mixture of learning types—Bayesian, who face incomplete information about others' types, and DeGroot, who average their neighbors' previous period guesses and follow the majority. We study (1) learning features of both types of agents in our incomplete information model; (2) what network structures lead to failures of asymptotic learning; (3) whether realistic networks exhibit such structures. We conducted lab experiments with 665 subjects in Indian villages and 350 students from ITAM in Mexico. We perform a reduced‐form analysis and then structurally estimate the mixing parameter, finding the share of Bayesian agents to be 10% and 50% in the Indian‐villager and Mexican‐student samples, respectively.
JMLR Optimization & Learning Theory · 发表于 2020
Alexander Novikov, Pavel Izmailov, Valentin Khrulkov, Michael Figurnov, Ivan Oseledets
摘要
Tensor Train decomposition is used across many branches of machine learning. We present T3F—a library for Tensor Train decomposition based on TensorFlow. T3F supports GPU execution, batch processing, automatic differentiation, and versatile functionality for the Riemannian optimization framework, which takes into account the underlying manifold structure to construct efficient optimization methods. The library makes it easier to implement machine learning papers that rely on the Tensor Train decomposition. T3F includes documentation, examples and 94% test coverage.
JMLR Networks & Graphs · 发表于 2020
Jean Kossaifi, Zachary C. Lipton, Arinbjorn Kolbeinsson, Aran Khanna, Tommaso Furlanello, Anima Anandkumar
摘要
Convolutional neural networks typically consist of many convolutional layers followed by one or more fully connected layers. While convolutional layers map between high-order activation tensors, the fully connected layers operate on flattened activation vectors. Despite empirical success, this approach has notable drawbacks. Flattening followed by fully connected layers discards multilinear structure in the activations and requires many parameters. We address these problems by incorporating tensor algebraic operations that preserve multilinear structure at every layer. First, we introduce Tensor Contraction Layers (TCLs) that reduce the dimensionality of their input while preserving their multilinear structure using tensor contraction. Next, we introduce Tensor Regression Layers (TRLs), which express outputs through a low-rank multilinear mapping from a high-order activation tensor to an output tensor of arbitrary order. We learn the contraction and regression factors end-to-end, and produce accurate nets with fewer parameters. Additionally, our layers regularize networks by imposing low-rank constraints on the activations (TCL) and regression weights (TRL). Experiments on ImageNet show that, applied to VGG and ResNet architectures, TCLs and TRLs reduce the number of parameters compared to fully connected layers by more than 65% while maintaining or increasing accuracy. In addition to the space savings, our approach's ability to leverage topological structure can be crucial for structured data such as MRI. In particular, we demonstrate significant performance improvements over comparable architectures on three tasks associated with the UK Biobank dataset.
JMLR Bayesian Methods · 发表于 2020
Tom Rainforth, Adam Golinski, Frank Wood, Sheheryar Zaidi
摘要
Standard approaches for Bayesian inference focus solely on approximating the posterior distribution. Typically, this approximation is, in turn, used to calculate expectations for one or more target functions—a computational pipeline that is inefficient when the target function(s) are known upfront. We address this inefficiency by introducing a framework for target–aware Bayesian inference (TABI) that estimates these expectations directly. While conventional Monte Carlo estimators have a fundamental limit on the error they can achieve for a given sample size, our TABI framework is able to breach this limit; it can theoretically produce arbitrarily accurate estimators using only three samples, while we show empirically that it can also breach this limit in practice. We utilize our TABI framework by combining it with adaptive importance sampling approaches and show both theoretically and empirically that the resulting estimators are capable of converging faster than the standard $\mathcal{O}(1/N)$ Monte Carlo rate, potentially producing rates as fast as $\mathcal{O}(1/N^2)$. We further combine our TABI framework with amortized inference methods, to produce a method for amortizing the cost of calculating expectations. Finally, we show how TABI can be used to convert any marginal likelihood estimator into a target aware inference scheme and demonstrate the substantial benefits this can yield.
Econometrica Networks & Graphs · 发表于 2020
Andrea Galeotti, Benjamin Golub, Sanjeev Goyal
摘要
We study games in which a network mediates strategic spillovers and externalities among the players. How does a planner optimally target interventions that change individuals' private returns to investment? We analyze this question by decomposing any intervention into orthogonal principal components, which are determined by the network and are ordered according to their associated eigenvalues. There is a close connection between the nature of spillovers and the representation of various principal components in the optimal intervention. In games of strategic complements (substitutes), interventions place more weight on the top (bottom) principal components, which reflect more global (local) network structure. For large budgets, optimal interventions are simple—they essentially involve only a single principal component.
JMLR High-Dimensional Networks & Graphs · 发表于 2020
Anders Ellern Bilgrau, Carel F.W. Peeters, Poul Svante Eriksen, Martin Boegsted, Wessel N. van Wieringen
摘要
We consider the problem of jointly estimating multiple inverse covariance matrices from high-dimensional data consisting of distinct classes. An $\ell_2$-penalized maximum likelihood approach is employed. The suggested approach is flexible and generic, incorporating several other $\ell_2$-penalized estimators as special cases. In addition, the approach allows specification of target matrices through which prior knowledge may be incorporated and which can stabilize the estimation procedure in high-dimensional settings. The result is a targeted fused ridge estimator that is of use when the precision matrices of the constituent classes are believed to chiefly share the same structure while potentially differing in a number of locations of interest. It has many applications in (multi)factorial study designs. We focus on the graphical interpretation of precision matrices with the proposed estimator then serving as a basis for integrative or meta-analytic Gaussian graphical modeling. Situations are considered in which the classes are defined by data sets and subtypes of diseases. The performance of the proposed estimator in the graphical modeling setting is assessed through extensive simulation experiments. Its practical usability is illustrated by the differential network modeling of 12 large-scale gene expression data sets of diffuse large B-cell lymphoma subtypes. The estimator and its related procedures are incorporated into the R-package rags2ridges.
JMLR Networks & Graphs Machine Learning · 发表于 2020
Nikolay Manchev, Michael Spratling
摘要
Recurrent Neural Networks have been widely used to process sequence data, but have long been criticized for their biological implausibility and training difficulties related to vanishing and exploding gradients. This paper presents a novel algorithm for training recurrent networks, target propagation through time (TPTT), that outperforms standard backpropagation through time (BPTT) on four out of the five problems used for testing. The proposed algorithm is initially tested and compared to BPTT on four synthetic time lag tasks, and its performance is also measured using the sequential MNIST data set. In addition, as TPTT uses target propagation, it allows for discrete nonlinearities and could potentially mitigate the credit assignment problem in more complex recurrent architectures.
Econometrica Econometrics & Economics · 发表于 2020
Livia Alfonsi, Oriana Bandiera, Vittorio Bassi, Robin Burgess, Imran Rasul, Munshi Sulaiman, Anna Vitali
摘要
We design a labor market experiment to compare demand‐ and supply‐side policies to tackle youth unemployment, a key issue in low‐income countries. The experiment tracks 1700 workers and 1500 firms over four years to compare the effect of offering workers either vocational training (VT) or firm‐provided training (FT) for six months in a common setting where youth unemployment is above 60%. Relative to control workers, we find that, averaged over three post‐intervention years, FT and VT workers: (i) enjoy large and similar upticks in sector‐specific skills, (ii) significantly improve their employment rates, and (iii) experience marked improvements in an index of labor market outcomes. These averages, however, mask differences in dynamics: FT gains materialize quickly but fade over time, while VT gains emerge slowly but are long‐lasting, leading VT worker employment and earning profiles to rise above those of FT workers. Estimating a job ladder model of worker search reveals the key reason for this: VT workers receive significantly higher rates of job offers when unemployed, thus hastening their movement back into work. This likely stems from the fact that the skills of VT workers are certified and therefore can be demonstrated to potential employers. Tackling youth unemployment by skilling youth using vocational training pre‐labor market entry therefore appears to be more effective than incentivizing firms through wage subsidies to hire and train young labor market entrants.
JMLR Causal Inference Latent Variables & Mixtures · 发表于 2020
Rune Christiansen, Jonas Peters
摘要
Given a response $Y$ and a vector $X = (X^1, \dots, X^d)$ of $d$ predictors, we investigate the problem of inferring direct causes of $Y$ among the vector $X$. Models for $Y$ that use all of its causal covariates as predictors enjoy the property of being invariant across different environments or interventional settings. Given data from such environments, this property has been exploited for causal discovery. Here, we extend this inference principle to situations in which some (discrete-valued) direct causes of $ Y $ are unobserved. Such cases naturally give rise to switching regression models. We provide sufficient conditions for the existence, consistency and asymptotic normality of the MLE in linear switching regression models with Gaussian noise, and construct a test for the equality of such models. These results allow us to prove that the proposed causal discovery method obtains asymptotic false discovery control under mild conditions. We provide an algorithm, make available code, and test our method on simulated data. It is robust against model violations and outperforms state-of-the-art approaches. We further apply our method to a real data set, where we show that it does not only output causal predictors, but also a process-based clustering of data points, which could be of additional interest to practitioners.
JMLR Machine Learning · 发表于 2020
Lucas Lehnert, Michael L. Littman
摘要
A key question in reinforcement learning is how an intelligent agent can generalize knowledge across different inputs. By generalizing across different inputs, information learned for one input can be immediately reused for improving predictions for another input. Reusing information allows an agent to compute an optimal decision-making strategy using less data. State representation is a key element of the generalization process, compressing a high-dimensional input space into a low-dimensional latent state space. This article analyzes properties of different latent state spaces, leading to new connections between model-based and model-free reinforcement learning. Successor features, which predict frequencies of future observations, form a link between model-based and model-free learning: Learning to predict future expected reward outcomes, a key characteristic of model-based agents, is equivalent to learning successor features. Learning successor features is a form of temporal difference learning and is equivalent to learning to predict a single policy's utility, which is a characteristic of model-free agents. Drawing on the connection between model-based reinforcement learning and successor features, we demonstrate that representations that are predictive of future reward outcomes generalize across variations in both transitions and rewards. This result extends previous work on successor features, which is constrained to fixed transitions and assumes re-learning of the transferred state representation.
JMLR Bayesian Methods · 发表于 2020
Tui H. Nolan, Marianne Menictas, Matt P. Wand
摘要
We derive and present explicit algorithms to facilitate streamlined computing for variational inference for models containing higher level random effects. Existing literature is such that streamlined variational inference is restricted to mean field variational Bayes algorithms for two-level random effects models. Here we provide the following extensions: (1) explicit Gaussian response mean field variational Bayes algorithms for three-level models, (2) explicit algorithms for the alternative variational message passing approach in the case of two-level and three-level models, and (3) an explanation of how arbitrarily high levels of nesting can be handled based on the recently published matrix algebraic results of the authors. A pay-off from (2) is simple extension to non-Gaussian response models. In summary, we remove barriers for streamlining variational inference algorithms based on either the mean field variational Bayes approach or the variational message passing approach when higher level random effects are present.
JMLR Optimization & Learning Theory · 发表于 2020
Dongruo Zhou, Pan Xu, Quanquan Gu
摘要
We study nonconvex optimization problems, where the objective function is either an average of $n$ nonconvex functions or the expectation of some stochastic function. We propose a new stochastic gradient descent algorithm based on nested variance reduction, namely, Stochastic Nested Variance-Reduced Gradient descent ($\text{SNVRG}$). Compared with conventional stochastic variance reduced gradient ($\text{SVRG}$) algorithm that uses two reference points to construct a semi-stochastic gradient with diminishing variance in each iteration, our algorithm uses $K+1$ nested reference points to build a semi-stochastic gradient to further reduce its variance in each iteration. For smooth nonconvex functions, $\text{SNVRG}$ converges to an $\epsilon$-approximate first-order stationary point within $\tilde O(n\land\epsilon^{-2}+\epsilon^{-3}\land n^{1/2}\epsilon^{-2})$ number of stochastic gradient evaluations. This improves the best known gradient complexity of $\text{SVRG}$ $O(n+n^{2/3}\epsilon^{-2})$ and that of $\text{SCSG}$ $O(n\land \epsilon^{-2}+\epsilon^{-10/3}\land n^{2/3}\epsilon^{-2})$. For gradient dominated functions, $\text{SNVRG}$ also achieves better gradient complexity than the state-of-the-art algorithms. Based on $\text{SNVRG}$, we further propose two algorithms that can find local minima faster than state-of-the-art algorithms in both finite-sum and general stochastic (online) nonconvex optimization. In particular, for finite-sum optimization problems, the proposed $\text{SNVRG}+\text{Neon2}^{\text{finite}}$ algorithm achieves $\tilde{O}(n^{1/2}\epsilon^{-2}+n\epsilon_H^{-3}+n^{3/4}\epsilon_H^{-7/2})$ gradient complexity to converge to an $(\epsilon, \epsilon_H)$-second-order stationary point, which outperforms $\text{SVRG}+\text{Neon2}^{\text{finite}}$ (Allen-Zhu and Li, 2018), the best existing algorithm, in a wide regime. For general stochastic optimization problems, the proposed $\text{SNVRG}+\text{Neon2}^{\text{online}}$ achieves $\tilde{O}(\epsilon^{-3}+\epsilon_H^{-5}+\epsilon^{-2}\epsilon_H^{-3})$ gradient complexity, which is better than both $\text{SVRG}+\text{Neon2}^{\text{online}}$ (Allen-Zhu and Li, 2018) and $\text{Natasha2}$ (Allen-Zhu, 2018a) in certain regimes. Thorough experimental results on different nonconvex optimization problems back up our theory.
JMLR Optimization & Learning Theory · 发表于 2020
Aryan Mokhtari, Hamed Hassani, Amin Karbasi
摘要
This paper considers stochastic optimization problems for a large class of objective functions, including convex and continuous submodular. Stochastic proximal gradient methods have been widely used to solve such problems; however, their applicability remains limited when the problem dimension is large and the projection onto a convex set is computationally costly. Instead, stochastic conditional gradient algorithms are proposed as an alternative solution which rely on (i) Approximating gradients via a simple averaging technique requiring a single stochastic gradient evaluation per iteration; (ii) Solving a linear program to compute the descent/ascent direction. The gradient averaging technique reduces the noise of gradient approximations as time progresses, and replacing projection step in proximal methods by a linear program lowers the computational complexity of each iteration. We show that under convexity and smoothness assumptions, our proposed stochastic conditional gradient method converges to the optimal objective function value at a sublinear rate of $\mathcal{O}(1/t^{1/3})$. Further, for a monotone and continuous DR-submodular function and subject to a general convex body constraint, we prove that our proposed method achieves a $((1-1/e)\text{OPT} -\epsilon)$ guarantee (in expectation) with $\mathcal{O}{(1/\epsilon^3)}$ stochastic gradient computations. This guarantee matches the known hardness results and closes the gap between deterministic and stochastic continuous submodular maximization. Additionally, we achieve $((1/e)\text{OPT} -\epsilon)$ guarantee after operating on $\mathcal{O}{(1/\epsilon^3)}$ stochastic gradients for the case that the objective function is continuous DR-submodular but non-monotone and the constraint set is a down-closed convex body. By using stochastic continuous optimization as an interface, we also provide the first $(1-1/e)$ tight approximation guarantee for maximizing a monotone but stochastic submodular set function subject to a general matroid constraint and $(1/e)$ approximation guarantee for the non-monotone case.
Econometrica Networks & Graphs Econometrics & Economics · 发表于 2020
Yuval Salant, Josh Cherry
摘要
We consider statistical inference in games. Each player obtains a small random sample of other players' actions, uses statistical inference to estimate their actions, and chooses an optimal action based on the estimate. In a sampling equilibrium with statistical inference (SESI), the sample is drawn from the distribution of players' actions based on this process. We characterize the set of SESIs in large two‐action games, and compare their predictions to those of Nash equilibrium, and for different sample sizes and statistical inference procedures. We then study applications to competitive markets, markets with network effects, monopoly pricing, and search and matching markets.
Econometrica Econometrics & Economics · 发表于 2020
Timothy Besley
摘要
This paper explores the role of civic culture in expanding fiscal capacity by developing a model based on reciprocal obligations: citizens pay their taxes and the state provides public goods. Civic culture evolves over time according to the relative payoff of civic‐minded and materialist citizens. A strong civic culture manifests itself as high tax revenues sustained by high levels of voluntary tax compliance and provision of public goods. This captures the idea of government as a reciprocal social contract between the state and its citizens. The paper highlights the role of political institutions and common interests in the emergence of civic culture.
JMLR Optimization & Learning Theory · 发表于 2020
Dimitris Bertsimas, Ivan Paskov
摘要
We investigate and ultimately suggest remediation to the widely held belief that the best way to train regression models is via random assignment of our data to training and validation sets. In particular, we show that taking a robust optimization approach, and optimally selecting such training and validation sets, leads to models that not only perform significantly better than their randomly constructed counterparts in terms of prediction error, but more importantly, are considerably more stable in the sense that the standard deviation of the resulting predictions, as well as of the model coefficients, is greatly reduced. Moreover, we show that this optimization approach to training is far more effective at recovering the true support of a given data set, i.e., correctly identifying important features while simultaneously excluding spurious ones. We further compare the robust optimization approach to cross validation and find that optimization continues to have a performance edge albeit smaller. Finally, we show that this optimization approach to training is equivalent to building models that are robust to all subpopulations in the data, and thus in particular are robust to the hardest subpopulation, which leads to interesting domain specific interpretations through the use of optimal classification trees. The proposed robust optimization algorithm is efficient and scales training to essentially any desired size.
JMLR Optimization & Learning Theory Networks & Graphs · 发表于 2020
Tomáš Kocák, Rémi Munos, Branislav Kveton, Shipra Agrawal, Michal Valko
摘要
Smooth functions on graphs have wide applications in manifold and semi-supervised learning. In this work, we study a bandit problem where the payoffs of arms are smooth on a graph. This framework is suitable for solving online learning problems that involve graphs, such as content-based recommendation. In this problem, each item we can recommend is a node of an undirected graph and its expected rating is similar to the one of its neighbors. The goal is to recommend items that have high expected ratings. We aim for the algorithms where the cumulative regret with respect to the optimal policy would not scale poorly with the number of nodes. In particular, we introduce the notion of an effective dimension, which is small in real-world graphs, and propose three algorithms for solving our problem that scale linearly and sublinearly in this dimension. Our experiments on content recommendation problem show that a good estimator of user preferences for thousands of items can be learned from just tens of node evaluations.
JMLR Causal Inference High-Dimensional · 发表于 2020
Domagoj Ćevid, Peter Bühlmann, Nicolai Meinshausen
摘要
Standard high-dimensional regression methods assume that the underlying coefficient vector is sparse. This might not be true in some cases, in particular in presence of hidden, confounding variables. Such hidden confounding can be represented as a high-dimensional linear model where the sparse coefficient vector is perturbed. For this model, we develop and investigate a class of methods that are based on running the Lasso on preprocessed data. The preprocessing step consists of applying certain spectral transformations that change the singular values of the design matrix. We show that, under some assumptions, one can achieve the usual Lasso $\ell_1$-error rate for estimating the underlying sparse coefficient vector, despite the presence of confounding. Our theory also covers the Lava estimator (Chernozhukov et al., 2017) for a special model class. The performance of the methodology is illustrated on simulated data and a genomic dataset.
JMLR High-Dimensional Spatial & Time Series · 发表于 2020
Emmanuel Bacry, Martin Bompaire, Stéphane Gaïffas, Jean-Francois Muzy
摘要
We consider the problem of unveiling the implicit network structure of node interactions (such as user interactions in a social network), based only on high-frequency timestamps. Our inference is based on the minimization of the least-squares loss associated with a multivariate Hawkes model, penalized by $\ell_1$ and trace norm of the interaction tensor. We provide a first theoretical analysis for this problem, that includes sparsity and low-rank inducing penalizations. This result involves a new data-driven concentration inequality for matrix martingales in continuous time with observable variance, which is a result of independent interest and a broad range of possible applications since it extends to matrix martingales former results restricted to the scalar case. A consequence of our analysis is the construction of sharply tuned $\ell_1$ and trace-norm penalizations, that leads to a data-driven scaling of the variability of information available for each users. Numerical experiments illustrate the significant improvements achieved by the use of such data-driven penalizations.
JMLR High-Dimensional Machine Learning · 发表于 2020
Tyler M. Tomita, James Browne, Cencheng Shen, Jaewon Chung, Jesse L. Patsolic, Benjamin Falk, Carey E. Priebe, Jason Yim, Randal Burns, Mauro Maggioni, Joshua T. Vogelstein
摘要
Decision forests, including Random Forests and Gradient Boosting Trees, have recently demonstrated state-of-the-art performance in a variety of machine learning settings. Decision forests are typically ensembles of axis-aligned decision trees; that is, trees that split only along feature dimensions. In contrast, many recent extensions to decision forests are based on axis-oblique splits. Unfortunately, these extensions forfeit one or more of the favorable properties of decision forests based on axis-aligned splits, such as robustness to many noise dimensions, interpretability, or computational efficiency. We introduce yet another decision forest, called “Sparse Projection Oblique Randomer Forests” (SPORF). SPORF trees recursively split along very sparse random projections. Our method significantly improves accuracy over existing state-of-the-art algorithms on a standard benchmark suite for classification with $>100$ problems of varying dimension, sample size, and number of classes. To illustrate how SPORF addresses the limitations of both axis-aligned and existing oblique decision forest methods, we conduct extensive simulated experiments. SPORF typically yields improved performance over existing decision forest methods, while mitigating computational efficiency and scalability and maintaining interpretability. Very sparse random projections can be incorporated into gradient boosted trees to obtain potentially similar gains.
Econometrica Networks & Graphs · 发表于 2020
Ruben Enikolopov, Alexey Makarin, Maria Petrova
摘要
Do new communication technologies, such as social media, alleviate the collective action problem? This paper provides evidence that penetration of VK, the dominant Russian online social network, led to more protest activity during a wave of protests in Russia in 2011. As a source of exogenous variation in network penetration, we use the information on the city of origin of the students who studied with the founder of VK, controlling for the city of origin of the students who studied at the same university several years earlier or later. We find that a 10% increase in VK penetration increased the probability of a protest by 4.6% and the number of protesters by 19%. Additional results suggest that social media induced protest activity by reducing the costs of coordination rather than by spreading information critical of the government. We observe that VK penetration increased pro‐governmental support, with no evidence of increased polarization. We also find that cities with higher fractionalization of network users between VK and Facebook experienced fewer protests, and the effect of VK on protests exhibits threshold behavior.
Econometrica Econometrics & Economics · 发表于 2020
Elchanan Mossel, Manuel Mueller-Frank, Allan Sly, Omer Tamuz
摘要
We consider a large class of social learning models in which a group of agents face uncertainty regarding a state of the world, share the same utility function, observe private signals, and interact in a general dynamic setting. We introduce social learning equilibria, a static equilibrium concept that abstracts away from the details of the given extensive form, but nevertheless captures the corresponding asymptotic equilibrium behavior. We establish general conditions for agreement, herding, and information aggregation in equilibrium, highlighting a connection between agreement and information aggregation.
JMLR Other · 发表于 2020
Simon Fischer, Ingo Steinwart
摘要
Learning rates for least-squares regression are typically expressed in terms of $L_2$-norms. In this paper we extend these rates to norms stronger than the $L_2$-norm without requiring the regression function to be contained in the hypothesis space. In the special case of Sobolev reproducing kernel Hilbert spaces used as hypotheses spaces, these stronger norms coincide with fractional Sobolev norms between the used Sobolev space and $L_2$. As a consequence, not only the target function but also some of its derivatives can be estimated without changing the algorithm. From a technical point of view, we combine the well-known integral operator techniques with an embedding property, which so far has only been used in combination with empirical process arguments. This combination results in new finite sample bounds with respect to the stronger norms. From these finite sample bounds our rates easily follow. Finally, we prove the asymptotic optimality of our results in many cases.
JMLR Nonparametric & Semiparametric · 发表于 2020
Yu Liu, Kris De Brabanter
摘要
Derivatives play an important role in bandwidth selection methods (e.g., plug-ins), data analysis and bias-corrected confidence intervals. Therefore, obtaining accurate derivative information is crucial. Although many derivative estimation methods exist, the majority require a fixed design assumption. In this paper, we propose an effective and fully data-driven framework to estimate the first and second order derivative in random design. We establish the asymptotic properties of the proposed derivative estimator, and also propose a fast selection method for the tuning parameters. The performance and flexibility of the method is illustrated via an extensive simulation study.
JMLR Networks & Graphs · 发表于 2020
Thomas Ricatte, Rémi Gilleron, Marc Tommasi
摘要
We consider the skill rating problem for multiplayer games, that is how to infer player skills from game outcomes in multiplayer games. We formulate the problem as a minimization problem $\arg \min_{s} s^T \Delta s$ where $\Delta$ is a positive semidefinite matrix and $s$ a real-valued function, of which some entries are the skill values to be inferred and other entries are constrained by the game outcomes. We leverage graph-based semi-supervised learning (SSL) algorithms for this problem. We apply our algorithms on several data sets of multiplayer games and obtain very promising results compared to Elo Duelling (see Elo, 1978) and TrueSkill (see Herbrich et al., 2006).. As we leverage graph-based SSL algorithms and because games can be seen as relations between sets of players, we then generalize the approach. For this aim, we introduce a new finite model, called hypernode graph, defined to be a set of weighted binary relations between sets of nodes. We define Laplacians of hypernode graphs. Then, we show that the skill rating problem for multiplayer games can be formulated as $\arg \min_{s} s^T \Delta s$ where $\Delta$ is the Laplacian of a hypernode graph constructed from a set of games. From a fundamental perspective, we show that hypernode graph Laplacians are symmetric positive semidefinite matrices with constant functions in their null space. We show that problems on hypernode graphs can not be solved with graph constructions and graph kernels. We relate hypernode graphs to signed graphs showing that positive relations between groups can lead to negative relations between individuals.
JMLR Networks & Graphs · 发表于 2020
Ming Yu, Varun Gupta, Mladen Kolar
摘要
Probabilistic graphical models provide a flexible yet parsimonious framework for modeling dependencies among nodes in networks. There is a vast literature on parameter estimation and consistent model selection for graphical models. However, in many of the applications, scientists are also interested in quantifying the uncertainty associated with the estimated parameters and selected models, which current literature has not addressed thoroughly. In this paper, we propose a novel estimator for statistical inference on edge parameters in pairwise graphical models based on generalized Hyvarinen scoring rule. Hyvarinen scoring rule is especially useful in cases where the normalizing constant cannot be obtained efficiently in a closed form, which is a common problem for graphical models, including Ising models and truncated Gaussian graphical models. Our estimator allows us to perform statistical inference for general graphical models whereas the existing works mostly focus on statistical inference for Gaussian graphical models where finding normalizing constant is computationally tractable. Under mild conditions that are typically assumed in the literature for consistent estimation, we prove that our proposed estimator is $\sqrt{n}$-consistent and asymptotically normal, which allows us to construct confidence intervals and build hypothesis tests for edge parameters. Moreover, we show how our proposed method can be applied to test hypotheses that involve a large number of model parameters simultaneously. We illustrate validity of our estimator through extensive simulation studies on a diverse collection of data-generating processes.