The Development of Green Software Process Model

Software process and development are the fundamental activities in software engineering. Increasing software usage either develops in-house or outsourcing requires improving the software process accordingly to minimise the adverse effects on the environment. The resources and power consumption controlled by hardware affected the software to move the process that causes high emission of power and energy. Thus, most of the existing work on software development is aimed at the efficiency of hardware operation through CPU, memory, and processor. Although sustainability is still initial in software engineering, the green software process can be achieved through sustainable development that concerns the preservation of the environment. However, there is still a lack of study and effort in the software process that emphasises sustainability perspectives and software waste elimination. Therefore, this study proposes the green factors for the software process that consider the sustainability elements and waste reduction during development. The green factors are the benchmark to measure a sustainable and green software process. Besides, this paper also presents the qualitative interview design and pilot study. The pilot study analysis has demonstrated the reliability of the interview protocol. Therefore, the actual interview and data analysis are currently in progress. Keywords—Software process; green factor; waste reduction; qualitative instrument; green software process model

I. INTRODUCTION
Software was becoming crucial and became part of our life today. The development of software systems needs to reflect on sustainability and environmental impact [1]. Software is vital to do work and tasks more efficiently. Software causes hardware activity, and it is responsible for the increment of energy consumption in that way. It has become the central aspect of daily life, and most people cannot imagine that future development without software.
Electricity consumption in the ICT sector is expected to increase by 60% from 2007 to 2020. Since ICT contributes to 2% of carbon dioxide emissions from the electronics, household, ICT services, and equipment sector, an estimated 8% is from electricity consumption [1]. Systematic methods for improving the organisation's environmental sustainability provided several guidelines such as the Eco-Management and Audit (EMAS) Scheme, the ISO 14001 standard, and the Environmental Management System (EMS). Meanwhile, large organisations need to publish their organisation's corporate social reports for employee compliance [2].
Generally, sustainability means the beginning to nurture the future generation aligned with the present and compliance with the own needs [3]. Sustainability in the software system is a concept of recycling to protect the environment as excessive waste production can harm the environment's wellbeing [4]. In addition, sustainability is a resource to support life and the environment that requires the courage of individuals or communities to be maintained for a long time [5]. In engineering, it needs to demonstrate efforts to improve the environment, social and economic. Therefore, sustainable software development is for the system requirements required [6] to ensure the sustainability of nature.
Today, "going green" is an essential part of business practices worldwide related to the environment [7]. Several factors that determine the greenness of the software process have been considered that take into account the sustainability aspect such as resources and products [8] [9], people [7][10], organisation [11] [12], technical [13] [14], and environmental [15] [16].To create every phase of the software process sustainable, it must go through the green strategy, guideline, and green metric that ultimately reflect the greenness of the entire stage [4].
Over the past three years, green software engineering has grown and evolved due to concerns over the software, industry, and consumers' development. However, it focuses on the fundamental aspects of energy efficiency and power consumption, affecting the environment [17]. Many studies discuss green software development that focuses on hardware perspective on energy efficiency and power consumption [18]. Green software development as a whole, the software process methodology should be considering investigating their requirement to create sustainable and green manner.
Green software engineering goals are to minimise the negative effect on the environment [1] [19] and produce sustainable software products. Previous studies [20][21][22][23] emphasise green hardware in energy efficiency, power consumption, waste reduction, and disposal. However, it seems to lack studies on green software even though the impacts are direct to hardware [17], but the software also indirectly impacts. The initiatives of green software are to save resources such as energy, power, and natural resources to preserve the stability of the ecosystem [24]. Nowadays, the software is no longer viewed in terms of productivity but needs to focus on scalability, usability, and quality [25] with recent advances in-demand new technology. www.ijacsa.thesai.org Therefore, this research is essential to ensure the software development process complies with the green requirement as needed by the community and industry in general. Currently, the green development issues are not being focused on comprehensively, especially from a sustainability perspective.
The article organisation is as follows. In Section 2, we discuss the background study and related works of the green software process. While in Section 3, the research method and activities are presented. It discusses the approach of carrying out this research. In Section 4, we will discuss the qualitative design and pilot analysis, and lastly, we will conclude this paper with a conclusion and future work.

II. RELATED WORK
The software process is a work in progress requiring changes to the user's needs to use the software effectively. In addition, the target of the software process is to improve the job done and used by various companies facing the inevitable difficulties and uncertainties of the process software. Some aspects of software development require the user's attention; the product developed should reach the customer well based on the specified cost and time [26].
Applying green practices as part of the software development process attempts to achieve a green software process. It means to practice for the software is considering the environmental aspects. In addition, the software process involves the development, operation, and maintenance that is carried out in a green approach and producing green software processes. Besides, the green software process can create less waste throughout the development [17,22].
The transition to the green software process requires careful study as it involves several critical activities in the software development process. The implementation of green initiatives can be done in phases, observing how the software works without cost during the software development process. Research on the transition and development of green software processes is to improve the practices of the process. There are ways to develop green software processes that are to implement green software process practices. Implementing this method supports reducing waste during software development, such as unproductive workers, power savings, and resources.

A. Issues and Challenges in Green Software Process
Information and Communication Technology (ICT), particularly in software development, remains significant and increasingly important even with the emergent of new areas such as big data, cloud computing, Cyber-Physical Systems (CPS), and IoT [25]. Nevertheless, software development still has issues and challenges maintaining relevance and sustainability of the process to ensure the quality of the developed product.
1) Software development process: As described by [27], software development involves a wide range of skills and disciplines, including identifying user needs, values, and features that support the final product. Software development projects have many obstacles and barriers to complete and deliver the project. Several factors come from the organisation environment, team, and user perspective that are not wellprepared according to requirement, budget, and time [28][29]. Most software development projects failed due to higher budgets, overtime, and low customer satisfaction. According to [25], the causes of failures are time, finances, staffing, and management.
Various software projects are often ambiguous, where the goals and objectives are unclear due to the lack of experience from the users. Software project development requires a lot of communication and the time taken to complete it successfully. As developers, they are intelligent users who do not use specialists to translate their needs into software engineering. In addition, developers should engage users in software development to help them understand the needs and delivery of project functions well. Users involvement [26], from the beginning of software development to the end, is vital as this is one of the criteria for the success of a project.
Generally, the software process has five main phases: requirement specification, design, implementation, testing, and maintenance. Some activities in this phase may cause problems and challenges, especially in fulfilling current demands such as reducing paper use, e-waste generation, and controlling carbon footprint and energy efficiency.
Shenoy and Eeratta [22] suggested creating sustainable and green software processes without adversely affecting global economic, environmental, social, and individual wellbeing. At the same time, there are five primary and fundamental activities associated with the development process and will be discussed in the following subsections: a) Requirement Specification Phase: The requirement specification is an important activity in software development. It is conducted with the specified team by getting information from the users. The software requirements specification (SRS) is delivered as the outcome of requirement gathering and analysis activity [30]. A good software requirement specification aims to satisfy the needs of its customers. Based on [31], some possible green analysis criteria include viability, requirements, and tests.
Many problems exist in requirement analysis, such as lack of user input, incomplete and frequently changing requirements, and specifications. The literature suggested coming across the software regarding its lifespan and durability [22]. In addition, the collection of requirement specifications is required through electronic methods to save resources such as paper and preserve the environment. Furthermore, as [30,32] suggested, software should adopt new hardware for energy efficiency and coping with power down during its operation.
b) Design Phase: The functional and technical requirements gathered during the requirement stage create the design document and artefact. During the design phase, the SRS is referred to as the primary reference for product architecture.
This documentation is supportive of the software development process. Therefore, the design team needs to cooperate with the software developer on this document www.ijacsa.thesai.org before proceeding to the next phase. All stakeholders must review the Document Design Specification (DDS), and the best approach is selected based on budget, time constraints, risk, robustness, and design method [30]. Reference [31] suggested that performance, reusability, and documentation are among the green analysis criteria in the green process. Design reuse and virtual design are also other factors defined in the green process by [33]. Furthermore, previous researchers [22,33] argue that the initial design should be moderate to avoid frequent design changes. The design should not be too large and lead towards practices that protect the resources.
c) Implementation Phase: Implementation and coding are the subsequent activities in the software development process. The source code is generated based on a detailed and well-organised design to avoid problems during the development. This phase involves source code written in specific programming languages based on the developer's preference and the project approach.
The implementation phase is an emphasis on programming. There are several things to avoid, which are the use of duplicate code, custom hardware APIs, and resourceintensive APIs. It encouraged the user to utilise the high resources on tap systems that need to process programming complexity. In addition, paired programming, code reuse, and automated code generation support minimising and saving energy consumption [22].
The guidelines in the design and implementation phase can support the sustainability of the environment if the programmer needs to be proficient in writing algorithms by summarising design code and data structure according to the hardware architecture, programming languages, and applications. Programmers must produce practical algorithms by minimising the number of program lines to reduce their execution later. As mentioned by [33][34], extending the program code requires energy efficiency and additional work to execute the code. d) Testing Phase: The testing phase relates to the product errors detected and re-analysed until they meet the quality requirements of SRS. There are different types of tests performed by integration system testing. Reference [30] stated that testing aims to ensure that the developed software is free of bugs, faults, or defects and meets all requirements specified during the requirement stage. The specifications are needed to be understood by conducted initial testing at the final stage of requirements. Then, different testers [35] can avoid bias and validate requirements correctly and consistently. The user acceptance test is the last activity in the system testing. The end-users [31] usually are carried out this task to ensure the system meets their needs.
According to [32], the software development team faces time constraints to find errors through testing. Therefore, previous studies [22,30] recommend using automated testing, reusing test cases to determine performance scalability and resource testing. In the testing phase, the program involved improvement of energy efficiency will use energy measuring instruments. The green analysis criteria are functionality and measurement. The functionality refers to all tests explained in the requirements, while the measurement evaluates the suitability of product energy consumption [35] measured and inspected during testing. e) Maintenance Phase: The maintenance phase is associated with software operation and maintenance, which implement the product in the real environment. Software maintenance takes place if issues need to be repaired or improved [36] [37] to ensure the sustainability and quality of the product are maintained and guaranteed.
Any errors and complaints should take through electronic documentation to save time and paper during the maintenance phase. Furthermore, software archaeology, reverse engineering, and software migration are not recommended because these will contribute to the high costs and effort in execution. It is encouraged to manage knowledge among the team member effectively [22] in the development and maintenance phase to ensure a clear understanding of the system. It may reduce cost and efforts in maintenance.
Maintenance costs are high due to understanding the system and the changes that need to be analysed. Some maintenance and development contracts are separate during system development because they are kept by the company and not by the system developer. It makes it difficult for maintenance tasks and increases energy consumption if there are any changes in the system as it needs time to understand the system [34]. It is suggested by [72] that the programmer write the code that is easy and more under regular programming because if any code change is required at any stage, the correction could be done quickly. The maintenance phase could be green by including the matrices like fault tolerance, failure management, and disposal stage.
Furthermore, to reduce costs and improve energy efficiency, managers must provide training or courses to the staff to understand the old and new programming languages to speed up the maintenance process. Environmental sustainability can be supported at the implementation stage, in which program development is written for good and clear understanding by programmers. If any changes are required, the program can be easily understood, and the internal maintenance work is completed quickly, improves energy efficiency [33,71], quality and long life of the product [38].
2) Software waste: According to [39], waste management is one of the critical aspects of preserving the environment. Waste is deemed by [40] as irrelevant and has no value to production. Solid waste produces waste in the manufacturing [40] and construction [41] industries. In general, software waste is used by resources without delivering any advantage. It may contain characteristics, objects, conditions, processes, and actions in project elements. In the software domain, wastes act as friction and occur throughout the development process [42] until they produce the end of the product. The wastes need to be reduced and thus will increase efficiency in development even though the awareness and identification of waste are critical during production. www.ijacsa.thesai.org Software waste often has a problem related [43] to scope, unclear requirements, specification and design, unnecessary features and technical, team conflict, and unorganised code programming during the development process. Many researchers have been investigated software waste during the development process [27,[44][45][46]. These wastes are identified, such as building the wrong feature or product, mismanaging the backlog, rework, unnecessarily complex solutions, extraneous cognitive load, psychological distress, waiting/multitasking, knowledge loss, and ineffective communication in software development.
Sedano et al. [47] suggested the way to improve software engineering productivity by proposing a theory of sustainable software development that incorporates sustainability toward the principles, policies and practices into the knowledge of extreme programming. These included encouraging knowledge sharing, developing a positive attitude toward the team disruption, and considering code quality. Besides that, the policies include team code ownership, a standard schedule, and avoiding technical debt. The developers can apply good practices like test-driven development, continuous refactoring, pair programming, overlapping pair rotation, and knowledge pollination [47].
3) Green software process: Previously, the general issues in the software development process are related to time constraints, high costs, bugs and errors. But nowadays, [48] discovers that more known problems are related to people, resource and development tasks coordination and tracking.
As mentioned earlier, the software development process in a suitable environment manner and practices will lead and enhance the efficiency of the development. Sound environmental practices attempt to improve the activities that need to be implemented through software process methodology. The method of green software refers to the use of resources to meet the needs of the software with regards to the economic, social, and environmental aspects and effects. Software sustainability is considered as the ability of the software to have a longer life. In addition, the production of little waste during software development and operation [49] is one of the meanings of green software.
Sustainability and green are closely related in software engineering to ensure the long-lasting of the software in their environment. The sustainable design of the software is essential to fulfilling the user's needs and current demands.
Sustainable software refines user needs in terms of economy, society, and environment [50] in the whole life cycle phase. It concerns ensuring the long-lasting software to design, develop and deploy. From a software perspective, green is aimed to reduce the carbon footprint and negative impacts of software based on economy, society, and environment [31] during the development process. The software engages with the life cycle in green software engineering and sustainable criteria. Furthermore, Agarwal, Nath, and Chowdhury [32] proposed integrating green software development life cycle and sustainability criteria. Sustainability supports these three main dimensions, namely economic, social and environmental. There are two different views when it comes to software. The first is sustainable software that prioritises the principles, practices, and processes that contribute to the durability of technical sustainability software. Next, [51] argues that software systems need to support other dimensions of sustainability and solve problems external to software systems. The second is software engineering for sustainability (SE4S). Both of these views are considered important as the centre of software sustainability development [53], and they need to support the five primary dimensions of economic, social, environmental, individual, and technical [52].
Generally, the economic dimension refers to capital assets or values involving capital investment, income, wealth, and profit. In contrast, the social element encompasses society, which consists of organisations and groups of people engaged in democracy, justice, employment, and social equality. The environmental dimension relates to ecosystems, climate, pollution, waste, and natural resources that can long-term impact humans and biological systems. The individual dimensions include mental and physical well-being, selfesteem, and the freedom to view human well-being as an individual. The latter is the technical dimension which involves system maintenance, infrastructure, the evolution of changing environmental conditions, and the long-term concept of system information.

