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
Franco, Sebastían; Gukov, Sergei; Lee, Sangmin; Seong, Rak-Kyeong; Sparks, James
(, Journal of High Energy Physics)
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.
Davarnia, Danial; Kiaghadi, Mohammadreza
(, International Conference on Artificial Intelligence and Statistics; Proceedings of Machine Learning Research)
Li, Yingzhen; Mandt, Stephan; Agrawal, Shipra; Khan, Emtiyaz
(Ed.)
Optimization problems with norm-bounding constraints appear in various applications, from portfolio optimization to machine learning, feature selection, and beyond. A widely used variant of these problems relaxes the norm-bounding constraint through Lagrangian relaxation and moves it to the objective function as a form of penalty or regularization term. A challenging class of these models uses the zero-norm function to induce sparsity in statistical parameter estimation models. Most existing exact solution methods for these problems use additional binary variables together with artificial bounds on variables to formulate them as a mixed-integer program in a higher dimension, which is then solved by off-the-shelf solvers. Other exact methods utilize specific structural properties of the objective function to solve certain variants of these problems, making them non-generalizable to other problems with different structures. An alternative approach employs nonconvex penalties with desirable statistical properties, which are solved using heuristic or local methods due to the structural complexity of those terms. In this paper, we develop a novel graph-based method to globally solve optimization problems that contain a generalization of norm-bounding constraints. This includes standard ℓp-norms for p∈[0,∞) as well as nonconvex penalty terms, such as SCAD and MCP, as special cases. Our method uses decision diagrams to build strong convex relaxations for these constraints in the original space of variables without the need to introduce additional auxiliary variables or impose artificial variable bounds. We show that the resulting convexification method, when incorporated into a spatial branch-and-cut framework, converges to the global optimal value of the problem. To demonstrate the capabilities of the proposed framework, we conduct preliminary computational experiments on benchmark sparse linear regression problems with challenging nonconvex penalty terms that cannot be modeled or solved by existing global solvers.
Garcia, Jorge Silva; Ohsawa, Tomoki
(, 2022 IEEE 61st Conference on Decision and Control (CDC))
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.
CSP sparsification, introduced by Kogan and Krauthgamer (ITCS 2015), considers the following question: how much can an instance of a constraint satisfaction problem be sparsified (by retaining a reweighted subset of the constraints) while still roughly capturing the weight of constraints satisfied by {\em every} assignment. CSP sparsification captures as a special case several well-studied problems including graph cut-sparsification, hypergraph cut-sparsification, hypergraph XOR-sparsification, and corresponds to a general class of hypergraph sparsification problems where an arbitrary 0/1-valued {\em splitting function} is used to define the notion of cutting a hyperedge (see, for instance, Veldt-Benson-Kleinberg SIAM Review 2022). The main question here is to understand, for a given constraint predicate P:Σr→{0,1} (where variables are assigned values in Σ), the smallest constant c such that O˜(nc) sized sparsifiers exist for every instance of a constraint satisfaction problem over P. A recent work of Khanna, Putterman and Sudan (SODA 2024) [KPS24] showed {\em existence} of near-linear size sparsifiers for new classes of CSPs. In this work (1) we significantly extend the class of CSPs for which nearly linear-size sparsifications can be shown to exist while also extending the scope to settings with non-linear-sized sparsifications; (2) we give a polynomial-time algorithm to extract such sparsifications for all the problems we study including the first efficient sparsification algorithms for the problems studied in [KPS24].
Anari, N; Haghtalab, N.; Naor, S; Pokutta, S.; Singh, M.; Torrico, A.
(, 22nd International Conference on Artificial Intelligence and Statistics (AISTATS) 2019)
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.
Chen, Zhehui, Li, Xingguo, Yang, Lin, Haupt, Jarvis, and Zhao, Tuo. On Constrained Nonconvex Stochastic Optimization: A Case Study for Generalized Eigenvalue Decomposition. Retrieved from https://par.nsf.gov/biblio/10105385. International Conference on Artificial Intelligence and Statistics .
Chen, Zhehui, Li, Xingguo, Yang, Lin, Haupt, Jarvis, & Zhao, Tuo. On Constrained Nonconvex Stochastic Optimization: A Case Study for Generalized Eigenvalue Decomposition. International Conference on Artificial Intelligence and Statistics, (). Retrieved from https://par.nsf.gov/biblio/10105385.
Chen, Zhehui, Li, Xingguo, Yang, Lin, Haupt, Jarvis, and Zhao, Tuo.
"On Constrained Nonconvex Stochastic Optimization: A Case Study for Generalized Eigenvalue Decomposition". International Conference on Artificial Intelligence and Statistics (). Country unknown/Code not available. https://par.nsf.gov/biblio/10105385.
@article{osti_10105385,
place = {Country unknown/Code not available},
title = {On Constrained Nonconvex Stochastic Optimization: A Case Study for Generalized Eigenvalue Decomposition},
url = {https://par.nsf.gov/biblio/10105385},
abstractNote = {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.},
journal = {International Conference on Artificial Intelligence and Statistics},
author = {Chen, Zhehui and Li, Xingguo and Yang, Lin and Haupt, Jarvis and Zhao, Tuo},
}
Warning: Leaving National Science Foundation Website
You are now leaving the National Science Foundation website to go to a non-government website.
Website:
NSF takes no responsibility for and exercises no control over the views expressed or the accuracy of
the information contained on this site. Also be aware that NSF's privacy policy does not apply to this site.
An official website of the United States government
