N. Krejić, N. Krklec Jerinkić, S. Rapajić, L. Rutesić

Optimization problems with the objective function in the form of weighted sum and linear equality constraints are considered. Given that the number of local cost functions can be large as well as the number of constraints, a stochastic optimization method is proposed. The method belongs to the class of variable sample size first order methods, where the sample size is adaptive and governed by the additional sampling technique earlier proposed in the unconstrained optimization framework. The resulting algorithm may be a mini-batch method, increasing sample size method, or even deterministic in a sense that it eventually reaches the full sample size, depending on the problem and similarity of the local cost functions. Regarding the constraints, the method uses controlled, but inexact projections on the feasible set, yielding possibly infeasible iterates. Almost sure convergence is proved under some standard assumptions for the stochastic framework, without imposing the convexity. Numerical results on relevant machine learning experiments, i.e., real-world data sets for logistic regression problems, show that the proposed algorithm is competitive with the state-of-the-art methods.

Nataša Krklec Jerinkić, Valeria Ruggiero andIlaria Trombini

In this paper, we propose a new stochastic gradient method for numerical minimization of finite sums. We also propose a modified version of this method applicable on more general problems referred to as infinite sum problems, where the objective function is in the form of mathematical expectation. The method is based on a strategy to exploit the effectiveness of the well-known Barzilai–Borwein (BB) rules or variants of these (BB-like) rules for updating the step length in the standard gradient method. The proposed method adapts the aforementioned strategy into the stochastic framework by exploiting the same Sample Average Approximations (SAA) estimator of the objective function for several iterations.

N. Krejić, N. Krklec Jerinkić, T. Ostojić, N. Vučićević

In this paper, we propose a new stochastic gradient method for numerical minimization of finite sums. We also propose a modified version of this method applicable on more general problems referred to as infinite sum problems, where the objective function is in the form of mathematical expectation. The method is based on a strategy to exploit the effectiveness of the well-known Barzilai–Borwein (BB) rules or variants of these (BB-like) rules for updating the step length in the standard gradient method. The proposed method adapts the aforementioned strategy into the stochastic framework by exploiting the same Sample Average Approximations (SAA) estimator of the objective function for several iterations.

Nataša Krklec Jerinkić, Federica Porta, Valeria Ruggiero, Ilaria Trombini

Regularized empirical risk minimization problems arise in a variety of applications, including machine learning, signal processing, and image processing. Proximal stochastic gradient algorithms are a standard approach to solve these problems due to their low computational cost per iteration and a relatively simple implementation. This paper introduces a class of proximal stochastic gradient methods built on three key elements: a variable metric underlying the iterations, a stochastic line search governing the decrease properties and an incremental mini-batch size technique based on additional sampling. Convergence results for the proposed algorithms are proved under different hypotheses on the function to minimize.

Nataša Krklec Jerinkić, Luka Rutešić, Ilaria Trombini

We consider unconstrained multi-criteria optimization problems with finite sum objective functions. The proposed algorithm belongs to a non-monotone trust region framework where additional sampling approach is used to govern the sample size and the acceptance of a candidate point. Depending on the problem, the method can yield a mini-batch or an increasing sample size behavior. This work can be viewed as an extension of additional sampling trust region method for scalar finite sum function minimization presented in the literature, requiring nontrivial modifications both in construction and in convergence analysis of the algorithm.

N. Krejić, N. Krklec Jerinkić, L. Rutesić

The problem we consider is a multi-objective optimization problem, in which the goal is to find an optimal value of a vector function representing various criteria. The aim of this work is to develop an algorithm which utilizes the trust region framework with probabilistic model functions, able to cope with noisy problems, using inaccurate functions and gradients. The key novelty is approximation of each function in the multiobjective problem with probabilistically fully linear model which yields the composite model defined by max operator as a satisfactory approximation for the nonsmooth scalarized objective function.

Zoltan Papp, Sanja Rapajić, Abdulkarim Hassan Ibrahim, Supak Phiangsungnoen

We propose two hybrid methods for solving large-scale monotone systems, which are based on derivative-free conjugate gradient approach and hyperplane projection technique. The conjugate gradient approach is efficient for large-scale systems due to low memory, while projection strategy is suitable for monotone equations because it enables simply globalization. The derivative-free function-value-based line search is combined with Hu-Storey type search directions and projection procedure, in order to construct globally convergent methods. Furthermore, the proposed methods are applied into solving a number of large-scale monotone nonlinear systems and reconstruction of sparse signals. Numerical experiments indicate the robustness of the proposed methods.

Abdulkarim Hassan Ibrahim, Sanja Rapajić, Ahmad Kamandi, Poom Kumam, Zoltan Papp

Solving systems of nonlinear equations has evolved into an active research field, with numerous iterative methods being proposed. Notably, iterative methods characterized by fast convergence remain of interest. In this paper, based on the modified line search scheme by Ou and Li, we introduce a derivative-free algorithm with a relaxed-inertial technique for approximating solutions of nonlinear systems involving pseudo-monotone mappings in Euclidean space. The global convergence of the proposed algorithm is established without Lipschitz continuity of the underlying mapping. Moreover, our approach allows flexibility in selecting the inertial extrapolation step length within the interval [0, 1]. To show the efficiency of the proposed method, we embed a derivative-free search direction into the scheme. Numerical experiments are given to illustrate the efficiency of the proposed algorithm for large-scale systems and sparse signal reconstruction.