B. Green Factors
The green factor is the benchmark used to assess the greenness of the software development process based on a certain standard. It should be used to ensure greenness in the software process and be applicable for future generations.
A literature study has identified green resources, people, organisational, technical, and environmental factors. From the software perspective, resource means the natural resources that must be protected from human needs and wastes. For instance, cloud computing is an alternative way to reduce energy and space in physical conditions. Meanwhile, people refer to improving the quality of human life [54] that reflects emotional health, including behaviour, thought, and action.
Organisational refers to the current need of an organisation includes leadership, employee, and performance [55]. Besides, the technical factor [56] is to cope with changes, quickly adapt to future changes, and the longevity of software systems. The environmental aspect relates to avoiding harm to the environment [57], and thus software should have minimal effects on the background during the development and maintenance process. Table I indicates the green factors and elements in the software process based on previous studies. It shows that the most popular aspects are energy efficiency, resource optimisation, environmental effect, performance, organisational support, employee support, and capacity optimisation associated with the green software process (refer to Table I). www.ijacsa.thesai.org A2 [58] A3 [11] A4 [59] A5 [60] A6 [8] A7 [56] A8 [61] A9 [62] A10 [63] A11 [64] A12 [65] A13 [66] A14 [67] A15 [68]  III. METHOD During the literature study, a list of green software process factors is identified. The factors are broken down into several elements and measurements. They are used to assess the greenness compliance and level of specific software. Fig. 1 presents the flow of this research, which shows the step-bystep activities carry out in this study.
The literature study has revealed five primary green factors: resource, people, organisation, technical and environmental. The qualitative interview is designed and constructed for field expert's or academician's validation of the factors. A pilot study and content validation are carried out before the actual survey is conducted to ensure the reliability of the interview protocol. After completing the pilot study, the actual empirical study through the interview approach will be carried out. The informants are the developers, practitioners, or project managers of in-house software development companies and agencies in the public sector, which is the scope of this study.
Then, the next activity will be the data analysis. This activity will be carried out after the interview series have been completed. The data analysis will be conducted using Atlas.ti 8 software to determine the code and thematic of the interview finding. Another important task during the analysis is triangulation. Triangulation refers to measuring the reliability www.ijacsa.thesai.org of the study and the extent to which it is accurate for evaluating the concept or idea. One way to conduct the triangulation is through obtaining confirmation and approval from the interviewees on the findings.
As shown in Fig. 1, this research is conducted in four main phases. The following sub-sections explain each of the phases in detail.

A. Phase 1: Theoretical Study
The first phase is the theoretical study investigating the integration between sustainability elements and waste management for software processes. The references consist of the current journals, books, and proceedings that are being studied and investigated. This phase aims to identify the types of waste and the green factors that influence the software process. It also examines issues and problems concerns to green software process from literature. The result of this phase is the theoretical framework for the Green Software Process Assessment based on Sustainability and Waste Elements. The author in [17] shows the theoretical framework.

B. Phase 2: Empirical Study
In this phase, interviews will be conducted involving software practitioners to get real input from the industry. The informants of this study will be identified and selected from software practitioners, project leaders, information technology (IT) officers, software engineers and related IT positions. They must involve in the software development process with experience and knowledge in the field of software development. The selection of informants is based on the purposive sampling technique and aims to the organisations involved in in-house software development.
This paper presents the activity in this empirical study phase. In this phase, the interview questions are designed and constructed. The validity of the content is determined through expert validation. Furthermore, we conducted a pilot study to ensure the reliability of the interview protocol. The pilot analysis is carried out and presented in this paper as the preliminary findings. The next step in this phase will be the actual interview sessions with the identified informants. This phase will reveal and verify the influential factors in the green and sustainability software process and the current green practices in the actual software industry. In addition, software wastes formed during the software process's development and sustainability measurements will also be identified at the end of this phase.

C. Phase 3: Development of Green Software Process (Green SoftPro) Model
The third phase of this study is developing the proposed green software process model based on sustainability and waste elements. The proposed model also integrates the concepts of software waste based on inputs from theory and empirical findings. The model will identify and embed the relationship between green factors and sustainability measures that influence the greenness of software processes. In addition, the wastes specified at each phase of the software process and in line with the sustainability requirements will be considered during the model construction. The outcome of this phase is a Green Software Process (Green SoftPro) model.

D. Phase 4: Model Validation
The last phase of this research is to validate the Green SoftPro model, and the validation involves two steps. The first step is the verification by experts. The experts from the software developers and practitioners will be invited to review and validate the Green SoftPro model, which consists of green factors, elements and measurements. Further, the validation will be conducted through a case study approach. At least two software companies or government agencies will be invited to participate in the case study. The Green SoftPro model will be applied and will be validated in the actual software-industrial environment. (IJACSA) International Journal of Advanced Computer Science and Applications, Vol. 12, No. 8, 2021 595 | P a g e www.ijacsa.thesai.org

IV. THE QUALITATIVE STUDY: DESIGN AND PILOT ANALYSIS
This study uses the interview method to identify the current practices, issues, and challenges for green and sustainable software processes. This paper focuses on the interview protocol design and pilot study.

