Search

We consider stochastic optimization problems involving an expected value of a nonlinear function of a base random vector and a conditional expectation of another function depending on the base random vector, a dependent random vector, and the decision variables. We call such problems conditional stochastic optimization problems. They arise in many applications, such as uplift modeling, reinforcement learning, and contextual optimization. We propose a specialized single time-scale stochastic method for nonconvex constrained conditional stochastic optimization problems with a Lipschitz smooth outer function and a generalized differentiable inner function. In the method, we approximate the inner conditional expectation with a rich parametric model whose mean squared error satisfies a stochastic version of a\Lojasiewicz condition. The model is used by an inner learning algorithm. The main feature of our approach is that unbiased stochastic estimates of the directions used by the method can be generated with one observation from the joint distribution per iteration, which makes it applicable to real-time learning. The directions, however, are not gradients or subgradients of any overall objective function. We prove the convergence of the method with probability one, using the method of differential inclusions and a specially designed Lyapunov function, involving a stochastic generalization of the Bregman distance. Finally, a numerical illustration demonstrates the viability of our approach. [ABSTRACT FROM AUTHOR]

We provide sufficient conditions for instability of the subgradient method with constant step size around a local minimum of a locally Lipschitz semialgebraic function. They are satisfied by several spurious local minima arising in robust principal component analysis and neural networks. [ABSTRACT FROM AUTHOR]

A variant of the compensated convexity process introduced and studied by Zhang and his colleagues is considered. It makes amenable the results and tools from convex analysis. It allows the regularization of functions with a strong decay, a new feature. It yields a family of tight approximations of the function that are always semiconvex functions. Thus, these approximating functions have interesting regularity properties. Their convergence is obtained under various assumptions. Additional questions and geometric applications that are important for several fields such as image analysis are deferred to the papers [H. V. Ngai, Proximal Subgradient Methods via the Semiconvex Regularization, in preparation], [H. V. Ngai and J.-P. Penot, Questions About the Semiconvex Regularization Method, in preparation], [H. V. Ngai and J.-P. Penot, Combining Different Regularization Methods, in preparation], and [H. V. Ngai and J.-P. Penot, The Medial Set and the Landscape Function of a Set, in preparation]. [ABSTRACT FROM AUTHOR]

We consider a class of nonsmooth optimization problems over the Stiefel manifold, in which the ob jective function is weakly convex in the ambient Euclidean space. Such problems are ubiquitous in engineering applications but still largely unexplored. We present a family of Rie-mannian subgradient-type methods--namely Riemannian subgradient, incremental subgradient, and stochastic subgradient methods--to solve these problems and show that they all have an iteration complexity of\scrO(\varepsilon-4) for driving a natural stationarity measure below\varepsilon. In addition, we establish the local linear convergence of the Riemannian subgradient and incremental subgradient methods when the problem at hand further satisfies a sharpness property and the algorithms are properly initialized and use geometrically diminishing stepsizes. To the best of our knowledge, these are the first convergence guarantees for using Riemannian subgradient-type methods to optimize a class of nonconvex nonsmooth functions over the Stiefel manifold. The fundamental ingredient in the proof of the aforementioned convergence results is a new Riemannian subgradient inequality for restrictions of weakly convex functions on the Stiefel manifold, which could be of independent interest. We also show that our convergence results can be extended to handle a class of compact embedded submanifolds of the Euclidean space. Finally, we discuss the sharpness properties of various formulations of the robust subspace recovery and orthogonal dictionary learning problems and demonstrate the convergence performance of the algorithms on both problems via numerical simulations. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of recovering a low-rank matrix from a number of random linear measurements that are corrupted by outliers taking arbitrary values. We consider a nonsmooth nonconvex formulation of the problem, in which we explicitly enforce the low-rank property of the solution by using a factored representation of the matrix variable and employ an l1- loss function to robustify the solution against outliers. We show that even when a constant fraction (which can be up to almost half) of the measurements are arbitrarily corrupted, as long as certain measurement operators arising from the measurement model satisfy the so-called l1/l2-restricted isometry property, the ground-truth matrix can be exactly recovered from any global minimum of the resulting optimization problem. Furthermore, we show that the objective function of the optimization problem is sharp and weakly convex. Consequently, a subgradient method (SubGM) with geometrically diminishing step sizes will converge linearly to the ground-truth matrix when suitably initialized. We demonstrate the efficacy of the SubGM for the nonconvex robust low-rank matrix recovery problem with various numerical experiments. [ABSTRACT FROM AUTHOR]

