NDLI: A Divide-and-Conquer Method for Scalable Robust Multitask Learning

Content Provider	IEEE Xplore Digital Library
Author	Yan Pan Rongkai Xia Jian Yin Ning Liu
Copyright Year	2012
Abstract	Multitask learning (MTL) aims at improving the generalization performance of multiple tasks by exploiting the shared factors among them. An important line of research in the MTL is the robust MTL (RMTL) methods, which use trace-norm regularization to capture task relatedness via a low-rank structure. The existing algorithms for the RMTL optimization problems rely on the accelerated proximal gradient (APG) scheme that needs repeated full singular value decomposition (SVD) operations. However, the time complexity of a full SVD is O(min(md², m²d)) for an RMTL problem with m tasks and d features, which becomes unaffordable in real-world MTL applications that often have a large number of tasks and high-dimensional features. In this paper, we propose a scalable solution for large-scale RMTL, with either the least squares loss or the squared hinge loss, by a divide-and-conquer method. The proposed method divides the original RMTL problem into several size-reduced subproblems, solves these cheaper subproblems in parallel by any base algorithm (e.g., APG) for RMTL, and then combines the results to obtain the final solution. Our theoretical analysis indicates that, with high probability, the recovery errors of the proposed divide-and-conquer algorithm are bounded by those of the base algorithm. Furthermore, in order to solve the subproblems with the least squares loss or the squared hinge loss, we propose two efficient base algorithms based on the linearized alternating direction method, respectively. Experimental results demonstrate that, with little loss of accuracy, our method is substantially faster than the state-of-the-art APG algorithms for RMTL.
Page Count	13
File Size	2258296
Starting Page	3163
Ending Page	3175
File Format	PDF
ISSN	2162237X
Volume Number	26
Issue Number	12
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-01-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Optimization Fasteners Partitioning algorithms Matrix decomposition Least squares approximations Algorithm design and analysis multitask learning (MTL). Divide-and-conquer method linearized alternating direction method (LADM) low-rank matrices multitask learning (MTL)
Content Type	Text
Resource Type	Article
Subject	Artificial Intelligence Computer Networks and Communications Computer Science Applications Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Direction-of-Arrival Tracking via Low-Rank Plus Sparse Matrix Decomposition

Alternating Least-Squares for Low-Rank Matrix Reconstruction

Successive Projection Method for Well-Conditioned Matrix Approximation Problems

Frequency Estimation Based on Hankel Matrices and the Alternating Direction Method of Multipliers

A Gauss-Newton-like optimization algorithm for weighted nonlinear least-squares problems

Heteroscedastic Low-Rank Matrix Approximation by the Wiberg Algorithm

Grassmann algorithms for low rank approximation of matrices with missing values

An efficient method for solving a matrix least squares problem over a matrix inequality constraint

Efficient Alternating Least Squares Algorithms for Low Multilinear Rank Approximation of Tensors

A Divide-and-Conquer Method for Scalable Robust Multitask Learning

Similar Documents

Direction-of-Arrival Tracking via Low-Rank Plus Sparse Matrix Decomposition

Alternating Least-Squares for Low-Rank Matrix Reconstruction

Successive Projection Method for Well-Conditioned Matrix Approximation Problems

Frequency Estimation Based on Hankel Matrices and the Alternating Direction Method of Multipliers

A Gauss-Newton-like optimization algorithm for weighted nonlinear least-squares problems

Heteroscedastic Low-Rank Matrix Approximation by the Wiberg Algorithm

Grassmann algorithms for low rank approximation of matrices with missing values

An efficient method for solving a matrix least squares problem over a matrix inequality constraint

Efficient Alternating Least Squares Algorithms for Low Multilinear Rank Approximation of Tensors

A Divide-and-Conquer Method for Scalable Robust Multitask Learning