Methodology and first-order algorithms for solving nonsmooth and non-strongly convex bilevel optimization problems

DOI10.1007/S10107-022-01914-4MaRDI QIDQ6165595zbMATH OpenOpenAlexFDO

Authors Lior Doron, Shimrit Shtern

Publication date 1 August 2023

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2212.09843

zbMATH Keywords

bilevel optimizationcomplexity analysisconvex minimizationfirst-order methods

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Nonlinear programming (90C30) Methods of reduced gradient type (90C52)

Abstract: Simple bilevel problems are optimization problems in which we want to find an optimal solution to an inner problem that minimizes an outer objective function. Such problems appear in many machine learning and signal processing applications as a way to eliminate undesirable solutions. %However, since these problems do not satisfy regularity conditions, they are often hard to solve exactly and are usually solved via iterative regularization. In the past few years, several algorithms were proposed to solve these bilevel problems directly and provide a rate for obtaining feasibility, assuming that the outer function is strongly convex. In our work, we suggest a new approach that is designed for bilevel problems with simple outer functions, such as the $l_1$ norm, which are not required to be either smooth or strongly convex. In our new ITerative Approximation and Level-set EXpansion (ITALEX) approach, we alternate between expanding the level-set of the outer function and approximately optimizing the inner problem over this level-set. We show that optimizing the inner function through first-order methods such as proximal gradient and generalized conditional gradient results in a feasibility convergence rate of $O(1/k)$, which up to now was a rate only achieved by bilevel algorithms for smooth and strongly convex outer functions. Moreover, we prove an $O(1/sqrtk)$ rate of convergence for the outer function, contrary to existing methods, which only provide asymptotic guarantees. We demonstrate this performance through numerical experiments.

Recommendations

• A first order method for solving convex bilevel optimization problems
• An online convex optimization-based framework for convex bilevel optimization
• Techniques for gradient-based bilevel optimization with non-smooth lower level problems
• An inertial extrapolation method for convex simple bilevel optimization
• A primal nonsmooth reformulation for bilevel optimization problems

Cites work

• -subgradient algorithms for bilevel convex optimization
• A first order method for finding minimal norm-like solutions of convex optimization problems
• A first order method for solving convex bilevel optimization problems
• Algorithms for simple bilevel programming
• An inertial extrapolation method for convex simple bilevel optimization
• Duality between subgradient and conditional gradient methods
• First-order methods in optimization
• scientific article; zbMATH DE number 6378119 (Why is no real title available?)
• scientific article; zbMATH DE number 3551792 (Why is no real title available?)
• scientific article; zbMATH DE number 1328979 (Why is no real title available?)
• scientific article; zbMATH DE number 845714 (Why is no real title available?)
• scientific article; zbMATH DE number 5176444 (Why is no real title available?)
• Introduction to nonlinear optimization: theory, algorithms, and applications with MATLAB
• Lectures on convex optimization
• On a decomposition formula for the proximal operator of the sum of two convex functions
• Primal and dual predicted decrease approximation methods
• Proximal Point Algorithm Controlled by a Slowly Vanishing Term: Applications to Hierarchical Minimization
• Regularization tools version 4.0 for matlab 7.3
• Ridge Regression: Applications to Nonorthogonal Problems

Cited in

(16)

• A primal nonsmooth reformulation for bilevel optimization problems
• Techniques for gradient-based bilevel optimization with non-smooth lower level problems
• A first order method for solving convex bilevel optimization problems
• An inertial extrapolation method for convex simple bilevel optimization
• A Two-Timescale Stochastic Algorithm Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• Convex Bi-level Optimization Problems with Nonsmooth Outer Objective Function
• An Improved Unconstrained Approach for Bilevel Optimization
• Linearly convergent bilevel optimization with single-step inner methods
• An accelerated proximal algorithm for regularized nonconvex and nonsmooth bi-level optimization
• First-order penalty methods for bilevel optimization
• A gentle introduction to algorithms for bilevel optimization from machine learning
• Two regularized inertial Tseng methods for solving inclusion problems with applications to convex bilevel programming
• A projection-free method for solving convex bilevel optimization problems
• On the convergence of proximal gradient methods for convex simple bilevel optimization
• On the convergence rates of iterative regularization algorithms for composite bilevel optimization
• Dynamic fista for convex composite bilevel optimization

This page was built for publication: Methodology and first-order algorithms for solving nonsmooth and non-strongly convex bilevel optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6165595)