Session: Large-scale optimization for data science
Chair: Jason Altschuler
Cluster: Optimization For Data Science
Talk 1: Preconditioning for Linear Regression and Kernel Methods: The State of Play
Speaker: Ethan Epperly
Abstract: Simple models like linear regression and kernel methods continue to be powerful tools for learning from data. For large-scale problems, the state-of-art algorithms for these models use iterative methods with randomized preconditioning. This talk surveys the best-known preconditioners for these models, discusses recent advances, and describes open problems.
Talk 2: Balancing Regret and Runtime: Faster Iterative Projections over Submodular Base Polytopes
Speaker: Jai Moondra
Abstract: Optimization algorithms like projected Newton’s method, FISTA, and Mirror Descent achieve near-optimal regret bounds (e.g., O(sqrt(T)) for Online Mirror Descent) but face high computational costs due to Bregman projections at each iteration. By contrast, conditional gradient methods perform linear optimization at each step, achieving faster runtimes but at the expense of suboptimal regret bounds (e.g., O(T^⅔) for Online Frank-Wolfe). Motivated by this runtime-regret trade-off, we propose efficient iterative projection techniques for closely spaced points over submodular base polytopes, a widely applicable structure. Our approach, using both continuous and discrete perspectives, leads to significant runtime improvements in Online Mirror Descent, achieving up to several orders of magnitude in speed-ups in numerical experiments. For cardinality-based submodular polytopes, we further reduce Bregman projection costs by a factor of Omega(n/log n) in n-dimensions. Joint work with Hassan Mortagy and Swati Gupta.
Talk 3: TBD
Speaker: Babak Hassibi
Abstract: TBD
