Algorithm Design and Modern Machine Learning (Fall 2025)
Algorithm Design and Modern Machine Learning (Fall 2025)
In modern machine learning, we usually see more highlights of applications like GANs and deep neural networks. However, if we take a deeper look, the foundational connection between algorithm design and machine learning remains critical as ever.
This course aims to explore the interplay between these two fields and demonstrate how they continue to drive innovation together. We will cover how algorithm design helps tackle major challenges in modern machine learning. You will learn the principles behind learning with efficiency to process very large datasets and techniques for learning from noisy, unreliable data. We will also explore how machine learning is facilitating algorithm design. We will examine how concepts originated from data science, e.g., differential privacy, are being integrated into general algorithms. We will also see how machine learning models can be used to dramatically boost the performance of algorithms.
This is a rigorous, proof-based course focused on algorithm design. A solid foundation in algorithms, data structures, and mathematical maturity is required. Expect to spend most of your time with math and proofs in this course.
Course Number: CSCI 4968/6971
Credit Hours: 4.0
Semester / Year: Fall 2025
Lectures: Monday/Thursday 12:00 pm -- 1:50 pm
Room Location: Materials Research Center 136
Prerequisites: CSCI-4020: Design and Analysis of Algorithms or permission of the instructor
For both CSCI 4968 and 6971 students:
Understand the fundamental interplay between algorithm design and modern machine learning
Learn the design and analysis of learning algorithms, including clustering, bandits, and online learning
Learn the mathematical principles for modern learning algorithm design
For 6971 students:
Being able to apply the mathematical principles to learning algorithm design
Exploring the frontier of research in learning algorithm design
Chen Wang
Email: wangc33@rpi.edu (please only use this email address for course-related communications)
Office hours: Wednesdays 3:00 - 4:00 pm at MRC 310
(Announcements will be made if the office hours change for a few special weeks)
Homework/Problem Sets (40%):
One homework every week
Tentatively, 12 homeworks, will take the 9 homeworks with the highest scores
If we ended up handing out x homeworks, we will count x-3 homeworks with the highest scores
No late submission (no exceptions)
Submit your homework with a PDF generated by LaTeX (recommend to use the template provided in the Box link)
For 4968 students: Undergraduate students get a different (easier) problem for each problem set.
Scribe Notes (30%)
I will work with you to prepare scribe notes
The purpose of scribe notes is to provide resources for future study and research
Please use the template provided by the Box link
Due dates:
The first draft is due on the Thursday after the lecture
The final version is due on Thursday two weeks after the lecture
For 4968 students: Depending on the final enrollment, it is possible for undergraduate students to provide scribe notes in teams
Final Project (30%)
For 4968 students: Depending on the final enrollment, it is possible for undergraduate students to work on the project in teams
Week 1: Introduction to the course and motivating examples (slides for RPI students only)
Week 2: Sublinear time algorithms and property testing
Discussions and examples for algorithm applications in modern ML
Sublinear-time algorithms; property testing; max-CSPs; testing sortedness; distribution testing
Streaming algorithms; frequency estimation; turnstile streams; Reservoir sampler; count-min sketch
Metric clustering; coresets; streaming clustering with coresets
Graph algorithms: connectivity, graph streaming, lower bound proofs with communication complexity
Graph learning algorithms: correlation clustering, pivot algorithm, agreement decomposition
Graph learning algorithms: hierarchical clustering, single and average linkage, objective functions (Dasgupta and Moseley-Wang)
Graph clustering in a stream; cut sparsifiers; connections to correlation clustering and hierarchical clustering
Learning with inherent uncertainty; multi-armed bandits; pure exploration and regret minimization
The expert problem and adversarial bandits; MWU; EXP3
Modern considerations in online learning: round of adaptivity and memory constraints; streaming bandits
Learning-augmented algorithms; frequency estimation; learning-augmented MIS
Differential privacy; connection to machine learning; differentially private shortest distances
We do not use any textbook for this course.
The following course materials are related and helpful:
Sublinear Algorithms and Algorithms for Big Data by Sepehr Assadi
Randomized Algorithms by Avrim Blum and Anupam Gupta
Theory of Multi-armed Bandits and Reinforcement Learning by Jiantao Jiao
Machine Learning Algorithms by Rong Ge and Debmalya Panigrahi
The Rensselaer Handbook of Student Rights and Responsibilities and The Graduate Student Supplement define various forms of Academic Dishonesty, and you should make yourself familiar with these. In this class, all assignments that are turned in for a grade must represent the student’s own work. Discussion and resorting to external resources are allowed; however, a notation on the assignment should indicate your collaboration.
Submission of any assignment that is in violation of this policy may result in a penalty of a direct F grade in the course and/or referral to the appropriate Dean (Dean of Students for undergraduate students or the Dean of Graduate Education for graduate students, respectively).
Large language models (LLMs) policy: the usage of large language models is allowed, provided that you are able to understand the generated content and formulate the answer in your own words (please also indicate such usage in your homework -- this will not affect your grade). Please note that directly copying from LLM answers without understanding them could often lead to very clear signals for such violations. If you are suspected of copying from LLMs without understanding them, you will receive a notification from me, and it is your responsibility to justify why it is not the case.
If you have any questions concerning this policy before submitting an assignment, please ask for clarification.
Rensselaer Polytechnic Institute strives to make all learning experiences as accessible as possible. If you anticipate or experience academic barriers based on a disability, please let me know immediately so that we can discuss your options. To establish reasonable accommodations, please register with The Office of Disability Services for Students. After registration, make arrangements with the Director of Disability Services as soon as possible to discuss your accommodations so that they may be implemented in a timely fashion. DSS contact information: dss@rpi.edu; +1-518-276-8197; 4226 Academy Hall.