A. Design and Development of Interview Protocol
The interview protocol is designed based on the literature review and the proposed theoretical framework (refer to [17]). The protocol consists of four main parts, Part 1: Demographics Background, Part 2: The Practice of Green Software Process, Part 3: Waste in Software Process, and Part 4: Green Factor and Measurement for Software Process. Table II shows the items of part 1, part 2 and part 3, which are designed in the interview protocol. And Table III shows the items associated with part 4 of the protocol that consists of the green factor and measurement. The factors are resources, people, organisational, technical and environmental.

B. Pilot Study
In qualitative research, the purpose of a pilot study is to validate and reliable the interview instruments. The pilot study was conducted in three selected organisations. The interview session was performed in 2020, and each session took about one hour during a face-to-face interview. Each of the interview sessions was recorded with permission and transcribed were analysed using transcription software. All comments and recommendations were recorded and taken into consideration.
The interview sessions in this pilot study were carried out with three software or IT experts. The selection criteria of experts are based on expertise in software engineering and, more specifically, in the in-house software development process. The duration of working experience was also considered in selection criteria where they have working experience of at least five years in the industry. The experts' working experience is based on the years suggested by [69][70]. Table IV shows the expert's background who was involved in this interview's session.  V. RESULT AND DISCUSSION Based on the pilot analysis, the experts recommended that some items in the protocol be improved because they believed that they were not related to the green software process. Some of the items required correction for clarification. Other than that, the expert agreed with the defined content in the protocol.
Three interview scripts were translated and analysed. The findings consist of the three main issues: current issues in the software development process, factors and elements of the green software process, and elements of software waste.

A. Current Practice in Software Process Development
Current practice in software development is an essential part of ensuring the process runs smoothly and correctly. The findings of this pilot study discover that software practitioners apply sustainability practices indirectly in the software development process; for instance, reducing paper usage, writing more effective programming code, and using online data storage space. www.ijacsa.thesai.org

B. Factors and Elements of Green Software Process
The pilot findings show that the green software measurements can be identified as effectiveness, cost reduction, job creation, competitiveness, usability, participation, ecosystem, resource, protection, human health, change, adaptation, endurance, satisfaction, happiness, and skills. The pilot informants propose and agree that these elements are appropriate and applicable for measuring the green software process. Table V signifies the finding of new green factors and their elements through the pilot study. Based on this pilot study has revealed a further aspect, namely technology. The technology factor consists of two separate elements, namely IoT (Internet of Things) and IR 4.0 (Industrial Revolution), that relate to smartphones and automation technology in future software development.

C. Elements of Software Waste
The green process can be achieved through the elimination of waste. Thus, this pilot study has identified software wastes and is consistent with the literature [27,44]; for instance, over-requirement, design, ineffective communication, rework, lack of knowledge, and expertise. These elements of wastes may affect the software development process in terms of budget, time constraint, and duration of completion.
During the pilot study, it discovers that most informants are not familiar with the meaning of software waste. After being explained further, they admit that particular wastes during the software development process include rework, loss of knowledge, and miscommunication. However, all these problems can be solved well and effectively in the end-stage. Furthermore, the pilot study proves the reliability of the protocol and the practicality of the interview instrument. The content of the interview protocol was validated and verified. The pilot study aims to test the questions' content, identify ambiguous questions, and test responses from small selected respondents. At the same time, findings from the pilot study are used to enhance the instrument via improving the questions to be more coherent or readable, accurate, presentable, justifiable, and relevant. Moreover, the time to answer the questionnaire was also identified in preparation for the actual interview session.

VI. CONCLUSION AND FUTURE WORK
This paper has presented the literature review on the green software process, the qualitative interview design, and the pilot findings. The literature study has revealed five primary green factors: resource, people, organisation, technical and environmental. The interview protocol was designed and constructed as discussed in this paper. Later, the pilot study was conducted to test the reliability and practicality of the interview protocol. The pilot analysis discovered the initial elements associated with the green software process. The current green practices in the software development process were identified through this pilot study.
Furthermore, it also discovers the influential green factors of the software process. In addition, this study reveals the relevant software wastes which the pilot informants have identified. For future work, the actual interview sessions are to be conducted until the information obtained is saturated. The data analysis will be performed to finalise the factors, elements, and measurements that will become the Green SoftPro model development input.


Hotel Recognition via Latent Image Embedding

We approach the problem of hotel recognition with deep metric learning. We overview the existing approaches and propose a modification to Contrastive loss called Contrastive-Triplet loss. We construct a robust pipeline for benchmarking metric learning models and perform experiments on Hotels-50K and CUB200 datasets. Contrastive-Triplet loss is shown to achieve better retrieval on Hotels-50k. We open-source our code.

Introduction
In large-scale image-based hotel recognition, the goal is to retrieve hotels from a large database of hotel images. The input is a hotel photo and the retrieved hotel images are expected to be from the same hotel or hotel chain. We approach this task as a deep metric learning problem. In this setting, we train a deep neural network to project images into an informative low-dimension latent space. This space is used for approximate nearest-neighbor retrieval.
The paper is structured in the following way. First we carefully investigate the available approaches. We investigate failure cases of Contrastive and Triplet losses, where they miss out on potentially important information within a triplet. Based on the hypotheses that Triplet loss and Contrastive loss use different information available in a batch we propose the Contrastive-Triplet loss. We construct a benchmarking pipeline for robust model comparisons, ensuring equal conditions for all approaches. The Mean Average Precision at R (MAP@R) metric is used for evaluation. Finally, we experimentally test the proposed approach by comparing the performance of Contrastive-Triplet loss to individual Contrastive and Triplet losses on the CUB200 and Hotels-50k datasets. We finish with a discussion of experimental results. The code for reproducing our experiments is available on Github. 1 Our contributions are two-fold: We find examples where Contrastive and Triplet losses fail to include important information within a batch and formulate the hypothesis that the classic losses use different aspects of similarity.
2. We propose the Contrastive-Triplet loss function which combines Contrastive loss and Triplet loss with no additional computational overhead. 3. For the first time to our knowledge we evaluate a newly proposed Deep Metric Learning approach against the fair benchmarking pipeline by Musgrave et al. [17] and open-source the code for reproduction.
2 Related work (a) Successful retrieval example.
(b) Unsuccessful retrieval example. The tasks of image retrieval, scene recognition and place recognition can be solved using metric learning. Metric learning attempts to map data to an embedding space, where similar data are close together and dissimilar data are far apart. There are two main approaches to deep metric learning: embedding and classification losses.

Classification
In this setting, a classification model is trained using softmax loss and the embeddings produced by the penultimate layer of the model are used.
The first caveat of this approach is that a model trained for classification does not directly optimize for similarity, which sometimes leads to sub-par results. The second caveat is that image retrieval problems tend to have large numbers of semantic labels, which makes it computationally hard to train a classifier model. Despite that, Zhai et al. [27] modify a softmax loss trained classifier for metric learning and show that such approach is very competitive and can be scaled to large numbers of classes.
Deng et al. [3] address the problem that softmax loss does not directly optimize for similarity. They introduce a new loss function ArcFace loss that distributes the data points on a hypersphere. Unlike a generic softmax loss, this loss function directly enforces an angular margin m between embeddings of different classes. Authors achieve great results on face recognition benchmark datasets, which tend to have high inter-class variance and large numbers of clusters.

Embedding losses
In this approach a model is trained to explicitly learn an embedding of data into a latent space, where the similarity is maximized for semantically similar data points and minimized otherwise. This is usually achieved by considering pairs, triplets or N-tuplets of images.
Contrastive loss [6] is a classic approach that had wide adoption. The idea behind it is to analyze pairs of embeddings and penalize the embedder model for images of the same label being too far apart and for images of different labels being too close. While training with Contrastive loss, the loss is computed over pairs of images within a batch. A pair with the same label is called a positive pair. A pair with different labels is called a negative pair. The loss is calculated as follows: Where d p is the distance for the positive pair, d n is the distance for the negative pair, m pos and m neg are hyperparameters, [x] + = max(0, x) is the hinge function.
Another classic approach is Triplet loss [23]. Triplets of images (a, p, n) are selected from each batch, where x a is an anchor image, p has the same label as the anchor, n has a different label. Triplet loss minimizes the anchor-positive pair distance and maximizes the anchor-negative distance, so that the anchorpositive pair is closer than the anchor-negative pair by some margin m triplet : Both Triplet loss and Contrastive loss share the issue of selecting useful triplets or pairs within a batch. The total number of possible triplets in a dataset is O(n 3 ), but only a tiny fraction of these produce useful gradients. Triplet mining aims to select useful triplets for learning.
Xuan et al. [26] show that sampling the easiest positive and semi-hard negative pairs for triplets leads to better results on datasets with high intra-class variance. An easiest positive image is the closest positive to the anchor in the batch. A semi-hard negative is a negative image that is further from the anchor than the positive image, but within the triplet margin. Such selection pushes each image closer to the most similar image of the same class. This reduces the over-clustering problem, when very different images of the same class are mapped to the same place. Authors indicate that mapping each image close to the closest positive leads to better generalization on unseen data.
Movshovitz et al. [16] argue that it's not enough to select useful triplets from each training batch, but careful sampling of batches is a problem as well. To counter the sensitivity to individual triplets picked into the batch, they propose to learn a small set of proxy points P that approximates the original data distribution. In a supervised setting, where all data points are labelled as belonging to a class, a single proxy is used for each class. Authors extend the NCA loss [4] with proxies, proposing the Proxy-NCA loss. This has the additional advantage over Triplet loss as the margin hyperparameter is no longer needed. This approach was extended [25] to ProxyNCA++ later.
Wang et al. [22] claim that different ranking losses take in account different aspects of similarity. Contrastive loss is based on the similarity between the anchor and the negative example. Triplet loss is based on the difference between the anchor-negative similarity and similarity to positive examples. According to the author each method only uses a specific part of information about a tuple. They propose a multi-similarity loss that attempts to capture all of the information at once and claim that it naturally selects harder pairs.

