Search

In this paper, we propose a first second-order scheme based on arbitrary non-Euclidean norms, incorporated by Bregman distances. They are introduced directly in the Newton iterate with regularization parameter proportional to the square root of the norm of the current gradient. For the basic scheme, as applied to the composite convex optimization problem, we establish the global convergence rate of the order O (k - 2) both in terms of the functional residual and in the norm of subgradients. Our main assumption on the smooth part of the objective is Lipschitz continuity of its Hessian. For uniformly convex functions of degree three, we justify global linear rate, and for strongly convex function we prove the local superlinear rate of convergence. Our approach can be seen as a relaxation of the Cubic Regularization of the Newton method (Nesterov and Polyak in Math Program 108(1):177–205, 2006) for convex minimization problems. This relaxation preserves the convergence properties and global complexities of the Cubic Newton in convex case, while the auxiliary subproblem at each iteration is simpler. We equip our method with adaptive search procedure for choosing the regularization parameter. We propose also an accelerated scheme with convergence rate O (k - 3) , where k is the iteration counter. [ABSTRACT FROM AUTHOR]

In this paper, a joint study of the behavior of solutions of the Heavy Ball ODE and Heavy Ball type algorithms is given. Since the pioneering work of Polyak (USSR Comput Math Math Phys 4(5):1–17, 1964), it is well known that such a scheme is very efficient for C 2 strongly convex functions with Lipschitz gradient. But much less is known when only growth conditions are considered. Depending on the geometry of the function to minimize, convergence rates for convex functions, with some additional regularity such as quasi-strong convexity, or strong convexity, were recently obtained in Aujol et al. (Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization, 2020). Convergence results with much weaker assumptions are given in the present paper: namely, linear convergence rates when assuming a growth condition (which amounts to a Łojasiewicz property in the convex case). This analysis is firstly performed in continuous time for the ODE, and then transposed for discrete optimization schemes. In particular, a variant of the Heavy Ball algorithm is proposed, which converges geometrically whatever the parameters choice, and which has the best state of the art convergence rate for first order methods to minimize composite non smooth convex functions satisfying a Łojasiewicz property. [ABSTRACT FROM AUTHOR]

It is well-known that the sum of two quasiconvex functions is not quasiconvex in general, and the same occurs with the minimum. Although apparently these two statements (for the sum or minimum) have nothing in common, they are related, as we show in this paper. To develop our study, the notion of quasiconvex family is introduced, and we establish various characterizations of such a concept: one of them being the quasiconvexity of the pointwise infimum of arbitrary translations of quasiconvex functions in the family; another is the convexity of the union of any two of their sublevel sets; a third one is the quasiconvexity of the sum of the quasiconvex functions, composed with arbitrary nondecreasing functions. As a by-product, any of the aforementioned characterizations, besides providing quasiconvexity of the sum, also implies the semistrict quasiconvexity of the sum if every function in the family has the same property. Three concrete applications in quasiconvex optimization are presented: First, we establish the convexity of the (Benson) proper efficient solution set to a quasiconvex vector optimization problem; second, we derive conditions that allow us to reduce a constrained optimization problem to one with a single inequality constraint, and finally, we show a class of quasiconvex minimization problems having zero duality gap. [ABSTRACT FROM AUTHOR]

Robust convex constraints are difficult to handle, since finding the worst-case scenario is equivalent to maximizing a convex function. In this paper, we propose a new approach to deal with such constraints that unifies most approaches known in the literature and extends them in a significant way. The extension is either obtaining better solutions than the ones proposed in the literature, or obtaining solutions for classes of problems unaddressed by previous approaches. Our solution is based on an extension of the Reformulation-Linearization-Technique, and can be applied to general convex inequalities and general convex uncertainty sets. It generates a sequence of conservative approximations which can be used to obtain both upper- and lower- bounds for the optimal objective value. We illustrate the numerical benefit of our approach on a robust control and robust geometric optimization example. [ABSTRACT FROM AUTHOR]

