We propose a communication- and computation-efficient distributed
optimization algorithm using second-order information for solving ERM problems
with a nonsmooth regularization term. Current second-order and quasi-Newton
methods for this problem either do not work well in the distributed setting or
work only for specific regularizers. Our algorithm uses successive quadratic
approximations, and we describe how to maintain an approximation of the Hessian
and solve subproblems efficiently in a distributed manner. The proposed method
enjoys global linear convergence for a broad range of non-strongly convex
problems that includes the most commonly used ERMs, thus requiring lower
communication complexity. It also converges on non-convex problems, so has the
potential to be used on applications such as deep learning. Initial
computational results on convex problems demonstrate that our method
significantly improves on communication cost and running time over the current
state-of-the-art methods.

提出了一种使用二阶信息进行通信和计算效率高的分布式优化算法来解决具有非平滑正则化项的 ERM 问题。该算法使用逐步二次逼近法，并描述了如何在分布式方式下有效地维护 Hessian 的逼近并解决子问题。该方法适用于广泛的非强凸问题，具有全局线性收敛性，需要更低的通信复杂度。同时，该方法可以收敛于非凸问题，因此具有在深度学习等应用中使用的潜力。初步的计算结果表明，该方法在凸问题上显著提高了通信成本和运行时间，超越了现有技术的方法。

一种用于非光滑规则化的经验风险最小化的分布式拟牛顿算法

A Distributed Quasi-Newton Algorithm for Empirical Risk Minimization  with Nonsmooth Regularization

Bilevel optimization problems are a class of challenging optimization
problems, which contain two levels of optimization tasks. In these problems,
the optimal solutions to the lower level problem become possible feasible
candidates to the upper level problem. Such a requirement makes the
optimization problem difficult to solve, and has kept the researchers busy
towards devising methodologies, which can efficiently handle the problem.
Despite the efforts, there hardly exists any effective methodology, which is
capable of handling a complex bilevel problem. In this paper, we introduce
bilevel evolutionary algorithm based on quadratic approximations (BLEAQ) of
optimal lower level variables with respect to the upper level variables. The
approach is capable of handling bilevel problems with different kinds of
complexities in relatively smaller number of function evaluations. Ideas from
classical optimization have been hybridized with evolutionary methods to
generate an efficient optimization algorithm for generic bilevel problems. The
efficacy of the algorithm has been shown on two sets of test problems. The
first set is a recently proposed SMD test set, which contains problems with
controllable complexities, and the second set contains standard test problems
collected from the literature. The proposed method has been evaluated against
two benchmarks, and the performance gain is observed to be significant.

本文提出了一种基于二次逼近的基础进化算法（BLEAQ），该方法可以较少的函数评估次数来处理不同类型复杂度的双层优化问题，其有效性已在多组测试问题上得到验证。

单目标双层优化高效进化算法

Efficient Evolutionary Algorithm for Single-Objective Bilevel  Optimization

The observations in many applications consist of counts of discrete events,
such as photons hitting a detector, which cannot be effectively modeled using
an additive bounded or Gaussian noise model, and instead require a Poisson
noise model. As a result, accurate reconstruction of a spatially or temporally
distributed phenomenon (f*) from Poisson data (y) cannot be effectively
accomplished by minimizing a conventional penalized least-squares objective
function. The problem addressed in this paper is the estimation of f* from y in
an inverse problem setting, where (a) the number of unknowns may potentially be
larger than the number of observations and (b) f* admits a sparse
approximation. The optimization formulation considered in this paper uses a
penalized negative Poisson log-likelihood objective function with nonnegativity
constraints (since Poisson intensities are naturally nonnegative). In
particular, the proposed approach incorporates key ideas of using separable
quadratic approximations to the objective function at each iteration and
penalization terms related to l1 norms of coefficient vectors, total variation
seminorms, and partition-based multiscale estimation methods.

本文探讨了如何从 Poisson 数据中准确地重建分布式现象，运用了带惩罚项的负 Poisson 对数似然目标函数，并结合采用分离二次近似和 l1 范数、总变差半范数以及基于分区的多尺度估计方法等关键思想。