Structured Large Scale Machine Learning

In this project we cover three research areas:

1)     Large-scale convex optimization

Large-scale convex optimization for big data: Many classification problems that practitioners are facing have large dimensions: large size of observations p, large number of observations n, large number of classes k. Supervised learning algorithms based on convex optimization (such as the support vector machines or logistic regression) cannot yet achieve robustly the ideal complexity O(nk+np), i.e., the size of the data. To achieve this complexity, we propose several open avenues of research (whose impact on solving large problems with higher accuracy is immediate).

Specifically we intend to focus on i) Large-scale learning with latent structure, ii) Optimal computational-statistical trade-offs, iii) Large-scale learning with large number of classes : scaling in log(k), iv) Large-scale active learning, v) Large-scale learning with large number of classes : dealing with imbalance and vi) Robust stochastic approximation algorithms.

2)      Large-scale combinatorial optimization

Many problems in computer vision or natural language processing involve large-scale combinatorial problems, for example involving graph cuts or submodular functions. We propose several open avenues of research at the interface between combinatorial and convex optimization (whose main impact is to enlarge the set of problems that can be solved through machine learning).

In this context we intend to work on i) Large-scale learning with large number of classes : leveraging the latent geometry; ii) Relationships between convex and combinatorial optimization; and iii)  Structured prediction without pain.

3)     Sequential decision making for structured data

Multi-Armed Bandit (MAB) problems constitute a generic benchmark model for learning to make sequential decisions under uncertainty. They capture the trade-off between exploring decisions to learn the statistical properties of the corresponding rewards, and exploiting decisions that have generated the highest rewards so far. In this project, we aim at investigating bandit problems with a large set of available decisions, with structured rewards. The project addresses bandit problems with known and unknown structure, and targets specific applications in online advertising, recommendation and ranking systems.

 

  • Francis Bach
    Francis Bach
    I am a researcher at INRIA, leading since 2011 the SIERRA project-team, which is part of the Computer Science Laboratory at Ecole Normale ...

Former members:
  • Alekh Agarwal Microsoft Research - New-York
  • Léon Bottou Microsoft Research - Redmond
  • Alexandre d'Aspremont CNRS
  • Miro Dudík Microsoft Research - New-York
  • Zaid Harchaoui Inria Grenoble - Rhône-Alpes
  • Nebojsa Jojic Microsoft Research - Redmond
  • Sham Kakade Microsoft research - New England
  • Pushmeet Kohli Microsoft Research Cambridge
  • Simon Lacoste-Julien Inria Paris-Rocquencourt
  • John Langford Microsoft Research - New-York
  • Sebastian Nowozin Microsoft Research Cambridge
  • Anton Osokin Microsoft Research-Inria Joint Centre (Post Doctoral Student)
  • Anastasia Podosinnikova Microsoft Research - Inria Joint Centre (PHD Student)
  • Alexandre Proutière Inria Paris - Rocquencourt
  • Bozidar Radunovic Microsoft Research cambridge
  • Milan Vojnovic Microsoft Research Cambridge
  • Se-Young Yun Microsoft Research-Inria Joint Centre (Post Doctoral Student)

2019

Pré-publication, Document de travail

titre
An Accelerated Decentralized Stochastic Proximal Algorithm for Finite Sums
auteur
Hadrien Hendrikx, Francis Bach, Laurent Massoulié
article
2019
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02280763/file/1905.11394.pdf BibTex

2018

Pré-publication, Document de travail

titre
Accelerated decentralized optimization with local updates for smooth and strongly convex objectives
auteur
Hadrien Hendrikx, Francis Bach, Laurent Massoulié
article
2018
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01893568/file/1810.02660.pdf BibTex

2017

Communication dans un congrès

titre
Invariance and Stability of Deep Convolutional Representations
auteur
Alberto Bietti, Julien Mairal
article
NIPS 2017 – 31st Conference on Advances in Neural Information Processing Systems, Dec 2017, Los Angeles, CA, United States. pp.1622-1632
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01630265/file/stability-nips.pdf BibTex
titre
Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite-Sum Structure
auteur
Alberto Bietti, Julien Mairal
article
NIPS 2017 – Advances in Neural Information Processing Systems, Dec 2017, Long Beach, CA, United States. pp.1622-1632
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01375816/file/stoch-miso-nips.pdf BibTex

Pré-publication, Document de travail

titre
Optimal algorithms for smooth and strongly convex distributed optimization in networks
auteur
Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, Laurent Massoulié
article
2017
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-01478317/file/distributed_dual_axiv.pdf BibTex

2016

Communication dans un congrès