This work aims to minimize a continuously differentiable convex function with Lipschitz continuous gradient under linear equality constraints. The proposed inertial algorithm results from the discretization of the second-order primal-dual dynamical system with asymptotically vanishing damping term addressed by Boţ and Nguyen (J. Differential Equations 303:369–406, 2021), and it is formulated in terms of the Augmented Lagrangian associated with the minimization problem. The general setting we consider for the inertial parameters covers the three classical rules by Nesterov, Chambolle–Dossal and Attouch–Cabot used in the literature to formulate fast gradient methods. For these rules, we obtain in the convex regime convergence rates of order O 1 / k 2 for the primal-dual gap, the feasibility measure, and the objective function value. In addition, we prove that the generated sequence of primal-dual iterates converges to a primal-dual solution in a general setting that covers the two latter rules. This is the first result which provides the convergence of the sequence of iterates generated by a fast algorithm for linearly constrained convex optimization problems without additional assumptions such as strong convexity. We also emphasize that all convergence results of this paper are compatible with the ones obtained in Boţ and Nguyen (J. Differential Equations 303:369–406, 2021) in the continuous setting. [ABSTRACT FROM AUTHOR]

In this paper, we present difference of convex algorithms for solving bilevel programs in which the upper level objective functions are difference of convex functions, and the lower level programs are fully convex. This nontrivial class of bilevel programs provides a powerful modelling framework for dealing with applications arising from hyperparameter selection in machine learning. Thanks to the full convexity of the lower level program, the value function of the lower level program turns out to be convex and hence the bilevel program can be reformulated as a difference of convex bilevel program. We propose two algorithms for solving the reformulated difference of convex program and show their convergence to stationary points under very mild assumptions. Finally we conduct numerical experiments to a bilevel model of support vector machine classification. [ABSTRACT FROM AUTHOR]

For two matroids M 1 and M 2 with the same ground set V and two cost functions w 1 and w 2 on 2 V , we consider the problem of finding bases X 1 of M 1 and X 2 of M 2 minimizing w 1 (X 1) + w 2 (X 2) subject to a certain cardinality constraint on their intersection X 1 ∩ X 2 . For this problem, Lendl et al. (Matroid bases with cardinality constraints on the intersection, arXiv:1907.04741v2, 2019) discussed modular cost functions: they reduced the problem to weighted matroid intersection for the case where the cardinality constraint is | X 1 ∩ X 2 | ≤ k or | X 1 ∩ X 2 | ≥ k ; and designed a new primal-dual algorithm for the case where the constraint is | X 1 ∩ X 2 | = k . The aim of this paper is to generalize the problems to have nonlinear convex cost functions, and to comprehend them from the viewpoint of discrete convex analysis. We prove that each generalized problem can be solved via valuated independent assignment, valuated matroid intersection, or M -convex submodular flow, to offer a comprehensive understanding of weighted matroid intersection with intersection constraints. We also show the NP-hardness of some variants of these problems, which clarifies the coverage of discrete convex analysis for those problems. Finally, we present applications of our generalized problems in the recoverable robust matroid basis problem, combinatorial optimization problems with interaction costs, and matroid congestion games. [ABSTRACT FROM AUTHOR]

Motivated by modern regression applications, in this paper, we study the convexification of a class of convex optimization problems with indicator variables and combinatorial constraints on the indicators. Unlike most of the previous work on convexification of sparse regression problems, we simultaneously consider the nonlinear non-separable objective, indicator variables, and combinatorial constraints. Specifically, we give the convex hull description of the epigraph of the composition of a one-dimensional convex function and an affine function under arbitrary combinatorial constraints. As special cases of this result, we derive ideal convexifications for problems with hierarchy, multi-collinearity, and sparsity constraints. Moreover, we also give a short proof that for a separable objective function, the perspective reformulation is ideal independent from the constraints of the problem. Our computational experiments with sparse regression problems demonstrate the potential of the proposed approach in improving the relaxation quality without significant computational overhead. [ABSTRACT FROM AUTHOR]

In this paper we establish general formulas for the subdifferential of the pointwise supremum of convex functions, which cover and unify both the compact continuous and the non-compact non-continuous settings. From the non-continuous to the continuous setting, we proceed by a compactification-based approach which leads us to problems having compact index sets and upper semi-continuously indexed mappings, giving rise to new characterizations of the subdifferential of the supremum by means of upper semicontinuous regularized functions and an enlarged compact index set. In the opposite sense, we rewrite the subdifferential of these new regularized functions by using the original data, also leading us to new results on the subdifferential of the supremum. We give two applications in the last section, the first one concerning the nonconvex Fenchel duality, and the second one establishing Fritz-John and KKT conditions in convex semi-infinite programming. [ABSTRACT FROM AUTHOR]