We develop model-based methods for solving stochastic convex optimization problems, introducing the approximate-proximal point, or aProx, family, which includes the stochastic subgradient, proximal point, and bundle methods. When the modeling approaches we propose are appropriately accurate, the methods enjoy stronger convergence and robustness guarantees than classical approaches, even though the model-based methods typically add little to no computational overhead over stochastic subgradient methods. For example, we show that improved models converge with probability 1 and enjoy optimal asymptotic normality results under weak assumptions; these methods are also adaptive to a natural class of what we term easy optimization problems, achieving linear convergence under appropriate strong growth conditions on the objective. Our substantial experimental investigation shows the advantages of more accurate modeling over standard subgradient methods across many smooth and nonsmooth optimization problems. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a stochastic projected subgradient method for weakly convex (i.e., uniformly prox-regular) nonsmooth, nonconvex functions---a wide class of functions which includes the additive and convex composite classes. At a high level, the method is an inexact proximal-point iteration in which the strongly convex proximal subproblems are quickly solved with a specialized stochastic projected subgradient method. The primary contribution of this paper is a simple proof that the proposed algorithm converges at the same rate as the stochastic gradient method for smooth nonconvex problems. This result appears to be the first convergence rate analysis of a stochastic (or even deterministic) subgradient method for the class of weakly convex functions. In addition, a two-phase variant is proposed that significantly reduces the variance of the solutions returned by the algorithm. Finally, preliminary numerical experiments are also provided. [ABSTRACT FROM AUTHOR]

We extend the classic convergence rate theory for subgradient methods to apply to non-Lipschitz functions. For the deterministic projected subgradient method, we present a global O(1/ √ T) convergence rate for any convex function which is locally Lipschitz around its minimizers. This approach is based on Shor's classic subgradient analysis and implies generalizations of the standard convergence rates for gradient descent on functions with Lipschitz or Hölder continuous gradients. Further, we show a O(1/ √ T) convergence rate for the stochastic projected subgradient method on convex functions with at most quadratic growth, which improves to O(1/T) under either strong convexity or a weaker quadratic lower bound condition. [ABSTRACT FROM AUTHOR]

This paper is devoted to the study of tilt stability in finite dimensional optimization via the approach of using the subgradient graphical derivative. We establish a new characterization of tilt-stable local minimizers for a broad class of unconstrained optimization problems in terms of a uniform positive-definiteness of the subgradient graphical derivative of the objective function around the point in question. By applying this result to nonlinear programming under the metric subregularity constraint qualification, we derive second-order characterizations and several new sufficient conditions for tilt stability. In particular, we show that each stationary point of a nonlinear programming problem satisfying the metric subregularity constraint qualification is a tilt-stable local minimizer if the classical strong second-order sufficient condition holds. [ABSTRACT FROM AUTHOR]

We present a subgradient method for minimizing nonsmooth, non-Lipschitz convex optimization problems. The only structure assumed is that a strictly feasible point is known. We extend the work of Renegar [SIAM J. Optim., 26 (2016), pp. 2649-2676] by taking a different perspective, leading to an algorithm which is conceptually more natural, has notably improved convergence rates, and for which the analysis is surprisingly simple. At each iteration, the algorithm takes a subgradient step and then performs a line search to move radially towards (or away from) the known feasible point. Our convergence results have striking similarities to those of traditional methods that require Lipschitz continuity. Costly orthogonal projections typical of subgradient methods are entirely avoided. [ABSTRACT FROM AUTHOR]