Other approaches
Kim et al. [9] propose an attention-based ensemble model. Multiple attention masks are used after spatial feature extraction, which focuses the model on different regions of the input image. They utilize a divergence loss that promotes each attention mask to learn a different embedding. Similar methods are used for content-based retrieval [21] and automated content editing techniques [5,12].
There were attempts to combine embedding and classification losses for better performance [13]. Jun et al. [8] combine the two major approaches by pre-training a DCNN using a classification loss and then fine-tuning the network using Triplet loss.
An loss-agnostic way to improve model performance is to provide the model more useful training samples. Lin et al. [11] use a generator network to generate hard negative points from easy negatives, so that the whole distribution of negative samples is covered by the network during training. Ko et al. [10] take a different approach for generating hard points: they generate points by linearly interpolating between negative data points during training and picking the hardest point. Other approaches may directly learn metric space transformation via graph embeddings [14,15].

Reality check
Musgrave et al. [17] benchmark the models proposed by numerous metric learning papers and find out that much of the claimed progress in the field was caused by flawed experiments. They find that most methods perform roughly like the classic Contrastive loss, Triplet loss or softmax loss approaches. Most of the gains of recent approaches are explained by using newer backbone DNN architectures, optimizing hyper-parameters on test subsets and using flawed accuracy metrics.

Proposed improvements
After analysing previous works on this topic, we formulated the following hypothesis that could be experimentally tested: embedding losses use different aspects of similarity and current embedding losses do not use all of the available information within a batch.

Contrastive-Triplet loss
To test the hypotheses that different embedding losses use different information in a batch, we engineer some examples where the classic losses could fail.  Example where Triplet loss fails. Consider Triplet loss with m triplet = 0.1 and two triplets with the following distances: d(a 1 , p 1 ) = 0.9, d(a 1 , n 1 ) = 0.9, and d(a 2 , p 2 ) = 0.1, d(a 2 , n 2 ) = 0.1. For both triplets the loss is equal to 0.1, even though they are different. The information about the positive example being very far from the anchor is ignored in the first triplet. This case is illustrated by Figure 2a.
Another failure case of Triplet loss is when a triplet produces no gradients. For example consider a triplet with d(a, p) = 0.3, d(a, n) = 0.4. This is considered an "easy" triplet and produces zero loss, even though the positive example could be pulled closer and the negative could be pushed further away.
Example where Contrastive loss fails. Consider Contrastive loss m pos = 0.2, m neg = 0.5 and pairs with the following distances: d(p 1,1 , p 1,2 ) = 0.4, d(p 1,1 , n 1,1 ) = 0.4, and d(p 2,1 , p 2,2 ) = 0.1, d(p 2,1 , n 2,1 ) = 0.2. For both cases the resulting loss is 0.3, even though in the first case the distances are equal and the example is therefore harder. The information about the relative distance between the positive and the negative examples is ignored. This is illustrated by Figure 2b.
We attempt to create a loss function for which these failure cases are avoided. We propose a new loss function that combines Contrastive and Triplet loss to use more information about the embedding whilst providing no computational overhead.
Consider a triplet (a, p, n). In addition to Triplet loss, we can also calculate the Contrastive loss for the triplet by taking d p = d(a, p) and d n = d(a, n).  By summing these losses, we obtain the Contrastive-Triplet loss: Where α triplet is a hyperparameter weight for the Triplet loss component. The pairwise distances matrix can be reused when computing both loss components, so there is no computation overhead.

Experiments
We follow the fair comparison procedure proposed by Musgrave et al. [17] and use the proposed benchmarker software [18] for our experiments. We ensure that all approaches are tested using the same backbone network, BatchNorm parameters, image augmentation and other conditions. The hyperparameters for each approach are optimized via Bayesian optimization first. We also use cross-validation and multiple reproductions to obtain robust estimates of model performance as well as confidence intervals. We use 25 Bayesian optimization iterations for CUB200 and 10 for Hotels-50k instead of 50 due to computation resource limits and time constraints.

Experiment setup
Experiments use the PyTorch [1] library with the following procedure: -The trunk model is an ImageNet [2] pre-trained BN-Inception [7] network. -The head model is a 1-layer MLP.
-Trunk BatchNorm parameters are frozen during training.
-Batch size is 32. Batches are constructed by sampling 8 classes and randomly sampling 4 images for each class.
-During training, images are first resized so that the shorter side has length 256, then a random crop is made of size between 40 and 256, and aspect ratio between 3/4 and 4/3. Finally, the crop is resized to 227x227, and flipped horizontally with 50% probability. Within each reproduction, for each CV split, we load the best model based on validation set error. We use the best models to obtain train and test set embeddings. We concatenate these embeddings into 512-dim embeddings and L2-normalize them. Using these embeddings we test retrieval and report the mean accuracy and confidence intervals.
For Hotels-50k the procedure has the following differences: -10 iterations of Bayesian optimization are performed.
-Only 500 batches are processed per epoch.
-For each cross-validation fold, the validation fold only has labels that are present in the training set. This is done to mimic the task of the dataset.
Batch-size can have a significant effect on neural networks, but Musgrave et al. [17] demonstrate that increasing batch size from 32 to 256 has little effect to relative rankings of metric learning approaches.

Accuracy metrics
We compare solutions using Mean Average Precision at R (MAP@R). For a given query it's defined as follows: Where P (i) = precision at i if the i-th retrieval is correct and 0 otherwise. R is the total number of references that have the same label as the query.
This metric takes in account both the number of correct retrievals and their ranking. We also provide the commonly used P (1) metric, also called Top-1 Accuracy, for comparison. However it should be noted that the metric can be very high even for poorly-clustered samples, as demonstrated in [17]. For the best hyperparameters, 5 reproduction iterations are run, following the standard cross-validation scheme. For each reproduction the accuracy score is computed. For each CV partition within a reproduction, the highest-accuracy checkpoint is loaded. The 4 models are used to obtain embeddings. For both train and test sets we concatenate the 128-dim embeddings of the 4 models to get 512-dim embeddings, and then L2 normalize them. We test and report the accuracy of retrieval using these embeddings. In the end, we aggregate the scores of reproductions to obtain mean accuracy metrics and confidence intervals.

CUB200 dataset
We benchmark our approaches on CUB200-2011 [24] dataset. The dataset contains photos of birds taken in the wild, with bird species used as labels. It's a commonly used benchmark in metric learning. Just like Hotels-50k, it contains a lot of hard cases of two types: images of the same class that are very different visually, images of different classes that are very similar visually.
In other words, this dataset is notable for high intra-class variance and high similarity between some classes.
The dataset contains 11,788 images distributed between 200 classes. In accordance with previous literature, we use the first 100 classes for the training dataset, and the last 100 classes for the test dataset.

Hotels-50k dataset
Finally, we benchmark on the Hotels-50k [19] dataset. The dataset contains images taken in hotel rooms. Some images are non-professional photos of hotel rooms taken with the TraffickCam app, the rest are professional photos from hotel booking websites. Each photo is labelled with hotel id, hotel chain id and image source (TraffickCam or not). All test images come from TraffickCam, so the task is to identify a hotel or chain given a poor-quality user submitted photo. The dataset provides two tasks: hotel instance recognition and hotel chain recognition. We only approach the hotel chain recognition task.
Due to the large size of the dataset, time and resource constraints, we use a subset of the dataset. For the training set, we remove all hotel chains that have fewer than 100 images and all hotels that have fewer than 10 images. Among the remaining images, we keep only a sample the non-TraffickCam images, such that their number is equal to the number of TraffickCam images. Finally, we remove all hotels from the test set if they are not in the resulting training set.
In the end, the training subset contains 86,936 images from 30,467 hotels of 90 hotel chains. 43,468 images among these come from TraffickCam. The test subset contains 10,900 images from 3,244 hotels of 85 hotel chains. All images in the testing set come from TraffickCam. The final subset we used, as well as the code for recreating it, can is available on Github 2 .
To speed up training on this large dataset, we convert the test and train sets into Lightning Memory Mapped Database [20] binary files storing the following key value pairs: (image index, (image, chain id, hotel id, image source)). LMDB allows multiple concurrent readers to read images from the file. This significantly increases the speed of loading images and training.

Baseline
For comparison, we reproduce the approach used in the original Hotels 50K paper [19]. A neural network is trained using Triplet loss. Batch-hard mining is used: a miner that samples the hardest positive and hardest negative triplet for each anchor. All losses are averaged, including zero values. All other parameters, including backbone network, batch size, embedding dimension and image augmentations, are the same as for other approaches (described in Section 4), to ensure a fair comparison.

Results
The benchmark results can be found in Table 2 and Table 3. The optimal hyperparameters for the CUB200 dataset can be found in Table 1, and for the Hotels-50k dataset in Table 1.
The hypotheses behind Contrastive-Triplet loss was that the different components of the loss might describe different aspects of similarity. If that was true, combining them with optimized hyperparameters would achieved better results. It does not appear to be the case for CUB200. Loss history plots, shown on Figure 3, indicate that adding a Triplet loss component does not significantly affect convergence. The negative loss component does not change with addition of the Triplet loss component. Our experiments show that adding a Triplet loss component to Contrastive loss shifts the positive loss margin towards zero, making the positive loss greater in value, while the Triplet loss margin also shifts towards zero. When m triplet is close to zero, Triplet loss only provides penalties when the positive pair is farther away than the negative pair. In that case Triplet loss component pulls positive examples that are too far away closer to the anchor, almost like positive Contrastive loss. For the CUB200 dataset, a combination of Triplet loss and Contrastive loss achieves the same results as Contrastive loss alone. This leads us to believe that either Triplet loss or Contrastive positive loss are redundant in this case. It should be noted that while Contrastive-Triplet loss does not achieve better results on CUB200, the hyperparameter values are much more stable for it than for Contrastive loss, as shown on Figure 4.
However, the approach does achieve slightly better results on Hotels-50k dataset. This might be explained by the fact that Contrastive-Triplet loss has more stable hyperparameters. Fewer Bayesian optimization iterations were done for Hotels-50k, which could lead to better results for the method that takes less steps to optimize hyperparameters. Examples of retrieval are provided on Figure 1. Overall, qualitative analysis indicates that the embedding produced is densely packed, with the distances between random pairs of images being very small, which leads to a lot of false positives. The network is not able to enforce a large margin between hotel chains.