In this paper, we present diverse new metric properties that prox-regular sets shared with convex ones. At the heart of our work lie the Legendre-Fenchel transform and complements of balls. First, we show that a connected prox-regular set is completely determined by the Legendre-Fenchel transform of a suitable perturbation of its indicator function. Then, we prove that such a function is also the right tool to extend, to the context of prox-regular sets, the famous connection between the distance function and the support function of a convex set. On the other hand, given a prox-regular set, we examine the intersection of complements of open balls containing the set. We establish that the distance of a point to a prox-regular set is the maximum of the distances of the point from boundaries of all such complements separating the set and the point. This is in the line of the known result expressing the distance from a convex set in terms of separating hyperplanes. To the best of our knowledge, these results are new in the literature and show that the class of prox-regular sets have good properties known in convex analysis. [ABSTRACT FROM AUTHOR]

A key question in many low-rank problems throughout optimization, machine learning, and statistics is to characterize the convex hulls of simple low-rank sets and judiciously apply these convex hulls to obtain strong yet computationally tractable relaxations. We invoke the matrix perspective function—the matrix analog of the perspective function—to characterize explicitly the convex hull of epigraphs of simple matrix convex functions under low-rank constraints. Further, we combine the matrix perspective function with orthogonal projection matrices—the matrix analog of binary variables which capture the row-space of a matrix—to develop a matrix perspective reformulation technique that reliably obtains strong relaxations for a variety of low-rank problems, including reduced rank regression, non-negative matrix factorization, and factor analysis. Moreover, we establish that these relaxations can be modeled via semidefinite constraints and thus optimized over tractably. The proposed approach parallels and generalizes the perspective reformulation technique in mixed-integer optimization and leads to new relaxations for a broad class of problems. [ABSTRACT FROM AUTHOR]

We consider minimizing a smooth and strongly convex objective function using a stochastic Newton method. At each iteration, the algorithm is given an oracle access to a stochastic estimate of the Hessian matrix. The oracle model includes popular algorithms such as Subsampled Newton and Newton Sketch, which can efficiently construct stochastic Hessian estimates for many tasks, e.g., training machine learning models. Despite using second-order information, these existing methods do not exhibit superlinear convergence, unless the stochastic noise is gradually reduced to zero during the iteration, which would lead to a computational blow-up in the per-iteration cost. We propose to address this limitation with Hessian averaging: instead of using the most recent Hessian estimate, our algorithm maintains an average of all the past estimates. This reduces the stochastic noise while avoiding the computational blow-up. We show that this scheme exhibits local Q-superlinear convergence with a non-asymptotic rate of (Υ log (t) / t ) t , where Υ is proportional to the level of stochastic noise in the Hessian oracle. A potential drawback of this (uniform averaging) approach is that the averaged estimates contain Hessian information from the global phase of the method, i.e., before the iterates converge to a local neighborhood. This leads to a distortion that may substantially delay the superlinear convergence until long after the local neighborhood is reached. To address this drawback, we study a number of weighted averaging schemes that assign larger weights to recent Hessians, so that the superlinear convergence arises sooner, albeit with a slightly slower rate. Remarkably, we show that there exists a universal weighted averaging scheme that transitions to local convergence at an optimal stage, and still exhibits a superlinear convergence rate nearly (up to a logarithmic factor) matching that of uniform Hessian averaging. [ABSTRACT FROM AUTHOR]

Many applications require minimizing the sum of smooth and nonsmooth functions. For example, basis pursuit denoising problems in data science require minimizing a measure of data misfit plus an ℓ 1 -regularizer. Similar problems arise in the optimal control of partial differential equations (PDEs) when sparsity of the control is desired. We develop a novel trust-region method to minimize the sum of a smooth nonconvex function and a nonsmooth convex function. Our method is unique in that it permits and systematically controls the use of inexact objective function and derivative evaluations. When using a quadratic Taylor model for the trust-region subproblem, our algorithm is an inexact, matrix-free proximal Newton-type method that permits indefinite Hessians. We prove global convergence of our method in Hilbert space and demonstrate its efficacy on three examples from data science and PDE-constrained optimization. [ABSTRACT FROM AUTHOR]

