pwc-archive/papers-with-abstracts huggingface dataset:
Regularized linear system identification using atomic, nuclear and kernel-based norms: the role of the stability constraint
Authors: Gianluigi Pillonetto, Tianshi Chen, Alessandro Chiuso, Giuseppe De Nicolao, Lennart Ljung
Date: 2015-07-02 00:00:00

Inspired by ideas taken from the machine learning literature, new
regularization techniques have been recently introduced in linear system
identification. In particular, all the adopted estimators solve a regularized
least squares problem, differing in the nature of the penalty term assigned to
the impulse response. Popular choices include atomic and nuclear norms (applied
to Hankel matrices) as well as norms induced by the so called stable spline
kernels. In this paper, a comparative study of estimators based on these
different types of regularizers is reported. Our findings reveal that stable
spline kernels outperform approaches based on atomic and nuclear norms since
they suitably embed information on impulse response stability and smoothness.
This point is illustrated using the Bayesian interpretation of regularization.
We also design a new class of regularizers defined by "integral" versions of
stable spline/TC kernels. Under quite realistic experimental conditions, the
new estimators outperform classical prediction error methods also when the
latter are equipped with an oracle for model order selection.
Classical vs. Bayesian methods for linear system identification: point estimators and confidence sets
Authors: D. Romeres, G. Prando, G. Pillonetto, A. Chiuso
Date: 2015-07-02 00:00:00

This paper compares classical parametric methods with recently developed
Bayesian methods for system identification. A Full Bayes solution is considered
together with one of the standard approximations based on the Empirical Bayes
paradigm. Results regarding point estimators for the impulse response as well
as for confidence regions are reported.
Learning the intensity of time events with change-points
Authors: Mokhtar Zahdi Alaya, Stéphane Gaïffas, Agathe Guilloux
Date: 2015-07-02 00:00:00
Tasks: Segmentation

We consider the problem of learning the inhomogeneous intensity of a counting
process, under a sparse segmentation assumption. We introduce a weighted
total-variation penalization, using data-driven weights that correctly scale
the penalization along the observation interval. We prove that this leads to a
sharp tuning of the convex relaxation of the segmentation prior, by stating
oracle inequalities with fast rates of convergence, and consistency for
change-points detection. This provides first theoretical guarantees for
segmentation with a convex proxy beyond the standard i.i.d signal + white noise
setting. We introduce a fast algorithm to solve this convex problem. Numerical
experiments illustrate our approach on simulated and on a high-frequency
genomics dataset.
Identification of stable models via nonparametric prediction error methods
Authors: Diego Romeres, Gianluigi Pillonetto, Alessandro Chiuso
Date: 2015-07-02 00:00:00

A new Bayesian approach to linear system identification has been proposed in
a series of recent papers. The main idea is to frame linear system
identification as predictor estimation in an infinite dimensional space, with
the aid of regularization/Bayesian techniques. This approach guarantees the
identification of stable predictors based on the prediction error minimization.
Unluckily, the stability of the predictors does not guarantee the stability of
the impulse response of the system. In this paper we propose and compare
various techniques to address this issue. Simulations results comparing these
techniques will be provided.
Distributed image reconstruction for very large arrays in radio astronomy
Authors: André Ferrari, David Mary, Rémi Flamary, Cédric Richard
Date: 2015-07-02 00:00:00
Tasks: Astronomy, Image Reconstruction

Current and future radio interferometric arrays such as LOFAR and SKA are
characterized by a paradox. Their large number of receptors (up to millions)
allow theoretically unprecedented high imaging resolution. In the same time,
the ultra massive amounts of samples makes the data transfer and computational
loads (correlation and calibration) order of magnitudes too high to allow any
currently existing image reconstruction algorithm to achieve, or even approach,
the theoretical resolution. We investigate here decentralized and distributed
image reconstruction strategies which select, transfer and process only a
fraction of the total data. The loss in MSE incurred by the proposed approach
is evaluated theoretically and numerically on simple test cases.
Non-convex Regularizations for Feature Selection in Ranking With Sparse SVM
Authors: Léa Laporte, Rémi Flamary, Stephane Canu, Sébastien Déjean, Josiane Mothe
Date: 2015-07-02 00:00:00
Tasks: feature selection, Learning-To-Rank