titre
PAC-Bayesian Theory Meets Bayesian Inference
auteur
Pascal Germain, Francis Bach, Alexandre Lacoste, Simon Lacoste-Julien
article
Neural Information Processing Systems (NIPS 2016), Dec 2016, Barcelone, Spain. pp.1876-1884
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-01324072/file/BPB.pdf BibTex
titre
Breaking Sticks and Ambiguities with Adaptive Skip-gram
auteur
Sergey Bartunov, Dmitry Kondrashkin, Anton Osokin, Dmitry Vetrov
article
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS), May 2016, Cadiz, Spain. pp.130-138
Accès au bibtex
https://arxiv.org/pdf/1502.07257 BibTex
titre
Deep Part-Based Generative Shape Model with Latent Variables
auteur
Alexander Kirillov, Mikhail Gavrikov, Ekaterina Lobacheva, Anton Osokin, Dmitry Vetrov
article
27th British Machine Vision Conference (BMVC 2016), Sep 2016, York, United Kingdom
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-01404071/file/kirillov16.pdf BibTex
titre
Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs
auteur
Anton Osokin, Jean-Baptiste Alayrac, Isabella Lukasewitz, Puneet K. Dokania, Simon Lacoste-Julien
article
International Conference on Machine Learning (ICML 2016)., 2016, New York, United States
Accès au bibtex
https://arxiv.org/pdf/1605.09346 BibTex
titre
Unsupervised Learning from Narrated Instruction Videos
auteur
Jean-Baptiste Alayrac, Piotr Bojanowski, Nishant Agrawal, Josef Sivic, Ivan Laptev, Simon Lacoste-Julien
article
CVPR2016 – 29th IEEE Conference on Computer Vision and Pattern Recognition, Jun 2016, Las Vegas, United States
Accès au bibtex
https://arxiv.org/pdf/1506.09215 BibTex

Pré-publication, Document de travail

titre
Convergence Rate of Frank-Wolfe for Non-Convex Objectives
auteur
Simon Lacoste-Julien
article
2016
Accès au bibtex
https://arxiv.org/pdf/1607.00345 BibTex
titre
Beyond CCA: Moment Matching for Multi-View Models
auteur
Anastasia Podosinnikova, Francis Bach, Simon Lacoste-Julien
article
2016
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01291060/file/cca16.pdf BibTex
titre
Asaga: Asynchronous Parallel Saga
auteur
Rémi Leblond, Fabian Pedregosa, Simon Lacoste-Julien
article
2016
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-01407833/file/1606.04809v1.pdf BibTex

2015

Communication dans un congrès

titre
Fast and Memory Optimal Low-Rank Matrix Approximation
auteur
Yun Se-Young, Marc Lelarge, Alexandre Proutière
article
NIPS 2015, Dec 2015, Montreal, Canada
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-01254913/file/5929-fast-and-memory-optimal-low-rank-matrix-approximation.pdf BibTex
titre
Greedy-Bayes for Targeted News Dissemination
auteur
Laurent Massoulié, Alexandre Proutière, Mesrob Ohannessian
article
SIGMETRICS ’15 Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, Jun 2015, Portland, United States. pp.12, ⟨10.1145/2745844.2745868⟩
Accès au bibtex
BibTex
titre
Is object localization for free? – Weakly-supervised learning with convolutional neural networks
auteur
Maxime Oquab, Léon Bottou, Ivan Laptev, Josef Sivic
article
IEEE Conference on Computer Vision and Pattern Recognition, Jun 2015, Boston, United States
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01015140/file/Oquab15.pdf BibTex
titre
On Pairwise Cost for Multi-Object Network Flow Tracking
auteur
Visesh Chari, Simon Lacoste-Julien, Ivan Laptev, Josef Sivic
article
CVPR 2015 – 28th IEEE Conference on Computer Vision and Pattern Recognition, Jun 2015, Boston, United States
Accès au bibtex
https://arxiv.org/pdf/1408.3304 BibTex
titre
Rethinking LDA: Moment Matching for Discrete ICA
auteur
Anastasia Podosinnikova, Francis Bach, Simon Lacoste-Julien
article
NIPS 2015 – Advances in Neural Information Processing Systems 28, Dec 2015, Montreal, Canada
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01225271/file/lda.pdf BibTex
titre
Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering
auteur
Simon Lacoste-Julien, Fredrik Lindsten, Francis Bach
article
18th International Conference on Artificial Intelligence and Statistics (AISTATS), May 2015, San Diego, United States
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-01099197/file/skh2014.pdf BibTex
titre
On the Global Linear Convergence of Frank-Wolfe Optimization Variants
auteur
Simon Lacoste-Julien, Martin Jaggi
article
NIPS 2015 – Advances in Neural Information Processing Systems 28, Dec 2015, Montreal, Canada
Accès au bibtex
https://arxiv.org/pdf/1511.05932 BibTex
titre
Variance Reduced Stochastic Gradient Descent with Neighbors
auteur
Thomas Hofmann, Aurelien Lucchi, Simon Lacoste-Julien, Brian Mcwilliams
article
NIPS 2015 – Advances in Neural Information Processing Systems 28, Dec 2015, Montreal, Canada
Accès au bibtex
https://arxiv.org/pdf/1506.03662 BibTex
titre
Barrier Frank-Wolfe for Marginal Inference
auteur
Rahul G. Krishnan, Simon Lacoste-Julien, David Sontag
article
NIPS 2015 – Advances in Neural Information Processing Systems 28, Dec 2015, Montreal, Canada
Accès au bibtex
https://arxiv.org/pdf/1511.02124 BibTex

