Search

The spectral risk has wide applications in machine learning, especially in real-world decision-making, where people are not only concerned with models' average performance. By assigning different weights to the losses of different sample points, rather than the same weights as in the empirical risk, it allows the model's performance to lie between the average performance and the worst-case performance. In this paper, we propose SOREL, the first stochastic gradient-based algorithm with convergence guarantees for the spectral risk minimization. Previous algorithms often consider adding a strongly concave function to smooth the spectral risk, thus lacking convergence guarantees for the original spectral risk. We theoretically prove that our algorithm achieves a near-optimal rate of $\widetilde{O}(1/\sqrt{\epsilon})$ in terms of $\epsilon$. Experiments on real datasets show that our algorithm outperforms existing algorithms in most cases, both in terms of runtime and sample complexity.

Hyperparameter tuning is an important task of machine learning, which can be formulated as a bilevel program (BLP). However, most existing algorithms are not applicable for BLP with non-smooth lower-level problems. To address this, we propose a single-level reformulation of the BLP based on lower-level duality without involving any implicit value function. To solve the reformulation, we propose a majorization minimization algorithm that marjorizes the constraint in each iteration. Furthermore, we show that the subproblems of the proposed algorithm for several widely used hyperparameter turning models can be reformulated into conic programs that can be efficiently solved by the off-the-shelf solvers. We theoretically prove the convergence of the proposed algorithm and demonstrate its superiority through numerical experiments., Comment: Accepted by AISTATS 2024

This paper studies a class of simple bilevel optimization problems where we minimize a composite convex function at the upper-level subject to a composite convex lower-level problem. Existing methods either provide asymptotic guarantees for the upper-level objective or attain slow sublinear convergence rates. We propose a bisection algorithm to find a solution that is $\epsilon_f$-optimal for the upper-level objective and $\epsilon_g$-optimal for the lower-level objective. In each iteration, the binary search narrows the interval by assessing inequality system feasibility. Under mild conditions, the total operation complexity of our method is ${\tilde {\mathcal{O}}}\left(\max\{\sqrt{L_{f_1}/\epsilon_f},\sqrt{L_{g_1}/\epsilon_g} \} \right)$. Here, a unit operation can be a function evaluation, gradient evaluation, or the invocation of the proximal mapping, $L_{f_1}$ and $L_{g_1}$ are the Lipschitz constants of the upper- and lower-level objectives' smooth components, and ${\tilde {\mathcal{O}}}$ hides logarithmic terms. Our approach achieves a near-optimal rate, matching the optimal rate in unconstrained smooth or composite convex optimization when disregarding logarithmic terms. Numerical experiments demonstrate the effectiveness of our method., Comment: Accepted to AISTATS2024

This paper investigates simple bilevel optimization problems where the upper-level objective minimizes a composite convex function over the optimal solutions of a composite convex lower-level problem. Existing methods for such problems either only guarantee asymptotic convergence, have slow sublinear rates, or require strong assumptions. To address these challenges, we develop a novel penalty-based approach that employs the accelerated proximal gradient (APG) method. Under an $\alpha$-H\"{o}lderian error bound condition on the lower-level objective, our algorithm attains an $(\epsilon,l_F^{-\beta}\epsilon^{\beta})$-optimal solution for any $\beta>0$ within $\mathcal{O}\left(\sqrt{\frac{L_{f_1}}{\epsilon }}\right)+\mathcal{O}\left(\sqrt{\frac{l_F^{\max\{\alpha,\beta\}}L_{g_1}}{\epsilon^{\max\{\alpha,\beta\}}}}\right)$ iterations, where $l_F$, $L_{f_1}$ and $L_{g_1}$ denote the Lipschitz constants of the upper-level objective, the gradients of the smooth parts of the upper- and lower-level objectives, respectively. If the smooth part of the upper-level objective is strongly convex, the result improves further. We also establish the complexity results when both upper- and lower-level objectives are general convex nonsmooth functions. Numerical experiments demonstrate the effectiveness of our algorithms.