Simple bilevel problems are optimization problems in which we want to find an optimal solution to an inner problem that minimizes an outer objective function. Such problems appear in many machine learning and signal processing applications as a way to eliminate undesirable solutions. In our work, we suggest a new approach that is designed for bilevel problems with simple outer functions, such as the l 1 norm, which are not required to be either smooth or strongly convex. In our new ITerative Approximation and Level-set EXpansion (ITALEX) approach, we alternate between expanding the level-set of the outer function and approximately optimizing the inner problem over this level-set. We show that optimizing the inner function through first-order methods such as proximal gradient and generalized conditional gradient results in a feasibility convergence rate of O(1/k), which up to now was a rate only achieved by bilevel algorithms for smooth and strongly convex outer functions. Moreover, we prove an O (1 / k) rate of convergence for the outer function, contrary to existing methods, which only provide asymptotic guarantees. We demonstrate this performance through numerical experiments. [ABSTRACT FROM AUTHOR]

We consider pessimistic bilevel stochastic programs in which the follower maximizes over a fixed compact convex set a strictly convex quadratic function, whose Hessian depends on the leader's decision. This results in a random upper level outcome which is evaluated by a convex risk measure. Under assumptions including real analyticity of the lower-level goal function, we prove the existence of optimal solutions. We discuss an alternate model, where the leader hedges against optimal lower-level solutions, and show that solvability can be guaranteed under weaker conditions in both, a deterministic and a stochastic setting. The approach is applied to a mechanical shape optimization problem in which the leader decides on an optimal material distribution to minimize a tracking-type cost functional, whereas the follower chooses forces from an admissible set to maximize a compliance objective. The material distribution is considered to be stochastically perturbed in the actual construction phase. Computational results illustrate the bilevel optimization concept and demonstrate the interplay of follower and leader in shape design and testing. [ABSTRACT FROM AUTHOR]

The solution of bilevel optimization problems with possibly nondifferentiable upper objective functions and with smooth and convex lower-level problems is discussed. A new approximate one-level reformulation for the original problem is introduced. An algorithm based on this reformulation is developed that is proven to converge to a solution of the bilevel problem. Each iteration of the algorithm depends on the solution of a nonsmooth optimization problem and its implementation leverages recent advances on nonsmooth optimization algorithms, which are fundamental to obtain a practical method. Experimental work is performed in order to demonstrate some characteristics of the algorithm in practice. [ABSTRACT FROM AUTHOR]

Minimizing finite sums of smooth and strongly convex functions is an important task in machine learning. Recent work has developed stochastic gradient methods that optimize these sums with less computation than methods that do not exploit the finite sum structure. This speedup results from using efficiently constructed stochastic gradient estimators, which have variance that diminishes as the algorithm progresses. In this work, we ask whether the benefits of variance reduction extend to fixed point and root-finding problems involving sums of nonlinear operators. Our main result shows that variance reduction offers a similar speedup when applied to a broad class of root-finding problems. We illustrate the result on three tasks involving sums of n nonlinear operators: averaged fixed point, monotone inclusions, and nonsmooth common minimizer problems. In certain "poorly conditioned regimes," the proposed method offers an n-fold speedup over standard methods. [ABSTRACT FROM AUTHOR]

We prove decomposition theorems for sparse positive (semi)definite polynomial matrices that can be viewed as sparsity-exploiting versions of the Hilbert–Artin, Reznick, Putinar, and Putinar–Vasilescu Positivstellensätze. First, we establish that a polynomial matrix P(x) with chordal sparsity is positive semidefinite for all x ∈ R n if and only if there exists a sum-of-squares (SOS) polynomial σ (x) such that σ P is a sum of sparse SOS matrices. Second, we show that setting σ (x) = (x 1 2 + ⋯ + x n 2) ν for some integer ν suffices if P is homogeneous and positive definite globally. Third, we prove that if P is positive definite on a compact semialgebraic set K = { x : g 1 (x) ≥ 0 , ... , g m (x) ≥ 0 } satisfying the Archimedean condition, then P (x) = S 0 (x) + g 1 (x) S 1 (x) + ⋯ + g m (x) S m (x) for matrices S i (x) that are sums of sparse SOS matrices. Finally, if K is not compact or does not satisfy the Archimedean condition, we obtain a similar decomposition for (x 1 2 + ⋯ + x n 2) ν P (x) with some integer ν ≥ 0 when P and g 1 , ... , g m are homogeneous of even degree. Using these results, we find sparse SOS representation theorems for polynomials that are quadratic and correlatively sparse in a subset of variables, and we construct new convergent hierarchies of sparsity-exploiting SOS reformulations for convex optimization problems with large and sparse polynomial matrix inequalities. Numerical examples demonstrate that these hierarchies can have a significantly lower computational complexity than traditional ones. [ABSTRACT FROM AUTHOR]

