Establishes Ω(T^{2/3}) regret lower bound for online learning with switching costs under bandit feedback, highlighting the difficulty compared to full-information settings.

Nicolo Cesa-Bianchi, Ofer Dekel, Ohad Shamir

Proposes an equivalence-class-based search space for Bayesian network structure learning, improving greedy search performance.

David Maxwell Chickering

Proposes two efficient models—CBOW and Skip-gram—for large-scale word embedding training, achieving 53.3% accuracy on semantic-syntactic tasks within 3 days on 1.6B words.

Tomas Mikolov, Kai Chen, Greg Corrado et al.

Deep learning detects robotic grasps with 84% and 89% success rates.

Ian Lenz, Honglak Lee, Ashutosh Saxena

Unified geometric framework for Blackwell approachability, regret minimization, and calibration, enabling efficient multi-objective sequential decision strategies.

Vianney Perchet

Expectation Propagation (EP) unifies assumed-density filtering and loopy belief propagation for efficient approximate Bayesian inference in hybrid networks, outperforming Laplace, VB, and Monte Carlo.

Thomas P. Minka

Introduces a weighted averaging scheme in projected stochastic subgradient method achieving O(1/t) convergence, with simple implementation and proof.

Simon Lacoste-Julien, Mark Schmidt, Francis Bach

Introduces non-commutative Khinchin inequalities, relaxes k/n→0 condition for series estimators, establishing pointwise and uniform asymptotic results.

Alexandre Belloni, Victor Chernozhukov, Denis Chetverikov et al.

Regularized reconstruction error enables auto-encoders to learn local features of data distribution, estimating gradients and Hessian matrices.

Guillaume Alain, Yoshua Bengio

Introduces OSNAP, a sparse subspace embedding with dimension O(d^2/ε^2), supporting s=1 sparsity, enabling faster linear algebra algorithms.

Jelani Nelson, Huy L. Nguyen

Introduces an efficient inference algorithm for fully connected CRFs, enhancing image segmentation accuracy.

Philipp Krähenbühl, Vladlen Koltun

Proposes a graph-based discrete signal processing framework using adjacency matrices and Jordan form, enabling spectral analysis for directed and weighted graphs.

Aliaksei Sandryhaila, Jose M. F. Moura

Vovk extends inductive conformal prediction to conditional guarantees and proves that exact object-conditional validity is generally inefficient.

Vladimir Vovk

Combining optimal transport and quantization, the paper derives convergence bounds for learning probability measures supported on manifolds, achieving rates of n^{-1/(2d+4)}.

Guillermo D. Canas, Lorenzo Rosasco

Introduces a variational principle for martingale optimal transport, supporting on two functions with support points ≤3, ensuring uniqueness under continuous marginals.

Mathias Beiglböck, Nicolas Juillet

Proposes a robust, fast recursive algorithm for separable NMF with theoretical guarantees under noise, outperforming existing methods in accuracy and efficiency.

Nicolas Gillis, Stephen A. Vavasis

Introduces ALE platform evaluating 55+ Atari games, combining reinforcement learning and planning for general AI assessment.

Marc G. Bellemare, Yavar Naddaf, Joel Veness et al.

Joint language-perception model using probabilistic grammar and classifiers significantly improves grounded attribute learning, achieving 82% precision in object set selection.

Cynthia Matuszek, Nicholas FitzGerald, Luke Zettlemoyer et al.

Explores causal learning's impact on semi-supervised learning with hypotheses and validation.

Bernhard Schoelkopf, Dominik Janzing, Jonas Peters et al.

Proposes Conservative PC (CPC) algorithm relying only on adjacency faithfulness, improving causal inference accuracy.

Joseph Ramsey, Jiji Zhang, Peter L. Spirtes