Invex Programs: First Order Algorithms and Their Convergence
Invex programs are a special kind of non-convex problems which attain global minima at every stationary point. While classical first-order gradient descent methods can solve them, they converge very slowly. In this paper, we propose new first-order algorithms to solve the general class of invex problems. We identify sufficient conditions for convergence of our algorithms and provide rates of convergence. Furthermore, we go beyond unconstrained problems and provide a novel projected gradient method for constrained invex programs with convergence rate guarantees. We compare and contrast our results with existing first-order algorithms for a variety of unconstrained and constrained invex problems. To the best of our knowledge, our proposed algorithm is the first algorithm to solve constrained invex programs.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Input Invex Neural Network
Connected decision boundaries are useful in several tasks like image segmentation, clustering, alpha-shape or defining a region in nD-space. However, the machine learning literature lacks methods for generating connected…
Image ClassificationImage SegmentationSemantic SegmentationLEARN: An Invex Loss for Outlier Oblivious Robust Online Optimization
We study a robust online convex optimization framework, where an adversary can introduce outliers by corrupting loss functions in an arbitrary number of rounds k, unknown to the learner. Our focus is on a novel setting a…
Sparse Mixed Linear Regression with Guarantees: Taming an Intractable Problem with Invex Relaxation
In this paper, we study the problem of sparse mixed linear regression on an unlabeled dataset that is generated from linear measurements from two different regression parameter vectors. Since the data is unlabeled, our t…
regressionFair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem
In this paper, we study the problem of fair sparse regression on a biased dataset where bias depends upon a hidden binary attribute. The presence of a hidden attribute adds an extra layer of complexity to the problem by …
AttributeClusteringFairnessregressionOutlier-robust Estimation of a Sparse Linear Model Using Invexity
In this paper, we study problem of estimating a sparse regression vector with correct support in the presence of outlier samples. The inconsistency of lasso-type methods is well known in this scenario. We propose a combi…
regression