mtybilly/Instruct2DS huggingface dataset:
Robust Sparse Regression under Adversarial Corruption
Authors: Chen, Yudong and Caramanis, Constantine and Mannor, Shie
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We consider high dimensional sparse regression with arbitrary – possibly, severe or coordinated – errors in the covariates matrix. We are interested in understanding how many corruptions we can tolerate, while identifying the correct support. To the best of our knowledge, neither standard outlier rejection techniques, nor recently developed robust regression algorithms (that focus only on corrupted response variables), nor recent algorithms for dealing with stochastic noise or erasures, can provide guarantees on support recovery. As we show, neither can the natural brute force algorithm that takes exponential time to find the subset of data and support columns, that yields the smallest regression error.     We explore the power of a simple idea: replace the essential linear algebraic calculation – the inner product – with a robust counterpart that cannot be greatly affected by a controlled number of arbitrarily corrupted points: the trimmed inner product. We consider three popular algorithms in the uncorrupted setting: Thresholding Regression, Lasso, and the Dantzig selector, and show that the counterparts obtained using the trimmed inner product are provably robust.
Optimization with First-Order Surrogate Functions
Authors: Mairal, Julien
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper, we study optimization methods consisting of iteratively minimizing surrogates of an objective function. By proposing several algorithmic variants and simple convergence analyses, we make two main contributions.  First, we provide a unified viewpoint for several first-order optimization techniques such as accelerated proximal gradient, block coordinate descent, or Frank-Wolfe algorithms.  Second, we introduce a new incremental scheme that experimentally matches or outperforms state-of-the-art solvers for large-scale optimization problems typically arising in machine learning.
Learning Spatio-Temporal Structure from RGB-D Videos for Human Activity Detection and Anticipation
Authors: Koppula, Hema and Saxena, Ashutosh
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We consider the problem of detecting past activities as well as anticipating which activity will happen in the future and how. We start by modeling the rich spatio-temporal relations between human poses and objects (called affordances) using a conditional random field (CRF). However, because of the ambiguity in the temporal segmentation of the sub-activities that constitute an activity, in the past as well as in the future, multiple graph structures are possible. In this paper, we reason about these alternate possibilities by reasoning over multiple possible graph structures. We obtain them by approximating the graph with only additive features, which lends to efficient dynamic programming. Starting with this proposal graph structure, we then design moves to obtain several other likely graph structures. We then show that our approach improves the state-of-the-art significantly for detecting past activities as well as for anticipating future activities, on a dataset of 120 activity videos collected from four subjects.
Consistency versus Realizable H-Consistency for Multiclass Classification
Authors: Long, Phil and Servedio, Rocco
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: A consistent loss function for multiclass classification is one such  that for any source of labeled examples, any tuple  of scoring functions that  minimizes the expected loss will have classification accuracy close to that  of the Bayes optimal classifier. While consistency has been proposed as a  desirable property for multiclass loss functions, we  give experimental and theoretical results exhibiting a  sequence of linearly separable data sources with the following property:  a multiclass classification algorithm which optimizes a loss function  due to Crammer and Singer (which is known not to be consistent) produces  classifiers whose expected error goes to 0, while the expected error  of an algorithm which optimizes a generalization of the loss  function used by LogitBoost (a loss function which is known to be consistent)  is bounded below by a positive constant.    We identify a property of a loss function, realizable  consistency with respect to a restricted class of scoring functions,  that accounts for this difference.   As our main technical results we show  that the Crammer–Singer loss function is  realizable consistent for the class of linear scoring functions, while  the generalization of LogitBoost is not.  Our result for LogitBoost is  a special case of a more general theorem that applies to several other  loss functions that have been proposed for multiclass classification.
Feature Multi-Selection among Subjective Features
Authors: Sabato, Sivan and Kalai, Adam
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: When dealing with subjective, noisy, or otherwise nebulous features, the “wisdom of crowds” suggests that one may benefit from multiple judgments of the same feature on the same object. We give theoretically-motivated ""feature multi-selection"" algorithms that choose, among a large set of candidate features, not only which features to judge but how many times to judge each one. We demonstrate the effectiveness of this approach for linear regression on a crowdsourced learning task of predicting people’s height and weight from photos, using features such as ""gender"" and  ""estimated weight"" as well as culturally fraught ones such as ""attractive"".
Domain Adaptation under Target and Conditional Shift
Authors: Zhang, Kun and Schölkopf, Bernhard and Muandet, Krikamol and Wang, Zhikun
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Let X denote the feature and Y the target. We consider domain adaptation under three possible scenarios: (1) the marginal P_Y changes, while the conditional P_X|Y stays the same (ıt target shift), (2) the marginal P_Y is fixed, while the conditional P_X|Y changes with certain constraints (ıt conditional shift), and (3) the marginal P_Y changes, and the conditional P_X|Y changes with constraints (ıt generalized target shift). Using background knowledge, causal interpretations allow us to determine the correct situation for a problem at hand. We exploit importance reweighting or sample transformation to find the learning machine that works well on test data, and propose to estimate the weights or transformations by ıt reweighting or transforming training data to reproduce the covariate distribution on the test domain. Thanks to kernel embedding of conditional as well as marginal distributions, the proposed approaches avoid distribution estimation, and are applicable for high-dimensional problems. Numerical evaluations on synthetic and real-world datasets demonstrate the effectiveness of the proposed framework.
Collective Stability in Structured Prediction: Generalization from One Example
Authors: London, Ben and Huang, Bert and Taskar, Ben and Getoor, Lise
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Structured predictors enable joint inference over multiple interdependent output variables. These models are often trained on a small number of examples with large internal structure. Existing distribution-free generalization bounds do not guarantee generalization in this setting, though this contradicts a large body of empirical evidence from computer vision, natural language processing, social networks and other fields. In this paper, we identify a set of natural conditions – weak dependence, hypothesis complexity and a new measure, collective stability – that are sufficient for generalization from even a single example, without imposing an explicit generative model of the data. We then demonstrate that the complexity and stability conditions are satisfied by a broad class of models, including marginal inference in templated graphical models. We thus obtain uniform convergence rates that can decrease significantly faster than previous bounds, particularly when each structured example is sufficiently large and the number of training examples is constant, even one.
Stable Coactive Learning via Perturbation
Authors: Raman, Karthik and Joachims, Thorsten and Shivaswamy, Pannaga and Schnabel, Tobias
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Coactive Learning is a model of interaction between a learning system (e.g. search engine) and its human users, wherein the system learns from (typically implicit) user feedback during operational use. User feedback takes the form of preferences, and recent work has introduced online algorithms that learn from this weak feedback. However, we show that these algorithms can be unstable and ineffective in real-world settings where biases and noise in the feedback are significant. In this paper, we propose the first coactive learning algorithm that can learn robustly despite bias and noise. In particular, we explore how presenting users with slightly perturbed objects (e.g., rankings) can stabilize the learning process. We theoretically validate the algorithm by proving bounds on the average regret. We also provide extensive empirical evidence on benchmarks and from a live search engine user study, showing that the new algorithm substantially outperforms existing methods.
Max-Margin Multiple-Instance Dictionary Learning
Authors: Wang, Xinggang and Wang, Baoyuan and Bai, Xiang and Liu, Wenyu and Tu, Zhuowen
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Dictionary learning has became an increasingly important task in machine learning, as it is fundamental to the representation problem. A number of emerging techniques specifically include a codebook learning step, in which a critical knowledge abstraction process is carried out. Existing approaches in dictionary (codebook) learning are either generative (unsupervised e.g. k-means) or discriminative (supervised e.g. extremely randomized forests). In this paper, we propose a multiple instance learning (MIL) strategy (along the line of weakly supervised learning) for dictionary learning. Each code is represented by a classifier, such as a linear SVM, which naturally performs metric fusion for multi-channel features. We design a formulation to simultaneously learn mixtures of codes by maximizing classification margins in MIL.  State-of-the-art results are observed in image classification benchmarks based on the learned codebooks, which observe both compactness and effectiveness.
Fast Semidifferential-based Submodular Function Optimization
Authors: Iyer, Rishabh and Jegelka, Stefanie and Bilmes, Jeff
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We present a practical and powerful new framework for both unconstrained and constrained submodular function optimization based on discrete semidifferentials (sub- and super-differentials). The resulting algorithms, which repeatedly compute and then efficiently optimize submodular semigradients, offer new and generalize many old methods for submodular optimization.  Our approach, moreover, takes steps towards providing a unifying paradigm applicable to both submodular minimization and maximization, problems that historically have been treated quite distinctly. The practicality of our algorithms is important since interest in submodularity, owing to its natural and wide applicability, has recently been in ascendance within machine learning.  We analyze theoretical properties of our algorithms for minimization and maximization, and show that many state-of-the-art maximization algorithms are special cases. Lastly, we complement our theoretical analyses with supporting empirical experiments.
Kernelized Bayesian Matrix Factorization
Authors: Gönen, Mehmet and Khan, Suleiman and Kaski, Samuel
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We extend kernelized matrix factorization with a fully Bayesian treatment and with an ability to work with multiple side information sources expressed as different kernels. Kernel functions have been introduced to matrix factorization to integrate side information about the rows and columns (e.g., objects and users in recommender systems), which is necessary for making out-of-matrix (i.e., cold start) predictions. We discuss specifically bipartite graph inference, where the output matrix is binary, but extensions to more general matrices are straightforward. We extend the state of the art in two key aspects: (i) A fully conjugate probabilistic formulation of the kernelized matrix factorization problem enables an efficient variational approximation, whereas fully Bayesian treatments are not computationally feasible in the earlier approaches. (ii) Multiple side information sources are included, treated as different kernels in multiple kernel learning that additionally reveals which side information sources are informative. Our method outperforms alternatives in predicting drug-protein interactions on two data sets. We then show that our framework can also be used for solving multilabel learning problems by considering samples and labels as the two domains where matrix factorization operates on. Our algorithm obtains the lowest Hamming loss values on 10 out of 14 multilabel classification data sets compared to five state-of-the-art multilabel learning algorithms.
Learning the Structure of Sum-Product Networks
Authors: Gens, Robert and Pedro, Domingos
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Sum-product networks (SPNs) are a new class of deep probabilistic models. SPNs can have unbounded treewidth but inference in them is always tractable. An SPN is either a univariate distribution, a product of SPNs over disjoint variables, or a weighted sum of SPNs over the same variables. We propose the first algorithm for learning the structure of SPNs that takes full advantage of their expressiveness. At each step, the algorithm attempts to divide the current variables into approximately independent subsets. If successful, it returns the product of recursive calls on the subsets; otherwise it returns the sum of recursive calls on subsets of similar instances from the current training set. A comprehensive empirical study shows that the learned SPNs are typically comparable to graphical models in likelihood but superior in inference speed and accuracy.
Quantile Regression for Large-scale Applications
Authors: Yang, Jiyan and Meng, Xiangrui and Mahoney, Michael
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Quantile regression is a method to estimate the quantiles of the   conditional distribution of a response variable, and as such it permits a   much more accurate portrayal of the relationship between the response variable   and observed covariates than methods such as Least-squares or   Least Absolute Deviations regression.  It can be expressed as a linear program,   and   interior-point methods can be used to find a solution for  moderately large problems.  Dealing with very large problems, \emphe.g., involving data up to and   beyond the terabyte regime, remains a challenge.  Here, we present a randomized algorithm that runs in time that is nearly   linear in the size of the input and that, with constant probability,   computes a (1+ε) approximate solution to an arbitrary quantile   regression problem.  Our algorithm computes a low-distortion subspace-preserving  embedding with respect to the loss function of quantile regression.  Our empirical evaluation illustrates that our algorithm is competitive with   the best previous work on small to medium-sized problems, and that   it can be implemented in MapReduce-like environments and    applied to terabyte-sized problems.
Robust Regression on MapReduce
Authors: Meng, Xiangrui and Mahoney, Michael
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Although the MapReduce framework is now the \emphde facto standard for   analyzing massive data sets, many algorithms (in particular, many   iterative algorithms popular in machine learning, optimization, and linear   algebra) are hard to fit into MapReduce.   Consider, \emphe.g., the \ell_p regression problem: given a matrix   A ∈\mathbbR^m \times n and a vector b ∈\mathbbR^m, find a   vector x^* ∈\mathbbR^n that minimizes f(x) = \|A x - b\|_p.   The widely-used \ell_2 regression, \emphi.e., linear least-squares, is   known to be highly sensitive to outliers; and choosing p ∈[1, 2) can   help improve robustness.  In this work, we propose an efficient algorithm for solving strongly   over-determined (m ≫n) robust \ell_p regression problems to moderate precision on   MapReduce.  Our empirical results on data up to the terabyte scale demonstrate   that our algorithm is a significant improvement over traditional iterative algorithms on MapReduce   for \ell_1 regression, even for a fairly small number   of iterations.   In addition, our proposed interior-point cutting-plane method can also be   extended to solving more general convex problems on MapReduce.
Infinitesimal Annealing for Training Semi-Supervised Support Vector Machines
Authors: Ogawa, Kohei and Imamura, Motoki and Takeuchi, Ichiro and Sugiyama, Masashi
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The semi-supervised support vector machine (S3VM) is a maximum-margin classification algorithm based on both labeled and unlabeled data. Training S3VM involves either a combinatorial or non-convex optimization problem and thus finding the global optimal solution is intractable in practice. It has been demonstrated that a key to successfully find a good (local) solution of S3VM is to gradually increase the effect of unlabeled data, a la annealing. However, existing algorithms suffer from the trade-off between the resolution of annealing steps and the computation cost. In this paper, we go beyond this trade-off by proposing a novel training algorithm that efficiently performs annealing with an infinitesimal resolution. Through experiments, we demonstrate that the proposed infinitesimal annealing algorithm tends to produce better solutions with less computation time than existing approaches.
One-Pass AUC Optimization
Authors: Gao, Wei and Jin, Rong and Zhu, Shenghuo and Zhou, Zhi-Hua
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: AUC is an important performance measure and many algorithms have been devoted to AUC optimization, mostly by minimizing a surrogate convex loss on a training data set. In this work, we focus on one-pass AUC optimization that requires only going through the training data once without storing the entire training dataset, where conventional online learning algorithms cannot be applied directly because AUC is measured by a sum of losses defined over pairs of instances from different classes. We develop a regression-based algorithm which only needs to maintain the first and second order statistics of training data in memory, resulting a storage requirement independent from the size of training data. To efficiently handle high dimensional data, we develop a randomized algorithm that approximates the covariance matrices by low rank matrices. We verify, both theoretically and empirically, the effectiveness of the proposed algorithm.
Learning Convex QP Relaxations for Structured Prediction
Authors: Jancsary, Jeremy and Nowozin, Sebastian and Rother, Carsten
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We introduce a new large margin approach to discriminative training of intractable discrete graphical models. Our approach builds on a convex quadratic programming relaxation of the MAP inference problem. The model parameters are trained directly within this restricted class of energy functions so as to optimize the predictions on the training data. We address the issue of how to parameterize the resulting model and point out its relation to existing approaches. The primary motivation behind our use of the QP relaxation is its computational efficiency; yet, empirically, its predictive accuracy compares favorably to more expensive approaches. This makes it an appealing choice for many practical tasks.
Concurrent Reinforcement Learning from Customer Interactions
Authors: Silver, David and Newnham, Leonard and Barker, David and Weller, Suzanne and McFall, Jason
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper, we explore applications in which a company interacts concurrently with many customers. The company has an objective function, such as maximising revenue, customer satisfaction, or customer loyalty, which depends primarily on the sequence of interactions between company and customer. A key aspect of this setting is that interactions with different customers occur in parallel. As a result, it is imperative to learn online from partial interaction sequences, so that information acquired from one customer is efficiently assimilated and applied in subsequent interactions with other customers. We present the first framework for concurrent reinforcement learning, using a variant of temporal-difference learning to learn efficiently from partial interaction sequences.   We evaluate our algorithms in two large-scale test-beds for online and email interaction respectively, generated from a database of 300,000 customer records.
Saving Evaluation Time for the Decision Function in Boosting: Representation and Reordering Base Learner
Authors: Sun, Peng and Zhou, Jie
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: For a well trained Boosting classifier, we are interested in how to save the testing time, i.e., to make the decision without evaluating all the base learners. To address this problem, in previous work the base learners are sequentially calculated and early stopping is allowed if the decision function has been confident enough to output its value. In such a chain structure, the order of base learners is critical: better order can lead to less evaluation time.    In this paper, we present a novel method for ordering. We base our discussion on the data structure representing Boosting’s decision function. Viewing the decision function a boolean expression, we propose a Binary Valued Tree for its representation. As a secondary contribution, such a representation unifies the work by previous researchers and helps devise new representation. Also, its connection to Binary Decision Diagram(BDD) is discussed.
Stability and Hypothesis Transfer Learning
Authors: Kuzborskij, Ilja and Orabona, Francesco
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We consider the transfer learning scenario, where the learner does not have access to the source domain directly, but rather operates on the basis of hypotheses induced from it – the Hypothesis Transfer Learning (HTL) problem. Particularly, we conduct a theoretical analysis of HTL by considering the algorithmic stability of a class of HTL algorithms based on Regularized Least Squares with biased regularization. We show that the relatedness of source and target domains accelerates the convergence of the Leave-One-Out error to the generalization error, thus enabling the use of the Leave-One-Out error to find the optimal transfer parameters, even in the presence of a small training set. In case of unrelated domains we also suggest a theoretically principled way to prevent negative transfer, so that in the limit we recover the performance of the algorithm not using any knowledge from the source domain.
Fast Dual Variational Inference for Non-Conjugate Latent Gaussian Models
Authors: Emtiyaz Khan, Mohammad and Aravkin, Aleksandr and Friedlander, Michael and Seeger, Matthias
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Latent Gaussian models (LGMs) are widely used in statistics and machine learning.  Bayesian inference in non-conjugate LGM is difficult due to intractable integrals involving the Gaussian prior and non-conjugate likelihoods.  Algorithms based on Variational Gaussian (VG) approximations are widely employed since they strike a favorable balance between accuracy, generality, speed, and ease of use.  However, the structure of optimization problems associated with them    remains poorly understood, and standard solvers take too long to converge.  In this paper, we derive a novel dual variational inference approach, which exploits the convexity property of the VG approximations.   The implications of our approach is that we obtain an algorithm that solves a convex optimization problem, reduces the number of variational parameters, and converges much faster than previous methods.  Using real world data, we demonstrate these advantages on a variety of LGMs including Gaussian process classification and latent Gaussian Markov random fields.
Modeling Temporal Evolution and Multiscale Structure in Networks
Authors: Herlau, Tue and Mørup, Morten and Schmidt, Mikkel
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Many real-world networks exhibit both temporal evolution and multiscale structure.  We propose a model for temporally correlated multifurcating hierarchies in complex networks which jointly capture both effects. We use the Gibbs fragmentation tree as prior over multifurcating trees and a change-point model to account for the temporal evolution of each vertex.  We demonstrate that our model is able to infer time-varying multiscale structure in synthetic as well as three real world time-evolving complex networks.  Our modeling of the temporal evolution of hierarchies brings new insights into the changing roles and position of entities and possibilities for better understanding these dynamic complex systems.
Dependent Normalized Random Measures
Authors: Chen, Changyou and Rao, Vinayak and Buntine, Wray and Whye Teh, Yee
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper we propose two constructions of dependent normalized random measures, a class of nonparametric priors over dependent probability measures. Our constructions, which we call mixed normalized random measures (MNRM) and thinned normalized random measures (TNRM), involve (respectively) weighting and thinning parts of a shared underlying Poisson process before combining them together. We show that both MNRM and TNRM are marginally normalized random measures, resulting in well understood theoretical properties. We develop marginal and slice samplers for both models, the latter necessary for inference in TNRM. In time-varying topic modelling experiments, both models exhibit superior performance over related dependent models such as the hierarchical Dirichlet process and the spatial normalized Gamma process.
Fast Max-Margin Matrix Factorization with Data Augmentation
Authors: Xu, Minjie and Zhu, Jun and Zhang, Bo
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Existing max-margin matrix factorization (M3F) methods either are computationally inefficient or need a model selection procedure to determine the number of latent factors. In this paper we present a probabilistic M3F model that admits a highly efficient Gibbs sampling algorithm through data augmentation. We further extend our approach to incorporate Bayesian nonparametrics and build accordingly a truncation-free nonparametric M3F model where the number of latent factors is literally unbounded and inferred from data. Empirical studies on two large real-world data sets verify the efficacy of our proposed methods.
Natural Image Bases to Represent Neuroimaging Data
Authors: Gupta, Ashish and Ayhan, Murat and Maida, Anthony
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Visual inspection of neuroimagery is susceptible to human eye limitations.  Computerized methods have been shown to be equally or more effective   than human clinicians in diagnosing dementia from neuroimages. Nevertheless,   much of the work involves the use of domain expertise to extract hand-crafted features. The key technique in this paper is the use of cross-domain features to represent MRI data.  We used a sparse autoencoder to learn a set of bases from natural images and   then applied convolution to extract features from the Alzheimer’s Disease Neuroimaging Initiative (ADNI) dataset.Using this new representation, we classify MRI instances into three categories: Alzheimer’s Disease (AD), Mild Cognitive Impairment (MCI) and Healthy Control (HC).Our approach, in spite of being very simple, achieved high classification performance,   which is competitive with or better than other approaches.
Breaking the Small Cluster Barrier of Graph Clustering
Authors: Ailon, Nir and Chen, Yudong and Xu, Huan
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: This paper investigates graph clustering in the planted cluster model in the   presence of  \em small clusters. Traditional results dictate that for an   algorithm to provably correctly recover the clusters, \em all clusters must be   sufficiently large (in particular, \tildeΩ(\sqrtn) where n is the number   of nodes of the graph). We show that this is not really a restriction: by a more refined   analysis of the trace-norm based matrix recovery approach proposed in (Jalali et al. 2011) and (Chen et al. 2012), we prove that small clusters, under certain mild assuptions, do not hinder recovery of large ones.  Based on this result, we further devise an iterative algorithm   to recover \em almost all clusters via a “peeling strategy”, i.e., recover large clusters   first, leading to a reduced problem, and repeat this procedure.   These results are extended to the    \em partial observation setting, in which only a (chosen) part of the graph is observed.  The peeling strategy gives rise to an active learning algorithm, in which   edges adjacent to smaller clusters are queried more often as large clusters are learned  (and removed).  Our findings are supported by experiments.    From a high level, this paper sheds novel insights on high-dimesional statistics and   learning structured data, by presenting a structured matrix learning problem for which  a one shot convex relaxation approach necessarily fails, but a carefully constructed sequence of convex relaxations  does the job.
Approximate Inference in Collective Graphical Models
Authors: Sheldon, Daniel and Sun, Tao and Kumar, Akshat and Dietterich, Tom
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We study the problem of approximate inference in collective graphical models (CGMs), which were recently introduced to model the problem of learning and inference with noisy aggregate observations. We first analyze the complexity of inference in CGMs: unlike inference in conventional graphical models, exact inference in CGMs is NP-hard even for tree-structured models. We then develop a tractable convex approximation to the NP-hard MAP inference problem in CGMs, and show how to use MAP inference for approximate marginal inference within the EM framework. We demonstrate empirically that these approximation techniques can reduce the computational cost of inference by two orders of magnitude and the cost of learning by at least an order of magnitude while providing solutions of equal or better quality.
Scaling the Indian Buffet Process via Submodular Maximization
Authors: Reed, Colorado and Zoubin, Ghahramani
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Inference for latent feature models is inherently difficult as the inference space grows exponentially with the size of the input data and number of latent features. In this work, we use Kurihara & Wellings (2008)’s maximization-expectation framework to perform approximate MAP inference for linear-Gaussian latent feature models with an Indian Buffet Process (IBP) prior. This formulation yields a submodular function of the features that corresponds to a lower bound on the model evidence. By adding a constant to this function, we obtain a nonnegative submodular function that can be maximized via a greedy algorithm that obtains at least a 1/3-approximation to the optimal solution. Our inference method scales linearly with the size of the input data, and we show the efficacy of our method on the largest datasets currently analyzed using an IBP model.
Mini-Batch Primal and Dual Methods for SVMs
Authors: Takac, Martin and Bijral, Avleen and Richtarik, Peter and Srebro, Nati
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We address the issue of using mini-batches in stochastic  optimization of SVMs. We show that the same quantity, the  spectral norm of the data, controls the parallelization  speedup obtained for both primal stochastic subgradient descent(SGD) and stochastic dual coordinate ascent (SCDA) methods and use it to derive novel variants of mini-batched SDCA. Our guarantees for both methods are expressed in terms of the original nonsmooth primal problem based on the hinge-loss.
The lasso, persistence, and cross-validation
Authors: Homrighausen, Darren and McDonald, Daniel
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: During the last fifteen years, the lasso procedure has been the target of a substantial amount of theoretical and applied research. Correspondingly, many results are known about its behavior for a fixed or optimally chosen smoothing parameter (given up to unknown constants). Much less, however, is known about the lasso’s behavior when the smoothing parameter is chosen in a data dependent way. To this end, we give the first result about the risk consistency of lasso when the smoothing parameter is chosen via cross-validation. We consider the high-dimensional setting wherein the number of predictors p=n^α, α>0 grows with the number of observations.
Spectral Experts for Estimating Mixtures of Linear Regressions
Authors: Tejasvi Chaganty, Arun and Liang, Percy
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Discriminative latent-variable models are typically learned using EM or gradient-based optimization, which suffer from local optima.  In this paper, we develop a new computationally efficient and provably consistent estimator for the mixture of linear regressions, a simple instance of discriminative latent-variable models.  Our approach relies on a low-rank linear regression to recover a symmetric tensor, which can be factorized into the parameters using the tensor power method.  We prove rates of convergence for our estimator and provide an empirical evaluation illustrating its strengths relative to local optimization (EM).
Distribution to Distribution Regression
Authors: Oliva, Junier and Poczos, Barnabas and Schneider, Jeff
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We analyze ’Distribution to Distribution regression’ where one is regressing a mapping where both the covariate (inputs) and response (outputs) are distributions. No parameters on the input or output distributions are assumed, nor are any strong assumptions made on the measure from which input distributions are drawn from. We develop an estimator and derive an upper bound for the L2 risk; also, we show that when the effective dimension is small enough (as measured by the doubling dimension), then the risk converges to zero with a polynomial rate.
Regularization of Neural Networks using DropConnect
Authors: Wan, Li and Zeiler, Matthew and Zhang, Sixin and Le Cun, Yann and Fergus, Rob
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We introduce DropConnect, a generalization of DropOut, for regularizing large fully-connected layers within neural networks. When training with Dropout, a randomly selected subset of activations are set to zero within each layer. DropConnect instead sets a randomly selected subset of weights within the network to zero. Each unit thus receives input from a random subset of units in the previous layer. We derive a bound on the generalization performance of both Dropout and DropConnect. We then evaluate DropConnect on a range of datasets, comparing to Dropout, and show state-of-the-art results on several image recoginition benchmarks can be obtained by aggregating multiple DropConnect-trained models.
Gaussian Process Kernels for Pattern Discovery and Extrapolation
Authors: Wilson, Andrew and Adams, Ryan
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Gaussian processes are rich distributions over functions, which provide a Bayesian nonparametric approach to smoothing and interpolation.  We introduce simple closed form kernels that can be used with Gaussian processes to discover patterns and enable extrapolation.  These kernels are derived by modelling a spectral density – the Fourier transform of a kernel – with a Gaussian mixture.  The proposed kernels support a broad class of stationary covariances, but Gaussian process inference remains simple and analytic.  We demonstrate the proposed kernels by discovering patterns and performing long range extrapolation on synthetic examples, as well as atmospheric CO2 trends and airline passenger data.  We also show that it is possible to reconstruct several popular standard covariances within our framework.
Anytime Representation Learning
Authors: Xu, Zhixiang and Kusner, Matt and Huang, Gao and Weinberger, Kilian
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Evaluation cost during test-time is becoming increasingly important as many real-world applications need fast evaluation (e.g. web search engines, email spam filtering) or use expensive features (e.g. medical diagnosis). We introduce Anytime Feature Representations (AFR), a novel algorithm that explicitly addresses this trade-off in the data representation rather than in the classifier. This enables us to turn conventional classifiers, in particular Support Vector Machines, into test-time cost sensitive <i>anytime classifiers</i> - combining the advantages of anytime learning and large-margin classification.
Algorithms for Direct 0--1 Loss Optimization in Binary Classification
Authors: Nguyen, Tan and Sanner, Scott
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: While convex losses for binary classification are attractive due to the existence of numerous (provably) efficient methods for finding their global optima, they are sensitive to outliers.  On the other hand, while the non-convex 0–1 loss is robust to outliers, it is NP-hard to optimize and thus rarely directly optimized in practice.  In this paper, however, we do just that: we explore a variety of practical methods for direct (approximate) optimization of the 0–1 loss based on branch and bound search, combinatorial search, and coordinate descent on smooth, differentiable relaxations of 0–1 loss. Empirically, we compare our proposed algorithms to logistic regression, SVM, and the Bayes point machine showing that the proposed 0–1 loss optimization algorithms perform at least as well and offer a clear advantage in the presence of outliers.  To this end, we believe this work reiterates the importance of 0–1 loss and its robustness properties while challenging the notion that it is difficult to directly optimize.
Top-k Selection based on Adaptive Sampling of Noisy Preferences
Authors: Busa-Fekete, Robert and Szorenyi, Balazs and Cheng, Weiwei and Weng, Paul and Huellermeier, Eyke
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We consider the problem of reliably selecting an optimal subset of fixed size from a given set of choice alternatives, based on noisy information about the quality of these alternatives. Problems of similar kind have been tackled by means of adaptive sampling schemes called racing algorithms. However, in contrast to existing approaches, we do not assume that each alternative is characterized by a real-valued random variable, and that samples are taken from the corresponding distributions. Instead, we only assume that alternatives can be compared in terms of pairwise preferences. We propose and formally analyze a general preference-based racing algorithm that we instantiate with three specific ranking procedures and corresponding sampling schemes. Experiments with real and synthetic data are presented to show the efficiency of our approach.
The Extended Parameter Filter
Authors: Bugra Erol, Yusuf and Li, Lei and Ramsundar, Bharath and Stuart, Russell
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The parameters of temporal models, such as dynamic Bayesian networks, may be modelled in a Bayesian context as static or atemporal variables that influence transition probabilities at every time step. Particle filters fail for models that include such variables, while methods that use Gibbs sampling of parameter variables may incur a per-sample cost that grows linearly with the length of the observation sequence. Storvik devised a method for incremental computation of exact sufficient statistics that, for some cases, reduces the per-sample cost to a constant.  In this paper, we demonstrate a connection between Storvik’s filter and a Kalman filter in parameter space and establish more general conditions under which Storvik’s filter works. Drawing on an analogy to the extended Kalman filter, we develop and analyze, both theoretically and experimentally, a Taylor approximation to the parameter posterior that allows Storvik’s method to be applied to a broader class of models. Our experiments on both synthetic examples and real applications show improvement over existing methods.
Exploiting Ontology Structures and Unlabeled Data for Learning
Authors: Balcan, Nina and Blum, Avrim and Mansour, Yishay
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We present and analyze a theoretical model designed to understand and  explain the effectiveness of ontologies for learning multiple related  tasks from primarily unlabeled data.  We present both  information-theoretic results as well as efficient algorithms.    We show in this model that an ontology, which specifies the  relationships between multiple outputs, in some cases is sufficient  to completely learn a classification using a large unlabeled data  source.
O(logT) Projections for Stochastic Optimization of Smooth and Strongly Convex Functions
Authors: Zhang, Lijun and Yang, Tianbao and Jin, Rong and He, Xiaofei
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Traditional algorithms for stochastic optimization require projecting the solution at each iteration into a given domain to ensure its feasibility. When facing complex domains, such as the positive semidefinite cone, the projection operation can be expensive, leading to a high computational cost per iteration. In this paper, we present a novel algorithm that aims to reduce the number of projections for stochastic optimization. The proposed algorithm combines the strength of several recent developments in stochastic optimization, including mini-batches, extra-gradient, and epoch gradient descent, in order to effectively explore the smoothness and strong convexity. We show, both in expectation and with a high probability, that when the objective function is both smooth and strongly convex, the proposed algorithm achieves the optimal O(1/T) rate of convergence with only O(logT) projections. Our empirical study verifies the theoretical result.
Optimizing the F-Measure in Multi-Label Classification: Plug-in Rule Approach versus Structured Loss Minimization
Authors: Dembczynski, Krzysztof and Jachnik, Arkadiusz and Kotlowski, Wojciech and Waegeman, Willem and Huellermeier, Eyke
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We compare the plug-in rule approach for optimizing the F-measure in multi-label classification with an approach based on structured loss minimization, such as the structured support vector machine (SSVM). Whereas the former derives an optimal prediction from a probabilistic model in a separate inference step, the latter seeks to optimize the F-measure directly during the training phase. We introduce a novel plug-in rule algorithm that estimates all parameters required for a Bayes-optimal prediction via a set of multinomial regression models, and we compare this algorithm with SSVMs in terms of computational complexity and statistical consistency. As a main theoretical result, we show that our plug-in rule algorithm is consistent, whereas the SSVM approaches are not. Finally, we present results of a large experimental study showing the benefits of the introduced algorithm.
On the importance of initialization and momentum in deep learning
Authors: Sutskever, Ilya and Martens, James and Dahl, George and Hinton, Geoffrey
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Deep and recurrent neural networks (DNNs and RNNs respectively) are powerful models that were considered to be almost impossible to train using stochastic gradient descent with momentum. In this paper, we show that when stochastic gradient descent with momentum uses a well-designed random initialization and a particular type of slowly increasing schedule for the momentum parameter, it can train both DNNs and RNNs (on datasets with long-term dependencies) to levels of performance that were previously achievable only with Hessian-Free optimization. We find that both the initialization and the momentum are crucial since poorly initialized networks cannot be trained with momentum and well-initialized networks perform markedly worse when the momentum is absent or poorly tuned.     Our success training these models suggests that previous attempts to train deep and recurrent neural networks from random initializations have likely failed due to poor initialization schemes. Furthermore, carefully tuned momentum methods suffice for dealing with the curvature issues in deep and recurrent network training objectives without the need for sophisticated second-order methods.