Feature selection in learning to rank has recently emerged as a crucial
issue. Whereas several preprocessing approaches have been proposed, only a few
works have been focused on integrating the feature selection into the learning
process. In this work, we propose a general framework for feature selection in
learning to rank using SVM with a sparse regularization term. We investigate
both classical convex regularizations such as $\ell\_1$ or weighted $\ell\_1$
and non-convex regularization terms such as log penalty, Minimax Concave
Penalty (MCP) or $\ell\_p$ pseudo norm with $p\textless{}1$. Two algorithms are
proposed, first an accelerated proximal approach for solving the convex
problems, second a reweighted $\ell\_1$ scheme to address the non-convex
regularizations. We conduct intensive experiments on nine datasets from Letor
3.0 and Letor 4.0 corpora. Numerical results show that the use of non-convex
regularizations we propose leads to more sparsity in the resulting models while
prediction performance is preserved. The number of features is decreased by up
to a factor of six compared to the $\ell\_1$ regularization. In addition, the
software is publicly available on the web.
DC Proximal Newton for Non-Convex Optimization Problems
Authors: Alain Rakotomamonjy, Remi Flamary, Gilles Gasso
Date: 2015-07-02 00:00:00
Tasks: Transductive Learning

We introduce a novel algorithm for solving learning problems where both the
loss function and the regularizer are non-convex but belong to the class of
difference of convex (DC) functions. Our contribution is a new general purpose
proximal Newton algorithm that is able to deal with such a situation. The
algorithm consists in obtaining a descent direction from an approximation of
the loss function and then in performing a line search to ensure sufficient
descent. A theoretical analysis is provided showing that the iterates of the
proposed algorithm {admit} as limit points stationary points of the DC
objective function. Numerical experiments show that our approach is more
efficient than current state of the art for a problem with a convex loss
functions and non-convex regularizer. We have also illustrated the benefit of
our algorithm in high-dimensional transductive learning problem where both loss
function and regularizers are non-convex.
Gaussian Process for Noisy Inputs with Ordering Constraints
Authors: Cuong Tran, Vladimir Pavlovic, Robert Kopp
Date: 2015-06-30 00:00:00

We study the Gaussian Process regression model in the context of training
data with noise in both input and output. The presence of two sources of noise
makes the task of learning accurate predictive models extremely challenging.
However, in some instances additional constraints may be available that can
reduce the uncertainty in the resulting predictive models. In particular, we
consider the case of monotonically ordered latent input, which occurs in many
application domains that deal with temporal data. We present a novel inference
and learning approach based on non-parametric Gaussian variational
approximation to learn the GP model while taking into account the new
constraints. The resulting strategy allows one to gain access to posterior
estimates of both the input and the output and results in improved predictive
performance. We compare our proposed models to state-of-the-art Noisy Input
Gaussian Process (NIGP) and other competing approaches on synthetic and real
sea-level rise data. Experimental results suggest that the proposed approach
consistently outperforms selected methods while, at the same time, reducing the
computational costs of learning and inference.
Categorical Matrix Completion
Authors: Yang Cao, Yao Xie
Date: 2015-07-02 00:00:00
Tasks: Matrix Completion

We consider the problem of completing a matrix with categorical-valued
entries from partial observations. This is achieved by extending the
formulation and theory of one-bit matrix completion. We recover a low-rank
matrix $X$ by maximizing the likelihood ratio with a constraint on the nuclear
norm of $X$, and the observations are mapped from entries of $X$ through
multiple link functions. We establish theoretical upper and lower bounds on the
recovery error, which meet up to a constant factor $\mathcal{O}(K^{3/2})$ where
$K$ is the fixed number of categories. The upper bound in our case depends on
the number of categories implicitly through a maximization of terms that
involve the smoothness of the link functions. In contrast to one-bit matrix
completion, our bounds for categorical matrix completion are optimal up to a
factor on the order of the square root of the number of categories, which is
consistent with an intuition that the problem becomes harder when the number of
categories increases. By comparing the performance of our method with the
conventional matrix completion method on the MovieLens dataset, we demonstrate
the advantage of our method.
Scale-Free Algorithms for Online Linear Optimization
Authors: Francesco Orabona, David Pal
Date: 2015-02-19 00:00:00

