Sagnik Chatterjee

About Me

I am a final-year PhD student in the BraQIIIT lab at IIIT-Delhi, where I am very fortunate to be advised by Prof. Debajyoti Bera. Next, I will be joining as a postdoc at the University of Latvia, Riga, hosted by Prof. Andris Ambainis.

My research

My main area of research lies at the intersection of quantum computing and computational learning theory, and involves developing learning algorithms for discriminative and generative tasks under various noise models and proving theoretical bounds for convergence, generalization, and speedups.

Contact

Office: B-513, R&D block, IIITD
Email: sagnikc[at]iiitd[at]ac[at]in

News

Feb'25: [Upcoming] Invited to present our work on Efficient Quantum Agnostic Improper Learning of Decision Trees at ARCS 2025.
Jan'25: [Upcoming] Visiting Prof. Gunjan Kumar at IIT Kanpur for a research internship.
October'24: Gave a talk on generalization bounds of statistical learning algorithms at the ACMU seminar series, ISI Kolkata.
Aug-Oct'24: Visiting Prof. Sourav Chakraborty at ISI Kolkata for a research internship.
July'24: Presented our work on Efficient Quantum Agnostic Improper Learning of Decision Trees at the Recent trends in Algorithms (RTA) 2024 workshop in IACS, Kolkata.
June'24: Gave a talk on Quantum Learning of Fourier-sparse Boolean functions at the ACMU seminar series, ISI Kolkata.
May'24: Presented our work on Efficient Quantum Agnostic Improper Learning of Decision Trees at AISTATS'24 in Valencia, Spain.
Feb'24: Gave 3 invited lectures on advanced quantum algorithms at the Quantum Computing Semester organized by the CMI, India.
Jan'24: Our paper on Efficient Quantum Agnostic Improper Learning of Decision Trees accepted at AISTATS'24.
Jan'24: Presented a poster on Efficient Quantum Agnostic Improper Learning of Decision Trees at QIP'24 in Taipei, Taiwan.
Jan'24: Teaching Assistant for Theory of Computaton.
Sep'23: Gave a Ketchup talk at IIIT-Delhi.
Sep'23: Gave an invited talk at the IDA seminar in Czech Technical University, Prague.
Sep'23: Gave an invited talk at the University of Latvia, Riga.
Jul-Sep'23: Visiting Czech Technical University, Prague for a research internship.
Jun'23: Our paper on Quantum boosting using domain-partitioning hypotheses accepted at Quantum Machine Intelligence.
Jun'23: Attended the JTG Summer School at IISc Bangalore.
Feb'23: Gave an invited talk on Quantum boosting using domain-partitioning hypotheses at the IIITD CSE Department seminar.
Jan'23: Teaching Assistant for Introduction to Quantum Computing.
Nov'22: Presented our paper Quantum boosting using domain-partitioning hypotheses at QTML'22 in Naples, Italy.
Aug'22: Quantum boosting using domain-partitioning hypotheses accepted at QTML'22 for a short talk.
Apr'22: Qualified my Ph.D. Comprehensive Exam.
Mar'22: Teaching Assistant for Data Structures and Algorithms.
Mar'22: Gave an invited talk on quantum boosting algorithms at the IITD Theoretical CS seminar.
Mar'22: Poster presented at QIP'22.
Dec'21: Organized and conducted the QISE'21 workshop at FSTTCS'21.
Aug'21: Teaching Assistant for Modern Algorithm Design.
Jan'21: Teaching Assistant for Theory of Computation.
Jan'21: Poster presented at QIP'21.
Dec'20: Gave an invited talk on Quantum Machine Learning at the Faculty Development program hosted by JNTU, Anantapur.
Nov'20: Extended Abstract on Applying QAOA+ to the graph matching problem accepted at AQIS'20.
Aug'20: Teaching Assistant for Modern Algorithm Design.
Feb'20: Attended the Boolean Functions workshop at ISI-Kolkata.
Jan'20: Runners-Up in the IBMQ Awards; Teach Me Quantum Category.
Jan'20: Teaching Assistant for Theory of Computation.
Dec'19: Attended the 4th Winter School in CS organized by the IIAS, HUJI in Jerusalem, Israel.

