text:
admit a unique underlying invariant Lebesgue density. Observations drawn from dynamical systems are not independent and moreover, usual mixing concepts may not be appropriate for measuring the dependence among these observations. By employing the C-mixing concept to measure the dependence, we conduct statistical analysis on the consistency and convergence of the kernel density estimator. Our main results are as follows: First, we show that with properly chosen bandwidth, the kernel density estimator is universally consistent under L1-norm; Second, we establish convergence rates for the estimator with respect to several classes of dynamical systems under L1-norm. In the analysis, the density function f is only assumed to be H\"{o}lder continuous or pointwise H\"{o}lder controllable which is a weak assumption in the literature of nonparametric density estimation and also more realistic in the dynamical system context. Last but not least, we prove that the same convergence rates of the estimator under L∞-norm and L1-norm can be achieved when the density function is H\"{o}lder continuous, compactly supported, and bounded. The bandwidth selection problem of the kernel density estimator for dynamical system is also discussed in our study via numerical simulations.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1260–1308},
numpages = {49},
keywords = {covering number, dynamical system, universal consistency, kernel density estimation, convergence rates, C-mixing process, learning theory, dependent observations}
}

@article{10.5555/3291125.3291159,
author = {Kailkhura, Bhavya and Thiagarajan, Jayaraman J. and Rastogi, Charvi and Varshney, Pramod K. and Bremer, Peer-Timo},
title = {A Spectral Approach for the Design of Experiments: Design, Analysis and Algorithms},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {This paper proposes a new approach to construct high quality space-filling sample designs. First, we propose a novel technique to quantify the space-filling property and optimally trade-off uniformity and randomness in sample designs in arbitrary dimensions. Second, we connect the proposed metric (defined in the spatial domain) to the quality metric of the design performance (defined in the spectral domain). This connection serves as an analytic framework for evaluating the qualitative properties of space-filling designs in general. Using the theoretical insights provided by this spatial-spectral analysis, we derive the notion of optimal space-filling designs, which we refer to as space-filling spectral designs. Third, we propose an efficient estimator to evaluate the space-_lling properties of sample designs in arbitrary dimensions and use it to develop an optimization framework for generating high quality space-filling designs. Finally, we carry out a detailed performance comparison on two diffierent applications in varying dimensions: a) image reconstruction and b) surrogate modeling for several benchmark optimization functions and a physics simulation code for inertial con_nement fusion (ICF). Our results clearly evidence the superiority of the proposed space-filling designs over existing approaches, particularly in high dimensions.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1214–1259},
numpages = {46},
keywords = {space-filling, poisson-disk sampling, surrogate modeling, design of experiments, regression}
}

@article{10.5555/3291125.3291158,
author = {Gao, Chao},
title = {Goodness-of-Fit Tests for Random Partitions via Symmetric Polynomials},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We consider goodness-of-fit tests with i.i.d. samples generated from a categorical distribution (p1,..., pk). For a given (q1,..., qk), we test the null hypothesis whether pj = qπ(j) for some label permutation π. The uncertainty of label permutation implies that the null hypothesis is composite instead of being singular. In this paper, we construct a testing procedure using statistics that are defined as indefinite integrals of some symmetric polynomials. This method is aimed directly at the invariance of the problem, and avoids the need of matching the unknown labels. The asymptotic distribution of the testing statistic is shown to be chi-squared, and its power is proved to be nearly optimal under a local alternative hypothesis. Various degenerate structures of the null hypothesis are carefully analyzed in the paper. A two-sample version of the test is also studied.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1164–1213},
numpages = {50},
keywords = {minimax optimality, Vandermonde matrix, elementary symmetric polynomials, Lagrange interpolating polynomials, hypothesis testing}
}

@article{10.5555/3291125.3291157,
author = {Shamir, Ohad},
title = {Distribution-Specific Hardness of Learning Neural Networks},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Although neural networks are routinely and successfully trained in practice using simple gradient-based methods, most existing theoretical results are negative, showing that learning such networks is difficult, in a worst-case sense over all data distributions. In this paper, we take a more nuanced view, and consider whether specific assumptions on the "niceness" of the input distribution, or "niceness" of the target function (e.g. in terms of smoothness, non-degeneracy, incoherence, random choice of parameters etc.), are sufficient to guarantee learnability using gradient-based methods. We provide evidence that neither class of assumptions alone is sufficient: On the one hand, for any member of a class of "nice" target functions, there are difficult input distributions. On the other hand, we identify a family of simple target functions, which are di_cult to learn even if the input distribution is "nice". To prove our results, we develop some tools which may be of independent interest, such as extending Fourier-based hardness techniques developed in the context of statistical queries (Blum et al., 1994), from the Boolean cube to Euclidean space and to more general classes of functions.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1135–1163},
numpages = {29},
keywords = {neural networks, distributional assumptions, computational hardness, gradient-based methods}
}

@article{10.5555/3291125.3291156,
author = {Jiang, Binyan and Wang, Xiangyu and Leng, Chenlei},
title = {A Direct Approach for Sparse Quadratic Discriminant Analysis},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Quadratic discriminant analysis (QDA) is a standard tool for classification due to its simplicity and exibility. Because the number of its parameters scales quadratically with the number of the variables, QDA is not practical, however, when the dimensionality is relatively large. To address this, we propose a novel procedure named DA-QDA for QDA in analyzing high-dimensional data. Formulated in a simple and coherent framework, DAQDA aims to directly estimate the key quantities in the Bayes discriminant function including quadratic interactions and a linear index of the variables for classification. Under appropriate sparsity assumptions, we establish consistency results for estimating the interactions and the linear index, and further demonstrate that the misclassification rate of our procedure converges to the optimal Bayes risk, even when the dimensionality is exponentially high with respect to the sample size. An efficient algorithm based on the alternating direction method of multipliers (ADMM) is developed for finding interactions, which is much faster than its competitor in the literature. The promising performance of DA-QDA is illustrated via extensive simulation studies and the analysis of four real datasets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1098–1134},
numpages = {37},
keywords = {consistency, high dimensional data, quadratic discriminant analysis, linear discriminant analysis, bayes risk, sparsity}
}

@article{10.5555/3291125.3291155,
author = {M\"{u}cke, Nicole and Blanchard, Gilles},
title = {Parallelizing Spectrally Regularized Kernel Algorithms},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We consider a distributed learning approach in supervised learning for a large class of spectral regularization methods in an reproducing kernel Hilbert space (RKHS) framework. The data set of size n is partitioned into m = O(nα), α < 1/2, disjoint subsamples. On each subsample, some spectral regularization method (belonging to a large class, including in particular Kernel Ridge Regression, L2-boosting and spectral cut-off) is applied. The regression function f is then estimated via simple averaging, leading to a substantial reduction in computation time. We show that minimax optimal rates of convergence are preserved if m grows sufficiently slowly (corresponding to an upper bound for α) as n → ∞, depending on the smoothness assumptions on f and the intrinsic dimensionality. In spirit, the analysis relies on a classical bias/stochastic error analysis.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1069–1097},
numpages = {29},
keywords = {spectral regularization, minimax optimality, distributed learning}
}

@article{10.5555/3291125.3291154,
author = {Hardt, Moritz and Ma, Tengyu and Recht, Benjamin},
title = {Gradient Descent Learns Linear Dynamical Systems},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We prove that stochastic gradient descent efficiently converges to the global optimizer of the maximum likelihood objective of an unknown linear time-invariant dynamical system from a sequence of noisy observations generated by the system. Even though the objective function is non-convex, we provide polynomial running time and sample complexity bounds under strong but natural assumptions. Linear systems identification has been studied for many decades, yet, to the best of our knowledge, these are the first polynomial guarantees for the problem we consider.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1025–1068},
numpages = {44},
keywords = {time series, non-convex optimization, generalization bounds, stochastic gradient descent, linear dynamical system, over-parameterization}
}