We focus on a new class of integrally convex functions which we call discrete 2-convex functions. Discrete 2-convexity generalizes known classes of integrally convex functions such as the well-established M-/M ♮ -convex and L-/L ♮ -convex functions by Murota et al., the recently investigated globally/locally discrete midpoint convex functions by Moriguchi, Murota, Tamura, and Tardella, the directed discrete midpoint convex functions by Tamura and Tsurumi, and BS ∗ -convex and UJ-convex functions by one of the authors. We provide a unifying view of all these functions within the class of integrally convex functions having discrete 2-convexity. We also introduce a new subclass of discrete 2-convex functions, called signed discrete 2-convex functions and we consider signed discrete 2-convex functions with a locally hereditary orientation property. We show that parallelogram inequalities, scalability, and proximity hold for such signed discrete 2-convex functions, which include globally/locally discrete midpoint convex functions and directed discrete midpoint convex functions. Hence, our results extend similar results recently established by Moriguchi, Murota, Tamura, and Tardella and by Tamura and Tsurumi. [ABSTRACT FROM AUTHOR]

We provide a control-theoretic perspective on optimal tensor algorithms for minimizing a convex function in a finite-dimensional Euclidean space. Given a function Φ : R d → R that is convex and twice continuously differentiable, we study a closed-loop control system that is governed by the operators ∇ Φ and ∇ 2 Φ together with a feedback control law λ (·) satisfying the algebraic equation (λ (t)) p ‖ ∇ Φ (x (t)) ‖ p - 1 = θ for some θ ∈ (0 , 1) . Our first contribution is to prove the existence and uniqueness of a local solution to this system via the Banach fixed-point theorem. We present a simple yet nontrivial Lyapunov function that allows us to establish the existence and uniqueness of a global solution under certain regularity conditions and analyze the convergence properties of trajectories. The rate of convergence is O (1 / t (3 p + 1) / 2) in terms of objective function gap and O (1 / t 3 p) in terms of squared gradient norm. Our second contribution is to provide two algorithmic frameworks obtained from discretization of our continuous-time system, one of which generalizes the large-step A-HPE framework of Monteiro and Svaiter (SIAM J Optim 23(2):1092–1125, 2013) and the other of which leads to a new optimal p-th order tensor algorithm. While our discrete-time analysis can be seen as a simplification and generalization of Monteiro and Svaiter (2013), it is largely motivated by the aforementioned continuous-time analysis, demonstrating the fundamental role that the feedback control plays in optimal acceleration and the clear advantage that the continuous-time perspective brings to algorithmic design. A highlight of our analysis is that we show that all of the p-th order optimal tensor algorithms that we discuss minimize the squared gradient norm at a rate of O (k - 3 p) , which complements the recent analysis in Gasnikov et al. (in: COLT, PMLR, pp 1374–1391, 2019), Jiang et al. (in: COLT, PMLR, pp 1799–1801, 2019) and Bubeck et al. (in: COLT, PMLR, pp 492–507, 2019). [ABSTRACT FROM AUTHOR]