The empirical loss, commonly referred to as the average loss, is extensively utilized for training machine learning models. However, in order to address the diverse performance requirements of machine learning models, the use of the rank-based loss is prevalent, replacing the empirical loss in many cases. The rank-based loss comprises a weighted sum of sorted individual losses, encompassing both convex losses like the spectral risk, which includes the empirical risk and conditional value-at-risk, and nonconvex losses such as the human-aligned risk and the sum of the ranked range loss. In this paper, we introduce a unified framework for the optimization of the rank-based loss through the utilization of a proximal alternating direction method of multipliers. We demonstrate the convergence and convergence rate of the proposed algorithm under mild conditions. Experiments conducted on synthetic and real datasets illustrate the effectiveness and efficiency of the proposed algorithm., Comment: conference

This paper presents strong worst-case iteration and operation complexity guarantees for Riemannian adaptive regularized Newton methods, a unified framework encompassing both Riemannian adaptive regularization (RAR) methods and Riemannian trust region (RTR) methods. We comprehensively characterize the sources of approximation in second-order manifold optimization methods: the objective function's smoothness, retraction's smoothness, and subproblem solver's inexactness. Specifically, for a function with a $\mu$-H\"older continuous Hessian, when equipped with a retraction featuring a $\nu$-H\"older continuous differential and a $\theta$-inexact subproblem solver, both RTR and RAR with $2+\alpha$ regularization (where $\alpha=\min\{\mu,\nu,\theta\}$) locate an $(\epsilon,\epsilon^{\alpha/(1+\alpha)})$-approximate second-order stationary point within at most $O(\epsilon^{-(2+\alpha)/(1+\alpha)})$ iterations and at most $\tilde{O}(\epsilon^{-(4+3\alpha)/(2(1+\alpha))})$ Hessian-vector products. These complexity results are novel and sharp, and reduce to an iteration complexity of $O(\epsilon^{-3/2})$ and an operation complexity of $\tilde{O}(\epsilon^{-7/4})$ when $\alpha=1$.

Manifold optimization has recently gained significant attention due to its wide range of applications in various areas. This paper introduces the first Riemannian trust region method for minimizing an SC$^1$ function, which is a differentiable function that has a semismooth gradient vector field, on manifolds with convergence guarantee. We provide proof of both global and local convergence results, along with demonstrating the local superlinear convergence rate of our proposed method. As an application and to demonstrate our motivation, we utilize our trust region method as a subproblem solver within an augmented Lagrangian method for minimizing nonsmooth nonconvex functions over manifolds. This represents the first approach that fully explores the second-order information of the subproblem in the context of augmented Lagrangian methods on manifolds. Numerical experiments confirm that our method outperforms existing methods.

In recent years, the proximal gradient method and its variants have been generalized to Riemannian manifolds for solving optimization problems with an additively separable structure, i.e., $f + h$, where $f$ is continuously differentiable, and $h$ may be nonsmooth but convex with computationally reasonable proximal mapping. In this paper, we generalize the proximal Newton method to embedded submanifolds for solving the type of problem with $h(x) = \mu \|x\|_1$. The generalization relies on the Weingarten and semismooth analysis. It is shown that the Riemannian proximal Newton method has a local quadratic convergence rate under certain reasonable assumptions. Moreover, a hybrid version is given by concatenating a Riemannian proximal gradient method and the Riemannian proximal Newton method. It is shown that if the switch parameter is chosen appropriately, then the hybrid method converges globally and also has a local quadratic convergence rate. Numerical experiments on random and synthetic data are used to demonstrate the performance of the proposed methods., Comment: Updates compared to the previous version: *) the updates for the published version. Additionally updates: *) local quadratic convergence rate *) update the proofs of Lemma 3.3. *) update the proofs of Proposition 3.13

Chance constrained programming (CCP) refers to a type of optimization problem with uncertain constraints that are satisfied with at least a prescribed probability level. In this work, we study the sample average approximation (SAA) of chance constraints. This is an important approach to solving CCP, especially in the data-driven setting where only a sample of multiple realizations of the random vector in the chance constraints is available. The SAA is obtained by replacing the underlying distribution with an empirical distribution over the available sample. Assuming that the functions in chance constraints are all convex, we reformulate the SAA of chance constraints into a difference-of-convex (DC) form. Moreover, considering that the objective function is a difference-of-convex function, the resulting formulation becomes a DC constrained DC program. Then, we propose a proximal DC algorithm for solving this reformulation. In particular, we show that the subproblems of the proximal DC are suitable for off-the-shelf solvers in some scenarios. Moreover, we not only prove the subsequential and sequential convergence of the proposed algorithm but also derive the iteration complexity for finding an approximate Karush-Kuhn-Tucker point. To support and complement our theoretical development, we show via numerical experiments that our proposed approach is competitive with a host of existing approaches., Comment: 43 pages, 4 tables

