Runtime guarantees for regression problems

DOI10.1145/2422436.2422469MaRDI QIDQ2986877zbMATH OpenOpenAlexFDO

Authors Hui Han Chin, Aleksander Mądry, Richard Peng, Gary L. Miller

Publication date 16 May 2017

Published in Proceedings of the 4th conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.1358

zbMATH Keywords

image processingoptimizationregression

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Ridge regression; shrinkage estimators (Lasso) (62J07) Analysis of algorithms and problem complexity (68Q25) Computing methodologies for image processing (68U10)

Abstract: We study theoretical runtime guarantees for a class of optimization problems that occur in a wide variety of inference problems. these problems are motivated by the lasso framework and have applications in machine learning and computer vision. Our work shows a close connection between these problems and core questions in algorithmic graph theory. While this connection demonstrates the difficulties of obtaining runtime guarantees, it also suggests an approach of using techniques originally developed for graph algorithms. We then show that most of these problems can be formulated as a grouped least squares problem, and give efficient algorithms for this formulation. Our algorithms rely on routines for solving quadratic minimization problems, which in turn are equivalent to solving linear systems. Finally we present some experimental results on applying our approximation algorithm to image processing problems.

Recommendations

• scientific article; zbMATH DE number 6253925
• Computational and statistical tradeoffs via convex relaxation
• Fast and scalable Lasso via stochastic Frank-Wolfe methods with a convergence guarantee
• Pathwise coordinate optimization
• Plug-and-play dual-tree algorithm runtime analysis

Cites work

• A model of interactive teaching
• A theory of goal-oriented communication
• A theory of the learnable
• Algorithmic Learning Theory
• Derandomizing polynomial identity tests means proving circuit lower bounds
• scientific article; zbMATH DE number 3154781 (Why is no real title available?)
• scientific article; zbMATH DE number 67625 (Why is no real title available?)
• scientific article; zbMATH DE number 67631 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Learning from different teachers
• Measuring teachability using variants of the teaching dimension
• Models of cooperative teaching and learning
• Occam's razor
• On specifying Boolean functions by labelled examples
• On the complexity of teaching
• On the limits of efficient teachability
• On the power of inductive inference from good examples
• Pseudorandom generators for space-bounded computation
• Recent Developments in Algorithmic Teaching
• Teachability in computational learning
• Teaching a smarter learner.
• Teaching Randomized Learners

Cited in

(7)

• A Laplacian approach to _1-norm minimization
• Unit Capacity Maxflow in Almost $m^{4/3}$ Time
• Hardness results for structured linear systems
• Reviewing extensions and solution methods of the planar Weber single facility location problem
• Fast algorithms for _p-regression
• Almost-linear-time weighted _p-norm solvers in slightly dense graphs via sparsification
• Acceleration meets inverse maintenance: faster _-regression

Describes a project that uses

Uses Software

• LASSO

This page was built for publication: Runtime guarantees for regression problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986877)