Conclusion
In this paper we approached the task of hotel recognition. Having reviewed the existing approaches we investigated the failure cases of Contrastive and Triplet losses and proposed the Contrastive-Triplet loss. We constructed a robust experiment pipeline to ensure consistent and reproducible results. Our experiments indicate that Contrastive-Triplet loss doesn't outperform the baseline on CUB200, but achieves better retrieval results on Hotels-50k than baseline Contrastive and Triplet losses.


s2fieldsofstudy:
Computer Science
Mathematics

text:
Safe rules for the identification of zeros in the solutions of the SLOPE problem

In this paper we propose a methodology to accelerate the resolution of the so-called"Sorted L-One Penalized Estimation"(SLOPE) problem. Our method leverages the concept of"safe screening", well-studied in the literature for \textit{group-separable} sparsity-inducing norms, and aims at identifying the zeros in the solution of SLOPE. More specifically, we derive a set of \(\tfrac{n(n+1)}{2}\) inequalities for each element of the \(n\)-dimensional primal vector and prove that the latter can be safely screened if some subsets of these inequalities are verified. We propose moreover an efficient algorithm to jointly apply the proposed procedure to all the primal variables. Our procedure has a complexity \(\mathcal{O}(n\log n + LT)\) where \(T\leq n\) is a problem-dependent constant and \(L\) is the number of zeros identified by the tests. Numerical experiments confirm that, for a prescribed computational budget, the proposed methodology leads to significant improvements of the solving precision.