Research ‡

Generalization Bounds for Dependent Data using Online-to-Batch Conversion.

with Manuj Mukherjee and Alhad Sethi.

Under submission.

We give generalization error bounds for statistical learning algorithms trained on non-i.i.d. data in the Online-to-Batch setting.

[arXiv | slides]

Abstract Citation

In this work, we give generalization bounds of statistical learning algorithms trained on samples drawn from a dependent data source both in expectation and with high probability, using the Online-to-Batch conversion paradigm. We show that the generalization error of statistical learners in the dependent data setting is equivalent to the generalization error of statistical learners in the i.i.d. setting up to a term that depends on the decay rate of the underlying mixing stochastic process, and is independent of the complexity of the statistical learner. Our proof techniques involve defining a new notion of stability of online learning algorithms based on Wasserstein distances, and employing ”near-martingale” concentration bounds for dependent random variables to arrive at appropriate upper bounds for the generalization error of statistical learners trained on dependent data.

@misc{chatterjee24b,
title = {Generalization Bounds for Dependent Data using Online-to-Batch Conversion},
author = {Chatterjee, Sagnik and Mukherjee, Manuj and Sethi, Alhad},
year={2024},
eprint={2405.13666},
archivePrefix={arXiv},
}

Efficient Quantum Agnostic Improper Learning of Decision Trees.

with Tharrmashastha SAPV and Debajyoti Bera.

Accepted at AISTATS 2024. Poster at QIP 2024.

We give the first polynomial-time and sample quantum algorithm for agnostically learning Boolean functions with size-\(t\) decision trees representations, w/o membership queries.

[proceedings | arXiv | slides | poster]

Abstract Citation

