Publications (60)
Generalized Inverse Classification
Michael T. Lash, Qihang Lin, W. Nick Street +2
Inverse classification is the process of perturbing an instance in a meaningful way such that it is more likely to conform to a specific class. Historical methods that address such…
Lower Complexity Bounds of First-order Methods for Affinely Constrained Composite Non-convex Problems
Wei Liu, Qihang Lin, Yangyang Xu
Many recent studies on first-order methods (FOMs) focus on \emph{composite non-convex non-smooth} optimization with linear and/or nonlinear function constraints. Upper (or worst-ca…
DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimization
Lin Xiao, Adams Wei Yu, Qihang Lin +1
Machine learning with big data often involves large optimization models. For distributed optimization over a cluster of machines, frequent communication and synchronization of all…
Self-guided Approximate Linear Programs
Parshan Pakiman, Selvaprabu Nadarajah, Negar Soheili +1
Approximate linear programs (ALPs) are well-known models based on value function approximations (VFAs) to obtain policies and lower bounds on the optimal policy cost of discounted-…
Learning to Rank with Top- Fairness
Boyang Zhang, Quanqi Hu, Mingxuan Sun +2
Fairness in ranking models is crucial, as disparities in exposure can disproportionately affect protected groups. Most fairness-aware ranking systems focus on ensuring comparable a…
Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
Jason D. Lee, Qihang Lin, Tengyu Ma +1
We study distributed optimization algorithms for minimizing the average of convex functions. The applications include empirical risk minimization problems in statistical machine le…
Stochastic Primal-Dual Algorithms with Faster Convergence than for Problems without Bilinear Structure
Yan Yan, Yi Xu, Qihang Lin +2
Previous studies on stochastic primal-dual algorithms for solving min-max problems with faster convergence heavily rely on the bilinear structure of the problem, which restricts th…
Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints
Ming Yang, Gang Li, Quanqi Hu +2
Constrained optimization with multiple functional inequality constraints has significant applications in machine learning. This paper examines a crucial subset of such problems whe…
Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization
Yankun Huang, Qihang Lin
We consider a non-convex constrained optimization problem, where the objective function is weakly convex and the constraint function is either convex or weakly convex. To solve thi…
Optimal Stochastic Strongly Convex Optimization with a Logarithmic Number of Projections
Jianhui Chen, Tianbao Yang, Qihang Lin +2
We consider stochastic strongly convex optimization with a complex inequality constraint. This complex inequality constraint may lead to computationally expensive projections in al…
A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates
Tianbao Yang, Qihang Lin, Lijun Zhang
This paper focuses on convex constrained optimization problems, where the solution is subject to a convex inequality constraint. In particular, we aim at challenging problems for w…
Multi-Output Distributional Fairness via Post-Processing
Gang Li, Qihang Lin, Ayush Ghosh +1
The post-processing approaches are becoming prominent techniques to enhance machine learning models' fairness because of their intuitiveness, low computational cost, and excellent…
Distributionally Robust Optimization with Confidence Bands for Probability Density Functions
Xi Chen, Qihang Lin, Guanglin Xu
Distributionally robust optimization (DRO) has been introduced for solving stochastic programs where the distribution of the random parameters is unknown and must be estimated by s…
A Unified Analysis of Stochastic Momentum Methods for Deep Learning
Yan Yan, Tianbao Yang, Zhe Li +2
Stochastic momentum methods have been widely adopted in training deep neural networks. However, their theoretical analysis of convergence of the training objective and the generali…
A Retention-Centric Framework for Continual Learning with Guaranteed Model Developmental Safety
Gang Li, Wendi Yu, Yao Yao +4
In real-world applications, learning-enabled systems often undergo iterative model development to address challenging or emerging tasks, which involve collecting new data, training…
Stochastic subGradient Methods with Linear Convergence for Polyhedral Convex Optimization
Tianbao Yang, Qihang Lin
In this paper, we show that simple {Stochastic} subGradient Decent methods with multiple Restarting, named {\bf RSGD}, can achieve a \textit{linear convergence rate} for a class of…
Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergence
Yi Xu, Qi Qi, Qihang Lin +2
Difference of convex (DC) functions cover a broad family of non-convex and possibly non-smooth and non-differentiable functions, and have wide applications in machine learning and…
Fast Sparse Least-Squares Regression with Non-Asymptotic Guarantees
Tianbao Yang, Lijun Zhang, Qihang Lin +1
In this paper, we study a fast approximation method for {\it large-scale high-dimensional} sparse least-squares regression problem by exploiting the Johnson-Lindenstrauss (JL) tran…
Smoothing proximal gradient method for general structured sparse regression
Xi Chen, Qihang Lin, Seyoung Kim +2
We study the problem of estimating high-dimensional regression models regularized by a structured sparsity-inducing penalty that encodes prior structural information on either the…
Inexact Moreau Envelope Lagrangian Method for Non-Convex Constrained Optimization under Local Error Bound Conditions on Constraint Functions
Yankun Huang, Qihang Lin, Yangyang Xu
In this paper, we investigate how structural properties of the constraint system impact the oracle complexity of smooth non-convex optimization problems with convex inequality cons…
On Data Preconditioning for Regularized Loss Minimization
Tianbao Yang, Rong Jin, Shenghuo Zhu +1
In this work, we study data preconditioning, a well-known and long-existing technique, for boosting the convergence of first-order methods for regularized loss minimization. It is…
Enforcing Fair Predicted Scores on Intervals of Percentiles by Difference-of-Convex Constraints
Yutian He, Yankun Huang, Yao Yao +1
Fairness in machine learning has become a critical concern. Existing approaches often focus on achieving full fairness across all score ranges generated by predictive models, ensur…
RSG: Beating Subgradient Method without Smoothness and Strong Convexity
Tianbao Yang, Qihang Lin
In this paper, we study the efficiency of a {\bf R}estarted {\bf S}ub{\bf G}radient (RSG) method that periodically restarts the standard subgradient method (SG). We show that, when…
Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems
Yiyang Shen, Yutian He, Weiran Wang +1
We study a class of bilevel optimization problems in which both the upper- and lower-level problems have minimax structures. This setting captures a broad range of emerging applica…
First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems
Mingrui Liu, Hassan Rafique, Qihang Lin +1
In this paper, we consider first-order convergence theory and algorithms for solving a class of non-convex non-concave min-max saddle-point problems, whose objective function is we…
Statistical Decision Making for Optimal Budget Allocation in Crowd Labeling
Xi Chen, Qihang Lin, Dengyong Zhou
In crowd labeling, a large amount of unlabeled data instances are outsourced to a crowd of workers. Workers will be paid for each label they provide, but the labeling requester usu…
Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization
Xingyu Chen, Bokun Wang, Ming Yang +2
Finite-sum Coupled Compositional Optimization (FCCO), characterized by its coupled compositional objective structure, emerges as an important optimization paradigm for addressing a…
Doubly Stochastic Primal-Dual Coordinate Method for Bilinear Saddle-Point Problem
Adams Wei Yu, Qihang Lin, Tianbao Yang
We propose a doubly stochastic primal-dual coordinate optimization algorithm for empirical risk minimization, which can be formulated as a bilinear saddle-point problem. In each it…
Block-Normalized Gradient Method: An Empirical Study for Training Deep Neural Network
Adams Wei Yu, Lei Huang, Qihang Lin +2
In this paper, we propose a generic and simple strategy for utilizing stochastic gradient information in optimization. The technique essentially contains two consecutive steps in e…
Homotopy Smoothing for Non-Smooth Problems with Lower Complexity than
Yi Xu, Yan Yan, Qihang Lin +1
In this paper, we develop a novel {\bf ho}moto{\bf p}y {\bf s}moothing (HOPS) algorithm for solving a family of non-smooth problems that is composed of a non-smooth term with an ex…
Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization
Tianbao Yang, Qihang Lin, Zhe Li
Recently, {\it stochastic momentum} methods have been widely adopted in training deep neural networks. However, their convergence analysis is still underexplored at the moment, in…
Prophit: Causal inverse classification for multiple continuously valued treatment policies
Michael T. Lash, Qihang Lin, W. Nick Street
Inverse classification uses an induced classifier as a queryable oracle to guide test instances towards a preferred posterior class label. The result produced from the process is a…
A Data Efficient and Feasible Level Set Method for Stochastic Convex Optimization with Expectation Constraints
Qihang Lin, Selvaprabu Nadarajah, Negar Soheili +1
Stochastic convex optimization problems with expectation constraints (SOECs) are encountered in statistics and machine learning, business, and engineering. In data-rich environment…
A Note on Complexity for Two Classes of Structured Non-Smooth Non-Convex Compositional Optimization
Yao Yao, Qihang Lin, Tianbao Yang
This note studies numerical methods for solving compositional optimization problems, where the inner function is smooth, and the outer function is Lipschitz continuous, non-smooth,…
ProtoX: Explaining a Reinforcement Learning Agent via Prototyping
Ronilo J. Ragodos, Tong Wang, Qihang Lin +1
While deep reinforcement learning has proven to be successful in solving control tasks, the "black-box" nature of an agent has received increasing concerns. We propose a prototype-…
Large-scale Optimization of Partial AUC in a Range of False Positive Rates
Yao Yao, Qihang Lin, Tianbao Yang
The area under the ROC curve (AUC) is one of the most widely used performance measures for classification models in machine learning. However, it summarizes the true positive rates…
Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraints
Runchao Ma, Qihang Lin, Tianbao Yang
Optimization models with non-convex constraints arise in many tasks in machine learning, e.g., learning with fairness constraints or Neyman-Pearson classification with non-convex l…
Stochastic Methods for AUC Optimization subject to AUC-based Fairness Constraints
Yao Yao, Qihang Lin, Tianbao Yang
As machine learning being used increasingly in making high-stakes decisions, an arising challenge is to avoid unfair AI systems that lead to discriminatory decisions for protected…
Inexact accelerated proximal gradient method with line search and reduced complexity for affine-constrained and bilinear saddle-point structured convex problems
Qihang Lin, Yangyang Xu
The goal of this paper is to reduce the total complexity of gradient-based methods for two classes of problems: affine-constrained composite convex optimization and bilinear saddle…
An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
Qihang Lin, Zhaosong Lu, Lin Xiao
We consider the problem of minimizing the sum of two convex functions: one is smooth and given by a gradient oracle, and the other is separable over blocks of coordinates and has a…
Comparison-Based Algorithms for One-Dimensional Stochastic Convex Optimization
Xi Chen, Qihang Lin, Zizhuo Wang
Stochastic optimization finds a wide range of applications in operations research and management science. However, existing stochastic optimization techniques usually require the i…
FedPAE: Peer-Adaptive Ensemble Learning for Asynchronous and Model-Heterogeneous Federated Learning
Brianna Mueller, W. Nick Street, Stephen Baek +3
Federated learning (FL) enables multiple clients with distributed data sources to collaboratively train a shared model without compromising data privacy. However, existing FL parad…
Smoothing Proximal Gradient Method for General Structured Sparse Learning
Xi Chen, Qihang Lin, Seyoung Kim +2
We study the problem of learning high dimensional regression models regularized by a structured-sparsity-inducing penalty that encodes prior structural information on either input…
First-order Methods for Affinely Constrained Composite Non-convex Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods
Wei Liu, Qihang Lin, Yangyang Xu
Many recent studies on first-order methods (FOMs) focus on \emph{composite non-convex non-smooth} optimization with linear and/or nonlinear function constraints. Upper (or worst-ca…
Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization
Yan Yan, Yi Xu, Qihang Lin +2
Epoch gradient descent method (a.k.a. Epoch-GD) proposed by Hazan and Kale (2011) was deemed a breakthrough for stochastic strongly convex minimization, which achieves the optimal…
Accelerate Stochastic Subgradient Method by Leveraging Local Growth Condition
Yi Xu, Qihang Lin, Tianbao Yang
In this paper, a new theory is developed for first-order stochastic convex optimization, showing that the global convergence rate is sufficiently quantified by a local growth rate…
Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning
Hassan Rafique, Mingrui Liu, Qihang Lin +1
Min-max problems have broad applications in machine learning, including learning with non-decomposable loss and learning with robustness to data distribution. Convex-concave min-ma…
Graph-Structured Multi-task Regression and an Efficient Optimization Method for General Fused Lasso
Xi Chen, Seyoung Kim, Qihang Lin +2
We consider the problem of learning a structured multi-task regression, where the output consists of multiple responses that are related by a graph and the correlated response vari…
On Degrees of Freedom of Projection Estimators with Applications to Multivariate Nonparametric Regression
Xi Chen, Qihang Lin, Bodhisattva Sen
In this paper, we consider the nonparametric regression problem with multivariate predictors. We provide a characterization of the degrees of freedom and divergence for estimators…
A Near-optimal Method for Linearly Constrained Composite Non-convex Non-smooth Problems
Wei Liu, Qihang Lin, Yangyang Xu
We study first-order methods (FOMs) for solving \emph{composite nonconvex nonsmooth} optimization with linear constraints. Recently, the lower complexity bounds of FOMs on finding…
A budget-constrained inverse classification framework for smooth classifiers
Michael T. Lash, Qihang Lin, W. Nick Street +1
Inverse classification is the process of manipulating an instance such that it is more likely to conform to a specific class. Past methods that address such a problem have shortcom…
Provable Optimization for Adversarial Fair Self-supervised Contrastive Learning
Qi Qi, Quanqi Hu, Qihang Lin +1
This paper studies learning fair encoders in a self-supervised learning (SSL) setting, in which all data are unlabeled and only a small portion of them are annotated with sensitive…
Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization
Qihang Lin, Runchao Ma, Yangyang Xu
In this paper, an inexact proximal-point penalty method is studied for constrained optimization problems, where the objective function is non-convex, and the constraint functions c…
Hybrid Predictive Model: When an Interpretable Model Collaborates with a Black-box Model
Tong Wang, Qihang Lin
Interpretable machine learning has become a strong competitor for traditional black-box models. However, the possible loss of the predictive performance for gaining interpretabilit…
Deterministic and Stochastic Accelerated Gradient Method for Convex Semi-Infinite Optimization
Yao Yao, Qihang Lin, Tianbao Yang
This paper explores numerical methods for solving a convex differentiable semi-infinite program. We introduce a primal-dual gradient method which performs three updates iteratively…
An Adaptive Parameter-free and Projection-free Restarting Level Set Method for Constrained Convex Optimization Under the Error Bound Condition
Qihang Lin, Negar Soheili, Runchao Ma +1
Recent efforts to accelerate first-order methods have focused on convex optimization problems that satisfy a geometric property known as error-bound condition, which covers a broad…
Model-Agnostic Linear Competitors -- When Interpretable Models Compete and Collaborate with Black-Box Models
Hassan Rafique, Tong Wang, Qihang Lin
Driven by an increasing need for model interpretability, interpretable models have become strong competitors for black-box models in many real applications. In this paper, we propo…
Bayesian Decision Process for Cost-Efficient Dynamic Ranking via Crowdsourcing
Xi Chen, Kevin Jiao, Qihang Lin
Rank aggregation based on pairwise comparisons over a set of items has a wide range of applications. Although considerable research has been devoted to the development of rank aggr…
Federated Learning on Adaptively Weighted Nodes by Bilevel Optimization
Yankun Huang, Qihang Lin, Nick Street +1
We propose a federated learning method with weighted nodes in which the weights can be modified to optimize the model's performance on a separate validation set. The problem is for…
A Smoothing Stochastic Gradient Method for Composite Optimization
Qihang Lin, Xi Chen, Javier Pena
We consider the unconstrained optimization problem whose objective function is composed of a smooth and a non-smooth conponents where the smooth component is the expectation a rand…