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.

Pruning is a critical strategy for compressing trained large language models (LLMs), aiming at substantial memory conservation and computational acceleration without compromising performance.However, existing pruning methods typically necessitate inefficient retraining for billion-scale LLMs or rely on heuristically designed metrics to determine pruning masks, leading to performance degradation.This paper presents, for the first time, a LASSO-like convex optimization model crafted to induce sparsity in LLMs.By leveraging FISTA, we introduce FISTAPruner, a novel method that includes a cumulative error elimination mechanism within decoder layers and supports parallel pruning for unstructured pruning.Additionally, we extend this method to 2:4 semistructured pruning.We comprehensively evaluate FISTAPruner on models such as OPT, LLaMA, and Qwen variants with 125M to 70B parameters under unstructured and 2:4 semistructured sparsity, showcasing superior performance over existing methods across various language benchmarks.Notably, it can remove 50% of the model parameters for LLaMA-3-70B while retaining 98.6% and 95.6% of the zero-shot task performance under these two sparsity patterns, respectively.

Large Language Models (LLMs) face significant deployment challenges due to their substantial resource requirements. While low-bit quantized weights can reduce memory usage and improve inference efficiency, current hardware lacks native support for mixed-precision General Matrix Multiplication (mpGEMM), resulting in inefficient dequantization-based implementations. Moreover, uniform quantization methods often fail to capture weight distributions adequately, leading to performance degradation. We propose GANQ (GPU-Adaptive Non-Uniform Quantization), a layer-wise post-training non-uniform quantization framework optimized for hardware-efficient lookup table-based mpGEMM. GANQ achieves superior quantization performance by utilizing a training-free, GPU-adaptive optimization algorithm to efficiently reduce layer-wise quantization errors. Extensive experiments demonstrate GANQ’s ability to reduce the perplexity gap from the FP16 baseline compared to state-of-the-art methods for both 3-bit and 4-bit quantization. Furthermore, when deployed on a single NVIDIA RTX 4090 GPU, GANQ’s quantized models achieve up to 2.57$\times$ speedup over the baseline, advancing memory and inference efficiency in LLM deployment.

Abstract 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 at https://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.

In recent years, a variety of gradient-based methods have been developed to solve Bi-Level Optimization (BLO) problems in machine learning and computer vision areas. However, the theoretical correctness and practical effectiveness of these existing approaches always rely on some restrictive conditions (e.g., Lower-Level Singleton, LLS), which could hardly be satisfied in real-world applications. Moreover, previous literature only proves theoretical results based on their specific iteration strategies, thus lack a general recipe to uniformly analyze the convergence behaviors of different gradient-based BLOs. In this work, we formulate BLOs from an optimistic bi-level viewpoint and establish a new gradient-based algorithmic framework, named Bi-level Descent Aggregation (BDA), to partially address the above issues. Specifically, BDA provides a modularized structure to hierarchically aggregate both the upper- and lower-level subproblems to generate our bi-level iterative dynamics. Theoretically, we establish a general convergence analysis template and derive a new proof recipe to investigate the essential theoretical properties of gradient-based BLO methods. Furthermore, this work systematically explores the convergence behavior of BDA in different optimization scenarios, i.e., considering various solution qualities (i.e., global/local/stationary solution) returned from solving approximation subproblems. Extensive experiments justify our theoretical results and demonstrate the superiority of the proposed algorithm for hyper-parameter optimization and meta-learning tasks. Source code is available at https://github.com/vis-opt-group/BDA.

We generalize the well-known primal-dual algorithm proposed by Chambolle and Pock for saddle point problems and relax the condition for ensuring its convergence. The relaxed convergence-guaranteeing condition is effective for the generic convex setting of saddle point problems, and we show by the canonical convex programming problem with linear equality constraints that the relaxed condition is optimal. It also allows us to discern larger step sizes for the resulting subproblems, and thus provides a simple and universal way to improve numerical performance of the original primal-dual algorithm. In addition, we present a structure-exploring heuristic to further relax the convergence-guaranteeing condition for some specific saddle point problems, which could yield much larger step sizes and hence significantly better performance. Effectiveness of this heuristic is numerically illustrated by the classic assignment problem.

This paper firstly proposes a convex bilevel optimization paradigm to formulate and optimize popular learning and vision problems in real-world scenarios. Different from conventional approaches, which directly design their iteration schemes based on given problem formulation, we introduce a task-oriented energy as our latent constraint which integrates richer task information. By explicitly re- characterizing the feasibility, we establish an efficient and flexible algorithmic framework to tackle convex models with both shrunken solution space and powerful auxiliary (based on domain knowledge and data distribution of the task). In theory, we present the convergence analysis of our latent feasibility re- characterization based numerical strategy. We also analyze the stability of the theoretical convergence under computational error perturbation. Extensive numerical experiments are conducted to verify our theoretical findings and evaluate the practical performance of our method on different applications.