The agnostic setting is the hardest generalization of the PAC model since it is akin to learning with adversarial noise. In this paper, we give a \(\mathrm{poly}\left(n,{t},{\frac{1}{\varepsilon}}\right)\) time quantum algorithm for learning size \(t\) decision trees with uniform marginal over instances, in the agnostic setting, without membership queries. Our algorithm is the first algorithm (classical or quantum) for learning decision trees in polynomial time without membership queries. We show how to construct a quantum agnostic weak learner by designing a quantum version of the classical Goldreich-Levin algorithm that works with strongly biased function oracles. We show how to quantize the agnostic boosting algorithm by Kalai and Kanade (NIPS'09) to obtain the first efficient quantum agnostic boosting algorithm. Our quantum boosting algorithm has a polynomial improvement in the dependence of the bias of the weak learner over all adaptive quantum boosting algorithms while retaining the standard speedup in the VC dimension over classical boosting algorithms. We then use our quantum boosting algorithm to boost the weak quantum learner we obtained in the previous step to obtain a quantum agnostic learner for decision trees. Using the above framework, we also give quantum decision tree learning algorithms for both the realizable setting and random classification noise model, again without membership queries.

@InProceedings{pmlr-v238-chatterjee24a,
title = { Efficient Quantum Agnostic Improper Learning of Decision Trees },
author = {Chatterjee, Sagnik and SAPV, Tharrmashastha and Bera, Debajyoti},
booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics},
pages = {514--522},
year = {2024},
editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen},
volume = {238},
series = {Proceedings of Machine Learning Research},
month = {02--04 May},
publisher = {PMLR},
url = {https://proceedings.mlr.press/v238/chatterjee24a.html} }

Quantum boosting using domain-partitioning hypotheses.

with Rohan Bhatia, Parmeet Singh-Chani, and Debajyoti Bera.

Published in Quantum Machine Intelligence, 5(2): 1-20 (2023). Short talk at QTML 2022. Poster at QIP 2022.

We answer an open question on the existence of quantum boosting algorithms for weak learners with non-binary hypotheses.

[journal | arXiv | code | poster | slides]

Abstract Citation

Boosting is an ensemble learning method that converts a weak learner into a strong learner in the PAC learning framework. The \(\mathrm{AdaBoost}\) algorithm is a well-known classical boosting algorithm for weak learners with binary hypotheses. Recently, Arunachalam and Maity (ICML'20) presented the first quantum boosting algorithm by quantizing \(\mathrm{AdaBoost}\). Their algorithm, which we refer to as \(\mathrm{QAdaBoost}\) hereafter, is a quantum adaptation of \(\mathrm{AdaBoost}\) and only works for the binary hypothesis case. \(\mathrm{QAdaBoost}\) is quadratically faster than \(\mathrm{AdaBoost}\) in terms of the VC dimension of the hypothesis class of the weak learner while it is polynomially worse in the bias of the weak learner.
In this work, we address an open question by Izdebski et al. on the existence of boosting algorithms for quantum weak learners with non-binary hypotheses. We answer this question in the affirmative by developing the \(\mathrm{QRealBoost}\) algorithm motivated by the classical \(\mathrm{RealBoost}\) algorithm. The main technical challenge was to provide provable guarantees for convergence, generalization bounds, and quantum speedup, given that quantum subroutines are noisy and probabilistic. We prove that \(\mathrm{QRealBoost}\) retains the quadratic speedup of \(\mathrm{QAdaBoost}\) over \(\mathrm{AdaBoost}\) and further achieves a polynomial speedup over \(\mathrm{QAdaBoost}\) in terms of both the bias \(\gamma\) of the learner and the time taken by the learner to learn the target concept class.
Finally, we perform empirical evaluations on \(\mathrm{QRealBoost}\) and report encouraging observations on quantum simulators by benchmarking the convergence performance of \(\mathrm{QRealBoost}\) against \(\mathrm{QAdaBoost}\), \(\mathrm{AdaBoost}\), \(\mathrm{RealBoost}\), and \(\mathrm{SmoothBoost}\) on a subset of the \(\mathrm{MNIST}\) dataset and \(\mathrm{Breast Cancer Wisconsin}\) dataset.

@Article{Chatterjee2023,
author={Chatterjee, Sagnik and Bhatia, Rohan and Singh Chani, Parmeet and Bera, Debajyoti},
title={Quantum boosting using domain-partitioning hypotheses},
journal={Quantum Machine Intelligence},
year={2023},
month={Jul},
day={27},
volume={5},
number={2},
pages={33},
issn={2524-4914},
doi={10.1007/s42484-023-00122-3},
url={https://doi.org/10.1007/s42484-023-00122-3}
}

Applying QAOA+ to the graph matching problem.

with Debajyoti Bera.

Extended Abstract at AQIS'20. Poster at QIP'21.

We show how to design linear depth \(\mathrm{QAOA}+\) style circuits to obtain distributions over all distinct matchings and all maximal matchings for \(2\)-regular graphs through novel mixing operators. We also empirically evaluate the effect of different ansatzes on our QAOA+ circuit.

[arXiv | poster | slides]

Abstract Citation

The Quantum Alternating Operator Ansatz (QAOA+) framework has recently gained attention due to its ability to solve discrete optimization problems on noisy intermediate-scale quantum (NISQ) devices in a manner that is amenable to derivation of worst-case guarantees. We design a technique in this framework to tackle a few problems over maximal matchings in graphs. Even though maximum matching is polynomial-time solvable, most counting and sampling versions are #P-hard. We design a few algorithms that generates superpositions over matchings allowing us to sample from them. In particular, we get a superposition over all possible matchings when given the empty state as input and a superposition over all maximal matchings when given the \(W\)-states as input. Our main result is that the expected size of the matchings corresponding to the output states of our QAOA+ algorithm when ran on a \(2\)-regular graph is greater than the expected matching size obtained from a uniform distribution over all matchings. This algorithm uses a \(W\)-state as input and we prove that this input state is better compared to using the empty matching as the input state.

@article{chatterjee2020applying,
title={Applying the Quantum Alternating Operator Ansatz to the Graph Matching Problem},
author={Chatterjee, Sagnik and Bera, Debajyoti},
journal={arXiv preprint arXiv:2011.11918},
year={2020}
}

‡ See CV for full list.