1. Introduction. During the last decades, sparse linear regression has attracted much attention in the field of statistics, machine learning and inverse problems. It consists in finding an approximation of some input vector y ∈ R m as the linear combination of a few columns of a matrix A ∈ R m×n (often called dictionary). Unfortunately, the general form of this problem is NP-hard and convex relaxations have been proposed in the literature to circumvent this issue. The most popular instance of convex relaxation for sparse linear regression is undoubtedly the so-called "LASSO" problem where the coefficients of the regression are penalized by an 1 norm, see [11]. Generalized versions of LASSO have also been introduced to account for some possible structure in the pattern of the nonzero coefficients of the regression, see [2].
Problem (1.1) is commonly referred to as "Sorted L-One Penalized Estimation" (SLOPE) or "Ordered Weighted L-One Linear Regression" in the literature and has been introduced in two parallel works [5,21]. 1 The first instance of a problem of the form (1.1) (for some nontrivial choice of the parameters γ k 's) is due to Bondell and Reich in [7]. The authors considered a problem similar to (1.1), named "Octagonal Shrinkage and Clustering Algorithm for Regression" (OSCAR), where the regularization function is a linear combination of an 1 norm and a sum of pairwise ∞ norms of the elements of x, that is (1.5) r oscar (x) = β 1 x 1 + β 2 j >j max(|x (j ) |, |x (j) |), for some β 1 ∈ R * + , β 2 ∈ R + . It is not difficult to see that r oscar can be expressed as a particular case of r slope with the following choice γ k = β 1 + β 2 (n − k). We note that some authors have recently considered "group" versions of the SLOPE problem where the ordered 2 norm of subsets of x is penalized by a decreasing sequence of parameters γ k , see e.g., [9,25,26].
SLOPE enjoys several desirable properties which have attracted many researchers during the last decade. First, it was shown in several works that, for some proper choices of parameters γ k 's, SLOPE promotes sparse solutions with some form of "clustering" 2 of the nonzero coefficients, see e.g., [7,21,30,39]. This feature has been exploited in many application domains: portfolio optimization [31,47], genetics [26], magnetic-resonance imaging [16], subspace clustering [38], deep neural networks [49], etc. Moreover, it has been pointed out in a series of works that SLOPE has very good statistical properties: it leads to an improvement of the false detection rate (as compared to LASSO) for moderately-correlated dictionaries [6,25] and is minimax optimal in some asymptotic regimes, see [33,40].
Another desirable feature of SLOPE is its convexity. In particular, it was shown in [6, Proposition 1.1] and [48,Lemma 2] that r slope is a norm as soon as (1.3) holds. As a consequence, several numerical procedures have been proposed in the literature to find the global minimizer(s) of problem (1.1). In [6] and [50], the authors considered an accelerated gradient proximal implementation for SLOPE and OSCAR, respectively. In [31], the authors tackled problem (1.1) via an alternating-direction method of multipliers [8]. An approach based on an augmented Lagrangian method was considered in [35]. In [48], the authors expressed r slope as an atomic norm and particularized a Frank-Wolfe minimization procedure [23] to problem (1.1). An efficient algorithm to compute the Euclidean projection onto the unit ball of the SLOPE norm was provided in [14]. Finally, in [10] a heuristic "message-passing" method was proposed.
In this paper, we introduce a new "safe screening" procedure to accelerate the resolution of SLOPE. The concept of "safe screening" is well known in the LASSO literature: it consists in performing simple tests to identify the zero elements of the minimizers; this knowledge can then be exploited to reduce the problem dimensionality by discarding the columns of the dictionary weighted by the zero coefficients. Safe screening for LASSO has been first introduced by El Ghaoui et al. in the seminal paper [24] and extended to group-separable sparsity-inducing norm in [36]. Safe screening has rapidly been recognized as a simple yet effective procedure to accelerate the resolution of LASSO, see e.g., [12,20,[27][28][29]34,42,43,45]. The term "safe" refers to the fact that all the elements identified by a safe screening procedure are theoretically guaranteed to correspond to zeros of the minimizers. In contrast, unsafe versions of screening for LASSO (often called "strong screening rules") also exist, see [41]. More recently, screening methodologies have been extended to detect saturated components in different convex optimization problems, see [17,18].
In this paper, we derive safe screening rules for SLOPE and emphasize that their implementation enables significant improvements of the solving precision when addressing SLOPE with a prescribed computational budget. We note that the SLOPE norm is not group-separable and the methodology proposed in [36] does therefore not trivially apply here. Prior to this work, we identified two contributions addressing screening for SLOPE. In [32], the authors proposed an extension of the strong screening rules derived in [41] to the SLOPE problem. In [3], the authors suggested a simple test to identify some zeros of the SLOPE solutions. Although the derivations made by these authors have been shown to contain several technical flaws [19], their test can be cast as a particular case of our result in Theorem 4.3 (and is therefore quite unexpectedly safe).
The paper is organized as follows. We introduce the notational conventions used throughout the paper in Section 2 and recall the main concepts of safe screening for LASSO in Section 3. Section 4 contains our proposed safe screening rules for SLOPE. Section 5 illustrates the effectiveness of the proposed approach through numerical simulations. All technical details and mathematical derivations are postponed to Appendices A and B.
2. Notations. Unless otherwise specified, we will use the following conventions throughout the paper. Vectors are denoted by lowercase bold letters (e.g., x) and matrices by uppercase bold letters (e.g., A). The "all-zero" vector of dimension n is written 0 n . We use symbol T to denote the transpose of a vector or a matrix. x (j) refers to the jth component of x. When referring to the sorted entries of a vector, we use bracket subscripts; more precisely, the notation x [k] refers to the kth largest value of x. For matrices, we use a j to denote the jth column of A. We use the notation |x| to denote the vector made up of the absolute value of the components of x. The sign function is defined for all scalars x as sign (x) = x/|x| with the convention sign (x) = 0. Calligraphic letters are used to denote sets (e.g., J ) and card ( · ) refers to their cardinality. If a < b are two integers, a, b is used as a shorthand notation for the set {a, a + 1, . . . , b}. Given a vector x ∈ R n and a set of indices J ⊆ 1, n , we let x J be the vector of components of x with indices in J . Similarly, A J denotes the submatrix of A whose columns have indices in J . A \ corresponds to matrix A deprived of its th column.
3. Screening: main concepts. "Safe screening" has been introduced by El Ghaoui et al. in [24] for 1 -penalized problems: where f : R m → R is a closed convex function. It is grounded on the following ideas. First, it is well-known that 1 -regularization favors sparsity of the minimizers of (3.1). For instance, if f = 1 2 · 2 2 and the solution of (3.1) is unique, it can be shown that the minimizer contains at most m nonzero coefficients, see e.g., [22,Theorem 3.1]. Second, if some zeros of the minimizers are identified, (3.1) can be shown to be equivalent to a problem of reduced dimension. More precisely, let L ⊆ 1, n be a set of indices such that we have for any minimizer x of (3.1): and letL = 1, n \L. Then the following problem admits the same optimal value as (3.1) and there exists a simple bijection between the minimizers of (3.1) and (3.3). We note that x belongs to an n-dimensional space whereas z is a card(L)-dimensional vector. Hence, solving (3.3) rather than (3.1) may lead to dramatic memory and computational savings if card(L) n. The crux of screening consists therefore in identifying (some) zeros of the minimizers of (3.1) with marginal cost. El Ghaoui et al. emphasized that this is possible by relaxing some primal-dual optimality condition of problem (3.1). More precisely, let be the dual problem of (3.1), where f * denotes the Fenchel conjugate. Then, by complementary slackness, we must have for any minimizer x of (3.1): Since dual feasibility imposes that |a T u | ≤ λ, we obtain the following implication: Hence, if u is available, the left-hand side of (3.6) can be used to detect if the th component of x is equal to zero. Unfortunately, finding a maximizer of dual problem (3.4) is generally as difficult as solving primal problem (3.1). This issue can nevertheless be circumvented by identifying some region R of the dual space (commonly referred to as "safe region") such that u ∈ R. Indeed, since the left-hand side of (3.7) constitutes an alternative (weaker) test to detect the zeros of x . For proper choices of R, the maximization over u admits a simple analytical solution. For example, if R is a ball, that is then max u∈R |a T u| = |a T c| + R a 2 and the relaxation of (3.7) leads to In this case, the screening test is straightforward to implement since it only requires the evaluation of one inner product between a and c. 3 Many procedures have been proposed in the literature to construct safe spheres [20,36,46] or safe regions with refined geometries [12,42,44,45]. If f * is a ζ-strongly convex function, a popular approach to construct a safe region is the so-called "GAP sphere" [36] whose center and radius are defined as follows: where (x, u) is any primal-dual feasible couple. This approach has gained in popularity because of its good behavior when (x, u) is close to optimality. In particular, if f is proper lower semi-continuous, x = x and u = u , then P (x) − D(u) = 0 by strong duality [4,Proposition 15.22]. In this case, screening test (3.9) reduces to (3.6) and, except in some degenerated cases, all the zero components of x can be identified by the screening test. Interestingly, this behavior also provably occurs for sufficiently small values of the dual gap [37, Propositions 8 and 9] and has been observed in many numerical experiments, see e.g., [17,20,28,36]. As a final remark, let us mention that the framework presented in this section extends to optimization problems where the (sparsity-promoting) penalty function describes a group-separable norm, see e.g., [13,36]. In particular, the complementary slackness condition (3.5) still holds (up to a minor modification), thus allowing to design safe screening tests based on the same rationale. We note that, since the SLOPE penalization does not feature such a separability property, the methodology presented in this section does unfortunately not apply.
4. Safe screening rules for SLOPE. In this section, we propose a new procedure to extend the concept of safe screening to SLOPE. Our exposition is organized as follows. In Subsection 4.1 we describe our working assumptions and in Subsection 4.2 we present a family of screening tests for SLOPE (see Theorem 4.3). Each test is defined by a set of parameters {p q } q∈ 1,n and takes the form of a series of inequalities. We show that a simple test of the form (3.9) can be recovered for some particular values of the parameters {p q } q∈ 1,n , although this choice does not correspond to the most effective test in the general case. In Subsection 4.3, we finally propose an efficient numerical procedure to verify simultaneously all the proposed screening tests.

Working hypotheses.
In this section, we present two working assumptions which are assumed to hold in the rest of the paper even when not explicitly mentioned.
We first suppose that the regularization parameter λ satisfies In particular, the hypothesis λ max > 0 is tantamount to assuming that y / ∈ ker(A T ). On the other hand, λ < λ max prevents the vector 0 n from being a minimizer of the SLOPE problem (1.1). More precisely, it can be shown that under condition (1.3), (4.2) λ and {γ k } n k=1 verify (4.1) ⇐⇒ 0 n is not a minimizer of (1.1).
A proof of this result is provided in Appendix A.2.
Second, we assume that the columns of the dictionary A are unit-norm, i.e., Assumption (4.3) simplifies the statement of our results in the next subsection. However, all our subsequent derivations can be easily extended to the general case where (4.3) does not hold.

Safe screening rules.
In this section, we derive a family of safe screening rules for SLOPE.
Let us first note that (1.1) admits at least one minimizer and our screening problem is therefore well-posed. Indeed, the primal cost function in (1.1) is continuous and coercive since r slope is a norm (see e.g., [6, Proposition 1.1] or [48, Lemma 2]); the existence of a minimizer then follows from Weierstrass theorem [4,Theorem 1.29]. In the following, we will assume that the minimizer is unique to simplify our statements. Nevertheless, all our results extend to the general case where there exist more than one minimizer by replacing "x ( ) = 0" by "x ( ) = 0 for any minimizer of (1.1)" in all our subsequent statements.
Our starting point to derive our safe screening rules is the following primal-dual optimality condition: Then, for all integers ∈ 1, n : A proof of this result is provided in Appendix B.1. We mention that, although it differs quite significantly in its formulation, Theorem 4.1 is closely related to [32, Proposition 1]. 4 We also note that (4.4) corresponds to the dual problem of (1.1), see e.g., [6, Section 2.5]. Moreover, u exists and is unique because D is a continuous strongly-concave function and U a closed set. The equality in (4.4) is therefore welldefined. Theorem 4.1 provides a condition similar to (3.6) relating the dual optimal solution u to the zero components of the primal minimizer x . Unfortunately, evaluating the dual solution u requires a computational load comparable to the one needed to solve the SLOPE problem (1.1). Similarly to 1 -penalized problems, tractable screening rules can nevertheless be devised if "easily-computable" upper bounds on the left-hand side of (4.6) can be found. In particular, for any set {B q, ∈ R} q∈ 1,n verifying we readily have that The next lemma provides several instances of such upper bounds: Let u ∈ S(c, R). Then ∀ ∈ 1, n and ∀q ∈ 1, n , we have that A proof of this result is available in Appendix B.2. We note that Lemma 4.2 defines one particular family of upper bounds on the left-hand side of (4.7). The derivation of these upper bounds is based on the knowledge of a safe spherical region and partially exploits the definition of the dual feasible set, see Appendix B.2. We nevertheless emphasize that other choices of safe regions or majorization techniques can be envisioned and possibly lead to more favorable upper bounds. Defining a straightforward particularization of (4.8) then leads to the following safe screening rules for SLOPE: Let {p q } q∈ 1,n be a sequence such that p q ∈ 1, q for all q ∈ 1, n . Then, the following statement holds: We mention that the notation "p q " is here introduced to stress the fact that a different value of p can be used for each q in (4.10). Since q ∈ 1, n and each parameter p q can take on q different values in Theorem 4.3, (4.10) thus defines n! different screening tests for SLOPE where n(n+1) 2 distinct inequalities are involved. We discuss two particular choices of parameters {p q } q∈ 1,n below and propose an efficient procedure to jointly evaluate all the tests defined by feasible sequences {p q } q∈ 1,n in the next section.
Let us first consider the case where (4.11) ∀q ∈ 1, n : p q = 1. Screening test (4.10) then particularizes as Interestingly, (4.12) shares the same mathematical structure as optimality condition (4.6). In particular, (4.12) reduces to (4.6) when c = u and R = 0. In this case, it is easy to see that (4.12) is the best 5 screening test within the family of tests defined in Theorem 4.3 since an equality occurs in (4.7). In practice, we may expect this conclusion to remain valid when R is "sufficiently" close to zero. This behavior is illustrated in Figure 1. The figure represents the proportion of zeros entries of x detected by screening test (4.10) for different "qualities" of the safe region and different choices of parameters {p q } q∈ 1,n . We refer the reader to Subsection 5.1 for a detailed description of the simulation setup. The center of the safe sphere used to apply (4.10) is assumed to be equal (up to machine precision) to u and the x-axis of the figure represents the radius R of the sphere region. The green curve corresponds to test (4.12); the orange curve represents the screening performance achieved when test (4.10) is implemented for all possible choices for {p q } q∈ 1,n . We note that, as expected, the green curve attains the best screening performance as soon as R becomes close to zero.
At the other extreme of the spectrum, another case of interest reads as: Using our initial hypothesis (1.3), the screening test (4.10) rewrites 6 (4.14) Interestingly, this test has the same mathematical structure as (3.9) with the exception that λ is multiplied by the value of the smallest weighting coefficient γ n . In particular, if γ k = 1 ∀k ∈ 1, n SLOPE reduces to LASSO and test (4.14) is equivalent to (3.9); Theorem 4.3 thus encompasses standard screening rule (3.9) for LASSO as a particular case. The following result emphasizes that (4.14) is in fact the best screening rule within the family of tests defined by Theorem 4.3 when γ k = 1 ∀k ∈ 1, n : Lemma 4.4. If γ k = 1 ∀k ∈ 1, n and test (4.10) passes for some choice of parameters {p q } q∈ 1,n , then test (4.14) also succeeds.
A proof of this result is available in Appendix B.3.
As a final remark, let us mention that, although we just emphasized that some choices of parameters {p q } q∈ 1,n can be optimal (in terms of screening performance) in some situations, no conclusion can be drawn in the general case. In particular, we found in our numerical experiments that the best choice for {p q } q∈ 1,n depends on many factors: the weights {γ k } n k=1 , the radius of the safe sphere R, the nature of the dictionary, the atom to screen, etc. This is illustrated in Fig. 1: we see that the blue and green curves deviate from the orange curve for certain values of R, that is the best screening performance is not necessarily achieved for p q = 1 or p q = q ∀q ∈ 1, n .

Efficient implementation.
Since the best values for {p q } q∈ 1,n cannot be foreseen, it is desirable to evaluate the screening rule (4.10) for any choice of these parameters. Formally, this ideal test reads: Since verifying this test for a given index involves the evaluation of O(n 2 ) inequalities, a brute-force evaluation of (4.15) for all atoms of the dictionary requires O(n 3 ) operations. In this section, we present a procedure to perform this task with a complexity scaling as O(n log n + T L) where T ≤ n is some problem-dependent constant (to be defined later on) and L is the number of atoms of the dictionary passing test (4.15). Our procedure is summarized in Algorithms 4.1 and 4.2, and is grounded on the following nesting properties.
Nesting of the tests for different atoms. We first emphasize that there exists an implication between the failures of test (4.15) for some group of indices. In particular, the following result holds:  Then ∀q ∈ 1, n : A proof of this result is provided in Appendix B.4. Lemma 4.5 has the following consequence: if (4.16) holds, the failure of test (4.15) for some ∈ 2, n implies the failure of the test for any index ∈ 1, − 1 . This immediately suggests a backward strategy for the evaluation of (4.15), starting from = n and going backward to smaller indices. This is the sense of the main recursion in Algorithm 4.1.
We note that hypothesis (4.16) can always be verified by a proper reordering of the elements of |A T c|. This can be achieved by state-of-the-art sorting procedures with a complexity of O(n log n). Therefore, in the sequel we will assume that (4.16) holds even if not explicitly mentioned.
Nesting of some inequalities. We next show that the number of inequalities to be verified may possibly be substantially smaller than O(n 2 ). We first focus on the case " = n" and then extend our result to the general case " < n".
Let us first note that under hypothesis (4.16): that is the kth largest element of |A T \n c| is simply equal to its kth component. The particularization of (4.15) to = n can then be rewritten as: (4.19) ∀q ∈ 1, n , ∃p q ∈ 1, q : a T n c < τ q,pq where τ q,p is defined ∀q ∈ 1, n and p ∈ 1, q as We show hereafter that (4.19) can be verified by only considering a "well-chosen" subset of thresholds T ⊆ {τ q,p : q ∈ 1, n , p ∈ 1, q }, see Lemma 4.6 below. If a T n c < τ q,p (q) ⇐⇒ ∃p q ∈ 1, q : a T n c < τ q,pq .
In other words, for each q ∈ 1, n , satisfying the inequality " a T n c < τ q,p " for p = p (q) is necessary and sufficient to ensure that it is verified for some p q ∈ 1, q .
Motivated by this observation, we show the following items below: i) p (q) can be evaluated ∀q ∈ 1, n with a complexity O(n); ii) similarly to p, only a subset of values of q ∈ 1, n are of interest to implement (4.19).
Let us define the function: We then have ∀q ∈ 1, n and p ∈ 1, q : In view of (4.24), the optimal value p (q) can be computed as Considering (4.23), we see that the evaluation of g(p) ∀p ∈ 1, n (and therefore p (q) ∀q ∈ 1, n ) can be done with a complexity scaling as O(n). This proves item i).
Let us now show that only some specific indices q ∈ 1, n are of interest to implement (4.19). Let (4.26) q (k) arg max and define the sequence {q (t) } t as where the recursion is applied as long as p (q (t−1) ) > 1. 7 We then have the following result whose proof is available in Appendix B.5:  ∀τ ∈ T : |a T n c| < τ.
Lemma 4.6 suggests the procedure described in Algorithm 4.2 (with = n) to verify if (4.19) is passed. In a nutshell, the lemma states that only card(T ) inequalities need to be taken into account to implement (4.19). We note that card(T ) ≤ n since only one value of p (that is p (q)) has to be considered for any q ∈ 1, n . This is in contrast with a brute-force evaluation of (4.19) which requires the verification of O(n 2 ) inequalities. We finally emphasize that the procedure described in Algorithm 4.2 also applies to < n as long as the screening test is passed for all > . More specifically, if test (4.15) is passed for all ∈ + 1, n , then its particularization to atom a reads (4.29) ∀τ ∈ T : a T c < τ for some T ⊆ T . Indeed, if screening test (4.15) is passed for all ∈ + 1, n , the corresponding elements can be discarded from the dictionary and we obtain a reduced problem only involving atoms {a } ∈ 1, . Since (4.16) is assumed to hold, a attains the smallest absolute inner product with c and we end up with the same setup as in the case " = n". In particular, if screening test (4.15) is passed for all ∈ + 1, n , Lemma 4.6 still holds for a by letting q (1) = q ( ) in the definition of the sequence {q (t) } t in (4.27).
To conclude this section, let us summarize the complexity needed to implement Algorithms 4.1 and 4.2. First, Algorithm 4.1 requires the entries |A T c| to be sorted to satisfy hypothesis (4.5). This involves a complexity O(n log n). Moreover, the sequences {g(p)} n p=1 , {p (q)} n q=1 , {q (k)} n k=1 can be evaluated with a complexity O(n). Finally, the main recursion in Algorithm 4.1 implies to run Algorithm 4.2 L times, where L is the number of atoms passing test (4.15). Since Algorithm 4.2 requires to verify at most T = card (T ) inequalities, the overall complexity of the main recursion scales as O(LT ). Overall, the complexity of Algorithm 4.1 is therefore O(n log n+LT ).

