"Recent Advances in Strongly Polynomial Algorithms for Linear Programming"

Abstract

Whereas ellipsoid methods and interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the simplex method that always admits an exponential bound. 
 
An important unresolved question in operations research, theoretical computer science, and related fields, concerns the existence of a strongly polynomial algorithm for linear programming. Such an algorithm's running time would solely depend on the problem's dimension and the number of constraints, independent of any additional condition numbers. This question, first articulated by Megiddo in the 1980s, has gained prominence as Smale's 9th problem.
 
In the first part of our talk, we introduce a new polynomial-time path-following interior point method where the number of iterations admits a combinatorial upper bound that is exponential in the number of constraints. More precisely, the iteration count of our algorithm is at most a small polynomial factor times the segment count of any piecewise linear trajectory within a wide neighborhood of the central path. Notably, it parallels the iteration count of any path-following interior point method, with an adjustment for this polynomial factor.
 
In the second part of our talk, we give a strongly polynomial algorithm for minimum cost generalized flow, and hence all linear programs with at most two nonzero entries per row, or at most two nonzero entries per column. This provides a next milestone towards answering Smale’s 9th problem.

Biography

Bento Natura is a Ronald J. and Carol T. Beerman/ARC Postdoctoral Fellow in ISyE at Georgia Tech. He obtained his PhD in the Department of Mathematics at the London School of Economics, where he was supervised by László Végh. His doctoral thesis earned him the departmental Dissertation Prize and placed as a runner-up for the PhD Prize awarded by the OR Society of the United Kingdom. Prior to his PhD, Bento earned Bachelor's and Master's degrees in Mathematics from the University of Bonn, under the supervision of Stephan Held and Jens Vygen. Bento's current research interests are centered on algorithms, optimization, and game theory.

Research Interests/Area

Algorithms and Optimization

"Modeling Uncertainty for Designing Efficient Algorithms for Machine Learning"

Abstract

Though modern machine learning has been highly successful, as we move towards more critical applications, many challenges towards ensuring robustness, privacy, and fairness, arise. Ad hoc and empirical approaches have often led to unintended consequences for these objectives, thus necessitating a principled approach. Traditional solutions often require redesigning entire pipelines or come with a significant loss in quality. In this talk, we will look at principles for modeling data towards can incorporating these important desiderata into existing pipelines without significant computational and statistical overhead.

We will see two vignettes of this line of research. First, the smoothed adversary model for sequential decision making, leading to statistically and computationally efficient algorithms for decision making under uncertainty. Second, we will see a nearly linear-time algorithm for distribution compression leading to improved computational efficiency in diverse downstream statistical tasks. 

 
 Biography

Abhishek Shetty is currently a PhD student in the Department of Computer Science at the University of California at Berkeley advised by Nika Haghtalab. His research focuses on designing mathematical frameworks bringing together the theory and practice of machine learning and using these to developing simple algorithms with provable guarantees on real-world data. His research has been awarded a American Statistical Association SCSG best student paper award and also the Apple AI/ML fellowship.

Research Interests/Area

Theory/Machine Learning

"Theoretical understanding of learning through the computational lens"

Abstract

One of the major mysteries in science is the towering success of machine learning. In this talk, I will present my work on advancing our theoretical understanding of learning and intelligence through the computational perspective. First, I will talk about the fundamental role of memory in learning, highlighting its importance in continual learning as well as decision making and optimization. Second, I will present an exponential improvement in swap-regret minimization algorithms, which achieves near-optimal computation/communication/iteration complexity for computing a correlated equilibrium, and implies the first polynomial-time algorithm for games with an exponentially large action space (e.g. Bayesian and extensive-form games). Finally, I will talk about learning over evolving data, and conclude the talk with future research directions and my vision for a computational understanding of learning.

Biography

Binghui Peng is a fifth year Ph.D. student at Columbia University, advised by Christos Papadimitriou and Xi Chen. Previously, he studied Computer Science with the Yao Class in Tsinghua. He studies the theory of computation and develops algorithms and complexity theory for machine learning, artificial intelligence and game theory. His research works have addressed long-standing questions in learning theory and game theory, and his research papers were published in theory conferences (STOC/FOCS/SODA; in the latter he has best student paper award) and ML conferences (NeurIPS/ICLR/ACL).

Research Interests/Area

Theory

CS Department Events

CSPAC Workshop Series

Other Events & Opportunities

Northwestern Medicine Healthcare AI Forum

 IEMS dIvErsion

What's Poppin'? "Am I Black Enough? Black Card Revoked"

3rd Annual Traditional Spring Pow Wow- Hosted by NAISA

CS News

NU News