We design algorithms for online linear optimization that have optimal regret
and at the same time do not need to know any upper or lower bounds on the norm
of the loss vectors. We achieve adaptiveness to norms of loss vectors by scale
invariance, i.e., our algorithms make exactly the same decisions if the
sequence of loss vectors is multiplied by any positive constant. Our algorithms
work for any decision set, bounded or unbounded. For unbounded decisions sets,
these are the first truly adaptive algorithms for online linear optimization.
Learning Privately with Labeled and Unlabeled Examples
Authors: Amos Beimel, Kobbi Nissim, Uri Stemmer
Date: 2014-07-10 00:00:00
Tasks: Active Learning

A private learner is an algorithm that given a sample of labeled individual
examples outputs a generalizing hypothesis while preserving the privacy of each
individual. In 2008, Kasiviswanathan et al. (FOCS 2008) gave a generic
construction of private learners, in which the sample complexity is (generally)
higher than what is needed for non-private learners. This gap in the sample
complexity was then further studied in several followup papers, showing that
(at least in some cases) this gap is unavoidable. Moreover, those papers
considered ways to overcome the gap, by relaxing either the privacy or the
learning guarantees of the learner.
  We suggest an alternative approach, inspired by the (non-private) models of
semi-supervised learning and active-learning, where the focus is on the sample
complexity of labeled examples whereas unlabeled examples are of a
significantly lower cost. We consider private semi-supervised learners that
operate on a random sample, where only a (hopefully small) portion of this
sample is labeled. The learners have no control over which of the sample
elements are labeled. Our main result is that the labeled sample complexity of
private learners is characterized by the VC dimension.
  We present two generic constructions of private semi-supervised learners. The
first construction is of learners where the labeled sample complexity is
proportional to the VC dimension of the concept class, however, the unlabeled
sample complexity of the algorithm is as big as the representation length of
domain elements. Our second construction presents a new technique for
decreasing the labeled sample complexity of a given private learner, while
roughly maintaining its unlabeled sample complexity. In addition, we show that
in some settings the labeled sample complexity does not depend on the privacy
parameters of the learner.
An Empirical Evaluation of True Online TD(λ)
Authors: Harm van Seijen, A. Rupam Mahmood, Patrick M. Pilarski, Richard S. Sutton
Date: 2015-07-01 00:00:00
Tasks: Reinforcement Learning

The true online TD({\lambda}) algorithm has recently been proposed (van
Seijen and Sutton, 2014) as a universal replacement for the popular
TD({\lambda}) algorithm, in temporal-difference learning and reinforcement
learning. True online TD({\lambda}) has better theoretical properties than
conventional TD({\lambda}), and the expectation is that it also results in
faster learning. In this paper, we put this hypothesis to the test.
Specifically, we compare the performance of true online TD({\lambda}) with that
of TD({\lambda}) on challenging examples, random Markov reward processes, and a
real-world myoelectric prosthetic arm. We use linear function approximation
with tabular, binary, and non-binary features. We assess the algorithms along
three dimensions: computational cost, learning speed, and ease of use. Our
results confirm the strength of true online TD({\lambda}): 1) for sparse
feature vectors, the computational overhead with respect to TD({\lambda}) is
minimal; for non-sparse features the computation time is at most twice that of
TD({\lambda}), 2) across all domains/representations the learning speed of true
online TD({\lambda}) is often better, but never worse than that of
TD({\lambda}), and 3) true online TD({\lambda}) is easier to use, because it
does not require choosing between trace types, and it is generally more stable
with respect to the step-size. Overall, our results suggest that true online
TD({\lambda}) should be the first choice when looking for an efficient,
general-purpose TD method.
Exploring Algorithmic Limits of Matrix Rank Minimization under Affine Constraints
Authors: Bo Xin, David Wipf
Date: 2014-06-10 00:00:00
Tasks: Collaborative Filtering, Matrix Completion

