BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/603
DTSTAMP:20230914T125931Z
SUMMARY:On Stochastic Approximation\, Stochastic Algebraic Topology\, and O
ptimization in High Dimensions
DESCRIPTION:Speaker: Gugan Thoppe\n\nAbstract: \nAbstract: In this talk\,
we shall discuss three problems respectively from stochastic approximation
\, stochastic algebraic topology\, and optimization in high dimensions.\n\
nProblem 1: Stochastic approximation (SA) refers to algorithms that attemp
t to find optimal points or zeroes of a function when only its noisy estim
ates are available. Given $\\epsilon > 0\,$ sample complexity of SA algori
thm is the probability that its iterates are eventually within an $\\epsil
on-$neighbourhood of a desired solution\, conditioned on the event that th
e iterates did enter some bigger neighbourhood of this desired solution. I
n the first part of this talk\, we shall obtain a tight sample complexity
estimate by making use of the Alekseev's analogue of variation of constant
s formula for nonlinear systems and a generalization of a concentration re
sult from Liu and Watbled\, 2009\nProblem 2: In stochastic algebraic topol
ogy\, one is interested in the algebraic topology of random sets. In the s
econd part of this talk\, we shall discuss a time varying analogue of the
Erdos-Renyi graph\, which we call the dynamic Erdos-Renyi graph\, and conc
entrate on the topological aspects of its clique complex. Each edge of the
dynamic Erdos-Renyi graph independently evolves as a continuous time on/o
ff Markov chain such that the connection probability is $p$ at all times.
Our main result is the weak convergence to stationary Ornstein-Uhlenbeck p
rocess of a (normalized) random process determined by $k-$th Betti number
of the clique complex associated with the graph when $p=n^\\alpha\,$ with
$\\alpha \\in (−1/k\,−1/(k+1)).$\n\nProblem 3: High dimensional uncons
trained quadratic programs (UQPs) involving massive datasets are now commo
n. Without computational resources that match up to these datasets\, solvi
ng such problems using classical UQP methods is very difficult. In the thi
rd part of this talk\, we shall first define high dimensional compliant (H
DC) methods for UQPs---methods that can solve high dimensional UQPs by ada
pting to available computational resources. We will then show that the cla
ss of block Kaczmarz and block coordinate descent (BCD) are the only exist
ing methods that can be easily made HDC. We shall then discuss a novel det
erministic\, but adaptive\, greedy BCD (GBCD) method for high dimensional
UQPs. We shall also see theoretical and experimental tests that demonstrat
e the effectiveness of GBCD.\n
URL:https://www.tcs.tifr.res.in/web/events/603
DTSTART;TZID=Asia/Kolkata:20150611T110000
DTEND;TZID=Asia/Kolkata:20150611T120000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR