[Theory] [TTIC Talks] 10/21 Research at TTIC: Aadirupa Saha, TTIC
Brandie Jones
bjones at ttic.edu
Fri Oct 14 13:00:00 CDT 2022
*When:* Friday, October 21st at *12:30pm CT*
*Where:* Talk will be given *live, in-person* at
TTIC, 6045 S. Kenwood Avenue
5th Floor, Room 530
*Virtually:* via Panopto (Livestream
<https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=cb67daa4-5852-479e-9b9b-af1801346ce1>
)
*Who:* Aadirupa Saha, TTIC
*Title:* Dueling-Opt: Convex Optimization with Relative Feedback
*Abstract: *In this talk we will discuss an unconventional version of
the standard bandit convex optimization (BCO) problem with preference
(dueling) feedback---Like the traditional optimization objective, the goal
is to find the minimizer of a convex function with the least possible query
complexity, however, without the luxury of even zeroth-order feedback; here
instead, at each round, the learner can only observe a single noisy 0/1
win-loss feedback for a pair of queried points (based on their underlying
function values). The problem is certainly of great practical relevance in
any real-world system with potentially large (or even infinite) decision
spaces.
The main difficulty in this framework is that any `gradient-descent’ based
technique is bound to fail as it is impossible to estimate gradient
information at any point from a single bit comparison preference feedback
which does not reveal any magnitude information of the underlying cost
function at the queried points. We overcome this challenge by designing a
normalized gradient descent based algorithms and showed near-optimal
convergence rates for smooth and strongly convex functions. Towards the
end, we will consider this problem for a very general class of preference
functions which includes all monotonic functions that can be approximated
by finite degree polynomials. We will conclude the talk with plethora of
open questions led by this general direction of optimization with
`unconventional feedback' which can help bridging the gaps between theory
and practice in many real world applications.
[Based on joint works with Tomer Koren (Tel Aviv Univ and Google), Yishay
Mansour (Tel Aviv Univ and Google)]
*Bio: * Aadirupa is visiting faculty at TTI Chicago. Before this, she
was a postdoctoral researcher at Microsoft Research New York City. She
obtained her Ph.D. from the Department of Computer Science, Indian
Institute of Science, Bangalore, advised by Aditya Gopalan and Chiranjib
Bhattacharyya. Aadirupa was an intern at Microsoft Research, Bangalore,
Inria, Paris, and Google AI, Mountain View.
Her research interests include Bandits, Reinforcement Learning,
Optimization, Learning theory, Algorithms. Off late, she is also very
interested in working on problems in the intersection of ML and Game
theory, Algorithmic fairness, and Privacy.
*Website:* https://aadirupa.github.io/
***********************************************************************************************
*Presence at TTIC requires being fully vaccinated for COVID-19 or having
a TTIC or UChicago-approved exemption. Masks are optional in all common
areas. Full visitor guidance is available at ttic.edu/visitors
<http://ttic.edu/visitors>.*
***********************************************************************************************
*Research at TTIC Seminar Series*
TTIC is hosting a weekly seminar series presenting the research currently
underway at the Institute. Every week a different TTIC faculty member will
present their research. The lectures are intended both for students
seeking research topics and advisors and for the general TTIC and
University of Chicago communities interested in hearing what their
colleagues are up to.
--
*Brandie Jones *
*Administrative Assistant*
Toyota Technological Institute
6045 S. Kenwood Avenue
Chicago, IL 60637
www.ttic.edu
Working Remote on Tuesdays
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20221014/0f3e677b/attachment-0001.html>
More information about the Theory
mailing list