Aleksandar Armacki, Himkant Sharma, Dragana Bajović, Dušan Jakovetić, Mrityunjoy Chakraborty, Soummya Kar

We study the effects of center initialization on the performance of a family of distributed gradient-based clustering
algorithms, that work over connected networks of users. In the considered scenario, each user contains a local dataset and communicates only with its immediate neighbours, with the aim of finding a global clustering of the joint data. We perform extensive numerical experiments, evaluating the effects of center initialization on the performance of our family of methods, demonstrating that our methods are more resilient to the effects of initialization, compared to centralized gradient clustering. Next, inspired by the K-means++ initialization, we propose a novel distributed center initialization scheme, which is shown to improve the performance of our methods, compared to the baseline random initialization.

Dragana Bajović, Dušan Jakovetić, Soummya Kar, Manojlo Vuković

We present an algorithm for distributed estimation of an unknown vector parameter in the presence of heavy-tailed observation and communication noises. Heavy-tailed noises frequently appear, e.g., in densely deployed Internet of Things (IoT) or wireless sensor network systems. The presented algorithm falls within the class of consensus + innovation estimators and combats the effect of heavy-tailed noises by adding general nonlinearities in the consensus and innovation update parts. We present results on the almost sure convergence and asymptotic normality of the estimator. In addition, we provide novel analytical studies that reveal interesting trade-offs between the system noises and the underlying network topology.

Aleksandar Armacki, Dragana Bajović, Dušan Jakovetić, Soummya Kar

We develop a family of distributed center-based clustering algorithms that work over networks of users. In the proposed scenario, users contain a local dataset and communicate only with their immediate neighbours, with the aim of finding a clustering of the full, joint data. Experiments validate our theory, demonstrating noise symmetry in real-life settings and showing that clipping is not always the optimal nonlinearity, further underlining the value of a general framework.

Aleksandar Armacki, Shuhua Yu, Pranay Sharma, Gauri Joshi, Dragana Bajovic, Dusan Jakovetic, Soummya Kar

We study high-probability convergence guarantees of learning on streaming data in the presence of heavy-tailed noise. In the proposed scenario, the model is updated in an online fashion, as new information is observed, without storing any additional data. To combat the heavy-tailed noise, we consider a general framework of nonlinear stochastic gradient descent (SGD), providing several strong results.

Dušan Jakovetić , Nataša Krejić , Greta Malaspina

We consider two formulations for distributed optimization wherein N nodes in a generic connected network solve a problem of common interest: distributed personalized optimization and consensus optimization. A new method termed DINAS (Distributed Inexact Newton method with Adaptive Step Size) is proposed. DINAS employs large, adaptively computed step sizes, requires reduced knowledge of global parameters compared with existing alternatives, and can operate without any local Hessian inverse calculations or Hessian communications.

Lidija Fodor, Dušan Jakovetić , Nataša Krejić , Greta Malaspina

Motivated by localization problems such as cadastral map refinements, we consider a generic Nonlinear Least Squares (NLS) problem of minimizing an aggregate squared fit across all nonlinear equations (measurements) with respect to the set of unknowns, e.g., coordinates of the unknown points’ locations. In a number of scenarios, NLS problems exhibit a nearly separable structure: the set of measurements can be partitioned into disjoint groups (blocks), such that the unknowns that correspond to different blocks are only loosely coupled.

Nataša Krklec Jerinkić , Federica Porta , Valeria Ruggiero and Ilaria Trombini

Regularized empirical risk minimization problems arise in a variety of applications, including machine learning, signal processing, and image processing. Proximal stochastic gradient algorithms are a standard approach to solve these problems due to their low computational cost per iteration and relatively simple implementation.

Nataša Krklec Jerinkić , Valeria Ruggiero and Ilaria Trombini

In this paper, we propose a new stochastic gradient method for the numerical minimization of finite sums. We also propose a modified version of this method that is applicable to more general problems, referred to as infinite-sum problems, where the objective function is expressed in the form of a mathematical expectation.The method is based on a strategy that exploits the effectiveness of the well-known Barzilai–Borwein (BB) rules, or variants of these BB-like rules, for updating the step length in the standard gradient method. The proposed method adapts this strategy to the stochastic framework by exploiting the same Sample Average Approximation (SAA) estimator of the objective function over several iterations.

Stefania Bellavia, Nataša Krejić, Nataša Krklec Jerinkić, Marcos Raydan

The spectral gradient method is known to be a powerful low-cost tool for solving large-scale optimization problems. In this paper, our goal is to exploit its advantages in the stochastic optimization framework, especially in the case of mini-batch subsampling that is often used in big data settings. To allow the spectral coefficient to properly explore the underlying approximate Hessian spectrum, we keep the same subsample for several iterations before subsampling again. We analyze the required algorithmic features and the conditions for almost sure convergence, and present initial numerical results that show the advantages of the proposed method.

Nataša Krejić, Nataša Krklec Jerinkić, Angeles Martinez, Mahsa Yousefi

In this work, we introduce a novel stochastic second-order method, within the framework of a non-monotone trust-region approach, for solving the unconstrained, nonlinear, and non-convex optimization problems arising in the training of deep neural networks. The proposed algorithm makes use of subsampling strategies which yield noisy approximations of the finite sum objective function and its gradient. To effectively control the resulting approximation error, we introduce an adaptive sample size strategy based on inexpensive additional sampling. Depending on the estimated progress of the algorithm, this can yield sample size scenarios ranging from mini-batch to full sample functions.