CAREER: Automated Analysis and Design of Optimization Algorithms

迭代优化算法是机器学习、计算机视觉和数据科学等现代数据密集型应用的核心。在商业、交通、医疗、应急响应和国家安全方面，社会已经变得越来越依赖这样的算法。尽管算法在社会中扮演着重要的角色，但它们通常是使用专家的见解、广泛的数值模拟和其他启发式方法来设计和调整的。这项研究开发了一种更原则性的理解和算法设计方法，自动考虑到对参数选择的敏感性、对噪声的稳健性和其他不确定性来源。这种方法使算法能够以一种保证性能和安全性的方式进行设计，这类似于飞机、摩天大楼和计算机硬件的构建方式。迭代算法可以被视为具有反馈的动态系统。例如，在基于梯度的下降方法中，在每一步评估梯度并用于计算后续迭代。通过将算法视为控制系统，本研究利用稳健控制的工具(具体地说：积分二次约束、图解方法和半定表示)，以高效、可扩展和系统的方式分析并最终综合不同假设下的各种算法。这项研究还涉及基因调控网络的图结构学习和交互式机器学习领域的合作努力，这些领域用于测试和验证新的算法设计。

Iterative optimization algorithms lie at the heart of modern data-intensive applications such as machine learning, computer vision, and data science. Society has become increasingly reliant on such algorithms for commerce, transportation, healthcare, emergency response, and national security. Despite their critical role in society, algorithms are typically designed and tuned using insight from experts, extensive numerical simulations, and other heuristics. This research develops a more principled understanding and approach to algorithm design that automatically accounts for sensitivity to parameter choice, robustness to noise, and other sources of uncertainty. This approach enables algorithms to be engineered in a way that guarantees performance and safety, which is similar to how airplanes, skyscrapers, and computer hardware are built.Iterative algorithms may be viewed as dynamical systems with feedback. In gradient-based descent methods, for example, gradients are evaluated at each step and used to compute subsequent iterates. By treating algorithms as control systems, this research leverages tools from robust control (specifically: integral quadratic constraints, graphical methods, and semidefinite representation) to analyze and ultimately synthesize a variety of algorithms under different assumptions in an efficient, scalable, and systematic manner. This research also involves collaborative efforts in the areas of graph structure learning of gene regulatory networks and interactive machine learning, which serve to test and validate new algorithm designs.