SYNTOLOGY HomeExplorerAtlasCodeMethodologyAboutDevelopersFeedPricing
Paper · 1808.03045 · 2018

Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization

arXiv · PDF · Open in the Atlas

Code that ran

9 of 11 samples (functions and classes) lifted from this paper's linked repositories executed on a synthesized input in Syntology's jail (0 of them constructed an object rather than computing a result; 1 honoured the contract we drafted, 0 violated it and 6 have no contract verdict; 2 failures of our instrument; 2 no recorded run), measured 2026-11-21; repository links from the Papers with Code archive attributed under CC BY-SA, no affiliation; bodies inline only under a permissive licence as GitHub detects it. Not a reproduction of the paper's results.

"Ran" means the function executed on a synthesized input and returned a value. It is not a reproduction of the paper's results. This record, dated, as JSON: /api/ran/1808.03045.json · badge: /api/ran/1808.03045.svg

Each repository's role is a label: a classifier's output recorded on the link, or, where no role is recorded, what the Papers with Code archive marked. The line under it names its basis. Neither says who wrote the code.

RepositoryRoleRan
Microsoft/accbpg canonical (classifier label)
classifier basis: census
6 ran · 2 no recorded run
linxiaolx/accbpg reimplementation (classifier label)
classifier basis: classifier_2025
3 ran · 0 no recorded run
FunctionStatusWhere it lives
ABPG Ran
ran; the contract check could not run (RAISES, DEP_MISSING or TIMEOUT)
linxiaolx/accbpg/accbpg/algorithms.py
code served (permissive licence) · get_code("9a55fc3fd11346ec")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1) and returned tuple. The image it ran in was not recorded. If your copy returns the same type on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import numpy as np

class MockSmoothFunction:
    """Mock smooth function f with gradient method"""
    def __call__(self, x):
        # Simple quadratic: f(x) = 0.5 * ||x||^2
        return 0.5 * np.sum(x ** 2)
    
    def gradient(self, x):
        # Gradient of 0.5 * ||x||^2 is x
        return x.copy()

class MockBregmanDivergence:
    """Mock Bregman divergence h with required methods"""
    def __init__(self, dim=4):
        self.dim = dim
    
    def extra_Psi(self, x):
        # Psi(x) = 0 for simplicity
        return 0.0
    
    def divergence(self, x, y):
        # Bregman divergence D_h(x, y) = 0.5 * ||x - y||^2
        diff = x - y
        return 0.5 * np.sum(diff ** 2)
    
    def div_prox_map(self, z, g, step_size):
        # Proximal map: z_new = z - step_size * g
        # (simplified Bregman proximal operator)
        return z - step_size * g

# Set random seed for reproducibility
np.random.seed(0)

# Create small test problem
dim = 4
x0 = np.random.randn(dim)

# Create function and Bregman divergence objects
f = MockSmoothFunction()
h = MockBregmanDivergence(dim=dim)

# Parameters
L = 1.0  # Smoothness constant
gamma = 1.5  # Triangle scaling exponent
maxitrs = 10  # Small number for testing

ARGS = {
    'f': f,
    'h': h,
    'L': L,
    'x0': x0,
    'gamma': gamma,
    'maxitrs': maxitrs,
    'epsilon': 1e-14,
    'theta_eq': False,
    'restart': False,
    'restart_rule': 'g',
    'verbose': True,
    'verbskip': 1,
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1
Imports
numpy — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type tuple — a tuple output has no array shape of its own; none is stated
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
BPG Ran
ran; the contract check could not run (RAISES, DEP_MISSING or TIMEOUT)
linxiaolx/accbpg/accbpg/algorithms.py
code served (permissive licence) · get_code("70d648a19e9e5f2a")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1) and returned tuple. The image it ran in was not recorded. If your copy returns the same type on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import numpy as np

class FunctionWithGradient:
    """Implements a simple quadratic function with gradient computation."""
    def __init__(self):
        self.A = np.array([[2.0, 0.5], [0.5, 1.0]])
        self.b = np.array([1.0, -1.0])
    
    def func_grad(self, x):
        """Returns (f(x), grad_f(x)) for f(x) = 0.5*x^T*A*x - b^T*x"""
        fx = 0.5 * np.dot(x, np.dot(self.A, x)) - np.dot(self.b, x)
        grad = np.dot(self.A, x) - self.b
        return fx, grad
    
    def __call__(self, x):
        """Returns f(x)"""
        return 0.5 * np.dot(x, np.dot(self.A, x)) - np.dot(self.b, x)


class BregmanDivergenceHandler:
    """Implements Bregman divergence operations with Euclidean distance and L2 regularization."""
    def __init__(self):
        self.lambda_reg = 0.1
    
    def extra_Psi(self, x):
        """Returns Psi(x) = 0.5*lambda*||x||^2 (L2 regularization)"""
        return 0.5 * self.lambda_reg * np.dot(x, x)
    
    def divergence(self, x1, x):
        """Returns D_h(x1, x) = 0.5*||x1 - x||^2 (Euclidean divergence)"""
        diff = x1 - x
        return 0.5 * np.dot(diff, diff)
    
    def div_prox_map(self, x, g, L):
        """
        Computes the Bregman proximal map:
        argmin_y { Psi(y) + <g, y> + L*D_h(y, x) }
        For Euclidean case with L2 regularization, this has a closed form.
        """
        # For Euclidean divergence and L2 regularization:
        # Solution is y = (L*x - g) / (L + lambda)
        coeff = L / (L + self.lambda_reg)
        return coeff * (x - g / L)


