Anthony Man-Cho So

Neural networks (NNs) have transformed the field of artificial intelligence, showcasing remarkable abilities in learning complex representations, scaling to large datasets, and driving advancements across a wide range of applications. The training of these networks often involves optimizing functions that are not only nonconvex but possibly also nonsmooth, which introduces significant challenges in algorithm design and analysis. In this article, we provide an overview of recent advancements in the theoretical and computational aspects of nonsmooth optimization, thereby highlighting an area of growing importance that we refer to as “computational nonsmooth analysis.” We also demonstrate the relevance of these advancements in some representative applications. Lastly, we discuss some fundamental open questions in this area, the answers to which will impact the use and understanding of nonsmooth models in modern deep learning and signal processing.

In this paper, we consider a class of nonconvex-linear minimax problems on Riemannian manifolds, which find wide applications in machine learning and signal processing. For solving this class of problems, we develop a flexible Riemannian alternating descent ascent (RADA) algorithmic framework. Within this framework, we propose two easy-to-implement yet efficient algorithms that alternately perform one or multiple projected/Riemannian gradient descent steps and a proximal gradient ascent step at each iteration. We show that the proposed RADA algorithmic framework can find both an [ ]-Riemannian game stationary point and an [ ]-Riemannian optimization stationary point within [ ] iterations, achieving the best known iteration complexity. We also reveal intriguing similarities and differences between the algorithms developed within our proposed framework and existing algorithms, thus providing important insights into the improved efficiency of the former. Lastly, we present numerical results on sparse principal component analysis (PCA), fair PCA, and sparse spectral clustering to demonstrate the superior performance of the proposed algorithms. Funding: M. Xu and Y.-F. Liu are supported in part by the National Natural Science Foundation of China [Grants 12371314 and 12021001]. B. Jiang is supported by the National Natural Science Foundation of China [Grants 12522116 and 12371314]. A. M.-C. So is supported in part by the Hong Kong Research Grants Council General Research Fund project [CUHK 14204823].

Transmit beamforming design is a fundamental problem in integrated sensing and communication (ISAC) systems. Numerous methods have been proposed to jointly optimize key performance metrics such as the signal-to-interference-plus-noise ratio and Cramér-Rao bound. However, the computational complexity of these methods often grows rapidly with the number of transmit antennas at the base station (BS). To tackle this challenge, we prove a fundamental structural property of the ISAC beamforming problem, i.e., there exists an optimal solution exhibiting a low-dimensional structure. This leads to an equivalent reformulation of the problem with dimension related to the number of users rather than the number of BS antennas, thereby enabling the development of low-complexity algorithms. When applying the interior-point method to the reformulated problem, we achieve up to six orders of magnitude in complexity reduction when the number of antennas exceeds the number of users by an order of magnitude. To further reduce the complexity, we develop a balanced augmented Lagrangian method to solve the reformulated problem. The proposed algorithm maintains optimality while achieving a computational complexity that scales quartically with the number of users. Our simulation results demonstrate that the proposed R-BAL method can achieve a speedup of more than 10000$\times$ over the conventional IPM in massive MIMO scenarios.

Smooth minimax optimization problems play a central role in a wide range of applications, including machine learning, game theory, and operations research. However, existing algorithmic frameworks vary significantly depending on the problem structure -- whether it is convex-concave, nonconvex-concave, convex-nonconcave, or even nonconvex-nonconcave with additional regularity conditions. In particular, this diversity complicates the tuning of step-sizes since even verifying convexity (or concavity) assumptions is challenging and problem-dependent. We introduce a universal and single-loop algorithm, Doubly Smoothed Optimistic Gradient Descent Ascent (DS-OGDA), that applies to a broad class of smooth minimax problems. Specifically, this class includes convex-concave, nonconvex-concave, convex-nonconcave, and nonconvex-nonconcave minimax optimization problems satisfying a one-sided Kurdyka-Lojasiewicz (KL) property. DS-OGDA works with a universal single set of parameters for all problems in this class, eliminating the need for prior structural knowledge to determine step-sizes. Moreover, when a particular problem structure in our class is specified, DS-OGDA achieves optimal or best-known performance guarantees. Overall, our results provide a comprehensive and versatile framework for smooth minimax optimization, bridging the gap between convex and nonconvex problem structures and simplifying the choice of algorithmic strategies across diverse applications.