More Like this

1. Multi-Attribute Graph Estimation With Sparse-Group Non-Convex Penalties

   https://doi.org/10.1109/ACCESS.2025.3566959  

   Tugnait, Jitendra K (January 2025, IEEE Access)

   We consider the problem of inferring the conditional independence graph (CIG) of high-dimensional Gaussian vectors from multi-attribute data. Most existing methods for graph estimation are based on single-attribute models where one associates a scalar random variable with each node. In multi-attribute graphical models, each node represents a random vector. In this paper we provide a unified theoretical analysis of multi-attribute graph learning using a penalized log-likelihood objective function. We consider both convex (sparse-group lasso) and sparse-group non-convex (log-sum and smoothly clipped absolute deviation (SCAD) penalties) penalty/regularization functions. An alternating direction method of multipliers (ADMM) approach coupled with local linear approximation to non-convex penalties is presented for optimization of the objective function. For non-convex penalties, theoretical analysis establishing local consistency in support recovery, local convexity and precision matrix estimation in high-dimensional settings is provided under two sets of sufficient conditions: with and without some irrepresentability conditions. We illustrate our approaches using both synthetic and real-data numerical examples. In the synthetic data examples the sparse-group log-sum penalized objective function significantly outperformed the lasso penalized as well as SCAD penalized objective functions with F1 -score and Hamming distance as performance metrics. 

   more » « less
2. Provable Convex Co-clustering of Tensors

   Chi, Eric C; Gaines, Brian J; Sun, Will Wei; Zhou, Hua; Yang, Jian (October 2020, Journal of machine learning research)

   null (Ed.)

   Cluster analysis is a fundamental tool for pattern discovery of complex heterogeneous data. Prevalent clustering methods mainly focus on vector or matrix-variate data and are not applicable to general-order tensors, which arise frequently in modern scientific and business applications. Moreover, there is a gap between statistical guarantees and computational efficiency for existing tensor clustering solutions due to the nature of their non-convex formulations. In this work, we bridge this gap by developing a provable convex formulation of tensor co-clustering. Our convex co-clustering (CoCo) estimator enjoys stability guarantees and its computational and storage costs are polynomial in the size of the data. We further establish a non-asymptotic error bound for the CoCo estimator, which reveals a surprising ``blessing of dimensionality" phenomenon that does not exist in vector or matrix-variate cluster analysis. Our theoretical findings are supported by extensive simulated studies. Finally, we apply the CoCo estimator to the cluster analysis of advertisement click tensor data from a major online company. Our clustering results provide meaningful business insights to improve advertising effectiveness. 

   more » « less
3. Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization

   Jambulapati, Arun; Sidford, Aaron; Tian, Kevin (June 2024, https://doi.org/10.48550/arXiv.2406.07373)

   This paper presents a new parallel algorithm for minimizing Lipschitz convex functions using a stochastic subgradient oracle. The proposed method matches the state-of-the-art in terms of total queries and query depth (parallel rounds of queries) from [CJJLLST23], while improving the computational depth by a polynomial factor for sufficiently small accuracy. When combined with previous methods, this result closes the gap between the best-known query depth and computational depth in parallel stochastic convex optimization. The approach builds on the ball acceleration framework from [CJJJLST20, ACJJS21], which reduces optimization to minimizing a Gaussian-convolved regularization of the function within Euclidean balls. By developing new stability properties of the Hessian of this induced function, the authors reduce ball-constrained problems to stochastic unconstrained quadratic minimization. Although concentration results for the asymmetric Hessian approximations are lacking, the authors design an efficient parallel method for solving these quadratics. Interestingly, the algorithm can be further enhanced using fast matrix multiplication, yielding nearly-linear work if the matrix multiplication exponent is 2. 

   more » « less
4. Multivariate Distributionally Robust Convex Regression under Absolute Error Loss

   Blanchet, Jose and (October 2019, Advances in Neural Information Processing Systems 32 (NIPS 2019))

   This paper proposes a novel non-parametric multidimensional convex regression estimator which is designed to be robust to adversarial perturbations in the empirical measure. We minimize over convex functions the maximum (over Wasserstein perturbations of the empirical measure) of the absolute regression errors. The inner maximization is solved in closed form resulting in a regularization penalty involves the norm of the gradient. We show consistency of our estimator and a rate of convergence of order O˜(n−1/d), matching the bounds of alternative estimators based on square-loss minimization. Contrary to all of the existing results, our convergence rates hold without imposing compactness on the underlying domain and with no a priori bounds on the underlying convex function or its gradient norm. 

   more » « less
5. Shortest Paths in Graphs of Convex Sets

   Tobia Marcucci, Jack Umenberger (December 2021, ArXivorg)

   Given a graph, the shortest-path problem requires finding a sequence of edges with minimum cumulative length that connects a source vertex to a target vertex. We consider a generalization of this classical problem in which the position of each vertex in the graph is a continuous decision variable, constrained to lie in a corresponding convex set. The length of an edge is then defined as a convex function of the positions of the vertices it connects. Problems of this form arise naturally in motion planning of autonomous vehicles, robot navigation, and even optimal control of hybrid dynamical systems. The price for such a wide applicability is the complexity of this problem, which is easily seen to be NP-hard. Our main contribution is a strong mixed-integer convex formulation based on perspective functions. This formulation has a very tight convex relaxation and makes it possible to efficiently find globally-optimal paths in large graphs and in high-dimensional spaces. 

   more » « less