Open Journal of Mathematical Optimization

To solve convex optimization problems with a noisy gradient input, we analyze the global behavior of subgradient-like flows under stochastic errors. The objective function is composite, being equal to the sum of two convex functions, one being differentiable and the other potentially non-smooth. We then use stochastic differential inclusions where the drift term is minus the subgradient of the objective function, and the diffusion term is either bounded or square-integrable. In this context, under Lipschitz’s continuity of the differentiable term and a growth condition of the non-smooth term, our first main result shows almost sure weak convergence of the trajectory process towards a minimizer of the objective function. Then, using Tikhonov regularization with a properly tuned vanishing parameter, we can obtain almost sure strong convergence of the trajectory towards the minimum norm solution. We find an explicit tuning of this parameter when our objective function satisfies a local error-bound inequality. We also provide a comprehensive complexity analysis by establishing several new pointwise and ergodic convergence rates in expectation for the convex, strongly convex, and Łojasiewicz case.

While there already exist randomized subspace Newton methods that restrict the search direction to a random subspace for a convex function, we propose a randomized subspace regularized Newton method for a non-convex function and more generally we investigate thoroughly, for the first time, the local convergence rate of the randomized subspace Newton method. In our proposed algorithm, we use a modified Hessian of the function restricted to some random subspace so that, with high probability, the function value decreases at each iteration, even when the objective function is non-convex. We show that our method has global convergence under appropriate assumptions and its convergence rate is the same as that of the full regularized Newton method. Furthermore, we obtain a local linear convergence rate under some additional assumptions, and prove that this rate is the best we can hope, in general, when using a random subspace. We furthermore prove that if the Hessian, at the local optimum, is rank deficient then super-linear convergence holds.

In this paper, we present a new framework, called “RYU”, for constructing “safe” regions – specifically, sets that are guaranteed to contain the dual solution of a target optimization problem. Our framework applies to the standard case where the objective function is composed of two components: a closed, proper, convex function with Lipschitz-smooth gradient and another closed, proper, convex function. We show that the RYU framework not only encompasses but also improves upon the state-of-the-art methods proposed over the past decade for this class of optimization problems.

In this paper, we focus on a class of problems characterized by solving a non-linear least squares minimization, for approximating a norm of a linear transformation. These problems are characterized by their non-convex and non-smooth nature, presenting challenges in finding (locally) optimal solutions. While existing optimization algorithms mostly concentrate on finding critical points of the associated least squares objective function, these functions often possess multiple non-global local minima and saddle points. These problems find wide applications in various domains, and we focus our attention on two challenging problems: Wireless Sensor Network Localization and Multi-Dimensional Scaling. We establish that non-differentiable points correspond to maximum or saddle points, and we provide a constructive approach to determine descent directions at these points. Leveraging this, we propose a straightforward procedure to escape non-differentiable saddle points that is applicable in either centralized or distributed computational setting. Furthermore, we develop a necessary condition for differentiable points to be local minimizers, by exploiting the structure of the objective function of these problems.

A fully stochastic pth-order adaptive-regularization method for unconstrained nonconvex optimization is presented which never computes the objective-function value, but yet achieves the optimal $\mathcal{O}(\epsilon ^{-(p+1)/p})$ complexity bound for finding first-order critical points. When stochastic gradients and Hessians are considered, we recover the optimal $\mathcal{O}\left(\epsilon ^{-3/2}\right)$ bound for finding first-order critical points. The method is noise-tolerant and the inexactness conditions required for convergence depend on the history of past steps. Applications to cases where derivative evaluation is inexact and to minimization of finite sums by sampling are discussed. Numerical experiments on large binary classification problems illustrate the potential of the new method.

In bilevel optimization problems, two players, the leader and the follower, make their decisions in a hierarchy, and both decisions may influence each other. Usually one assumes that both players have full knowledge also of the other player’s data. In a more realistic model, uncertainty can be quantified, e.g., using the robust optimization approach: We assume that the leader does not know the follower’s objective function precisely, but only knows an uncertainty set of potential follower’s objectives, and her aim is to optimize the worst case of the corresponding scenarios. Now the question arises how the computational complexity of bilevel optimization problems changes under the additional complications of this type of uncertainty.