Bi-level optimization model is able to capture a wide range of complex learning tasks with practical interest. Due to the witnessed efficiency in solving bi-level programs, gradient-based methods have gained popularity in the machine learning community. In this work, we propose a new gradient-based solution scheme, namely, the Bi-level Value-Function-based Interior-point Method (BVFIM). Following the main idea of the log-barrier interior-point scheme, we penalize the regularized value function of the lower level problem into the upper level objective. By further solving a sequence of differentiable unconstrained approximation problems, we consequently derive a sequential programming scheme. The numerical advantage of our scheme relies on the fact that, when gradient methods are applied to solve the approximation problem, we successfully avoid computing any expensive Hessian-vector or Jacobian-vector product. We prove the convergence without requiring any convexity assumption on either the upper level or the lower level objective. Experiments demonstrate the efficiency of the proposed BVFIM on non-convex bi-level problems.

In recent years, a variety of gradient-based bi-level optimization methods have been developed for learning tasks. However, theoretical guarantees of these existing approaches often heavily rely on the simplification that for each fixed upper-level variable, the lower-level solution must be a singleton (a.k.a., Lower-Level Singleton, LLS). In this work, by formulating bi-level models from the optimistic viewpoint and aggregating hierarchical objective information, we establish Bi-level Descent Aggregation (BDA), a flexible and modularized algorithmic framework for bi-level programming. Theoretically, we derive a new methodology to prove the convergence of BDA without the LLS condition. Furthermore, we improve the convergence properties of conventional first-order bi-level schemes (under the LLS simplification) based on our proof recipe. Extensive experiments justify our theoretical results and demonstrate the superiority of the proposed BDA for different tasks, including hyper-parameter optimization and meta learning.

Despite the rich literature, the linear convergence of alternating direction method of multipliers (ADMM) has not been fully understood even for the convex case. For example, the linear convergence of ADMM can be empirically observed in a wide range of applications arising in statistics, machine learning, and related areas, while existing theoretical results seem to be too stringent to be satisfied or too ambiguous to be checked and thus why the ADMM performs linear convergence for these applications still seems to be unclear. In this paper, we systematically study the local linear convergence of ADMM in the context of convex optimization through the lens of variational analysis. We show that the local linear convergence of ADMM can be guaranteed without the strong convexity of objective functions together with the full rank assumption of the coefficient matrices, or the full polyhedricity assumption of their subdifferential; and it is possible to discern the local linear convergence for various concrete applications, especially for some representative models arising in statistical learning. We use some variational analysis techniques sophisticatedly; and our analysis is conducted in the most general proximal version of ADMM with Fortin and Glowinski's larger step size so that all major variants of the ADMM known in the literature are covered.

In this paper, we study an image decomposition model for patterned fabric inspection. It is important to represent fabric patterns effectively so that fabric defects can be separated. One concern is that both patterned fabric (e.g., star- or box-patterned fabrics) and fabric defects contain mainly low frequency components. The main idea of this paper is to use the convolution of a lattice with a Dirac comb to characterize a patterned fabric image so that its repetitive components can be effectively represented in the image decomposition model. We formulate a model with total variation, sparsity, and low-rank terms for patterned fabric inspection. The total variation term is used to regularize the defective image, and the sparsity and the low-rank terms are employed to control the Dirac comb function. The proposed model can be solved efficiently via a convex programming solver. Our experimental results for different types of patterned fabrics show that the proposed model can inspect defects at a higher accuracy compared with some classical methods in the literature.

The alternating direction method of multipliers (ADMM), also well known as a special split Bregman algorithm in imaging, is being popularly used in many areas including the image processing field. One useful modification is the symmetric version of the original ADMM, which updates the Lagrange multiplier twice at each iteration and thus the variables are treated in a symmetric manner. The symmetric version of ADMM, however, is not necessarily convergent. It was recently found that the convergence of symmetric ADMM can be sufficiently ensured if both the step sizes for updating the Lagrange multiplier are shrunk conservatively. Despite the theoretical significance in ensuring convergence, however, smaller step sizes should be strongly avoided in practice. On the contrary, we actually have the desire of seeking larger step sizes whenever possible in order to accelerate the numerical performance. Another technique leading to numerical acceleration of ADMM is enlarging its step size by a constant originally proposed by Fortin and Glowinski. These two numerically favorable techniques are commonly but usually separately used in ADMM literature, and intuitively they seem to be incompatible in combination with the symmetric ADMM due to the conflict between the theoretical role in ensuring the convergence with smaller step sizes and the empirical necessity in accelerating numerical performance with larger step sizes. It is thus open whether the ADMM scheme in combination with these two techniques simultaneously is convergent. We answer this question affirmatively in this paper and rigorously show the convergence of the symmetric version of ADMM with step sizes that can be enlarged by Fortin and Glowinski's constant. We thus move forward to the counterintuitive understanding that shrinking both the step sizes is not necessary for the symmetric ADMM. We conduct the convergence analysis by specifying a step size domain that can ensure the convergence of symmetric ADMM; some known results in the ADMM literature turn out to be special cases of our discussion. Since the step sizes can be enlarged by constants that are problem-independent and the strategy is applicable to the general iterative scheme when the generic setting of the model is considered, our theoretical study provides an easily implementable strategy to accelerate the ADMM numerically which can be immediately applied to a variety of applications including some standard image processing tasks.

