This work proposes a class of Multi-Objective Moreau Envelope based Hessian-free Algorithms (MOMEHA) to solve the multi-objective bilevel learning problems with nonconvex lower level and proposes a momentum-based variant of MOMEHA (i.e., MB-MOMEHA) method to solve the stochastic multi-objective bilevel learning problems.
Abstract
Multi-objective bilevel optimization has wide applications in the AI area such as automated learning and multi-task meta-learning. Although recently some works have been begun to study the multi-objective bilevel optimization, the proposed methods rely on the (strongly) convex lower level problems. In fact, these multi-objective bilevel learning problems are generally nonconvex, and particularly their lower level problems are nonconvex. To fill this gap, we propose a class of Multi-Objective Moreau Envelope based Hessian-free Algorithms (MOMEHA) to solve the multi-objective bilevel learning problems with nonconvex lower level. Specifically, our method uses the Moreau envelope to convert the original problem into a multi-objective single-level optimization with an envelope constraint. In particular, our method retains computational advantages of being single-loop and Hessian-free in the multi-objective setting by incorporating a smooth weighted Tchebycheff scalarization. Furthermore, we propose a momentum-based variant of MOMEHA (i.e., MB-MOMEHA) method to solve the stochastic multi-objective bilevel learning problems. In theory, we provide the convergence properties of our algorithms under both deterministic and stochastic setting. Some experiments on few-shot meta-learning and neural architecture search demonstrate that our methods outperform the existing approaches in Pareto front, validating its effectiveness and robustness.
One of the peculiar features of multi-parametric approach for bilevel programs is that most methods using this approach can be extended to tri-level (and generally to $k$-level) programs, which is not always the case with other non-heuristic solution methods. However, most of existing multi-parametric methods work well when the constraint of the lower-level problem is polyhedral. In this article we propose a multi-parametric programming based solution algorithm for bilevel optimization problems whose lower-level problem involves convex smooth nonlinear constraints. The method is also extended to solve some classes of $k$-level convex optimization problems with nonlinear constraints. The algorithm recasts the lower-level problem as a multi-parametric problem and employs an equivalent barrier problem reformulation. The solution obtained through multi-parametric programming is incorporated in the upper-level problem to create a set of single-level optimization problems which are solved using standard global optimization techniques. The proposed algorithm can give an exact global solution to some class of nonlinear Multi-level problems with convex nonlinear constraints.
In this paper, we propose a balanced augmented Lagrangian method based on accelerated stochastic ADMM (b-ASADMM) to efficiently solve structured separable nonconvex optimization problems subject to linear constraints. The objective function in this problem comprises potentially nonsmooth and smooth functions, where the smooth function is an average of multiple nonconvex smooth functions. The involved smooth subproblem is tackled by an accelerated stochastic gradient method based on weighting of stochastic item and pre-variable. The involved nonsmooth subproblem is solved under incorporation of Bregman distance to avoid the case that subproblem does not have a closed-form solution due to the complicated quadratic term or other hindering. The involved balanced augmented Lagrangian method advances the original ALM by balancing its subproblems and improving its implementation. In contrast to most deterministic and stochastic ADMMs, our dual variable allows a more flexible and larger step-size region. By standard smoothness assumption, we establish the global convergence and iteration complexity of the generated sequence. Furthermore, we provide a linear convergence rate of b-ASADMM under a local error bound condition and the weakly convex property of the nonsmooth component. Numerical experiments on the graph-guided fused Lasso problem and the smooth clipped absolute deviation penalty problem are conducted to verify the effectiveness of b-ASADMM.
Multiobjective composite optimization problems arise in sparse regularization, constrained multiobjective models, and multi-task learning, but their numerical solution remains challenging when the smooth components are ill-conditioned. Proximal gradient methods are inexpensive per iteration but may converge slowly, while proximal Newton and quasi-Newton methods exploit curvature information at the cost of evaluating expensive metric proximal mappings. To address these issues, we propose a preconditioned proximal Barzilai--Borwein method for multiobjective composite optimization. The method combines objective-wise Barzilai--Borwein scaling, which reduces imbalance among objectives, with a common preconditioner that captures shared curvature information. To avoid non-diagonal metric proximal mappings, we develop a subspace variant in which the search direction is computed in a two-dimensional subspace generated by a proximal-gradient-type direction and a projected historical direction. By constructing a conjugate basis with respect to the preconditioning metric, the subspace model decomposes into tractable one-dimensional subproblems. The framework is further extended to nonsmooth terms of the form $g_i(Ax)$ through a linear-operator-aware preconditioner, yielding explicit proximal evaluations via dual subproblems. We also analyze an inexact version based on relaxed descent conditions. We establish the global convergence of the inexact algorithm in the nonconvex setting and prove a linear convergence rate under an error-bound condition. Numerical experiments on ill-conditioned $\ell_1$-regularized, structured $\ell_1$-regularized, and linearly constrained problems demonstrate the effectiveness of the proposed method.
A new method for surgically removing training examples from a model reveals that as datasets grow, the link between what a model learns and what it produces dissolves.
