Search

The EM (Expectation-Maximization) algorithm is regarded as an MM (Majorization-Minimization) algorithm for maximum likelihood estimation of statistical models. Expanding this view, this paper demonstrates that by choosing an appropriate probability distribution, even nonstatistical optimization problem can be cast as a negative log-likelihood-like minimization problem, which can be approached by an EM (or MM) algorithm. When a polynomial objective is optimized over a simple polyhedral feasible set and an exponential family distribution is employed, the EM algorithm can be reduced to a natural gradient descent of the employed distribution with a constant step size. This is demonstrated through three examples. In this paper, we demonstrate the global convergence of specific cases with some exponential family distributions in a general form. In instances when the feasible set is not sufficiently simple, the use of MM algorithms can nevertheless be adequately described. When the objective is to minimize a convex quadratic function and the constraints are polyhedral, global convergence can also be established based on the existing results for an entropy-like proximal point algorithm.

This paper presents a new approach to selecting knots at the same time as estimating the B-spline regression model. Such simultaneous selection of knots and model is not trivial, but our strategy can make it possible by employing a nonconvex regularization on the least square method that is usually applied. More specifically, motivated by the constraint that directly designates (the upper bound of) the number of knots to be used, we present an (unconstrained) regularized least square reformulation, which is later shown to be equivalent to the motivating cardinality-constrained formulation. The obtained formulation is further modified so that we can employ a proximal gradient-type algorithm, known as GIST, for a class of non-smooth non-convex optimization problems. We show that under a mild technical assumption, the algorithm is shown to reach a local minimum of the problem. Since it is shown that any local minimum of the problem satisfies the cardinality constraint, the proposed algorithm can be used to obtain a spline regression model that depends only on a designated number of knots at most. Numerical experiments demonstrate how our approach performs on synthetic and real data sets.

This paper studies the properties of d-stationary points of the trimmed lasso (Luo et al., 2013, Huang et al., 2015, and Gotoh et al., 2018) and the composite optimization problem with the truncated nuclear norm (Gao and Sun, 2010, and Zhang et al., 2012), which are known as tight relaxations of nonconvex optimization problems that have either cardinality or rank constraints, respectively. First, we extend the trimmed lasso for broader applications and for conducting a unified analysis of the property of the generalized trimmed lasso. Next, the equivalence between local optimality and d-stationarity of the generalized trimmed lasso is shown under a suitable assumption. More generally, the equivalence is shown for problems that minimize a function defined by the pointwise minimum of finitely many convex functions. Then, we present new results of the exact penalty at d-stationary points of the generalized trimmed lasso and the problem with the truncated nuclear norm penalty under mild assumptions. Our exact penalty results are not only new, but also intuitive, so that we can see what properties of the problems play a role for establishing the exact penalization. Lastly, matters relating to algorithms are also discussed.

While solutions of Distributionally Robust Optimization (DRO) problems can sometimes have a higher out-of-sample expected reward than the Sample Average Approximation (SAA), there is no guarantee. In this paper, we introduce a class of Distributionally Optimistic Optimization (DOO) models, and show that it is always possible to ``beat" SAA out-of-sample if we consider not just worst-case (DRO) models but also best-case (DOO) ones. We also show, however, that this comes at a cost: Optimistic solutions are more sensitive to model error than either worst-case or SAA optimizers, and hence are less robust and calibrating the worst- or best-case model to outperform SAA may be difficult when data is limited., Comment: 25 pages, 2 page bibliography, 2 Figures, 12 page Appendix

Network Lasso (NL for short) is a methodology for estimating models by simultaneously clustering data samples and fitting the models to the samples. It often succeeds in forming clusters thanks to the geometry of the $\ell_1$-regularizer employed therein, but there might be limitations because of the convexity of the regularizer. This paper focuses on the cluster structure that NL yields and reinforces it by developing a non-convex extension, which we call Network Trimmed Lasso (NTL for short). Specifically, we first study a sufficient condition that guarantees the recovery of the latent cluster structure of NL on the basis of the result of Sun et al. (2021) for Convex Clustering, which is a special case of NL for clustering. Second, we extend NL to NTL to incorporate a cardinality (or, $\ell_0$-)constraint and rewrite the constrained optimization problem defined with the $\ell_0$ norm, a discontinuous function, into an equivalent unconstrained continuous optimization problem. We develop ADMM algorithms to solve NTL and provide its convergence results. Numerical illustrations demonstrate that the non-convex extension provides a more clear-cut cluster structure when NL fails to form clusters without incorporating prior knowledge of the associated parameters.