ARGS = {
    'f': FunctionWithGradient(),
    'h': BregmanDivergenceHandler(),
    'L': 1.0,
    'x0': np.array([0.5, -0.5]),
    'maxitrs': 10,
    'epsilon': 1e-14,
    'linesearch': True,
    'ls_ratio': 1.2,
    'verbose': True,
    'verbskip': 1
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1
Imports
numpy — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type tuple — a tuple output has no array shape of its own; none is stated
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
D_opt_FW Ran
ran on a synthesized input
Microsoft/accbpg/accbpg/D_opt_alg.py
code served (permissive licence) · get_code("6d3542f113696500")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned tuple. The image it ran in was not recorded. If your copy returns the same type on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import numpy as np

np.random.seed(0)

# V must be m by n with m < n
# The function uses: V.shape, V*x (element-wise mult), V.T, V[:, i]
m = 3
n = 5
V = np.random.randn(m, n)

# x0 must be initial point on the simplex (sum to 1, all non-negative)
# Size must match n
x0 = np.ones(n) / n

# eps: precision threshold for optimality conditions
eps = 1e-3

# maxitrs: maximum number of iterations
maxitrs = 10

ARGS = {
    'V': V,
    'x0': x0,
    'eps': eps,
    'maxitrs': maxitrs,
    'verbose': True,
    'verbskip': 1
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type tuple — a tuple output has no array shape of its own; none is stated
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
D_opt_FW_away Ran
ran on a synthesized input
Microsoft/accbpg/accbpg/D_opt_alg.py
code served (permissive licence) · get_code("ebb43079607596cc")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned tuple. The image it ran in was not recorded. If your copy returns the same type on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import numpy as np

np.random.seed(0)

# V is m by n matrix with m < n
# Create a small valid D-optimal design problem
m = 2  # number of rows
n = 4  # number of columns (must be > m)
V = np.random.randn(m, n)

# x0 is initial point - must be on the simplex (non-negative, sums to 1)
x0 = np.ones(n) / n

# eps is precision for optimality conditions
eps = 1e-4

# maxitrs is maximum number of iterations
maxitrs = 100

# verbose controls whether to print progress
verbose = True

# verbskip controls how often to print
verbskip = 10

ARGS = {
    'V': V,
    'x0': x0,
    'eps': eps,
    'maxitrs': maxitrs,
    'verbose': verbose,
    'verbskip': verbskip
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type tuple — a tuple output has no array shape of its own; none is stated
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
D_opt_KYinit Ran
ran on a synthesized input
Microsoft/accbpg/accbpg/applications.py
code served (permissive licence) · get_code("87864de3167417a5")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned ndarray, ndim 1, dtype family float, shape (8,) as a later run recorded it. The image it ran in was not recorded. If your copy returns the same type, ndim and shape on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import numpy as np

# Create a small test matrix V with shape (m, n)
# m = 3 (number of rows/features)
# n = 8 (number of columns/design points)
m = 3
n = 8
V = np.random.randn(m, n)

ARGS = {
    "V": V
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type ndarray, ndim 1, dtype family float, shape (8,) — shape (8,) as a later run recorded it
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
load_libsvm_file Ran
ran on a synthesized input
Microsoft/accbpg/accbpg/utils.py
code served (permissive licence) · get_code("8097e49b7557dfbf")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned tuple. The image it ran in was not recorded. If your copy returns the same type on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import tempfile
import os
import numpy as np

# Create a temporary libsvm format file
temp_file = tempfile.NamedTemporaryFile(mode='w', delete=False, suffix='.txt')
temp_filename = temp_file.name

# Write sample libsvm format data
# Format: label index1:value1 index2:value2 ...
libsvm_content = """1 1:0.5 2:1.2 4:0.8
-1 2:0.3 3:2.1
1 1:0.9 3:1.5 4:2.0
"""

temp_file.write(libsvm_content)
temp_file.close()

ARGS = {
    'filename': temp_filename,
    'dtype': np.float64,
    'n_features': None,
    'zero_based': 'auto',
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy, scipy — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type tuple — a tuple output has no array shape of its own; none is stated
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
mnist_2digits Ran
ran on a synthesized input
Microsoft/accbpg/accbpg/utils.py
code served (permissive licence) · get_code("39b1e2f7bd6e45fb")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned tuple. The image it ran in was not recorded. If your copy returns the same type on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import numpy as np

# Set random seed for reproducibility
np.random.seed(0)

# Create small synthetic data
# X: shape (10, 4) - 10 samples with 4 features
# y: shape (10,) - labels with values 0-9
X = np.random.randn(10, 4).astype(np.float32)
y = np.array([0, 0, 0, 1, 1, 1, 2, 3, 4, 5], dtype=np.int64)

# Parameters for the function
d1 = 0  # First digit class
d2 = 1  # Second digit class

ARGS = {
    'X': X,
    'y': y,
    'd1': d1,
    'd2': d2
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type tuple — a tuple output has no array shape of its own; none is stated
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
shuffle_data Ran
ran on a synthesized input
Microsoft/accbpg/accbpg/utils.py
code served (permissive licence) · get_code("fb69d5f3793a0e5b")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned tuple. The image it ran in was not recorded. If your copy returns the same type on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import numpy as np

# Set random seed for reproducibility
np.random.seed(42)

# Create sample data
# X: feature matrix with shape (5, 3) - 5 samples, 3 features
X = np.array([[1.0, 2.0, 3.0],
              [4.0, 5.0, 6.0],
              [7.0, 8.0, 9.0],
              [10.0, 11.0, 12.0],
              [13.0, 14.0, 15.0]])

# y: labels with shape (5,) - 5 labels
y = np.array([0, 1, 0, 1, 2])

ARGS = {
    "X": X,
    "y": y
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type tuple — a tuple output has no array shape of its own; none is stated
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
solve_theta Ran
ran, honoured the contract we drafted
linxiaolx/accbpg/accbpg/algorithms.py
code served (permissive licence) · get_code("5aabc13a3b3cb060")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1) and returned float, ndim 0, dtype family float, shape () as a later run recorded it. The image it ran in was not recorded. If your copy returns the same type, ndim and shape on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import torch
import numpy as np

torch.manual_seed(0)

# Analyze the function:
# - theta: used in arithmetic operations (**, -, +), appears to be a scalar float
# - gamma: used in arithmetic operations (**, -), appears to be a scalar float
# - gainratio: used in division, appears to be a scalar float (default=1)

# The function performs Newton's method to solve an equation
# All parameters are scalars used in mathematical operations

ARGS = {
    "theta": 0.5,
    "gamma": 2.0,
    "gainratio": 1.0
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1
Imports
numpy, torch — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type float, ndim 0, dtype family float, shape () — shape () as a later run recorded it
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
D_opt_design Not yet run
unverified (harvested, no recorded run)
Microsoft/accbpg/accbpg/applications.py
code served (permissive licence) · get_code("5ff255477435bde3")
How it ran

no invocation recorded.

D_opt_libsvm Not yet run
unverified (harvested, no recorded run)
Microsoft/accbpg/accbpg/applications.py
code served (permissive licence) · get_code("0779cc54868c0714")
How it ran

no invocation recorded.

Also present in other papers' code

Of 11 samples lifted from this paper's linked repositories, 11 carry a function identity and 0 do not. Of the 11 distinct functions with an identity, 0 are also present in other papers whose code we hold (0 with at least one paper dated earlier, 0 the same month, 0 later) and 11 are only here among the 52,977 papers whose code Syntology holds (as of 2026-09-26).

Only here means: among the 52,977 papers whose code Syntology holds (51,887 with lifted samples, 1,090 through their assemblies only), as of 2026-09-26, no other paper's lifted samples or current assembly bricks contain an identical function body after normalisation.

Presence, not direction: an identical function body in two papers' repositories does not say who wrote it, which came from which, or that either paper's method rests on it. Matching is exact after normalisation, so a renamed or edited function is not matched. Dates are when papers appeared, not when code was written. Only .py files the harvester lifted are covered; notebooks are not read. A new-style arXiv id YYMM.NNNN dates a paper to the month 20YY-MM; otherwise Paper.year dates it to the year; otherwise it is undated. Dates are when the paper appeared, not when the code was written. Read 2026-11-21.

Repositories linked to this paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

We consider the problem of minimizing the sum of two convex functions: one is differentiable and relatively smooth with respect to a reference convex function, and the other can be nondifferentiable but simple to optimize. We investigate a triangle scaling property of the Bregman distance generated by the reference convex function and present accelerated Bregman proximal gradient (ABPG) methods that attain an $O(k^{-γ})$ convergence rate, where $γ\in(0,2]$ is the triangle scaling exponent (TSE) of the Bregman distance. For the Euclidean distance, we have $γ=2$ and recover the convergence rate of Nesterov's accelerated gradient methods. For non-Euclidean Bregman distances, the TSE can be much smaller (say $γ\leq 1$), but we show that a relaxed definition of intrinsic TSE is always equal to 2. We exploit the intrinsic TSE to develop adaptive ABPG methods that converge much faster in practice. Although theoretical guarantees on a fast convergence rate seem to be out of reach in general, our methods obtain empirical $O(k^{-2})$ rates in numerical experiments on several applications and provide posterior numerical certificates for the fast rates.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("1808.03045")
get_code_for_paper("1808.03045")
have("1808.03045")

The run record, dated, one paper per request, free:

curl https://syntology.ai/api/ran/1808.03045.json

A badge for a README (the split and the date, never a ratio):

[![Syntology run record](https://syntology.ai/api/ran/1808.03045.svg)](https://syntology.ai/paper/1808.03045)

Connect an agent — have() is free.