We make a further step towards answering this question by examining an easy bilevel problem. In the Bilevel Selection Problem, the leader and the follower each select some items from their own item set, while a common number of items to select in total is given, and each of the two players minimizes the total costs of the selected items, according to different sets of item costs. We show that this problem can be solved in polynomial time without uncertainty and then investigate the complexity of its robust version. If the leader’s item set and the follower’s item set are disjoint, it can still be solved in polynomial time in case of discrete uncertainty, interval uncertainty, and discrete uncorrelated uncertainty, using ideas from [6]. Otherwise, we show that the Robust Bilevel Selection Problem becomes NP-hard, even for discrete uncertainty. We present a 2-approximation algorithm and exact exponential-time approaches for this setting, including an algorithm that runs in polynomial time if the number of scenarios is a constant.

Furthermore, we investigate variants of the Bilevel Selection Problem where one or both of the two decision makers take a continuous decision. One variant leads to an example of a bilevel optimization problem whose optimal value may not be attained. For the Robust Continuous Bilevel Selection Problem, where all variables are continuous, we generalize results from [6] and also develop a new approach for the setting of discrete uncorrelated uncertainty, which gives a polynomial-time algorithm for the Robust Continuous Bilevel Selection Problem and a pseudopolynomial-time algorithm for the Robust Bilevel Continuous Knapsack Problem, answering an open question from [6].

We propose an adaptive refinement algorithm to solve total variation regularized measure optimization problems. The method iteratively constructs dyadic partitions of the unit cube based on (i) the resolution of discretized dual problems and (ii) the detection of cells containing points that violate the dual constraints. The detection is based on upper-bounds on the dual certificate, in the spirit of branch-and-bound methods. The interest of this approach is that it avoids the use of heuristic approaches to find the maximizers of dual certificates. We prove the convergence of this approach under mild hypotheses and a linear convergence rate under additional non-degeneracy assumptions. These results are confirmed by simple numerical experiments.

Robust and bilevel optimization share the common feature that they involve a certain multilevel structure. Hence, although they model something rather different when used in practice, they seem to have a similar mathematical structure. In this paper, we analyze the connections between different types of robust problems (static robust problems with and without decision-dependence of their uncertainty sets, worst-case regret problems, and two-stage robust problems) as well as of bilevel problems (optimistic problems, pessimistic problems, and robust bilevel problems). It turns out that bilevel optimization seems to be more general in the sense that for most types of robust problems, one can find proper reformulations as bilevel problems but not necessarily the other way around. We hope that these results pave the way for a stronger connection between the two fields—in particular to use both theory and algorithms from one field in the other and vice versa.

We consider the problem of computing mixed Nash equilibria of two-player zero-sum games with continuous sets of pure strategies and with first-order access to the payoff function. This problem arises for example in game-theory-inspired machine learning applications, such as distributionally-robust learning. In those applications, the strategy sets are high-dimensional and thus methods based on discretisation cannot tractably return high-accuracy solutions. In this paper, we introduce and analyze a particle-based method that enjoys guaranteed local convergence for this problem. This method consists in parametrizing the mixed strategies as atomic measures and applying proximal point updates to both the atoms’ weights and positions. It can be interpreted as an implicit time discretization of the “interacting” Wasserstein–Fisher–Rao gradient flow.

We prove that, under non-degeneracy assumptions, this method converges at an exponential rate to the exact mixed Nash equilibrium from any initialization satisfying a natural notion of closeness to optimality. We illustrate our results with numerical experiments and discuss applications to max-margin and distributionally-robust classification using two-layer neural networks, where our method has a natural interpretation as a simultaneous training of the network’s weights and of the adversarial distribution.

In this work, we propose an adaptive variation on the classical Heavy-ball method for convex quadratic minimization. The adaptivity crucially relies on so-called “Polyak step-sizes”, which consists of using the knowledge of the optimal value of the optimization problem at hand instead of problem parameters such as a few eigenvalues of the Hessian of the problem. This method happens to also be equivalent to a variation of the classical conjugate gradient method, and thereby inherits many of its attractive features, including its finite-time convergence, instance optimality, and its worst-case convergence rates.

The classical gradient method with Polyak step-sizes is known to behave very well in situations in which it can be used, and the question of whether incorporating momentum in this method is possible and can improve the method itself appeared to be open. We provide a definitive answer to this question for minimizing convex quadratic functions, an arguably necessary first step for developing such methods in more general setups.