This paper proposes a novel numerical method for solving the problem of decision making under cumulative prospect theory (CPT), where the goal is to maximize utility subject to practical constraints, assuming only finite realizations of the associated distribution are available. Existing methods for CPT optimization rely on particular assumptions that may not hold in practice. To overcome this limitation, we present the first numerical method with a theoretical guarantee for solving CPT optimization using an alternating direction method of multipliers (ADMM). One of its subproblems involves optimization with the CPT utility subject to a chain constraint, which presents a significant challenge. To address this, we develop two methods for solving this subproblem. The first method uses dynamic programming, while the second method is a modified version of the pooling-adjacent-violators algorithm that incorporates the CPT utility function. Moreover, we prove the theoretical convergence of our proposed ADMM method and the two subproblem-solving methods. Finally, we conduct numerical experiments to validate our proposed approach and demonstrate how CPT's parameters influence investor behavior using real-world data., Comment: 32 pages

The Stackelberg prediction game (SPG) is popular in characterizing strategic interactions between a learner and an attacker. As an important special case, the SPG with least squares loss (SPG-LS) has recently received much research attention. Although initially formulated as a difficult bi-level optimization problem, SPG-LS admits tractable reformulations which can be polynomially globally solved by semidefinite programming or second order cone programming. However, all the available approaches are not well-suited for handling large-scale datasets, especially those with huge numbers of features. In this paper, we explore an alternative reformulation of the SPG-LS. By a novel nonlinear change of variables, we rewrite the SPG-LS as a spherically constrained least squares (SCLS) problem. Theoretically, we show that an $\epsilon$ optimal solution to the SCLS (and the SPG-LS) can be achieved in $\tilde{O}(N/\sqrt{\epsilon})$ floating-point operations, where $N$ is the number of nonzero entries in the data matrix. Practically, we apply two well-known methods for solving this new reformulation, i.e., the Krylov subspace method and the Riemannian trust region method. Both algorithms are factorization free so that they are suitable for solving large scale problems. Numerical results on both synthetic and real-world datasets indicate that the SPG-LS, equipped with the SCLS reformulation, can be solved orders of magnitude faster than the state of the art.

Subset-sum problems belong to the NP class and play an important role in both complexity theory and knapsack-based cryptosystems, which have been proved in the literature to become hardest when the so-called density approaches one. Lattice attacks, which are acknowledged in the literature as the most effective methods, fail occasionally even when the number of unknown variables is of medium size. In this paper we propose a modular disaggregation technique and a simplified lattice formulation based on which two lattice attack algorithms are further designed. We introduce the new concept "jump points" in our disaggregation technique, and derive inequality conditions to identify superior jump points which can more easily cut-off non-desirable short integer solutions. Empirical tests have been conducted to show that integrating the disaggregation technique with lattice attacks can effectively raise success ratios to 100% for randomly generated problems with density one and of dimensions up to 100. Finally, statistical regressions are conducted to test significant features, thus revealing reasonable factors behind the empirical success of our algorithms and techniques proposed in this paper., Comment: 50 pages, 6 figures, 17 tables

The cubic regularization (CR) algorithm has attracted a lot of attentions in the literature in recent years. We propose a new reformulation of the cubic regularization subproblem. The reformulation is an unconstrained convex problem that requires computing the minimum eigenvalue of the Hessian. Then based on this reformulation, we derive a variant of the (non-adaptive) CR provided a known Lipschitz constant for the Hessian and a variant of adaptive regularization with cubics (ARC). We show that the iteration complexity of our variants matches the best known bounds for unconstrained minimization algorithms using first- and second-order information. Moreover, we show that the operation complexity of both of our variants also matches the state-of-the-art bounds in the literature. Numerical experiments on test problems from CUTEst collection show that the ARC based on our new subproblem reformulation is comparable to existing algorithms.

