On the Convergence of Weak Greedy Algorithm for a Class of Non-Smooth Optimization Problemsin Banach Spaces

The paper discusses a greedy algorithm that can be used to solve non-smooth optimization problems in which its objective function can be represented as a minimum of a compactly parameterized family of uniformly smooth functions. The algorithm guarantees a sparse solution by adding one atom from the dictionary to the solution at each iteration. The algorithm employs a gradient greedy step that maximizes a linear functional using gradient information from the previous iteration. However, the algorithm is considered “weak” because it only solves the linear subproblems approximately. By employing the duality gap evaluated at each gradient-greedy step, the paper proves convergence of the algorithm to Clarke stationary points. Explicit upper bounds on the duality gap are derived, yielding a quantitative measure of proximity to stationarity and establishing the corresponding rates of convergence.