Xiaoming Yuan

Algorithmic stability is a fundamental concept in learning theory for studying the generalization guarantees of learning algorithms. A notable limitation of classical stability analyses is that they often require convexity assumptions to obtain nontrivial bounds. In this paper, we investigate the stability and generalization properties of learning algorithms in nonconvex settings. We introduce an algorithm-dependent quantity that depends only on the training dataset and the algorithm's output. Under a mild differentiability assumption, we establish stability and generalization bounds that apply to almost any algorithm. Our bounds explicitly involve the optimization error and the algorithm-dependent quantity, thereby capturing the local curvature of the objective function around the learned model. A key feature of our analysis is that it remains valid even when the algorithm does not converge to a global or local minimizer. We further apply our general framework to gradient descent and demonstrate its implications for both linear models and shallow neural networks. Empirical studies verify the effectiveness of our stability analyses.

We propose an optimization-informed deep neural network approach, named iUzawa-Net, aiming for the first solver that enables real-time solutions for a class of nonsmooth optimal control problems of linear partial differential equations (PDEs). The iUzawa-Net unrolls an inexact Uzawa method for saddle point problems, replacing classical preconditioners and PDE solvers with specifically designed learnable neural networks. We prove universal approximation properties and establish the asymptotic $\varepsilon$-optimality for the iUzawa-Net, and validate its promising numerical efficiency through nonsmooth elliptic and parabolic optimal control problems. Our techniques offer a versatile framework for designing and analyzing various optimization-informed deep learning approaches to optimal control and other PDE-constrained optimization problems. The proposed learning-to-control approach synergizes model-based optimization algorithms and data-driven deep learning techniques, inheriting the merits of both methodologies.

The deployment of large language models (LLMs) is often constrained by their substantial computational and memory demands. While structured pruning presents a viable approach by eliminating entire network components, existing methods suffer from performance degradation, reliance on heuristic metrics, or expensive finetuning. To address these challenges, we propose SPAP (Structured Pruning via Alternating Optimization and Penalty Methods), a novel and efficient structured pruning framework for LLMs grounded in optimization theory. SPAP formulates the pruning problem through a mixed-integer optimization model, employs a penalty method that effectively makes pruning decisions to minimize pruning errors, and introduces an alternating minimization algorithm tailored to the splittable problem structure for efficient weight updates and performance recovery. Extensive experiments on OPT, LLaMA-3/3.1/3.2, and Qwen2.5 models demonstrate SPAP's superiority over state-of-the-art methods, delivering linear inference speedups (1.29$\times$ at 30% sparsity) and proportional memory reductions. Our work offers a practical, optimization-driven solution for pruning LLMs while preserving model performance.

The rapid increase in the size of large language models (LLMs) has significantly escalated their computational and memory demands, posing challenges for efficient deployment, especially on resource-constrained devices. Structured pruning has emerged as an effective model compression method that can reduce these demands while preserving performance. In this paper, we introduce FASP (Fast and Accurate Structured Pruning), a novel structured pruning framework for LLMs that emphasizes both speed and accuracy. FASP employs a distinctive pruning structure that interlinks sequential layers, allowing for the removal of columns in one layer while simultaneously eliminating corresponding rows in the preceding layer without incurring additional performance loss. The pruning metric, inspired by Wanda, is computationally efficient and effectively selects components to prune. Additionally, we propose a restoration mechanism that enhances model fidelity by adjusting the remaining weights post-pruning. We evaluate FASP on the OPT and LLaMA model families, demonstrating superior performance in terms of perplexity and accuracy on downstream tasks compared to state-of-the-art methods. Our approach achieves significant speed-ups, pruning models such as OPT-125M in 17 seconds and LLaMA-30B in 15 minutes on a single NVIDIA RTX 4090 GPU, making it a highly practical solution for optimizing LLMs.

Pengxiang Zhao, Hanyu Hu, Ping Li, Yi Zheng, Zhefeng Wang, Xiaoming Yuan. Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing. 2025.

We introduce Coverage Axis++, a novel and efficient approach to 3D shape skeletonization. The current state‐of‐the‐art approaches for this task often rely on the watertightness of the input [LWS*15; PWG*19; PWG*19] or suffer from substantial computational costs [DLX*22; CD23], thereby limiting their practicality. To address this challenge, Coverage Axis++ proposes a heuristic algorithm to select skeletal points, offering a high‐accuracy approximation of the Medial Axis Transform (MAT) while significantly mitigating computational intensity for various shape representations. We introduce a simple yet effective strategy that considers shape coverage, uniformity, and centrality to derive skeletal points. The selection procedure enforces consistency with the shape structure while favoring the dominant medial balls, which thus introduces a compact underlying shape representation in terms of MAT. As a result, Coverage Axis++ allows for skeletonization for various shape representations (e.g., water‐tight meshes, triangle soups, point clouds), specification of the number of skeletal points, few hyperparameters, and highly efficient computation with improved reconstruction accuracy. Extensive experiments across a wide range of 3D shapes validate the efficiency and effectiveness of Coverage Axis++. Our codes are available athttps://github.com/Frank-ZY-Dou/Coverage_Axis.

In cloud ecosystems, managing bandwidth costs is pivotal for both operational efficiency and service quality. This paper tackles the cloud-edge traffic allocation problem, particularly optimizing for the 95th percentile billing scheme, which is widely employed across various cloud computing scenarios by Internet Service Providers but has yet to be efficiently addressed. We introduce a mathematical model for this issue, confirm its NP-hard complexity, and reformulate it as a mixed-integer programming (MIP). The intricacy of the problem is further magnified by the scale of the cloud ecosystem, involving numerous data centers, client groups, and long billing cycles. Based on a structural analysis of our MIP model, we propose a two-stage solution strategy that retains optimality. We introduce the Circling Reduction Algorithm (CRA), a polynomial-time algorithm based on a rigorously derived lower bound for the objective value, to efficiently determine the binary variables in the first stage, while the remaining linear programming problem in the second stage can be easily resolved. Using the CRA, we develop algorithms for both offline and online traffic allocation scenarios and validate them on real-world datasets from the cloud provider under study. In offline scenarios, our method delivers up to 66.34% cost savings compared to a commercial solver, while also significantly improving computational speed. Additionally, it achieves an average of 14% cost reduction over the current solution of the studied cloud provider. For online scenarios, we achieve an average cost-saving of 8.64% while staying within a 9% gap of the theoretical optimum.

As deep learning models exponentially increase in size, optimizers such as Adam encounter significant memory consumption challenges due to the storage of first and second moment data. Current memory-efficient methods like Adafactor and CAME often compromise accuracy with their matrix factorization techniques. Addressing this, we introduce Adapprox, a novel approach that employs randomized low-rank matrix approximation for a more effective and accurate approximation of Adam's second moment. Adapprox features an adaptive rank selection mechanism, finely balancing accuracy and memory efficiency, and includes an optional cosine similarity guidance strategy to enhance stability and expedite convergence. In GPT-2 training and downstream tasks, Adapprox surpasses AdamW by achieving 34.5% to 49.9% and 33.8% to 49.9% memory savings for the 117M and 345M models, respectively, with the first moment enabled, and further increases these savings without the first moment. Besides, it enhances convergence speed and improves downstream task performance relative to its counterparts.