Counterexamples to some old-standing optimization problems in the smooth convex coercive setting are provided. We show that block-coordinate, steepest descent with exact search or Bregman descent methods do not generally converge. Other failures of various desirable features are established: directional convergence of Cauchy's gradient curves, convergence of Newton's flow, finite length of Tikhonov path, convergence of central paths, or smooth Kurdyka–Łojasiewicz inequality. All examples are planar. These examples are based on general smooth convex interpolation results. Given a decreasing sequence of positively curved C k convex compact sets in the plane, we provide a level set interpolation of a C k smooth convex function where k ≥ 2 is arbitrary. If the intersection is reduced to one point our interpolant has positive definite Hessian, otherwise it is positive definite out of the solution set. Furthermore, given a sequence of decreasing polygons we provide an interpolant agreeing with the vertices and whose gradients coincide with prescribed normals. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing composite functions of the form f (g (x)) + h (x) , where f and h are convex functions (which can be nonsmooth) and g is a smooth vector mapping. In addition, we assume that g is the average of finite number of component mappings or the expectation over a family of random component mappings. We propose a class of stochastic variance-reduced prox-linear algorithms for solving such problems and bound their sample complexities for finding an ϵ -stationary point in terms of the total number of evaluations of the component mappings and their Jacobians. When g is a finite average of N components, we obtain sample complexity O (N + N 4 / 5 ϵ - 1) for both mapping and Jacobian evaluations. When g is a general expectation, we obtain sample complexities of O (ϵ - 5 / 2) and O (ϵ - 3 / 2) for component mappings and their Jacobians respectively. If in addition f is smooth, then improved sample complexities of O (N + N 1 / 2 ϵ - 1) and O (ϵ - 3 / 2) are derived for g being a finite average and a general expectation respectively, for both component mapping and Jacobian evaluations. [ABSTRACT FROM AUTHOR]

Gradient-based optimization algorithms can be studied from the perspective of limiting ordinary differential equations (ODEs). Motivated by the fact that existing ODEs do not distinguish between two fundamentally different algorithms—Nesterov's accelerated gradient method for strongly convex functions (NAG-SC) and Polyak's heavy-ball method—we study an alternative limiting process that yields high-resolution ODEs. We show that these ODEs permit a general Lyapunov function framework for the analysis of convergence in both continuous and discrete time. We also show that these ODEs are more accurate surrogates for the underlying algorithms; in particular, they not only distinguish between NAG-SC and Polyak's heavy-ball method, but they allow the identification of a term that we refer to as "gradient correction" that is present in NAG-SC but not in the heavy-ball method and is responsible for the qualitative difference in convergence of the two methods. We also use the high-resolution ODE framework to study Nesterov's accelerated gradient method for (non-strongly) convex functions, uncovering a hitherto unknown result—that NAG-C minimizes the squared gradient norm at an inverse cubic rate. Finally, by modifying the high-resolution ODE of NAG-C, we obtain a family of new optimization methods that are shown to maintain the accelerated convergence rates of NAG-C for smooth convex functions. [ABSTRACT FROM AUTHOR]

We study robustness properties of some iterative gradient-based methods for strongly convex functions, as well as for the larger class of functions with sector-bounded gradients, under a relative error model. Proofs of the corresponding convergence rates are based on frequency-domain criteria for the stability of nonlinear systems. Applications are given to inexact versions of gradient descent and the Triple Momentum Method. To further emphasize the usefulness of frequency-domain methods, we derive improved analytic bounds for the convergence rate of Nesterov's accelerated method (in the exact setting) on strongly convex functions. [ABSTRACT FROM AUTHOR]

A classic result by Cook, Gerards, Schrijver, and Tardos provides an upper bound of n Δ on the proximity of optimal solutions of an Integer Linear Programming problem and its standard linear relaxation. In this bound, n is the number of variables and Δ denotes the maximum of the absolute values of the subdeterminants of the constraint matrix. Hochbaum and Shanthikumar, and Werman and Magagnosc showed that the same upper bound is valid if a more general convex function is minimized, instead of a linear function. No proximity result of this type is known when the objective function is nonconvex. In fact, if we minimize a concave quadratic, no upper bound can be given as a function of n and Δ . Our key observation is that, in this setting, proximity phenomena still occur, but only if we consider also approximate solutions instead of optimal solutions only. In our main result we provide upper bounds on the distance between approximate (resp., optimal) solutions to a Concave Integer Quadratic Programming problem and optimal (resp., approximate) solutions of its continuous relaxation. Our bounds are functions of n , Δ , and a parameter ϵ that controls the quality of the approximation. Furthermore, we discuss how far from optimal are our proximity bounds. [ABSTRACT FROM AUTHOR]

