skip to main content


Title: On Constrained Nonconvex Stochastic Optimization: A Case Study for Generalized Eigenvalue Decomposition
We study constrained nonconvex optimization problems in machine learning and signal processing. It is well-known that these problems can be rewritten to a min-max problem in a Lagrangian form. However, due to the lack of convexity, their landscape is not well understood and how to find the stable equilibria of the Lagrangian function is still unknown. To bridge the gap, we study the landscape of the Lagrangian function. Further, we define a special class of Lagrangian functions. They enjoy the following two properties: 1. Equilibria are either stable or unstable (Formal definition in Section 2); 2.Stable equilibria correspond to the global optima of the original problem. We show that a generalized eigenvalue (GEV) problem, including canonical correlation analysis and other problems as special examples, belongs to the class. Specifically, we characterize its stable and unstable equilibria by leveraging an invariant group and symmetric property (more details in Section 3). Motivated by these neat geometric structures, we propose a simple, efficient, and stochastic primal-dual algorithm solving the online GEV problem. Theoretically, under sufficient conditions, we establish an asymptotic rate of convergence and obtain the first sample complexity result for the online GEV problem by diffusion approximations, which are widely used in applied probability. Numerical results are also provided to support our theory.  more » « less
Award ID(s):
1717916
PAR ID:
10105385
Author(s) / Creator(s):
; ; ; ;
Date Published:
Journal Name:
International Conference on Artificial Intelligence and Statistics
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    A bstract While the study of bordered (pseudo-)holomorphic curves with boundary on Lagrangian submanifolds has a long history, a similar problem that involves (special) Lagrangian submanifolds with boundary on complex surfaces appears to be largely overlooked in both physics and math literature. We relate this problem to geometry of coassociative submanifolds in G 2 holonomy spaces and to Spin(7) metrics on 8-manifolds with T 2 fibrations. As an application to physics, we propose a large class of brane models in type IIA string theory that generalize brane brick models on the one hand and 2d theories T [ M 4 ] on the other. 
    more » « less
  2. We consider the problem of stabilizing what we call a pendulum skate, a simple model of a figure skater developed by Gzenda and Putkaradze. By exploiting the symmetry of the system as well as taking care of the part of the symmetry broken by the gravity, the equations of motion are given as nonholonomic Euler–Poincaré equation with advected parameters. Our main interest is the stability of the sliding and spinning equilibria of the system. We show that the former is unstable and the latter is stable only under certain conditions. We use the method of Controlled Lagrangians to find a control to stabilize the sliding equilibrium. 
    more » « less
  3. Constrained submodular function maximization has been used in subset selection problems such as selection of most informative sensor locations. While these models have been quite popular, the solutions obtained via this approach are unstable to perturbations in data defining the submodular functions. Robust submodular maximization has been proposed as a richer model that aims to overcome this discrepancy as well as increase the modeling scope of submodular optimization. In this work, we consider robust submodular maximization with structured combinatorial constraints and give efficient algorithms with provable guarantees. Our approach is applicable to constraints defined by single or multiple matroids, knapsack as well as distributionally robust criteria. We consider both the offline setting where the data defining the problem is known in advance as well as the online setting where the input data is revealed over time. For the offline setting, we give a nearly optimal bi-criteria approximation algorithm that relies on new extensions of the classical greedy algorithm. For the online version of the problem, we give an algorithm that returns a bi-criteria solution with sub-linear regret. 
    more » « less
  4. Abstract

    We study a class of mixed integer optimization problems with linear constraints and a multilinear objective function, the so‐called mixed integer linear maximum multiplicative programs (MIL‐MMPs). Such a problem can be transformed into a second‐order cone program (SOCP) and can be solved effectively by a commercial solver such as CPLEX. However, MIL‐MMPs can also be viewed as special cases of the problem of optimization over the set of efficient solutions in multiobjective optimization. Using this observation, we develop a criterion space search algorithm for solving any MIL‐MMP. An extensive computational study on around 2000 instances illustrates that the proposed algorithm significantly outperforms not only the CPLEX mixed integer SOCP solver but also a state‐of‐the‐art algorithm that is capable of solving special cases of MIL‐MMPs. Moreover, the computational study illustrates that even if we linearize the objective function and solve the linearized problem by CPLEX, the proposed algorithm still performs significantly better.

     
    more » « less
  5. We present measurements of the cross section for antineutrino charged-current quasielasticlike scattering on hydrocarbon using the medium energy NuMI wide-band neutrino beam peaking at antineutrino energy hE¯νi ∼ 6 GeV. The measurements are presented as a function of the longitudinal momentum (pjj) and transverse momentum (pT) of the final state muon. This work complements our previously reported high statistics measurement in the neutrino channel and extends the previous antineutrino measurement made in a low energy beam at hE¯νi ∼ 3.5 GeV out to pT of 2.5 GeV=c. Current theoretical models do not completely describe the data in this previously unexplored high pT region. The single differential cross section as a function of four-momentum transfer (Q2 QE) now extends to 4 GeV2 with high statistics. The cross section as a function of Q2 QE shows that the tuned simulations developed by the MINERvA Collaboration that agreed well with the low energy beam measurements do not agree as well with the medium energy beam measurements. Newer neutrino interaction models such as the GENIE v3 tunes are better able to simulate the high Q2 QE region. 
    more » « less