Skip to main content

Accelerated Bregman proximal gradient (ABPG) methods

Project description

# Accelerated Bregman Proximal Gradient Methods

Accelerated first-order algorithms for solving relatively-smooth convex optimization problems of the form

minimize { f(x) + P(x) | x in C }

with a reference function h(x), where

  • h(x) is convex and essentially smooth on C
  • f(x) is convex and differentiable, and L-smooth relative to h(x), that is, f(x)-L*h(x) is convex
  • P(x) is convex and closed (lower semi-continuous)
  • C is a closed convex set

### Implemented algorithms in [HRX2018](https://arxiv.org/abs/1808.03045)

  • BPG_LS (Bregman proximal gradient) method with line search
  • ABPG (Accelerated BPG) method
  • ABPG-expo (ABPG with exponent adaption)
  • ABPG-gain (ABPG with gain adaption)
  • ABDA (Accelerated Bregman dual averaging) method

## Installation

Clone or fork from GitHub. Or install from PyPI:

pip install accbpg

## Usage

import accbpg

# generate a random instance of D-optimal design problem f, h, L, x0 = accbpg.D_opt_design(80, 200)

# solve the problem instance using BPG with line search x1, F1, G1 = accbpg.BPG_LS(f, h, L, x0, maxitrs=1000, verskip=100)

# solve it again using ABPG_gain with gamma=2 x2, F2, G2, D2 = accbpg.ABPG_gain(f, h, L, 2, x0, maxitrs=1000, verbskip=100)

compare the two methods by visualization

import matplotlib.pyplot as plt Fmin = min(F1.min(), F2.min()) plt.semilogy(range(len(F1)), F1-Fmin, range(len(F2)), F2-Fmin)

## Examples in [HRX2018](https://arxiv.org/abs/1808.03045)

D-optimal experiment design

import accbpg.ex_D_opt

Nonnegative regression with KL-divergence

import accbpg.ex_KL_regr

Poisson linear inverse problems

import accbpg.ex_PoissonL1 import accbpg.ex_PoissonL2

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

accbpg-0.1.tar.gz (11.2 kB view hashes)

Uploaded source

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Huawei Huawei PSF Sponsor Microsoft Microsoft PSF Sponsor NVIDIA NVIDIA PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page