Numerical simulations.
We present hereafter several simulation results demonstrating the effectiveness of the proposed screening procedure to accelerate the resolution of SLOPE. This section is organized as follows. In Subsection 5.1, we present the experimental setups considered in our simulations. In Subsection 5.2 we compare the effectiveness of different screening strategies. In Subsection 5.3, we show that our methodology enables to reach better convergence properties for a given computational budget.

Experimental setup. We detail below the experimental setups used in all our numerical experiments.
Dictionaries and observation vectors: New realizations of A and y are drawn for each trial as follows. The observation vector is generated according to a uniform distribution on the m-dimensional sphere. The elements of A obey one of the following models: 1. the entries are i.i.d. realizations of a centered Gaussian, 2. the entries are i.i.d. realizations of a uniform distribution on [0, 1], 3. the columns are shifted versions of a Gaussian curve. For all distributions, the columns of A are normalized to have unit 2 -norm. In the following, these three options will be respectively referred to as "Gaussian", "Uniform" and "Toeplitz".

Performance of screening strategies.
We first compare the effectiveness of different screening strategies described in Section 4. More specifically, we evaluate the proportion of zero entries in x -the solution of SLOPE problem (1.1) -that can be identified by tests (4.12), (4.14) and (4.15) as a function of the "quality" of the safe sphere. These tests will respectively be referred to as "test-p=1", "test-p=q" and "test-all" in the following. Figures 1 (see Subsection 4.2) and 2 represent this criterion of performance as a function of some parameter R 0 (described below) and different values of the ratio λ/λ max . The results are averaged over 50 realizations. For each simulation trial, we draw a new realization of y ∈ R 100 and A ∈ R 100×300 according to the distributions described in Subsection 5.1. We consider Toeplitz dictionaries in Figure 1 and Gaussian dictionaries in Figure 2.
The safe sphere used in the screening tests is constructed as follows. A primaldual solution (x a , u a ) of problems (1.1) and (4.4) is evaluated with "high-accuracy", i.e., with a duality GAP of 10 −14 as stopping criterion. More precisely, x a is first evaluated by solving the SLOPE problem (1.1) with the algorithm proposed in [5]. To evaluate u a , we extend the so-called "dual scaling" operator [24,Section 3.3] to the SLOPE problem: we let u a = (y − Ax a )/β(y − Ax a ) where The couple (x a , u a ) is then used to construct a sphere S(c a , R a ) in R m whose parameters are given by where R 0 is a nonnegative scalar. We note that for R 0 = 0, the latter sphere corresponds to the GAP safe sphere described in (3.10). 8 Hence, (5.3a) and (5.3b) define a safe sphere for any choice of the nonnegative scalar R 0 ≥ 0. Figure 1 concentrates on the sequence OSCAR-1 whereas each subfigure corresponds to a different choice for {γ k } n k=1 in Figure 2. For the three considered screening strategies, we observe that the detection performance decreases as R 0 increases. Interestingly, different behaviors can be noticed. For all simulation setups, test-p=1 reaches a detection rate of 100% whenever R 0 is sufficiently small. The performance of test-p=q varies from one sequence to another: it outperforms test-p=1 for OSCAR-1, is able to detect at most 20% of the zeros for OSCAR-2 and fail for all values of R 0 for OSCAR-3. Finally, test-all outperforms quite logically the two other strategies. The gap in performance depends on both the considered setup and the radius R 0 but can be quite significant in some cases. For example, when λ/λ max = 0.5 and R 0 = 10 −2 , there is 80% more entries passing test-all than test-p=1 for all parameter sequences.
These results may be explained as follows. First, we already mentioned in Section 4 that when the radius of the safe sphere is sufficiently small (that is, when R 0 is close to zero), test-p=1 is expected to be the best 9 screening test within the family of tests defined in Theorem 4.3. Similarly, if the SLOPE weights satisfy γ 1 = γ n , we showed in Lemma 4.4 that no test in Theorem 4.3 can outperform test-p=q. Hence, one may reasonably expect that this conclusion remains valid whenever γ 1 γ n , as observed for the sequence OSCAR-1 in our simulations. On the other hand, passing test-p=q becomes more difficult as parameter γ n is small. As a matter of fact, the test will never pass when γ n = 0. In our experiments, the sequences {γ k } n k=1 are such that γ n is close to zero for OSCAR-2 and OSCAR-3. Finally, since test-all encompasses the two other tests, it is expected to always perform at least as well as the latter.

