If asked, what mathematical tools are mostly used in machine learning, one would probably name statistics, probability, or combinatorics. So it is especially pleasing when some other tools, considered rather exotic in this area, find natural applications to ML problems. In this talk, I will speak about an application of (a variant of) topological Radon theorem to an old open problem in theoretical machine learning regarding the existence of the so-called sample compression schemes.

The talk is based on the joint work with Zachary Chase, Steve Hanneke, Shay Moran, and Amir Yehudayoff.

TBD

Probabilistically checkable proofs (PCPs) allow encoding a computation so that it can be quickly verified by only reading a few symbols. Inspired by tree codes (Schulman, STOC'93), we propose tree PCPs; these are PCPs that evolve as the computation progresses so that a proof for time t is obtained by appending a short string to the end of the tree PCP proof for time t-1. At any given time step t, a verifier can make a small number of queries to the entire tree PCP string (constructed thus far) to verify the correctness of the entire computation.

We construct tree PCPs for non-deterministic space-s computation, where at time step t, the proof only grows by an additional poly(s,log(t)) bits, and the number of queries made by the verifier to the overall proof is poly(s)*t^epsilon, for an arbitrary constant epsilon > 0.
 

Tree PCPs are well-suited to proving correctness of ongoing computation that unfolds over time.  They may be thought of as an information-theoretic analog of the cryptographic notion of incrementally verifiable computation (Valiant, TCC'08). We show that, in the random oracle model, tree PCPs can be compiled to realize a variant of incrementally verifiable computation where the prover is allowed a small number of queries to a large evolving state. This yields the first construction of (a natural variant of) IVC in the random oracle model.

This is a joint work with Alon Rosen and Ron D. Rothblum.

Infants gradually learn to recognize and categorize objects, a process that is influenced by language. This talk explores how caregivers' naming of objects, even if inconsistent and unclear, can enhance a child's visual understanding. Using a computer model and a synthetic set of images seen by a toddler-like agent during play, we study how matching images and words over time improves category recognition. Our findings show that small changes in how often objects are named can significantly affect learning, highlighting the importance of aligning visual and language inputs. We also discuss how humans learn relationships between objects. Using a bio-inspired neural network model, we simulate visual experiences to see how objects are grouped based on context, like kitchen or bedroom scenes. Our results reveal that higher network layers group objects by context, while lower layers focus on object identity. This dual approach of matching visuals with words and timing helps explain how we develop semantic knowledge. Overall, this talk suggests computational models to explore the role of language and context in shaping visual and semantic learning in early development.

Bio:
Gemma is a full professor (W3) at the Computer Science Department in Goethe University Frankfurt. She is also a hessian.AI member and affiliated at the Center for Brains Minds and Machines at MIT. Before, she was assistant prof. at Singapore University of Technology and Design. Previously, she was a postdoc fellow at MIT in the Center for Brains Minds and Machines with Prof. Tomaso Poggio. She was also affiliated at the Laboratory for Computational and Statistical Learning. She pursued her doctoral degree in Computer Vision at ETH Zurich.