Many applications require recovering a matrix of minimal rank within an
affine constraint set, with matrix completion a notable special case. Because
the problem is NP-hard in general, it is common to replace the matrix rank with
the nuclear norm, which acts as a convenient convex surrogate. While elegant
theoretical conditions elucidate when this replacement is likely to be
successful, they are highly restrictive and convex algorithms fail when the
ambient rank is too high or when the constraint set is poorly structured.
Non-convex alternatives fare somewhat better when carefully tuned; however,
convergence to locally optimal solutions remains a continuing source of
failure. Against this backdrop we derive a deceptively simple and
parameter-free probabilistic PCA-like algorithm that is capable, over a wide
battery of empirical tests, of successful recovery even at the theoretical
limit where the number of measurements equal the degrees of freedom in the
unknown low-rank matrix. Somewhat surprisingly, this is possible even when the
affine constraint set is highly ill-conditioned. While proving general recovery
guarantees remains evasive for non-convex algorithms, Bayesian-inspired or
otherwise, we nonetheless show conditions whereby the underlying cost function
has a unique stationary point located at the global optimum; no existing cost
function we are aware of satisfies this same property. We conclude with a
simple computer vision application involving image rectification and a standard
collaborative filtering benchmark.
A Chaining Algorithm for Online Nonparametric Regression
Authors: Pierre Gaillard, Sébastien Gerchinovitz
Date: 2015-02-26 00:00:00
Tasks: Computational Efficiency, regression

We consider the problem of online nonparametric regression with arbitrary
deterministic sequences. Using ideas from the chaining technique, we design an
algorithm that achieves a Dudley-type regret bound similar to the one obtained
in a non-constructive fashion by Rakhlin and Sridharan (2014). Our regret bound
is expressed in terms of the metric entropy in the sup norm, which yields
optimal guarantees when the metric and sequential entropies are of the same
order of magnitude. In particular our algorithm is the first one that achieves
optimal rates for online regression over H{\"o}lder balls. In addition we show
for this example how to adapt our chaining algorithm to get a reasonable
computational efficiency with similar regret guarantees (up to a log factor).
Pose Embeddings: A Deep Architecture for Learning to Match Human Poses
Authors: Greg Mori, Caroline Pantofaru, Nisarg Kothari, Thomas Leung, George Toderici, Alexander Toshev, Weilong Yang
Date: 2015-07-01 00:00:00
Tasks: Retrieval, Triplet

We present a method for learning an embedding that places images of humans in
similar poses nearby. This embedding can be used as a direct method of
comparing images based on human pose, avoiding potential challenges of
estimating body joint positions. Pose embedding learning is formulated under a
triplet-based distance criterion. A deep architecture is used to allow learning
of a representation capable of making distinctions between different poses.
Experiments on human pose matching and retrieval from video data demonstrate
the potential of the method.
Bootstrapped Thompson Sampling and Deep Exploration
Authors: Ian Osband, Benjamin Van Roy
Date: 2015-07-01 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Thompson Sampling

This technical note presents a new approach to carrying out the kind of
exploration achieved by Thompson sampling, but without explicitly maintaining
or sampling from posterior distributions. The approach is based on a bootstrap
technique that uses a combination of observed and artificially generated data.
The latter serves to induce a prior distribution which, as we will demonstrate,
is critical to effective exploration. We explain how the approach can be
applied to multi-armed bandit and reinforcement learning problems and how it
relates to Thompson sampling. The approach is particularly well-suited for
contexts in which exploration is coupled with deep learning, since in these
settings, maintaining or generating samples from a posterior distribution
becomes computationally infeasible.
Energy-efficient neuromorphic classifiers
Authors: Daniel Martí, Mattia Rigotti, Mingoo Seok, Stefano Fusi
Date: 2015-07-01 00:00:00

Neuromorphic engineering combines the architectural and computational
principles of systems neuroscience with semiconductor electronics, with the aim
of building efficient and compact devices that mimic the synaptic and neural
machinery of the brain. Neuromorphic engineering promises extremely low energy
consumptions, comparable to those of the nervous system. However, until now the
neuromorphic approach has been restricted to relatively simple circuits and
specialized functions, rendering elusive a direct comparison of their energy
consumption to that used by conventional von Neumann digital machines solving
real-world tasks. Here we show that a recent technology developed by IBM can be
leveraged to realize neuromorphic circuits that operate as classifiers of
complex real-world stimuli. These circuits emulate enough neurons to compete
with state-of-the-art classifiers. We also show that the energy consumption of
the IBM chip is typically 2 or more orders of magnitude lower than that of
conventional digital machines when implementing classifiers with comparable
performance. Moreover, the spike-based dynamics display a trade-off between
integration time and accuracy, which naturally translates into algorithms that
can be flexibly deployed for either fast and approximate classifications, or
more accurate classifications at the mere expense of longer running times and
higher energy costs. This work finally proves that the neuromorphic approach
can be efficiently used in real-world applications and it has significant
advantages over conventional digital devices when energy consumption is
considered.
Bigeometric Organization of Deep Nets
Authors: Alexander Cloninger, Ronald R. Coifman, Nicholas Downing, Harlan M. Krumholz
Date: 2015-07-01 00:00:00

In this paper, we build an organization of high-dimensional datasets that
cannot be cleanly embedded into a low-dimensional representation due to missing
entries and a subset of the features being irrelevant to modeling functions of
interest. Our algorithm begins by defining coarse neighborhoods of the points
and defining an expected empirical function value on these neighborhoods. We
then generate new non-linear features with deep net representations tuned to
model the approximate function, and re-organize the geometry of the points with
respect to the new representation. Finally, the points are locally z-scored to
create an intrinsic geometric organization which is independent of the
parameters of the deep net, a geometry designed to assure smoothness with
respect to the empirical function. We examine this approach on data from the
Center for Medicare and Medicaid Services Hospital Quality Initiative, and
generate an intrinsic low-dimensional organization of the hospitals that is
smooth with respect to an expert driven function of quality.
Natural Neural Networks
Authors: Guillaume Desjardins, Karen Simonyan, Razvan Pascanu, Koray Kavukcuoglu
Date: 2015-07-01 00:00:00
Proceeding: NeurIPS 2015 12

We introduce Natural Neural Networks, a novel family of algorithms that speed
up convergence by adapting their internal representation during training to
improve conditioning of the Fisher matrix. In particular, we show a specific
example that employs a simple and efficient reparametrization of the neural
network weights by implicitly whitening the representation obtained at each
layer, while preserving the feed-forward computation of the network. Such
networks can be trained efficiently via the proposed Projected Natural Gradient
Descent algorithm (PRONG), which amortizes the cost of these reparametrizations
over many parameter updates and is closely related to the Mirror Descent online
learning algorithm. We highlight the benefits of our method on both
unsupervised and supervised learning tasks, and showcase its scalability by
training on the large-scale ImageNet Challenge dataset.
Dimensionality on Summarization
Authors: Hai Zhuge
Date: 2015-07-01 00:00:00
Tasks: Text Summarization

Summarization is one of the key features of human intelligence. It plays an
important role in understanding and representation. With rapid and continual
expansion of texts, pictures and videos in cyberspace, automatic summarization
becomes more and more desirable. Text summarization has been studied for over
half century, but it is still hard to automatically generate a satisfied
summary. Traditional methods process texts empirically and neglect the
fundamental characteristics and principles of language use and understanding.
This paper summarizes previous text summarization approaches in a
multi-dimensional classification space, introduces a multi-dimensional
methodology for research and development, unveils the basic characteristics and
principles of language use and understanding, investigates some fundamental
mechanisms of summarization, studies the dimensions and forms of
representations, and proposes a multi-dimensional evaluation mechanisms.
Investigation extends to the incorporation of pictures into summary and to the
summarization of videos, graphs and pictures, and then reaches a general
summarization framework.