Benchmarks.
As far as our simulation setup is concerned, the results presented in the previous section show a significant advantage in implementing test-all in terms of detection performance. However, this conclusion does not include any consideration about the numerical complexity of the tests. We note that, although the proposed screening rules can lead to a significant reduction of the problem dimen-sions, our tests also induce some additional computational burden. In particular, we emphasized in Subsection 4.3 that test-all can be verified for all atoms of the dictionary with a complexity O(n log n + T L) where T ≤ n is a problem-dependent parameter and L is the number of atoms passing the test. Moreover, we also note that, as far as a GAP safe sphere is considered in the implementation of the tests, its construction requires the identification of a dual feasible point u and this operation typically induces a computational overhead of O(n log n) (see below for more details).
In this section, we therefore investigate the benefits (from a "complexity-accuracy trade-off" point of view) of interleaving the proposed safe screening methodology with the iterations of an accelerated proximal gradient algorithm [5]. In all our tests, we consider the GAP safe sphere defined in (3.10). The primal point used in the construction of the GAP sphere corresponds to the current iterate of the solving procedure, say x (t) . A dual feasible point u (t) is constructed as where β : R m → R m is either defined as in (5.2) or as follows: λγ k .
(5.2) matches the standard definition of the "dual scaling" operator proposed in [24, Section 3.3] whereas (5.5) corresponds to the option considered in [3]. 10 We notice that the two options require to sort the elements of A T z and thus lead to a complexity overhead scaling as O(n log n).
In our simulations, we consider the four following solving strategies: 1. Run the proximal gradient procedure [5] with no screening. These strategies will respectively be denoted "PG-no", "PG-p=q", "PG-Bao" and "PG-all" in the sequel. We note that PG-Bao closely matches the solving procedure considered in [3]. We compare the performance of these solving strategies by resorting to Dolan-Moré profiles [15]. More precisely, we run each procedure for a given budget of time (that is the algorithm is stopped after a predefined amount of time) on I = 50 different instances of the SLOPE problems. In PG-p=q, PG-Bao and PG-all, the screening procedure is applied once every 20 iterations. Each problem instance is generated by drawing a new dictionary A ∈ R 100×300 and observation vector y ∈ R 100 according to the distributions described in Subsection 5.1. We then compute the following performance profile for each solver solv ∈ {PG-no, PG-p=q, PG-Bao, PG-all}: where d i,solv denotes the dual gap attained by solver solv for problem instance i. ρ solv (δ) thus represents the (empirical) probability that solver solv reaches a dual gap no greater than δ for the considered budget of time. Figure 3 presents the performance profiles obtained for three types of dictionaries (Gaussian, Uniform and Toeplitz) and three different weighting sequences {γ k } n k=1 (OSCAR-1, OSCAR-2 and OSCAR-3). The results are displayed for λ/λ max = 0.5 but similar performance profiles have been obtained for other values of the ratio λ/λ max . All algorithms are implemented in Python with Cython bindings and experiments are run on a Dell laptop, 1.80 GHz, Intel Core i7. For each setup, we adjusted the time budget so that ρ PG-all (10 −8 ) 50% for the sake of comparison.
As far as our simulation setup is concerned, these results show that the proposed screening methodologies improve the solving accuracy as compared to a standard proximal gradient. PG-all improves the average accuracy over PG-no in all the considered settings. The gap in performance depends on the setup but is generally quite significant. PG-p=q also enhances the average accuracy in most cases and performs at least comparably to PG-Bao in all setups. As expected, the behavior of PG-p=q and PG-Bao is more sensitive to the choice of the weighting sequence {γ k } n k=1 . In particular, the screening performance of these strategies decreases when γ n 0 as emphasized in Subsection 5.2. This results in no accuracy gain over PG-no for the sequence OSCAR-3 as illustrated in Figure 3. Nevertheless, we note that, even in absence of gain, PG-p=q and PG-Bao do not seem to significantly degrade the performance as compared to PG-no.
6. Conclusions. In this paper we proposed a new methodology to safely identify the zeros of the solutions of the SLOPE problem. In particular, we introduced a family of screening rules indexed by some parameters {p q } n q=1 where n is the dimension of the primal variable. Each test of this family takes the form of a series of n inequalities which, when verified, imply the nullity of some coefficient of the minimizers. Interestingly, the proposed tests encompass standard "sphere" screening rule for LASSO as a particular case for some {p q } n q=1 , although this choice does not correspond to the most effective test in the general case. We then introduced an efficient numerical procedure to jointly evaluate all the tests in the proposed family. Our algorithm has a complexity O(n log n + T L) where T ≤ n is some problem-dependent constant and L is the number of elements passing at least one test of the family. We finally assessed the performance of our screening strategy through numerical simulations and showed that the proposed methodology leads to significant improvements of the solving accuracy for a prescribed computational budget. A.1. Some results of convex analysis. We remind below several results of convex analysis that will be used in our subsequent derivations. The first lemma provides a necessary and sufficient condition for x ∈ R n to be a minimizer of the SLOPE problem (1.1): Lemma A.1 follows from a direct application of Fermat's rule [4,Proposition 16.4] to problem (1.1). We note that under condition (1.3), r slope defines a norm on R n , see e.g., [6,Proposition 1.1] or [48,Lemma 2]. The subdifferential ∂r slope (x) is therefore well defined for all x ∈ R n and writes as (A.1) ∂r slope (x) = g ∈ R n : g T x = r slope (x) and r slope, * (g) ≤ 1 , where (A.2) r slope, * (g) sup is the dual norm of r slope , see e.g., [1,Eq. (1.4)].
The next lemma states a technical result which will be useful in the proof of Theorem 4.1 in Appendix B: Lemma A.2. If g ∈ ∂r slope (x), then x T (g−g ) ≥ 0 ∀g ∈ R n s.t. r slope, * (g ) ≤ 1.
Proof. Let g ∈ ∂r slope (x). One has where r * slope refers to the Fenchel conjugate of r slope . The first equivalence is a consequence of [4,Theorem 16.29] and the second of the definition of the subdifferential set. Lemma A.2 follows by noticing that r * slope (g ) = 0 ∀g ∈ R n such that r slope, * (g ) ≤ 1 by property of r * slope [4,Item (v) of Example 13.3].
In the last lemma of this section, we provide a closed-form expression of the subdifferential and the dual norm of r slope : 11 Lemma A.3. The dual norm and the subdifferential of r slope (x) respectively write: ∂r slope (x) = g ∈ R n : g T x = r slope (x) and ∀q ∈ 1, n : Proof. The expression of the dual norm is a direct consequence of [48,Lemma 4]. More precisely, the authors showed that where V q 1 q k=1 γ k s : s ∈ {0, −1, +1} n , card {j : s (j) = 0} = q for all q ∈ 1, n . The expression of r slope, * given in Lemma A.3 is a compact rewriting of (A.4) that can be obtained as follows. See first that for all q ∈ 1, n , Second, for q ∈ 1, n , let J q ⊂ 1, n be a set q distinct indices such that |g (j) | ≥ |g| [q] for all j ∈ J q . Then, the upper bound in (A.5) is attained by evaluating the left-hand side at v ∈ V q defined as The expression of the subdifferential follows from (A.1) by plugging the expression of the dual norm in the inequality "r slope, * (g) ≤ 1".
A.2. Proof of (4.2). We first observe that (A.7) 0 n is not a minimizer of (1.1) ⇐⇒ λ −1 A T y / ∈ ∂r slope (0 n ), as a direct consequence of Lemma A.1. Particularizing the expression of ∂r slope (x) in Lemma A.3 to x = 0 n , the right-hand side of (A.7) can equivalently be rewritten as Since γ 1 > 0 and the sequence {γ k } n k=1 is nonnegative by hypothesis (1.3), (A.8) can also be rewritten as The statement in (4.2) then follows by noticing that the right-hand side of (4.1) is a compact reformulation of (A.9).
Appendix B. Proofs related to screening tests.
B.1. Proof of Theorem 4.1. In this section, we provide the technical details leading to (4.6). Our derivation leverages the Fermat's rule and the expression of the subdifferential derived in Lemma A.3.
We prove (4.6) by contraposition. More precisely, we show that if x ( ) = 0 for some ∈ 1, n , then Using Lemma A.1 and the following connection between primal-dual solutions (see [6, Section 2.5]) we have that x is a minimizer of (1.1) if and only if In the rest of the proof, we will use Lemma A.2 with x = x , g = g and different instances of vector g to prove our statement. First, let us define g ∈ R n as It is easy to verify that r slope, * (g ) ≤ 1. Applying Lemma A.2 then leads to Since x ( ) is assumed to be nonzero, we then have where the equality holds if and only if g ( ) = 0. Second, let us consider the following choice for g ∈ R n : and δ is any nonnegative scalar such that (B.8) r slope, * (g ) ≤ 1.
On the one hand, we note that (B.8) is verified for δ = 0. On the other hand, it can be seen that (B.8) is violated as soon as δ > 0 by using the following arguments. Let us next emphasize that the range of values for q 0 can be restricted by choosing some suitable value for δ. In particular, define q 0 ∈ 1, n as q 0 min q ∈ 1, n : |g ( ) | = |g | [q] (B.12) and let with the convention g [0] = +∞. Considering g as defined in (B.6) with δ satisfying (B.13), we have that the first q 0 − 1 largest absolute elements of g and g are the same. Since r slope, * (g ) ≤ 1, the inequality in the right-hand side of (B.10) can therefore not be verified for q 0 ∈ 1, q 0 − 1 . Hence, considering δ as in (B.13), we have (B.14) ∃q 0 ∈ q 0 , n : We finally obtain our original assertion (B.1) by using the definition of g in (B.3) and the fact that B.2. Proof of Lemma 4.2. We first state and prove the following technical lemma: Lemma B.1. Let g ∈ R n and h ∈ R n be such that g (j) ≤ h (j) ∀j ∈ 1, n . Then Proof. Let k ∈ 1, n . We have by definition where the inequality follows from our assumption g (j) ≤ h (j) ∀j ∈ 1, n .
We are now ready to prove Lemma 4.2. For any p ∈ 1, q , we can write: First, since u is dual feasible, we have: We next show that if u ∈ S(c, R), then We then obtain the result stated in the lemma by combining (B. 18 .
Combining these results leads to B.3. Proof of Lemma 4.4. We want to show that if test (4.10) is passed for some {p q } q∈ 1,n , then test (4.14) is also passed when γ k = 1 ∀k ∈ 1, n .
Since γ k = 1 ∀k ∈ 1, n by hypothesis, the latter inequality is equal to (4.14) and the result is proved.
B.4. Proof of Lemma 4.5. We prove the result by showing that ∀q ∈ 1, n the sequence {B q, } ∈ 1,n is non-increasing. To this end, we first rewrite B q, in a slightly different manner, easier to analyze. Let (B.26) C q,p (q − p + 1)R + λ p−1 k=1 γ k ∀q ∈ 1, n , ∀p ∈ 1, q σ q q k=1 |a T k c| ∀q ∈ 0, n with the convention σ 0 0. Using these notations and hypothesis (4.16), B q, can be rewritten as (B.28) We next show that ∀q ∈ 1, n the sequence {B q, } ∈ 1,n is non-increasing. We first notice that C q,p does not depend on and we can therefore focus on (B.28) to prove our claim. Using the fact that |a T c| ≥ |a T +1 c| by hypothesis, we immediately obtain that B q, ≥ B q, +1 whenever / ∈ {p − 1, q}. We conclude the proof by treating the cases " = p − 1" and " = q" separately.
If = q we have from (B.28): where the last inequality holds true by virtue of (4.16). If = p − 1 (and provided that p ≥ 2) the same rationale leads to (B.30) B q, +1 − B q, = |a T p c| − |a T p−1 c| ≤ 0.
B.5. Proof of Lemma 4.6. The necessity of (4.28) can be shown as follows. Assume |a T n c| ≥ τ for some τ ∈ T and let q ∈ 1, n be such that τ = τ q,p (q) . From (4.22) we then have (B. 31) ∀p ∈ 1, q : |a T n c| ≥ τ q,p and test (4.19) therefore fails.