交叉科学研究院研究生分享会

2025年12月7日（周日）；

上午 9 : 00 - 12 : 00

信息管理与工程学院102室

上海财经大学（第三教学楼西侧）

上海市杨浦区武东路100号

报告 ①

Accelerated Prox-level Method for Unknown Piecewise Smooth Problems

Abstract

In this work, we address the challenge of designing an algorithm that achieves the optimal convergence rate for optimizing unknown piecewise smooth (PWS) functions. PWS optimization refers to a special case of nonsmooth optimization in which the domain is partitioned into multiple regions, and the objective function is smooth within each region. The "unknown" setting means we have no prior knowledge of the locations or structure of these smooth regions; we treat the problem entirely as a black box.

Our approach builds upon the bundle level method. We rigorously show that when the number of cutting planes (cuts) exceeds the number of smooth pieces in the PWS function, the algorithm attains a convergence rate of $k\sqrt{L/\mu^*}\log(1/\varepsilon)$, where $k$ is the number of pieces, $L$ is the Lipschitz constant, $\mu^*$ is the quadratic growth modulus, and $\varepsilon$ is the target accuracy. Furthermore, we establish that this rate matches the corresponding lower complexity bound, thereby proving the optimality of our method. Notably, our algorithm is nearly parameter-free: apart from setting the number of cuts greater than the number of pieces, no additional problem-specific information is required.

报告 ②

Abstract

Federated learning (FL) has emerged as a powerful paradigm for collaborative model training across distributed clients while preserving data privacy. However, existing FL algorithms predominantly focus on unconstrained optimization problems with exact gradient information, limiting its applicability in scenarios where only noisy function evaluations are accessible or where model parameters are constrained. To address these challenges, we propose a novel zeroth-order projection-based algorithm on Riemannian manifolds for FL. By leveraging the projection operator, we introduce a computationally efficient zeroth-order Riemannian gradient estimator. Unlike existing estimators, ours requires only a simple Euclidean random perturbation, eliminating the need to sample random vectors in the tangent space, thus reducing computational cost. Theoretically, we first prove the approximation properties of the estimator and then establish the sublinear convergence of the proposed algorithm, matching the rate of its first-order counterpart. Numerically, we first assess the efficiency of our estimator using kernel principal component analysis. Furthermore, we apply the proposed algorithm to two real-world scenarios: zeroth-order attacks on deep neural networks and low-rank neural network training to validate the theoretical findings.

报告 ③

Abstract

In this paper, we consider the optimization problem of minimizing a sum of smooth and nonsmooth convex functions subject to both set and linear constraints. Our main contribution is the Subgradient Method based on Operator Splitting (SOS), a novel primal-dual method leveraging the framework of operator splitting to significantly reduce the computational cost brought by projection steps. Specifically, SOS separates the tasks of performing projection from the minimization of the objective function. This separation yields a major complexity improvement: the number of projection oracle calls is reduced from $\mcal O(\epsilon^{-2})$ to $\mcal O(\epsilon^{-1})$, while the number of subgradient oracle calls maintains the optimal rate of $\mcal O(\epsilon^{-2})$ for nonsmooth convex optimization. Similar results are also obtained when strongly convexity is present. Furthermore, we develop a $\text{projection-free}$ variant, SOSFW, which replaces the projection step by linear minimization oracles and allows for approximately solving the proximal subproblem. Finally, to optimize the smooth component's complexity, we propose an Accelerated SOS/SOSFW scheme. This advanced method is built upon an accelerated framework that repeatedly invokes the base SOS/SOSFW routines. The resulting scheme achieves an optimal complexity of $\mathcal{O}(\epsilon^{-1/2})$ for gradient oracle calls, matching the optimal rate for smooth convex optimization, while maintaining the established complexity for all other oracles.