## 1 Introduction
However, for some practical problems, the functions may be nondifferentiable (nonsmooth), not easy to handle, and computationally expensive in the sense that the exact first-order information may be impossible to calculate, or be computable but difficult to obtain. For example, if \(f\) has the form  
\[f(x):=\sup\{\phi_{u}(x):\ u\in U\},\]  
where \(U\) is an infinite set and \(\phi_{u}(x):\ \mathbb{R}^{n}\to\mathbb{R}\) is convex for any \(u\in U\), then it is often difficult to calculate the exact function value \(f(x)\). But for any tolerance \(\epsilon>0\), we may usually find a lower approximation \(f_{x}^{\epsilon}\approx f(x)\) in finite time such that \(f_{x}^{\epsilon}\in[f(x)-\epsilon,f(x)]\) and \(f_{x}^{\epsilon}=\phi_{u_{\epsilon}}(x)\) for some \(u_{\epsilon}\in U\). Then we can take a subgradient of \(\phi_{u_{\epsilon}}\) at \(x\) as an approximate subgradient of \(f\) at \(x\). Another example is two-stage stochastic programming (see, e.g., References [23; 24]), in which the function value is generated after solving a series of linear programs (details will be given in the section of numerical experiments), therefore its accuracy is determined by the tolerance of the linear programming solver. Some other practical examples, such as Lagrangian relaxation, chance-constrained programs and convex composite functions, can be found in Reference [25]. Based on the above observation, in this paper, we focus particularly on the case where the function \(f\) is general, possibly nonsmooth and its exact function values and subgradients may be difficult to obtain, whereas the function \(h\) is assumed to be relatively simple. Our main goal is to provide an efficient method, namely, the improved alternating linearization bundle method, for such kind of structured convex optimization problems. The basic tool we used here to handle nonsmoothness and inexactness is the bundle technique, since in the nonsmooth optimization community, bundle methods [26; 27; 28; 29] are regarded as the most robust and reliable methods, whose variants have been well studied for handling inexact oracles [23; 25; 30; 31; 32; 33]. Roughly speaking, our method generalizes the alternating linearization bundle method of [PERSON] [22] from exact and inexact oracles to various oracles, including exact, inexact, partially inexact, asymptotically exact and partially asymptotically exact oracles. These oracles are covered by the so-called _on-demand accuracy oracles_ proposed by [PERSON] and [PERSON] [23], whose accuracy is controlled by two parameters: a descent target and an error bound. More precisely, the accuracy is bounded by an error bound whenever the function estimation reaches a certain descent target. The most advantage of oracles with on-demand accuracy is that the function and subgradient estimations can be rough without an accuracy control for some \"non-critical\" iterates, thus the computational effort can be saved. At each iteration, the proposed algorithm alternately solves two interrelated subproblems: one is to find the proximal point of the polyhedron model of \(f\) plus the linearization of \(h\); the other is to find the proximal point of the linearization of \(f\) plus \(h\). We establish global convergence of the algorithm under different types of inexactness. Finally, some preliminary numerical results on a set of two-stage stochastic linear programming problems show that our method is very encouraging. This paper is organized as follows. In Section 2, we recall the condition of the inexact first-order oracles. In Section 3, we present an improved alternating linearization bundle method for structured convex optimization with inexact first-order oracles and show some properties of the algorithm. In Section 4, we establish global convergence of the algorithm under different types of inexactness. In Section 5, we provide some numerical experiments on two-stage stochastic linear programming problems. The notations are standard.