Minimizing the difference of two submodular (DS) functions is a problem that
naturally occurs in various machine learning problems. Although it is well
known that a DS problem can be equivalently formulated as the minimization of
the difference of two convex (DC) functions, existing algorithms do not fully
exploit this connection. A classical algorithm for DC problems is called the DC
algorithm (DCA). We introduce variants of DCA and its complete form (CDCA) that
we apply to the DC program corresponding to DS minimization. We extend existing
convergence properties of DCA, and connect them to convergence properties on
the DS problem. Our results on DCA match the theoretical guarantees satisfied
by existing DS algorithms, while providing a more complete characterization of
convergence properties. In the case of CDCA, we obtain a stronger local
minimality guarantee. Our numerical results show that our proposed algorithms
outperform existing baselines on two applications: speech corpus selection and
feature selection.

介绍了 DC 算法及其变种算法，并将其应用于 DS 问题的 DC 程序中，并将收敛性质与 DS 问题的收敛性质相连结，取得了比现有基线更好的结果。

基于 DC 规划的子模函数最小化差异

Difference of Submodular Minimization via DC Programming

The stringent requirements for low-latency and privacy of the emerging
high-stake applications with intelligent devices such as drones and smart
vehicles make the cloud computing inapplicable in these scenarios. Instead,
edge machine learning becomes increasingly attractive for performing training
and inference directly at network edges without sending data to a centralized
data center. This stimulates a nascent field termed as federated learning for
training a machine learning model on computation, storage, energy and bandwidth
limited mobile devices in a distributed manner. To preserve data privacy and
address the issues of unbalanced and non-IID data points across different
devices, the federated averaging algorithm has been proposed for global model
aggregation by computing the weighted average of locally updated model at each
selected device. However, the limited communication bandwidth becomes the main
bottleneck for aggregating the locally computed updates. We thus propose a
novel over-the-air computation based approach for fast global model aggregation
via exploring the superposition property of a wireless multiple-access channel.
This is achieved by joint device selection and beamforming design, which is
modeled as a sparse and low-rank optimization problem to support efficient
algorithms design. To achieve this goal, we provide a
difference-of-convex-functions (DC) representation for the sparse and low-rank
function to enhance sparsity and accurately detect the fixed-rank constraint in
the procedure of device selection. A DC algorithm is further developed to solve
the resulting DC program with global convergence guarantees. The algorithmic
advantages and admirable performance of the proposed methodologies are
demonstrated through extensive numerical results.

提出了一种基于超过空气计算的方法，探索了无线多接入通道的叠加属性，用于边缘机器学习中的快速全局模型聚合。