In this article we consider a consistent convex feasibility problem in a real Hilbert space defined by a finite family of sets Ci. We are interested, in particular, in the case where for each i, Ci = FixUi = {z ∈ H ∣ pi(z) = 0}, Ui : H → H is a cutter and pi : H → [0,∞) is a proximity function. Moreover, we make the following assumption: the computation of pi is at most as difficult as the evaluation of Ui and this is at most as difficult as projecting onto Ci. We study a double-layer fixed point algorithm which applies two types of controls in every iteration step. The first one—the outer control—is assumed to be almost cyclic. The second one—the inner control—determines the most important sets from those offered by the first one. The selection is made in terms of proximity functions. The convergence results presented in this manuscript depend on the conditions which, first, bind together the sets, the operators, and the proximity functions and, second, connect the inner and outer controls. In particular, weak regularity (demi-closedness principle), bounded regularity, and bounded linear regularity imply weak, strong, and linear convergence of our algorithm, respectively. The framework presented in this paper covers many known (subgradient) projection algorithms already existing in the literature, for example, those applied with (almost) cyclic, remotest-set, maximum displacement, most-violated constraint, and simultaneous controls. In addition, we provide several new examples, where the double-layer approach indeed accelerates the convergence speed as we demonstrate numerically. [ABSTRACT FROM AUTHOR]

The recent literature on first order methods for smooth optimization shows that significant improvements on the practical convergence behavior can be achieved with variable step size and scaling for the gradient, making this class of algorithms attractive for a variety of relevant applications. In this paper we introduce a variable metric in the context of the ε-subgradient methods for nonsmooth, convex problems, in combination with two different step size selection strategies. We develop the theoretical convergence analysis of the proposed approach in the general framework of forward-backward ε-subgradient splitting methods and we also discuss practical implementation issues. In order to illustrate the effectiveness of the method, we consider a specific problem in the image restoration framework and we numerically evaluate the effects of a variable scaling and of the step length selection strategy on the convergence behavior. [ABSTRACT FROM AUTHOR]

We consider convex optimization problems with structures that are suitable for sequential treatment or online sampling. In particular, we focus on problems where the objective function is an expected value, and the constraint set is the intersection of a large number of simpler sets. We propose an algorithmic framework for stochastic first-order methods using random projection/proximal updates and random constraint updates, which contain as special cases several known algorithms as well as many new algorithms. To analyze the convergence of these algorithms in a unified manner, we prove a general coupled convergence theorem. It states that the convergence is obtained from an interplay between two coupled processes: progress toward feasibility and progress toward optimality. Under suitable stepsize assumptions, we show that the optimality error decreases at a rate of O(1/√k) and the feasibility error decreases at a rate of O(log k/k). We also consider a number of typical sampling processes for generating stochastic first-order information and random constraints, which are common in data-intensive applications, online learning, and simulation optimization. By using the coupled convergence theorem as a modular architecture, we are able to analyze the convergence of stochastic algorithms that use arbitrary combinations of these sampling processes. [ABSTRACT FROM AUTHOR]

We study the convergence issue of the subgradient algorithm for solving the convex feasibility problems in Riemannian manifolds, which was first proposed and analyzed by Bento and Melo [J. Optim. Theory Appl., 152 (2012), pp. 773-785]. The linear convergence property about the subgradient algorithm for solving the convex feasibility problems with the Slater condition in Riemannian manifolds are established, and some step sizes rules are suggested for finite convergence purposes, which are motivated by the work due to De Pierro Iusem [Appl. Math. Optim., 17 (1988), pp. 225-235]. As a by-product, the convergence result of this algorithm is obtained for the convex feasibility problem without the Slater condition assumption. These results extend and/or improve the corresponding known ones in both the Euclidean space and Riemannian manifolds. [ABSTRACT FROM AUTHOR]