@article{10.5555/3291125.3291153,
author = {Khetan, Ashish and Oh, Sewoong},
title = {Generalized Rank-Breaking: Computational and Statistical Tradeoffs},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {For massive and heterogeneous modern datasets, it is of fundamental interest to provide guarantees on the accuracy of estimation when computational resources are limited. In the application of rank aggregation, for the Plackett-Luce model, we provide a hierarchy of rank-breaking mechanisms ordered by the complexity in thus generated sketch of the data. This allows the number of data points collected to be gracefully traded offs against computational resources available, while guaranteeing the desired level of accuracy. Theoretical guarantees on the proposed generalized rank-breaking implicitly provide such trade-offs, which can be explicitly characterized under certain canonical scenarios on the structure of the data. Further, the proposed generalized rank-breaking algorithm involves set-wise comparisons as opposed to traditional pairwise comparisons. The maximum likelihood estimate of pairwise comparisons is computed efficiently using the celebrated minorization maximization algorithm (Hunter, 2004). To compute the pseudo-maximum likelihood estimate of the set-wise comparisons, we provide a generalization of the minorization maximization algorithm and give guarantees on its convergence.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {983–1024},
numpages = {42},
keywords = {rank aggregation, Plackett-Luce model, sample and computational tradeoff}
}

@article{10.5555/3291125.3291152,
author = {Csiba, Dominik and Richt\'{a}rik, Peter},
title = {Importance Sampling for Minibatches},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Minibatching is a very well studied and highly popular technique in supervised learning, used by practitioners due to its ability to accelerate training through better utilization of parallel processing power and reduction of stochastic variance. Another popular technique is importance sampling--a strategy for preferential sampling of more important examples also capable of accelerating the training process. However, despite considerable effort by the community in these areas, and due to the inherent technical difficulty of the problem, there is virtually no existing work combining the power of importance sampling with the strength of minibatching. In this paper we propose the first practical importance sampling for minibatches and give simple and rigorous complexity analysis of its performance. We illustrate on synthetic problems that for training data of certain properties, our sampling can lead to several orders of magnitude improvement in training time. We then test the new sampling on several popular data sets, and show that the improvement can reach an order of magnitude.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {962–982},
numpages = {21},
keywords = {importance sampling, minibatching, variance-reduced methods, convex optimization, empirical risk minimization}
}

@article{10.5555/3291125.3291151,
author = {Ronan, Tom and Anastasio, Shawn and Qi, Zhijie and Sloutsky, Roman and Naegle, Kristen M. and Tavares, Pedro Henrique S. Vieira},
title = {Openensembles: A Python Resource for Ensemble Clustering},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {In this paper we introduce OpenEnsembles, a Python toolkit for performing and analyzing ensemble clustering. Ensemble clustering is the process of creating many clustering solutions for a given dataset and utilizing the relationships observed across the ensemble to identify final solutions, which are more robust, stable or better than the individual solutions within the ensemble. The OpenEnsembles library provides a unified interface for applying transformations to data, clustering data, visualizing individual clustering solutions, visualizing and finishing the ensemble, and calculating validation metrics for a clustering solution for any given partitioning of the data. We have documented examples of using OpenEnsembles to create, analyze, and visualize a number of different types of ensemble approaches on toy and example datasets. OpenEnsembles is released under the GNU General Public License version 3, can be installed via Conda or the Python Package Index (pip), and is available at https://github.com/NaegleLab/OpenEnsembles.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {956–961},
numpages = {6},
keywords = {unsupervised learning, clustering, ensembles, ensemble clustering, finishing Techniques}
}

@article{10.5555/3291125.3291150,
author = {Raissi, Maziar},
title = {Deep Hidden Physics Models: Deep Learning of Nonlinear Partial Differential Equations},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We put forth a deep learning approach for discovering nonlinear partial differential equations from scattered and potentially noisy observations in space and time. Specifically, we approximate the unknown solution as well as the nonlinear dynamics by two deep neural networks. The first network acts as a prior on the unknown solution and essentially enables us to avoid numerical differentiations which are inherently ill-conditioned and unstable. The second network represents the nonlinear dynamics and helps us distill the mechanisms that govern the evolution of a given spatiotemporal data-set. We test the effectiveness of our approach for several benchmark problems spanning a number of scientific domains and demonstrate how the proposed framework can help us accurately learn the underlying dynamics and forecast future states of the system. In particular, we study the Burgers', Korteweg-de Vries (KdV), Kuramoto-Sivashinsky, nonlinear Schr\"{o}dinger, and Navier-Stokes equations.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {932–955},
numpages = {24},
keywords = {systems identification, predictive modeling, data-driven scientific discovery, big data, physics informed machine learning, nonlinear dynamics}
}

@article{10.5555/3291125.3291149,
author = {Grigoryeva, Lyudmila and Ortega, Juan-Pablo},
title = {Universal Discrete-Time Reservoir Computers with Stochastic Inputs and Linear Readouts Using Non-Homogeneous State-Affine Systems},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {A new class of non-homogeneous state-affine systems is introduced for use in reservoir computing. Sufficient conditions are identified that guarantee first, that the associated reservoir computers with linear readouts are causal, time-invariant, and satisfy the fading memory property and second, that a subset of this class is universal in the category of fading memory filters with stochastic almost surely uniformly bounded inputs. This means that any discrete-time filter that satisfies the fading memory property with random inputs of that type can be uniformly approximated by elements in the non-homogeneous state-affine family.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {892–931},
numpages = {40},
keywords = {echo state affine systems, stochastic signal treatment, universality, linear training, fading memory property, machine learning, ESN, reservoir computing, state-affine systems, SAS, echo state networks}
}

@article{10.5555/3291125.3291148,
author = {Derezi\'{n}ski, Micha\l{} and Warmuth, Manfred K.},
title = {Reverse Iterative Volume Sampling for Linear Regression},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We study the following basic machine learning task: Given a fixed set of input points in ℝd for a linear regression problem, we wish to predict a hidden response value for each of the points. We can only afford to attain the responses for a small subset of the points that are then used to construct linear predictions for all points in the dataset. The performance of the predictions is evaluated by the total square loss on all responses (the attained as well as the remaining hidden ones). We show that a good approximate solution to this least squares problem can be obtained from just dimension d many responses by using a joint sampling technique called volume sampling. Moreover, the least squares solution obtained for the volume sampled subproblem is an unbiased estimator of optimal solution based on all n responses. This unbiasedness is a desirable property that is not shared by other common subset selection techniques.Motivated by these basic properties, we develop a theoretical framework for studying volume sampling, resulting in a number of new matrix expectation equalities and statistical guarantees which are of importance not only to least squares regression but also to numerical linear algebra in general. Our methods also lead to a regularized variant of volume sampling, and we propose the first efficient algorithm for volume sampling which makes this technique a practical tool in the machine learning toolbox. Finally, we provide experimental evidence which confirms our theoretical findings.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {853–891},
numpages = {39},
keywords = {optimal design, volume sampling, linear regression, row sampling, active learning}
}

@article{10.5555/3291125.3291147,
author = {Amjad, Muhammad and Shah, Devavrat and Shen, Dennis},
title = {Robust Synthetic Control},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We present a robust generalization of the synthetic control method for comparative case studies. Like the classical method cf. Abadie and Gardeazabal (2003), we present an algorithm to estimate the unobservable counterfactual of a treatment unit. A distinguishing feature of our algorithm is that of de-noising the data matrix via singular value thresholding, which renders our approach robust in multiple facets: it automatically identifies a good subset of donors for the synthetic control, overcomes the challenges of missing data, and continues to work well in settings where covariate information may not be provided. We posit that the setting can be viewed as an instance of the Latent Variable Model and provide the first finite sample analysis (coupled with asymptotic results) for the estimation of the counterfactual. Our algorithm accurately imputes missing entries and filters corrupted observations in producing a consistent estimator of the underlying signal matrix, provided p = Ω(T-1+ζ) for some ζ > 0; here, p is the fraction of observed data and T is the time interval of interest. Under the same proportion of observations, we demonstrate that the mean-squared error in our counterfactual estimation scales as O(σ2/p + 1/√T), where σ2 is the variance of the inherent noise. Additionally, we introduce a Bayesian framework to quantify the estimation uncertainty. Our experiments, using both synthetic and real-world datasets, demonstrate that our robust generalization yields an improvement over the classical synthetic control method.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {802–852},
numpages = {51},
keywords = {matrix estimation, observation studies, causal inference}
}

@article{10.5555/3291125.3291146,
author = {Wen, Zeyi and Shi, Jiashuai and Li, Qinbin and He, Bingsheng and Chen, Jian},
title = {ThunderSVM: A Fast SVM Library on GPUs and CPUs},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Support Vector Machines (SVMs) are classic supervised learning models for classification, regression and distribution estimation. A survey conducted by Kaggle in 2017 shows that 26% of the data mining and machine learning practitioners are users of SVMs. However, SVM training and prediction are very expensive computationally for large and complex problems. This paper presents an efficient and open source SVM software toolkit called ThunderSVM which exploits the high-performance of Graphics Processing Units (GPUs) and multi-core CPUs. ThunderSVM supports all the functionalities--including classification (SVC), regression (SVR) and one-class SVMs--of LibSVM and uses identical command line options, such that existing LibSVM users can easily apply our toolkit. ThunderSVM can be used through multiple language interfaces including C/C++, Python, R and MATLAB. Our experimental results show that ThunderSVM is generally an order of magnitude faster than LibSVM while producing identical SVMs. In addition to the high efficiency, we design our convex optimization solver in a general way such that SVC, SVR, and one-class SVMs share the same solver for the ease of maintenance. Documentation, examples, and more about ThunderSVM are available at https://github.com/zeyiwen/thundersvm.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {797–801},
numpages = {5},
keywords = {SVMs, efficiency, multi-core CPUs, multiple interfaces, GPUs}
}

@article{10.5555/3291125.3291145,
author = {Lattimore, Tor},
title = {Refining the Confidence Level for Optimistic Bandit Strategies},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {This paper introduces the first strategy for stochastic bandits with unit variance Gaussian noise that is simultaneously minimax optimal up to constant factors, asymptotically optimal, and never worse than the classical upper confidence bound strategy up to universal constant factors. Preliminary empirical evidence is also promising. Besides this, a conjecture on the optimal form of the regret is shown to be false and a finite-time lower bound on the regret of any strategy is presented that very nearly matches the finite-time upper bound of the newly proposed strategy.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {765–796},
numpages = {32},
keywords = {sequential decision making, stochastic bandits, regret minimisation}
}

@article{10.5555/3291125.3291144,
author = {Zhou, Yi and Liang, Yingbin and Yu, Yaoliang and Dai, Wei and Xing, Eric P.},
title = {Distributed Proximal Gradient Algorithm for Partially Asynchronous Computer Clusters},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {With ever growing data volume and model size, an error-tolerant, communication efficient, yet versatile distributed algorithm has become vital for the success of many large-scale machine learning applications. In this work we propose m-PAPG, an implementation of the flexible proximal gradient algorithm in model parallel systems equipped with the partially asynchronous communication protocol. The worker machines communicate asynchronously with a controlled staleness bound s and operate at different frequencies. We characterize various convergence properties of m-PAPG: 1) Under a general non-smooth and nonconvex setting, we prove that every limit point of the sequence generated by m-PAPG is a critical point of the objective function; 2) Under an error bound condition of convex objective functions, we prove that the optimality gap decays linearly for every s steps; 3) Under the Kurdyka-undefinedojasiewicz inequality and a sufficient decrease assumption, we prove that the sequences generated by m-PAPG converge to the same critical point, provided that a proximal Lipschitz condition is satisfied.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {733–764},
numpages = {32},
keywords = {model parallel, partially asynchronous, machine learning, proximal gradient, distributed system}
}

@article{10.5555/3291125.3291143,
author = {Tsakiris, Manolis C. and Vidal, Ren\'{e}},
title = {Dual Principal Component Pursuit},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of learning a linear subspace from data corrupted by outliers. Classical approaches are typically designed for the case in which the subspace dimension is small relative to the ambient dimension. Our approach works with a dual representation of the subspace and hence aims to find its orthogonal complement; as such, it is particularly suitable for subspaces whose dimension is close to the ambient dimension (subspaces of high relative dimension). We pose the problem of computing normal vectors to the inlier subspace as a non-convex l1 minimization problem on the sphere, which we call Dual Principal Component Pursuit (DPCP) problem. We provide theoretical guarantees under which every global solution to DPCP is a vector in the orthogonal complement of the inlier subspace. Moreover, we relax the non-convex DPCP problem to a recursion of linear programs whose solutions are shown to converge in a finite number of steps to a vector orthogonal to the subspace. In particular, when the inlier subspace is a hyperplane, the solutions to the recursion of linear programs converge to the global minimum of the nonconvex DPCP problem in a finite number of steps. We also propose algorithms based on alternating minimization and iteratively re-weighted least squares, which are suitable for dealing with large-scale data. Experiments on synthetic data show that the proposed methods are able to handle more outliers and higher relative dimensions than current state-of-the-art methods, while experiments in the context of the three-view geometry problem in computer vision suggest that the proposed methods can be a useful or even superior alternative to traditional RANSAC-based approaches for computer vision and other applications.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {684–732},
numpages = {49},
keywords = {robust principal component analysis, outliers, linear programming, l1 minimization, non-convex optimization, trifocal tensor, high relative dimension}
}

@article{10.5555/3291125.3291142,
author = {Durand, Audrey and Maillard, Odalric-Ambrym and Pineau, Joelle},
title = {Streaming Kernel Regression with Provably Adaptive Mean, Variance, and Regularization},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of streaming kernel regression, when the observations arrive sequentially and the goal is to recover the underlying mean function, assumed to belong to an RKHS. The variance of the noise is not assumed to be known. In this context, we tackle the problem of tuning the regularization parameter adaptively at each time step, while maintaining tight confidence bounds estimates on the value of the mean function at each point. To this end, we first generalize existing results for finite-dimensional linear regression with fixed regularization and known variance to the kernel setup with a regularization parameter allowed to be a measurable function of past observations. Then, using appropriate self-normalized inequalities we build upper and lower bound estimates for the variance, leading to Bernstein-like concentration bounds. The latter is used in order to define the adaptive regularization. The bounds resulting from our technique are valid uniformly over all observation points and all time steps, and are compared against the literature with numerical experiments. Finally, the potential of these tools is illustrated by an application to kernelized bandits, where we revisit the Kernel UCB and Kernel Thompson Sampling procedures, and show the benefits of the novel adaptive kernel tuning strategy.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {650–683},
numpages = {34},
keywords = {adaptive tuning, kernel, regression, online learning, bandits}
}

@article{10.5555/3291125.3291141,
author = {Lintusaari, Jarno and Vuollekoski, Henri and Kangasr\"{a}\"{a}si\"{o}, Antti and Skyt\'{e}n, Kusti and J\"{a}rvenp\"{a}\"{a}, Marko and Marttinen, Pekka and Gutmann, Michael U. and Vehtari, Aki and Corander, Jukka and Kaski, Samuel},
title = {ELFI: Engine for Likelihood-Free Inference},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Engine for Likelihood-Free Inference (ELFI) is a Python software library for performing likelihood-free inference (LFI). ELFI provides a convenient syntax for arranging components in LFI, such as priors, simulators, summaries or distances, to a network called ELFI graph. The components can be implemented in a wide variety of languages. The stand-alone ELFI graph can be used with any of the available inference methods without modifications. A central method implemented in ELFI is Bayesian Optimization for Likelihood-Free Inference (BOLFI), which has recently been shown to accelerate likelihood-free inference up to several orders of magnitude by surrogate-modelling the distance. ELFI also has an inbuilt support for output data storing for reuse and analysis, and supports parallelization of computation from multiple cores up to a cluster environment. ELFI is designed to be extensible and provides interfaces for widening its functionality. This makes the adding of new inference methods to ELFI straightforward and automatically compatible with the inbuilt features.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {643–649},
numpages = {7},
keywords = {approximate Bayesian computation, likelihood-free inference, python, BOLFI, parallel computing}
}

@article{10.5555/3291125.3291140,
author = {Dessein, Arnaud and Papadakis, Nicolas and Rouas, Jean-Luc},
title = {Regularized Optimal Transport and the Rot Mover's Distance},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {This paper presents a unified framework for smooth convex regularization of discrete optimal transport problems. In this context, the regularized optimal transport turns out to be equivalent to a matrix nearness problem with respect to Bregman divergences. Our framework thus naturally generalizes a previously proposed regularization based on the Boltzmann-Shannon entropy related to the Kullback-Leibler divergence, and solved with the Sinkhorn-Knopp algorithm. We call the regularized optimal transport distance the rot mover's distance in reference to the classical earth mover's distance. By exploiting alternate Bregman projections, we develop the alternate scaling algorithm and non-negative alternate scaling algorithm, to compute efficiently the regularized optimal plans depending on whether the domain of the regularizer lies within the non-negative orthant or not. We further enhance the separable case with a sparse extension to deal with high data dimensions. We also instantiate our framework and discuss the inherent specificities for well-known regularizers and statistical divergences in the machine learning and information geometry communities. Finally, we demonstrate the merits of our methods with experiments using synthetic data to illustrate the effect of different regularizers, penalties and dimensions, as well as real-world data for a pattern recognition application to audio scene classification.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {590–642},
numpages = {53},
keywords = {rot mover's distance, convex analysis, statistical divergences, alternate projections, regularized optimal transport}
}

@article{10.5555/3291125.3291139,
author = {Akrour, Riad and Abdolmaleki, Abbas and Abdulsamad, Hany and Peters, Jan and Neumann, Gerhard},
title = {Model-Free Trajectory-Based Policy Optimization with Monotonic Improvement},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Many of the recent trajectory optimization algorithms alternate between linear approximation of the system dynamics around the mean trajectory and conservative policy update. One way of constraining the policy change is by bounding the Kullback-Leibler (KL) divergence between successive policies. These approaches already demonstrated great experimental success in challenging problems such as end-to-end control of physical systems. However, the linear approximation of the system dynamics can introduce a bias in the policy update and prevent convergence to the optimal policy. In this article, we propose a new model-free trajectory-based policy optimization algorithm with guaranteed monotonic improvement. The algorithm backpropagates a local, quadratic and time-dependent Q-Function learned from trajectory data instead of a model of the system dynamics. Our policy update ensures exact KL-constraint satisfaction without simplifying assumptions on the system dynamics. We experimentally demonstrate on highly non-linear control tasks the improvement in performance of our algorithm in comparison to approaches linearizing the system dynamics. In order to show the monotonic improvement of our algorithm, we additionally conduct a theoretical analysis of our policy update scheme to derive a lower bound of the change in policy return between successive iterations.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {565–589},
numpages = {25},
keywords = {robotics, reinforcement learning, trajectory optimization, policy optimization}
}

@article{10.5555/3291125.3291138,
author = {Chen, Ruidi and Paschalidis, Ioannis Ch.},
title = {A Robust Learning Approach for Regression Models Based on Distributionally Robust Optimization},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We present a Distributionally Robust Optimization (DRO) approach to estimate a robustified regression plane in a linear regression setting, when the observed samples are potentially contaminated with adversarially corrupted outliers. Our approach mitigates the impact of outliers by hedging against a family of probability distributions on the observed data, some of which assign very low probabilities to the outliers. The set of distributions under consideration are close to the empirical distribution in the sense of the Wasserstein metric. We show that this DRO formulation can be relaxed to a convex optimization problem which encompasses a class of models. By selecting proper norm spaces for the Wasserstein metric, we are able to recover several commonly used regularized regression models. We provide new insights into the regularization term and give guidance on the selection of the regularization coefficient from the standpoint of a confidence region. We establish two types of performance guarantees for the solution to our formulation under mild conditions. One is related to its out-of-sample behavior (prediction bias), and the other concerns the discrepancy between the estimated and true regression planes (estimation bias). Extensive numerical results demonstrate the superiority of our approach to a host of regression models, in terms of the prediction and estimation accuracies. We also consider the application of our robust learning procedure to outlier detection, and show that our approach achieves a much higher AUC (Area Under the ROC Curve) than M-estimation (Huber, 1964, 1973).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {517–564},
numpages = {48},
keywords = {distributionally robust optimization, robust learning, generalization guarantees, wasserstein metric, regularized regression}
}

@article{10.5555/3291125.3291137,
author = {Carri\`{e}re, Mathieu and Michel, Bertrand and Oudot, Steve},
title = {Statistical Analysis and Parameter Selection for Mapper},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {In this article, we study the question of the statistical convergence of the 1-dimensional Mapper to its continuous analogue, the Reeb graph. We show that the Mapper is an optimal estimator of the Reeb graph, which gives, as a byproduct, a method to automatically tune its parameters and compute confidence regions on its topological features, such as its loops and ares. This allows to circumvent the issue of testing a large grid of parameters and keeping the most stable ones in the brute-force setting, which is widely used in visualization, clustering and feature selection with the Mapper.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {478–516},
numpages = {39},
keywords = {topological data analysis, extended persistence, parameter selection, confidence regions, mapper}
}

@article{10.5555/3291125.3291136,
author = {Bybee, Leland and Atchad\'{e}, Yves},
title = {Change-Point Computation for Large Graphical Models: A Scalable Algorithm for Gaussian Graphical Models with Change-Points},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Graphical models with change-points are computationally challenging to fit, particularly in cases where the number of observation points and the number of nodes in the graph are large. Focusing on Gaussian graphical models, we introduce an approximate majorizeminimize (MM) algorithm that can be useful for computing change-points in large graphical models. The proposed algorithm is an order of magnitude faster than a brute force search. Under some regularity conditions on the data generating process, we show that with high probability, the algorithm converges to a value that is within statistical error of the true change-point. A fast implementation of the algorithm using Markov Chain Monte Carlo is also introduced. The performances of the proposed algorithms are evaluated on synthetic data sets and the algorithm is also used to analyze structural changes in the S&P 500 over the period 2000-2016.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {440–477},
numpages = {38},
keywords = {proximal gradient, Gaussian graphical models, simulated annealing, change-points, stochastic optimization}
}

@article{10.5555/3291125.3291135,
author = {Huang, Jian and Jiao, Yuling and Liu, Yanyan and Lu, Xiliang},
title = {A Constructive Approach to L<sub>0</sub> Penalized Regression},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We propose a constructive approach to estimating sparse, high-dimensional linear regression models. The approach is a computational algorithm motivated from the KKT conditions for the l0-penalized least squares solutions. It generates a sequence of solutions iteratively, based on support detection using primal and dual information and root finding. We refer to the algorithm as SDAR for brevity. Under a sparse Riesz condition on the design matrix and certain other conditions, we show that with high probability, the l2 estimation error of the solution sequence decays exponentially to the minimax error bound in O(log(Rp√J)) iterations, where J is the number of important predictors and R is the relative magnitude of the nonzero target coefficients; and under a mutual coherence condition and certain other conditions, the l∞ estimation error decays to the optimal error bound in O(log(R)) iterations. Moreover the SDAR solution recovers the oracle least squares estimator within a finite number of iterations with high probability if the sparsity level is known. Computational complexity analysis shows that the cost of SDAR is O(np) per iteration. We also consider an adaptive version of SDAR for use in practical applications where the true sparsity level is unknown. Simulation studies demonstrate that SDAR outperforms Lasso, MCP and two greedy methods in accuracy and efficiency.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {403–439},
numpages = {37},
keywords = {geometrical convergence, root finding, nonasymptotic error bounds, support detection, KKT conditions, oracle property}
}

@article{10.5555/3291125.3291134,
author = {De Bruin, Tim and Kober, Jens and Tuyls, Karl and Babu\v{s}ka, Robert},
title = {Experience Selection in Deep Reinforcement Learning for Control},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Experience replay is a technique that allows off-policy reinforcement-learning methods to reuse past experiences. The stability and speed of convergence of reinforcement learning, as well as the eventual performance of the learned policy, are strongly dependent on the experiences being replayed. Which experiences are replayed depends on two important choices. The first is which and how many experiences to retain in the experience replay buffer. The second choice is how to sample the experiences that are to be replayed from that buffer. We propose new methods for the combined problem of experience retention and experience sampling. We refer to the combination as experience selection. We focus our investigation specifically on the control of physical systems, such as robots, where exploration is costly. To determine which experiences to keep and which to replay, we investigate different proxies for their immediate and long-term utility. These proxies include age, temporal difference error and the strength of the applied exploration noise. Since no currently available method works in all situations, we propose guidelines for using prior knowledge about the characteristics of the control problem at hand to choose the appropriate experience replay strategy.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {347–402},
numpages = {56},
keywords = {reinforcement learning, control, experience replay, deep learning, robotics}
}

@article{10.5555/3291125.3291133,
author = {Srivastava, Sanvesh and Li, Cheng and Dunson, David B.},
title = {Scalable Bayes via Barycenter in Wasserstein Space},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Divide-and-conquer based methods for Bayesian inference provide a general approach for tractable posterior inference when the sample size is large. These methods divide the data into smaller subsets, sample from the posterior distribution of parameters in parallel on all the subsets, and combine posterior samples from all the subsets to approximate the full data posterior distribution. The smaller size of any subset compared to the full data implies that posterior sampling on any subset is computationally more efficient than sampling from the true posterior distribution. Since the combination step takes negligible time relative to sampling, posterior computations can be scaled to massive data by dividing the full data into sufficiently large number of data subsets. One such approach relies on the geometry of posterior distributions estimated across different subsets and combines them through their barycenter in a Wasserstein space of probability measures. We provide theoretical guarantees on the accuracy of approximation that are valid in many applications. We show that the geometric method approximates the full data posterior distribution better than its competitors across diverse simulations and reproduces known results when applied to a movie ratings database.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {312–346},
numpages = {35},
keywords = {big data, distributed Bayesian computations, empirical measures, barycenter, linear programming, Wasserstein distance, Wasserstein space, optimal transportation}
}

@article{10.5555/3291125.3291132,
author = {Park, Chiwoo and Apley, Daniel},
title = {Patchwork Kriging for Large-Scale Gaussian Process Regression},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {This paper presents a new approach for Gaussian process (GP) regression for large datasets. The approach involves partitioning the regression input domain into multiple local regions with a different local GP model fitted in each region. Unlike existing local partitioned GP approaches, we introduce a technique for patching together the local GP models nearly seamlessly to ensure that the local GP models for two neighboring regions produce nearly the same response prediction and prediction error variance on the boundary between the two regions. This largely mitigates the well-known discontinuity problem that degrades the prediction accuracy of existing local partitioned GP methods over regional boundaries. Our main innovation is to represent the continuity conditions as additional pseudoobservations that the differences between neighboring GP responses are identically zero at an appropriately chosen set of boundary input locations. To predict the response at any input location, we simply augment the actual response observations with the pseudo-observations and apply standard GP prediction methods to the augmented data. In contrast to heuristic continuity adjustments, this has an advantage of working within a formal GP framework, so that the GP-based predictive uncertainty quantification remains valid. Our approach also inherits a sparse block-like structure for the sample covariance matrix, which results in computationally efficient closed-form expressions for the predictive mean and variance. In addition, we provide a new spatial partitioning scheme based on a recursive space partitioning along local principal component directions, which makes the proposed approach applicable for regression domains having more than two dimensions. Using three spatial datasets and three higher dimensional datasets, we investigate the numerical performance of the approach and compare it to several state-of-the-art approaches.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {269–311},
numpages = {43},
keywords = {local kriging, pseudo observations, spatial partition, model split and merge}
}

@article{10.5555/3291125.3291131,
author = {Yang, Tianbao and Lin, Qihang},
title = {RSG: Beating Subgradient Method without Smoothness and Strong Convexity},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {In this paper, we study the efficiency of a Restarted SubGradient (RSG) method that periodically restarts the standard subgradient method (SG). We show that, when applied to a broad class of convex optimization problems, RSG method can find an ε-optimal solution with a lower complexity than the SG method. In particular, we first show that RSG can reduce the dependence of SG's iteration complexity on the distance between the initial solution and the optimal set to that between the ε-level set and the optimal set multiplied by a logarithmic factor. Moreover, we show the advantages of RSG over SG in solving a broad family of problems that satisfy a local error bound condition, and also demonstrate its advantages for three specific families of convex optimization problems with di_erent power constants in the local error bound condition. (a) For the problems whose epigraph is a polyhedron, RSG is shown to converge linearly. (b) For the problems with local quadratic growth property in the ε-sublevel set, RSG has an O(1/ε log(1/ε)) iteration complexity. (c) For the problems that admit a local Kurdyka-undefinedojasiewicz property with a power constant of β∈ 2 [0; 1), RSG has an O(1/ε2β log(1/ε)) iteration complexity. The novelty of our analysis lies at exploiting the lower bound of the first-order optimality residual at the ε-level set. It is this novelty that allows us to explore the local properties of functions (e.g., local quadratic growth property, local Kurdyka-undefinedojasiewicz property, more generally local error bound conditions) to develop the improved convergence of RSG. We also develop a practical variant of RSG enjoying faster convergence than the SG method, which can be run without knowing the involved parameters in the local error bound condition. We demonstrate the effectiveness of the proposed algorithms on several machine learning tasks including regression, classification and matrix completion.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {236–268},
numpages = {33},
keywords = {local error bound, subgradient method, improved convergence, machine learning}
}

@article{10.5555/3291125.3291130,
author = {El Karoui, Noureddine and Purdom, Elizabeth},
title = {Can We Trust the Bootstrap in High-Dimensions? The Case of Linear Models},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We consider the performance of the bootstrap in high-dimensions for the setting of linear regression, where p < n but p/n is not close to zero. We consider ordinary least-squares as well as robust regression methods and adopt a minimalist performance requirement: can the bootstrap give us good confidence intervals for a single coordinate of β (where β is the true regression vector)?We show through a mix of numerical and theoretical work that the bootstrap is fraught with problems. Both of the most commonly used methods of bootstrapping for regression-- residual bootstrap and pairs bootstrap--give very poor inference on β as the ratio p/n grows. We find that the residual bootstrap tend to give anti-conservative estimates (inflated Type I error), while the pairs bootstrap gives very conservative estimates (severe loss of power) as the ratio p/n grows. We also show that the jackknife resampling technique for estimating the variance of β severely overestimates the variance in high dimensions.We contribute alternative procedures based on our theoretical results that result in dimensionality adaptive and robust bootstrap methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {170–235},
numpages = {66},
keywords = {bootstrap, high-dimensional inference, resampling, random matrices}
}

@article{10.5555/3291125.3291129,
author = {Alaa, Ahmed M. and Van Der Schaar, Mihaela},
title = {A Hidden Absorbing Semi-Markov Model for Informatively Censored Temporal Data: Learning and Inference},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Modeling continuous-time physiological processes that manifest a patient's evolving clinical states is a key step in approaching many problems in healthcare. In this paper, we develop the Hidden Absorbing Semi-Markov Model (HASMM): a versatile probabilistic model that is capable of capturing the modern electronic health record (EHR) data. Unlike existing models, the HASMM accommodates irregularly sampled, temporally correlated, and informatively censored physiological data, and can describe non-stationary clinical state transitions. Learning the HASMM parameters from the EHR data is achieved via a novel forward-filtering backward-sampling Monte-Carlo EM algorithm that exploits the knowledge of the end-point clinical outcomes (informative censoring) in the EHR data, and implements the E-step by sequentially sampling the patients' clinical states in the reverse-time direction while conditioning on the future states. Real-time inferences are drawn via a forward-filtering algorithm that operates on a virtually constructed discrete-time embedded Markov chain that mirrors the patient's continuous-time state trajectory. We demonstrate the prognostic utility of the HASMM in a critical care prognosis setting using a real-world dataset for patients admitted to the Ronald Reagan UCLA Medical Center. In particular, we show that using HASMMs, a patient's clinical deterioration can be predicted 8-9 hours prior to intensive care unit admission, with a 22% AUC gain compared to the Rothman index, which is the state-of-the-art critical care risk scoring technology.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {108–169},
numpages = {62},
keywords = {medical informatics, Monte Carlo methods, hidden semi-markov models}
}

@article{10.5555/3291125.3291128,
author = {Das, Abhimanyu and Kempe, David},
title = {Approximate Submodularity and Its Applications: Subset Selection, Sparse Approximation and Dictionary Selection},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We introduce the submodularity ratio as a measure of how "close" to submodular a set function f is. We show that when f has submodularity ratio γ, the greedy algorithm for maximizing f provides a (1 - e-γ)-approximation. Furthermore, when γ is bounded away from 0, the greedy algorithm for minimum submodular cover also provides essentially an O(log n) approximation for a universe of n elements.As a main application of this framework, we study the problem of selecting a subset of k random variables from a large set, in order to obtain the best linear prediction of another variable of interest. We analyze the performance of widely used greedy heuristics; in particular, by showing that the submodularity ratio is lower-bounded by the smallest 2k- sparse eigenvalue of the covariance matrix, we obtain the strongest known approximation guarantees for the Forward Regression and Orthogonal Matching Pursuit algorithms.As a second application, we analyze greedy algorithms for the dictionary selection problem, and significantly improve the previously known guarantees. Our theoretical analysis is complemented by experiments on real-world and synthetic data sets; in particular, we focus on an analysis of how tight various spectral parameters and the submodularity ratio are in terms of predicting the performance of the greedy algorithms.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {74–107},
numpages = {34}
}

@article{10.5555/3291125.3291127,
author = {Chen, Chen and Ren, Min and Zhang, Min and Zhang, Dabao},
title = {A Two-Stage Penalized Least Squares Method for Constructing Large Systems of Structural Equations},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We propose a two-stage penalized least squares method to build large systems of structural equations based on the instrumental variables view of the classical two-stage least squares method. We show that, with large numbers of endogenous and exogenous variables, the system can be constructed via consistent estimation of a set of conditional expectations at the first stage, and consistent selection of regulatory effects at the second stage. While the consistent estimation at the first stage can be obtained via the ridge regression, the adaptive lasso is employed at the second stage to achieve the consistent selection. This method is computationally fast and allows for parallel implementation. We demonstrate its effectiveness via simulation studies and real data analysis.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {40–73},
numpages = {34},
keywords = {graphical model, structural equation model, simultaneous equation model, reciprocal graphical model, high-dimensional data}
}

@article{10.5555/3291125.3291126,
author = {Guo, Weili and Wei, Haikun and Ong, Yew-Soon and Hervas, Jaime Rubio and Zhao, Junsheng and Wang, Hai and Zhang, Kanjian},
title = {Numerical Analysis near Singularities in RBF Networks},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {The existence of singularities often affects the learning dynamics in feedforward neural networks. In this paper, based on theoretical analysis results, we numerically analyze the learning dynamics of radial basis function (RBF) networks near singularities to understand to what extent singularities influence the learning dynamics. First, we show the explicit expression of the Fisher information matrix for RBF networks. Second, we demonstrate through numerical simulations that the singularities have a significant impact on the learning dynamics of RBF networks. Our results show that overlap singularities mainly have influence on the low dimensional RBF networks and elimination singularities have a more significant impact to the learning processes than overlap singularities in both low and high dimensional RBF networks, whereas the plateau phenomena are mainly caused by the elimination singularities. The results can also be the foundation to investigate the singular learning dynamics in deep feedforward neural networks.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1–39},
numpages = {39},
keywords = {numerical analysis, learning dynamics, deep learning, RBF networks, singularity}
}

@article{10.5555/3122009.3290419,
author = {Angelino, Elaine and Larus-Stone, Nicholas and Alabi, Daniel and Seltzer, Margo and Rudin, Cynthia},
title = {Learning Certifiably Optimal Rule Lists for Categorical Data},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We present the design and implementation of a custom discrete optimization technique for building rule lists over a categorical feature space. Our algorithm produces rule lists with optimal training performance, according to the regularized empirical risk, with a certificate of optimality. By leveraging algorithmic bounds, efficient data structures, and computational reuse, we achieve several orders of magnitude speedup in time and a massive reduction of memory consumption. We demonstrate that our approach produces optimal rule lists on practical problems in seconds. Our results indicate that it is possible to construct optimal sparse rule lists that are approximately as accurate as the COMPAS proprietary risk prediction tool on data from Broward County, Florida, but that are completely interpretable. This framework is a novel alternative to CART and other decision tree methods for interpretable modeling.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8753–8830},
numpages = {78},
keywords = {optimization, decision trees, rule lists, interpretable models, criminal justice applications}
}

@article{10.5555/3122009.3290418,
author = {Szab\'{o}, Zolt\'{a}n and Sriperumbudur, Bharath K.},
title = {Characteristic and Universal Tensor Product Kernels},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Maximum mean discrepancy (MMD), also called energy distance or N-distance in statistics and Hilbert-Schmidt independence criterion (HSIC), specifically distance covariance in statistics, are among the most popular and successful approaches to quantify the difference and independence of random variables, respectively. Thanks to their kernel-based foundations, MMD and HSIC are applicable on a wide variety of domains. Despite their tremendous success, quite little is known about when HSIC characterizes independence and when MMD with tensor product kernel can discriminate probability distributions. In this paper, we answer these questions by studying various notions of characteristic property of the tensor product kernel.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8724–8752},
numpages = {29},
keywords = {tensor product kernel, universality, maximum mean discrepancy, characteristic kernel, kernel mean embedding, I-characteristic kernel, hilbert-schmidt independence criterion}
}

@article{10.5555/3122009.3290417,
author = {Price, Bradley S. and Sherwood, Ben},
title = {A Cluster Elastic Net for Multivariate Regression},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We propose a method for simultaneously estimating regression coefficients and clustering response variables in a multivariate regression model, to increase prediction accuracy and give insights into the relationship between response variables. The estimates of the regression coefficients and clusters are found by using a penalized likelihood estimator, which includes a cluster fusion penalty, to shrink the difference in fitted values from responses in the same cluster, and an L1 penalty for simultaneous variable selection and estimation. We propose a two-step algorithm, that iterates between k-means clustering and solving the penalized likelihood function assuming the clusters are known, which has desirable parallel computational properties obtained by using the cluster fusion penalty. If the response variable clusters are known a priori then the algorithm reduces to just solving the penalized likelihood problem. Theoretical results are presented for the penalized least squares case, including asymptotic results allowing for p ≫ n. We extend our method to the setting where the responses are binomial variables. We propose a coordinate descent algorithm for the normal likelihood and a proximal gradient descent algorithm for the binomial likelihood, which can easily be extended to other generalized linear model (GLM) settings. Simulations and data examples from business operations and genomics are presented to show the merits of both the least squares and binomial methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8685–8723},
numpages = {39},
keywords = {fusion penalty, clustering, multivariate regression}
}

@article{10.5555/3122009.3290416,
author = {Chen, Likai and Wu, Wei Biao},
title = {Concentration Inequalities for Empirical Processes of Linear Time Series},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {The paper considers suprema of empirical processes for linear time series indexed by functional classes. We derive an upper bound for the tail probability of the suprema under conditions on the size of the function class, the sample size, temporal dependence and the moment conditions of the underlying time series. Due to the dependence and heavy-tailness, our tail probability bound is substantially different from those classical exponential bounds obtained under the independence assumption in that it involves an extra polynomial decaying term. We allow both short- and long-range dependent processes. For empirical processes indexed by half intervals, our tail probability inequality is sharp up to a multiplicative constant.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8639–8684},
numpages = {46},
keywords = {tail probability, martingale decomposition, heavy tail, MA(∞)}
}

@article{10.5555/3122009.3290415,
author = {Smith, Virginia and Forte, Simone and Ma, Chenxin and Tak\'{a}\v{c}, Martin and Jordan, Michael I. and Jaggi, Martin},
title = {CoCoA: A General Framework for Communication-Efficient Distributed Optimization},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {The scale of modern datasets necessitates the development of efficient distributed optimization methods for machine learning. We present a general-purpose framework for distributed computing environments, CoCoA, that has an efficient communication scheme and is applicable to a wide variety of problems in machine learning and signal processing. We extend the framework to cover general non-strongly-convex regularizers, including L1-regularized problems like lasso, sparse logistic regression, and elastic net regularization, and show how earlier work can be derived as a special case. We provide convergence guarantees for the class of convex regularized loss minimization objectives, leveraging a novel approach in handling non-strongly-convex regularizers and non-smooth loss functions. The resulting framework has markedly improved performance over state-of-the-art methods, as we illustrate with an extensive set of experiments on real distributed datasets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8590–8638},
numpages = {49},
keywords = {large-scale machine learning, parallel and distributed algorithms, convex optimization, distributed systems}
}

@article{10.5555/3122009.3290414,
author = {Sabato, Sivan and Hess, Tom},
title = {Interactive Algorithms: Pool, Stream and Precognitive Stream},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We consider interactive algorithms in the pool-based setting, and in the stream-based setting. Interactive algorithms observe suggested elements (representing actions or queries), and interactively select some of them and receive responses. Pool-based algorithms can select elements at any order, while stream-based algorithms observe elements in sequence, and can only select elements immediately after observing them. We further consider an intermediate setting, which we term precognitive stream, in which the algorithm knows in advance the identity of all the elements in the sequence, but can select them only in the order of their appearance. For all settings, we assume that the suggested elements are generated independently from some source distribution, and ask what is the stream size required for emulating a pool algorithm with a given pool size, in the stream-based setting and in the precognitive stream setting. We provide algorithms and matching lower bounds for general pool algorithms, and for utility-based pool algorithms. We further derive nearly matching upper and lower bounds on the gap between the two settings for the special case of active learning for binary classification.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8551–8589},
numpages = {39},
keywords = {stream-based, pool-based, interactive algorithms, active learning}
}

@article{10.5555/3122009.3290413,
author = {Van Rooyen, Brendan and Williamson, Robert C.},
title = {A Theory of Learning with Corrupted Labels},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {It is usual in machine learning theory to assume that the training and testing sets comprise of draws from the same distribution. This is rarely, if ever, true and one must admit the presence of corruption. There are many different types of corruption that can arise and as of yet there is no general means to compare the relative ease of learning in these settings. Such results are necessary if we are to make informed economic decisions regarding the acquisition of data.Here we begin to develop an abstract framework for tackling these problems. We present a generic method for learning from a fixed, known, reconstructible corruption, along with an analyses of its statistical properties. We demonstrate the utility of our framework via concrete novel results in solving supervised learning problems wherein the labels are corrupted, such as learning with noisy labels, semi-supervised learning and learning with partial labels.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8501–8550},
numpages = {50},
keywords = {noise, generalized supervision, data processing, minimax bounds, decision theory, supervised learning}
}

@article{10.5555/3122009.3242084,
author = {D\"{o}ring, Maik and Gy\"{o}rfi, L\'{a}szl\'{o} and Walk, Harro},
title = {Rate of Convergence of <i>k</i>-Nearest-Neighbor Classification Rule},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {A binary classification problem is considered. The excess error probability of the k-nearest-neighbor classification rule according to the error probability of the Bayes decision is revisited by a decomposition of the excess error probability into approximation and estimation errors. Under a weak margin condition and under a modified Lipschitz condition or a local Lipschitz condition, tight upper bounds are presented such that one avoids the condition that the feature vector is bounded. The concept of modified Lipschitz condition is applied for discrete distributions, too. As a consequence of both concepts, we present the rate of convergence of L2 error for the corresponding nearest neighbor regression estimate.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8485–8500},
numpages = {16},
keywords = {classification, k-nearest-neighbor rule, rate of convergence, error probability}
}

@article{10.5555/3122009.3242083,
author = {Athreya, Avanti and Fishkind, Donniell E. and Tang, Minh and Priebe, Carey E. and Park, Youngser and Vogelstein, Joshua T. and Levin, Keith and Lyzinski, Vince and Qin, Yichen},
title = {Statistical Inference on Random Dot Product Graphs: A Survey},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {The random dot product graph (RDPG) is an independent-edge random graph that is analytically tractable and, simultaneously, either encompasses or can successfully approximate a wide range of random graphs, from relatively simple stochastic block models to complex latent position graphs. In this survey paper, we describe a comprehensive paradigm for statistical inference on random dot product graphs, a paradigm centered on spectral embeddings of adjacency and Laplacian matrices. We examine the graph-inferential analogues of several canonical tenets of classical Euclidean inference. In particular, we summarize a body of existing results on the consistency and asymptotic normality of the adjacency and Laplacian spectral embeddings, and the role these spectral embeddings can play in the construction of single- and multi-sample hypothesis tests for graph data. We investigate several real-world applications, including community detection and classification in large social networks and the determination of functional and biologically relevant network properties from an exploratory data analysis of the Drosophila connectome. We outline requisite background and current open problems in spectral graph inference.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8393–8484},
numpages = {92},
keywords = {laplacian spectral embedding, adjacency spectral embedding, multi-sample graph hypothesis testing, random dot product graph, semiparametric modeling}
}

@article{10.5555/3122009.3242082,
author = {Ali, Hafiz Tiomoko and Couillet, Romain},
title = {Improved Spectral Community Detection in Large Heterogeneous Networks},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In this article, we propose and study the performance of spectral community detection for a family of "α-normalized" adjacency matrices A, of the type D-αAD-α with D the degree matrix, in heterogeneous dense graph models. We show that the previously used normalization methods based on A or D-1AD-1 are in general suboptimal in terms of correct recovery rates and, relying on advanced random matrix methods, we prove instead the existence of an optimal value αopt of the parameter α in our generic model; we further provide an online estimation of αopt only based on the node degrees in the graph. Numerical simulations show that the proposed method outperforms state-of-the-art spectral approaches on moderately dense to dense heterogeneous graphs.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8344–8392},
numpages = {49},
keywords = {community detection, random networks, spectral clustering, random matrix theory, heterogeneous graphs}
}

@article{10.5555/3122009.3242081,
author = {Park, Gunwoong and Raskutti, Garvesh},
title = {Learning Quadratic Variance Function (QVF) DAG Models via Overdispersion Scoring (ODS)},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Learning DAG or Bayesian network models is an important problem in multi-variate causal inference. However, a number of challenges arises in learning large-scale DAG models including model identifiability and computational complexity since the space of directed graphs is huge. In this paper, we address these issues in a number of steps for a broad class of DAG models where the noise or variance is signal-dependent. Firstly we introduce a new class of identifiable DAG models, where each node has a distribution where the variance is a quadratic function of the mean (QVF DAG models). Our QVF DAG models include many interesting classes of distributions such as Poisson, Binomial, Geometric, Exponential, Gamma and many other distributions in which the noise variance depends on the mean. We prove that this class of QVF DAG models is identifiable, and introduce a new algorithm, the OverDispersion Scoring (ODS) algorithm, for learning large-scale QVF DAG models. Our algorithm is based on firstly learning the moralized or undirected graphical model representation of the DAG to reduce the DAG search-space, and then exploiting the quadratic variance property to learn the ordering. We show through theoretical results and simulations that our algorithm is statistically consistent in the high-dimensional p > n setting provided that the degree of the moralized graph is bounded and performs well compared to state-of-the-art DAG-learning algorithms. We also demonstrate through a real data example involving multi-variate count data, that our ODS algorithm is wellsuited to estimating DAG models for count data in comparison to other methods used for discrete data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8300–8342},
numpages = {43},
keywords = {directed acyclic graph, overdispersion, Bayesian networks, multi-variate count distribution, identifiability}
}

@article{10.5555/3122009.3242080,
author = {Jain, Prateek and Netrapalli, Praneeth and Kakade, Sham M. and Kidambi, Rahul and Sidford, Aaron},
title = {Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-Batching, Averaging, and Model Misspecification},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {This work characterizes the benefits of averaging techniques widely used in conjunction with stochastic gradient descent (SGD). In particular, this work presents a sharp analysis of: (1) mini-batching, a method of averaging many samples of a stochastic gradient to both reduce the variance of a stochastic gradient estimate and for parallelizing SGD and (2) tail-averaging, a method involving averaging the final few iterates of SGD in order to decrease the variance in SGD's final iterate. This work presents sharp finite sample generalization error bounds for these schemes for the stochastic approximation problem of least squares regression.Furthermore, this work establishes a precise problem-dependent extent to which mini-batching can be used to yield provable near-linear parallelization speedups over SGD with batch size one. This characterization is used to understand the relationship between learning rate versus batch size when considering the excess risk of the final iterate of an SGD procedure. Next, this mini-batching characterization is utilized in providing a highly parallelizable SGD method that achieves the minimax risk with nearly the same number of serial updates as batch gradient descent, improving significantly over existing SGD-style methods. Following this, a non-asymptotic excess risk bound for model averaging (which is a communication efficient parallelization scheme) is provided.Finally, this work sheds light on fundamental differences in SGD's behavior when dealing with mis-specified models in the non-realizable least squares problem. This paper shows that maximal stepsizes ensuring minimax risk for the mis-specified case must depend on the noise properties.The analysis tools used by this paper generalize the operator view of averaged SGD (D\'{e}fossez and Bach, 2015) followed by developing a novel analysis in bounding these operators to characterize the generalization error. These techniques are of broader interest in analyzing various computational aspects of stochastic approximation.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8258–8299},
numpages = {42},
keywords = {batchsize doubling, parameter mixing, mini batch SGD, model averaging, agnostic learning, parallelization, suffix averaging, least squares regression, mis-specified models, stochastic gradient descent, heteroscedastic noise, iterate averaging, stochastic approximation}
}

@article{10.5555/3122009.3242079,
author = {Gonen, Alon and Shalev-Shwartz, Shai},
title = {Average Stability is Invariant to Data Preconditioning: Implications to Exp-Concave Empirical Risk Minimization},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We show that the average stability notion introduced by Kearns and Ron (1999); Bousquet and Elisseeff (2002) is invariant to data preconditioning, for a wide class of generalized linear models that includes most of the known exp-concave losses. In other words, when analyzing the stability rate of a given algorithm, we may assume the optimal preconditioning of the data. This implies that, at least from a statistical perspective, explicit regularization is not required in order to compensate for ill-conditioned data, which stands in contrast to a widely common approach that includes a regularization for analyzing the sample complexity of generalized linear models. Several important implications of our findings include: a) We demonstrate that the excess risk of empirical risk minimization (ERM) is controlled by the preconditioned stability rate. This immediately yields a relatively short and elegant proof for the fast rates attained by ERM in our context. b) We complement the recent bounds of Hardt et al. (2015) on the stability rate of the Stochastic Gradient Descent algorithm.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8245–8257},
numpages = {13}
}

@article{10.5555/3122009.3242078,
author = {Allen-Zhu, Zeyuan},
title = {Katyusha: The First Direct Acceleration of Stochastic Gradient Methods},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Nesterov's momentum trick is famously known for accelerating gradient descent, and has been proven useful in building fast iterative algorithms. However, in the stochastic setting, counterexamples exist and prevent Nesterov's momentum from providing similar acceleration, even if the underlying problem is convex and finite-sum.We introduce Katyusha, a direct, primal-only stochastic gradient method to fix this issue. In convex finite-sum stochastic optimization, Katyusha has an optimal accelerated convergence rate, and enjoys an optimal parallel linear speedup in the mini-batch setting.The main ingredient is Katyusha momentum, a novel "negative momentum" on top of Nesterov's momentum. It can be incorporated into a variance-reduction based algorithm and speed it up, both in terms of sequential and parallel performance. Since variance reduction has been successfully applied to a growing list of practical problems, our paper suggests that in each of such cases, one could potentially try to give Katyusha a hug.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8194–8244},
numpages = {51}
}

@article{10.5555/3122009.3242077,
author = {Perkovic, Emilija and Textor, Johannes and Kalisch, Markus and Maathuis, Marloes H.},
title = {Complete Graphical Characterization and Construction of Adjustment Sets in Markov Equivalence Classes of Ancestral Graphs},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We present a graphical criterion for covariate adjustment that is sound and complete for four different classes of causal graphical models: directed acyclic graphs (DAGs), maximal ancestral graphs (MAGs), completed partially directed acyclic graphs (CPDAGs), and partial ancestral graphs (PAGs). Our criterion unifies covariate adjustment for a large set of graph classes. Moreover, we define an explicit set that satisfies our criterion, if there is any set that satisfies our criterion. We also give efficient algorithms for constructing all sets that fulfill our criterion, implemented in the R package dagitty. Finally, we discuss the relationship between our criterion and other criteria for adjustment, and we provide new soundness and completeness proofs for the adjustment criterion for DAGs.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8132–8193},
numpages = {62},
keywords = {confounding, covariate adjustment, latent variables, causal effects, graphical models}
}

@article{10.5555/3122009.3242076,
author = {Gr\"{u}new\"{a}lder, Steffen},
title = {Compact Convex Projections},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We study the usefulness of conditional gradient like methods for determining projections onto convex sets, in particular, projections onto naturally arising convex sets in reproducing kernel Hilbert spaces. Our work is motivated by the recently introduced kernel herding algorithm which is closely related to the Conditional Gradient Method (CGM). It is known that the herding algorithm converges with a rate of 1/t , where t counts the number of iterations, when a point in the interior of a convex set is approximated. We generalize this result and we provide a necessary and sufficient condition for the algorithm to approximate projections with a rate of 1/t . The CGM, which is in general vastly superior to the herding algorithm, achieves only an inferior rate of 1/√t in this setting. We study the usefulness of such projection algorithms further by exploring ways to use these for solving concrete machine learning problems. In particular, we derive non-parametric regression algorithms which use at their core a slightly modified kernel herding algorithm to determine projections. We derive bounds to control approximation errors of these methods and we demonstrate via experiments that the developed regressors are en-par with state-of-the-art regression algorithms for large scale problems.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8089–8131},
numpages = {43}
}

@article{10.5555/3122009.3242075,
author = {Wang, Shusen and Gittens, Alex and Mahoney, Michael W.},
title = {Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We address the statistical and optimization impacts of the classical sketch and Hessian sketch used to approximately solve the Matrix Ridge Regression (MRR) problem. Prior research has quantified the effects of classical sketch on the strictly simpler least squares regression (LSR) problem. We establish that classical sketch has a similar effect upon the optimization properties of MRR as it does on those of LSR: namely, it recovers nearly optimal solutions. By contrast, Hessian sketch does not have this guarantee; instead, the approximation error is governed by a subtle interplay between the "mass" in the responses and the optimal objective value.For both types of approximation, the regularization in the sketched MRR problem results in significantly different statistical properties from those of the sketched LSR problem. In particular, there is a bias-variance trade-off in sketched MRR that is not present in sketched LSR. We provide upper and lower bounds on the bias and variance of sketched MRR; these bounds show that classical sketch significantly increases the variance, while Hessian sketch significantly increases the bias. Empirically, sketched MRR solutions can have risks that are higher by an order-of-magnitude than those of the optimal MRR solutions.We establish theoretically and empirically that model averaging greatly decreases the gap between the risks of the true and sketched solutions to the MRR problem. Thus, in parallel or distributed settings, sketching combined with model averaging is a powerful technique that quickly obtains near-optimal solutions to the MRR problem while greatly mitigating the increased statistical risk incurred by sketching.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8039–8088},
numpages = {50},
keywords = {ridge regression, matrix sketching, randomized linear algebra}
}

@article{10.5555/3122009.3242074,
author = {Hao, Botao and Sun, Will Wei and Liu, Yufeng and Cheng, Guang},
title = {Simultaneous Clustering and Estimation of Heterogeneous Graphical Models},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We consider joint estimation of multiple graphical models arising from heterogeneous and high-dimensional observations. Unlike most previous approaches which assume that the cluster structure is given in advance, an appealing feature of our method is to learn cluster structure while estimating heterogeneous graphical models. This is achieved via a high dimensional version of Expectation Conditional Maximization (ECM) algorithm (Meng and Rubin, 1993). A joint graphical lasso penalty is imposed on the conditional maximization step to extract both homogeneity and heterogeneity components across all clusters. Our algorithm is computationally efficient due to fast sparse learning routines and can be implemented without unsupervised learning knowledge. The superior performance of our method is demonstrated by extensive experiments and its application to a Glioblastoma cancer dataset reveals some new insights in understanding the Glioblastoma cancer. In theory, a non-asymptotic error bound is established for the output directly from our high dimensional ECM algorithm, and it consists of two quantities: statistical error (statistical accuracy) and optimization error (computational complexity). Such a result gives a theoretical guideline in terminating our ECM iterations.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7981–8038},
numpages = {58},
keywords = {clustering, high-dimensional statistics, non-convex optimization, graphical models, finite-sample analysis}
}

@article{10.5555/3122009.3242073,
author = {Buccapatnam, Swapna and Liu, Fang and Eryilmaz, Atilla and Shroff, Ness B.},
title = {Reward Maximization under Uncertainty: Leveraging Side-Observations on Networks},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We study the stochastic multi-armed bandit (MAB) problem in the presence of side-observations across actions that occur as a result of an underlying network structure. In our model, a bipartite graph captures the relationship between actions and a common set of unknowns such that choosing an action reveals observations for the unknowns that it is connected to. This models a common scenario in online social networks where users respond to their friends' activity, thus providing side information about each other's preferences. Our contributions are as follows: 1) We derive an asymptotic lower bound (with respect to time) as a function of the bi-partite network structure on the regret of any uniformly good policy that achieves the maximum long-term average reward. 2) We propose two policies - a randomized policy; and a policy based on the well-known upper confidence bound (UCB) policies - both of which explore each action at a rate that is a function of its network position. We show, under mild assumptions, that these policies achieve the asymptotic lower bound on the regret up to a multiplicative factor, independent of the network structure. Finally, we use numerical examples on a real-world social network and a routing example network to demonstrate the benefits obtained by our policies over other existing policies.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7947–7980},
numpages = {34},
keywords = {regret bounds, bipartite graph, side observations, multi-armed bandits}
}

@article{10.5555/3122009.3242072,
author = {Kasai, Hiroyuki},
title = {SGDLibrary: A Matlab Library for Stochastic Optimization Algorithms},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of finding the minimizer of a function f : Rd → R of the finite-sum form min f(w) = 1/nΣin fi(w). This problem has been studied intensively in recent years in the field of machine learning (ML). One promising approach for large-scale data is to use a stochastic optimization algorithm to solve the problem. SGDLibrary is a readable, flexible and extensible pure-MATLAB library of a collection of stochastic optimization algorithms. The purpose of the library is to provide researchers and implementers a comprehensive evaluation environment for the use of these algorithms on various ML problems.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7942–7946},
numpages = {5},
keywords = {stochastic optimization, finite-sum minimization problem, stochastic gradient, large-scale optimization problem}
}

@article{10.5555/3122009.3242071,
author = {Bacry, Emmanuel and Bompaire, Martin and Deegan, Philip and Ga\"{\i}ffas, St\'{e}phane and Poulsen, S\o{}ren V.},
title = {Tick: A Python Library for Statistical Learning, with an Emphasis on Hawkes Processes and Time-Dependent Models},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {This paper introduces tick, is a statistical learning library for Python 3, with a particular emphasis on time-dependent models, such as point processes, tools for generalized linear models and survival analysis. The core of the library provides model computational classes, solvers and proximal operators for regularization. It relies on a C++ implementation and state-of-the-art optimization algorithms to provide very fast computations in a single node multi-core setting. Source code and documentation can be downloaded from https://github.com/X-DataInitiative/tick.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7937–7941},
numpages = {5},
keywords = {statistical learning, python, survival analysis, generalized linear models, point process, Hawkes processes, optimization}
}

@article{10.5555/3122009.3242070,
author = {Painsky, Amichai and Tishby, Naftali},
title = {Gaussian Lower Bound for the Information Bottleneck Limit},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {The Information Bottleneck (IB) is a conceptual method for extracting the most compact, yet informative, representation of a set of variables, with respect to the target. It generalizes the notion of minimal sufficient statistics from classical parametric statistics to a broader information-theoretic sense. The IB curve defines the optimal trade-off between representation complexity and its predictive power. Specifically, it is achieved by minimizing the level of mutual information (MI) between the representation and the original variables, subject to a minimal level of MI between the representation and the target. This problem is shown to be in general NP hard. One important exception is the multivariate Gaussian case, for which the Gaussian IB (GIB) is known to obtain an analytical closed form solution, similar to Canonical Correlation Analysis (CCA). In this work we introduce a Gaussian lower bound to the IB curve; we find an embedding of the data which maximizes its "Gaussian part", on which we apply the GIB. This embedding provides an efficient (and practical) representation of any arbitrary data-set (in the IB sense), which in addition holds the favorable properties of a Gaussian distribution. Importantly, we show that the optimal Gaussian embedding is bounded from above by non-linear CCA. This allows a fundamental limit for our ability to Gaussianize arbitrary data-sets and solve complex problems by linear methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7908–7936},
numpages = {29},
keywords = {canonical correlations, ACE, mutual information maximization, infomax, information bottleneck, gaussianization}
}

@article{10.5555/3122009.3242069,
author = {Lin, Hongzhou and Mairal, Julien and Harchaoui, Zaid},
title = {Catalyst Acceleration for First-Order Convex Optimization: From Theory to Practice},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We introduce a generic scheme for accelerating gradient-based optimization methods in the sense of Nesterov. The approach, called Catalyst, builds upon the inexact accelerated proximal point algorithm for minimizing a convex objective function, and consists of approximately solving a sequence of well-chosen auxiliary problems, leading to faster convergence. One of the keys to achieve acceleration in theory and in practice is to solve these sub-problems with appropriate accuracy by using the right stopping criterion and the right warm-start strategy. We give practical guidelines to use Catalyst and present a comprehensive analysis of its global complexity. We show that Catalyst applies to a large class of algorithms, including gradient descent, block coordinate descent, incremental algorithms such as SAG, SAGA, SDCA, SVRG, MISO/Finito, and their proximal variants. For all of these methods, we establish faster rates using the Catalyst acceleration, for strongly convex and non-strongly convex objectives. We conclude with extensive experiments showing that acceleration is useful in practice, especially for ill-conditioned problems.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7854–7907},
numpages = {54},
keywords = {large-scale machine learning, convex optimization, first-order methods}
}

@article{10.5555/3122009.3242068,
author = {Yang, Jiyan and Chow, Yin-Lam and R\'{e}, Christopher and Mahoney, Michael W.},
title = {Weighted SGD for ℓ<sub>p</sub> Regression with Randomized Preconditioning},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In recent years, stochastic gradient descent (SGD) methods and randomized linear algebra (RLA) algorithms have been applied to many large-scale problems in machine learning and data analysis. SGD methods are easy to implement and applicable to a wide range of convex optimization problems. In contrast, RLA algorithms provide much stronger performance guarantees but are applicable to a narrower class of problems. We aim to bridge the gap between these two methods in solving constrained overdetermined linear regression problems--e.g., ℓ2 and ℓ1 regression problems.• We propose a hybrid algorithm named PWSGD that uses RLA techniques for preconditioning and constructing an importance sampling distribution, and then performs an SGD-like iterative process with weighted sampling on the preconditioned system.• By rewriting a deterministic ℓp regression problem as a stochastic optimization problem, we connect PWSGD to several existing ℓp solvers including RLA methods with algorithmic leveraging (RLA for short).• We prove that PWSGD inherits faster convergence rates that only depend on the lower dimension of the linear system, while maintaining low computation complexity. Such SGD convergence rates are superior to other related SGD algorithm such as the weighted randomized Kaczmarz algorithm.• Particularly, when solving ℓ1 regression with size n by d, PWSGD returns an approximate solution with ε relative error in the objective value in O(log n · nnz(A) + poly(d)/ε2) time. This complexity is uniformly better than that of RLA methods in terms of both ε and d when the problem is unconstrained. In the presence of constraints, PWSGD only has to solve a sequence of much simpler and smaller optimization problem over the same constraints. In general this is more efficient than solving the constrained subproblem required in RLA.• For ℓ2 regression, PWSGD returns an approximate solution with ε relative error in the objective value and the solution vector measured in prediction norm in O(log n· nnz(A)+poly(d) log(1/ε)/ε) time. We show that for unconstrained ℓ2 regression, this complexity is comparable to that of RLA and is asymptotically better over several state-of-the-art solvers in the regime where the desired accuracy ε, high dimension n and low dimension d satisfy d ≥ 1/ε and n ≥ d2/ε.We also provide lower bounds on the coreset complexity for more general regression problems, indicating that still new ideas will be needed to extend similar RLA preconditioning ideas to weighted SGD algorithms for more general regression problems. Finally, the effectiveness of such algorithms is illustrated numerically on both synthetic and real datasets, and the results are consistent with our theoretical findings and demonstrate that PWSGD converges to a medium-precision solution, e.g., ε = 10-3, more quickly.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7811–7853},
numpages = {43}
}

@article{10.5555/3122009.3242067,
author = {Borgs, Christian and Chayes, Jennifer T. and Cohn, Henry and Holden, Nina},
title = {Sparse Exchangeable Graphs and Their Limits via Graphon Processes},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In a recent paper, Caron and Fox suggest a probabilistic model for sparse graphs which are exchangeable when associating each vertex with a time parameter in R+. Here we show that by generalizing the classical definition of graphons as functions over probability spaces to functions over σ-finite measure spaces, we can model a large family of exchangeable graphs, including the Caron-Fox graphs and the traditional exchangeable dense graphs as special cases. Explicitly, modelling the underlying space of features by a σ-finite measure space (S, S, µ) and the connection probabilities by an integrable function W : S \texttimes{} S → [0, 1], we construct a random family (Gt)t≥0 of growing graphs such that the vertices of Gt are given by a Poisson point process on S with intensity tµ, with two points x, y of the point process connected with probability W(x, y). We call such a random family a graphon process. We prove that a graphon process has convergent subgraph frequencies (with possibly infinite limits) and that, in the natural extension of the cut metric to our setting, the sequence converges to the generating graphon. We also show that the underlying graphon is identifiable only as an equivalence class over graphons with cut distance zero. More generally, we study metric convergence for arbitrary (not necessarily random) sequences of graphs, and show that a sequence of graphs has a convergent subsequence if and only if it has a subsequence satisfying a property we call uniform regularity of tails. Finally, we prove that every graphon is equivalent to a graphon on R+ equipped with Lebesgue measure.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7740–7810},
numpages = {71},
keywords = {graphons, sparse graph convergence, modelling of sparse networks, exchangeable graph models, graph convergence}
}

@article{10.5555/3122009.3242066,
author = {Tarzanagh, Davoud Ataee and Michailidis, George},
title = {Estimation of Graphical Models through Structured Norm Minimization},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Estimation of Markov Random Field and covariance models from high-dimensional data represents a canonical problem that has received a lot of attention in the literature. A key assumption, widely employed, is that of sparsity of the underlying model. In this paper, we study the problem of estimating such models exhibiting a more intricate structure comprising simultaneously of sparse, structured sparse and dense components. Such structures naturally arise in several scientific fields, including molecular biology, finance and political science. We introduce a general framework based on a novel structured norm that enables us to estimate such complex structures from high-dimensional data. The resulting optimization problem is convex and we introduce a linearized multi-block alternating direction method of multipliers (ADMM) algorithm to solve it efficiently. We illustrate the superior performance of the proposed framework on a number of synthetic data sets generated from both random and structured networks. Further, we apply the method to a number of real data sets and discuss the results.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7692–7739},
numpages = {48},
keywords = {Gaussian covariance graph model, structured sparse norm, regularization, convergence, alternating direction method of multipliers (ADMM), Markov rRandom fields}
}

@article{10.5555/3122009.3242065,
author = {Shen, Jie and Li, Ping},
title = {A Tight Bound of Hard Thresholding},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {This paper is concerned with the hard thresholding operator which sets all but the k largest absolute elements of a vector to zero. We establish a tight bound to quantitatively characterize the deviation of the thresholded solution from a given signal. Our theoretical result is universal in the sense that it holds for all choices of parameters, and the underlying analysis depends only on fundamental arguments in mathematical optimization. We discuss the implications for two domains: Compressed Sensing. On account of the crucial estimate, we bridge the connection between the restricted isometry property (RIP) and the sparsity parameter for a vast volume of hard thresholding based algorithms, which renders an improvement on the RIP condition especially when the true sparsity is unknown. This suggests that in essence, many more kinds of sensing matrices or fewer measurements are admissible for the data acquisition procedure. Machine Learning. In terms of large-scale machine learning, a significant yet challenging problem is learning accurate sparse models in an efficient manner. In stark contrast to prior work that attempted the l1-relaxation for promoting sparsity, we present a novel stochastic algorithm which performs hard thresholding in each iteration, hence ensuring such parsimonious solutions. Equipped with the developed bound, we prove the global linear convergence for a number of prevalent statistical models under mild assumptions, even though the problem turns out to be non-convex.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7650–7691},
numpages = {42},
keywords = {hard thresholding, sparsity, stochastic optimization, compressed sensing}
}

@article{10.5555/3122009.3242064,
author = {Fan, Jianqing and Wang, Weichen and Zhong, Yiqiao},
title = {An ℓ<sub>∞</sub> Eigenvector Perturbation Bound and Its Application to Robust Covariance Estimation},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In statistics and machine learning, we are interested in the eigenvectors (or singular vectors) of certain matrices (e.g. covariance matrices, data matrices, etc). However, those matrices are usually perturbed by noises or statistical errors, either from random sampling or structural patterns. The Davis-Kahan sin θ theorem is often used to bound the difference between the eigenvectors of a matrix A and those of a perturbed matrix \~{A} = A + E, in terms of ℓ2 norm. In this paper, we prove that when A is a low-rank and incoherent matrix, the ℓ∞ norm perturbation bound of singular vectors (or eigenvectors in the symmetric case) is smaller by a factor of √d1 or √d2 for left and right vectors, where d1 and d2 are the matrix dimensions. The power of this new perturbation result is shown in robust covariance estimation, particularly when random variables have heavy tails. There, we propose new robust covariance estimators and establish their asymptotic properties using the newly developed perturbation bound. Our theoretical results are verified through extensive numerical experiments.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7608–7649},
numpages = {42},
keywords = {approximate factor model, sparsity, matrix perturbation theory, incoherence, low-rank matrices}
}

@article{10.5555/3122009.3242063,
author = {Ray, Avik and Neeman, Joe and Sanghavi, Sujay and Shakkottai, Sanjay},
title = {The Search Problem in Mixture Models},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We consider the task of learning the parameters of a single component of a mixture model, for the case when we are given side information about that component; we call this the "search problem" in mixture models. We would like to solve this with computational and sample complexity lower than solving the overall original problem, where one learns parameters of all components.Our main contributions are the development of a simple but general model for the notion of side information, and a corresponding simple matrix-based algorithm for solving the search problem in this general setting. We then specialize this model and algorithm to four common scenarios: Gaussian mixture models, LDA topic models, subspace clustering, and mixed linear regression. For each one of these we show that if (and only if) the side information is informative, we obtain parameter estimates with greater accuracy, and also improved computation complexity than existing moment based mixture model algorithms (e.g. tensor methods). We also illustrate several natural ways one can obtain such side information, for specific problem instances. Our experiments on real data sets (NY Times, Yelp, BSDS500) further demonstrate the practicality of our algorithms showing significant improvement in runtime and accuracy.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7547–7607},
numpages = {61},
keywords = {side information, mixture models, method of moments, semi-supervised, search}
}

@article{10.5555/3122009.3242062,
author = {Zarezade, Ali and De, Abir and Upadhyay, Utkarsh and Rabiee, Hamid R. and Gomez-Rodriguez, Manuel},
title = {Steering Social Activity: A Stochastic Optimal Control Point of View},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {User engagement in online social networking depends critically on the level of social activity in the corresponding platform--the number of online actions, such as posts, shares or replies, taken by their users. Can we design data-driven algorithms to increase social activity? At a user level, such algorithms may increase activity by helping users decide when to take an action to be more likely to be noticed by their peers. At a network level, they may increase activity by incentivizing a few inuential users to take more actions, which in turn will trigger additional actions by other users.In this paper, we model social activity using the framework of marked temporal point processes, derive an alternate representation of these processes using stochastic differential equations (SDEs) with jumps and, exploiting this alternate representation, develop two efficient online algorithms with provable guarantees to steer social activity both at a user and at a network level. In doing so, we establish a previously unexplored connection between optimal control of jump SDEs and doubly stochastic marked temporal point processes, which is of independent interest. Finally, we experiment both with synthetic and real data gathered from Twitter and show that our algorithms consistently steer social activity more effectively than the state of the art.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7512–7546},
numpages = {35},
keywords = {social networks, stochastic differential equations with jumps, information networks, marked temporal point processes, stochastic optimal control}
}

@article{10.5555/3122009.3242061,
author = {Zhang, Quan and Zhou, Mingyuan},
title = {Permuted and Augmented Stick-Breaking Bayesian Multinomial Regression},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {To model categorical response variables given their covariates, we propose a permuted and augmented stick-breaking (paSB) construction that one-to-one maps the observed categories to randomly permuted latent sticks. This new construction transforms multinomial regression into regression analysis of stick-specific binary random variables that are mutually independent given their covariate-dependent stick success probabilities, which are parameterized by the regression coefficients of their corresponding categories. The paSB construction allows transforming an arbitrary cross-entropy-loss binary classifier into a Bayesian multinomial one. Specifically, we parameterize the negative logarithms of the stick failure probabilities with a family of covariate-dependent softplus functions to construct nonparametric Bayesian multinomial softplus regression, and transform Bayesian support vector machine (SVM) into Bayesian multinomial SVM. These Bayesian multinomial regression models are not only capable of providing probability estimates, quantifying uncertainty, increasing robustness, and producing nonlinear classification decision boundaries, but also amenable to posterior simulation. Example results demonstrate their attractive properties and performance.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7479–7511},
numpages = {33},
keywords = {nonlinear classification, logistic regression, support vector machines, softplus regression, discrete choice models}
}

@article{10.5555/3122009.3242060,
author = {Lu, Junwei and Kolar, Mladen and Liu, Han},
title = {Post-Regularization Inference for Time-Varying Nonparanormal Graphical Models},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We propose a novel class of time-varying nonparanormal graphical models, which allows us to model high dimensional heavy-tailed systems and the evolution of their latent network structures. Under this model we develop statistical tests for presence of edges both locally at a fixed index value and globally over a range of values. The tests are developed for a high-dimensional regime, are robust to model selection mistakes and do not require commonly assumed minimum signal strength. The testing procedures are based on a high dimensional, debiasing-free moment estimator, which uses a novel kernel smoothed Kendall's tau correlation matrix as an input statistic. The estimator consistently estimates the latent inverse Pearson correlation matrix uniformly in both the index variable and kernel bandwidth. Its rate of convergence is shown to be minimax optimal. Our method is supported by thorough numerical simulations and an application to a neural imaging data set.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7401–7478},
numpages = {78},
keywords = {graphical model selection, time-varying network analysis, hypothesis test, nonparanormal graph, regularized rank-based estimator}
}

@article{10.5555/3122009.3242059,
author = {Liang, Shuhan and Lu, Wenbin and Song, Rui and Wang, Lan},
title = {Sparse Concordance-Assisted Learning for Optimal Treatment Decision},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {To find optimal decision rule, Fan et al. (2016) proposed an innovative concordance-assisted learning algorithm which is based on maximum rank correlation estimator. It makes better use of the available information through pairwise comparison. However the objective function is discontinuous and computationally hard to optimize. In this paper, we consider a convex surrogate loss function to solve this problem. In addition, our algorithm ensures sparsity of decision rule and renders easy interpretation. We derive the L2 error bound of the estimated coefficients under ultra-high dimension. Simulation results of various settings and application to STAR*D both illustrate that the proposed method can still estimate optimal treatment regime successfully when the number of covariates is large.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7375–7400},
numpages = {26},
keywords = {concordance-assisted learning, support vector machine, optimal treatment regime, L1 norm, variable selection}
}

@article{10.5555/3122009.3242058,
author = {Konev, Boris and Lutz, Carsten and Ozaki, Ana and Wolter, Frank},
title = {Exact Learning of Lightweight Description Logic Ontologies},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We study the problem of learning description logic (DL) ontologies in Angluin et al.'s framework of exact learning via queries. We admit membership queries ("is a given subsumption entailed by the target ontology?") and equivalence queries ("is a given ontology equivalent to the target ontology?"). We present three main results: (1) ontologies formulated in (two relevant versions of) the description logic DL-Lite can be learned with polynomially many queries of polynomial size; (2) this is not the case for ontologies formulated in the description logic EL, even when only acyclic ontologies are admitted; and (3) ontologies formulated in a fragment of EL related to the web ontology language OWL 2 RL can be learned in polynomial time. We also show that neither membership nor equivalence queries alone are sufficient in cases (1) and (3).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7312–7374},
numpages = {63},
keywords = {description logic, exact learning, complexity}
}

@article{10.5555/3122009.3242057,
author = {Helmbold, David P. and Long, Philip M.},
title = {Surprising Properties of Dropout in Deep Networks},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We analyze dropout in deep networks with rectified linear units and the quadratic loss. Our results expose surprising differences between the behavior of dropout and more traditional regularizers like weight decay. For example, on some simple data sets dropout training produces negative weights even though the output is the sum of the inputs. This provides a counterpoint to the suggestion that dropout discourages co-adaptation of weights. We also show that the dropout penalty can grow exponentially in the depth of the network while the weight-decay penalty remains essentially linear, and that dropout is insensitive to various re-scalings of the input features, outputs, and network weights. This last insensitivity implies that there are no isolated local minima of the dropout training criterion. Our work uncovers new properties of dropout, extends our understanding of why dropout succeeds, and lays the foundation for further progress.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7284–7311},
numpages = {28},
keywords = {deep neural networks, learning theory, regularization, dropout}
}

@article{10.5555/3122009.3242056,
author = {Shah, Nihar B. and Wainwright, Martin J.},
title = {Simple, Robust and Optimal Ranking from Pairwise Comparisons},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We consider data in the form of pairwise comparisons of n items, with the goal of identifying the top k items for some value of k < n, or alternatively, recovering a ranking of all the items. We analyze the Borda counting algorithm that ranks the items in order of the number of pairwise comparisons won, and show it has three attractive features: (a) it is an optimal method achieving the information-theoretic limits up to constant factors; (b) it is robust in that its optimality holds without imposing conditions on the underlying matrix of pairwise-comparison probabilities, in contrast to some prior work that applies only to the BTL parametric model; and (c) its computational efficiency leads to speedups of several orders of magnitude. We address the problem of exact recovery, and for the top-k recovery problem we also extend our results to obtain sharp guarantees for approximate recovery under the Hamming distortion metric, and more generally, to any arbitrary error requirement that satisfies a simple and natural monotonicity condition. In doing so, we introduce a general framework that allows us to treat a variety of problems in the literature in an unified manner.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7246–7283},
numpages = {38},
keywords = {borda count, occam's razor, approximate recovery, ranking, set recovery, pairwise comparisons, permutation-based models}
}

@article{10.5555/3122009.3242055,
author = {Patrascu, Andrei and Necoara, Ion},
title = {Nonasymptotic Convergence of Stochastic Proximal Point Methods for Constrained Convex Optimization},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {A popular approach for solving stochastic optimization problems is the stochastic gradient descent (SGD) method. Although the SGD iteration is computationally cheap and its practical performance may be satisfactory under certain circumstances, there is recent evidence of its convergence difficulties and instability for unappropriate choice of parameters. To avoid some of the drawbacks of SGD, stochastic proximal point (SPP) algorithms have been recently considered. We introduce a new variant of the SPP method for solving stochastic convex problems subject to (in)finite intersection of constraints satisfying a linear regularity condition. For the newly introduced SPP scheme we prove new nonasymptotic convergence results. In particular, for convex Lipschitz continuous objective functions, we prove nonasymptotic convergence rates in terms of the expected value function gap of order O(1/k1/2), where k is the iteration counter. We also derive better nonasymptotic convergence rates in terms of expected quadratic distance from the iterates to the optimal solution for smooth strongly convex objective functions, which in the best case is of order O(1/k). Since these convergence rates can be attained by our SPP algorithm only under some natural restrictions on the stepsize, we also introduce a restarting variant of SPP that overcomes these difficulties and derive the corresponding nonasymptotic convergence rates. Numerical evidence supports the effectiveness of our methods in real problems.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7204–7245},
numpages = {42},
keywords = {stochastic proximal point, stochastic convex optimization, intersection of convex constraints, rates of convergence, nonasymptotic convergence analysis}
}

@article{10.5555/3122009.3242054,
author = {Boyd, Nicholas and Hastie, Trevor and Boyd, Stephen and Recht, Benjamin and Jordan, Michael I.},
title = {Saturating Splines and Feature Selection},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We extend the adaptive regression spline model by incorporating saturation, the natural requirement that a function extend as a constant outside a certain range. We fit saturating splines to data via a convex optimization problem over a space of measures, which we solve using an efficient algorithm based on the conditional gradient method. Unlike many existing approaches, our algorithm solves the original infinite-dimensional (for splines of degree at least two) optimization problem without pre-specified knot locations. We then adapt our algorithm to fit generalized additive models with saturating splines as coordinate functions and show that the saturation requirement allows our model to simultaneously perform feature selection and nonlinear function fitting. Finally, we briey sketch how the method can be extended to higher order splines and to different requirements on the extension outside the data range.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7172–7203},
numpages = {32},
keywords = {feature selection, convex optimization, splines, regression, lasso}
}

@article{10.5555/3122009.3242053,
author = {Bertsimas, Dimitris and Pawlowski, Colin and Zhuo, Ying Daisy},
title = {From Predictive Methods to Missing Data Imputation: An Optimization Approach},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Missing data is a common problem in real-world settings and for this reason has attracted significant attention in the statistical literature. We propose a flexible framework based on formal optimization to impute missing data with mixed continuous and categorical variables. This framework can readily incorporate various predictive models including K- nearest neighbors, support vector machines, and decision tree based methods, and can be adapted for multiple imputation. We derive fast first-order methods that obtain high quality solutions in seconds following a general imputation algorithm opt.impute presented in this paper. We demonstrate that our proposed method improves out-of-sample accuracy in large-scale computational experiments across a sample of 84 data sets taken from the UCI Machine Learning Repository. In all scenarios of missing at random mechanisms and various missing percentages, opt.impute produces the best overall imputation in most data sets benchmarked against five other methods: mean impute, K-nearest neighbors, iterative knn, Bayesian PCA, and predictive-mean matching, with an average reduction in mean absolute error of 8.3% against the best cross-validated benchmark method. Moreover, opt.impute leads to improved out-of-sample performance of learning algorithms trained using the imputed data, demonstrated by computational experiments on 10 downstream tasks. For models trained using opt.impute single imputations with 50% data missing, the average out-of-sample R2 is 0.339 in the regression tasks and the average out-of-sample accuracy is 86.1% in the classification tasks, compared to 0.315 and 84.4% for the best cross-validated benchmark method. In the multiple imputation setting, downstream models trained using opt.impute obtain a statistically significant improvement over models trained using multivariate imputation by chained equations (mice) in 8/10 missing data scenarios considered.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7133–7171},
numpages = {39},
keywords = {missing data imputation, optimal decision trees, K-NN, SVM}
}

@article{10.5555/3122009.3242052,
author = {Kontorovich, Aryeh and Sabato, Sivan and Urner, Ruth},
title = {Active Nearest-Neighbor Learning in Metric Spaces},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We propose a pool-based non-parametric active learning algorithm for general metric spaces, called MArgin Regularized Metric Active Nearest Neighbor (MARMANN), which outputs a nearest-neighbor classifier. We give prediction error guarantees that depend on the noisy-margin properties of the input sample, and are competitive with those obtained by previously proposed passive learners. We prove that the label complexity of MARMANN is significantly lower than that of any passive learner with similar error guarantees. MARMANN is based on a generalized sample compression scheme, and a new label-efficient active model-selection procedure.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7095–7132},
numpages = {38},
keywords = {nearest-neighbors, non-parametric learning, active learning, metric spaces}
}

@article{10.5555/3122009.3242051,
author = {Tikka, Santtu and Karvanen, Juha},
title = {Enhancing Identification of Causal Effects by Pruning},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Causal models communicate our assumptions about causes and effects in real-world phenomena. Often the interest lies in the identification of the effect of an action which means deriving an expression from the observed probability distribution for the interventional distribution resulting from the action. In many cases an identifiability algorithm may return a complicated expression that contains variables that are in fact unnecessary. In practice this can lead to additional computational burden and increased bias or inefficiency of estimates when dealing with measurement error or missing data. We present graphical criteria to detect variables which are redundant in identifying causal effects. We also provide an improved version of a well-known identifiability algorithm that implements these criteria.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7072–7094},
numpages = {23},
keywords = {causal inference, causal model, algorithm, identifiability, pruning}
}

@article{10.5555/3122009.3242050,
author = {Vaughan, Jennifer Wortman},
title = {Making Better Use of the Crowd: How Crowdsourcing Can Advance Machine Learning Research},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {This survey provides a comprehensive overview of the landscape of crowdsourcing research, targeted at the machine learning community. We begin with an overview of the ways in which crowdsourcing can be used to advance machine learning research, focusing on four application areas: 1) data generation, 2) evaluation and debugging of models, 3) hybrid intelligence systems that leverage the complementary strengths of humans and machines to expand the capabilities of AI, and 4) crowdsourced behavioral experiments that improve our understanding of how humans interact with machine learning systems and technology more broadly. We next review the extensive literature on the behavior of crowdworkers themselves. This research, which explores the prevalence of dishonesty among crowdworkers, how workers respond to both monetary incentives and intrinsic forms of motivation, and how crowdworkers interact with each other, has immediate implications that we distill into best practices that researchers should follow when using crowdsourcing in their own research. We conclude with a discussion of additional tips and best practices that are crucial to the success of any project that uses crowdsourcing, but rarely mentioned in the literature.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7026–7071},
numpages = {46},
keywords = {mechanical turk, data generation, behavioral experiments, hybrid intelligence, model evaluation, crowdsourcing, incentives}
}

@article{10.5555/3122009.3242049,
author = {Achab, Massil and Bacry, Emmanuel and Ga\"{\i}ffas, St\'{e}phane and Mastromatteo, Iacopo and Muzy, Jean-Fran\c{c}ois},
title = {Uncovering Causality from Multivariate Hawkes Integrated Cumulants},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We design a new nonparametric method that allows one to estimate the matrix of integrated kernels of a multivariate Hawkes process. This matrix not only encodes the mutual influences of each node of the process, but also disentangles the causality relationships between them. Our approach is the first that leads to an estimation of this matrix without any parametric modeling and estimation of the kernels themselves. As a consequence, it can give an estimation of causality relationships between nodes (or users), based on their activity timestamps (on a social network for instance), without knowing or estimating the shape of the activities lifetime. For that purpose, we introduce a moment matching method that fits the second-order and the third-order integrated cumulants of the process. A theoretical analysis allows us to prove that this new estimation technique is consistent. Moreover, we show, on numerical experiments, that our approach is indeed very robust with respect to the shape of the kernels and gives appealing results on the MemeTracker database and on financial order book data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6998–7025},
numpages = {28},
keywords = {cumulants, causality inference, Hawkes process, generalized method of moments}
}

@article{10.5555/3122009.3242048,
author = {Filice, Simone and Castellucci, Giuseppe and Da San Martino, Giovanni and Moschitti, Alessandro and Croce, Danilo and Basili, Roberto},
title = {KeLP: A Kernel-Based Learning Platform},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {KELP is a Java framework that enables fast and easy implementation of kernel functions over discrete data, such as strings, trees or graphs and their combination with standard vectorial kernels. Additionally, it provides several kernel-based algorithms, e.g., online and batch kernel machines for classification, regression and clustering, and a Java environment for easy implementation of new algorithms. KELP is a versatile toolkit, very appealing both to experts and practitioners of machine learning and Java language programming, who can find extensive documentation, tutorials and examples of increasing complexity on the accompanying website. Interestingly, KELP can be also used without any knowledge of Java programming through command line tools and JSON/XML interfaces enabling the declaration and instantiation of articulated learning models using simple templates. Finally, the extensive use of modularity and interfaces in KeLP enables developers to easily extend it with their own kernels and algorithms.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6993–6997},
numpages = {5},
keywords = {Kernel machines, java framework, structured data and kernels}
}

@article{10.5555/3122009.3242047,
author

license_type: permissive

branch_name: refs/heads/main

extension: bib