Minimizing a convex function of a measure with a sparsity-inducing penalty is a typical problem arising, e.g., in sparse spikes deconvolution or two-layer neural networks training. We show that this problem can be solved by discretizing the measure and running non-convex gradient descent on the positions and weights of the particles. For measures on a d-dimensional manifold and under some non-degeneracy assumptions, this leads to a global optimization algorithm with a complexity scaling as log (1 / ϵ) in the desired accuracy ϵ , instead of ϵ - d for convex methods. The key theoretical tools are a local convergence analysis in Wasserstein space and an analysis of a perturbed mirror descent in the space of measures. Our bounds involve quantities that are exponential in d which is unavoidable under our assumptions. [ABSTRACT FROM AUTHOR]

In a Hilbert space H , we introduce a new class of first-order algorithms which naturally occur as discrete temporal versions of an inertial differential inclusion jointly involving viscous friction and dry friction. The function f : H → R to be minimized is supposed to be differentiable (not necessarily convex), and enters the algorithm via its gradient. The dry friction damping function ϕ : H → R + is convex with a sharp minimum at the origin, (typically ϕ (x) = r ‖ x ‖ with r > 0 ). It enters the algorithm via its proximal mapping, which acts as a soft threshold operator on the velocities. As a result, we obtain a new class of splitting algorithms involving separately the proximal and gradient steps. The sequence of iterates has a finite length, and therefore strongly converges towards an approximate critical point x ∞ of f (typically ‖ ∇ f (x ∞) ‖ ≤ r ). Under a geometric property satisfied by the limit point x ∞ , we obtain geometric and finite rates of convergence. The convergence results tolerate the presence of errors, under the sole assumption of their asymptotic convergence towards zero. By replacing the function f by its Moreau envelope, we extend the results to the case of nonsmooth convex functions. In this case, the algorithm involves the proximal operators of f and ϕ separately. Several variants of this algorithm are considered, including the case of the Nesterov accelerated gradient method. We then consider the extension in the case of additive composite optimization, thus leading to new splitting methods. Numerical experiments are given for Lasso-type problems. The performance profiles, as a comparison tool, demonstrate the efficiency of the Nesterov accelerated method with asymptotic vanishing damping combined with dry friction. [ABSTRACT FROM AUTHOR]

In a Hilbert space setting, for convex optimization, we analyze the convergence rate of a class of first-order algorithms involving inertial features. They can be interpreted as discrete time versions of inertial dynamics involving both viscous and Hessian-driven dampings. The geometrical damping driven by the Hessian intervenes in the dynamics in the form ∇ 2 f (x (t)) x ˙ (t) . By treating this term as the time derivative of ∇ f (x (t)) , this gives, in discretized form, first-order algorithms in time and space. In addition to the convergence properties attached to Nesterov-type accelerated gradient methods, the algorithms thus obtained are new and show a rapid convergence towards zero of the gradients. On the basis of a regularization technique using the Moreau envelope, we extend these methods to non-smooth convex functions with extended real values. The introduction of time scale factors makes it possible to further accelerate these algorithms. We also report numerical results on structured problems to support our theoretical findings. [ABSTRACT FROM AUTHOR]

We consider the generalized trust region subproblem (GTRS) of minimizing a nonconvex quadratic objective over a nonconvex quadratic constraint. A lifting of this problem recasts the GTRS as minimizing a linear objective subject to two nonconvex quadratic constraints. Our first main contribution is structural: we give an explicit description of the convex hull of this nonconvex set in terms of the generalized eigenvalues of an associated matrix pencil. This result may be of interest in building relaxations for nonconvex quadratic programs. Moreover, this result allows us to reformulate the GTRS as the minimization of two convex quadratic functions in the original space. Our next set of contributions is algorithmic: we present an algorithm for solving the GTRS up to an ϵ additive error based on this reformulation. We carefully handle numerical issues that arise from inexact generalized eigenvalue and eigenvector computations and establish explicit running time guarantees for these algorithms. Notably, our algorithms run in linear (in the size of the input) time. Furthermore, our algorithm for computing an ϵ -optimal solution has a slightly-improved running time dependence on ϵ over the state-of-the-art algorithm. Our analysis shows that the dominant cost in solving the GTRS lies in solving a generalized eigenvalue problem—establishing a natural connection between these problems. Finally, generalizations of our convex hull results allow us to apply our algorithms and their theoretical guarantees directly to equality-, interval-, and hollow-constrained variants of the GTRS. This gives the first linear-time algorithm in the literature for these variants of the GTRS. [ABSTRACT FROM AUTHOR]