2014

Article dans une revue

titre
Activity representation with motion hierarchies
auteur
Adrien Gaidon, Zaid Harchaoui, Cordelia Schmid
article
International Journal of Computer Vision, Springer Verlag, 2014, 107 (3), pp.219-238. ⟨10.1007/s11263-013-0677-1⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-00908581/file/tracklets_journal.pdf BibTex

Communication dans un congrès

titre
SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
auteur
Aaron Defazio, Francis Bach, Simon Lacoste-Julien
article
Advances In Neural Information Processing Systems, Nov 2014, Montreal, Canada
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-01016843/file/nips2014.pdf BibTex
titre
Category-specific video summarization
auteur
Danila Potapov, Matthijs Douze, Zaid Harchaoui, Cordelia Schmid
article
ECCV – European Conference on Computer Vision, Sep 2014, Zurich, Switzerland. pp.540-555, ⟨10.1007/978-3-319-10599-4_35⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01022967/file/video_summarization.pdf BibTex
titre
Learning and Transferring Mid-Level Image Representations using Convolutional Neural Networks
auteur
Maxime Oquab, Léon Bottou, Ivan Laptev, Josef Sivic
article
IEEE Conference on Computer Vision and Pattern Recognition, Jun 2014, Columbus, OH, United States
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-00911179/file/oquab14.pdf BibTex
titre
Mixing Body-Part Sequences for Human Pose Estimation
auteur
Anoop Cherian, Julien Mairal, Karteek Alahari, Cordelia Schmid
article
CVPR – IEEE Conference on Computer Vision & Pattern Recognition, Jun 2014, Columbus, OH, United States. pp. 2361-2368, ⟨10.1109/CVPR.2014.302⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-00978643/file/posecvpr2014.pdf BibTex
titre
Streaming, Memory Limited Algorithms for Community Detection
auteur
Se-Young Yun, Marc Lelarge, Alexandre Proutière
article
NIPS 2014, Dec 2014, Montreal, Canada
Accès au bibtex
https://arxiv.org/pdf/1411.1279 BibTex

2013

Article dans une revue

titre
Temporal Localization of Actions with Actoms
auteur
Adrien Gaidon, Zaid Harchaoui, Cordelia Schmid
article
IEEE Transactions on Pattern Analysis and Machine Intelligence, Institute of Electrical and Electronics Engineers, 2013, 35 (11), pp.2782-2795. ⟨10.1109/TPAMI.2013.65⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-00804627/file/ASM_TPAMI_Gaidon.pdf BibTex

2012

Communication dans un congrès

titre
Recognizing activities with cluster-trees of tracklets
auteur
Adrien Gaidon, Zaid Harchaoui, Cordelia Schmid
article
BMVC 2012 – British Machine Vision Conference, Sep 2012, Guildford, United Kingdom. pp.30.1-30.13, ⟨10.5244/C.26.30⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-00722955/file/gaidon_tracklets_bmvc2012.pdf BibTex

Rapport

titre
Temporal Localization of Actions with Actoms
auteur
Adrien Gaidon, Zaid Harchaoui, Cordelia Schmid
article
[Research Report] RR-7930, INRIA. 2012
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-00687312/file/RR-7930.pdf BibTex

2011

Communication dans un congrès

titre
Actom Sequence Models for Efficient Action Detection
auteur
Adrien Gaidon, Zaid Harchaoui, Cordelia Schmid
article
CVPR 2011 – IEEE Conference on Computer Vision & Pattern Recognition, Jun 2011, Colorado Springs, United States. pp.3201-3208, ⟨10.1109/CVPR.2011.5995646⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00575217/file/1513.pdf BibTex
titre
A time series kernel for action recognition
auteur
Adrien Gaidon, Zaid Harchaoui, Cordelia Schmid
article
BMVC 2011 – British Machine Vision Conference, Aug 2011, Dundee, United Kingdom. pp.63.1-63.11, ⟨10.5244/C.25.63⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00613089/file/kernel_time_series.pdf BibTex

2006

Article dans une revue

titre
A Queueing Analysis of Max-Min Fairness, Proportional Fairness and Balanced Fairness
auteur
Thomas Bonald, Laurent Massoulié, Alexandre Proutière, Jorma Virtamo
article
Queueing Systems, Springer Verlag, 2006, ⟨10.1007/s11134-006-7587-7⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01244245/file/questa06.pdf BibTex