The subgradient projector is of considerable importance in convex optimization because it plays the key role in Polyak's seminal work--and the many papers it spawned--on subgradient projection algorithms for solving convex feasibility problems. In this paper, we offer a systematic study of the subgradient projector. Fundamental properties such as continuity, nonexpansiveness, and monotonicity are investigated. We also discuss the Yamagishi--Yamada operator. Numerous examples illustrate our results. [ABSTRACT FROM AUTHOR]

Given a convex optimization problem and its dual, there are many possible firstorder algorithms. In this paper, we show the equivalence between mirror descent algorithms and algorithms generalizing the conditional gradient method. This is done through convex duality and implies notably that for certain problems, such as for supervised machine learning problems with nonsmooth losses or problems regularized by nonsmooth regularizers, the primal subgradient method and the dual conditional gradient method are formally equivalent. The dual interpretation leads to a form of line search for mirror descent, as well as guarantees of convergence for primal-dual certificates. [ABSTRACT FROM AUTHOR]

This paper considers a networked system consisting of an operator, which manages the system, and a finite number of subnetworks with all users, and studies the problem of minimizing the sum of the operator's and all users' objective functions over the intersection of the operator's and all users' constraint sets. When users in each subnetwork can communicate with each other, they can implement an incremental subgradient method that uses the transmitted information from their neighbor users. Since the operator can communicate with users in the subnetworks, it can implement a broadcast distributed algorithm that uses all available information in the subnetworks. We present an iterative method combining broadcast and incremental distributed optimization algorithms. Our method has faster convergence and a wider range of application compared with conventional distributed algorithms. We also prove that under certain assumptions our method converges to the solution to the problem in the sense of the strong topology of a Hubert space. Moreover, we numerically compare our method with the conventional distributed algorithms in the case of a data storage system. The numerical results demonstrate the effectiveness and fast convergence of our method. [ABSTRACT FROM AUTHOR]

We present algorithms for solving a number of new models of facility location which generalize the classical Fermat-Torricelli problem. Our first approach involves using Nesterov's smoothing technique and the minimization majorization principle to build smooth approximations that are convenient for applying smooth optimization schemes. Another approach uses subgradient-type algorithms to cope directly with the nondifferentiability of the cost functions. Convergence results of the algorithms are proved and numerical tests are presented to show the effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we develop a primal-dual subgradient method for solving huge-scale linear conic optimization problems. Our main assumption is that the primal cone is formed as a direct product of many small-dimensional convex cones and that the matrix A of the corresponding linear operator is uniformly sparse. In this case, our method can approximate the primal-dual optimal solution with accuracy ∈ in O(... iterations. At the same time, the complexity of each iteration of this scheme does not exceed O(rqlog2 n) operations, where r and q are the maximal numbers of nonzero elements in the rows and columns of matrix A, and n is the number of variables. [ABSTRACT FROM AUTHOR]

This paper considers stochastic subgradient mirror-descent method for solving constrained convex minimization problems. In particular, a stochastic subgradient mirror-descent method with weighted iterate-averaging is investigated and its per-iterate convergence rate is analyzed. The novel part of the approach is in the choice of weights that are used to construct the averages. Through the use of these weighted averages, we show that the known optimal rates can be obtained with simpler algorithms than those currently existing in the literature. Specifically, by suitably choosing the stepsize values, one can obtain the rate of the order 1/k for strongly convex functions, and the rate 1/√k for general convex functions (not necessarily differentiable). Furthermore, for the latter case, it is shown that a stochastic subgradient mirror-descent with iterate averaging converges (along a subsequence) to an optimal solution, almost surely, even with the stepsize of the form 1/ √1 + k, which was not previously known. The stepsize choices that achieve the best rates are those proposed by Tseng for acceleration of proximal gradient methods [P. Tseng, SIAM J. Optim., submitted]. [ABSTRACT FROM AUTHOR]