We seek tight bounds on the viable parallelism in asynchronous implementations of coordinate descent that achieves linear speedup. We focus on asynchronous coordinate descent (ACD) algorithms on convex functions which consist of the sum of a smooth convex part and a possibly non-smooth separable convex part. We quantify the shortfall in progress compared to the standard sequential stochastic gradient descent. This leads to a simple yet tight analysis of the standard stochastic ACD in a partially asynchronous environment, generalizing and improving the bounds in prior work. We also give a considerably more involved analysis for general asynchronous environments in which the only constraint is that each update can overlap with at most q others. The new lower bound on the maximum degree of parallelism attaining linear speedup is tight and improves the best prior bound almost quadratically. [ABSTRACT FROM AUTHOR]

We study the computation and efficiency of pure Nash equilibria in combinatorial congestion games, where the strategies of each player i are given by the binary vectors of a polytope P i . Our main goal is to understand which structural properties of such polytopal congestion games enable us to derive an efficient equilibrium selection procedure to compute pure Nash equilibria with attractive social cost approximation guarantees. To this aim, we identify two general properties of the underlying aggregation polytope P N = ∑ i P i which are sufficient for our results to go through, namely the integer decomposition property (IDP) and the box-totally dual integrality property (box-TDI). Our main results for polytopal congestion games satisfying IDP and box-TDI are as follows: (i) we show that pure Nash equilibria can be computed in polynomial time. In fact, we obtain this result through a general framework for separable convex function minimization, which might be of independent interest. (ii) We bound the inefficiency of these equilibria and show that this provides a tight bound on the price of stability. (iii) We also prove that these results extend to strong equilibria for the "bottleneck variant" of polytopal congestion games. Examples of polytopal congestion games satisfying IDP and box-TDI include common source network congestion games, symmetric totally unimodular congestion games, non-symmetric matroid congestion games and symmetric matroid intersection congestion games (in particular, r-arborescences and strongly base-orderable matroids). [ABSTRACT FROM AUTHOR]

We investigate an inertial algorithm of gradient type in connection with the minimization of a non-convex differentiable function. The algorithm is formulated in the spirit of Nesterov's accelerated convex gradient method. We prove some abstract convergence results which applied to our numerical scheme allow us to show that the generated sequences converge to a critical point of the objective function, provided a regularization of the objective function satisfies the Kurdyka–Łojasiewicz property. Further, we obtain convergence rates for the generated sequences and the objective function values formulated in terms of the Łojasiewicz exponent of a regularization of the objective function. Finally, some numerical experiments are presented in order to compare our numerical scheme and some algorithms well known in the literature. [ABSTRACT FROM AUTHOR]

We present an approach to regularize and approximate solution mappings of parametric convex optimization problems that combines interior penalty (log-barrier) solutions with Tikhonov regularization. Because the regularized mappings are single-valued and smooth under reasonable conditions, they can be used to build a computationally practical smoothing for the associated optimal value function. The value function in question, while resulting from parameterized convex problems, need not be convex. One motivating application of interest is two-stage (possibly nonconvex) stochastic programming. We show that our approach, being computationally implementable, provides locally bounded upper bounds for the subdifferential of the value function of qualified convex problems. As a by-product of our development, we also recover that in the given setting the value function is locally Lipschitz continuous. Numerical experiments are presented for two-stage convex stochastic programming problems, comparing the approach with the bundle method for nonsmooth optimization. [ABSTRACT FROM AUTHOR]

We characterize the closed convex subsets of R n which have open or closed Gauss ranges. Some special attention is paid to epigraphs of lower semicontinuous convex functions. [ABSTRACT FROM AUTHOR]

We establish necessary and sufficient conditions for strong duality of extended monotropic optimization problems with possibly infinite sum of separable functions. The results are applied to a minimization problem of the infinite sum of proper convex functions. We consider a truncation method for duality and obtain the zero duality gap by using only dual variable of finite support. An application to minimum cost flow problems in infinite networks is also discussed. [ABSTRACT FROM AUTHOR]