A strictly contractive Peaceman--Rachford splitting method was proposed recently for solving separable convex programming problems. In this paper we further discuss a proximal version of this method, where a subproblem at each iteration is regularized by a proximal point term. The resulting regularized subproblem thus may have closed-form or easily computable solutions, especially in some interesting applications such as a class of sparse and low-rank optimization models. We establish the worst-case convergence rate measured by the iteration complexity in both the ergodic and nonergodic senses for the new algorithm. Some applications arising in image processing are tested to demonstrate the efficiency of the new algorithm.

The primal-dual hybrid gradient algorithm (PDHG) has been widely used, especially for some basic image processing models. In the literature, PDHG's convergence was established only under some restrictive conditions on its step sizes. In this paper, we revisit PDHG's convergence in the context of a saddle-point problem and try to better understand how to choose its step sizes. More specifically, we show by an extremely simple example that PDHG is not necessarily convergent even when the step sizes are fixed as tiny constants. We then show that PDHG with constant step sizes is indeed convergent if one of the functions of the saddle-point problem is strongly convex, a condition that does hold for some variational models in imaging. With this additional condition, we also establish a worst-case convergence rate measured by the iteration complexity for PDHG with constant step sizes.

This paper analyzes the cartoon and texture structures to inspect and visualize defective objects in a patterned fabric image. It presents a method of an image decomposition (ID) and solves it by a convex optimization algorithm. Our experimental results on benchmark fabric images are superior to those by other methods.

The total variation (TV) model is attractive in that it is able to preserve sharp attributes in images. However, the restored images from TV-based methods do not usually stay in a given dynamic range, and hence projection is required to bring them back into the dynamic range for visual presentation or for storage in digital media. This will affect the accuracy of the restoration as the projected image will no longer be the minimizer of the given TV model. In this paper, we show that one can get much more accurate solutions by imposing box constraints on the TV models and solving the resulting constrained models. Our numerical results show that for some images where there are many pixels with values lying on the boundary of the dynamic range, the gain can be as great as 10.28 decibel in the peak signal-to-noise ratio. One traditional hindrance using the constrained model is that it is difficult to solve. However, in this paper, we propose using the alternating direction method of multipliers (ADMM) to solve the constrained models. This leads to a fast and convergent algorithm that is applicable for both Gaussian and impulse noise. Numerical results show that our ADMM algorithm is better than some state-of-the-art algorithms for unconstrained models in terms of both accuracy and robustness with respect to the regularization parameter.

In this paper, we develop a decomposition model to restore blurred images with missing pixels. Our assumption is that the underlying image is the superposition of cartoon and texture components. We use the total variation norm and its dual norm to regularize the cartoon and texture, respectively. We recommend an efficient numerical algorithm based on the splitting versions of augmented Lagrangian method to solve the problem. Theoretically, the existence of a minimizer to the energy function and the convergence of the algorithm are guaranteed. In contrast to recently developed methods for deblurring images, the proposed algorithm not only gives the restored image, but also gives a decomposition of cartoon and texture parts. These two parts can be further used in segmentation and inpainting problems. Numerical comparisons between this algorithm and some state-of-the-art methods are also reported.

Recently, some primal-dual algorithms have been proposed for solving a saddle-point problem, with particular applications in the area of total variation image restoration. This paper focuses on the convergence analysis of these primal-dual algorithms and shows that their involved parameters (including step sizes) can be significantly enlarged if some simple correction steps are supplemented. Some new primal-dual–based methods are thus proposed for solving the saddle-point problem. We show that these new methods are of the contraction type: the iterative sequences generated by these new methods are contractive with respect to the solution set of the saddle-point problem. The global convergence of these new methods thus can be obtained within the analytic framework of contraction-type methods. The novel study on these primal-dual algorithms from the perspective of contraction methods substantially simplifies existing convergence analysis. Finally, we show the efficiency of the new methods numerically.

Image inpainting in wavelet domains refers to the recovery of an image from incomplete and/or inaccurate wavelet coefficients. To reconstruct the image, total variation (TV) models have been widely used in the literature, and they produce high-quality reconstructed images. In this paper, we consider an unconstrained, TV-regularized, $\ell_2$-data-fitting model to recover the image. The model is solved by the alternating direction method (ADM). At each iteration, the ADM needs to solve three subproblems, all of which have closed-form solutions. The per-iteration computational cost of the ADM is dominated by two Fourier transforms and two wavelet transforms, all of which admit fast computation. Convergence of the ADM iterative scheme is readily obtained. We also discuss extensions of this ADM scheme to solving two closely related constrained models. We present numerical results to show the efficiency and stability of the ADM for solving wavelet domain image inpainting problems. Numerical results comparing the ADM with some recent algorithms are also reported.