The Stackelberg prediction game (SPG) has been extensively used to model the interactions between the learner and data provider in the training process of various machine learning algorithms. Particularly, SPGs played prominent roles in cybersecurity applications, such as intrusion detection, banking fraud detection, spam filtering, and malware detection. Often formulated as NP-hard bi-level optimization problems, it is generally computationally intractable to find global solutions to SPGs. As an interesting progress in this area, a special class of SPGs with the least squares loss (SPG-LS) have recently been shown polynomially solvable by a bisection method. However, in each iteration of this method, a semidefinite program (SDP) needs to be solved. The resulted high computational costs prevent its applications for large-scale problems. In contrast, we propose a novel approach that reformulates a SPG-LS as a single SDP of a similar form and the same dimension as those solved in the bisection method. Our SDP reformulation is, evidenced by our numerical experiments, orders of magnitude faster than the existing bisection method. We further show that the obtained SDP can be reduced to a second order cone program (SOCP). This allows us to provide real-time response to large-scale SPG-LS problems. Numerical results on both synthetic and real world datasets indicate that the proposed SOCP method is up to 20,000+ times faster than the state of the art.

A set of quadratic forms is simultaneously diagonalizable via congruence (SDC) if there exists a basis under which each of the quadratic forms is diagonal. This property appears naturally when analyzing quadratically constrained quadratic programs (QCQPs) and has important implications in this context. This paper extends the reach of the SDC property by studying two new related but weaker notions of simultaneous diagonalizability. Specifically, we say that a set of quadratic forms is almost SDC (ASDC) if it is the limit of SDC sets and d-restricted SDC (d-RSDC) if it is the restriction of an SDC set in up to d-many additional dimensions. Our main contributions are a complete characterization of the ASDC pairs and the nonsingular ASDC triples, as well as a sufficient condition for the 1-RSDC property for pairs of quadratic forms. Surprisingly, we show that every singular pair is ASDC and that almost every pair is 1-RSDC. We accompany our theoretical results with preliminary numerical experiments applying the RSDC property to QCQPs with a single quadratic constraint.

We propose a first-order method to solve the cubic regularization subproblem (CRS) based on a novel reformulation. The reformulation is a constrained convex optimization problem whose feasible region admits an easily computable projection. Our reformulation requires computing the minimum eigenvalue of the Hessian. To avoid the expensive computation of the exact minimum eigenvalue, we develop a surrogate problem to the reformulation where the exact minimum eigenvalue is replaced with an approximate one. We then apply first-order methods such as the Nesterov's accelerated projected gradient method (APG) and projected Barzilai-Borwein method to solve the surrogate problem. As our main theoretical contribution, we show that when an $\epsilon$-approximate minimum eigenvalue is computed by the Lanczos method and the surrogate problem is approximately solved by APG, our approach returns an $\epsilon$-approximate solution to CRS in $\tilde O(\epsilon^{-1/2})$ matrix-vector multiplications (where $\tilde O(\cdot)$ hides the logarithmic factors). Numerical experiments show that our methods are comparable to and outperform the Krylov subspace method in the easy and hard cases, respectively. We further implement our methods as subproblem solvers of adaptive cubic regularization methods, and numerical results show that our algorithms are comparable to the state-of-the-art algorithms.

In this paper, we study the local variational geometry of the optimal solution set of the trust region subproblem (TRS), which minimizes a general, possibly nonconvex, quadratic function over the unit ball. Specifically, we demonstrate that a H\"olderian error bound holds globally for the TRS with modulus 1/4 and the Kurdyka-{\L}ojasiewicz (KL) inequality holds locally for the TRS with a KL exponent 3/4 at any optimal solution. We further prove that unless in a special case, the H\"olderian error bound modulus, as well as the KL exponent, is 1/2. Finally, based on the obtained KL property, we further show that the projected gradient methods studied in [A. Beck and Y. Vaisbourd, SIAM J. Optim., 28 (2018), pp. 1951--1967] for solving the TRS achieve a sublinear or even linear rate of convergence.

