Proximal methods are known to identify the underlying substructure of nonsmooth optimization problems. Even more, in many interesting situations, the output of a proximity operator comes with its ...structure at no additional cost, and convergence is improved once it matches the structure of a minimizer. However, it is impossible in general to know whether the current structure is final or not; such highly valuable information has to be exploited adaptively. To do so, we place ourselves in the case where a proximal gradient method can identify manifolds of differentiability of the nonsmooth objective. Leveraging this manifold identification, we show that Riemannian Newton-like methods can be intertwined with the proximal gradient steps to drastically boost the convergence. We prove the superlinear convergence of the algorithm when solving some nondegenerated nonsmooth nonconvex optimization problems. We provide numerical illustrations on optimization problems regularized by
ℓ
1
-norm or trace-norm.
Nonsmoothness is often a curse for optimization; but it is sometimes a blessing, in particular for applications in machine learning. In this paper, we present the specific structure of nonsmooth ...optimization problems appearing in machine learning and illustrate how to leverage this structure in practice, for compression, acceleration, or dimension reduction. We pay a special attention to the presentation to make it concise and easily accessible, with both simple examples and general results.
We present a federated learning framework that is designed to robustly deliver good predictive performance across individual clients with heterogeneous data. The proposed approach hinges upon a ...superquantile-based learning objective that captures the tail statistics of the error distribution over heterogeneous clients. We present a stochastic training algorithm that interleaves differentially private client filtering with federated averaging steps. We prove finite time convergence guarantees for the algorithm:
O
(
1
/
T
)
in the nonconvex case in
T
communication rounds and
O
(
exp
(
-
T
/
κ
3
/
2
)
+
κ
/
T
)
in the strongly convex case with local condition number
κ
. Experimental results on benchmark datasets for federated learning demonstrate that our approach is competitive with classical ones in terms of average error and outperforms them in terms of tail statistics of the error.
In this paper, we investigate attractive properties of the proximal gradient algorithm with inertia. Notably, we show that using
alternated inertia
yields monotonically decreasing functional values, ...which contrasts with usual accelerated proximal gradient methods. We also provide convergence rates for the algorithm with alternated inertia, based on local geometric properties of the objective function. The results are put into perspective by discussions on several extensions (strongly convex case, non-convex case, and alternated extrapolation) and illustrations on common regularized optimization problems.
In this paper, we consider nonsmooth convex optimization problems with additive structure featuring independent oracles (black-boxes) working in parallel. Existing methods for solving these ...distributed problems in a general form are synchronous, in the sense that they wait for the responses of all the oracles before performing a new iteration. In this paper, we propose level bundle methods handling asynchronous oracles. These methods require original upper-bounds (using upper-models or scarce coordinations) to deal with asynchronicity. We prove their convergence using variational-analysis techniques and illustrate their practical performance on a Lagrangian decomposition problem.
Probability constraints are often employed to intuitively define safety of given decisions in optimization problems. They simply express that a given system of inequalities depending on a decision ...vector and a random vector is satisfied with high enough probability. It is known that, even if this system is convex in the decision vector, the associated probability constraint is not convex in general. In this paper, we show that some degree of convexity is still preserved, for the large class of elliptical random vectors, encompassing for example Gaussian or Student random vectors. More precisely, our main result establishes that, under mild assumptions, eventual convexity holds, i.e. the probability constraint is convex when the safety level is large enough. We also provide tools to compute a concrete convexity certificate from nominal problem data. Our results are illustrated on several examples, including the situation of polyhedral systems with random technology matrices and arbitrary covariance structure.
Chance constraints are a valuable tool for the design of safe decisions in uncertain environments; they are used to model satisfaction of a constraint with a target probability. However, because of ...possible non-convexity and non-smoothness, optimizing over a chance constrained set is challenging. In this paper, we consider chance constrained programs where the objective function and the constraints are convex with respect to the decision parameter. We establish an exact reformulation of such a problem as a bilevel problem with a convex lower-level. Then we leverage this bilevel formulation to propose a tractable penalty approach, in the setting of finitely supported random variables. The penalized objective is a difference-of-convex function that we minimize with a suitable bundle algorithm. We release an easy-to-use open-source python toolbox implementing the approach, with a special emphasis on fast computational subroutines.
We consider the blind source separation (BSS) problem and the closely related approximate joint diagonalization (AJD) problem of symmetric positive definite (SPD) matrices. These two problems can be ...reduced to an optimization problem with three key components: the criterion to minimize, the constraint on the solution, and the optimization algorithm to solve it. This paper contains two contributions that allow us to treat these issues independently. We build the first complete Riemannian optimization framework suited for BSS and AJD handling three classical constraints, and allowing to use a large panel of general optimization algorithms on manifolds. We also perform a thorough study of the AJD problem of SPD matrices from an information geometry point of view. We study AJD criteria based on several divergences of the set of SPD matrices, provide three optimization strategies to minimize them, and analyze their properties. Our numerical experiments on simulated and pseudoreal electroencephalographic data show the interest of the Riemannian optimization framework and of the different AJD criteria we consider.
This article presents
BiqCrunch
, an exact solver for binary quadratic optimization problems.
BiqCrunch
is a branch-and-bound method that uses an original, efficient semidefinite-optimization-based ...bounding procedure. It has been successfully tested on a variety of well-known combinatorial optimization problems, such as Max-Cut, Max-
k
-Cluster, and Max-Independent-Set. The code is publicly available online; a web interface and many conversion tools are also provided.
PDF