We introduce the notion of Worst-Case Sensitivity, defined as the worst-case rate of increase in the expected cost of a Distributionally Robust Optimization (DRO) model when the size of the uncertainty set vanishes. We show that worst-case sensitivity is a Generalized Measure of Deviation and that a large class of DRO models are essentially mean-(worst-case) sensitivity problems when uncertainty sets are small, unifying recent results on the relationship between DRO and regularized empirical optimization with worst-case sensitivity playing the role of the regularizer. More generally, DRO solutions can be sensitive to the family and size of the uncertainty set, and reflect the properties of its worst-case sensitivity. We derive closed-form expressions of worst-case sensitivity for well known uncertainty sets including smooth $\phi$-divergence, total variation, "budgeted" uncertainty sets, uncertainty sets corresponding to a convex combination of expected value and CVaR, and the Wasserstein metric. These can be used to select the uncertainty set and its size for a given application., Comment: 27 Pages + 11 page Appendix, 4 Figures

This paper conducts a comparative study of proximal gradient methods (PGMs) and proximal DC algorithms (PDCAs) for sparse regression problems which can be cast as Difference-of-two-Convex-functions (DC) optimization problems. It has been shown that for DC optimization problems, both General Iterative Shrinkage and Thresholding algorithm (GIST), a modified version of PGM, and PDCA converge to critical points. Recently some enhanced versions of PDCAs are shown to converge to d-stationary points, which are stronger necessary condition for local optimality than critical points. In this paper we claim that without any modification, PGMs converge to a d-stationary point not only to DC problems but also to more general nonsmooth nonconvex problems under some technical assumptions. While the convergence to d-stationary points is known for the case where the step size is small enough, the finding of this paper is valid also for extended versions such as GIST and its alternating optimization version, which is to be developed in this paper. Numerical results show that among several algorithms in the two categories, modified versions of PGM perform best among those not only in solution quality but also in computation time., Comment: Theorem 5.2. and its proof; We have added an assumption and modified the proof because the previous version (and Theorem 2 of the published version in Optimization Letters) had some mathematical errors. Furthermore, we have corrected some typos

We study the out-of-sample properties of robust empirical optimization problems with smooth $\phi$-divergence penalties and smooth concave objective functions, and develop a theory for data-driven calibration of the non-negative "robustness parameter" $\delta$ that controls the size of the deviations from the nominal model. Building on the intuition that robust optimization reduces the sensitivity of the expected reward to errors in the model by controlling the spread of the reward distribution, we show that the first-order benefit of ``little bit of robustness" (i.e., $\delta$ small, positive) is a significant reduction in the variance of the out-of-sample reward while the corresponding impact on the mean is almost an order of magnitude smaller. One implication is that substantial variance (sensitivity) reduction is possible at little cost if the robustness parameter is properly calibrated. To this end, we introduce the notion of a robust mean-variance frontier to select the robustness parameter and show that it can be approximated using resampling methods like the bootstrap. Our examples show that robust solutions resulting from "open loop" calibration methods (e.g., selecting a $90\%$ confidence level regardless of the data and objective function) can be very conservative out-of-sample, while those corresponding to the robustness parameter that optimizes an estimate of the out-of-sample expected reward (e.g., via the bootstrap) with no regard for the variance are often insufficiently robust., Comment: 51 pages

We address the minimization of a smooth objective function under an $\ell_0$-constraint and simple convex constraints. When the problem has no constraints except the $\ell_0$-constraint, some efficient algorithms are available; for example, Proximal DC (Difference of Convex functions) Algorithm (PDCA) repeatedly evaluates closed-form solutions of convex subproblems, leading to a stationary point of the $\ell_0$-constrained problem. However, when the problem has additional convex constraints, they become inefficient because it is difficult to obtain closed-form solutions of the associated subproblems. In this paper, we reformulate the problem by employing a new DC representation of the $\ell_0$-constraint, so that PDCA can retain the efficiency by reducing its subproblems to the projection operation onto a convex set. Moreover, inspired by the Nesterov's acceleration technique for proximal methods, we propose the Accelerated PDCA (APDCA), which attains the optimal convergence rate if applied to convex programs, and performs well in numerical experiments.