Vector optimization problems are a significant extension of scalar optimization and have many real life applications. We consider an extension of the projected subgradient method to convex vector optimization, which works directly with vector-valued functions, without using scalarvalued objectives. We eliminate the scalarization approach, a popular strategy for solving vector optimization problems, exploring strongly the structure of these kinds of problems. Under suitable assumptions, we show that the sequence generated by the algorithm converges to a weakly efficient optimum point. [ABSTRACT FROM AUTHOR]

Stochastic programming problems arise in many practical situations, hi general, the deterministic equivalents of these problems can be very large and may not be solvable directly by general-purpose optimization approaches. For the particular case of two-stage stochastic programs, we consider decomposition approaches akin to a regularized L-shaped method that can handle inexactness ill the subproblem solution. From a nonsmooth optimization perspective, these variants amount to applying a proximal bundle method to an oracle that gives inaccurate values for the objective function and a subgradient. Rather than forcing early termination of the subproblem optimization to define inexact oracles, we select a small subset of scenarios for which the subproblem solution is exact, and we replace the information for the remaining scenarios by a fast procedure that does not involve solving an optimization problem. The inaccurate oracle information creates inexact cuts in the master program, which are well handled by the recently introduced inexact bundle methods. The proposed approaches are validated by encouraging numerical results on several two-stage stochastic linear programs found in the literature. [ABSTRACT FROM AUTHOR]

We present a unifying framework for nonsmooth convex minimization bringing together ∈-subgradient algorithms and methods for the convex feasibility problem. This development is a natural step for ∈-subgradient methods in the direction of constrained optimization since the Euclidean projection frequently required in such methods is replaced by an approximate projection, which is often easier to compute. The developments are applied to incremental subgradient methods, resulting in new algorithms suitable to large-scale optimization problems, such as those arising in tomographic imaging. [ABSTRACT FROM AUTHOR]

Subgradient methods for nondifferentiable optimization benefit from deflection, i.e., defining the search direction as a combination of the previous direction and the current subgradient. In the constrained case they also benefit from projection of the search direction onto the feasible set prior to computing the steplength, that is, from the use of conditional subgradient techniques. However, combining the two techniques is not straightforward, especially if an inexact oracle is available which can only compute approximate function values and subgradients. We present a convergence analysis of several different variants, both conceptual and implementable, of approximate conditional deflected subgradient methods. Our analysis extends the available results in the literature by using the main stepsize rules presented so far, while allowing deflection in a more flexible way. Furthermore, to allow for (diminishing/square summable) rules where the stepsize is tightly controlled a priori, we propose a new class of deflection-restricted approaches where it is the deflection parameter, rather than the stepsize, which is dynamically adjusted using the "target value" of the optimization sequence. For both Polyak-type and diminishing/square summable stepsizes, we propose a "correction" of the standard formula which shows that, in the inexact case, knowledge about the error computed by the oracle (which is available in several practical applications) can be exploited in order to strengthen the convergence properties of the method. The analysis allows for several variants of the algorithm; at least one of them is likely to show numerical performances similar to these of "heavy ball" subgradient methods, popular within backpropagation approaches to train neural networks, while possessing stronger convergence properties. [ABSTRACT FROM AUTHOR]

In this paper, we study methods for generating approximate primal solutions as a byproduct of subgradient methods applied to the Lagrangian dual of a primal convex (possibly nondifferentiable) constrained optimization problem. Our work is motivated by constrained primal problems with a favorable dual problem structure that leads to efficient implementation of dual subgradient methods, such as the recent resource allocation problems in large-scale networks. For such problems, we propose and analyze dual subgradient methods that use averaging schemes to generate approximate primal optimal solutions. These algorithms use a constant stepsize in view of its simplicity and practical significance. We provide estimates on the primal infeasibility and primal suboptimality of the generated approximate primal solutions. These estimates are given per iteration, thus providing a basis for analyzing the trade-offs between the desired level of error and the selection of the stepsize value. Our analysis relies on the Slater condition and the inherited boundedness properties of the dual problem under this condition. It also relies on the boundedness of subgradients, which is ensured by assuming the compactness of the constraint set. [ABSTRACT FROM AUTHOR]