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. A unifying convex analysis and switching system approach to consensus with undirected communication graphs

   Goebel, R.; Sanfelice, R. (January 2018, 2018 IEEE Conference on Decision and Control)

   Switching between finitely many continuous-time autonomous steepest descent dynamics for convex functions is considered. Convergence of complete solutions to common minimizers of the convex functions, if such minimizers exist, is shown. The convex functions need not be smooth and may be subject to constraints. Since the common minimizers may represent consensus in a multi-agent system modeled by an undirected communication graph, several known results about asymptotic consensus are deduced as special cases. Extensions to time-varying convex functions and to dynamics given by set-valued mappings more general than subdifferentials of convex functions are included. 

   more » « less
3. A unified approach for a 1D generalized total variation problem

   https://doi.org/10.1007/s10107-021-01633-2  

   Lu, Cheng; Hochbaum, Dorit S. (July 2021, Mathematical Programming)

   null (Ed.)

   Abstract We study a 1-dimensional discrete signal denoising problem that consists of minimizing a sum of separable convex fidelity terms and convex regularization terms, the latter penalize the differences of adjacent signal values. This problem generalizes the total variation regularization problem. We provide here a unified approach to solve the problem for general convex fidelity and regularization functions that is based on the Karush–Kuhn–Tucker optimality conditions. This approach is shown here to lead to a fast algorithm for the problem with general convex fidelity and regularization functions, and a faster algorithm if, in addition, the fidelity functions are differentiable and the regularization functions are strictly convex. Both algorithms achieve the best theoretical worst case complexity over existing algorithms for the classes of objective functions studied here. Also in practice, our C++ implementation of the method is considerably faster than popular C++ nonlinear optimization solvers for the problem. 

   more » « less
4. Stability of SGD: Tightness analysis and improved bounds

   Zhang, Yikai; Zhang, Wenjia; Bald, Sammy; Pingali, Vamsi; Chen, Chao; Goswami, Mayank (August 2022, Uncertainty in artificial intelligence)

   Stochastic Gradient Descent (SGD) based methods have been widely used for training large-scale machine learning models that also generalize well in practice. Several explanations have been offered for this generalization performance, a prominent one being algorithmic stability [18]. However, there are no known examples of smooth loss functions for which the analysis can be shown to be tight. Furthermore, apart from the properties of the loss function, data distribution has also been shown to be an important factor in generalization performance. This raises the question: is the stability analysis of [18] tight for smooth functions, and if not, for what kind of loss functions and data distributions can the stability analysis be improved? In this paper we first settle open questions regarding tightness of bounds in the data-independent setting: we show that for general datasets, the existing analysis for convex and strongly-convex loss functions is tight, but it can be improved for non-convex loss functions. Next, we give a novel and improved data-dependent bounds: we show stability upper bounds for a large class of convex regularized loss functions, with negligible regularization parameters, and improve existing data-dependent bounds in the non-convex setting. We hope that our results will initiate further efforts to better understand the data-dependent setting under non-convex loss functions, leading to an improved understanding of the generalization abilities of deep networks. 

   more » « less
5. Byzantine-Resilient SGD in High Dimensions on Heterogeneous Data

   https://doi.org/10.1109/ISIT45174.2021.9518248  

   Data, Deepesh; Diggavi, Suhas (July 2021, IEEE International Symposium on Information Theory (ISIT))

   We study distributed stochastic gradient descent (SGD) in the master-worker architecture under Byzantine attacks. We consider the heterogeneous data model, where different workers may have different local datasets, and we do not make any probabilistic assumptions on data generation. At the core of our algorithm, we use the polynomial-time outlier-filtering procedure for robust mean estimation proposed by Steinhardt et al. (ITCS 2018) to filter-out corrupt gradients. In order to be able to apply their filtering procedure in our heterogeneous data setting where workers compute stochastic gradients, we derive a new matrix concentration result, which may be of independent interest. We provide convergence analyses for smooth strongly-convex and non-convex objectives and show that our convergence rates match that of vanilla SGD in the Byzantine-free setting. In order to bound the heterogeneity, we assume that the gradients at different workers have bounded deviation from each other, and we also provide concrete bounds on this deviation in the statistical heterogeneous data model. 

   more » « less