研究园简易版 · 经典书籍 · 期刊文章 · 有原文 · 完整版(可多选筛选、搜索) · 首页
2019 年的期刊文章 · 第 26 页
共 1232 篇,按发表时间排,新的在前,每页 40 篇。这一页是 2019 到 2019。
按期刊、按主题看 →
JMLR Other · 发表于 2019
Ofer Meshi, Ben London, Adrian Weller, David Sontag
摘要
Structured prediction is used in areas including computer vision and natural language processing to predict structured outputs such as segmentations or parse trees. In these settings, prediction is performed by MAP inference or, equivalently, by solving an integer linear program. Because of the complex scoring functions required to obtain accurate predictions, both learning and inference typically require the use of approximate solvers. We propose a theoretical explanation for the striking observation that approximations based on linear programming (LP) relaxations are often tight (exact) on real-world instances. In particular, we show that learning with LP relaxed inference encourages integrality of training instances, and that this training tightness generalizes to test data.
Econometrica Other · 发表于 2019
Alessandra Casella, Thomas Palfrey
摘要
We develop a framework to study the dynamics of vote trading over multiple binary issues. We prove that there always exists a stable allocation of votes that is reachable in a finite number of trades, for any number of voters and issues, any separable preference profile, and any restrictions on the coalitions that may form. If at every step all blocking trades are chosen with positive probability, convergence to a stable allocation occurs in finite time with probability 1. If coalitions are unrestricted, the outcome of vote trading must be Pareto optimal, but unless there are three voters or two issues, it need not correspond to the Condorcet winner.
Econometrica Econometrics & Economics Networks & Graphs · 发表于 2019
Tamás Fleiner, Ravi Jagadeesan, Zsuzsanna Jankó, Alexander Teytelboym
摘要
We show how frictions and continuous transfers jointly affect equilibria in a model of matching in trading networks. Our model incorporates distortionary frictions such as transaction taxes and commissions. When contracts are fully substitutable for firms, competitive equilibria exist and coincide with outcomes that satisfy a cooperative solution concept called trail stability. However, competitive equilibria are generally neither stable nor Pareto‐efficient.
Econometrica Econometrics & Economics · 发表于 2019
Lorenzo Caliendo, Maximiliano Dvorkin, Fernando Parro
摘要
We develop a dynamic trade model with spatially distinct labor markets facing varying exposure to international trade. The model captures the role of labor mobility frictions, goods mobility frictions, geographic factors, and input‐output linkages in determining equilibrium allocations. We show how to solve the equilibrium of the model and take the model to the data without assuming that the economy is at a steady state and without estimating productivities, migration frictions, or trade costs, which can be difficult to identify. We calibrate the model to 22 sectors, 38 countries, and 50 U.S. states. We study how the rise in China's trade for the period 2000 to 2007 impacted U.S. households across more than a thousand U.S. labor markets distinguished by sector and state. We find that the China trade shock resulted in a reduction of about 0.55 million U.S. manufacturing jobs, about 16% of the observed decline in manufacturing employment from 2000 to 2007. The U.S. gains in the aggregate, but due to trade and migration frictions, the welfare and employment effects vary across U.S. labor markets. Estimated transition costs to the new long‐run equilibrium are also heterogeneous and reflect the importance of accounting for labor dynamics.
JMLR Survival Analysis Networks & Graphs Machine Learning · 发表于 2019
Håvard Kvamme, Ørnulf Borgan, Ida Scheel
摘要
New methods for time-to-event prediction are proposed by extending the Cox proportional hazards model with neural networks. Building on methodology from nested case-control studies, we propose a loss function that scales well to large data sets and enables fitting of both proportional and non-proportional extensions of the Cox model. Through simulation studies, the proposed loss function is verified to be a good approximation for the Cox partial log-likelihood. The proposed methodology is compared to existing methodologies on real-world data sets and is found to be highly competitive, typically yielding the best performance in terms of Brier score and binomial log-likelihood. A python package for the proposed methods is available at https://github.com/havakv/pycox.
JMLR Machine Learning · 发表于 2019
Mónika Csikós, Nabil H. Mustafa, Andrey Kupavskii
摘要
The VC-dimension of a set system is a way to capture its complexity and has been a key parameter studied extensively in machine learning and geometry communities. In this paper, we resolve two longstanding open problems on bounding the VC-dimension of two fundamental set systems: $k$-fold unions/intersections of half-spaces and the simplices set system. Among other implications, it settles an open question in machine learning that was first studied in the foundational paper of Blumer et al. (1989) as well as by Eisenstat and Angluin (2007) and Johnson (2008).
JMLR Optimization & Learning Theory · 发表于 2019
Sondre Glimsdal, Ole-Christoffer Granmo
摘要
The multi-armed bandit problem forms the foundation for solving a wide range of online stochastic optimization problems through a simple, yet effective mechanism. One simply casts the problem as a gambler who repeatedly pulls one out of N slot machine arms, eliciting random rewards. Learning of reward probabilities is then combined with reward maximization, by carefully balancing reward exploration against reward exploitation. In this paper, we address a particularly intriguing variant of the multi-armed bandit problem, referred to as the Stochastic Point Location (SPL) problem. The gambler is here only told whether the optimal arm (point) lies to the “left” or to the “right” of the arm pulled, with the feedback being erroneous with probability $1-\pi$. This formulation thus targets optimization in continuous action spaces with both informative and deceptive feedback. To tackle this class of problems, we formulate a compact and scalable Bayesian representation of the solution space that simultaneously captures both the location of the optimal arm as well as the probability of receiving correct feedback. We further introduce the accompanying Thompson Sampling guided Stochastic Point Location (TS-SPL) scheme for balancing exploration against exploitation. By learning $\pi$, TS-SPL also supports deceptive environments that are lying about the direction of the optimal arm. This, in turn, allows us to address the fundamental Stochastic Root Finding (SRF) problem. Empirical results demonstrate that our scheme deals with both deceptive and informative environments, significantly outperforming competing algorithms both for SRF and SPL.
JMLR Latent Variables & Mixtures · 发表于 2019
Dong Xia, Fan Zhou
摘要
The higher order singular value decomposition (HOSVD) of tensors is a generalization of matrix SVD. The perturbation analysis of HOSVD under random noise is more delicate than its matrix counterpart. Recently, polynomial time algorithms have been proposed where statistically optimal estimates of the singular subspaces and the low rank tensors are attainable in the Euclidean norm. In this article, we analyze the sup-norm perturbation bounds of HOSVD and introduce estimators of the singular subspaces with sharp deviation bounds in the sup-norm. We also investigate a low rank tensor denoising estimator and demonstrate its fast convergence rate with respect to the entry-wise errors. The sup-norm perturbation bounds reveal unconventional phase transitions for statistical learning applications such as the exact clustering in high dimensional Gaussian mixture model and the exact support recovery in sub-tensor localizations. In addition, the bounds established for HOSVD also elaborate the one-sided sup-norm perturbation bounds for the singular subspaces of unbalanced (or fat) matrices.
JMLR Other · 发表于 2019
Roei Gelbhart, Ran El-Yaniv
摘要
A selective classifier $(f,g)$ comprises a classification function $f$ and a binary selection function $g$, which determines if the classifier abstains from prediction, or uses $f$ to predict. The classifier is called pointwise-competitive if it classifies each point identically to the best classifier in hindsight (from the same class), whenever it does not abstain. The quality of such a classifier is quantified by its rejection mass, defined to be the probability mass of the points it rejects. A “fast” rejection rate is achieved if the rejection mass is bounded from above by $\tilde{O}(1/m)$ where $m$ is the number of labeled examples used to train the classifier (and $\tilde{O}$ hides logarithmic factors). Pointwise-competitive selective (PCS) classifiers are intimately related to disagreement-based active learning and it is known that in the realizable case, a fast rejection rate of a known PCS algorithm (called Consistent Selective Strategy) is equivalent to an exponential speedup of the well-known CAL active algorithm. We focus on the agnostic setting, for which there is a known algorithm called LESS that learns a PCS classifier and achieves a fast rejection rate (depending on Hannekeâs disagreement coefficient) under strong assumptions. We present an improved PCS learning algorithm called ILESS for which we show a fast rate (depending on Hanneke's disagreement coefficient) without any assumptions. Our rejection bound smoothly interpolates the realizable and agnostic settings. The main result of this paper is an equivalence between the following three entities: (i) the existence of a fast rejection rate for any PCS learning algorithm (such as ILESS); (ii) a poly-logarithmic bound for Hanneke's disagreement coefficient; and (iii) an exponential speedup for a new disagreement-based active learner called {\ActiveiLESS}.
JMLR Networks & Graphs Causal Inference · 发表于 2019
Arjun Sondhi, Ali Shojaie
摘要
We consider the task of estimating a high-dimensional directed acyclic graph, given observations from a linear structural equation model with arbitrary noise distribution. By exploiting properties of common random graphs, we develop a new algorithm that requires conditioning only on small sets of variables. The proposed algorithm, which is essentially a modified version of the PC-Algorithm, offers significant gains in both computational complexity and estimation accuracy. In particular, it results in more efficient and accurate estimation in large networks containing hub nodes, which are common in biological systems. We prove the consistency of the proposed algorithm, and show that it also requires a less stringent faithfulness assumption than the PC-Algorithm. Simulations in low and high-dimensional settings are used to illustrate these findings. An application to gene expression data suggests that the proposed algorithm can identify a greater number of clinically relevant genes than current methods.
Econometrica Other · 发表于 2019
Lorenzo Bastianello, Marco LiCalzi
摘要
We revisit the Nash bargaining model and axiomatize a procedural solution that maximizes the probability of successful bargaining. Our characterization spans several known solution concepts, including the special cases of the Nash, egalitarian, and utilitarian solutions. Using a probability‐based language, we offer a natural interpretation for the product operator underlying the Nash solution: when the bargainers' individual acceptance probabilities are independent, their product recovers the joint acceptance probability.
Econometrica Other · 发表于 2019
Thomas Demuynck, P. Jean-Jacques Herings, Riccardo D. Saulle, Christian Seel
摘要
We introduce a new solution concept for models of coalition formation, called the myopic stable set (MSS). The MSS is defined for a general class of social environments and allows for an infinite state space. An MSS exists and, under minor continuity assumptions, it is also unique. The MSS generalizes and unifies various results from more specific applications. It coincides with the coalition structure core in coalition function form games when this set is nonempty; with the set of stable matchings in the Gale-Shapley matching model; with the set of pairwise stable networks and closed cycles in models of network formation; and with the set of pure strategy Nash equilibria in pseudo-potential games and finite supermodular games. We also characterize the MSS for the class of proper simple games. *(abstract via OpenAlex)*
Econometrica Econometrics & Economics · 发表于 2019
David Rezza Baqaee, Emmanuel Farhi
摘要
We provide a nonlinear characterization of the macroeconomic impact of microeconomic productivity shocks in terms of reduced‐form nonparametric elasticities for efficient economies. We also show how microeconomic parameters are mapped to these reduced‐form general equilibrium elasticities. In this sense, we extend the foundational theorem of Hulten (1978) beyond the first order to capture nonlinearities. Key features ignored by first‐order approximations that play a crucial role are: structural microeconomic elasticities of substitution, network linkages, structural microeconomic returns to scale, and the extent of factor reallocation. In a business‐cycle calibration with sectoral shocks, nonlinearities magnify negative shocks and attenuate positive shocks, resulting in an aggregate output distribution that is asymmetric (negative skewness), fat‐tailed (excess kurtosis), and has a negative mean, even when shocks are symmetric and thin‐tailed. Average output losses due to short‐run sectoral shocks are an order of magnitude larger than the welfare cost of business cycles calculated by Lucas (1987). Nonlinearities can also cause shocks to critical sectors to have disproportionate macroeconomic effects, almost tripling the estimated impact of the 1970s oil shocks on world aggregate output. Finally, in a long‐run growth context, nonlinearities, which underpin Baumol's cost disease via the increase over time in the sales shares of low‐growth bottleneck sectors, account for a 20 percentage point reduction in aggregate TFP growth over the period 1948–2014 in the United States.
Econometrica Other · 发表于 2019
Yingni Guo, Eran Shmaya
摘要
A sender persuades a receiver to accept a project by disclosing information about a payoff‐relevant quality. The receiver has private information about the quality, referred to as his type. We show that the sender‐optimal mechanism takes the form of nested intervals: each type accepts on an interval of qualities and a more optimistic type's interval contains a less optimistic type's interval. This nested‐interval structure offers a simple algorithm to solve for the optimal disclosure and connects our problem to the monopoly screening problem. The mechanism is optimal even if the sender conditions the disclosure mechanism on the receiver's reported type.
JMLR Optimization & Learning Theory · 发表于 2019
Po-Wei Wang, Ching-pei Lee, Chih-Jen Lin
摘要
State-of-the-art first- and second-order optimization methods are able to achieve either fast global linear convergence rates or quadratic convergence, but not both of them. In this work, we propose an interpolation between first- and second-order methods for regularized empirical risk minimization that exploits the problem structure to efficiently combine multiple update directions. Our method attains both optimal global linear convergence rate for first-order methods, and local quadratic convergence. Experimental results show that our method outperforms state-of-the-art first- and second-order optimization methods in terms of the number of data accesses, while is competitive in training time.
Econometrica Econometrics & Economics · 发表于 2019
Chang-Tai Hsieh, Erik Hurst, Charles I. Jones, Peter J. Klenow
摘要
In 1960, 94 percent of doctors and lawyers were white men. By 2010, the fraction was just 62 percent. Similar changes in other highly‐skilled occupations have occurred throughout the U.S. economy during the last 50 years. Given that the innate talent for these professions is unlikely to have changed differently across groups, the change in the occupational distribution since 1960 suggests that a substantial pool of innately talented women and black men in 1960 were not pursuing their comparative advantage. We examine the effect on aggregate productivity of the convergence in the occupational distribution between 1960 and 2010 through the prism of a Roy model. Across our various specifications, between 20% and 40% of growth in aggregate market output per person can be explained by the improved allocation of talent.
Econometrica Econometrics & Economics · 发表于 2019
Martin Beraja, Erik Hurst, Juan Ospina
摘要
Making inferences about aggregate business cycles from regional variation alone is difficult because of economic channels and shocks that differ between regional and aggregate economies. However, we argue that regional business cycles contain valuable information that can help discipline models of aggregate fluctuations. We begin by documenting a strong relationship across U.S. states between local employment and wage growth during the Great Recession. This relationship is much weaker in U.S. aggregates. Then, we present a methodology that combines such regional and aggregate data in order to estimate a medium‐scale New Keynesian DSGE model. We find that aggregate demand shocks were important drivers of aggregate employment during the Great Recession, but the wage stickiness necessary for them to account for the slow employment recovery and the modest fall in aggregate wages is inconsistent with the flexibility of wages we observe across U.S. states. Finally, we show that our methodology yields different conclusions about the causes of aggregate employment and wage dynamics between 2007 and 2014 than either estimating our model with aggregate data alone or performing back‐of‐the‐envelope calculations that directly extrapolate from well‐identified regional elasticities.
JMLR Machine Learning · 发表于 2019
Jean Kossaifi, Yannis Panagakis, Anima Anandkumar, Maja Pantic
摘要
Tensors are higher-order extensions of matrices. While matrix methods form the cornerstone of traditional machine learning and data analysis, tensor methods have been gaining increasing traction. However, software support for tensor operations is not on the same footing. In order to bridge this gap, we have developed TensorLy, a Python library that provides a high-level API for tensor methods and deep tensorized neural networks. TensorLy aims to follow the same standards adopted by the main projects of the Python scientific community, and to seamlessly integrate with them. Its BSD license makes it suitable for both academic and commercial applications. TensorLy's backend system allows users to perform computations with several libraries such as NumPy or PyTorch to name but a few. They can be scaled on multiple CPU or GPU machines. In addition, using the deep-learning frameworks as backend allows to easily design and train deep tensorized neural networks. TensorLy is available at https://github.com/tensorly/tensorly
Econometrica Econometrics & Economics · 发表于 2019
Mark Aguiar, Manuel Amador, Hugo Hopenhayn, Iván Werning
摘要
We study the interactions between sovereign debt default and maturity choice in a setting with limited commitment for repayment as well as future debt issuances. Our main finding is that, under a wide range of conditions, the sovereign should, as long as default is not preferable, remain passive in long‐term bond markets, making payments and retiring long‐term bonds as they mature but never actively issuing or buying back such bonds. The only active debt‐management margin is the short‐term bond market. We show that any attempt to manipulate the existing maturity profile of outstanding long‐term bonds generates losses, as bond prices move against the sovereign. Our results hold regardless of the shape of the yield curve. The yield curve captures the average costs of financing at different maturities but is misleading regarding the marginal costs.
Econometrica Other · 发表于 2019
Andreas Kleiner, Alejandro Manelli
摘要
The main result in Daskalakis, Deckelbaum, and Tzamos (2017) establishes strong duality in the monopoly problem with an argument based on transportation theory. We provide a short, alternative proof using linear programming.
JMLR Other · 发表于 2019
Armin Eftekhari, Gregory Ongie, Laura Balzano, Michael B. Wakin
摘要
Linear subspace models are pervasive in computational sciences and particularly used for large datasets which are often incomplete due to privacy issues or sampling constraints. Therefore, a critical problem is developing an efficient algorithm for detecting low-dimensional linear structure from incomplete data efficiently, in terms of both computational complexity and storage. In this paper we propose a streaming subspace estimation algorithm called Subspace Navigation via Interpolation from Partial Entries (SNIPE) that efficiently processes blocks of incomplete data to estimate the underlying subspace model. In every iteration, SNIPE finds the subspace that best fits the new data block but remains close to the previous estimate. We show that SNIPE is a streaming solver for the underlying nonconvex matrix completion problem, that it converges globally {to a stationary point of this program} regardless of initialization, and that the convergence is locally linear with high probability. We also find that SNIPE shows state-of-the-art performance in our numerical simulations.
Econometrica Other · 发表于 2019
Tilman Börgers, Jiangtao Li
摘要
We define and investigate a property of mechanisms that we call “strategic simplicity,” and that is meant to capture the idea that, in strategically simple mechanisms, strategic choices require limited strategic sophistication. We define a mechanism to be strategically simple if choices can be based on first‐order beliefs about the other agents' preferences and first‐order certainty about the other agents' rationality alone, and there is no need for agents to form higher‐order beliefs, because such beliefs are irrelevant to the optimal strategies. All dominant strategy mechanisms are strategically simple. But many more mechanisms are strategically simple. In particular, strategically simple mechanisms may be more flexible than dominant strategy mechanisms in the bilateral trade problem and the voting problem.
Econometrica Other · 发表于 2019
Gabriel Carroll, Georgy Egorov
摘要
A receiver wants to learn multidimensional information from a sender, and she has the capacity to verify just one dimension. The sender's payoff depends on the belief he induces, via an exogenously given monotone function. We show that by using a randomized verification strategy, the receiver can learn the sender's information fully in many cases. We characterize exactly when it is possible to do so. In particular, when the exogenous payoff function is submodular, we can explicitly describe a full‐learning mechanism; when it is (strictly) supermodular, full learning is not possible. In leading cases where full learning is possible, it can be attained using an indirect mechanism in which the sender chooses the probability of verifying each dimension.
JMLR Optimization & Learning Theory · 发表于 2019
Dongruo Zhou, Pan Xu, Quanquan Gu
摘要
We propose a stochastic variance-reduced cubic regularized Newton method (SVRC) for non-convex optimization. At the core of SVRC is a novel semi-stochastic gradient along with a semi-stochastic Hessian, which are specifically designed for cubic regularization method. For a nonconvex function with $n$ component functions, we show that our algorithm is guaranteed to converge to an $(\epsilon,\sqrt{\epsilon})$-approximate local minimum within $\tilde{O}(n^{4/5}/\epsilon^{3/2})$\footnote{Here $\tilde{O}$ hides poly-logarithmic factors.} second-order oracle calls, which outperforms the state-of-the-art cubic regularization algorithms including subsampled cubic regularization. To further reduce the sample complexity of Hessian matrix computation in cubic regularization based methods, we also propose a sample efficient stochastic variance-reduced cubic regularization (Lite-SVRC) algorithm for finding the local minimum more efficiently. Lite-SVRC converges to an $(\epsilon,\sqrt{\epsilon})$-approximate local minimum within $\tilde{O}(n+n^{2/3}/\epsilon^{3/2})$ Hessian sample complexity, which is faster than all existing cubic regularization based methods. Numerical experiments with different nonconvex optimization problems conducted on real datasets validate our theoretical results for both SVRC and Lite-SVRC.
JMLR Optimization & Learning Theory · 发表于 2019
Qianxiao Li, Cheng Tai, Weinan E
摘要
We develop the mathematical foundations of the stochastic modified equations (SME) framework for analyzing the dynamics of stochastic gradient algorithms, where the latter is approximated by a class of stochastic differential equations with small noise parameters. We prove that this approximation can be understood mathematically as an weak approximation, which leads to a number of precise and useful results on the approximations of stochastic gradient descent (SGD), momentum SGD and stochastic Nesterov's accelerated gradient method in the general setting of stochastic objectives. We also demonstrate through explicit calculations that this continuous-time approach can uncover important analytical insights into the stochastic gradient algorithms under consideration that may not be easy to obtain in a purely discrete-time setting.
JMLR Optimization & Learning Theory · 发表于 2019
Chao Gao, Dan Garber, Nathan Srebro, Jialei Wang, Weiran Wang
摘要
We study the sample complexity of canonical correlation analysis (CCA), i.e., the number of samples needed to estimate the population canonical correlation and directions up to arbitrarily small error. With mild assumptions on the data distribution, we show that in order to achieve $\epsilon$-suboptimality in a properly defined measure of alignment between the estimated canonical directions and the population solution, we can solve the empirical objective exactly with $N(\epsilon, \Delta, \gamma)$ samples, where $\Delta$ is the singular value gap of the whitened cross-covariance matrix and $1/\gamma$ is an upper bound of the condition number of auto-covariance matrices. Moreover, we can achieve the same learning accuracy by drawing the same level of samples and solving the empirical objective approximately with a stochastic optimization algorithm; this algorithm is based on the shift-and-invert power iterations and only needs to process the dataset for $\mathcal{O} \left(\log \frac{1}{\epsilon} \right)$ passes. Finally, we show that, given an estimate of the canonical correlation, the streaming version of the shift-and-invert power iterations achieves the same learning accuracy with the same level of sample complexity, by processing the data only once.
Econometrica Econometrics & Economics · 发表于 2019
Yeon-Koo Che, Jinwoo Kim, Fuhito Kojima
摘要
We study stability of two-sided many-to-one matching in which firms' preferences for workers may exhibit complementarities. Although such preferences are known to jeopardize stability in a finite market, we show that a stable matching exists in a large market with a continuum of workers, provided that each firm's choice is convex and changes continuously as the set of available workers changes. We also study the existence and structure of stable matchings under preferences exhibiting substitutability and indifferences in a large market. Building on these results, we show that an approximately stable matching exists in large finite economies. We extend our framework to ensure a stable matching with desirable incentive and fairness properties in the presence of indifferences in firms' preferences. *(abstract via OpenAlex)*
JMLR Machine Learning Networks & Graphs Optimization & Learning Theory · 发表于 2019
Luca Venturi, Afonso S. Bandeira, Joan Bruna
摘要
Neural networks provide a rich class of high-dimensional, non-convex optimization problems. Despite their non-convexity, gradient-descent methods often successfully optimize these models. This has motivated a recent spur in research attempting to characterize properties of their loss surface that may explain such success. In this paper, we address this phenomenon by studying a key topological property of the loss: the presence or absence of spurious valleys, defined as connected components of sub-level sets that do not include a global minimum. Focusing on a class of one-hidden-layer neural networks defined by smooth (but generally non-linear) activation functions, we identify a notion of intrinsic dimension and show that it provides necessary and sufficient conditions for the absence of spurious valleys. More concretely, finite intrinsic dimension guarantees that for sufficiently overparametrised models no spurious valleys exist, independently of the data distribution. Conversely, infinite intrinsic dimension implies that spurious valleys do exist for certain data distributions, independently of model overparametrisation. Besides these positive and negative results, we show that, although spurious valleys may exist in general, they are confined to low risk levels and avoided with high probability on overparametrised models.
JMLR Networks & Graphs · 发表于 2019
Ashish Khetan, Sewoong Oh
摘要
Singular values of a data in a matrix form provide insights on the structure of the data, the effective dimensionality, and the choice of hyper-parameters on higher-level data analysis tools. However, in many practical applications such as collaborative filtering and network analysis, we only get a partial observation. Under such scenarios, we consider the fundamental problem of recovering spectral properties of the underlying matrix from a sampling of its entries. In this paper, we address the problem of directly recovering the spectrum, which is the set of singular values, and also in sample-efficient approaches for recovering a spectral sum function, which is an aggregate sum of a fixed function applied to each of the singular values. Our approach is to first estimate the Schatten $k$-norms of a matrix for a small set of values of $k$, and then apply Chebyshev approximation when estimating a spectral sum function or apply moment matching in Wasserstein distance when estimating the singular values directly. The main technical challenge is in accurately estimating the Schatten norms from a sampling of a matrix. We introduce a novel unbiased estimator based on counting small structures called network motifs in a graph and provide guarantees that match its empirical performance. Our theoretical analysis shows that Schatten norms can be recovered accurately from strictly smaller number of samples compared to what is needed to recover the underlying low-rank matrix. Numerical experiments suggest that we significantly improve upon a competing approach of using matrix completion methods, below the matrix completion threshold, above which matrix completion algorithms recover the underlying low-rank matrix exactly.
JMLR Nonparametric & Semiparametric High-Dimensional · 发表于 2019
Lei Shi, Xiaolin Huang, Yunlong Feng, Johan A.K. Suykens
摘要
In this paper, we consider the $\ell_q-$regularized kernel regression with $0 < q \leq 1$. In form, the algorithm minimizes a least-square loss functional adding a coefficient-based $\ell_q-$penalty term over a linear span of features generated by a kernel function. We study the asymptotic behavior of the algorithm under the framework of learning theory. The contribution of this paper is two-fold. First, we derive a tight bound on the $\ell_2-$empirical covering numbers of the related function space involved in the error analysis. Based on this result, we obtain the convergence rates for the $\ell_1-$regularized kernel regression which is the best so far. Second, for the case $0 < q < 1$, we show that the regularization parameter plays a role as a trade-off between sparsity and convergence rates. Under some mild conditions, the fraction of non-zero coefficients in a local minimizer of the algorithm will tend to $0$ at a polynomial decay rate when the sample size $m$ becomes large. As the concerned algorithm is non-convex, we also discuss how to generate a minimizing sequence iteratively, which can help us to search a local minimizer around any initial point.
JMLR High-Dimensional · 发表于 2019
Ziyan Luo, Defeng Sun, Kim-Chuan Toh, Naihua Xiu
摘要
The octagonal shrinkage and clustering algorithm for regression (OSCAR), equipped with the $\ell_1$-norm and a pair-wise $\ell_{\infty}$-norm regularizer, is a useful tool for feature selection and grouping in high-dimensional data analysis. The computational challenge posed by OSCAR, for high dimensional and/or large sample size data, has not yet been well resolved due to the non-smoothness and non-separability of the regularizer involved. In this paper, we successfully resolve this numerical challenge by proposing a sparse semismooth Newton-based augmented Lagrangian method to solve the more general SLOPE (the sorted L-one penalized estimation) model. By appropriately exploiting the inherent sparse and low-rank property of the generalized Jacobian of the semismooth Newton system in the augmented Lagrangian subproblem, we show how the computational complexity can be substantially reduced. Our algorithm offers a notable computational advantage in the high-dimensional statistical regression settings. Numerical experiments are conducted on real data sets, and the results demonstrate that our algorithm is far superior, in both speed and robustness, to the existing state-of-the-art algorithms based on first-order iterative schemes, including the widely used accelerated proximal gradient (APG) method and the alternating direction method of multipliers (ADMM).
Econometrica Networks & Graphs · 发表于 2019
Emily Breza, Arun G. Chandrasekhar
摘要
We study whether individuals save more when information about their savings is shared with another village member (a monitor). We focus on whether the monitor's eectiveness depends on her network position. Central monitors may be better able to disseminate information, and more proximate monitors may pass information to individ- uals who interact with the saver frequently. In 30 villages, we randomly assign monitors. Average monitors increase savings by 35%. A one-standard deviation more central monitor increases savings by 14%; increasing proximity from social distance three to two increases savings by 16%. The increased savings persist over a year after the intervention's end, and monitored savers better respond to shocks. In 30 other villages, savers choose their monitors. Proximate and central monitors are chosen. Information flows. 63% of monitors tell others about the saver's progress. 15 months later, others know more about the saver's progress and believe she is responsible if the saver was assigned a more central monitor. *(abstract via OpenAlex)*
JMLR Networks & Graphs · 发表于 2019
Ben Dai, Junhui Wang, Xiaotong Shen, Annie Qu
摘要
Recommender systems predict users' preferences over a large number of items by pooling similar information from other users and/or items in the presence of sparse observations. One major challenge is how to utilize user-item specific covariates and networks describing user-item interactions in a high-dimensional situation, for accurate personalized prediction. In this article, we propose a smooth neighborhood recommender in the framework of the latent factor models. A similarity kernel is utilized to borrow neighborhood information from continuous covariates over a user-item specific network, such as a user's social network, where the grouping information defined by discrete covariates is also integrated through the network. Consequently, user-item specific information is built into the recommender to battle the `cold-start” issue in the absence of observations in collaborative and content-based filtering. Moreover, we utilize a “divide-and-conquer” version of the alternating least squares algorithm to achieve scalable computation, and establish asymptotic results for the proposed method, demonstrating that it achieves superior prediction accuracy. Finally, we illustrate that the proposed method improves substantially over its competitors in simulated examples and real benchmark data--Last.fm music data.
JMLR Optimization & Learning Theory · 发表于 2019
Mark Bun, Kobbi Nissim, Uri Stemmer
摘要
We investigate the direct-sum problem in the context of differentially private PAC learning: What is the sample complexity of solving $k$ learning tasks simultaneously under differential privacy, and how does this cost compare to that of solving $k$ learning tasks without privacy? In our setting, an individual example consists of a domain element $x$ labeled by $k$ unknown concepts $(c_1,\ldots,c_k)$. The goal of a multi-learner is to output $k$ hypotheses $(h_1,\ldots,h_k)$ that generalize the input examples. Without concern for privacy, the sample complexity needed to simultaneously learn $k$ concepts is essentially the same as needed for learning a single concept. Under differential privacy, the basic strategy of learning each hypothesis independently yields sample complexity that grows polynomially with $k$. For some concept classes, we give multi-learners that require fewer samples than the basic strategy. Unfortunately, however, we also give lower bounds showing that even for very simple concept classes, the sample cost of private multi-learning must grow polynomially in $k$.
JMLR Other · 发表于 2019
Ali Ahmed, Alireza Aghasi, Paul Hand
摘要
We consider the task of recovering two real or complex $m$-vectors from phaseless Fourier measurements of their circular convolution. Our method is a novel convex relaxation that is based on a lifted matrix recovery formulation that allows a non-trivial convex relaxation of the bilinear measurements from convolution. We prove that if the two signals belong to known random subspaces of dimensions $k$ and $n$, then they can be recovered up to the inherent scaling ambiguity with $m \gg (k+n) \log^2 m$ phaseless measurements. Our method provides the first theoretical recovery guarantee for this problem by a computationally efficient algorithm and does not require a solution estimate to be computed for initialization. Our proof is based on Rademacher complexity estimates. Additionally, we provide an alternating direction method of multipliers (ADMM) implementation and provide numerical experiments that verify the theory.
JMLR Meta-Analysis & Data Integration · 发表于 2019
Yuntao Chen, Chenxia Han, Yanghao Li, Zehao Huang, Yi Jiang, Naiyan Wang, Zhaoxiang Zhang
摘要
Object detection and instance recognition play a central role in many AI applications like autonomous driving, video surveillance and medical image analysis. However, training object detection models on large scale datasets remains computationally expensive and time consuming. This paper presents an efficient and open source object detection framework called SimpleDet which enables the training of state-of-the-art detection models on consumer grade hardware at large scale. SimpleDet covers a wide range of models including both high-performance and high-speed ones. SimpleDet is well-optimized for both low precision training and distributed training and achieves 70% higher throughput for the Mask R-CNN detector compared with existing frameworks. Codes, examples and documents of SimpleDet can be found at https://github.com/tusimple/simpledet.
JMLR Other · 发表于 2019
Richard Y. Zhang, Somayeh Sojoudi, Javad Lavaei
摘要
Nonconvex matrix recovery is known to contain no spurious local minima under a restricted isometry property (RIP) with a sufficiently small RIP constant $\delta$. If $\delta$ is too large, however, then counterexamples containing spurious local minima are known to exist. In this paper, we introduce a proof technique that is capable of establishing sharp thresholds on $\delta$ to guarantee the inexistence of spurious local minima. Using the technique, we prove that in the case of a rank-1 ground truth, an RIP constant of $\delta<1/2$ is both necessary and sufficient for exact recovery from any arbitrary initial point (such as a random point). We also prove a local recovery result: given an initial point $x_{0}$ satisfying $f(x_{0})\le(1-\delta)^{2}f(0)$, any descent algorithm that converges to second-order optimality guarantees exact recovery.
JMLR Bayesian Methods · 发表于 2019
Alexander M. Franks, Peter Hoff
摘要
We develop a model-based method for evaluating heterogeneity among several $p\times p$ covariance matrices in the large $p$, small $n$ setting. This is done by assuming a spiked covariance model for each group and sharing information about the space spanned by the group-level eigenvectors. We use an empirical Bayes method to identify a low-dimensional subspace which explains variation across all groups and use an MCMC algorithm to estimate the posterior uncertainty of eigenvectors and eigenvalues on this subspace. The implementation and utility of our model is illustrated with analyses of high-dimensional multivariate gene expression.
Biometrics Bayesian Methods Nonparametric & Semiparametric High-Dimensional · 发表于 2019
Antonio R. Linero, Debajyoti Sinha, Stuart R. Lipsitz
摘要
This paper demonstrates the advantages of sharing information about unknown features of covariates across multiple model components in various nonparametric regression problems including multivariate, heteroscedastic, and semicontinuous responses. In this paper, we present a methodology which allows for information to be shared nonparametrically across various model components using Bayesian sum‐of‐tree models. Our simulation results demonstrate that sharing of information across related model components is often very beneficial, particularly in sparse high‐dimensional problems in which variable selection must be conducted. We illustrate our methodology by analyzing medical expenditure data from the Medical Expenditure Panel Survey (MEPS). To facilitate the Bayesian nonparametric regression analysis, we develop two novel models for analyzing the MEPS data using Bayesian additive regression trees—a heteroskedastic log‐normal hurdle model with a “shrink‐toward‐homoskedasticity” prior and a gamma hurdle model.
JMLR High-Dimensional Meta-Analysis & Data Integration · 发表于 2019
Tomoyuki Obuchi, Yoshiyuki Kabashima
摘要
An approximate method for conducting resampling in Lasso, the $\ell_1$ penalized linear regression, in a semi-analytic manner is developed, whereby the average over the resampled datasets is directly computed without repeated numerical sampling, thus enabling an inference free of the statistical fluctuations due to sampling finiteness, as well as a significant reduction of computational time. The proposed method is based on a message passing type algorithm, and its fast convergence is guaranteed by the state evolution analysis, when covariates are provided as zero-mean independently and identically distributed Gaussian random variables. It is employed to implement bootstrapped Lasso (Bolasso) and stability selection, both of which are variable selection methods using resampling in conjunction with Lasso, and resolves their disadvantage regarding computational cost. To examine approximation accuracy and efficiency, numerical experiments were carried out using simulated datasets. Moreover, an application to a real-world dataset, the wine quality dataset, is presented. To process such real-world datasets, an objective criterion for determining the relevance of selected variables is also introduced by the addition of noise variables and resampling. MATLAB codes implementing the proposed method are distributed in (Obuchi, 2018).