In this paper, we provide the first provable linear-time (in the number of non-zero entries of the input) algorithm for approximately solving the generalized trust region subproblem (GTRS) of minimizing a quadratic function over a quadratic constraint under some regular conditions. Our algorithm is motivated by and extends a recent linear-time algorithm for the trust region subproblem by Hazan and Koren [Math. Program., 2016, 158(1-2): 363-381]. However, due to the non-convexity and non-compactness of the feasible region, such an extension is nontrivial. Our main contribution is to demonstrate that under some regular condition, the optimal solution is in a compact and convex set and lower and upper bounds of the optimal value can be computed in linear time. Using these properties, we develop a linear-time algorithm for the GTRS.

We present a new solution framework to solve the generalized trust region subproblem (GTRS) of minimizing a quadratic objective over a quadratic constraint. More specifically, we derive a convex quadratic reformulation (CQR) via minimizing a linear objective over two convex quadratic constraints for the GTRS. We show that an optimal solution of the GTRS can be recovered from an optimal solution of the CQR. We further prove that this CQR is equivalent to minimizing the maximum of the two convex quadratic functions derived from the CQR for the case under our investigation. Although the latter minimax problem is nonsmooth, it is well-structured and convex. We thus develop two steepest descent algorithms corresponding to two different line search rules. We prove for both algorithms their global sublinear convergence rates. We also obtain a local linear convergence rate of the first algorithm by estimating the Kurdyka- Lojasiewicz exponent at any optimal solution under mild conditions. We finally demonstrate the efficiency of our algorithms in our numerical experiments.

In this paper, we present new convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP) problems. While recent research has focused on strengthening convex relaxations using reformulation-linearization technique (RLT), the state-of-the-art methods lose their effectiveness when dealing with (multiple) nonconvex quadratic constraints in QCQP. In this research, we decompose and relax each nonconvex constraint to two second order cone (SOC) constraints and then linearize the products of the SOC constraints and linear constraints to construct some effective new valid constraints. Moreover, we extend the reach of the RLT-like techniques for almost all different types of constraint-pairs (including valid inequalities by linearizing the product of a pair of SOC constraints, and the the Hadamard product or the Kronecker product of two respective valid linear matrix inequalities), examine dominance relationships among different valid inequalities, and explore almost all possibilities of gaining benefits from generating valid constraints. Especially, we successfully demonstrate that applying RLT-like techniques to additional redundant linear constraints could reduce the relaxation gap. We demonstrate the efficiency of our results with numerical experiments.

We investigate in this paper the generalized trust region subproblem (GTRS) of minimizing a general quadratic objective function subject to a general quadratic inequality constraint. By applying a simultaneous block diagonalization approach, we obtain a congruent canonical form for the symmetric matrices in both the objective and constraint functions. By exploiting the block separability of the canonical form, we show that all GTRSs with an optimal value bounded from below are second order cone programming (SOCP) representable. Our result generalizes the recent work of Ben-Tal and Hertog (Math. Program. 143(1-2):1-29, 2014), which establishes the SOCP representability of the GTRS under the assumption of the simultaneous diagonalizability of the two matrices in the objective and constraint functions. Compared with the state-of-the-art approach to reformulate the GTRS as a semi-definite programming problem, our SOCP reformulation delivers a much faster solution algorithm. We further extend our method to two variants of the GTRS in which the inequality constraint is replaced by either an equality constraint or an interval constraint. Our methods also enable us to obtain simplified versions of the classical S-lemma, the S-lemma with equality, and the S-lemma with interval bounds.

An equivalence between attainability of simultaneous diagonalization (SD) and hidden convexity in quadratically constrained quadratic programming (QCQP) stimulates us to investigate necessary and sufficient SD conditions, which is one of the open problems posted by Hiriart-Urruty (SIAM Rev., 49 (2007), pp. 255-273) nine years ago. In this paper we give a necessary and sufficient SD condition for any two real symmetric matrices and offer a necessary and sufficient SD condition for any finite collection of real symmetric matrices under the existence assumption of a semi-definite matrix pencil. Moreover, we apply our SD conditions to QCQP, especially with one or two quadratic constraints, to verify the exactness of its second-order cone programming relaxation and to facilitate the solution process of QCQP., Comment: 19 pages